common/lib/libprop/prop_dictionary.c

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