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 signed numbers,
 200          * but in the portable proplib we changed it to be human readable.
 201          */
 202         if (pn->pn_value.pnv_is_unsigned)
 203                 sprintf(tmpstr, "%" PRIu64, pn->pn_value.pnv_unsigned);
 204         else
 205                 sprintf(tmpstr, "%" PRIi64, pn->pn_value.pnv_signed);
 206
 207         if (_prop_object_externalize_start_tag(ctx, "integer") == false ||
 208             _prop_object_externalize_append_cstring(ctx, tmpstr) == false ||
 209             _prop_object_externalize_end_tag(ctx, "integer") == false)
 210                 return (false);
 211
 212         return (true);
 213 }
 214
 215 /* ARGSUSED */
 216 static _prop_object_equals_rv_t
 217 _prop_number_equals(prop_object_t v1, prop_object_t v2,
 218     void **stored_pointer1, void **stored_pointer2,
 219     prop_object_t *next_obj1, prop_object_t *next_obj2)
 220 {
 221         prop_number_t num1 = v1;
 222         prop_number_t num2 = v2;
 223
 224         /*
 225          * There is only ever one copy of a number object at any given
 226          * time, so we can reduce this to a simple pointer equality check
 227          * in the common case.
 228          */
 229         if (num1 == num2)
 230                 return (_PROP_OBJECT_EQUALS_TRUE);
 231
 232         /*
 233          * If the numbers are the same signed-ness, then we know they
 234          * cannot be equal because they would have had pointer equality.
 235          */
 236         if (num1->pn_value.pnv_is_unsigned == num2->pn_value.pnv_is_unsigned)
 237                 return (_PROP_OBJECT_EQUALS_FALSE);
 238
 239         /*
 240          * We now have one signed value and one unsigned value.  We can
 241          * compare them iff:
 242          *      - The unsigned value is not larger than the signed value
 243          *        can represent.
 244          *      - The signed value is not smaller than the unsigned value
 245          *        can represent.
 246          */
 247         if (num1->pn_value.pnv_is_unsigned) {
 248                 /*
 249                  * num1 is unsigned and num2 is signed.
 250                  */
 251                 if (num1->pn_value.pnv_unsigned > INT64_MAX)
 252                         return (_PROP_OBJECT_EQUALS_FALSE);
 253                 if (num2->pn_value.pnv_signed < 0)
 254                         return (_PROP_OBJECT_EQUALS_FALSE);
 255         } else {
 256                 /*
 257                  * num1 is signed and num2 is unsigned.
 258                  */
 259                 if (num1->pn_value.pnv_signed < 0)
 260                         return (_PROP_OBJECT_EQUALS_FALSE);
 261                 if (num2->pn_value.pnv_unsigned > INT64_MAX)
 262                         return (_PROP_OBJECT_EQUALS_FALSE);
 263         }
 264
 265         if (num1->pn_value.pnv_signed == num2->pn_value.pnv_signed)
 266                 return _PROP_OBJECT_EQUALS_TRUE;
 267         else
 268                 return _PROP_OBJECT_EQUALS_FALSE;
 269 }
 270
 271 static prop_number_t
 272 _prop_number_alloc(const struct _prop_number_value *pnv)
 273 {
 274         prop_number_t opn, pn, rpn;
 275
 276         _PROP_ONCE_RUN(_prop_number_init_once, _prop_number_init);
 277
 278         /*
 279          * Check to see if this already exists in the tree.  If it does,
 280          * we just retain it and return it.
 281          */
 282         _PROP_MUTEX_LOCK(_prop_number_tree_mutex);
 283         opn = _prop_rb_tree_find(&_prop_number_tree, pnv);
 284         if (opn != NULL) {
 285                 prop_object_retain(opn);
 286                 _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
 287                 return (opn);
 288         }
 289         _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
 290
 291         /*
 292          * Not in the tree.  Create it now.
 293          */
 294
 295         pn = _PROP_POOL_GET(_prop_number_pool);
 296         if (pn == NULL)
 297                 return (NULL);
 298
 299         _prop_object_init(&pn->pn_obj, &_prop_object_type_number);
 300
 301         pn->pn_value = *pnv;
 302
 303         /*
 304          * We dropped the mutex when we allocated the new object, so
 305          * we have to check again if it is in the tree.
 306          */
 307         _PROP_MUTEX_LOCK(_prop_number_tree_mutex);
 308         opn = _prop_rb_tree_find(&_prop_number_tree, pnv);
 309         if (opn != NULL) {
 310                 prop_object_retain(opn);
 311                 _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
 312                 _PROP_POOL_PUT(_prop_number_pool, pn);
 313                 return (opn);
 314         }
 315         rpn = _prop_rb_tree_insert_node(&_prop_number_tree, pn);
 316         _PROP_ASSERT(rpn == pn);
 317         _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
 318         return (pn);
 319 }
 320
 321 /*
 322  * prop_number_create_integer --
 323  *      Create a prop_number_t and initialize it with the
 324  *      provided integer value.
 325  */
 326 prop_number_t
 327 prop_number_create_integer(int64_t val)
 328 {
 329         struct _prop_number_value pnv;
 330
 331         memset(&pnv, 0, sizeof(pnv));
 332         pnv.pnv_signed = val;
 333         pnv.pnv_is_unsigned = false;
 334
 335         return (_prop_number_alloc(&pnv));
 336 }
 337
 338 /*
 339  * prop_number_create_unsigned_integer --
 340  *      Create a prop_number_t and initialize it with the
 341  *      provided unsigned integer value.
 342  */
 343 prop_number_t
 344 prop_number_create_unsigned_integer(uint64_t val)
 345 {
 346         struct _prop_number_value pnv;
 347
 348         memset(&pnv, 0, sizeof(pnv));
 349         pnv.pnv_unsigned = val;
 350         pnv.pnv_is_unsigned = true;
 351
 352         return (_prop_number_alloc(&pnv));
 353 }
 354
 355 /*
 356  * prop_number_copy --
 357  *      Copy a prop_number_t.
 358  */
 359 prop_number_t
 360 prop_number_copy(prop_number_t opn)
 361 {
 362
 363         if (! prop_object_is_number(opn))
 364                 return (NULL);
 365
 366         /*
 367          * Because we only ever allocate one object for any given
 368          * value, this can be reduced to a simple retain operation.
 369          */
 370         prop_object_retain(opn);
 371         return (opn);
 372 }
 373
 374 /*
 375  * prop_number_unsigned --
 376  *      Returns true if the prop_number_t has an unsigned value.
 377  */
 378 bool
 379 prop_number_unsigned(prop_number_t pn)
 380 {
 381
 382         return (pn->pn_value.pnv_is_unsigned);
 383 }
 384
 385 /*
 386  * prop_number_size --
 387  *      Return the size, in bits, required to hold the value of
 388  *      the specified number.
 389  */
 390 int
 391 prop_number_size(prop_number_t pn)
 392 {
 393         struct _prop_number_value *pnv;
 394
 395         if (! prop_object_is_number(pn))
 396                 return (0);
 397
 398         pnv = &pn->pn_value;
 399
 400         if (pnv->pnv_is_unsigned) {
 401                 if (pnv->pnv_unsigned > UINT32_MAX)
 402                         return (64);
 403                 if (pnv->pnv_unsigned > UINT16_MAX)
 404                         return (32);
 405                 if (pnv->pnv_unsigned > UINT8_MAX)
 406                         return (16);
 407                 return (8);
 408         }
 409
 410         if (pnv->pnv_signed > INT32_MAX || pnv->pnv_signed < INT32_MIN)
 411                 return (64);
 412         if (pnv->pnv_signed > INT16_MAX || pnv->pnv_signed < INT16_MIN)
 413                 return (32);
 414         if (pnv->pnv_signed > INT8_MAX  || pnv->pnv_signed < INT8_MIN)
 415                 return (16);
 416         return (8);
 417 }
 418
 419 /*
 420  * prop_number_integer_value --
 421  *      Get the integer value of a prop_number_t.
 422  */
 423 int64_t
 424 prop_number_integer_value(prop_number_t pn)
 425 {
 426
 427         /*
 428          * XXX Impossible to distinguish between "not a prop_number_t"
 429          * XXX and "prop_number_t has a value of 0".
 430          */
 431         if (! prop_object_is_number(pn))
 432                 return (0);
 433
 434         return (pn->pn_value.pnv_signed);
 435 }
 436
 437 /*
 438  * prop_number_unsigned_integer_value --
 439  *      Get the unsigned integer value of a prop_number_t.
 440  */
 441 uint64_t
 442 prop_number_unsigned_integer_value(prop_number_t pn)
 443 {
 444
 445         /*
 446          * XXX Impossible to distinguish between "not a prop_number_t"
 447          * XXX and "prop_number_t has a value of 0".
 448          */
 449         if (! prop_object_is_number(pn))
 450                 return (0);
 451
 452         return (pn->pn_value.pnv_unsigned);
 453 }
 454
 455 /*
 456  * prop_number_equals --
 457  *      Return true if two numbers are equivalent.
 458  */
 459 bool
 460 prop_number_equals(prop_number_t num1, prop_number_t num2)
 461 {
 462         if (!prop_object_is_number(num1) || !prop_object_is_number(num2))
 463                 return (false);
 464
 465         return (prop_object_equals(num1, num2));
 466 }
 467
 468 /*
 469  * prop_number_equals_integer --
 470  *      Return true if the number is equivalent to the specified integer.
 471  */
 472 bool
 473 prop_number_equals_integer(prop_number_t pn, int64_t val)
 474 {
 475
 476         if (! prop_object_is_number(pn))
 477                 return (false);
 478
 479         if (pn->pn_value.pnv_is_unsigned &&
 480             (pn->pn_value.pnv_unsigned > INT64_MAX || val < 0))
 481                 return (false);
 482
 483         return (pn->pn_value.pnv_signed == val);
 484 }
 485
 486 /*
 487  * prop_number_equals_unsigned_integer --
 488  *      Return true if the number is equivalent to the specified
 489  *      unsigned integer.
 490  */
 491 bool
 492 prop_number_equals_unsigned_integer(prop_number_t pn, uint64_t val)
 493 {
 494
 495         if (! prop_object_is_number(pn))
 496                 return (false);
 497
 498         if (! pn->pn_value.pnv_is_unsigned &&
 499             (pn->pn_value.pnv_signed < 0 || val > INT64_MAX))
 500                 return (false);
 501
 502         return (pn->pn_value.pnv_unsigned == val);
 503 }
 504
 505 static bool
 506 _prop_number_internalize_unsigned(struct _prop_object_internalize_context *ctx,
 507                                   struct _prop_number_value *pnv)
 508 {
 509         char *cp;
 510
 511         _PROP_ASSERT(/*CONSTCOND*/sizeof(unsigned long long) ==
 512                      sizeof(uint64_t));
 513
 514 #ifndef _KERNEL
 515         errno = 0;
 516 #endif
 517         pnv->pnv_unsigned = (uint64_t) strtoull(ctx->poic_cp, &cp, 0);
 518 #ifndef _KERNEL         /* XXX can't check for ERANGE in the kernel */
 519         if (pnv->pnv_unsigned == UINT64_MAX && errno == ERANGE)
 520                 return (false);
 521 #endif
 522         pnv->pnv_is_unsigned = true;
 523         ctx->poic_cp = cp;
 524
 525         return (true);
 526 }
 527
 528 static bool
 529 _prop_number_internalize_signed(struct _prop_object_internalize_context *ctx,
 530                                 struct _prop_number_value *pnv)
 531 {
 532         char *cp;
 533
 534         _PROP_ASSERT(/*CONSTCOND*/sizeof(long long) == sizeof(int64_t));
 535
 536 #ifndef _KERNEL
 537         errno = 0;
 538 #endif
 539         pnv->pnv_signed = (int64_t) strtoll(ctx->poic_cp, &cp, 0);
 540 #ifndef _KERNEL         /* XXX can't check for ERANGE in the kernel */
 541         if ((pnv->pnv_signed == INT64_MAX || pnv->pnv_signed == INT64_MIN) &&
 542             errno == ERANGE)
 543                 return (false);
 544 #endif
 545         pnv->pnv_is_unsigned = false;
 546         ctx->poic_cp = cp;
 547
 548         return (true);
 549 }
 550
 551 /*
 552  * _prop_number_internalize --
 553  *      Parse a <number>...</number> and return the object created from
 554  *      the external representation.
 555  */
 556 /* ARGSUSED */
 557 bool
 558 _prop_number_internalize(prop_stack_t stack, prop_object_t *obj,
 559     struct _prop_object_internalize_context *ctx)
 560 {
 561         struct _prop_number_value pnv;
 562
 563         memset(&pnv, 0, sizeof(pnv));
 564
 565         /* No attributes, no empty elements. */
 566         if (ctx->poic_tagattr != NULL || ctx->poic_is_empty_element)
 567                 return (true);
 568
 569         /*
 570          * If the first character is '-', then we treat as signed.
 571          * If the first two characters are "0x" (i.e. the number is
 572          * in hex), then we treat as unsigned.  Otherwise, we try
 573          * signed first, and if that fails (presumably due to ERANGE),
 574          * then we switch to unsigned.
 575          */
 576         if (ctx->poic_cp[0] == '-') {
 577                 if (_prop_number_internalize_signed(ctx, &pnv) == false)
 578                         return (true);
 579         } else if (ctx->poic_cp[0] == '0' && ctx->poic_cp[1] == 'x') {
 580                 if (_prop_number_internalize_unsigned(ctx, &pnv) == false)
 581                         return (true);
 582         } else {
 583                 if (_prop_number_internalize_signed(ctx, &pnv) == false &&
 584                     _prop_number_internalize_unsigned(ctx, &pnv) == false)
 585                         return (true);
 586         }
 587
 588         if (_prop_object_internalize_find_tag(ctx, "integer",
 589                                               _PROP_TAG_TYPE_END) == false)
 590                 return (true);
 591
 592         *obj = _prop_number_alloc(&pnv);
 593         return (true);
 594 }