src/prop_number.c

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