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