1/*
2 * Copyright (c) 2009 Apple Inc.  All rights reserved.
3 *
4 * @APPLE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. Please obtain a copy of the License at
10 * http://www.opensource.apple.com/apsl/ and read it before using this
11 * file.
12 *
13 * The Original Code and all software distributed under the License are
14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
18 * Please see the License for the specific language governing rights and
19 * limitations under the License.
20 *
21 * @APPLE_LICENSE_HEADER_END@
22 */
23
24#include <stdarg.h>
25#include <stdio.h>
26#include <stdlib.h>
27#include <string.h>
28#include <kvbuf.h>
29
30#define KVBUF_CHUNK 256
31
32/*
33 * kvbuf_t is a list of key/value dictionaries.
34 *
35 * First 4 bytes are the number of dictionaries.
36 * For each dictionary, first 4 bytes is the key / value list count.
37 * For each value list, first 4 bytes is the list length.
38 * Keys and values are a 4-byte length followed by a nul-terminated string
39 *
40 * When the databuf needs to grow, we add memory in KVBUF_CHUNK size
41 * increments to reduce malloc / realloc activity.
42 * The _size variable stores the actual allocated size.
43 * The datalen variable stores the used data size.
44 *
45 * The _dict variable holds an offset from the start of the buffer
46 * to the "current" dictionary.  kvbuf_reset() resets this,
47 * and kvbuf_next_dict() bumps the offset so that databuf + _dict
48 * points to the next dictionary.
49 *
50 * The _key variable holds an offset from the start of the buffer
51 * to the "current" key.  kvbuf_reset() resets this, and
52 * kvbuf_next_key() bumps the offset so that databuf + _key
53 * points to the next key.
54 *
55 * The _val variable holds an offset from the start of the buffer
56 * to the "current" value.  kvbuf_reset() resets this, and
57 * kvbuf_next_val() bumps the offset so that databuf + _val
58 * points to the next value.
59 *
60 * The cache_entry_list_to_kvbuf() routine contains the only
61 * code that builds an array.
62 *
63 */
64
65/*
66 * kvbuf_query is a simple utility for constructing a
67 * kvbuf with a single dictionary.  The format string may
68 * contain the chars "k", "s", "i", and "u".  "k" denotes a key
69 * (keys are always strings), "s" denotes a string value,
70 * "i" denotes a 32 bit signed int, and "u" denotes an unsigned.
71 */
72kvbuf_t *
73kvbuf_query(char *fmt, ...)
74{
75	va_list ap;
76	char *arg, *f, str[32];
77	int32_t iarg;
78	uint32_t uarg;
79	kvbuf_t *kv;
80
81	if (fmt == NULL) return NULL;
82
83	kv = kvbuf_new();
84	if (kv == NULL) return NULL;
85
86	kvbuf_add_dict(kv);
87
88	va_start(ap, fmt);
89	for (f = fmt; (*f) != '\0'; f++)
90	{
91		if (*f == 'k')
92		{
93			arg = va_arg(ap, char *);
94			kvbuf_add_key(kv, arg);
95		}
96		else if (*f == 's')
97		{
98			arg = va_arg(ap, char *);
99			kvbuf_add_val(kv, arg);
100		}
101		else if (*f == 'i')
102		{
103			iarg = va_arg(ap, int32_t);
104			snprintf(str, sizeof(str), "%d", iarg);
105			kvbuf_add_val(kv, str);
106		}
107		else if (*f == 'u')
108		{
109			uarg = va_arg(ap,uint32_t);
110			snprintf(str, sizeof(str), "%u", uarg);
111			kvbuf_add_val(kv, str);
112		}
113	}
114	va_end(ap);
115
116	return kv;
117}
118
119kvbuf_t *
120kvbuf_query_key_val(const char *key, const char *val)
121{
122	kvbuf_t *kv;
123	uint32_t x, kl, vl, vc;
124	char *p;
125
126	if (key == NULL) return NULL;
127
128	kl = strlen(key) + 1;
129
130	vl = 0;
131	vc = 0;
132
133	if (val != NULL)
134	{
135		vl = strlen(val) + 1;
136		vc = 1;
137	}
138
139	kv = (kvbuf_t *)calloc(1, sizeof(kvbuf_t));
140	if (kv == NULL) return NULL;
141
142	kv->_size = (5 * sizeof(uint32_t)) + kl + vl;
143	kv->datalen = kv->_size;
144
145	kv->databuf = calloc(1, kv->_size);
146	if (kv->databuf == NULL)
147	{
148		free(kv);
149		return NULL;
150	}
151
152	p = kv->databuf;
153
154	/* 1 dict */
155	x = htonl(1);
156	memcpy(p, &x, sizeof(uint32_t));
157	p += sizeof(uint32_t);
158
159	/* 1 key */
160	memcpy(p, &x, sizeof(uint32_t));
161	p += sizeof(uint32_t);
162
163	/* key length */
164	x = htonl(kl);
165	memcpy(p, &x, sizeof(uint32_t));
166	p += sizeof(uint32_t);
167
168	/* key */
169	memcpy(p, key, kl);
170	p += kl;
171
172	/* number of values */
173	x = htonl(vc);
174	memcpy(p, &x, sizeof(uint32_t));
175	p += sizeof(uint32_t);
176
177	if (vc > 0)
178	{
179		/* value length */
180		x = htonl(vl);
181		memcpy(p, &x, sizeof(uint32_t));
182		p += sizeof(uint32_t);
183
184		/* value */
185		memcpy(p, val, vl);
186	}
187
188	return kv;
189}
190
191kvbuf_t *
192kvbuf_query_key_int(const char *key, int32_t i)
193{
194	char str[32];
195
196	snprintf(str, sizeof(str), "%d", i);
197	return kvbuf_query_key_val(key, str);
198}
199
200kvbuf_t *
201kvbuf_query_key_uint(const char *key, uint32_t u)
202{
203	char str[32];
204
205	snprintf(str, sizeof(str), "%u", u);
206	return kvbuf_query_key_val(key, str);
207}
208
209kvbuf_t *
210kvbuf_new_zone(malloc_zone_t *zone)
211{
212	kvbuf_t *kv;
213
214	if (zone == NULL) return NULL;
215
216	kv = (kvbuf_t *)malloc_zone_calloc(zone, 1, sizeof(kvbuf_t));
217	if (kv == NULL) return NULL;
218
219	kv->_size = KVBUF_START_SIZE;
220	kv->databuf = malloc_zone_calloc(zone, 1, kv->_size);
221	if (kv->databuf == NULL)
222	{
223		free(kv);
224		return NULL;
225	}
226
227	kv->datalen = sizeof(uint32_t);
228	kv->_dict = kv->datalen;
229
230	return kv;
231}
232
233kvbuf_t *
234kvbuf_new(void)
235{
236	return kvbuf_new_zone(malloc_default_zone());
237}
238
239kvbuf_t *
240kvbuf_init_zone(malloc_zone_t *zone, char *buffer, uint32_t length)
241{
242	kvbuf_t *kv;
243
244	if (zone == NULL) return NULL;
245
246	kv = (kvbuf_t *)malloc_zone_calloc(zone, 1, sizeof(kvbuf_t));
247	if (kv == NULL) return NULL;
248
249	kv->_size = length;
250	kv->datalen = length;
251	if (length > 0)
252	{
253		kv->databuf = malloc_zone_calloc(zone, 1, length);
254		if (kv->databuf == NULL)
255		{
256			free(kv);
257			kv = NULL;
258		}
259		else
260		{
261			memcpy(kv->databuf, buffer, length);
262		}
263	}
264
265	return kv;
266}
267
268kvbuf_t *
269kvbuf_init(char *buffer, uint32_t length)
270{
271	return kvbuf_init_zone(malloc_default_zone(), buffer, length);
272}
273
274static void
275kvbuf_grow(kvbuf_t *kv, uint32_t delta)
276{
277	uint32_t newlen;
278	char *p, *newbuf;
279	malloc_zone_t *zone;
280
281	if (kv == NULL) return;
282	if (delta == 0) return;
283
284	if (kv->databuf == NULL) delta += sizeof(uint32_t);
285
286	newlen = kv->datalen + delta;
287	if (newlen <= kv->_size) return;
288
289	kv->_size = ((newlen + KVBUF_CHUNK - 1) / KVBUF_CHUNK) * KVBUF_CHUNK;
290
291	zone = malloc_zone_from_ptr(kv);
292	if (kv->databuf == NULL)
293	{
294		kv->databuf = malloc_zone_calloc(zone, 1, kv->_size);
295		if (kv->databuf == NULL)
296		{
297			memset(kv, 0, sizeof(kvbuf_t));
298			return;
299		}
300
301		kv->datalen = sizeof(uint32_t);
302		kv->_dict = sizeof(uint32_t);
303	}
304	else
305	{
306		newbuf = malloc_zone_realloc(zone, kv->databuf, kv->_size);
307		if (newbuf == NULL) free(kv->databuf);
308		kv->databuf = newbuf;
309		if (kv->databuf == NULL)
310		{
311			memset(kv, 0, sizeof(kvbuf_t));
312			return;
313		}
314
315		p = kv->databuf + kv->datalen;
316		memset(p, 0, kv->_size - kv->datalen);
317	}
318}
319
320void
321kvbuf_add_dict(kvbuf_t *kv)
322{
323	char *p;
324	uint32_t x, dict_count;
325
326	if (kv == NULL) return;
327
328	/* Add a key count */
329	kvbuf_grow(kv, sizeof(uint32_t));
330	if (kv->databuf == NULL) return;
331
332	kv->_dict = kv->datalen;
333	kv->datalen += sizeof(uint32_t);
334
335	kv->_key = kv->datalen;
336	kv->_vlist = 0;
337	kv->_val = 0;
338
339	/* increment and rewrite the dict count */
340	p = kv->databuf;
341
342	x = 0;
343	memcpy(&x, p, sizeof(uint32_t));
344	dict_count = ntohl(x);
345
346	dict_count++;
347	x = htonl(dict_count);
348	memcpy(p, &x, sizeof(uint32_t));
349}
350
351void
352kvbuf_add_key(kvbuf_t *kv, const char *key)
353{
354	uint32_t kl, x, key_count, delta;
355	char *p;
356
357	if (kv == NULL) return;
358	if (key == NULL) return;
359
360	kl = strlen(key) + 1;
361
362	/* Grow to hold key len, key, and value list count. */
363	delta = (2 * sizeof(uint32_t)) + kl;
364	kvbuf_grow(kv, delta);
365
366	if (kv->databuf == NULL) return;
367
368	/* increment and rewrite the key count for the current dictionary */
369	p = kv->databuf + kv->_dict;
370
371	x = 0;
372	memcpy(&x, p, sizeof(uint32_t));
373	key_count = ntohl(x);
374
375	if (key_count == 0) kv->_key = kv->_dict + sizeof(uint32_t);
376	else kv->_key = kv->datalen;
377
378	key_count++;
379	x = htonl(key_count);
380	memcpy(p, &x, sizeof(uint32_t));
381
382	/* append key to data buffer */
383	p = kv->databuf + kv->datalen;
384
385	x = htonl(kl);
386	memcpy(p, &x, sizeof(uint32_t));
387	p += sizeof(uint32_t);
388	memcpy(p, key, kl);
389	p += kl;
390
391	kv->_vlist = kv->datalen + sizeof(uint32_t) + kl;
392
393	x = 0;
394	memcpy(p, &x, sizeof(uint32_t));
395
396	kv->datalen += delta;
397	kv->_val = kv->datalen;
398}
399
400void
401kvbuf_add_val_len(kvbuf_t *kv, const char *val, uint32_t len)
402{
403	uint32_t x, val_count, delta;
404	char *p;
405
406	if (kv == NULL) return;
407	if (val == NULL) return;
408	if (len == 0) return;
409
410	/* Grow to hold val len and value. */
411	delta = sizeof(uint32_t) + len;
412	kvbuf_grow(kv, delta);
413
414	if (kv->databuf == NULL) return;
415
416	/* increment and rewrite the value count for the value_list dictionary */
417	p = kv->databuf + kv->_vlist;
418
419	x = 0;
420	memcpy(&x, p, sizeof(uint32_t));
421	val_count = ntohl(x);
422	val_count++;
423	x = htonl(val_count);
424	memcpy(p, &x, sizeof(uint32_t));
425
426	/* append val to data buffer */
427	p = kv->databuf + kv->_val;
428
429	x = htonl(len);
430	memcpy(p, &x, sizeof(uint32_t));
431	p += sizeof(uint32_t);
432	memcpy(p, val, len);
433	p += len;
434
435	kv->datalen += delta;
436	kv->_val = kv->datalen;
437}
438
439/*
440 * WARNING!  Kludge Alert!
441 *
442 * This call just looks for the buffer length encoded into a serialized kvbuf_t,
443 * which preceeds a pointer to a key or value.  Obviously, calling it with anything
444 * other than a pointer value which is embedded in a kvbuf_t is asking for trouble.
445 */
446uint32_t
447kvbuf_get_len(const char *p)
448{
449	uint32_t x;
450
451	x = 0;
452	memcpy(&x, p - sizeof(uint32_t), sizeof(uint32_t));
453	return ntohl(x);
454}
455
456void
457kvbuf_add_val(kvbuf_t *kv, const char *val)
458{
459	if (kv == NULL) return;
460	if (val == NULL) return;
461
462	kvbuf_add_val_len(kv, val, strlen(val) + 1);
463}
464
465void
466kvbuf_make_purgeable(kvbuf_t *kv)
467{
468	if (kv == NULL) return;
469
470	if (kv->databuf != NULL) malloc_make_purgeable(kv->databuf);
471}
472
473int
474kvbuf_make_nonpurgeable(kvbuf_t *kv)
475{
476	if (kv == NULL) return 0;
477
478	/*
479	 * malloc_make_nonpurgeable returns 0 even if memory was not
480	 * allocated from the purgeable zone, so this is safe to call.
481	 */
482	if ((kv->databuf == NULL) || (malloc_make_nonpurgeable(kv->databuf) == 0)) return 0;
483
484	/* return non-zero since something failed */
485	return 1;
486}
487
488void
489kvbuf_free(kvbuf_t *kv)
490{
491	if (kv == NULL) return;
492
493	if (kv->databuf != NULL) free(kv->databuf);
494	memset(kv, 0, sizeof(kvbuf_t));
495	free(kv);
496}
497
498/* appends a kvbuf to an existing kvbuf */
499void
500kvbuf_append_kvbuf(kvbuf_t *kv, const kvbuf_t *kv2)
501{
502	uint32_t curr_count, new_count, temp;
503
504	if (kv == NULL) return;
505	if (kv2 == NULL) return;
506
507	curr_count = 0;
508	new_count = 0;
509
510	memcpy(&temp, kv->databuf, sizeof(uint32_t));
511	curr_count = ntohl(temp);
512
513	memcpy(&temp, kv2->databuf, sizeof(uint32_t));
514	new_count = ntohl(temp);
515
516	/* nothing to do */
517	if (new_count == 0) return;
518
519	/* add the dictionary count to the current dictionary counts */
520	curr_count += new_count;
521
522	temp = htonl(curr_count);
523	memcpy(kv->databuf, &temp, sizeof(uint32_t));
524
525	/* grow the current buffer so we can append the new buffer */
526	temp = kv2->datalen - sizeof(uint32_t);
527
528	kvbuf_grow(kv, temp);
529
530	memcpy(kv->databuf + kv->datalen, kv2->databuf + sizeof(uint32_t), temp);
531	kv->datalen += temp;
532}
533
534/* returns number of dictionaries */
535uint32_t
536kvbuf_reset(kvbuf_t *kv)
537{
538	uint32_t x;
539
540	if (kv == NULL) return 0;
541	if (kv->databuf == NULL) return 0;
542
543	kv->_dict = 0;
544	kv->_key = 0;
545	kv->_vlist = 0;
546	kv->_val = 0;
547
548	if (kv->datalen < sizeof(uint32_t)) return 0;
549
550	x = 0;
551	memcpy(&x, kv->databuf, sizeof(uint32_t));
552	return ntohl(x);
553}
554
555/* advance to next dictionary, returns key count */
556uint32_t
557kvbuf_next_dict(kvbuf_t *kv)
558{
559	uint32_t x, k, v, kcount, vcount, kl, vl;
560	char *p;
561
562	if (kv == NULL) return 0;
563	if (kv->databuf == NULL) return 0;
564
565	kv->_key = 0;
566	kv->_vlist = 0;
567	kv->_val = 0;
568
569	if (kv->_dict == 0)
570	{
571		/* first dict */
572		if (kv->datalen < sizeof(uint32_t)) return 0;
573		kv->_dict = sizeof(uint32_t);
574
575		if (kv->datalen < (kv->_dict + sizeof(uint32_t))) return 0;
576
577		p = kv->databuf + kv->_dict;
578		x = 0;
579		memcpy(&x, p, sizeof(uint32_t));
580		kcount = ntohl(x);
581
582		return kcount;
583	}
584
585	p = kv->databuf + kv->_dict;
586
587	x = 0;
588	memcpy(&x, p, sizeof(uint32_t));
589	p += sizeof(uint32_t);
590	kv->_dict += sizeof(uint32_t);
591	kcount = ntohl(x);
592
593	for (k = 0; k < kcount; k++)
594	{
595		x = 0;
596		memcpy(&x, p, sizeof(uint32_t));
597		p += sizeof(uint32_t);
598		kv->_dict += sizeof(uint32_t);
599		kl = ntohl(x);
600		p += kl;
601		kv->_dict += kl;
602
603		x = 0;
604		memcpy(&x, p, sizeof(uint32_t));
605		p += sizeof(uint32_t);
606		kv->_dict += sizeof(uint32_t);
607		vcount = ntohl(x);
608
609		for (v = 0; v < vcount; v++)
610		{
611			x = 0;
612			memcpy(&x, p, sizeof(uint32_t));
613			p += sizeof(uint32_t);
614			kv->_dict += sizeof(uint32_t);
615			vl = ntohl(x);
616			p += vl;
617			kv->_dict += vl;
618		}
619	}
620
621	if (kv->datalen < (kv->_dict + sizeof(uint32_t))) return 0;
622
623	p = kv->databuf + kv->_dict;
624	x = 0;
625	memcpy(&x, p, sizeof(uint32_t));
626	kcount = ntohl(x);
627
628	return kcount;
629}
630
631/* advance to next key, returns key and sets val_count */
632char *
633kvbuf_next_key(kvbuf_t *kv, uint32_t *val_count)
634{
635	uint32_t x, kl, v, vl, vc;
636	char *p, *out;
637
638	if (kv == NULL) return NULL;
639	if (val_count == NULL) return NULL;
640
641	*val_count = 0;
642
643	if (kv->databuf == NULL) return NULL;
644	if (kv->_dict == 0) return NULL;
645
646	kv->_vlist = 0;
647	kv->_val = 0;
648
649	if (kv->_key == 0)
650	{
651		/* first key */
652		if (kv->datalen < (kv->_dict +  sizeof(uint32_t))) return NULL;
653		kv->_key = kv->_dict + sizeof(uint32_t);
654	}
655	else
656	{
657		p = kv->databuf + kv->_key;
658
659		x = 0;
660		memcpy(&x, p, sizeof(uint32_t));
661		kl = ntohl(x);
662
663		if (kv->datalen < (kv->_key + sizeof(uint32_t) + kl)) return NULL;
664
665		p += (sizeof(uint32_t) + kl);
666		kv->_key += (sizeof(uint32_t) + kl);
667
668		/* skip over values */
669		if (kv->datalen < (kv->_key + sizeof(uint32_t))) return NULL;
670
671		x = 0;
672		memcpy(&x, p, sizeof(uint32_t));
673		vc = ntohl(x);
674
675		p += sizeof(uint32_t);
676		kv->_key += sizeof(uint32_t);
677
678		for (v = 0; v < vc; v++)
679		{
680			if (kv->datalen < (kv->_key + sizeof(uint32_t))) return NULL;
681
682			x = 0;
683			memcpy(&x, p, sizeof(uint32_t));
684			vl = ntohl(x);
685
686			if (kv->datalen < (kv->_key + kl)) return NULL;
687
688			p += (sizeof(uint32_t) + vl);
689			kv->_key += (sizeof(uint32_t) + vl);
690		}
691	}
692
693	if (kv->datalen < (kv->_key + sizeof(uint32_t))) return NULL;
694
695	p = kv->databuf + kv->_key;
696	x = 0;
697	memcpy(&x, p, sizeof(uint32_t));
698	kl = ntohl(x);
699
700	p += sizeof(uint32_t);
701	out = p;
702
703	kv->_vlist = kv->_key + sizeof(uint32_t) + kl;
704	if (kv->datalen < (kv->_vlist + sizeof(uint32_t)))
705	{
706		kv->_vlist = 0;
707		return NULL;
708	}
709
710	p = kv->databuf + kv->_vlist;
711	x = 0;
712	memcpy(&x, p, sizeof(uint32_t));
713	*val_count = ntohl(x);
714
715	return out;
716}
717
718char *
719kvbuf_next_val(kvbuf_t *kv)
720{
721	return kvbuf_next_val_len(kv, NULL);
722}
723
724char *
725kvbuf_next_val_len(kvbuf_t *kv, uint32_t *len)
726{
727	uint32_t x = 0;
728	uint32_t vltemp = 0;
729	char *p;
730
731	if (kv == NULL) return NULL;
732	if (kv->databuf == NULL) return NULL;
733	if (kv->_vlist == 0) return NULL;
734
735	if (kv->_val == 0)
736	{
737		/* first val */
738		if (kv->datalen < (kv->_vlist +  sizeof(uint32_t))) return NULL;
739		kv->_val = kv->_vlist + sizeof(uint32_t);
740
741		p = kv->databuf + kv->_val;
742
743		memcpy(&x, p, sizeof(uint32_t));
744		vltemp = ntohl(x);
745	}
746	else
747	{
748		p = kv->databuf + kv->_val;
749
750		memcpy(&x, p, sizeof(uint32_t));
751		vltemp = ntohl(x);
752
753		if (kv->datalen < (kv->_val + sizeof(uint32_t) + vltemp)) return NULL;
754
755		p += (sizeof(uint32_t) + vltemp);
756		kv->_val += (sizeof(uint32_t) + vltemp);
757	}
758
759	if (kv->datalen < (kv->_val + sizeof(uint32_t))) return NULL;
760
761	if (len != NULL) (*len) = vltemp;
762	p = kv->databuf + kv->_val + sizeof(uint32_t);
763	return p;
764}
765
766/*
767 * Builds a kvarray_t / kvdict_t structure on top of a kvbuf_t.
768 * It allocates the appropriate number of kvdict_t structures
769 * for the array, sets all the counters, and fills in pointers
770 * for keys and valuse.  The pointers are NOT to newly allocated
771 * strings: they just point into the kvbuf data buffer.
772 *
773 * To dispose of the kvarray_t and all of the associated
774 * memory AND to free the original kvbuf, clients only
775 * need to call kvarray_free().
776 */
777kvarray_t *
778kvbuf_decode(kvbuf_t *kv)
779{
780	kvarray_t *a;
781	uint32_t x, d, k, v;
782	char *p;
783
784	if (kv == NULL) return NULL;
785	if (kv->databuf == NULL) return NULL;
786
787	if (kv->datalen < sizeof(uint32_t)) return NULL;
788
789	p = kv->databuf;
790	kv->_size = kv->datalen;
791
792	/* array count */
793	x = 0;
794	memcpy(&x, p, sizeof(uint32_t));
795	p += sizeof(uint32_t);
796	kv->_size -= sizeof(uint32_t);
797	x = ntohl(x);
798
799	if (x == 0) return NULL;
800
801	a = (kvarray_t *)calloc(1, sizeof(kvarray_t));
802	if (a == NULL) return NULL;
803
804	a->count = x;
805	a->dict = (kvdict_t *)calloc(a->count, sizeof(kvdict_t));
806	if (a->dict == NULL)
807	{
808		free(a);
809		return NULL;
810	}
811
812	for (d = 0; d < a->count; d++)
813	{
814		if (kv->_size < sizeof(uint32_t))
815		{
816			kvarray_free(a);
817			return NULL;
818		}
819
820		/* key count */
821		x = 0;
822		memcpy(&x, p, sizeof(uint32_t));
823		p += sizeof(uint32_t);
824		kv->_size -= sizeof(uint32_t);
825		a->dict[d].kcount = ntohl(x);
826
827		if (a->dict[d].kcount > 0)
828		{
829			a->dict[d].key = (const char **)calloc(a->dict[d].kcount, sizeof(const char *));
830			if (a->dict[d].key == NULL)
831			{
832				kvarray_free(a);
833				return NULL;
834			}
835
836			a->dict[d].vcount = (uint32_t *)calloc(a->dict[d].kcount, sizeof(uint32_t));
837			if (a->dict[d].vcount == NULL)
838			{
839				kvarray_free(a);
840				return NULL;
841			}
842
843			a->dict[d].val = (const char ***)calloc(a->dict[d].kcount, sizeof(char **));
844			if (a->dict[d].val == NULL)
845			{
846				kvarray_free(a);
847				return NULL;
848			}
849		}
850
851		for (k = 0; k < a->dict[d].kcount; k++)
852		{
853			/* get key */
854			if (kv->_size < sizeof(uint32_t))
855			{
856				kvarray_free(a);
857				return NULL;
858			}
859
860			/* key length */
861			x = 0;
862			memcpy(&x, p, sizeof(uint32_t));
863			p += sizeof(uint32_t);
864			kv->_size -= sizeof(uint32_t);
865			x = ntohl(x);
866
867			if (kv->_size < x)
868			{
869				kvarray_free(a);
870				return NULL;
871			}
872
873			/* key data */
874			a->dict[d].key[k] = p;
875
876			p += x;
877			kv->_size -= x;
878
879			if (kv->_size < sizeof(uint32_t))
880			{
881				kvarray_free(a);
882				return NULL;
883			}
884
885			/* val count */
886			x = 0;
887			memcpy(&x, p, sizeof(uint32_t));
888			p += sizeof(uint32_t);
889			kv->_size -= sizeof(uint32_t);
890			a->dict[d].vcount[k] = ntohl(x);
891
892			if (a->dict[d].vcount[k] > 0)
893			{
894				/* N.B. we add a NULL pointer at the end of the list */
895				a->dict[d].val[k] = (const char **)calloc(a->dict[d].vcount[k] + 1, sizeof(const char *));
896				if (a->dict[d].val[k] == NULL)
897				{
898					kvarray_free(a);
899					return NULL;
900				}
901			}
902
903			for (v = 0; v < a->dict[d].vcount[k]; v++)
904			{
905				/* get val */
906				if (kv->_size < sizeof(uint32_t))
907				{
908					kvarray_free(a);
909					return NULL;
910				}
911
912				/* val length */
913				x = 0;
914				memcpy(&x, p, sizeof(uint32_t));
915				p += sizeof(uint32_t);
916				kv->_size -= sizeof(uint32_t);
917				x = ntohl(x);
918
919				if (kv->_size < x)
920				{
921					kvarray_free(a);
922					return NULL;
923				}
924
925				/* val data */
926				a->dict[d].val[k][v] = p;
927
928				p += x;
929				kv->_size -= x;
930			}
931		}
932	}
933
934	a->kv = kv;
935	return a;
936}
937
938void
939kvarray_free(kvarray_t *a)
940{
941	uint32_t d, k;
942
943	if (a == NULL) return;
944
945	for (d = 0; d < a->count; d++)
946	{
947		for (k = 0; k < a->dict[d].kcount; k++)
948		{
949			if (a->dict[d].val == NULL) continue;
950			if (a->dict[d].val[k] != NULL) free(a->dict[d].val[k]);
951		}
952
953		if (a->dict[d].key != NULL) free(a->dict[d].key);
954		if (a->dict[d].vcount != NULL) free(a->dict[d].vcount);
955		if (a->dict[d].val != NULL) free(a->dict[d].val);
956	}
957
958	a->count = 0;
959
960	if (a->dict != NULL) free(a->dict);
961	a->dict = NULL;
962
963	if (a->kv != NULL) kvbuf_free(a->kv);
964	a->kv = NULL;
965
966	free(a);
967}
968
969