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 } 602