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