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