The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/libprop/prop_dictionary.c

Version: -  FREEBSD  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-2  -  FREEBSD-11-1  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-4  -  FREEBSD-10-3  -  FREEBSD-10-2  -  FREEBSD-10-1  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-3  -  FREEBSD-9-2  -  FREEBSD-9-1  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-4  -  FREEBSD-8-3  -  FREEBSD-8-2  -  FREEBSD-8-1  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-4  -  FREEBSD-7-3  -  FREEBSD-7-2  -  FREEBSD-7-1  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-4  -  FREEBSD-6-3  -  FREEBSD-6-2  -  FREEBSD-6-1  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-5  -  FREEBSD-5-4  -  FREEBSD-5-3  -  FREEBSD-5-2  -  FREEBSD-5-1  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  linux-2.6  -  linux-2.4.22  -  MK83  -  MK84  -  PLAN9  -  DFBSD  -  NETBSD  -  NETBSD5  -  NETBSD4  -  NETBSD3  -  NETBSD20  -  OPENBSD  -  xnu-517  -  xnu-792  -  xnu-792.6.70  -  xnu-1228  -  xnu-1456.1.26  -  xnu-1699.24.8  -  xnu-2050.18.24  -  OPENSOLARIS  -  minix-3-1-1 
SearchContext: -  none  -  3  -  10 

    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 */

Cache object: 247ee79ad83140beadde6bd2f20483b4


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.