1 /* $NetBSD: prop_dictionary.c,v 1.51 2025/05/14 03:25:46 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_extern_append_cstring(ctx, ": ") == false) { 451 return false; 452 } 453 break; 454 455 default: /* XML */ 456 if (_prop_extern_end_line(ctx, NULL) == false || 457 _prop_extern_start_line(ctx) == false) { 458 return false; 459 } 460 break; 461 } 462 463 return (*po->po_type->pot_extern)(ctx, po); 464 } 465 466 static bool 467 _prop_dictionary_externalize(struct _prop_object_externalize_context *ctx, 468 void *v) 469 { 470 prop_dictionary_t pd = v; 471 prop_dictionary_keysym_t pdk; 472 struct _prop_object *po; 473 struct _prop_dictionary_iterator *pdi; 474 bool rv = false; 475 const char * const sep = 476 ctx->poec_format == PROP_FORMAT_JSON ? "," : NULL; 477 478 _PROP_ASSERT(ctx->poec_format == PROP_FORMAT_XML || 479 ctx->poec_format == PROP_FORMAT_JSON); 480 481 _PROP_RWLOCK_RDLOCK(pd->pd_rwlock); 482 483 if (pd->pd_count == 0) { 484 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock); 485 return (_prop_extern_append_empty_tag(ctx, 486 &_prop_dictionary_type_tags)); 487 } 488 489 if (_prop_extern_append_start_tag(ctx, 490 &_prop_dictionary_type_tags, NULL) == false || 491 _prop_extern_end_line(ctx, NULL) == false) 492 goto out; 493 494 pdi = _prop_dictionary_iterator_locked(pd); 495 if (pdi == NULL) 496 goto out; 497 498 ctx->poec_depth++; 499 _PROP_ASSERT(ctx->poec_depth != 0); 500 501 while ((pdk = _prop_dictionary_iterator_next_object_locked(pdi)) 502 != NULL) { 503 po = _prop_dictionary_get_keysym(pd, pdk, true); 504 if (_prop_extern_start_line(ctx) == false || 505 _prop_dictionary_externalize_one(ctx, pdk, po) == false || 506 _prop_extern_end_line(ctx, 507 pdi->pdi_index < pd->pd_count ? 508 sep : NULL) == false) { 509 prop_object_iterator_release(&pdi->pdi_base); 510 goto out; 511 } 512 } 513 514 prop_object_iterator_release(&pdi->pdi_base); 515 516 ctx->poec_depth--; 517 if (_prop_extern_start_line(ctx) == false || 518 _prop_extern_append_end_tag(ctx, 519 &_prop_dictionary_type_tags) == false) { 520 521 goto out; 522 } 523 524 rv = true; 525 526 out: 527 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock); 528 return (rv); 529 } 530 531 /* ARGSUSED */ 532 static _prop_object_equals_rv_t 533 _prop_dictionary_equals(prop_object_t v1, prop_object_t v2, 534 void **stored_pointer1, void **stored_pointer2, 535 prop_object_t *next_obj1, prop_object_t *next_obj2) 536 { 537 prop_dictionary_t dict1 = v1; 538 prop_dictionary_t dict2 = v2; 539 uintptr_t idx; 540 _prop_object_equals_rv_t rv = _PROP_OBJECT_EQUALS_FALSE; 541 542 if (dict1 == dict2) 543 return (_PROP_OBJECT_EQUALS_TRUE); 544 545 _PROP_ASSERT(*stored_pointer1 == *stored_pointer2); 546 547 idx = (uintptr_t)*stored_pointer1; 548 549 if (idx == 0) { 550 if ((uintptr_t)dict1 < (uintptr_t)dict2) { 551 _PROP_RWLOCK_RDLOCK(dict1->pd_rwlock); 552 _PROP_RWLOCK_RDLOCK(dict2->pd_rwlock); 553 } else { 554 _PROP_RWLOCK_RDLOCK(dict2->pd_rwlock); 555 _PROP_RWLOCK_RDLOCK(dict1->pd_rwlock); 556 } 557 } 558 559 if (dict1->pd_count != dict2->pd_count) 560 goto out; 561 562 if (idx == dict1->pd_count) { 563 rv = _PROP_OBJECT_EQUALS_TRUE; 564 goto out; 565 } 566 567 _PROP_ASSERT(idx < dict1->pd_count); 568 569 *stored_pointer1 = (void *)(idx + 1); 570 *stored_pointer2 = (void *)(idx + 1); 571 572 *next_obj1 = dict1->pd_array[idx].pde_objref; 573 *next_obj2 = dict2->pd_array[idx].pde_objref; 574 575 if (!prop_dictionary_keysym_equals(dict1->pd_array[idx].pde_key, 576 dict2->pd_array[idx].pde_key)) 577 goto out; 578 579 return (_PROP_OBJECT_EQUALS_RECURSE); 580 581 out: 582 _PROP_RWLOCK_UNLOCK(dict1->pd_rwlock); 583 _PROP_RWLOCK_UNLOCK(dict2->pd_rwlock); 584 return (rv); 585 } 586 587 static void 588 _prop_dictionary_equals_finish(prop_object_t v1, prop_object_t v2) 589 { 590 _PROP_RWLOCK_UNLOCK(((prop_dictionary_t)v1)->pd_rwlock); 591 _PROP_RWLOCK_UNLOCK(((prop_dictionary_t)v2)->pd_rwlock); 592 } 593 594 static prop_dictionary_t 595 _prop_dictionary_alloc(unsigned int capacity) 596 { 597 prop_dictionary_t pd; 598 struct _prop_dict_entry *array; 599 600 if (capacity != 0) { 601 array = _PROP_CALLOC(capacity * sizeof(*array), M_PROP_DICT); 602 if (array == NULL) 603 return (NULL); 604 } else 605 array = NULL; 606 607 pd = _PROP_POOL_GET(_prop_dictionary_pool); 608 if (pd != NULL) { 609 _prop_object_init(&pd->pd_obj, &_prop_object_type_dictionary); 610 611 _PROP_RWLOCK_INIT(pd->pd_rwlock); 612 pd->pd_array = array; 613 pd->pd_capacity = capacity; 614 pd->pd_count = 0; 615 pd->pd_flags = 0; 616 617 pd->pd_version = 0; 618 } else if (array != NULL) 619 _PROP_FREE(array, M_PROP_DICT); 620 621 return (pd); 622 } 623 624 static bool 625 _prop_dictionary_expand(prop_dictionary_t pd, unsigned int capacity) 626 { 627 struct _prop_dict_entry *array, *oarray; 628 629 /* 630 * Dictionary must be WRITE-LOCKED. 631 */ 632 633 oarray = pd->pd_array; 634 635 array = _PROP_CALLOC(capacity * sizeof(*array), M_PROP_DICT); 636 if (array == NULL) 637 return (false); 638 if (oarray != NULL) 639 memcpy(array, oarray, pd->pd_capacity * sizeof(*array)); 640 pd->pd_array = array; 641 pd->pd_capacity = capacity; 642 643 if (oarray != NULL) 644 _PROP_FREE(oarray, M_PROP_DICT); 645 646 return (true); 647 } 648 649 static prop_object_t 650 _prop_dictionary_iterator_next_object_locked(void *v) 651 { 652 struct _prop_dictionary_iterator *pdi = v; 653 prop_dictionary_t pd = pdi->pdi_base.pi_obj; 654 prop_dictionary_keysym_t pdk = NULL; 655 656 _PROP_ASSERT(prop_object_is_dictionary(pd)); 657 658 if (pd->pd_version != pdi->pdi_base.pi_version) 659 goto out; /* dictionary changed during iteration */ 660 661 _PROP_ASSERT(pdi->pdi_index <= pd->pd_count); 662 663 if (pdi->pdi_index == pd->pd_count) 664 goto out; /* we've iterated all objects */ 665 666 pdk = pd->pd_array[pdi->pdi_index].pde_key; 667 pdi->pdi_index++; 668 669 out: 670 return (pdk); 671 } 672 673 static prop_object_t 674 _prop_dictionary_iterator_next_object(void *v) 675 { 676 struct _prop_dictionary_iterator *pdi = v; 677 prop_dictionary_t pd _PROP_ARG_UNUSED = pdi->pdi_base.pi_obj; 678 prop_dictionary_keysym_t pdk; 679 680 _PROP_ASSERT(prop_object_is_dictionary(pd)); 681 682 _PROP_RWLOCK_RDLOCK(pd->pd_rwlock); 683 pdk = _prop_dictionary_iterator_next_object_locked(pdi); 684 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock); 685 return (pdk); 686 } 687 688 static void 689 _prop_dictionary_iterator_reset_locked(void *v) 690 { 691 struct _prop_dictionary_iterator *pdi = v; 692 prop_dictionary_t pd = pdi->pdi_base.pi_obj; 693 694 _PROP_ASSERT(prop_object_is_dictionary(pd)); 695 696 pdi->pdi_index = 0; 697 pdi->pdi_base.pi_version = pd->pd_version; 698 } 699 700 static void 701 _prop_dictionary_iterator_reset(void *v) 702 { 703 struct _prop_dictionary_iterator *pdi = v; 704 prop_dictionary_t pd _PROP_ARG_UNUSED = pdi->pdi_base.pi_obj; 705 706 _PROP_RWLOCK_RDLOCK(pd->pd_rwlock); 707 _prop_dictionary_iterator_reset_locked(pdi); 708 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock); 709 } 710 711 /* 712 * prop_dictionary_create -- 713 * Create a dictionary. 714 */ 715 _PROP_EXPORT prop_dictionary_t 716 prop_dictionary_create(void) 717 { 718 719 return (_prop_dictionary_alloc(0)); 720 } 721 722 /* 723 * prop_dictionary_create_with_capacity -- 724 * Create a dictionary with the capacity to store N objects. 725 */ 726 _PROP_EXPORT prop_dictionary_t 727 prop_dictionary_create_with_capacity(unsigned int capacity) 728 { 729 730 return (_prop_dictionary_alloc(capacity)); 731 } 732 733 /* 734 * prop_dictionary_copy -- 735 * Copy a dictionary. The new dictionary has an initial capacity equal 736 * to the number of objects stored int the original dictionary. The new 737 * dictionary contains references to the original dictionary's objects, 738 * not copies of those objects (i.e. a shallow copy). 739 */ 740 _PROP_EXPORT prop_dictionary_t 741 prop_dictionary_copy(prop_dictionary_t opd) 742 { 743 prop_dictionary_t pd; 744 prop_dictionary_keysym_t pdk; 745 prop_object_t po; 746 unsigned int idx; 747 748 if (! prop_object_is_dictionary(opd)) 749 return (NULL); 750 751 _PROP_RWLOCK_RDLOCK(opd->pd_rwlock); 752 753 pd = _prop_dictionary_alloc(opd->pd_count); 754 if (pd != NULL) { 755 for (idx = 0; idx < opd->pd_count; idx++) { 756 pdk = opd->pd_array[idx].pde_key; 757 po = opd->pd_array[idx].pde_objref; 758 759 prop_object_retain(pdk); 760 prop_object_retain(po); 761 762 pd->pd_array[idx].pde_key = pdk; 763 pd->pd_array[idx].pde_objref = po; 764 } 765 pd->pd_count = opd->pd_count; 766 pd->pd_flags = opd->pd_flags; 767 } 768 _PROP_RWLOCK_UNLOCK(opd->pd_rwlock); 769 return (pd); 770 } 771 772 /* 773 * prop_dictionary_copy_mutable -- 774 * Like prop_dictionary_copy(), but the resulting dictionary is 775 * mutable. 776 */ 777 _PROP_EXPORT prop_dictionary_t 778 prop_dictionary_copy_mutable(prop_dictionary_t opd) 779 { 780 prop_dictionary_t pd; 781 782 if (! prop_object_is_dictionary(opd)) 783 return (NULL); 784 785 pd = prop_dictionary_copy(opd); 786 if (pd != NULL) 787 pd->pd_flags &= ~PD_F_IMMUTABLE; 788 789 return (pd); 790 } 791 792 /* 793 * prop_dictionary_make_immutable -- 794 * Set the immutable flag on that dictionary. 795 */ 796 _PROP_EXPORT void 797 prop_dictionary_make_immutable(prop_dictionary_t pd) 798 { 799 800 _PROP_RWLOCK_WRLOCK(pd->pd_rwlock); 801 if (prop_dictionary_is_immutable(pd) == false) 802 pd->pd_flags |= PD_F_IMMUTABLE; 803 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock); 804 } 805 806 /* 807 * prop_dictionary_count -- 808 * Return the number of objects stored in the dictionary. 809 */ 810 _PROP_EXPORT unsigned int 811 prop_dictionary_count(prop_dictionary_t pd) 812 { 813 unsigned int rv; 814 815 if (! prop_object_is_dictionary(pd)) 816 return (0); 817 818 _PROP_RWLOCK_RDLOCK(pd->pd_rwlock); 819 rv = pd->pd_count; 820 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock); 821 822 return (rv); 823 } 824 825 /* 826 * prop_dictionary_ensure_capacity -- 827 * Ensure that the dictionary has the capacity to store the specified 828 * total number of objects (including the objects already stored in 829 * the dictionary). 830 */ 831 _PROP_EXPORT bool 832 prop_dictionary_ensure_capacity(prop_dictionary_t pd, unsigned int capacity) 833 { 834 bool rv; 835 836 if (! prop_object_is_dictionary(pd)) 837 return (false); 838 839 _PROP_RWLOCK_WRLOCK(pd->pd_rwlock); 840 if (capacity > pd->pd_capacity) 841 rv = _prop_dictionary_expand(pd, capacity); 842 else 843 rv = true; 844 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock); 845 return (rv); 846 } 847 848 static struct _prop_dictionary_iterator * 849 _prop_dictionary_iterator_locked(prop_dictionary_t pd) 850 { 851 struct _prop_dictionary_iterator *pdi; 852 853 if (! prop_object_is_dictionary(pd)) 854 return (NULL); 855 856 pdi = _PROP_CALLOC(sizeof(*pdi), M_TEMP); 857 if (pdi == NULL) 858 return (NULL); 859 pdi->pdi_base.pi_next_object = _prop_dictionary_iterator_next_object; 860 pdi->pdi_base.pi_reset = _prop_dictionary_iterator_reset; 861 prop_object_retain(pd); 862 pdi->pdi_base.pi_obj = pd; 863 _prop_dictionary_iterator_reset_locked(pdi); 864 865 return pdi; 866 } 867 868 /* 869 * prop_dictionary_iterator -- 870 * Return an iterator for the dictionary. The dictionary is retained by 871 * the iterator. 872 */ 873 _PROP_EXPORT prop_object_iterator_t 874 prop_dictionary_iterator(prop_dictionary_t pd) 875 { 876 struct _prop_dictionary_iterator *pdi; 877 878 _PROP_RWLOCK_RDLOCK(pd->pd_rwlock); 879 pdi = _prop_dictionary_iterator_locked(pd); 880 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock); 881 return &pdi->pdi_base; 882 } 883 884 /* 885 * prop_dictionary_all_keys -- 886 * Return an array containing a snapshot of all of the keys 887 * in the dictionary. 888 */ 889 _PROP_EXPORT prop_array_t 890 prop_dictionary_all_keys(prop_dictionary_t pd) 891 { 892 prop_array_t array; 893 unsigned int idx; 894 bool rv = true; 895 896 if (! prop_object_is_dictionary(pd)) 897 return (NULL); 898 899 /* There is no pressing need to lock the dictionary for this. */ 900 array = prop_array_create_with_capacity(pd->pd_count); 901 902 _PROP_RWLOCK_RDLOCK(pd->pd_rwlock); 903 904 for (idx = 0; idx < pd->pd_count; idx++) { 905 rv = prop_array_add(array, pd->pd_array[idx].pde_key); 906 if (rv == false) 907 break; 908 } 909 910 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock); 911 912 if (rv == false) { 913 prop_object_release(array); 914 array = NULL; 915 } 916 return (array); 917 } 918 919 static struct _prop_dict_entry * 920 _prop_dict_lookup(prop_dictionary_t pd, const char *key, 921 unsigned int *idxp) 922 { 923 struct _prop_dict_entry *pde; 924 unsigned int base, idx, distance; 925 int res; 926 927 /* 928 * Dictionary must be READ-LOCKED or WRITE-LOCKED. 929 */ 930 931 for (idx = 0, base = 0, distance = pd->pd_count; distance != 0; 932 distance >>= 1) { 933 idx = base + (distance >> 1); 934 pde = &pd->pd_array[idx]; 935 _PROP_ASSERT(pde->pde_key != NULL); 936 res = strcmp(key, pde->pde_key->pdk_key); 937 if (res == 0) { 938 if (idxp != NULL) 939 *idxp = idx; 940 return (pde); 941 } 942 if (res > 0) { /* key > pdk_key: move right */ 943 base = idx + 1; 944 distance--; 945 } /* else move left */ 946 } 947 948 /* idx points to the slot we looked at last. */ 949 if (idxp != NULL) 950 *idxp = idx; 951 return (NULL); 952 } 953 954 static prop_object_t 955 _prop_dictionary_get(prop_dictionary_t pd, const char *key, bool locked) 956 { 957 const struct _prop_dict_entry *pde; 958 prop_object_t po = NULL; 959 960 if (! prop_object_is_dictionary(pd)) 961 return (NULL); 962 963 if (!locked) { 964 _PROP_RWLOCK_RDLOCK(pd->pd_rwlock); 965 } 966 pde = _prop_dict_lookup(pd, key, NULL); 967 if (pde != NULL) { 968 _PROP_ASSERT(pde->pde_objref != NULL); 969 po = pde->pde_objref; 970 } 971 if (!locked) { 972 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock); 973 } 974 return (po); 975 } 976 /* 977 * prop_dictionary_get -- 978 * Return the object stored with specified key. 979 */ 980 _PROP_EXPORT prop_object_t 981 prop_dictionary_get(prop_dictionary_t pd, const char *key) 982 { 983 prop_object_t po = NULL; 984 985 if (! prop_object_is_dictionary(pd)) 986 return (NULL); 987 988 _PROP_RWLOCK_RDLOCK(pd->pd_rwlock); 989 po = _prop_dictionary_get(pd, key, true); 990 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock); 991 return (po); 992 } 993 994 static prop_object_t 995 _prop_dictionary_get_keysym(prop_dictionary_t pd, prop_dictionary_keysym_t pdk, 996 bool locked) 997 { 998 999 if (! (prop_object_is_dictionary(pd) && 1000 prop_object_is_dictionary_keysym(pdk))) 1001 return (NULL); 1002 1003 return (_prop_dictionary_get(pd, pdk->pdk_key, locked)); 1004 } 1005 1006 /* 1007 * prop_dictionary_get_keysym -- 1008 * Return the object stored at the location encoded by the keysym. 1009 */ 1010 _PROP_EXPORT prop_object_t 1011 prop_dictionary_get_keysym(prop_dictionary_t pd, prop_dictionary_keysym_t pdk) 1012 { 1013 1014 return (_prop_dictionary_get_keysym(pd, pdk, false)); 1015 } 1016 1017 /* 1018 * prop_dictionary_set -- 1019 * Store a reference to an object at with the specified key. 1020 * If the key already exist, the original object is released. 1021 */ 1022 _PROP_EXPORT bool 1023 prop_dictionary_set(prop_dictionary_t pd, const char *key, prop_object_t po) 1024 { 1025 struct _prop_dict_entry *pde; 1026 prop_dictionary_keysym_t pdk; 1027 unsigned int idx; 1028 bool rv = false; 1029 1030 if (! prop_object_is_dictionary(pd)) 1031 return (false); 1032 1033 _PROP_ASSERT(pd->pd_count <= pd->pd_capacity); 1034 1035 if (prop_dictionary_is_immutable(pd)) 1036 return (false); 1037 1038 _PROP_RWLOCK_WRLOCK(pd->pd_rwlock); 1039 1040 pde = _prop_dict_lookup(pd, key, &idx); 1041 if (pde != NULL) { 1042 prop_object_t opo = pde->pde_objref; 1043 prop_object_retain(po); 1044 pde->pde_objref = po; 1045 prop_object_release(opo); 1046 rv = true; 1047 goto out; 1048 } 1049 1050 pdk = _prop_dict_keysym_alloc(key); 1051 if (pdk == NULL) 1052 goto out; 1053 1054 if (pd->pd_count == pd->pd_capacity && 1055 _prop_dictionary_expand(pd, 1056 pd->pd_capacity + EXPAND_STEP) == false) { 1057 prop_object_release(pdk); 1058 goto out; 1059 } 1060 1061 /* At this point, the store will succeed. */ 1062 prop_object_retain(po); 1063 1064 if (pd->pd_count == 0) { 1065 pd->pd_array[0].pde_key = pdk; 1066 pd->pd_array[0].pde_objref = po; 1067 pd->pd_count++; 1068 pd->pd_version++; 1069 rv = true; 1070 goto out; 1071 } 1072 1073 pde = &pd->pd_array[idx]; 1074 _PROP_ASSERT(pde->pde_key != NULL); 1075 1076 if (strcmp(key, pde->pde_key->pdk_key) < 0) { 1077 /* 1078 * key < pdk_key: insert to the left. This is the same as 1079 * inserting to the right, except we decrement the current 1080 * index first. 1081 * 1082 * Because we're unsigned, we have to special case 0 1083 * (grumble). 1084 */ 1085 if (idx == 0) { 1086 memmove(&pd->pd_array[1], &pd->pd_array[0], 1087 pd->pd_count * sizeof(*pde)); 1088 pd->pd_array[0].pde_key = pdk; 1089 pd->pd_array[0].pde_objref = po; 1090 pd->pd_count++; 1091 pd->pd_version++; 1092 rv = true; 1093 goto out; 1094 } 1095 idx--; 1096 } 1097 1098 memmove(&pd->pd_array[idx + 2], &pd->pd_array[idx + 1], 1099 (pd->pd_count - (idx + 1)) * sizeof(*pde)); 1100 pd->pd_array[idx + 1].pde_key = pdk; 1101 pd->pd_array[idx + 1].pde_objref = po; 1102 pd->pd_count++; 1103 1104 pd->pd_version++; 1105 1106 rv = true; 1107 1108 out: 1109 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock); 1110 return (rv); 1111 } 1112 1113 /* 1114 * prop_dictionary_set_keysym -- 1115 * Replace the object in the dictionary at the location encoded by 1116 * the keysym. 1117 */ 1118 _PROP_EXPORT bool 1119 prop_dictionary_set_keysym(prop_dictionary_t pd, prop_dictionary_keysym_t pdk, 1120 prop_object_t po) 1121 { 1122 1123 if (! (prop_object_is_dictionary(pd) && 1124 prop_object_is_dictionary_keysym(pdk))) 1125 return (false); 1126 1127 return (prop_dictionary_set(pd, pdk->pdk_key, po)); 1128 } 1129 1130 static void 1131 _prop_dictionary_remove(prop_dictionary_t pd, struct _prop_dict_entry *pde, 1132 unsigned int idx) 1133 { 1134 prop_dictionary_keysym_t pdk = pde->pde_key; 1135 prop_object_t po = pde->pde_objref; 1136 1137 /* 1138 * Dictionary must be WRITE-LOCKED. 1139 */ 1140 1141 _PROP_ASSERT(pd->pd_count != 0); 1142 _PROP_ASSERT(idx < pd->pd_count); 1143 _PROP_ASSERT(pde == &pd->pd_array[idx]); 1144 1145 idx++; 1146 memmove(&pd->pd_array[idx - 1], &pd->pd_array[idx], 1147 (pd->pd_count - idx) * sizeof(*pde)); 1148 pd->pd_count--; 1149 pd->pd_version++; 1150 1151 1152 prop_object_release(pdk); 1153 1154 prop_object_release(po); 1155 } 1156 1157 /* 1158 * prop_dictionary_remove -- 1159 * Remove the reference to an object with the specified key from 1160 * the dictionary. 1161 */ 1162 _PROP_EXPORT void 1163 prop_dictionary_remove(prop_dictionary_t pd, const char *key) 1164 { 1165 struct _prop_dict_entry *pde; 1166 unsigned int idx; 1167 1168 if (! prop_object_is_dictionary(pd)) 1169 return; 1170 1171 _PROP_RWLOCK_WRLOCK(pd->pd_rwlock); 1172 1173 /* XXX Should this be a _PROP_ASSERT()? */ 1174 if (prop_dictionary_is_immutable(pd)) 1175 goto out; 1176 1177 pde = _prop_dict_lookup(pd, key, &idx); 1178 /* XXX Should this be a _PROP_ASSERT()? */ 1179 if (pde == NULL) 1180 goto out; 1181 1182 _prop_dictionary_remove(pd, pde, idx); 1183 out: 1184 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock); 1185 } 1186 1187 /* 1188 * prop_dictionary_remove_keysym -- 1189 * Remove a reference to an object stored in the dictionary at the 1190 * location encoded by the keysym. 1191 */ 1192 _PROP_EXPORT void 1193 prop_dictionary_remove_keysym(prop_dictionary_t pd, 1194 prop_dictionary_keysym_t pdk) 1195 { 1196 1197 if (! (prop_object_is_dictionary(pd) && 1198 prop_object_is_dictionary_keysym(pdk))) 1199 return; 1200 1201 prop_dictionary_remove(pd, pdk->pdk_key); 1202 } 1203 1204 /* 1205 * prop_dictionary_equals -- 1206 * Return true if the two dictionaries are equivalent. Note we do a 1207 * by-value comparison of the objects in the dictionary. 1208 */ 1209 _PROP_EXPORT bool 1210 prop_dictionary_equals(prop_dictionary_t dict1, prop_dictionary_t dict2) 1211 { 1212 if (!prop_object_is_dictionary(dict1) || 1213 !prop_object_is_dictionary(dict2)) 1214 return (false); 1215 1216 return (prop_object_equals(dict1, dict2)); 1217 } 1218 1219 /* 1220 * prop_dictionary_keysym_value -- 1221 * Return a reference to the keysym's value. 1222 */ 1223 _PROP_EXPORT const char * 1224 prop_dictionary_keysym_value(prop_dictionary_keysym_t pdk) 1225 { 1226 1227 if (! prop_object_is_dictionary_keysym(pdk)) 1228 return (NULL); 1229 1230 return (pdk->pdk_key); 1231 } 1232 1233 _PROP_DEPRECATED(prop_dictionary_keysym_cstring_nocopy, 1234 "this program uses prop_dictionary_keysym_cstring_nocopy(), " 1235 "which is deprecated; use prop_dictionary_keysym_value() instead.") 1236 _PROP_EXPORT const char * 1237 prop_dictionary_keysym_cstring_nocopy(prop_dictionary_keysym_t pdk) 1238 { 1239 1240 if (! prop_object_is_dictionary_keysym(pdk)) 1241 return (NULL); 1242 1243 return (pdk->pdk_key); 1244 } 1245 1246 /* 1247 * prop_dictionary_keysym_equals -- 1248 * Return true if the two dictionary key symbols are equivalent. 1249 * Note: We do not compare the object references. 1250 */ 1251 _PROP_EXPORT bool 1252 prop_dictionary_keysym_equals(prop_dictionary_keysym_t pdk1, 1253 prop_dictionary_keysym_t pdk2) 1254 { 1255 if (!prop_object_is_dictionary_keysym(pdk1) || 1256 !prop_object_is_dictionary_keysym(pdk2)) 1257 return (false); 1258 1259 return (prop_object_equals(pdk1, pdk2)); 1260 } 1261 1262 /* 1263 * prop_dictionary_externalize -- 1264 * Externalize a dictionary in XML format. 1265 */ 1266 _PROP_EXPORT char * 1267 prop_dictionary_externalize(prop_dictionary_t pd) 1268 { 1269 return _prop_object_externalize(&pd->pd_obj, PROP_FORMAT_XML); 1270 } 1271 1272 /* 1273 * _prop_dictionary_internalize -- 1274 * Parse a <dict>...</dict> and return the object created from the 1275 * external representation. 1276 * 1277 * Internal state in via rec_data is the storage area for the last processed 1278 * key. 1279 * _prop_dictionary_internalize_body is the upper half of the parse loop. 1280 * It is responsible for parsing the key directly and storing it in the area 1281 * referenced by rec_data. 1282 * _prop_dictionary_internalize_cont is the lower half and called with the value 1283 * associated with the key. 1284 */ 1285 static bool _prop_dictionary_internalize_body(prop_stack_t, 1286 prop_object_t *, struct _prop_object_internalize_context *, char *); 1287 1288 bool 1289 _prop_dictionary_internalize(prop_stack_t stack, prop_object_t *obj, 1290 struct _prop_object_internalize_context *ctx) 1291 { 1292 prop_dictionary_t dict; 1293 char *tmpkey; 1294 1295 /* We don't currently understand any attributes. */ 1296 if (ctx->poic_tagattr != NULL) 1297 return (true); 1298 1299 dict = prop_dictionary_create(); 1300 if (dict == NULL) 1301 return (true); 1302 1303 if (ctx->poic_is_empty_element) { 1304 *obj = dict; 1305 return (true); 1306 } 1307 1308 tmpkey = _PROP_MALLOC(PDK_MAXKEY + 1, M_TEMP); 1309 if (tmpkey == NULL) { 1310 prop_object_release(dict); 1311 return (true); 1312 } 1313 1314 *obj = dict; 1315 /* 1316 * Opening tag is found, storage for key allocated and 1317 * now continue to the first element. 1318 */ 1319 return _prop_dictionary_internalize_body(stack, obj, ctx, tmpkey); 1320 } 1321 1322 static bool 1323 _prop_dictionary_internalize_continue(prop_stack_t stack, prop_object_t *obj, 1324 struct _prop_object_internalize_context *ctx, void *data, prop_object_t child) 1325 { 1326 prop_dictionary_t dict = *obj; 1327 char *tmpkey = data; 1328 1329 _PROP_ASSERT(tmpkey != NULL); 1330 1331 if (child == NULL || 1332 prop_dictionary_set(dict, tmpkey, child) == false) { 1333 _PROP_FREE(tmpkey, M_TEMP); 1334 if (child != NULL) 1335 prop_object_release(child); 1336 prop_object_release(dict); 1337 *obj = NULL; 1338 return (true); 1339 } 1340 1341 prop_object_release(child); 1342 1343 /* 1344 * key, value was added, now continue looking for the next key 1345 * or the closing tag. For JSON, we'll skip the comma separator, 1346 * if present. 1347 * 1348 * By doing this here, we correctly error out if a separator 1349 * is found other than after an element, but this does mean 1350 * that we do allow a trailing comma after the final element 1351 * which isn't allowed in the JSON spec, but seems pretty 1352 * harmless (and there are other JSON parsers that also allow 1353 * it). 1354 * 1355 * Conversely, we don't want to *require* the separator if the 1356 * spec doesn't require it, and we don't know what's next in 1357 * the buffer, so we basically treat the separator as completely 1358 * optional. Since there does not appear to be any ambiguity, 1359 * this also seems pretty harmless. 1360 * 1361 * (FWIW, RFC 8259 section 9 seems to specifically allow this.) 1362 */ 1363 if (ctx->poic_format == PROP_FORMAT_JSON) { 1364 ctx->poic_cp = _prop_intern_skip_whitespace(ctx->poic_cp); 1365 if (*ctx->poic_cp == ',') { 1366 ctx->poic_cp++; 1367 } 1368 } 1369 return _prop_dictionary_internalize_body(stack, obj, ctx, tmpkey); 1370 } 1371 1372 static bool 1373 _prop_dictionary_internalize_body(prop_stack_t stack, prop_object_t *obj, 1374 struct _prop_object_internalize_context *ctx, char *tmpkey) 1375 { 1376 prop_dictionary_t dict = *obj; 1377 size_t keylen; 1378 1379 if (ctx->poic_format == PROP_FORMAT_JSON) { 1380 ctx->poic_cp = _prop_intern_skip_whitespace(ctx->poic_cp); 1381 1382 /* Check to see if this is the end of the dictionary. */ 1383 if (*ctx->poic_cp == '}') { 1384 /* It is, so don't iterate any further. */ 1385 ctx->poic_cp++; 1386 return true; 1387 } 1388 1389 /* It must be the key. */ 1390 if (*ctx->poic_cp != '"') { 1391 goto bad; 1392 } 1393 ctx->poic_cp++; 1394 1395 /* Empty keys are not allowed. */ 1396 if (*ctx->poic_cp == '"') { 1397 goto bad; 1398 } 1399 } else { 1400 /* Fetch the next tag. */ 1401 if (_prop_xml_intern_find_tag(ctx, NULL, 1402 _PROP_TAG_TYPE_EITHER) == false) 1403 goto bad; 1404 1405 /* Check to see if this is the end of the dictionary. */ 1406 if (_PROP_TAG_MATCH(ctx, "dict") && 1407 ctx->poic_tag_type == _PROP_TAG_TYPE_END) { 1408 _PROP_FREE(tmpkey, M_TEMP); 1409 return (true); 1410 } 1411 1412 /* Ok, it must be a non-empty key start tag. */ 1413 if (!_PROP_TAG_MATCH(ctx, "key") || 1414 ctx->poic_tag_type != _PROP_TAG_TYPE_START || 1415 ctx->poic_is_empty_element) 1416 goto bad; 1417 } 1418 1419 if (_prop_intern_decode_string(ctx, tmpkey, PDK_MAXKEY, &keylen, 1420 &ctx->poic_cp) == false) 1421 goto bad; 1422 1423 _PROP_ASSERT(keylen <= PDK_MAXKEY); 1424 tmpkey[keylen] = '\0'; 1425 1426 if (ctx->poic_format == PROP_FORMAT_JSON) { 1427 if (*ctx->poic_cp != '"') { 1428 goto bad; 1429 } 1430 ctx->poic_cp++; 1431 1432 /* 1433 * Next thing we counter needs to be the key/value 1434 * separator. 1435 */ 1436 ctx->poic_cp = _prop_intern_skip_whitespace(ctx->poic_cp); 1437 if (*ctx->poic_cp != ':') { 1438 goto bad; 1439 } 1440 ctx->poic_cp++; 1441 } else { 1442 if (_prop_xml_intern_find_tag(ctx, "key", 1443 _PROP_TAG_TYPE_END) == false) 1444 goto bad; 1445 1446 /* ..and now the beginning of the value. */ 1447 if (_prop_xml_intern_find_tag(ctx, NULL, 1448 _PROP_TAG_TYPE_START) == false) 1449 goto bad; 1450 } 1451 1452 /* 1453 * Key is found, now wait for value to be parsed. 1454 */ 1455 if (_prop_stack_push(stack, *obj, 1456 _prop_dictionary_internalize_continue, 1457 tmpkey, NULL)) 1458 return (false); 1459 1460 bad: 1461 _PROP_FREE(tmpkey, M_TEMP); 1462 prop_object_release(dict); 1463 *obj = NULL; 1464 return (true); 1465 } 1466 1467 /* 1468 * prop_dictionary_internalize -- 1469 * Create a dictionary by parsing the external representation. 1470 */ 1471 _PROP_EXPORT prop_dictionary_t 1472 prop_dictionary_internalize(const char *data) 1473 { 1474 return _prop_object_internalize(data, &_prop_dictionary_type_tags); 1475 } 1476 1477 #if !defined(_KERNEL) && !defined(_STANDALONE) 1478 /* 1479 * prop_dictionary_externalize_to_file -- 1480 * Externalize a dictionary to the specified file. 1481 */ 1482 _PROP_EXPORT bool 1483 prop_dictionary_externalize_to_file(prop_dictionary_t dict, const char *fname) 1484 { 1485 return _prop_object_externalize_to_file(&dict->pd_obj, fname, 1486 PROP_FORMAT_XML); 1487 } 1488 1489 /* 1490 * prop_dictionary_internalize_from_file -- 1491 * Internalize a dictionary from a file. 1492 */ 1493 _PROP_EXPORT prop_dictionary_t 1494 prop_dictionary_internalize_from_file(const char *fname) 1495 { 1496 return _prop_object_internalize_from_file(fname, 1497 &_prop_dictionary_type_tags); 1498 } 1499 #endif /* !_KERNEL && !_STANDALONE */ 1500
Indexes created Sat Sep 20 22:09:52 GMT 2025