prop_dictionary.c revision 1.23
1 /* $NetBSD: prop_dictionary.c,v 1.23 2008/03/05 07:47:09 cube 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_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_dictionary_iterator_reset(pdi); 775 776 return (&pdi->pdi_base); 777 } 778 779 /* 780 * prop_dictionary_all_keys -- 781 * Return an array containing a snapshot of all of the keys 782 * in the dictionary. 783 */ 784 prop_array_t 785 prop_dictionary_all_keys(prop_dictionary_t pd) 786 { 787 prop_array_t array; 788 unsigned int idx; 789 bool rv = true; 790 791 if (! prop_object_is_dictionary(pd)) 792 return (NULL); 793 794 /* There is no pressing need to lock the dictionary for this. */ 795 array = prop_array_create_with_capacity(pd->pd_count); 796 797 _PROP_RWLOCK_RDLOCK(pd->pd_rwlock); 798 799 for (idx = 0; idx < pd->pd_count; idx++) { 800 rv = prop_array_add(array, pd->pd_array[idx].pde_key); 801 if (rv == false) 802 break; 803 } 804 805 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock); 806 807 if (rv == false) { 808 prop_object_release(array); 809 array = NULL; 810 } 811 return (array); 812 } 813 814 static struct _prop_dict_entry * 815 _prop_dict_lookup(prop_dictionary_t pd, const char *key, 816 unsigned int *idxp) 817 { 818 struct _prop_dict_entry *pde; 819 unsigned int base, idx, distance; 820 int res; 821 822 /* 823 * Dictionary must be READ-LOCKED or WRITE-LOCKED. 824 */ 825 826 for (idx = 0, base = 0, distance = pd->pd_count; distance != 0; 827 distance >>= 1) { 828 idx = base + (distance >> 1); 829 pde = &pd->pd_array[idx]; 830 _PROP_ASSERT(pde->pde_key != NULL); 831 res = strcmp(key, pde->pde_key->pdk_key); 832 if (res == 0) { 833 if (idxp != NULL) 834 *idxp = idx; 835 return (pde); 836 } 837 if (res > 0) { /* key > pdk_key: move right */ 838 base = idx + 1; 839 distance--; 840 } /* else move left */ 841 } 842 843 /* idx points to the slot we looked at last. */ 844 if (idxp != NULL) 845 *idxp = idx; 846 return (NULL); 847 } 848 849 /* 850 * prop_dictionary_get -- 851 * Return the object stored with specified key. 852 */ 853 prop_object_t 854 prop_dictionary_get(prop_dictionary_t pd, const char *key) 855 { 856 const struct _prop_dict_entry *pde; 857 prop_object_t po = NULL; 858 859 if (! prop_object_is_dictionary(pd)) 860 return (NULL); 861 862 _PROP_RWLOCK_RDLOCK(pd->pd_rwlock); 863 pde = _prop_dict_lookup(pd, key, NULL); 864 if (pde != NULL) { 865 _PROP_ASSERT(pde->pde_objref != NULL); 866 po = pde->pde_objref; 867 } 868 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock); 869 return (po); 870 } 871 872 /* 873 * prop_dictionary_get_keysym -- 874 * Return the object stored at the location encoded by the keysym. 875 */ 876 prop_object_t 877 prop_dictionary_get_keysym(prop_dictionary_t pd, prop_dictionary_keysym_t pdk) 878 { 879 880 if (! (prop_object_is_dictionary(pd) && 881 prop_object_is_dictionary_keysym(pdk))) 882 return (NULL); 883 884 return (prop_dictionary_get(pd, pdk->pdk_key)); 885 } 886 887 /* 888 * prop_dictionary_set -- 889 * Store a reference to an object at with the specified key. 890 * If the key already exisit, the original object is released. 891 */ 892 bool 893 prop_dictionary_set(prop_dictionary_t pd, const char *key, prop_object_t po) 894 { 895 struct _prop_dict_entry *pde; 896 prop_dictionary_keysym_t pdk; 897 unsigned int idx; 898 bool rv = false; 899 900 if (! prop_object_is_dictionary(pd)) 901 return (false); 902 903 _PROP_ASSERT(pd->pd_count <= pd->pd_capacity); 904 905 if (prop_dictionary_is_immutable(pd)) 906 return (false); 907 908 _PROP_RWLOCK_WRLOCK(pd->pd_rwlock); 909 910 pde = _prop_dict_lookup(pd, key, &idx); 911 if (pde != NULL) { 912 prop_object_t opo = pde->pde_objref; 913 prop_object_retain(po); 914 pde->pde_objref = po; 915 prop_object_release(opo); 916 rv = true; 917 goto out; 918 } 919 920 pdk = _prop_dict_keysym_alloc(key); 921 if (pdk == NULL) 922 goto out; 923 924 if (pd->pd_count == pd->pd_capacity && 925 _prop_dictionary_expand(pd, 926 pd->pd_capacity + EXPAND_STEP) == false) { 927 prop_object_release(pdk); 928 goto out; 929 } 930 931 /* At this point, the store will succeed. */ 932 prop_object_retain(po); 933 934 if (pd->pd_count == 0) { 935 pd->pd_array[0].pde_key = pdk; 936 pd->pd_array[0].pde_objref = po; 937 pd->pd_count++; 938 pd->pd_version++; 939 rv = true; 940 goto out; 941 } 942 943 pde = &pd->pd_array[idx]; 944 _PROP_ASSERT(pde->pde_key != NULL); 945 946 if (strcmp(key, pde->pde_key->pdk_key) < 0) { 947 /* 948 * key < pdk_key: insert to the left. This is the same as 949 * inserting to the right, except we decrement the current 950 * index first. 951 * 952 * Because we're unsigned, we have to special case 0 953 * (grumble). 954 */ 955 if (idx == 0) { 956 memmove(&pd->pd_array[1], &pd->pd_array[0], 957 pd->pd_count * sizeof(*pde)); 958 pd->pd_array[0].pde_key = pdk; 959 pd->pd_array[0].pde_objref = po; 960 pd->pd_count++; 961 pd->pd_version++; 962 rv = true; 963 goto out; 964 } 965 idx--; 966 } 967 968 memmove(&pd->pd_array[idx + 2], &pd->pd_array[idx + 1], 969 (pd->pd_count - (idx + 1)) * sizeof(*pde)); 970 pd->pd_array[idx + 1].pde_key = pdk; 971 pd->pd_array[idx + 1].pde_objref = po; 972 pd->pd_count++; 973 974 pd->pd_version++; 975 976 rv = true; 977 978 out: 979 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock); 980 return (rv); 981 } 982 983 /* 984 * prop_dictionary_set_keysym -- 985 * Replace the object in the dictionary at the location encoded by 986 * the keysym. 987 */ 988 bool 989 prop_dictionary_set_keysym(prop_dictionary_t pd, prop_dictionary_keysym_t pdk, 990 prop_object_t po) 991 { 992 993 if (! (prop_object_is_dictionary(pd) && 994 prop_object_is_dictionary_keysym(pdk))) 995 return (false); 996 997 return (prop_dictionary_set(pd, pdk->pdk_key, po)); 998 } 999 1000 static void 1001 _prop_dictionary_remove(prop_dictionary_t pd, struct _prop_dict_entry *pde, 1002 unsigned int idx) 1003 { 1004 prop_dictionary_keysym_t pdk = pde->pde_key; 1005 prop_object_t po = pde->pde_objref; 1006 1007 /* 1008 * Dictionary must be WRITE-LOCKED. 1009 */ 1010 1011 _PROP_ASSERT(pd->pd_count != 0); 1012 _PROP_ASSERT(idx < pd->pd_count); 1013 _PROP_ASSERT(pde == &pd->pd_array[idx]); 1014 1015 idx++; 1016 memmove(&pd->pd_array[idx - 1], &pd->pd_array[idx], 1017 (pd->pd_count - idx) * sizeof(*pde)); 1018 pd->pd_count--; 1019 pd->pd_version++; 1020 1021 prop_object_release(pdk); 1022 prop_object_release(po); 1023 } 1024 1025 /* 1026 * prop_dictionary_remove -- 1027 * Remove the reference to an object with the specified key from 1028 * the dictionary. 1029 */ 1030 void 1031 prop_dictionary_remove(prop_dictionary_t pd, const char *key) 1032 { 1033 struct _prop_dict_entry *pde; 1034 unsigned int idx; 1035 1036 if (! prop_object_is_dictionary(pd)) 1037 return; 1038 1039 _PROP_RWLOCK_WRLOCK(pd->pd_rwlock); 1040 1041 /* XXX Should this be a _PROP_ASSERT()? */ 1042 if (prop_dictionary_is_immutable(pd)) 1043 goto out; 1044 1045 pde = _prop_dict_lookup(pd, key, &idx); 1046 /* XXX Should this be a _PROP_ASSERT()? */ 1047 if (pde == NULL) 1048 goto out; 1049 1050 _prop_dictionary_remove(pd, pde, idx); 1051 out: 1052 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock); 1053 } 1054 1055 /* 1056 * prop_dictionary_remove_keysym -- 1057 * Remove a reference to an object stored in the dictionary at the 1058 * location encoded by the keysym. 1059 */ 1060 void 1061 prop_dictionary_remove_keysym(prop_dictionary_t pd, 1062 prop_dictionary_keysym_t pdk) 1063 { 1064 1065 if (! (prop_object_is_dictionary(pd) && 1066 prop_object_is_dictionary_keysym(pdk))) 1067 return; 1068 1069 prop_dictionary_remove(pd, pdk->pdk_key); 1070 } 1071 1072 /* 1073 * prop_dictionary_equals -- 1074 * Return true if the two dictionaries are equivalent. Note we do a 1075 * by-value comparison of the objects in the dictionary. 1076 */ 1077 bool 1078 prop_dictionary_equals(prop_dictionary_t dict1, prop_dictionary_t dict2) 1079 { 1080 if (!prop_object_is_dictionary(dict1) || 1081 !prop_object_is_dictionary(dict2)) 1082 return (false); 1083 1084 return (prop_object_equals(dict1, dict2)); 1085 } 1086 1087 /* 1088 * prop_dictionary_keysym_cstring_nocopy -- 1089 * Return an immutable reference to the keysym's value. 1090 */ 1091 const char * 1092 prop_dictionary_keysym_cstring_nocopy(prop_dictionary_keysym_t pdk) 1093 { 1094 1095 if (! prop_object_is_dictionary_keysym(pdk)) 1096 return (NULL); 1097 1098 return (pdk->pdk_key); 1099 } 1100 1101 /* 1102 * prop_dictionary_keysym_equals -- 1103 * Return true if the two dictionary key symbols are equivalent. 1104 * Note: We do not compare the object references. 1105 */ 1106 bool 1107 prop_dictionary_keysym_equals(prop_dictionary_keysym_t pdk1, 1108 prop_dictionary_keysym_t pdk2) 1109 { 1110 if (!prop_object_is_dictionary_keysym(pdk1) || 1111 !prop_object_is_dictionary_keysym(pdk2)) 1112 return (_PROP_OBJECT_EQUALS_FALSE); 1113 1114 return (prop_object_equals(pdk1, pdk2)); 1115 } 1116 1117 /* 1118 * prop_dictionary_externalize -- 1119 * Externalize a dictionary, returning a NUL-terminated buffer 1120 * containing the XML-style representation. The buffer is allocated 1121 * with the M_TEMP memory type. 1122 */ 1123 char * 1124 prop_dictionary_externalize(prop_dictionary_t pd) 1125 { 1126 struct _prop_object_externalize_context *ctx; 1127 char *cp; 1128 1129 ctx = _prop_object_externalize_context_alloc(); 1130 if (ctx == NULL) 1131 return (NULL); 1132 1133 if (_prop_object_externalize_header(ctx) == false || 1134 (*pd->pd_obj.po_type->pot_extern)(ctx, pd) == false || 1135 _prop_object_externalize_footer(ctx) == false) { 1136 /* We are responsible for releasing the buffer. */ 1137 _PROP_FREE(ctx->poec_buf, M_TEMP); 1138 _prop_object_externalize_context_free(ctx); 1139 return (NULL); 1140 } 1141 1142 cp = ctx->poec_buf; 1143 _prop_object_externalize_context_free(ctx); 1144 1145 return (cp); 1146 } 1147 1148 /* 1149 * _prop_dictionary_internalize -- 1150 * Parse a <dict>...</dict> and return the object created from the 1151 * external representation. 1152 * 1153 * Internal state in via rec_data is the storage area for the last processed 1154 * key. 1155 * _prop_dictionary_internalize_body is the upper half of the parse loop. 1156 * It is responsible for parsing the key directly and storing it in the area 1157 * referenced by rec_data. 1158 * _prop_dictionary_internalize_cont is the lower half and called with the value 1159 * associated with the key. 1160 */ 1161 static bool _prop_dictionary_internalize_body(prop_stack_t, 1162 prop_object_t *, struct _prop_object_internalize_context *, char *); 1163 1164 bool 1165 _prop_dictionary_internalize(prop_stack_t stack, prop_object_t *obj, 1166 struct _prop_object_internalize_context *ctx) 1167 { 1168 prop_dictionary_t dict; 1169 char *tmpkey; 1170 1171 /* We don't currently understand any attributes. */ 1172 if (ctx->poic_tagattr != NULL) 1173 return (true); 1174 1175 dict = prop_dictionary_create(); 1176 if (dict == NULL) 1177 return (true); 1178 1179 if (ctx->poic_is_empty_element) { 1180 *obj = dict; 1181 return (true); 1182 } 1183 1184 tmpkey = _PROP_MALLOC(PDK_MAXKEY + 1, M_TEMP); 1185 if (tmpkey == NULL) { 1186 prop_object_release(dict); 1187 return (true); 1188 } 1189 1190 *obj = dict; 1191 /* 1192 * Opening tag is found, storage for key allocated and 1193 * now continue to the first element. 1194 */ 1195 return _prop_dictionary_internalize_body(stack, obj, ctx, tmpkey); 1196 } 1197 1198 static bool 1199 _prop_dictionary_internalize_continue(prop_stack_t stack, prop_object_t *obj, 1200 struct _prop_object_internalize_context *ctx, void *data, prop_object_t child) 1201 { 1202 prop_dictionary_t dict = *obj; 1203 char *tmpkey = data; 1204 1205 _PROP_ASSERT(tmpkey != NULL); 1206 1207 if (child == NULL || 1208 prop_dictionary_set(dict, tmpkey, child) == false) { 1209 _PROP_FREE(tmpkey, M_TEMP); 1210 if (child != NULL) 1211 prop_object_release(child); 1212 prop_object_release(dict); 1213 *obj = NULL; 1214 return (true); 1215 } 1216 1217 prop_object_release(child); 1218 1219 /* 1220 * key, value was added, now continue looking for the next key 1221 * or the closing tag. 1222 */ 1223 return _prop_dictionary_internalize_body(stack, obj, ctx, tmpkey); 1224 } 1225 1226 static bool 1227 _prop_dictionary_internalize_body(prop_stack_t stack, prop_object_t *obj, 1228 struct _prop_object_internalize_context *ctx, char *tmpkey) 1229 { 1230 prop_dictionary_t dict = *obj; 1231 size_t keylen; 1232 1233 /* Fetch the next tag. */ 1234 if (_prop_object_internalize_find_tag(ctx, NULL, _PROP_TAG_TYPE_EITHER) == false) 1235 goto bad; 1236 1237 /* Check to see if this is the end of the dictionary. */ 1238 if (_PROP_TAG_MATCH(ctx, "dict") && 1239 ctx->poic_tag_type == _PROP_TAG_TYPE_END) { 1240 _PROP_FREE(tmpkey, M_TEMP); 1241 return (true); 1242 } 1243 1244 /* Ok, it must be a non-empty key start tag. */ 1245 if (!_PROP_TAG_MATCH(ctx, "key") || 1246 ctx->poic_tag_type != _PROP_TAG_TYPE_START || 1247 ctx->poic_is_empty_element) 1248 goto bad; 1249 1250 if (_prop_object_internalize_decode_string(ctx, 1251 tmpkey, PDK_MAXKEY, &keylen, 1252 &ctx->poic_cp) == false) 1253 goto bad; 1254 1255 _PROP_ASSERT(keylen <= PDK_MAXKEY); 1256 tmpkey[keylen] = '\0'; 1257 1258 if (_prop_object_internalize_find_tag(ctx, "key", 1259 _PROP_TAG_TYPE_END) == false) 1260 goto bad; 1261 1262 /* ..and now the beginning of the value. */ 1263 if (_prop_object_internalize_find_tag(ctx, NULL, 1264 _PROP_TAG_TYPE_START) == false) 1265 goto bad; 1266 1267 /* 1268 * Key is found, now wait for value to be parsed. 1269 */ 1270 if (_prop_stack_push(stack, *obj, 1271 _prop_dictionary_internalize_continue, 1272 tmpkey, NULL)) 1273 return (false); 1274 1275 bad: 1276 _PROP_FREE(tmpkey, M_TEMP); 1277 prop_object_release(dict); 1278 *obj = NULL; 1279 return (true); 1280 } 1281 1282 /* 1283 * prop_dictionary_internalize -- 1284 * Create a dictionary by parsing the NUL-terminated XML-style 1285 * representation. 1286 */ 1287 prop_dictionary_t 1288 prop_dictionary_internalize(const char *xml) 1289 { 1290 return _prop_generic_internalize(xml, "dict"); 1291 } 1292 1293 #if !defined(_KERNEL) && !defined(_STANDALONE) 1294 /* 1295 * prop_dictionary_externalize_to_file -- 1296 * Externalize a dictionary to the specified file. 1297 */ 1298 bool 1299 prop_dictionary_externalize_to_file(prop_dictionary_t dict, const char *fname) 1300 { 1301 char *xml; 1302 bool rv; 1303 int save_errno = 0; /* XXXGCC -Wuninitialized [mips, ...] */ 1304 1305 xml = prop_dictionary_externalize(dict); 1306 if (xml == NULL) 1307 return (false); 1308 rv = _prop_object_externalize_write_file(fname, xml, strlen(xml)); 1309 if (rv == false) 1310 save_errno = errno; 1311 _PROP_FREE(xml, M_TEMP); 1312 if (rv == false) 1313 errno = save_errno; 1314 1315 return (rv); 1316 } 1317 1318 /* 1319 * prop_dictionary_internalize_from_file -- 1320 * Internalize a dictionary from a file. 1321 */ 1322 prop_dictionary_t 1323 prop_dictionary_internalize_from_file(const char *fname) 1324 { 1325 struct _prop_object_internalize_mapped_file *mf; 1326 prop_dictionary_t dict; 1327 1328 mf = _prop_object_internalize_map_file(fname); 1329 if (mf == NULL) 1330 return (NULL); 1331 dict = prop_dictionary_internalize(mf->poimf_xml); 1332 _prop_object_internalize_unmap_file(mf); 1333 1334 return (dict); 1335 } 1336 #endif /* !_KERNEL && !_STANDALONE */ 1337
Indexes created Thu Sep 25 16:09:42 GMT 2025