src/prop_number.c

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