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