sys/libprop/prop_dictionary.c

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