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