1 /*
2 * key+value vector library
3 *
4 * Small and simple, but pretty helpful when parsing configurations
5 * from random formats into something a program can easily make sense
6 * of.
7 *
8 * The main type (struct kvvec *) should possibly be opaque since
9 * all callers should use the kvvec_foreach() variable to trudge
10 * around in the key/value vector.
11 */
12 #include <stdlib.h>
13 #include <string.h>
14 #include "kvvec.h"
15
kvvec_init(struct kvvec * kvv,int hint)16 struct kvvec *kvvec_init(struct kvvec *kvv, int hint)
17 {
18 if (!kvv)
19 return NULL;
20
21 kvv->kv_pairs = 0;
22 if (kvv->kv_alloc < hint && kvvec_resize(kvv, hint) < 0)
23 return NULL;
24
25 return kvv;
26 }
27
kvvec_create(int hint)28 struct kvvec *kvvec_create(int hint)
29 {
30 struct kvvec *kvv = calloc(1, sizeof(*kvv));
31 if (kvv && !kvvec_init(kvv, hint)) {
32 free(kvv);
33 return NULL;
34 }
35 return kvv;
36 }
37
kvvec_resize(struct kvvec * kvv,int hint)38 int kvvec_resize(struct kvvec *kvv, int hint)
39 {
40 struct key_value *kv;
41
42 if (!kvv)
43 return -1;
44
45 if (hint <= kvv->kv_alloc)
46 return 0;
47
48 kv = realloc(kvv->kv, sizeof(struct key_value) * hint);
49 if (!kv) {
50 if (kvv->kv)
51 free(kvv->kv);
52 return -1;
53 }
54
55 memset(&kv[kvv->kv_alloc], 0, (hint - kvv->kv_alloc) * sizeof(*kv));
56 kvv->kv = kv;
57 kvv->kv_alloc = hint;
58 return 0;
59 }
60
kvvec_grow(struct kvvec * kvv,int hint)61 int kvvec_grow(struct kvvec *kvv, int hint)
62 {
63 if (!kvv)
64 return -1;
65
66 /* grow reasonably when we don't have a hint */
67 if (!hint)
68 hint = (kvv->kv_alloc / 3) + 15;
69
70 return kvvec_resize(kvv, kvv->kv_alloc + hint);
71 }
72
kvvec_addkv_wlen(struct kvvec * kvv,const char * key,int keylen,const char * value,int valuelen)73 int kvvec_addkv_wlen(struct kvvec *kvv, const char *key, int keylen, const char *value, int valuelen)
74 {
75 struct key_value *kv;
76
77 if (!kvv || !key)
78 return -1;
79
80 if (kvv->kv_pairs >= kvv->kv_alloc - 1) {
81 if (kvvec_grow(kvv, 0))
82 return -1;
83 }
84
85 kv = &kvv->kv[kvv->kv_pairs++];
86
87 kv->key = (char *)key;
88 if (!keylen) {
89 kv->key_len = strlen(key);
90 } else {
91 kv->key_len = keylen;
92 }
93
94 kv->value = (char *)value;
95 if (value) {
96 if (!valuelen) {
97 kv->value_len = strlen(value);
98 } else {
99 kv->value_len = valuelen;
100 }
101 } else {
102 kv->value_len = 0;
103 }
104
105 kvv->kvv_sorted = 0;
106
107 return 0;
108 }
109
kv_compare(const void * a_,const void * b_)110 static int kv_compare(const void *a_, const void *b_)
111 {
112 const struct key_value *a = (const struct key_value *)a_;
113 const struct key_value *b = (const struct key_value *)b_;
114 int ret = 0;
115
116 ret = strcmp(a->key, b->key);
117 if (ret)
118 return ret;
119
120 if (!a->value && !b->value) {
121 return 0;
122 }
123 if (a->value && !b->value)
124 return -1;
125 if (!a->value && b->value)
126 return 1;
127
128 return strcmp(a->value, b->value);
129 }
130
kvvec_sort(struct kvvec * kvv)131 int kvvec_sort(struct kvvec *kvv)
132 {
133 qsort(kvv->kv, kvv->kv_pairs, sizeof(struct key_value), kv_compare);
134 kvv->kvv_sorted = 1;
135 return 0;
136 }
137
kvvec_foreach(struct kvvec * kvv,void * arg,int (* callback)(struct key_value *,void *))138 int kvvec_foreach(struct kvvec *kvv, void *arg, int (*callback)(struct key_value *,void *))
139 {
140 int i;
141
142 if (!kvv)
143 return 0;
144
145 for (i = 0; i < kvv->kv_pairs; i++) {
146 callback(&kvv->kv[i], arg);
147 }
148 return 0;
149 }
150
kvvec_free_kvpairs(struct kvvec * kvv,int flags)151 void kvvec_free_kvpairs(struct kvvec *kvv, int flags)
152 {
153 int i;
154
155 if (flags == KVVEC_FREE_ALL) {
156 for (i = 0; i < kvv->kv_pairs; i++) {
157 free(kvv->kv[i].key);
158 free(kvv->kv[i].value);
159 }
160 } else if (flags == KVVEC_FREE_KEYS) {
161 for (i = 0; i < kvv->kv_pairs; i++) {
162 free(kvv->kv[i].key);
163 }
164 } else if (flags == KVVEC_FREE_VALUES) {
165 for (i = 0; i < kvv->kv_pairs; i++) {
166 free(kvv->kv[i].value);
167 }
168 }
169
170 kvv->kv_pairs = 0;
171 }
172
173
kvvec_destroy(struct kvvec * kvv,int flags)174 int kvvec_destroy(struct kvvec *kvv, int flags)
175 {
176 kvvec_free_kvpairs(kvv, flags);
177 free(kvv->kv);
178 free(kvv);
179 return 0;
180 }
181
182 /*
183 * Caller can tell us to over-allocate the buffer if he/she wants
184 * to put extra stuff at the end of it.
185 */
kvvec2buf(struct kvvec * kvv,char kv_sep,char pair_sep,int overalloc)186 struct kvvec_buf *kvvec2buf(struct kvvec *kvv, char kv_sep, char pair_sep, int overalloc)
187 {
188 struct kvvec_buf *kvvb;
189 int i;
190 unsigned long len = 0;
191
192 if (!kvv)
193 return NULL;
194
195 kvvb = malloc(sizeof(struct kvvec_buf));
196 if (!kvvb)
197 return NULL;
198
199 /* overalloc + (kv_sep_size * kv_pairs) + (pair_sep_size * kv_pairs) */
200 kvvb->bufsize = overalloc + (kvv->kv_pairs * 2);
201 for (i = 0; i < kvv->kv_pairs; i++) {
202 struct key_value *kv = &kvv->kv[i];
203 kvvb->bufsize += kv->key_len + kv->value_len;
204 }
205
206 kvvb->buf = malloc(kvvb->bufsize);
207 if (!kvvb->buf) {
208 free(kvvb);
209 return NULL;
210 }
211
212 for (i = 0; i < kvv->kv_pairs; i++) {
213 struct key_value *kv = &kvv->kv[i];
214 memcpy(kvvb->buf + len, kv->key, kv->key_len);
215 len += kv->key_len;
216 kvvb->buf[len++] = kv_sep;
217 if (kv->value_len) {
218 memcpy(kvvb->buf + len, kv->value, kv->value_len);
219 len += kv->value_len;
220 }
221 kvvb->buf[len++] = pair_sep;
222 }
223 memset(kvvb->buf + len, 0, kvvb->bufsize - len);
224 kvvb->buflen = len;
225 return kvvb;
226 }
227
kvvec_capacity(struct kvvec * kvv)228 unsigned int kvvec_capacity(struct kvvec *kvv)
229 {
230 if (!kvv)
231 return 0;
232
233 return kvv->kv_alloc - kvv->kv_pairs;
234 }
235
236 /*
237 * Converts a buffer of random bytes to a key/value vector.
238 * This requires a fairly rigid format in the input data to be of
239 * much use, but it's nifty for ipc where only computers are
240 * involved, and it will parse the kvvec2buf() produce nicely.
241 */
buf2kvvec_prealloc(struct kvvec * kvv,char * str,unsigned int len,const char kvsep,const char pair_sep,int flags)242 int buf2kvvec_prealloc(struct kvvec *kvv, char *str,
243 unsigned int len, const char kvsep,
244 const char pair_sep, int flags)
245 {
246 unsigned int num_pairs = 0, i, offset = 0;
247
248 if (!str || !len || !kvv)
249 return -1;
250
251 /* first we count the number of key/value pairs */
252 while (offset < len) {
253 const char *ptr;
254
255 /* keys can't start with nul bytes */
256 if (*(str + offset)) {
257 num_pairs++;
258 }
259
260 ptr = memchr(str + offset, pair_sep, len - offset);
261 ptr++;
262 if (!ptr)
263 break;
264 offset += (unsigned long)ptr - ((unsigned long)str + offset);
265 }
266
267 if (!num_pairs) {
268 return 0;
269 }
270
271 /* make sure the key/value vector is large enough */
272 if (!(flags & KVVEC_APPEND)) {
273 kvvec_init(kvv, num_pairs);
274 } else if (kvvec_capacity(kvv) < num_pairs && kvvec_resize(kvv, num_pairs) < 0) {
275 return -1;
276 }
277
278 offset = 0;
279 for (i = 0; i < num_pairs; i++) {
280 struct key_value *kv;
281 char *key_end_ptr, *kv_end_ptr;
282
283 /* keys can't begin with nul bytes */
284 if (offset && str[offset] == '\0') {
285 return kvv->kv_pairs;
286 }
287
288 key_end_ptr = memchr(str + offset, kvsep, len - offset);
289 if (!key_end_ptr) {
290 break;
291 }
292 kv_end_ptr = memchr(key_end_ptr + 1, pair_sep, len - ((unsigned long)key_end_ptr - (unsigned long)str));
293 if (!kv_end_ptr) {
294 if (i != num_pairs - 1)
295 break;
296 /* last pair doesn't need a pair separator */
297 kv_end_ptr = str + len;
298 }
299
300 kv = &kvv->kv[kvv->kv_pairs++];
301 kv->key_len = (unsigned long)key_end_ptr - ((unsigned long)str + offset);
302 if (flags & KVVEC_COPY) {
303 kv->key = malloc(kv->key_len + 1);
304 memcpy(kv->key, str + offset, kv->key_len);
305 } else {
306 kv->key = str + offset;
307 }
308 kv->key[kv->key_len] = 0;
309
310 offset += kv->key_len + 1;
311
312 if (str[offset] == pair_sep) {
313 kv->value_len = 0;
314 if (flags & KVVEC_COPY) {
315 kv->value = strdup("");
316 } else {
317 kv->value = (char *)"";
318 }
319 } else {
320 kv->value_len = (unsigned long)kv_end_ptr - ((unsigned long)str + offset);
321 if (flags & KVVEC_COPY) {
322 kv->value = malloc(kv->value_len + 1);
323 memcpy(kv->value, str + offset, kv->value_len);
324 } else {
325 kv->value = str + offset;
326 }
327 kv->value[kv->value_len] = 0;
328 }
329
330 offset += kv->value_len + 1;
331 }
332
333 return i;
334 }
335
buf2kvvec(char * str,unsigned int len,const char kvsep,const char pair_sep,int flags)336 struct kvvec *buf2kvvec(char *str, unsigned int len, const char kvsep,
337 const char pair_sep, int flags)
338 {
339 struct kvvec *kvv;
340
341 kvv = kvvec_create(len / 20);
342 if (!kvv)
343 return NULL;
344
345 if (buf2kvvec_prealloc(kvv, str, len, kvsep, pair_sep, flags) >= 0)
346 return kvv;
347
348 free(kvv);
349 return NULL;
350 }
351