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