1 /* $NetBSD: prop_dictionary.c,v 1.35 2009/04/14 02:53:41 haad Exp $ */
4 * Copyright (c) 2006, 2007 The NetBSD Foundation, Inc.
7 * This code is derived from software contributed to The NetBSD Foundation
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
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.
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.
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"
38 #if !defined(_KERNEL) && !defined(_STANDALONE)
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.
48 #define EXPAND_STEP 16
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().
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.
61 struct _prop_dictionary_keysym {
62 struct _prop_object pdk_obj;
64 struct rb_node pdk_link;
66 /* actually variable length */
69 #define RBNODE_TO_PDK(n) \
70 ((struct _prop_dictionary_keysym *) \
71 ((uintptr_t)n - offsetof(struct _prop_dictionary_keysym, pdk_link)))
73 /* pdk_key[1] takes care of the NUL */
74 #define PDK_SIZE_16 (sizeof(struct _prop_dictionary_keysym) + 16)
75 #define PDK_SIZE_32 (sizeof(struct _prop_dictionary_keysym) + 32)
76 #define PDK_SIZE_128 (sizeof(struct _prop_dictionary_keysym) + 128)
78 #define PDK_MAXKEY 128
80 _PROP_POOL_INIT(_prop_dictionary_keysym16_pool, PDK_SIZE_16, "pdict16")
81 _PROP_POOL_INIT(_prop_dictionary_keysym32_pool, PDK_SIZE_32, "pdict32")
82 _PROP_POOL_INIT(_prop_dictionary_keysym128_pool, PDK_SIZE_128, "pdict128")
84 struct _prop_dict_entry {
85 prop_dictionary_keysym_t pde_key;
86 prop_object_t pde_objref;
89 struct _prop_dictionary {
90 struct _prop_object pd_obj;
91 _PROP_RWLOCK_DECL(pd_rwlock)
92 struct _prop_dict_entry *pd_array;
93 unsigned int pd_capacity;
94 unsigned int pd_count;
100 #define PD_F_IMMUTABLE 0x01 /* dictionary is immutable */
102 _PROP_POOL_INIT(_prop_dictionary_pool, sizeof(struct _prop_dictionary),
104 _PROP_MALLOC_DEFINE(M_PROP_DICT, "prop dictionary",
105 "property dictionary container object")
107 static _prop_object_free_rv_t
108 _prop_dictionary_free(prop_stack_t, prop_object_t *);
109 static void _prop_dictionary_emergency_free(prop_object_t);
110 static bool _prop_dictionary_externalize(
111 struct _prop_object_externalize_context *,
113 static _prop_object_equals_rv_t
114 _prop_dictionary_equals(prop_object_t, prop_object_t,
116 prop_object_t *, prop_object_t *);
117 static void _prop_dictionary_equals_finish(prop_object_t, prop_object_t);
118 static prop_object_iterator_t
119 _prop_dictionary_iterator_locked(prop_dictionary_t);
121 _prop_dictionary_iterator_next_object_locked(void *);
123 _prop_dictionary_get_keysym(prop_dictionary_t,
124 prop_dictionary_keysym_t, bool);
126 _prop_dictionary_get(prop_dictionary_t, const char *, bool);
128 static void _prop_dictionary_lock(void);
129 static void _prop_dictionary_unlock(void);
131 static const struct _prop_object_type _prop_object_type_dictionary = {
132 .pot_type = PROP_TYPE_DICTIONARY,
133 .pot_free = _prop_dictionary_free,
134 .pot_emergency_free = _prop_dictionary_emergency_free,
135 .pot_extern = _prop_dictionary_externalize,
136 .pot_equals = _prop_dictionary_equals,
137 .pot_equals_finish = _prop_dictionary_equals_finish,
138 .pot_lock = _prop_dictionary_lock,
139 .pot_unlock = _prop_dictionary_unlock,
142 static _prop_object_free_rv_t
143 _prop_dict_keysym_free(prop_stack_t, prop_object_t *);
144 static bool _prop_dict_keysym_externalize(
145 struct _prop_object_externalize_context *,
147 static _prop_object_equals_rv_t
148 _prop_dict_keysym_equals(prop_object_t, prop_object_t,
150 prop_object_t *, prop_object_t *);
152 static const struct _prop_object_type _prop_object_type_dict_keysym = {
153 .pot_type = PROP_TYPE_DICT_KEYSYM,
154 .pot_free = _prop_dict_keysym_free,
155 .pot_extern = _prop_dict_keysym_externalize,
156 .pot_equals = _prop_dict_keysym_equals,
159 #define prop_object_is_dictionary(x) \
160 ((x) != NULL && (x)->pd_obj.po_type == &_prop_object_type_dictionary)
161 #define prop_object_is_dictionary_keysym(x) \
162 ((x) != NULL && (x)->pdk_obj.po_type == &_prop_object_type_dict_keysym)
164 #define prop_dictionary_is_immutable(x) \
165 (((x)->pd_flags & PD_F_IMMUTABLE) != 0)
167 struct _prop_dictionary_iterator {
168 struct _prop_object_iterator pdi_base;
169 unsigned int pdi_index;
173 * Dictionary key symbols are immutable, and we are likely to have many
174 * duplicated key symbols. So, to save memory, we unique'ify key symbols
175 * so we only have to have one copy of each string.
179 _prop_dict_keysym_rb_compare_nodes(const struct rb_node *n1,
180 const struct rb_node *n2)
182 const prop_dictionary_keysym_t pdk1 = RBNODE_TO_PDK(n1);
183 const prop_dictionary_keysym_t pdk2 = RBNODE_TO_PDK(n2);
185 return (strcmp(pdk1->pdk_key, pdk2->pdk_key));
189 _prop_dict_keysym_rb_compare_key(const struct rb_node *n,
192 const prop_dictionary_keysym_t pdk = RBNODE_TO_PDK(n);
195 return (strcmp(pdk->pdk_key, cp));
198 static const struct rb_tree_ops _prop_dict_keysym_rb_tree_ops = {
199 .rbto_compare_nodes = _prop_dict_keysym_rb_compare_nodes,
200 .rbto_compare_key = _prop_dict_keysym_rb_compare_key,
203 static struct rb_tree _prop_dict_keysym_tree;
205 _PROP_ONCE_DECL(_prop_dict_init_once)
206 _PROP_MUTEX_DECL_STATIC(_prop_dict_keysym_tree_mutex)
209 _prop_dict_init(void)
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);
219 _prop_dict_keysym_put(prop_dictionary_keysym_t pdk)
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);
227 _PROP_ASSERT(pdk->pdk_size <= PDK_SIZE_128);
228 _PROP_POOL_PUT(_prop_dictionary_keysym128_pool, pdk);
233 static _prop_object_free_rv_t
234 _prop_dict_keysym_free(prop_stack_t stack, prop_object_t *obj)
236 prop_dictionary_keysym_t pdk = *obj;
238 _prop_rb_tree_remove_node(&_prop_dict_keysym_tree, &pdk->pdk_link);
239 _prop_dict_keysym_put(pdk);
241 return _PROP_OBJECT_FREE_DONE;
245 _prop_dict_keysym_externalize(struct _prop_object_externalize_context *ctx,
248 prop_dictionary_keysym_t pdk = v;
250 /* We externalize these as strings, and they're never empty. */
252 _PROP_ASSERT(pdk->pdk_key[0] != '\0');
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)
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)
269 prop_dictionary_keysym_t pdk1 = v1;
270 prop_dictionary_keysym_t pdk2 = v2;
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.
277 return _PROP_OBJECT_EQUALS_TRUE;
279 return _PROP_OBJECT_EQUALS_FALSE;
282 static prop_dictionary_keysym_t
283 _prop_dict_keysym_alloc(const char *key)
285 prop_dictionary_keysym_t opdk, pdk;
286 const struct rb_node *n;
290 _PROP_ONCE_RUN(_prop_dict_init_once, _prop_dict_init);
293 * Check to see if this already exists in the tree. If it does,
294 * we just retain it and return it.
296 _PROP_MUTEX_LOCK(_prop_dict_keysym_tree_mutex);
297 n = _prop_rb_tree_find(&_prop_dict_keysym_tree, key);
299 opdk = RBNODE_TO_PDK(n);
300 prop_object_retain(opdk);
301 _PROP_MUTEX_UNLOCK(_prop_dict_keysym_tree_mutex);
304 _PROP_MUTEX_UNLOCK(_prop_dict_keysym_tree_mutex);
307 * Not in the tree. Create it now.
310 size = sizeof(*pdk) + strlen(key) /* pdk_key[1] covers the NUL */;
312 if (size <= PDK_SIZE_16)
313 pdk = _PROP_POOL_GET(_prop_dictionary_keysym16_pool);
314 else if (size <= PDK_SIZE_32)
315 pdk = _PROP_POOL_GET(_prop_dictionary_keysym32_pool);
316 else if (size <= PDK_SIZE_128)
317 pdk = _PROP_POOL_GET(_prop_dictionary_keysym128_pool);
319 pdk = NULL; /* key too long */
324 _prop_object_init(&pdk->pdk_obj, &_prop_object_type_dict_keysym);
326 strcpy(pdk->pdk_key, key);
327 pdk->pdk_size = size;
330 * We dropped the mutex when we allocated the new object, so
331 * we have to check again if it is in the tree.
333 _PROP_MUTEX_LOCK(_prop_dict_keysym_tree_mutex);
334 n = _prop_rb_tree_find(&_prop_dict_keysym_tree, key);
336 opdk = RBNODE_TO_PDK(n);
337 prop_object_retain(opdk);
338 _PROP_MUTEX_UNLOCK(_prop_dict_keysym_tree_mutex);
339 _prop_dict_keysym_put(pdk);
342 rv = _prop_rb_tree_insert_node(&_prop_dict_keysym_tree, &pdk->pdk_link);
343 _PROP_ASSERT(rv == true);
344 _PROP_MUTEX_UNLOCK(_prop_dict_keysym_tree_mutex);
348 static _prop_object_free_rv_t
349 _prop_dictionary_free(prop_stack_t stack, prop_object_t *obj)
351 prop_dictionary_t pd = *obj;
352 prop_dictionary_keysym_t pdk;
355 _PROP_ASSERT(pd->pd_count <= pd->pd_capacity);
356 _PROP_ASSERT((pd->pd_capacity == 0 && pd->pd_array == NULL) ||
357 (pd->pd_capacity != 0 && pd->pd_array != NULL));
359 /* The empty dictorinary is easy, handle that first. */
360 if (pd->pd_count == 0) {
361 if (pd->pd_array != NULL)
362 _PROP_FREE(pd->pd_array, M_PROP_DICT);
364 _PROP_RWLOCK_DESTROY(pd->pd_rwlock);
366 _PROP_POOL_PUT(_prop_dictionary_pool, pd);
368 return (_PROP_OBJECT_FREE_DONE);
371 po = pd->pd_array[pd->pd_count - 1].pde_objref;
372 _PROP_ASSERT(po != NULL);
376 * If we are in emergency release mode,
377 * just let caller recurse down.
380 return (_PROP_OBJECT_FREE_FAILED);
383 /* Otherwise, try to push the current object on the stack. */
384 if (!_prop_stack_push(stack, pd, NULL, NULL, NULL)) {
385 /* Push failed, entering emergency release mode. */
386 return (_PROP_OBJECT_FREE_FAILED);
388 /* Object pushed on stack, caller will release it. */
390 pdk = pd->pd_array[pd->pd_count].pde_key;
391 _PROP_ASSERT(pdk != NULL);
393 prop_object_release(pdk);
396 return (_PROP_OBJECT_FREE_RECURSE);
401 _prop_dictionary_lock(void)
404 /* XXX: once necessary or paranoia? */
405 _PROP_ONCE_RUN(_prop_dict_init_once, _prop_dict_init);
406 _PROP_MUTEX_LOCK(_prop_dict_keysym_tree_mutex);
410 _prop_dictionary_unlock(void)
412 _PROP_MUTEX_UNLOCK(_prop_dict_keysym_tree_mutex);
416 _prop_dictionary_emergency_free(prop_object_t obj)
418 prop_dictionary_t pd = obj;
419 prop_dictionary_keysym_t pdk;
421 _PROP_ASSERT(pd->pd_count != 0);
424 pdk = pd->pd_array[pd->pd_count].pde_key;
425 _PROP_ASSERT(pdk != NULL);
426 prop_object_release(pdk);
430 _prop_dictionary_externalize(struct _prop_object_externalize_context *ctx,
433 prop_dictionary_t pd = v;
434 prop_dictionary_keysym_t pdk;
435 struct _prop_object *po;
436 prop_object_iterator_t pi;
440 _PROP_RWLOCK_RDLOCK(pd->pd_rwlock);
442 if (pd->pd_count == 0) {
443 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock);
444 return (_prop_object_externalize_empty_tag(ctx, "dict"));
447 if (_prop_object_externalize_start_tag(ctx, "dict") == false ||
448 _prop_object_externalize_append_char(ctx, '\n') == false)
451 pi = _prop_dictionary_iterator_locked(pd);
456 _PROP_ASSERT(ctx->poec_depth != 0);
458 while ((pdk = _prop_dictionary_iterator_next_object_locked(pi))
460 po = _prop_dictionary_get_keysym(pd, pdk, true);
462 _prop_object_externalize_start_tag(ctx, "key") == false ||
463 _prop_object_externalize_append_encoded_cstring(ctx,
464 pdk->pdk_key) == false ||
465 _prop_object_externalize_end_tag(ctx, "key") == false ||
466 (*po->po_type->pot_extern)(ctx, po) == false) {
467 prop_object_iterator_release(pi);
472 prop_object_iterator_release(pi);
475 for (i = 0; i < ctx->poec_depth; i++) {
476 if (_prop_object_externalize_append_char(ctx, '\t') == false)
479 if (_prop_object_externalize_end_tag(ctx, "dict") == false)
485 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock);
490 static _prop_object_equals_rv_t
491 _prop_dictionary_equals(prop_object_t v1, prop_object_t v2,
492 void **stored_pointer1, void **stored_pointer2,
493 prop_object_t *next_obj1, prop_object_t *next_obj2)
495 prop_dictionary_t dict1 = v1;
496 prop_dictionary_t dict2 = v2;
498 _prop_object_equals_rv_t rv = _PROP_OBJECT_EQUALS_FALSE;
501 return (_PROP_OBJECT_EQUALS_TRUE);
503 _PROP_ASSERT(*stored_pointer1 == *stored_pointer2);
505 idx = (uintptr_t)*stored_pointer1;
508 if ((uintptr_t)dict1 < (uintptr_t)dict2) {
509 _PROP_RWLOCK_RDLOCK(dict1->pd_rwlock);
510 _PROP_RWLOCK_RDLOCK(dict2->pd_rwlock);
512 _PROP_RWLOCK_RDLOCK(dict2->pd_rwlock);
513 _PROP_RWLOCK_RDLOCK(dict1->pd_rwlock);
517 if (dict1->pd_count != dict2->pd_count)
520 if (idx == dict1->pd_count) {
521 rv = _PROP_OBJECT_EQUALS_TRUE;
525 _PROP_ASSERT(idx < dict1->pd_count);
527 *stored_pointer1 = (void *)(idx + 1);
528 *stored_pointer2 = (void *)(idx + 1);
530 *next_obj1 = &dict1->pd_array[idx].pde_objref;
531 *next_obj2 = &dict2->pd_array[idx].pde_objref;
533 if (!prop_dictionary_keysym_equals(dict1->pd_array[idx].pde_key,
534 dict2->pd_array[idx].pde_key))
537 return (_PROP_OBJECT_EQUALS_RECURSE);
540 _PROP_RWLOCK_UNLOCK(dict1->pd_rwlock);
541 _PROP_RWLOCK_UNLOCK(dict2->pd_rwlock);
546 _prop_dictionary_equals_finish(prop_object_t v1, prop_object_t v2)
548 _PROP_RWLOCK_UNLOCK(((prop_dictionary_t)v1)->pd_rwlock);
549 _PROP_RWLOCK_UNLOCK(((prop_dictionary_t)v2)->pd_rwlock);
552 static prop_dictionary_t
553 _prop_dictionary_alloc(unsigned int capacity)
555 prop_dictionary_t pd;
556 struct _prop_dict_entry *array;
559 array = _PROP_CALLOC(capacity * sizeof(*array), M_PROP_DICT);
565 pd = _PROP_POOL_GET(_prop_dictionary_pool);
567 _prop_object_init(&pd->pd_obj, &_prop_object_type_dictionary);
569 _PROP_RWLOCK_INIT(pd->pd_rwlock);
570 pd->pd_array = array;
571 pd->pd_capacity = capacity;
576 } else if (array != NULL)
577 _PROP_FREE(array, M_PROP_DICT);
583 _prop_dictionary_expand(prop_dictionary_t pd, unsigned int capacity)
585 struct _prop_dict_entry *array, *oarray;
588 * Dictionary must be WRITE-LOCKED.
591 oarray = pd->pd_array;
593 array = _PROP_CALLOC(capacity * sizeof(*array), M_PROP_DICT);
597 memcpy(array, oarray, pd->pd_capacity * sizeof(*array));
598 pd->pd_array = array;
599 pd->pd_capacity = capacity;
602 _PROP_FREE(oarray, M_PROP_DICT);
608 _prop_dictionary_iterator_next_object_locked(void *v)
610 struct _prop_dictionary_iterator *pdi = v;
611 prop_dictionary_t pd = pdi->pdi_base.pi_obj;
612 prop_dictionary_keysym_t pdk = NULL;
614 _PROP_ASSERT(prop_object_is_dictionary(pd));
616 if (pd->pd_version != pdi->pdi_base.pi_version)
617 goto out; /* dictionary changed during iteration */
619 _PROP_ASSERT(pdi->pdi_index <= pd->pd_count);
621 if (pdi->pdi_index == pd->pd_count)
622 goto out; /* we've iterated all objects */
624 pdk = pd->pd_array[pdi->pdi_index].pde_key;
632 _prop_dictionary_iterator_next_object(void *v)
634 struct _prop_dictionary_iterator *pdi = v;
635 prop_dictionary_t pd __unused = pdi->pdi_base.pi_obj;
636 prop_dictionary_keysym_t pdk;
638 _PROP_ASSERT(prop_object_is_dictionary(pd));
640 _PROP_RWLOCK_RDLOCK(pd->pd_rwlock);
641 pdk = _prop_dictionary_iterator_next_object_locked(pdi);
642 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock);
647 _prop_dictionary_iterator_reset_locked(void *v)
649 struct _prop_dictionary_iterator *pdi = v;
650 prop_dictionary_t pd = pdi->pdi_base.pi_obj;
652 _PROP_ASSERT(prop_object_is_dictionary(pd));
655 pdi->pdi_base.pi_version = pd->pd_version;
659 _prop_dictionary_iterator_reset(void *v)
661 struct _prop_dictionary_iterator *pdi = v;
662 prop_dictionary_t pd __unused = pdi->pdi_base.pi_obj;
664 _PROP_RWLOCK_RDLOCK(pd->pd_rwlock);
665 _prop_dictionary_iterator_reset_locked(pdi);
666 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock);
670 * prop_dictionary_create --
671 * Create a dictionary.
674 prop_dictionary_create(void)
677 return (_prop_dictionary_alloc(0));
681 * prop_dictionary_create_with_capacity --
682 * Create a dictionary with the capacity to store N objects.
685 prop_dictionary_create_with_capacity(unsigned int capacity)
688 return (_prop_dictionary_alloc(capacity));
692 * prop_dictionary_copy --
693 * Copy a dictionary. The new dictionary has an initial capacity equal
694 * to the number of objects stored int the original dictionary. The new
695 * dictionary contains refrences to the original dictionary's objects,
696 * not copies of those objects (i.e. a shallow copy).
699 prop_dictionary_copy(prop_dictionary_t opd)
701 prop_dictionary_t pd;
702 prop_dictionary_keysym_t pdk;
706 if (! prop_object_is_dictionary(opd))
709 _PROP_RWLOCK_RDLOCK(opd->pd_rwlock);
711 pd = _prop_dictionary_alloc(opd->pd_count);
713 for (idx = 0; idx < opd->pd_count; idx++) {
714 pdk = opd->pd_array[idx].pde_key;
715 po = opd->pd_array[idx].pde_objref;
717 prop_object_retain(pdk);
718 prop_object_retain(po);
720 pd->pd_array[idx].pde_key = pdk;
721 pd->pd_array[idx].pde_objref = po;
723 pd->pd_count = opd->pd_count;
724 pd->pd_flags = opd->pd_flags;
726 _PROP_RWLOCK_UNLOCK(opd->pd_rwlock);
731 * prop_dictionary_copy_mutable --
732 * Like prop_dictionary_copy(), but the resulting dictionary is
736 prop_dictionary_copy_mutable(prop_dictionary_t opd)
738 prop_dictionary_t pd;
740 if (! prop_object_is_dictionary(opd))
743 pd = prop_dictionary_copy(opd);
745 pd->pd_flags &= ~PD_F_IMMUTABLE;
751 * prop_dictionary_make_immutable --
752 * Set the immutable flag on that dictionary.
755 prop_dictionary_make_immutable(prop_dictionary_t pd)
758 _PROP_RWLOCK_WRLOCK(pd->pd_rwlock);
759 if (prop_dictionary_is_immutable(pd) == false)
760 pd->pd_flags |= PD_F_IMMUTABLE;
761 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock);
765 * prop_dictionary_count --
766 * Return the number of objects stored in the dictionary.
769 prop_dictionary_count(prop_dictionary_t pd)
773 if (! prop_object_is_dictionary(pd))
776 _PROP_RWLOCK_RDLOCK(pd->pd_rwlock);
778 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock);
784 * prop_dictionary_ensure_capacity --
785 * Ensure that the dictionary has the capacity to store the specified
786 * total number of objects (including the objects already stored in
790 prop_dictionary_ensure_capacity(prop_dictionary_t pd, unsigned int capacity)
794 if (! prop_object_is_dictionary(pd))
797 _PROP_RWLOCK_WRLOCK(pd->pd_rwlock);
798 if (capacity > pd->pd_capacity)
799 rv = _prop_dictionary_expand(pd, capacity);
802 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock);
806 static prop_object_iterator_t
807 _prop_dictionary_iterator_locked(prop_dictionary_t pd)
809 struct _prop_dictionary_iterator *pdi;
811 if (! prop_object_is_dictionary(pd))
814 pdi = _PROP_CALLOC(sizeof(*pdi), M_TEMP);
817 pdi->pdi_base.pi_next_object = _prop_dictionary_iterator_next_object;
818 pdi->pdi_base.pi_reset = _prop_dictionary_iterator_reset;
819 prop_object_retain(pd);
820 pdi->pdi_base.pi_obj = pd;
821 _prop_dictionary_iterator_reset_locked(pdi);
823 return (&pdi->pdi_base);
827 * prop_dictionary_iterator --
828 * Return an iterator for the dictionary. The dictionary is retained by
831 prop_object_iterator_t
832 prop_dictionary_iterator(prop_dictionary_t pd)
834 prop_object_iterator_t pi;
836 _PROP_RWLOCK_RDLOCK(pd->pd_rwlock);
837 pi = _prop_dictionary_iterator_locked(pd);
838 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock);
843 * prop_dictionary_all_keys --
844 * Return an array containing a snapshot of all of the keys
848 prop_dictionary_all_keys(prop_dictionary_t pd)
854 if (! prop_object_is_dictionary(pd))
857 /* There is no pressing need to lock the dictionary for this. */
858 array = prop_array_create_with_capacity(pd->pd_count);
860 _PROP_RWLOCK_RDLOCK(pd->pd_rwlock);
862 for (idx = 0; idx < pd->pd_count; idx++) {
863 rv = prop_array_add(array, pd->pd_array[idx].pde_key);
868 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock);
871 prop_object_release(array);
877 static struct _prop_dict_entry *
878 _prop_dict_lookup(prop_dictionary_t pd, const char *key,
881 struct _prop_dict_entry *pde;
882 unsigned int base, idx, distance;
886 * Dictionary must be READ-LOCKED or WRITE-LOCKED.
889 for (idx = 0, base = 0, distance = pd->pd_count; distance != 0;
891 idx = base + (distance >> 1);
892 pde = &pd->pd_array[idx];
893 _PROP_ASSERT(pde->pde_key != NULL);
894 res = strcmp(key, pde->pde_key->pdk_key);
900 if (res > 0) { /* key > pdk_key: move right */
903 } /* else move left */
906 /* idx points to the slot we looked at last. */
913 _prop_dictionary_get(prop_dictionary_t pd, const char *key, bool locked)
915 const struct _prop_dict_entry *pde;
916 prop_object_t po = NULL;
918 if (! prop_object_is_dictionary(pd))
922 _PROP_RWLOCK_RDLOCK(pd->pd_rwlock);
923 pde = _prop_dict_lookup(pd, key, NULL);
925 _PROP_ASSERT(pde->pde_objref != NULL);
926 po = pde->pde_objref;
929 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock);
933 * prop_dictionary_get --
934 * Return the object stored with specified key.
937 prop_dictionary_get(prop_dictionary_t pd, const char *key)
939 prop_object_t po = NULL;
941 if (! prop_object_is_dictionary(pd))
944 _PROP_RWLOCK_RDLOCK(pd->pd_rwlock);
945 po = _prop_dictionary_get(pd, key, true);
946 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock);
951 _prop_dictionary_get_keysym(prop_dictionary_t pd, prop_dictionary_keysym_t pdk,
955 if (! (prop_object_is_dictionary(pd) &&
956 prop_object_is_dictionary_keysym(pdk)))
959 return (_prop_dictionary_get(pd, pdk->pdk_key, locked));
963 * prop_dictionary_get_keysym --
964 * Return the object stored at the location encoded by the keysym.
967 prop_dictionary_get_keysym(prop_dictionary_t pd, prop_dictionary_keysym_t pdk)
970 return (_prop_dictionary_get_keysym(pd, pdk, false));
974 * prop_dictionary_set --
975 * Store a reference to an object at with the specified key.
976 * If the key already exisit, the original object is released.
979 prop_dictionary_set(prop_dictionary_t pd, const char *key, prop_object_t po)
981 struct _prop_dict_entry *pde;
982 prop_dictionary_keysym_t pdk;
986 if (! prop_object_is_dictionary(pd))
989 _PROP_ASSERT(pd->pd_count <= pd->pd_capacity);
991 if (prop_dictionary_is_immutable(pd))
994 _PROP_RWLOCK_WRLOCK(pd->pd_rwlock);
996 pde = _prop_dict_lookup(pd, key, &idx);
998 prop_object_t opo = pde->pde_objref;
999 prop_object_retain(po);
1000 pde->pde_objref = po;
1001 prop_object_release(opo);
1006 pdk = _prop_dict_keysym_alloc(key);
1010 if (pd->pd_count == pd->pd_capacity &&
1011 _prop_dictionary_expand(pd,
1012 pd->pd_capacity + EXPAND_STEP) == false) {
1013 prop_object_release(pdk);
1017 /* At this point, the store will succeed. */
1018 prop_object_retain(po);
1020 if (pd->pd_count == 0) {
1021 pd->pd_array[0].pde_key = pdk;
1022 pd->pd_array[0].pde_objref = po;
1029 pde = &pd->pd_array[idx];
1030 _PROP_ASSERT(pde->pde_key != NULL);
1032 if (strcmp(key, pde->pde_key->pdk_key) < 0) {
1034 * key < pdk_key: insert to the left. This is the same as
1035 * inserting to the right, except we decrement the current
1038 * Because we're unsigned, we have to special case 0
1042 memmove(&pd->pd_array[1], &pd->pd_array[0],
1043 pd->pd_count * sizeof(*pde));
1044 pd->pd_array[0].pde_key = pdk;
1045 pd->pd_array[0].pde_objref = po;
1054 memmove(&pd->pd_array[idx + 2], &pd->pd_array[idx + 1],
1055 (pd->pd_count - (idx + 1)) * sizeof(*pde));
1056 pd->pd_array[idx + 1].pde_key = pdk;
1057 pd->pd_array[idx + 1].pde_objref = po;
1065 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock);
1070 * prop_dictionary_set_keysym --
1071 * Replace the object in the dictionary at the location encoded by
1075 prop_dictionary_set_keysym(prop_dictionary_t pd, prop_dictionary_keysym_t pdk,
1079 if (! (prop_object_is_dictionary(pd) &&
1080 prop_object_is_dictionary_keysym(pdk)))
1083 return (prop_dictionary_set(pd, pdk->pdk_key, po));
1087 _prop_dictionary_remove(prop_dictionary_t pd, struct _prop_dict_entry *pde,
1090 prop_dictionary_keysym_t pdk = pde->pde_key;
1091 prop_object_t po = pde->pde_objref;
1094 * Dictionary must be WRITE-LOCKED.
1097 _PROP_ASSERT(pd->pd_count != 0);
1098 _PROP_ASSERT(idx < pd->pd_count);
1099 _PROP_ASSERT(pde == &pd->pd_array[idx]);
1102 memmove(&pd->pd_array[idx - 1], &pd->pd_array[idx],
1103 (pd->pd_count - idx) * sizeof(*pde));
1108 prop_object_release(pdk);
1110 prop_object_release(po);
1114 * prop_dictionary_remove --
1115 * Remove the reference to an object with the specified key from
1119 prop_dictionary_remove(prop_dictionary_t pd, const char *key)
1121 struct _prop_dict_entry *pde;
1124 if (! prop_object_is_dictionary(pd))
1127 _PROP_RWLOCK_WRLOCK(pd->pd_rwlock);
1129 /* XXX Should this be a _PROP_ASSERT()? */
1130 if (prop_dictionary_is_immutable(pd))
1133 pde = _prop_dict_lookup(pd, key, &idx);
1134 /* XXX Should this be a _PROP_ASSERT()? */
1138 _prop_dictionary_remove(pd, pde, idx);
1140 _PROP_RWLOCK_UNLOCK(pd->pd_rwlock);
1144 * prop_dictionary_remove_keysym --
1145 * Remove a reference to an object stored in the dictionary at the
1146 * location encoded by the keysym.
1149 prop_dictionary_remove_keysym(prop_dictionary_t pd,
1150 prop_dictionary_keysym_t pdk)
1153 if (! (prop_object_is_dictionary(pd) &&
1154 prop_object_is_dictionary_keysym(pdk)))
1157 prop_dictionary_remove(pd, pdk->pdk_key);
1161 * prop_dictionary_equals --
1162 * Return true if the two dictionaries are equivalent. Note we do a
1163 * by-value comparison of the objects in the dictionary.
1166 prop_dictionary_equals(prop_dictionary_t dict1, prop_dictionary_t dict2)
1168 if (!prop_object_is_dictionary(dict1) ||
1169 !prop_object_is_dictionary(dict2))
1172 return (prop_object_equals(dict1, dict2));
1176 * prop_dictionary_keysym_cstring_nocopy --
1177 * Return an immutable reference to the keysym's value.
1180 prop_dictionary_keysym_cstring_nocopy(prop_dictionary_keysym_t pdk)
1183 if (! prop_object_is_dictionary_keysym(pdk))
1186 return (pdk->pdk_key);
1190 * prop_dictionary_keysym_equals --
1191 * Return true if the two dictionary key symbols are equivalent.
1192 * Note: We do not compare the object references.
1195 prop_dictionary_keysym_equals(prop_dictionary_keysym_t pdk1,
1196 prop_dictionary_keysym_t pdk2)
1198 if (!prop_object_is_dictionary_keysym(pdk1) ||
1199 !prop_object_is_dictionary_keysym(pdk2))
1202 return (prop_object_equals(pdk1, pdk2));
1206 * prop_dictionary_externalize --
1207 * Externalize a dictionary, returning a NUL-terminated buffer
1208 * containing the XML-style representation. The buffer is allocated
1209 * with the M_TEMP memory type.
1212 prop_dictionary_externalize(prop_dictionary_t pd)
1214 struct _prop_object_externalize_context *ctx;
1217 ctx = _prop_object_externalize_context_alloc();
1221 if (_prop_object_externalize_header(ctx) == false ||
1222 (*pd->pd_obj.po_type->pot_extern)(ctx, pd) == false ||
1223 _prop_object_externalize_footer(ctx) == false) {
1224 /* We are responsible for releasing the buffer. */
1225 _PROP_FREE(ctx->poec_buf, M_TEMP);
1226 _prop_object_externalize_context_free(ctx);
1231 _prop_object_externalize_context_free(ctx);
1237 * _prop_dictionary_internalize --
1238 * Parse a <dict>...</dict> and return the object created from the
1239 * external representation.
1241 * Internal state in via rec_data is the storage area for the last processed
1243 * _prop_dictionary_internalize_body is the upper half of the parse loop.
1244 * It is responsible for parsing the key directly and storing it in the area
1245 * referenced by rec_data.
1246 * _prop_dictionary_internalize_cont is the lower half and called with the value
1247 * associated with the key.
1249 static bool _prop_dictionary_internalize_body(prop_stack_t,
1250 prop_object_t *, struct _prop_object_internalize_context *, char *);
1253 _prop_dictionary_internalize(prop_stack_t stack, prop_object_t *obj,
1254 struct _prop_object_internalize_context *ctx)
1256 prop_dictionary_t dict;
1259 /* We don't currently understand any attributes. */
1260 if (ctx->poic_tagattr != NULL)
1263 dict = prop_dictionary_create();
1267 if (ctx->poic_is_empty_element) {
1272 tmpkey = _PROP_MALLOC(PDK_MAXKEY + 1, M_TEMP);
1273 if (tmpkey == NULL) {
1274 prop_object_release(dict);
1280 * Opening tag is found, storage for key allocated and
1281 * now continue to the first element.
1283 return _prop_dictionary_internalize_body(stack, obj, ctx, tmpkey);
1287 _prop_dictionary_internalize_continue(prop_stack_t stack, prop_object_t *obj,
1288 struct _prop_object_internalize_context *ctx, void *data, prop_object_t child)
1290 prop_dictionary_t dict = *obj;
1291 char *tmpkey = data;
1293 _PROP_ASSERT(tmpkey != NULL);
1295 if (child == NULL ||
1296 prop_dictionary_set(dict, tmpkey, child) == false) {
1297 _PROP_FREE(tmpkey, M_TEMP);
1299 prop_object_release(child);
1300 prop_object_release(dict);
1305 prop_object_release(child);
1308 * key, value was added, now continue looking for the next key
1309 * or the closing tag.
1311 return _prop_dictionary_internalize_body(stack, obj, ctx, tmpkey);
1315 _prop_dictionary_internalize_body(prop_stack_t stack, prop_object_t *obj,
1316 struct _prop_object_internalize_context *ctx, char *tmpkey)
1318 prop_dictionary_t dict = *obj;
1321 /* Fetch the next tag. */
1322 if (_prop_object_internalize_find_tag(ctx, NULL, _PROP_TAG_TYPE_EITHER) == false)
1325 /* Check to see if this is the end of the dictionary. */
1326 if (_PROP_TAG_MATCH(ctx, "dict") &&
1327 ctx->poic_tag_type == _PROP_TAG_TYPE_END) {
1328 _PROP_FREE(tmpkey, M_TEMP);
1332 /* Ok, it must be a non-empty key start tag. */
1333 if (!_PROP_TAG_MATCH(ctx, "key") ||
1334 ctx->poic_tag_type != _PROP_TAG_TYPE_START ||
1335 ctx->poic_is_empty_element)
1338 if (_prop_object_internalize_decode_string(ctx,
1339 tmpkey, PDK_MAXKEY, &keylen,
1340 &ctx->poic_cp) == false)
1343 _PROP_ASSERT(keylen <= PDK_MAXKEY);
1344 tmpkey[keylen] = '\0';
1346 if (_prop_object_internalize_find_tag(ctx, "key",
1347 _PROP_TAG_TYPE_END) == false)
1350 /* ..and now the beginning of the value. */
1351 if (_prop_object_internalize_find_tag(ctx, NULL,
1352 _PROP_TAG_TYPE_START) == false)
1356 * Key is found, now wait for value to be parsed.
1358 if (_prop_stack_push(stack, *obj,
1359 _prop_dictionary_internalize_continue,
1364 _PROP_FREE(tmpkey, M_TEMP);
1365 prop_object_release(dict);
1371 * prop_dictionary_internalize --
1372 * Create a dictionary by parsing the NUL-terminated XML-style
1376 prop_dictionary_internalize(const char *xml)
1378 return _prop_generic_internalize(xml, "dict");
1381 #if !defined(_KERNEL) && !defined(_STANDALONE)
1383 * prop_dictionary_externalize_to_file --
1384 * Externalize a dictionary to the specified file.
1387 prop_dictionary_externalize_to_file(prop_dictionary_t dict, const char *fname)
1391 int save_errno = 0; /* XXXGCC -Wuninitialized [mips, ...] */
1393 xml = prop_dictionary_externalize(dict);
1396 rv = _prop_object_externalize_write_file(fname, xml, strlen(xml));
1399 _PROP_FREE(xml, M_TEMP);
1407 * prop_dictionary_internalize_from_file --
1408 * Internalize a dictionary from a file.
1411 prop_dictionary_internalize_from_file(const char *fname)
1413 struct _prop_object_internalize_mapped_file *mf;
1414 prop_dictionary_t dict;
1416 mf = _prop_object_internalize_map_file(fname);
1419 dict = prop_dictionary_internalize(mf->poimf_xml);
1420 _prop_object_internalize_unmap_file(mf);
1424 #endif /* !_KERNEL && !_STANDALONE */