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