sys/libprop/prop_number.c

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