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