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