prop_dictionary.c revision 1.19
1 /* $NetBSD: prop_dictionary.c,v 1.19 2007/08/16 21:44:07 joerg Exp $ */ 2 3 /*- 4 * Copyright (c) 2006, 2007 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_array.h> 40 #include <prop/prop_dictionary.h> 41 #include <prop/prop_string.h> 42 #include "prop_object_impl.h" 43 #include "prop_rb_impl.h" 44 45 #if !defined(_KERNEL) && !defined(_STANDALONE) 46 #include <errno.h> 47 #endif 48 49 /* 50 * We implement these like arrays, but we keep them sorted by key. 51 * This allows us to binary-search as well as keep externalized output 52 * sane-looking for human eyes. 53 */ 54 55 #define EXPAND_STEP 16 56 57 /* 58 * prop_dictionary_keysym_t is allocated with space at the end to hold the 59 * key. This must be a regular object so that we can maintain sane iterator 60 * semantics -- we don't want to require that the caller release the result 61 * of prop_object_iterator_next(). 62 * 63 * We'd like to have some small'ish keysym objects for up-to-16 characters 64 * in a key, some for up-to-32 characters in a key, and then a final bucket 65 * for up-to-128 characters in a key (not including NUL). Keys longer than 66 * 128 characters are not allowed. 67 */ 68 struct _prop_dictionary_keysym { 69 struct _prop_object pdk_obj; 70 size_t pdk_size; 71 struct rb_node pdk_link; 72 char pdk_key[1]; 73 /* actually variable length */ 74 }; 75 76 #define RBNODE_TO_PDK(n) \ 77 ((struct _prop_dictionary_keysym *) \ 78 ((uintptr_t)n - offsetof(struct _prop_dictionary_keysym, pdk_link))) 79 80 /* pdk_key[1] takes care of the NUL */ 81 #define PDK_SIZE_16 (sizeof(struct _prop_dictionary_keysym) + 16) 82 #define PDK_SIZE_32 (sizeof(struct _prop_dictionary_keysym) + 32) 83 #define PDK_SIZE_128 (sizeof(struct _prop_dictionary_keysym) + 128) 84 85 #define PDK_MAXKEY 128 86 87 _PROP_POOL_INIT(_prop_dictionary_keysym16_pool, PDK_SIZE_16, "pdict16") 88 _PROP_POOL_INIT(_prop_dictionary_keysym32_pool, PDK_SIZE_32, "pdict32") 89 _PROP_POOL_INIT(_prop_dictionary_keysym128_pool, PDK_SIZE_128, "pdict128") 90 91 struct _prop_dict_entry { 92 prop_dictionary_keysym_t pde_key; 93 prop_object_t pde_objref; 94 }; 95 96 struct _prop_dictionary { 97 struct _prop_object pd_obj; 98 _PROP_RWLOCK_DECL(pd_rwlock) 99 struct _prop_dict_entry *pd_array; 100 unsigned int pd_capacity; 101 unsigned int pd_count; 102 int pd_flags; 103 104 uint32_t pd_version; 105 }; 106 107 #define PD_F_IMMUTABLE 0x01 /* dictionary is immutable */ 108 109 _PROP_POOL_INIT(_prop_dictionary_pool, sizeof(struct _prop_dictionary), 110 "propdict") 111 _PROP_MALLOC_DEFINE(M_PROP_DICT, "prop dictionary", 112 "property dictionary container object") 113 114 static int _prop_dictionary_free(prop_stack_t, prop_object_t *); 115 static void _prop_dictionary_emergency_free(prop_object_t); 116 static bool _prop_dictionary_externalize( 117 struct _prop_object_externalize_context *, 118 void *); 119 static bool _prop_dictionary_equals(void *, void *); 120 121 static const struct _prop_object_type _prop_object_type_dictionary = { 122 .pot_type = PROP_TYPE_DICTIONARY, 123 .pot_free = _prop_dictionary_free, 124 .pot_emergency_free = _prop_dictionary_emergency_free, 125 .pot_extern = _prop_dictionary_externalize, 126 .pot_equals = _prop_dictionary_equals, 127 }; 128 129 static int _prop_dict_keysym_free(prop_stack_t, prop_object_t *); 130 static bool _prop_dict_keysym_externalize( 131 struct _prop_object_externalize_context *, 132 void *); 133 static bool _prop_dict_keysym_equals(void *, void *); 134 135 static const struct _prop_object_type _prop_object_type_dict_keysym = { 136 .pot_type = PROP_TYPE_DICT_KEYSYM, 137 .pot_free = _prop_dict_keysym_free, 138 .pot_extern = _prop_dict_keysym_externalize, 139 .pot_equals = _prop_dict_keysym_equals, 140 }; 141 142 #define prop_object_is_dictionary(x) \ 143 ((x) != NULL && (x)->pd_obj.po_type == &_prop_object_type_dictionary) 144 #define prop_object_is_dictionary_keysym(x) \ 145 ((x) != NULL && (x)->pdk_obj.po_type == &_prop_object_type_dict_keysym) 146 147 #define prop_dictionary_is_immutable(x) \ 148 (((x)->pd_flags & PD_F_IMMUTABLE) != 0) 149 150 struct _prop_dictionary_iterator { 151 struct _prop_object_iterator pdi_base; 152 unsigned int pdi_index; 153 }; 154 155 /* 156 * Dictionary key symbols are immutable, and we are likely to have many 157 * duplicated key symbols. So, to save memory, we unique'ify key symbols 158 * so we only have to have one copy of each string. 159 */ 160 161 static int 162 _prop_dict_keysym_rb_compare_nodes(const struct rb_node *n1, 163 const struct rb_node *n2) 164 { 165 const prop_dictionary_keysym_t pdk1 = RBNODE_TO_PDK(n1); 166 const prop_dictionary_keysym_t pdk2 = RBNODE_TO_PDK(n2); 167 168 return (strcmp(pdk1->pdk_key, pdk2->pdk_key)); 169 } 170 171 static int 172 _prop_dict_keysym_rb_compare_key(const struct rb_node *n, 173 const void *v) 174 { 175 const prop_dictionary_keysym_t pdk = RBNODE_TO_PDK(n); 176 const char *cp = v; 177 178 return (strcmp(pdk->pdk_key, cp)); 179 } 180 181 static const struct rb_tree_ops _prop_dict_keysym_rb_tree_ops = { 182 .rbto_compare_nodes = _prop_dict_keysym_rb_compare_nodes, 183 .rbto_compare_key = _prop_dict_keysym_rb_compare_key, 184 }; 185 186 static struct rb_tree _prop_dict_keysym_tree; 187 static bool _prop_dict_keysym_tree_initialized; 188 189 _PROP_MUTEX_DECL_STATIC(_prop_dict_keysym_tree_mutex) 190 191 static void 192 _prop_dict_keysym_put(prop_dictionary_keysym_t pdk) 193 { 194 195 if (pdk->pdk_size <= PDK_SIZE_16) 196 _PROP_POOL_PUT(_prop_dictionary_keysym16_pool, pdk); 197 else if (pdk->pdk_size <= PDK_SIZE_32) 198 _PROP_POOL_PUT(_prop_dictionary_keysym32_pool, pdk); 199 else { 200 _PROP_ASSERT(pdk->pdk_size <= PDK_SIZE_128); 201 _PROP_POOL_PUT(_prop_dictionary_keysym128_pool, pdk); 202 } 203 } 204 205 /* ARGSUSED */ 206 static int 207 _prop_dict_keysym_free(prop_stack_t stack, prop_object_t *obj) 208 { 209 prop_dictionary_keysym_t pdk = *obj; 210 211 _PROP_MUTEX_LOCK(_prop_dict_keysym_tree_mutex); 212 _prop_rb_tree_remove_node(&_prop_dict_keysym_tree, &pdk->pdk_link); 213 _PROP_MUTEX_UNLOCK(_prop_dict_keysym_tree_mutex); 214 215 _prop_dict_keysym_put(pdk); 216 217 return _PROP_OBJECT_FREE_DONE; 218 } 219 220 static bool 221 _prop_dict_keysym_externalize(struct _prop_object_externalize_context *ctx, 222 void *v) 223 { 224 prop_dictionary_keysym_t pdk = v; 225 226 /* We externalize these as strings, and they're never empty. */ 227 228 _PROP_ASSERT(pdk->pdk_key[0] != '\0'); 229 230 if (_prop_object_externalize_start_tag(ctx, "string") == false || 231 _prop_object_externalize_append_encoded_cstring(ctx, 232 pdk->pdk_key) == false || 233 _prop_object_externalize_end_tag(ctx, "string") == false) 234 return (false); 235 236 return (true); 237 } 238 239 static bool 240 _prop_dict_keysym_equals(void *v1, void *v2) 241 { 242 prop_dictionary_keysym_t pdk1 = v1; 243 prop_dictionary_keysym_t pdk2 = v2; 244 245 if (! (prop_object_is_dictionary_keysym(pdk1) && 246 prop_object_is_dictionary_keysym(pdk2))) 247 return (false); 248 249 /* 250 * There is only ever one copy of a keysym at any given time, 251 * so we can reduce this to a simple pointer equality check. 252 */ 253 return (pdk1 == pdk2); 254 } 255 256 static prop_dictionary_keysym_t 257 _prop_dict_keysym_alloc(const char *key) 258 { 259 prop_dictionary_keysym_t opdk, pdk; 260 const struct rb_node *n; 261 size_t size; 262 263 /* 264 * Check to see if this already exists in the tree. If it does, 265 * we just retain it and return it. 266 */ 267 _PROP_MUTEX_LOCK(_prop_dict_keysym_tree_mutex); 268 if (! _prop_dict_keysym_tree_initialized) { 269 _prop_rb_tree_init(&_prop_dict_keysym_tree, 270 &_prop_dict_keysym_rb_tree_ops); 271 _prop_dict_keysym_tree_initialized = true; 272 } else { 273 n = _prop_rb_tree_find(&_prop_dict_keysym_tree, key); 274 if (n != NULL) { 275 opdk = RBNODE_TO_PDK(n); 276 prop_object_retain(opdk); 277 _PROP_MUTEX_UNLOCK(_prop_dict_keysym_tree_mutex); 278 return (opdk); 279 } 280 } 281 _PROP_MUTEX_UNLOCK(_prop_dict_keysym_tree_mutex); 282 283 /* 284 * Not in the tree. Create it now. 285 */ 286 287 size = sizeof(*pdk) + strlen(key) /* pdk_key[1] covers the NUL */; 288 289 if (size <= PDK_SIZE_16) 290 pdk = _PROP_POOL_GET(_prop_dictionary_keysym16_pool); 291 else if (size <= PDK_SIZE_32) 292 pdk = _PROP_POOL_GET(_prop_dictionary_keysym32_pool); 293 else if (size <= PDK_SIZE_128) 294 pdk = _PROP_POOL_GET(_prop_dictionary_keysym128_pool); 295 else 296 pdk = NULL; /* key too long */ 297 298 if (pdk == NULL) 299 return (NULL); 300 301 _prop_object_init(&pdk->pdk_obj, &_prop_object_type_dict_keysym); 302 303 strcpy(pdk->pdk_key, key); 304 pdk->pdk_size = size; 305 306 /* 307 * We dropped the mutex when we allocated the new object, so 308 * we have to check again if it is in the tree. 309 */ 310 _PROP_MUTEX_LOCK(_prop_dict_keysym_tree_mutex); 311 n = _prop_rb_tree_find(&_prop_dict_keysym_tree, key); 312 if (n != NULL) { 313 opdk = RBNODE_TO_PDK(n); 314 prop_object_retain(opdk); 315 _PROP_MUTEX_UNLOCK(_prop_dict_keysym_tree_mutex); 316 _prop_dict_keysym_put(pdk); 317 return (opdk); 318 } 319 _prop_rb_tree_insert_node(&_prop_dict_keysym_tree, &pdk->pdk_link); 320 _PROP_MUTEX_UNLOCK(_prop_dict_keysym_tree_mutex); 321 return (pdk); 322 } 323 324 int dont_free = 1; 325 326 static int 327 _prop_dictionary_free(prop_stack_t stack, prop_object_t *obj) 328 { 329 prop_dictionary_t pd = *obj; 330 prop_dictionary_keysym_t pdk; 331 prop_object_t po; 332 333 _PROP_ASSERT(pd->pd_count <= pd->pd_capacity); 334 _PROP_ASSERT((pd->pd_capacity == 0 && pd->pd_array == NULL) || 335 (pd->pd_capacity != 0 && pd->pd_array != NULL)); 336 337 /* The empty dictorinary is easy, handle that first. */ 338 if (pd->pd_count == 0) { 339 if (pd->pd_array != NULL) 340 _PROP_FREE(pd->pd_array, M_PROP_DICT); 341 342 _PROP_RWLOCK_DESTROY(pd->pd_rwlock); 343 344 _PROP_POOL_PUT(_prop_dictionary_pool, pd); 345 346 return (_PROP_OBJECT_FREE_DONE); 347 } 348 349 po = pd->pd_array[pd->pd_count - 1].pde_objref; 350 _PROP_ASSERT(po != NULL); 351 352 if (stack == NULL) { 353 /* 354 * If we are in emergency release mode, 355 * just let caller recurse down. 356 */ 357 *obj = po; 358 return (_PROP_OBJECT_FREE_FAILED); 359 } 360 361 /* Otherwise, try to push the current object on the stack. */ 362 if (!_prop_stack_push(stack, pd, NULL, NULL)) { 363 /* Push failed, entering emergency release mode. */ 364 return (_PROP_OBJECT_FREE_FAILED); 365 } 366 /* Object pushed on stack, caller will release it. */ 367 --pd->pd_count; 368 pdk = pd->pd_array[pd->pd_count].pde_key; 369 _PROP_ASSERT(pdk != NULL); 370 prop_object_release(pdk); 371 *obj = po; 372 return (_PROP_OBJECT_FREE_RECURSE); 373 } 374 375 static void 376 _prop_dictionary_emergency_free(prop_object_t obj) 377 { 378 prop_dictionary_t pd = obj; 379 prop_dictionary_keysym_t pdk; 380 381 _PROP_ASSERT(pd->pd_count != 0); 382 --pd->pd_count; 383 384 pdk = pd->pd_array[pd->pd_count].pde_key; 385 _PROP_ASSERT(pdk != NULL); 386 prop_object_release(pdk); 387 } 388 389 static bool 390 _prop_dictionary_externalize(struct _prop_object_externalize_context *ctx, 391 void *v) 392 { 393 prop_dictionary_t pd = v; 394 prop_dictionary_keysym_t pdk; 395 struct _prop_object *po; 396 prop_object_iterator_t pi; 397 unsigned int i; 398 bool rv = false; 399 400 _PROP_RWLOCK_RDLOCK(pd->pd_rwlock); 401 402 if (pd->pd_count == 0) { 403 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock); 404 return (_prop_object_externalize_empty_tag(ctx, "dict")); 405 } 406 407 if (_prop_object_externalize_start_tag(ctx, "dict") == false || 408 _prop_object_externalize_append_char(ctx, '\n') == false) 409 goto out; 410 411 pi = prop_dictionary_iterator(pd); 412 if (pi == NULL) 413 goto out; 414 415 ctx->poec_depth++; 416 _PROP_ASSERT(ctx->poec_depth != 0); 417 418 while ((pdk = prop_object_iterator_next(pi)) != NULL) { 419 po = prop_dictionary_get_keysym(pd, pdk); 420 if (po == NULL || 421 _prop_object_externalize_start_tag(ctx, "key") == false || 422 _prop_object_externalize_append_encoded_cstring(ctx, 423 pdk->pdk_key) == false || 424 _prop_object_externalize_end_tag(ctx, "key") == false || 425 (*po->po_type->pot_extern)(ctx, po) == false) { 426 prop_object_iterator_release(pi); 427 goto out; 428 } 429 } 430 431 prop_object_iterator_release(pi); 432 433 ctx->poec_depth--; 434 for (i = 0; i < ctx->poec_depth; i++) { 435 if (_prop_object_externalize_append_char(ctx, '\t') == false) 436 goto out; 437 } 438 if (_prop_object_externalize_end_tag(ctx, "dict") == false) 439 goto out; 440 441 rv = true; 442 443 out: 444 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock); 445 return (rv); 446 } 447 448 static bool 449 _prop_dictionary_equals(void *v1, void *v2) 450 { 451 prop_dictionary_t dict1 = v1; 452 prop_dictionary_t dict2 = v2; 453 const struct _prop_dict_entry *pde1, *pde2; 454 unsigned int idx; 455 bool rv = false; 456 457 if (! (prop_object_is_dictionary(dict1) && 458 prop_object_is_dictionary(dict2))) 459 return (false); 460 461 if (dict1 == dict2) 462 return (true); 463 464 if ((uintptr_t)dict1 < (uintptr_t)dict2) { 465 _PROP_RWLOCK_RDLOCK(dict1->pd_rwlock); 466 _PROP_RWLOCK_RDLOCK(dict2->pd_rwlock); 467 } else { 468 _PROP_RWLOCK_RDLOCK(dict2->pd_rwlock); 469 _PROP_RWLOCK_RDLOCK(dict1->pd_rwlock); 470 } 471 472 if (dict1->pd_count != dict2->pd_count) 473 goto out; 474 475 for (idx = 0; idx < dict1->pd_count; idx++) { 476 pde1 = &dict1->pd_array[idx]; 477 pde2 = &dict2->pd_array[idx]; 478 479 if (prop_dictionary_keysym_equals(pde1->pde_key, 480 pde2->pde_key) == false) 481 goto out; 482 if (prop_object_equals(pde1->pde_objref, 483 pde2->pde_objref) == false) 484 goto out; 485 } 486 487 rv = true; 488 489 out: 490 _PROP_RWLOCK_UNLOCK(dict1->pd_rwlock); 491 _PROP_RWLOCK_UNLOCK(dict2->pd_rwlock); 492 return (rv); 493 } 494 495 static prop_dictionary_t 496 _prop_dictionary_alloc(unsigned int capacity) 497 { 498 prop_dictionary_t pd; 499 struct _prop_dict_entry *array; 500 501 if (capacity != 0) { 502 array = _PROP_CALLOC(capacity * sizeof(*array), M_PROP_DICT); 503 if (array == NULL) 504 return (NULL); 505 } else 506 array = NULL; 507 508 pd = _PROP_POOL_GET(_prop_dictionary_pool); 509 if (pd != NULL) { 510 _prop_object_init(&pd->pd_obj, &_prop_object_type_dictionary); 511 512 _PROP_RWLOCK_INIT(pd->pd_rwlock); 513 pd->pd_array = array; 514 pd->pd_capacity = capacity; 515 pd->pd_count = 0; 516 pd->pd_flags = 0; 517 518 pd->pd_version = 0; 519 } else if (array != NULL) 520 _PROP_FREE(array, M_PROP_DICT); 521 522 return (pd); 523 } 524 525 static bool 526 _prop_dictionary_expand(prop_dictionary_t pd, unsigned int capacity) 527 { 528 struct _prop_dict_entry *array, *oarray; 529 530 /* 531 * Dictionary must be WRITE-LOCKED. 532 */ 533 534 oarray = pd->pd_array; 535 536 array = _PROP_CALLOC(capacity * sizeof(*array), M_PROP_DICT); 537 if (array == NULL) 538 return (false); 539 if (oarray != NULL) 540 memcpy(array, oarray, pd->pd_capacity * sizeof(*array)); 541 pd->pd_array = array; 542 pd->pd_capacity = capacity; 543 544 if (oarray != NULL) 545 _PROP_FREE(oarray, M_PROP_DICT); 546 547 return (true); 548 } 549 550 static prop_object_t 551 _prop_dictionary_iterator_next_object(void *v) 552 { 553 struct _prop_dictionary_iterator *pdi = v; 554 prop_dictionary_t pd = pdi->pdi_base.pi_obj; 555 prop_dictionary_keysym_t pdk = NULL; 556 557 _PROP_ASSERT(prop_object_is_dictionary(pd)); 558 559 _PROP_RWLOCK_RDLOCK(pd->pd_rwlock); 560 561 if (pd->pd_version != pdi->pdi_base.pi_version) 562 goto out; /* dictionary changed during iteration */ 563 564 _PROP_ASSERT(pdi->pdi_index <= pd->pd_count); 565 566 if (pdi->pdi_index == pd->pd_count) 567 goto out; /* we've iterated all objects */ 568 569 pdk = pd->pd_array[pdi->pdi_index].pde_key; 570 pdi->pdi_index++; 571 572 out: 573 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock); 574 return (pdk); 575 } 576 577 static void 578 _prop_dictionary_iterator_reset(void *v) 579 { 580 struct _prop_dictionary_iterator *pdi = v; 581 prop_dictionary_t pd = pdi->pdi_base.pi_obj; 582 583 _PROP_ASSERT(prop_object_is_dictionary(pd)); 584 585 _PROP_RWLOCK_RDLOCK(pd->pd_rwlock); 586 587 pdi->pdi_index = 0; 588 pdi->pdi_base.pi_version = pd->pd_version; 589 590 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock); 591 } 592 593 /* 594 * prop_dictionary_create -- 595 * Create a dictionary. 596 */ 597 prop_dictionary_t 598 prop_dictionary_create(void) 599 { 600 601 return (_prop_dictionary_alloc(0)); 602 } 603 604 /* 605 * prop_dictionary_create_with_capacity -- 606 * Create a dictionary with the capacity to store N objects. 607 */ 608 prop_dictionary_t 609 prop_dictionary_create_with_capacity(unsigned int capacity) 610 { 611 612 return (_prop_dictionary_alloc(capacity)); 613 } 614 615 /* 616 * prop_dictionary_copy -- 617 * Copy a dictionary. The new dictionary has an initial capacity equal 618 * to the number of objects stored int the original dictionary. The new 619 * dictionary contains refrences to the original dictionary's objects, 620 * not copies of those objects (i.e. a shallow copy). 621 */ 622 prop_dictionary_t 623 prop_dictionary_copy(prop_dictionary_t opd) 624 { 625 prop_dictionary_t pd; 626 prop_dictionary_keysym_t pdk; 627 prop_object_t po; 628 unsigned int idx; 629 630 if (! prop_object_is_dictionary(opd)) 631 return (NULL); 632 633 _PROP_RWLOCK_RDLOCK(opd->pd_rwlock); 634 635 pd = _prop_dictionary_alloc(opd->pd_count); 636 if (pd != NULL) { 637 for (idx = 0; idx < opd->pd_count; idx++) { 638 pdk = opd->pd_array[idx].pde_key; 639 po = opd->pd_array[idx].pde_objref; 640 641 prop_object_retain(pdk); 642 prop_object_retain(po); 643 644 pd->pd_array[idx].pde_key = pdk; 645 pd->pd_array[idx].pde_objref = po; 646 } 647 pd->pd_count = opd->pd_count; 648 pd->pd_flags = opd->pd_flags; 649 } 650 _PROP_RWLOCK_UNLOCK(opd->pd_rwlock); 651 return (pd); 652 } 653 654 /* 655 * prop_dictionary_copy_mutable -- 656 * Like prop_dictionary_copy(), but the resulting dictionary is 657 * mutable. 658 */ 659 prop_dictionary_t 660 prop_dictionary_copy_mutable(prop_dictionary_t opd) 661 { 662 prop_dictionary_t pd; 663 664 if (! prop_object_is_dictionary(opd)) 665 return (NULL); 666 667 pd = prop_dictionary_copy(opd); 668 if (pd != NULL) 669 pd->pd_flags &= ~PD_F_IMMUTABLE; 670 671 return (pd); 672 } 673 674 /* 675 * prop_dictionary_count -- 676 * Return the number of objects stored in the dictionary. 677 */ 678 unsigned int 679 prop_dictionary_count(prop_dictionary_t pd) 680 { 681 unsigned int rv; 682 683 if (! prop_object_is_dictionary(pd)) 684 return (0); 685 686 _PROP_RWLOCK_RDLOCK(pd->pd_rwlock); 687 rv = pd->pd_count; 688 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock); 689 690 return (rv); 691 } 692 693 /* 694 * prop_dictionary_ensure_capacity -- 695 * Ensure that the dictionary has the capacity to store the specified 696 * total number of objects (including the objects already stored in 697 * the dictionary). 698 */ 699 bool 700 prop_dictionary_ensure_capacity(prop_dictionary_t pd, unsigned int capacity) 701 { 702 bool rv; 703 704 if (! prop_object_is_dictionary(pd)) 705 return (false); 706 707 _PROP_RWLOCK_WRLOCK(pd->pd_rwlock); 708 if (capacity > pd->pd_capacity) 709 rv = _prop_dictionary_expand(pd, capacity); 710 else 711 rv = true; 712 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock); 713 return (rv); 714 } 715 716 /* 717 * prop_dictionary_iterator -- 718 * Return an iterator for the dictionary. The dictionary is retained by 719 * the iterator. 720 */ 721 prop_object_iterator_t 722 prop_dictionary_iterator(prop_dictionary_t pd) 723 { 724 struct _prop_dictionary_iterator *pdi; 725 726 if (! prop_object_is_dictionary(pd)) 727 return (NULL); 728 729 pdi = _PROP_CALLOC(sizeof(*pdi), M_TEMP); 730 if (pdi == NULL) 731 return (NULL); 732 pdi->pdi_base.pi_next_object = _prop_dictionary_iterator_next_object; 733 pdi->pdi_base.pi_reset = _prop_dictionary_iterator_reset; 734 prop_object_retain(pd); 735 pdi->pdi_base.pi_obj = pd; 736 _prop_dictionary_iterator_reset(pdi); 737 738 return (&pdi->pdi_base); 739 } 740 741 /* 742 * prop_dictionary_all_keys -- 743 * Return an array containing a snapshot of all of the keys 744 * in the dictionary. 745 */ 746 prop_array_t 747 prop_dictionary_all_keys(prop_dictionary_t pd) 748 { 749 prop_array_t array; 750 unsigned int idx; 751 bool rv = true; 752 753 if (! prop_object_is_dictionary(pd)) 754 return (NULL); 755 756 /* There is no pressing need to lock the dictionary for this. */ 757 array = prop_array_create_with_capacity(pd->pd_count); 758 759 _PROP_RWLOCK_RDLOCK(pd->pd_rwlock); 760 761 for (idx = 0; idx < pd->pd_count; idx++) { 762 rv = prop_array_add(array, pd->pd_array[idx].pde_key); 763 if (rv == false) 764 break; 765 } 766 767 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock); 768 769 if (rv == false) { 770 prop_object_release(array); 771 array = NULL; 772 } 773 return (array); 774 } 775 776 static struct _prop_dict_entry * 777 _prop_dict_lookup(prop_dictionary_t pd, const char *key, 778 unsigned int *idxp) 779 { 780 struct _prop_dict_entry *pde; 781 unsigned int base, idx, distance; 782 int res; 783 784 /* 785 * Dictionary must be READ-LOCKED or WRITE-LOCKED. 786 */ 787 788 for (idx = 0, base = 0, distance = pd->pd_count; distance != 0; 789 distance >>= 1) { 790 idx = base + (distance >> 1); 791 pde = &pd->pd_array[idx]; 792 _PROP_ASSERT(pde->pde_key != NULL); 793 res = strcmp(key, pde->pde_key->pdk_key); 794 if (res == 0) { 795 if (idxp != NULL) 796 *idxp = idx; 797 return (pde); 798 } 799 if (res > 0) { /* key > pdk_key: move right */ 800 base = idx + 1; 801 distance--; 802 } /* else move left */ 803 } 804 805 /* idx points to the slot we looked at last. */ 806 if (idxp != NULL) 807 *idxp = idx; 808 return (NULL); 809 } 810 811 /* 812 * prop_dictionary_get -- 813 * Return the object stored with specified key. 814 */ 815 prop_object_t 816 prop_dictionary_get(prop_dictionary_t pd, const char *key) 817 { 818 const struct _prop_dict_entry *pde; 819 prop_object_t po = NULL; 820 821 if (! prop_object_is_dictionary(pd)) 822 return (NULL); 823 824 _PROP_RWLOCK_RDLOCK(pd->pd_rwlock); 825 pde = _prop_dict_lookup(pd, key, NULL); 826 if (pde != NULL) { 827 _PROP_ASSERT(pde->pde_objref != NULL); 828 po = pde->pde_objref; 829 } 830 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock); 831 return (po); 832 } 833 834 /* 835 * prop_dictionary_get_keysym -- 836 * Return the object stored at the location encoded by the keysym. 837 */ 838 prop_object_t 839 prop_dictionary_get_keysym(prop_dictionary_t pd, prop_dictionary_keysym_t pdk) 840 { 841 842 if (! (prop_object_is_dictionary(pd) && 843 prop_object_is_dictionary_keysym(pdk))) 844 return (NULL); 845 846 return (prop_dictionary_get(pd, pdk->pdk_key)); 847 } 848 849 /* 850 * prop_dictionary_set -- 851 * Store a reference to an object at with the specified key. 852 * If the key already exisit, the original object is released. 853 */ 854 bool 855 prop_dictionary_set(prop_dictionary_t pd, const char *key, prop_object_t po) 856 { 857 struct _prop_dict_entry *pde; 858 prop_dictionary_keysym_t pdk; 859 unsigned int idx; 860 bool rv = false; 861 862 if (! prop_object_is_dictionary(pd)) 863 return (false); 864 865 _PROP_ASSERT(pd->pd_count <= pd->pd_capacity); 866 867 if (prop_dictionary_is_immutable(pd)) 868 return (false); 869 870 _PROP_RWLOCK_WRLOCK(pd->pd_rwlock); 871 872 pde = _prop_dict_lookup(pd, key, &idx); 873 if (pde != NULL) { 874 prop_object_t opo = pde->pde_objref; 875 prop_object_retain(po); 876 pde->pde_objref = po; 877 prop_object_release(opo); 878 rv = true; 879 goto out; 880 } 881 882 pdk = _prop_dict_keysym_alloc(key); 883 if (pdk == NULL) 884 goto out; 885 886 if (pd->pd_count == pd->pd_capacity && 887 _prop_dictionary_expand(pd, 888 pd->pd_capacity + EXPAND_STEP) == false) { 889 prop_object_release(pdk); 890 goto out; 891 } 892 893 /* At this point, the store will succeed. */ 894 prop_object_retain(po); 895 896 if (pd->pd_count == 0) { 897 pd->pd_array[0].pde_key = pdk; 898 pd->pd_array[0].pde_objref = po; 899 pd->pd_count++; 900 pd->pd_version++; 901 rv = true; 902 goto out; 903 } 904 905 pde = &pd->pd_array[idx]; 906 _PROP_ASSERT(pde->pde_key != NULL); 907 908 if (strcmp(key, pde->pde_key->pdk_key) < 0) { 909 /* 910 * key < pdk_key: insert to the left. This is the same as 911 * inserting to the right, except we decrement the current 912 * index first. 913 * 914 * Because we're unsigned, we have to special case 0 915 * (grumble). 916 */ 917 if (idx == 0) { 918 memmove(&pd->pd_array[1], &pd->pd_array[0], 919 pd->pd_count * sizeof(*pde)); 920 pd->pd_array[0].pde_key = pdk; 921 pd->pd_array[0].pde_objref = po; 922 pd->pd_count++; 923 pd->pd_version++; 924 rv = true; 925 goto out; 926 } 927 idx--; 928 } 929 930 memmove(&pd->pd_array[idx + 2], &pd->pd_array[idx + 1], 931 (pd->pd_count - (idx + 1)) * sizeof(*pde)); 932 pd->pd_array[idx + 1].pde_key = pdk; 933 pd->pd_array[idx + 1].pde_objref = po; 934 pd->pd_count++; 935 936 pd->pd_version++; 937 938 rv = true; 939 940 out: 941 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock); 942 return (rv); 943 } 944 945 /* 946 * prop_dictionary_set_keysym -- 947 * Replace the object in the dictionary at the location encoded by 948 * the keysym. 949 */ 950 bool 951 prop_dictionary_set_keysym(prop_dictionary_t pd, prop_dictionary_keysym_t pdk, 952 prop_object_t po) 953 { 954 955 if (! (prop_object_is_dictionary(pd) && 956 prop_object_is_dictionary_keysym(pdk))) 957 return (false); 958 959 return (prop_dictionary_set(pd, pdk->pdk_key, po)); 960 } 961 962 static void 963 _prop_dictionary_remove(prop_dictionary_t pd, struct _prop_dict_entry *pde, 964 unsigned int idx) 965 { 966 prop_dictionary_keysym_t pdk = pde->pde_key; 967 prop_object_t po = pde->pde_objref; 968 969 /* 970 * Dictionary must be WRITE-LOCKED. 971 */ 972 973 _PROP_ASSERT(pd->pd_count != 0); 974 _PROP_ASSERT(idx < pd->pd_count); 975 _PROP_ASSERT(pde == &pd->pd_array[idx]); 976 977 idx++; 978 memmove(&pd->pd_array[idx - 1], &pd->pd_array[idx], 979 (pd->pd_count - idx) * sizeof(*pde)); 980 pd->pd_count--; 981 pd->pd_version++; 982 983 prop_object_release(pdk); 984 prop_object_release(po); 985 } 986 987 /* 988 * prop_dictionary_remove -- 989 * Remove the reference to an object with the specified key from 990 * the dictionary. 991 */ 992 void 993 prop_dictionary_remove(prop_dictionary_t pd, const char *key) 994 { 995 struct _prop_dict_entry *pde; 996 unsigned int idx; 997 998 if (! prop_object_is_dictionary(pd)) 999 return; 1000 1001 _PROP_RWLOCK_WRLOCK(pd->pd_rwlock); 1002 1003 /* XXX Should this be a _PROP_ASSERT()? */ 1004 if (prop_dictionary_is_immutable(pd)) 1005 goto out; 1006 1007 pde = _prop_dict_lookup(pd, key, &idx); 1008 /* XXX Should this be a _PROP_ASSERT()? */ 1009 if (pde == NULL) 1010 goto out; 1011 1012 _prop_dictionary_remove(pd, pde, idx); 1013 out: 1014 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock); 1015 } 1016 1017 /* 1018 * prop_dictionary_remove_keysym -- 1019 * Remove a reference to an object stored in the dictionary at the 1020 * location encoded by the keysym. 1021 */ 1022 void 1023 prop_dictionary_remove_keysym(prop_dictionary_t pd, 1024 prop_dictionary_keysym_t pdk) 1025 { 1026 1027 if (! (prop_object_is_dictionary(pd) && 1028 prop_object_is_dictionary_keysym(pdk))) 1029 return; 1030 1031 prop_dictionary_remove(pd, pdk->pdk_key); 1032 } 1033 1034 /* 1035 * prop_dictionary_equals -- 1036 * Return true if the two dictionaries are equivalent. Note we do a 1037 * by-value comparison of the objects in the dictionary. 1038 */ 1039 bool 1040 prop_dictionary_equals(prop_dictionary_t dict1, prop_dictionary_t dict2) 1041 { 1042 1043 return (_prop_dictionary_equals(dict1, dict2)); 1044 } 1045 1046 /* 1047 * prop_dictionary_keysym_cstring_nocopy -- 1048 * Return an immutable reference to the keysym's value. 1049 */ 1050 const char * 1051 prop_dictionary_keysym_cstring_nocopy(prop_dictionary_keysym_t pdk) 1052 { 1053 1054 if (! prop_object_is_dictionary_keysym(pdk)) 1055 return (NULL); 1056 1057 return (pdk->pdk_key); 1058 } 1059 1060 /* 1061 * prop_dictionary_keysym_equals -- 1062 * Return true if the two dictionary key symbols are equivalent. 1063 * Note: We do not compare the object references. 1064 */ 1065 bool 1066 prop_dictionary_keysym_equals(prop_dictionary_keysym_t pdk1, 1067 prop_dictionary_keysym_t pdk2) 1068 { 1069 1070 return (_prop_dict_keysym_equals(pdk1, pdk2)); 1071 } 1072 1073 /* 1074 * prop_dictionary_externalize -- 1075 * Externalize a dictionary, returning a NUL-terminated buffer 1076 * containing the XML-style representation. The buffer is allocated 1077 * with the M_TEMP memory type. 1078 */ 1079 char * 1080 prop_dictionary_externalize(prop_dictionary_t pd) 1081 { 1082 struct _prop_object_externalize_context *ctx; 1083 char *cp; 1084 1085 ctx = _prop_object_externalize_context_alloc(); 1086 if (ctx == NULL) 1087 return (NULL); 1088 1089 if (_prop_object_externalize_header(ctx) == false || 1090 (*pd->pd_obj.po_type->pot_extern)(ctx, pd) == false || 1091 _prop_object_externalize_footer(ctx) == false) { 1092 /* We are responsible for releasing the buffer. */ 1093 _PROP_FREE(ctx->poec_buf, M_TEMP); 1094 _prop_object_externalize_context_free(ctx); 1095 return (NULL); 1096 } 1097 1098 cp = ctx->poec_buf; 1099 _prop_object_externalize_context_free(ctx); 1100 1101 return (cp); 1102 } 1103 1104 /* 1105 * _prop_dictionary_internalize -- 1106 * Parse a <dict>...</dict> and return the object created from the 1107 * external representation. 1108 * 1109 * Internal state in via rec_data is the storage area for the last processed 1110 * key. 1111 * _prop_dictionary_internalize_body is the upper half of the parse loop. 1112 * It is responsible for parsing the key directly and storing it in the area 1113 * referenced by rec_data. 1114 * _prop_dictionary_internalize_cont is the lower half and called with the value 1115 * associated with the key. 1116 */ 1117 static bool _prop_dictionary_internalize_body(prop_stack_t, 1118 prop_object_t *, struct _prop_object_internalize_context *, char *); 1119 1120 bool 1121 _prop_dictionary_internalize(prop_stack_t stack, prop_object_t *obj, 1122 struct _prop_object_internalize_context *ctx) 1123 { 1124 prop_dictionary_t dict; 1125 char *tmpkey; 1126 1127 /* We don't currently understand any attributes. */ 1128 if (ctx->poic_tagattr != NULL) 1129 return (true); 1130 1131 dict = prop_dictionary_create(); 1132 if (dict == NULL) 1133 return (true); 1134 1135 if (ctx->poic_is_empty_element) { 1136 *obj = dict; 1137 return (true); 1138 } 1139 1140 tmpkey = _PROP_MALLOC(PDK_MAXKEY + 1, M_TEMP); 1141 if (tmpkey == NULL) { 1142 prop_object_release(dict); 1143 return (true); 1144 } 1145 1146 *obj = dict; 1147 /* 1148 * Opening tag is found, storage for key allocated and 1149 * now continue to the first element. 1150 */ 1151 return _prop_dictionary_internalize_body(stack, obj, ctx, tmpkey); 1152 } 1153 1154 static bool 1155 _prop_dictionary_internalize_continue(prop_stack_t stack, prop_object_t *obj, 1156 struct _prop_object_internalize_context *ctx, void *data, prop_object_t child) 1157 { 1158 prop_dictionary_t dict = *obj; 1159 char *tmpkey = data; 1160 1161 _PROP_ASSERT(tmpkey != NULL); 1162 1163 if (child == NULL || 1164 prop_dictionary_set(dict, tmpkey, child) == false) { 1165 _PROP_FREE(tmpkey, M_TEMP); 1166 if (child != NULL) 1167 prop_object_release(child); 1168 prop_object_release(dict); 1169 *obj = NULL; 1170 return (true); 1171 } 1172 1173 prop_object_release(child); 1174 1175 /* 1176 * key, value was added, now continue looking for the next key 1177 * or the closing tag. 1178 */ 1179 return _prop_dictionary_internalize_body(stack, obj, ctx, tmpkey); 1180 } 1181 1182 static bool 1183 _prop_dictionary_internalize_body(prop_stack_t stack, prop_object_t *obj, 1184 struct _prop_object_internalize_context *ctx, char *tmpkey) 1185 { 1186 prop_dictionary_t dict = *obj; 1187 size_t keylen; 1188 1189 /* Fetch the next tag. */ 1190 if (_prop_object_internalize_find_tag(ctx, NULL, _PROP_TAG_TYPE_EITHER) == false) 1191 goto bad; 1192 1193 /* Check to see if this is the end of the dictionary. */ 1194 if (_PROP_TAG_MATCH(ctx, "dict") && 1195 ctx->poic_tag_type == _PROP_TAG_TYPE_END) { 1196 _PROP_FREE(tmpkey, M_TEMP); 1197 return (true); 1198 } 1199 1200 /* Ok, it must be a non-empty key start tag. */ 1201 if (!_PROP_TAG_MATCH(ctx, "key") || 1202 ctx->poic_tag_type != _PROP_TAG_TYPE_START || 1203 ctx->poic_is_empty_element) 1204 goto bad; 1205 1206 if (_prop_object_internalize_decode_string(ctx, 1207 tmpkey, PDK_MAXKEY, &keylen, 1208 &ctx->poic_cp) == false) 1209 goto bad; 1210 1211 _PROP_ASSERT(keylen <= PDK_MAXKEY); 1212 tmpkey[keylen] = '\0'; 1213 1214 if (_prop_object_internalize_find_tag(ctx, "key", 1215 _PROP_TAG_TYPE_END) == false) 1216 goto bad; 1217 1218 /* ..and now the beginning of the value. */ 1219 if (_prop_object_internalize_find_tag(ctx, NULL, 1220 _PROP_TAG_TYPE_START) == false) 1221 goto bad; 1222 1223 /* 1224 * Key is found, now wait for value to be parsed. 1225 */ 1226 if (_prop_stack_push(stack, *obj, tmpkey, 1227 _prop_dictionary_internalize_continue)) 1228 return (false); 1229 1230 bad: 1231 _PROP_FREE(tmpkey, M_TEMP); 1232 prop_object_release(dict); 1233 *obj = NULL; 1234 return (true); 1235 } 1236 1237 /* 1238 * prop_dictionary_internalize -- 1239 * Create a dictionary by parsing the NUL-terminated XML-style 1240 * representation. 1241 */ 1242 prop_dictionary_t 1243 prop_dictionary_internalize(const char *xml) 1244 { 1245 return _prop_generic_internalize(xml, "dict"); 1246 } 1247 1248 #if !defined(_KERNEL) && !defined(_STANDALONE) 1249 /* 1250 * prop_dictionary_externalize_to_file -- 1251 * Externalize a dictionary to the specified file. 1252 */ 1253 bool 1254 prop_dictionary_externalize_to_file(prop_dictionary_t dict, const char *fname) 1255 { 1256 char *xml; 1257 bool rv; 1258 int save_errno = 0; /* XXXGCC -Wuninitialized [mips, ...] */ 1259 1260 xml = prop_dictionary_externalize(dict); 1261 if (xml == NULL) 1262 return (false); 1263 rv = _prop_object_externalize_write_file(fname, xml, strlen(xml)); 1264 if (rv == false) 1265 save_errno = errno; 1266 _PROP_FREE(xml, M_TEMP); 1267 if (rv == false) 1268 errno = save_errno; 1269 1270 return (rv); 1271 } 1272 1273 /* 1274 * prop_dictionary_internalize_from_file -- 1275 * Internalize a dictionary from a file. 1276 */ 1277 prop_dictionary_t 1278 prop_dictionary_internalize_from_file(const char *fname) 1279 { 1280 struct _prop_object_internalize_mapped_file *mf; 1281 prop_dictionary_t dict; 1282 1283 mf = _prop_object_internalize_map_file(fname); 1284 if (mf == NULL) 1285 return (NULL); 1286 dict = prop_dictionary_internalize(mf->poimf_xml); 1287 _prop_object_internalize_unmap_file(mf); 1288 1289 return (dict); 1290 } 1291 #endif /* !_KERNEL && !_STANDALONE */ 1292
Indexes created Fri Sep 26 08:10:20 GMT 2025