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