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