src/prop_number.c

   1 /*      $NetBSD: prop_number.c,v 1.23 2010/09/24 22:51:52 rmind Exp $   */
   2
   3 /*-
   4  * Copyright (c) 2006 The NetBSD Foundation, Inc.
   5  * All rights reserved.
   6  *
   7  * This code is derived from software contributed to The NetBSD Foundation
   8  * by Jason R. Thorpe.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
  20  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  21  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  22  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
  23  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  24  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  25  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  26  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  27  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  28  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  29  * POSSIBILITY OF SUCH DAMAGE.
  30  */
  31
  32 #include <prop/prop_number.h>
  33 #include "prop_object_impl.h"
  34 #include "prop_rb_impl.h"
  35
  36 #if defined(_KERNEL)
  37 #include <sys/systm.h>
  38 #elif defined(_STANDALONE)
  39 #include <sys/param.h>
  40 #include <lib/libkern/libkern.h>
  41 #else
  42 #include <errno.h>
  43 #include <stdlib.h>
  44 #define __unused        /* empty */
  45 #endif
  46
  47 struct _prop_number {
  48         struct _prop_object     pn_obj;
  49         struct rb_node          pn_link;
  50         struct _prop_number_value {
  51                 union {
  52                         int64_t  pnu_signed;
  53                         uint64_t pnu_unsigned;
  54                 } pnv_un;
  55 #define pnv_signed      pnv_un.pnu_signed
  56 #define pnv_unsigned    pnv_un.pnu_unsigned
  57                 unsigned int    pnv_is_unsigned :1,
  58                                                 :31;
  59         } pn_value;
  60 };
  61
  62 _PROP_POOL_INIT(_prop_number_pool, sizeof(struct _prop_number), "propnmbr")
  63
  64 static _prop_object_free_rv_t
  65                 _prop_number_free(prop_stack_t, prop_object_t *);
  66 static bool     _prop_number_externalize(
  67                                 struct _prop_object_externalize_context *,
  68                                 void *);
  69 static _prop_object_equals_rv_t
  70                 _prop_number_equals(prop_object_t, prop_object_t,
  71                                     void **, void **,
  72                                     prop_object_t *, prop_object_t *);
  73
  74 static void _prop_number_lock(void);
  75 static void _prop_number_unlock(void);
  76
  77 static const struct _prop_object_type _prop_object_type_number = {
  78         .pot_type       =       PROP_TYPE_NUMBER,
  79         .pot_free       =       _prop_number_free,
  80         .pot_extern     =       _prop_number_externalize,
  81         .pot_equals     =       _prop_number_equals,
  82         .pot_lock       =       _prop_number_lock,
  83         .pot_unlock     =       _prop_number_unlock,
  84 };
  85
  86 #define prop_object_is_number(x)        \
  87         ((x) != NULL && (x)->pn_obj.po_type == &_prop_object_type_number)
  88
  89 /*
  90  * Number objects are immutable, and we are likely to have many number
  91  * objects that have the same value.  So, to save memory, we unique'ify
  92  * numbers so we only have one copy of each.
  93  */
  94
  95 static int
  96 _prop_number_compare_values(const struct _prop_number_value *pnv1,
  97                             const struct _prop_number_value *pnv2)
  98 {
  99
 100         /* Signed numbers are sorted before unsigned numbers. */
 101
 102         if (pnv1->pnv_is_unsigned) {
 103                 if (! pnv2->pnv_is_unsigned)
 104                         return (1);
 105                 if (pnv1->pnv_unsigned < pnv2->pnv_unsigned)
 106                         return (-1);
 107                 if (pnv1->pnv_unsigned > pnv2->pnv_unsigned)
 108                         return (1);
 109                 return (0);
 110         }
 111
 112         if (pnv2->pnv_is_unsigned)
 113                 return (-1);
 114         if (pnv1->pnv_signed < pnv2->pnv_signed)
 115                 return (-1);
 116         if (pnv1->pnv_signed > pnv2->pnv_signed)
 117                 return (1);
 118         return (0);
 119 }
 120
 121 static int
 122 /*ARGSUSED*/
 123 _prop_number_rb_compare_nodes(void *ctx __unused,
 124                               const void *n1, const void *n2)
 125 {
 126         const struct _prop_number *pn1 = n1;
 127         const struct _prop_number *pn2 = n2;
 128
 129         return _prop_number_compare_values(&pn1->pn_value, &pn2->pn_value);
 130 }
 131
 132 static int
 133 /*ARGSUSED*/
 134 _prop_number_rb_compare_key(void *ctx __unused, const void *n, const void *v)
 135 {
 136         const struct _prop_number *pn = n;
 137         const struct _prop_number_value *pnv = v;
 138
 139         return _prop_number_compare_values(&pn->pn_value, pnv);
 140 }
 141
 142 static const rb_tree_ops_t _prop_number_rb_tree_ops = {
 143         .rbto_compare_nodes = _prop_number_rb_compare_nodes,
 144         .rbto_compare_key = _prop_number_rb_compare_key,
 145         .rbto_node_offset = offsetof(struct _prop_number, pn_link),
 146         .rbto_context = NULL
 147 };
 148
 149 static struct rb_tree _prop_number_tree;
 150 _PROP_MUTEX_DECL_STATIC(_prop_number_tree_mutex)
 151
 152 /* ARGSUSED */
 153 static _prop_object_free_rv_t
 154 _prop_number_free(prop_stack_t stack, prop_object_t *obj)
 155 {
 156         prop_number_t pn = *obj;
 157
 158         _prop_rb_tree_remove_node(&_prop_number_tree, pn);
 159
 160         _PROP_POOL_PUT(_prop_number_pool, pn);
 161
 162         return (_PROP_OBJECT_FREE_DONE);
 163 }
 164
 165 _PROP_ONCE_DECL(_prop_number_init_once)
 166
 167 static int
 168 _prop_number_init(void)
 169 {
 170
 171         _PROP_MUTEX_INIT(_prop_number_tree_mutex);
 172         _prop_rb_tree_init(&_prop_number_tree, &_prop_number_rb_tree_ops);
 173         return 0;
 174 }
 175
 176 static void
 177 _prop_number_lock(void)
 178 {
 179         /* XXX: init necessary? */
 180         _PROP_ONCE_RUN(_prop_number_init_once, _prop_number_init);
 181         _PROP_MUTEX_LOCK(_prop_number_tree_mutex);
 182 }
 183
 184 static void
 185 _prop_number_unlock(void)
 186 {
 187         _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
 188 }
 189
 190 static bool
 191 _prop_number_externalize(struct _prop_object_externalize_context *ctx,
 192                          void *v)
 193 {
 194         prop_number_t pn = v;
 195         char tmpstr[32];
 196
 197         /*
 198          * For the record:
 199          * the original NetBSD implementation used hexadecimal for unsigned
 200          * numbers, but in the portable proplib we changed it to be human
 201          * readable (base 10).
 202          */
 203         if (pn->pn_value.pnv_is_unsigned)
 204                 sprintf(tmpstr, "%" PRIu64, pn->pn_value.pnv_unsigned);
 205         else
 206                 sprintf(tmpstr, "%" PRIi64, pn->pn_value.pnv_signed);
 207
 208         if (_prop_object_externalize_start_tag(ctx, "integer") == false ||
 209             _prop_object_externalize_append_cstring(ctx, tmpstr) == false ||
 210             _prop_object_externalize_end_tag(ctx, "integer") == false)
 211                 return (false);
 212
 213         return (true);
 214 }
 215
 216 /* ARGSUSED */
 217 static _prop_object_equals_rv_t
 218 _prop_number_equals(prop_object_t v1, prop_object_t v2,
 219     void **stored_pointer1, void **stored_pointer2,
 220     prop_object_t *next_obj1, prop_object_t *next_obj2)
 221 {
 222         prop_number_t num1 = v1;
 223         prop_number_t num2 = v2;
 224
 225         /*
 226          * There is only ever one copy of a number object at any given
 227          * time, so we can reduce this to a simple pointer equality check
 228          * in the common case.
 229          */
 230         if (num1 == num2)
 231                 return (_PROP_OBJECT_EQUALS_TRUE);
 232
 233         /*
 234          * If the numbers are the same signed-ness, then we know they
 235          * cannot be equal because they would have had pointer equality.
 236          */
 237         if (num1->pn_value.pnv_is_unsigned == num2->pn_value.pnv_is_unsigned)
 238                 return (_PROP_OBJECT_EQUALS_FALSE);
 239
 240         /*
 241          * We now have one signed value and one unsigned value.  We can
 242          * compare them iff:
 243          *      - The unsigned value is not larger than the signed value
 244          *        can represent.
 245          *      - The signed value is not smaller than the unsigned value
 246          *        can represent.
 247          */
 248         if (num1->pn_value.pnv_is_unsigned) {
 249                 /*
 250                  * num1 is unsigned and num2 is signed.
 251                  */
 252                 if (num1->pn_value.pnv_unsigned > INT64_MAX)
 253                         return (_PROP_OBJECT_EQUALS_FALSE);
 254                 if (num2->pn_value.pnv_signed < 0)
 255                         return (_PROP_OBJECT_EQUALS_FALSE);
 256         } else {
 257                 /*
 258                  * num1 is signed and num2 is unsigned.
 259                  */
 260                 if (num1->pn_value.pnv_signed < 0)
 261                         return (_PROP_OBJECT_EQUALS_FALSE);
 262                 if (num2->pn_value.pnv_unsigned > INT64_MAX)
 263                         return (_PROP_OBJECT_EQUALS_FALSE);
 264         }
 265
 266         if (num1->pn_value.pnv_signed == num2->pn_value.pnv_signed)
 267                 return _PROP_OBJECT_EQUALS_TRUE;
 268         else
 269                 return _PROP_OBJECT_EQUALS_FALSE;
 270 }
 271
 272 static prop_number_t
 273 _prop_number_alloc(const struct _prop_number_value *pnv)
 274 {
 275         prop_number_t opn, pn, rpn;
 276
 277         _PROP_ONCE_RUN(_prop_number_init_once, _prop_number_init);
 278
 279         /*
 280          * Check to see if this already exists in the tree.  If it does,
 281          * we just retain it and return it.
 282          */
 283         _PROP_MUTEX_LOCK(_prop_number_tree_mutex);
 284         opn = _prop_rb_tree_find(&_prop_number_tree, pnv);
 285         if (opn != NULL) {
 286                 prop_object_retain(opn);
 287                 _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
 288                 return (opn);
 289         }
 290         _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
 291
 292         /*
 293          * Not in the tree.  Create it now.
 294          */
 295
 296         pn = _PROP_POOL_GET(_prop_number_pool);
 297         if (pn == NULL)
 298                 return (NULL);
 299
 300         _prop_object_init(&pn->pn_obj, &_prop_object_type_number);
 301
 302         pn->pn_value = *pnv;
 303
 304         /*
 305          * We dropped the mutex when we allocated the new object, so
 306          * we have to check again if it is in the tree.
 307          */
 308         _PROP_MUTEX_LOCK(_prop_number_tree_mutex);
 309         opn = _prop_rb_tree_find(&_prop_number_tree, pnv);
 310         if (opn != NULL) {
 311                 prop_object_retain(opn);
 312                 _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
 313                 _PROP_POOL_PUT(_prop_number_pool, pn);
 314                 return (opn);
 315         }
 316         rpn = _prop_rb_tree_insert_node(&_prop_number_tree, pn);
 317         _PROP_ASSERT(rpn == pn);
 318         _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
 319         return (pn);
 320 }
 321
 322 /*
 323  * prop_number_create_integer --
 324  *      Create a prop_number_t and initialize it with the
 325  *      provided integer value.
 326  */
 327 prop_number_t
 328 prop_number_create_integer(int64_t val)
 329 {
 330         struct _prop_number_value pnv;
 331
 332         memset(&pnv, 0, sizeof(pnv));
 333         pnv.pnv_signed = val;
 334         pnv.pnv_is_unsigned = false;
 335
 336         return (_prop_number_alloc(&pnv));
 337 }
 338
 339 /*
 340  * prop_number_create_unsigned_integer --
 341  *      Create a prop_number_t and initialize it with the
 342  *      provided unsigned integer value.
 343  */
 344 prop_number_t
 345 prop_number_create_unsigned_integer(uint64_t val)
 346 {
 347         struct _prop_number_value pnv;
 348
 349         memset(&pnv, 0, sizeof(pnv));
 350         pnv.pnv_unsigned = val;
 351         pnv.pnv_is_unsigned = true;
 352
 353         return (_prop_number_alloc(&pnv));
 354 }
 355
 356 /*
 357  * prop_number_copy --
 358  *      Copy a prop_number_t.
 359  */
 360 prop_number_t
 361 prop_number_copy(prop_number_t opn)
 362 {
 363
 364         if (! prop_object_is_number(opn))
 365                 return (NULL);
 366
 367         /*
 368          * Because we only ever allocate one object for any given
 369          * value, this can be reduced to a simple retain operation.
 370          */
 371         prop_object_retain(opn);
 372         return (opn);
 373 }
 374
 375 /*
 376  * prop_number_unsigned --
 377  *      Returns true if the prop_number_t has an unsigned value.
 378  */
 379 bool
 380 prop_number_unsigned(prop_number_t pn)
 381 {
 382
 383         return (pn->pn_value.pnv_is_unsigned);
 384 }
 385
 386 /*
 387  * prop_number_size --
 388  *      Return the size, in bits, required to hold the value of
 389  *      the specified number.
 390  */
 391 int
 392 prop_number_size(prop_number_t pn)
 393 {
 394         struct _prop_number_value *pnv;
 395
 396         if (! prop_object_is_number(pn))
 397                 return (0);
 398
 399         pnv = &pn->pn_value;
 400
 401         if (pnv->pnv_is_unsigned) {
 402                 if (pnv->pnv_unsigned > UINT32_MAX)
 403                         return (64);
 404                 if (pnv->pnv_unsigned > UINT16_MAX)
 405                         return (32);
 406                 if (pnv->pnv_unsigned > UINT8_MAX)
 407                         return (16);
 408                 return (8);
 409         }
 410
 411         if (pnv->pnv_signed > INT32_MAX || pnv->pnv_signed < INT32_MIN)
 412                 return (64);
 413         if (pnv->pnv_signed > INT16_MAX || pnv->pnv_signed < INT16_MIN)
 414                 return (32);
 415         if (pnv->pnv_signed > INT8_MAX  || pnv->pnv_signed < INT8_MIN)
 416                 return (16);
 417         return (8);
 418 }
 419
 420 /*
 421  * prop_number_integer_value --
 422  *      Get the integer value of a prop_number_t.
 423  */
 424 int64_t
 425 prop_number_integer_value(prop_number_t pn)
 426 {
 427
 428         /*
 429          * XXX Impossible to distinguish between "not a prop_number_t"
 430          * XXX and "prop_number_t has a value of 0".
 431          */
 432         if (! prop_object_is_number(pn))
 433                 return (0);
 434
 435         return (pn->pn_value.pnv_signed);
 436 }
 437
 438 /*
 439  * prop_number_unsigned_integer_value --
 440  *      Get the unsigned integer value of a prop_number_t.
 441  */
 442 uint64_t
 443 prop_number_unsigned_integer_value(prop_number_t pn)
 444 {
 445
 446         /*
 447          * XXX Impossible to distinguish between "not a prop_number_t"
 448          * XXX and "prop_number_t has a value of 0".
 449          */
 450         if (! prop_object_is_number(pn))
 451                 return (0);
 452
 453         return (pn->pn_value.pnv_unsigned);
 454 }
 455
 456 /*
 457  * prop_number_equals --
 458  *      Return true if two numbers are equivalent.
 459  */
 460 bool
 461 prop_number_equals(prop_number_t num1, prop_number_t num2)
 462 {
 463         if (!prop_object_is_number(num1) || !prop_object_is_number(num2))
 464                 return (false);
 465
 466         return (prop_object_equals(num1, num2));
 467 }
 468
 469 /*
 470  * prop_number_equals_integer --
 471  *      Return true if the number is equivalent to the specified integer.
 472  */
 473 bool
 474 prop_number_equals_integer(prop_number_t pn, int64_t val)
 475 {
 476
 477         if (! prop_object_is_number(pn))
 478                 return (false);
 479
 480         if (pn->pn_value.pnv_is_unsigned &&
 481             (pn->pn_value.pnv_unsigned > INT64_MAX || val < 0))
 482                 return (false);
 483
 484         return (pn->pn_value.pnv_signed == val);
 485 }
 486
 487 /*
 488  * prop_number_equals_unsigned_integer --
 489  *      Return true if the number is equivalent to the specified
 490  *      unsigned integer.
 491  */
 492 bool
 493 prop_number_equals_unsigned_integer(prop_number_t pn, uint64_t val)
 494 {
 495
 496         if (! prop_object_is_number(pn))
 497                 return (false);
 498
 499         if (! pn->pn_value.pnv_is_unsigned &&
 500             (pn->pn_value.pnv_signed < 0 || val > INT64_MAX))
 501                 return (false);
 502
 503         return (pn->pn_value.pnv_unsigned == val);
 504 }
 505
 506 static bool
 507 _prop_number_internalize_unsigned(struct _prop_object_internalize_context *ctx,
 508                                   struct _prop_number_value *pnv)
 509 {
 510         char *cp;
 511
 512         _PROP_ASSERT(/*CONSTCOND*/sizeof(unsigned long long) ==
 513                      sizeof(uint64_t));
 514
 515 #ifndef _KERNEL
 516         errno = 0;
 517 #endif
 518         pnv->pnv_unsigned = (uint64_t) strtoull(ctx->poic_cp, &cp, 0);
 519 #ifndef _KERNEL         /* XXX can't check for ERANGE in the kernel */
 520         if (pnv->pnv_unsigned == UINT64_MAX && errno == ERANGE)
 521                 return (false);
 522 #endif
 523         pnv->pnv_is_unsigned = true;
 524         ctx->poic_cp = cp;
 525
 526         return (true);
 527 }
 528
 529 static bool
 530 _prop_number_internalize_signed(struct _prop_object_internalize_context *ctx,
 531                                 struct _prop_number_value *pnv)
 532 {
 533         char *cp;
 534
 535         _PROP_ASSERT(/*CONSTCOND*/sizeof(long long) == sizeof(int64_t));
 536
 537 #ifndef _KERNEL
 538         errno = 0;
 539 #endif
 540         pnv->pnv_signed = (int64_t) strtoll(ctx->poic_cp, &cp, 0);
 541 #ifndef _KERNEL         /* XXX can't check for ERANGE in the kernel */
 542         if ((pnv->pnv_signed == INT64_MAX || pnv->pnv_signed == INT64_MIN) &&
 543             errno == ERANGE)
 544                 return (false);
 545 #endif
 546         pnv->pnv_is_unsigned = false;
 547         ctx->poic_cp = cp;
 548
 549         return (true);
 550 }
 551
 552 /*
 553  * _prop_number_internalize --
 554  *      Parse a <number>...</number> and return the object created from
 555  *      the external representation.
 556  */
 557 /* ARGSUSED */
 558 bool
 559 _prop_number_internalize(prop_stack_t stack, prop_object_t *obj,
 560     struct _prop_object_internalize_context *ctx)
 561 {
 562         struct _prop_number_value pnv;
 563
 564         memset(&pnv, 0, sizeof(pnv));
 565
 566         /* No attributes, no empty elements. */
 567         if (ctx->poic_tagattr != NULL || ctx->poic_is_empty_element)
 568                 return (true);
 569
 570         /*
 571          * If the first character is '-', then we treat as signed.
 572          * If the first two characters are "0x" (i.e. the number is
 573          * in hex), then we treat as unsigned.  Otherwise, we try
 574          * signed first, and if that fails (presumably due to ERANGE),
 575          * then we switch to unsigned.
 576          */
 577         if (ctx->poic_cp[0] == '-') {
 578                 if (_prop_number_internalize_signed(ctx, &pnv) == false)
 579                         return (true);
 580         } else if (ctx->poic_cp[0] == '0' && ctx->poic_cp[1] == 'x') {
 581                 if (_prop_number_internalize_unsigned(ctx, &pnv) == false)
 582                         return (true);
 583         } else {
 584                 if (_prop_number_internalize_signed(ctx, &pnv) == false &&
 585                     _prop_number_internalize_unsigned(ctx, &pnv) == false)
 586                         return (true);
 587         }
 588
 589         if (_prop_object_internalize_find_tag(ctx, "integer",
 590                                               _PROP_TAG_TYPE_END) == false)
 591                 return (true);
 592
 593         *obj = _prop_number_alloc(&pnv);
 594         return (true);
 595 }