xref: /dragonfly/sys/libprop/prop_dictionary.c (revision f3f3eadb)
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*/
_prop_dict_keysym_rb_compare_nodes(void * ctx __unused,const void * n1,const void * n2)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*/
_prop_dict_keysym_rb_compare_key(void * ctx __unused,const void * n,const void * v)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)
_PROP_MUTEX_DECL_STATIC(_prop_dict_keysym_tree_mutex)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
_prop_dict_keysym_put(prop_dictionary_keysym_t pdk)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
_prop_dict_keysym_free(prop_stack_t stack,prop_object_t * obj)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
_prop_dict_keysym_externalize(struct _prop_object_externalize_context * ctx,void * v)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
_prop_dict_keysym_equals(prop_object_t v1,prop_object_t v2,void ** stored_pointer1,void ** stored_pointer2,prop_object_t * next_obj1,prop_object_t * next_obj2)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
_prop_dict_keysym_alloc(const char * key)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
_prop_dictionary_free(prop_stack_t stack,prop_object_t * obj)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
_prop_dictionary_lock(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
_prop_dictionary_unlock(void)406 _prop_dictionary_unlock(void)
407 {
408 	_PROP_MUTEX_UNLOCK(_prop_dict_keysym_tree_mutex);
409 }
410 
411 static void
_prop_dictionary_emergency_free(prop_object_t obj)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
_prop_dictionary_externalize(struct _prop_object_externalize_context * ctx,void * v)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
_prop_dictionary_equals(prop_object_t v1,prop_object_t v2,void ** stored_pointer1,void ** stored_pointer2,prop_object_t * next_obj1,prop_object_t * next_obj2)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
_prop_dictionary_equals_finish(prop_object_t v1,prop_object_t v2)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
_prop_dictionary_alloc(unsigned int capacity)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
_prop_dictionary_expand(prop_dictionary_t pd,unsigned int capacity)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
_prop_dictionary_iterator_next_object_locked(void * v)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
_prop_dictionary_iterator_next_object(void * v)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
_prop_dictionary_iterator_reset_locked(void * v)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
_prop_dictionary_iterator_reset(void * v)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
prop_dictionary_create(void)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
prop_dictionary_create_with_capacity(unsigned int capacity)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
prop_dictionary_copy(prop_dictionary_t opd)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
prop_dictionary_copy_mutable(prop_dictionary_t opd)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
prop_dictionary_make_immutable(prop_dictionary_t pd)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
prop_dictionary_count(prop_dictionary_t pd)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
prop_dictionary_ensure_capacity(prop_dictionary_t pd,unsigned int capacity)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
_prop_dictionary_iterator_locked(prop_dictionary_t pd)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
prop_dictionary_iterator(prop_dictionary_t pd)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
prop_dictionary_all_keys(prop_dictionary_t pd)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 *
_prop_dict_lookup(prop_dictionary_t pd,const char * key,unsigned int * idxp)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
_prop_dictionary_get(prop_dictionary_t pd,const char * key,bool locked)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
prop_dictionary_get(prop_dictionary_t pd,const char * key)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
_prop_dictionary_get_keysym(prop_dictionary_t pd,prop_dictionary_keysym_t pdk,bool locked)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
prop_dictionary_get_keysym(prop_dictionary_t pd,prop_dictionary_keysym_t pdk)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
prop_dictionary_set(prop_dictionary_t pd,const char * key,prop_object_t po)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
prop_dictionary_set_keysym(prop_dictionary_t pd,prop_dictionary_keysym_t pdk,prop_object_t po)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
_prop_dictionary_remove(prop_dictionary_t pd,struct _prop_dict_entry * pde,unsigned int idx)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
prop_dictionary_remove(prop_dictionary_t pd,const char * key)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
prop_dictionary_remove_keysym(prop_dictionary_t pd,prop_dictionary_keysym_t pdk)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
prop_dictionary_equals(prop_dictionary_t dict1,prop_dictionary_t dict2)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 *
prop_dictionary_keysym_cstring_nocopy(prop_dictionary_keysym_t pdk)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
prop_dictionary_keysym_equals(prop_dictionary_keysym_t pdk1,prop_dictionary_keysym_t pdk2)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 *
prop_dictionary_externalize(prop_dictionary_t pd)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
_prop_dictionary_internalize(prop_stack_t stack,prop_object_t * obj,struct _prop_object_internalize_context * ctx)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
_prop_dictionary_internalize_continue(prop_stack_t stack,prop_object_t * obj,struct _prop_object_internalize_context * ctx,void * data,prop_object_t child)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
_prop_dictionary_internalize_body(prop_stack_t stack,prop_object_t * obj,struct _prop_object_internalize_context * ctx,char * tmpkey)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
prop_dictionary_internalize(const char * xml)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
prop_dictionary_externalize_to_file(prop_dictionary_t dict,const char * fname)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
prop_dictionary_internalize_from_file(const char * fname)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 */
1421