1 /*
2 ** OSSP val - Value Access
3 ** Copyright (c) 2002-2005 Ralf S. Engelschall <rse@engelschall.com>
4 ** Copyright (c) 2002-2005 The OSSP Project <http://www.ossp.org/>
5 ** Copyright (c) 2002-2005 Cable & Wireless <http://www.cw.com/>
6 **
7 ** This file is part of OSSP val, a value access library which
8 ** can be found at http://www.ossp.org/pkg/lib/val/.
9 **
10 ** Permission to use, copy, modify, and distribute this software for
11 ** any purpose with or without fee is hereby granted, provided that
12 ** the above copyright notice and this permission notice appear in all
13 ** copies.
14 **
15 ** THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
16 ** WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
17 ** MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18 ** IN NO EVENT SHALL THE AUTHORS AND COPYRIGHT HOLDERS AND THEIR
19 ** CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
20 ** SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
21 ** LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
22 ** USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23 ** ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
24 ** OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
25 ** OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 ** SUCH DAMAGE.
27 **
28 ** val.c: library implementation
29 */
30
31 /* include optional Autoconf header */
32 #ifdef HAVE_CONFIG_H
33 #include "config.h"
34 #endif
35
36 /* include system API headers */
37 #include <stdio.h> /* for "size_t" */
38 #include <stdlib.h>
39 #include <stdarg.h>
40 #include <string.h>
41
42 /* optional memory debugging support */
43 #if defined(HAVE_DMALLOC_H) && defined(WITH_DMALLOC)
44 #include "dmalloc.h"
45 #endif
46
47 /* include own API header */
48 #include "val.h"
49
50 /* boolean values */
51 #ifndef FALSE
52 #define FALSE (0)
53 #endif
54 #ifndef TRUE
55 #define TRUE (!FALSE)
56 #endif
57
58 /* unique library identifier */
59 const char val_id[] = "OSSP val";
60
61 /* support for OSSP ex based exception throwing */
62 #ifdef WITH_EX
63 #include "ex.h"
64 #define VAL_RC(rv) \
65 ( (rv) != VAL_OK && (ex_catching && !ex_shielding) \
66 ? (ex_throw(val_id, NULL, (rv)), (rv)) : (rv) )
67 #else
68 #define VAL_RC(rv) (rv)
69 #endif /* WITH_EX */
70
71 /*
72 ** ____ ____
73 ** ____ LINEAR HASHING SUB-LIBRARY ____
74 **
75 ** This part implements a Dynamic Hash Table, based on WITOLD LITWIN
76 ** and PER-AKE LARSON's ``Linear Hashing'' algorithm (1980/1988),
77 ** implemented on top of a two-level virtual array with separate
78 ** collision chains as the backend data structure. Some ideas were
79 ** taken over from MIKAEL PETTERSON's Linear Hashing enhancements
80 ** (1993). The code is derived from OSSP act. See there for details.
81 */
82
83 struct lh_st;
84 typedef struct lh_st lh_t;
85
86 typedef int (*lh_cb_t)(void *ctx, const void *keyptr, int keylen, const void *datptr, int datlen);
87
88 /* fixed size (number of pointers) of the directory and of each segment */
89 #define INITDIRSIZE 256 /* can be an arbitrary value */
90 #define SEGMENTSIZE 512 /* has to be a power of 2 for below arithmetic */
91
92 /* the borders for the hash table load */
93 #define MINLOADFCTR 1 /* should be between 0 and 1 */
94 #define MAXLOADFCTR 2 /* should be between 2 and 4 */
95
96 /* the per-element structure (keep as small as possible!) */
97 typedef struct element_st element_t;
98 struct element_st {
99 element_t *e_next; /* pointer to next element in collision chain */
100 unsigned long e_hash; /* cached hash value of element (rehashing optimization) */
101 void *e_keyptr; /* pointer to key (= also pointer to key+data memory chunk) */
102 void *e_datptr; /* pointer to data in key+data memory chunk */
103 void *e_endptr; /* pointer to end of key+data memory chunk */
104 };
105
106 /* the hash table segments */
107 typedef struct segment_st segment_t;
108 struct segment_st {
109 element_t *s_element[SEGMENTSIZE]; /* array of pointers to elements */
110 };
111
112 /* the top-level hash table structure */
113 struct lh_st {
114 unsigned int h_p; /* pointer to start of unsplit region */
115 unsigned int h_pmax; /* pointer to end of unsplit region */
116 int h_slack; /* grow/shrink indicator */
117 unsigned h_dirsize; /* current size of directory */
118 segment_t **h_dir; /* pointer to directory */
119 };
120
121 /* on-the-fly calculate index into directory and segment from virtual array index */
122 #define DIRINDEX(addr) (int)((addr) / SEGMENTSIZE)
123 #define SEGINDEX(addr) (int)((addr) % SEGMENTSIZE)
124
125 /* on-the-fly calculate lengths of key and data to reduce memory in element_t */
126 #define el_keylen(el) ((char *)((el)->e_endptr)-(char *)((el)->e_keyptr))
127 #define el_datlen(el) ((char *)((el)->e_keyptr)-(char *)((el)->e_datptr))
128
129 /*
130 * BJDDJ Hash Function (Bob Jenkins, Dr. Dobbs Journal):
131 * This is a very complex but also very good hash function, as proposed
132 * in the March'97 issue of Dr. Dobbs Journal (DDJ) by Bob Jenkins (see
133 * http://burtleburtle.net/bob/hash/doobs.html for online version). He
134 * showed that this hash function has both very good distribution and
135 * performance and our own hash function comparison confirmed this. The
136 * only difference to the original function of B.J. here is that our
137 * version doesn't provide the `level' (= previous hash) argument for
138 * consistency reasons with the other hash functions (i.e. same function
139 * signature). It can be definetely recommended as a good general
140 * purpose hash function.
141 */
142 static long
lh_hash(register const unsigned char * k,register size_t length)143 lh_hash(
144 register const unsigned char *k,
145 register size_t length)
146 {
147 register long a,b,c,len;
148
149 /* some abbreviations */
150 #define ub4 long
151 #define mix(a,b,c) { \
152 a -= b; a -= c; a ^= (c>>13); \
153 b -= c; b -= a; b ^= (a<< 8); \
154 c -= a; c -= b; c ^= (b>>13); \
155 a -= b; a -= c; a ^= (c>>12); \
156 b -= c; b -= a; b ^= (a<<16); \
157 c -= a; c -= b; c ^= (b>> 5); \
158 a -= b; a -= c; a ^= (c>> 3); \
159 b -= c; b -= a; b ^= (a<<10); \
160 c -= a; c -= b; c ^= (b>>15); \
161 }
162
163 /* setup the internal state */
164 len = length;
165 a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */
166 c = 0;
167
168 /* handle most of the key */
169 while (len >= 12) {
170 a += (k[0] +((ub4)k[1]<<8) +((ub4)k[ 2]<<16) +((ub4)k[ 3]<<24));
171 b += (k[4] +((ub4)k[5]<<8) +((ub4)k[ 6]<<16) +((ub4)k[ 7]<<24));
172 c += (k[8] +((ub4)k[9]<<8) +((ub4)k[10]<<16) +((ub4)k[11]<<24));
173 mix(a,b,c);
174 k += 12; len -= 12;
175 }
176
177 /* handle the last 11 bytes */
178 c += length;
179 switch(len) {
180 /* all the case statements fall through */
181 case 11: c+=((ub4)k[10]<<24);
182 case 10: c+=((ub4)k[ 9]<<16);
183 case 9 : c+=((ub4)k[ 8]<< 8);
184 /* the first byte of c is reserved for the length */
185 case 8 : b+=((ub4)k[ 7]<<24);
186 case 7 : b+=((ub4)k[ 6]<<16);
187 case 6 : b+=((ub4)k[ 5]<< 8);
188 case 5 : b+=k[4];
189 case 4 : a+=((ub4)k[ 3]<<24);
190 case 3 : a+=((ub4)k[ 2]<<16);
191 case 2 : a+=((ub4)k[ 1]<< 8);
192 case 1 : a+=k[0];
193 /* case 0: nothing left to add */
194 }
195 mix(a,b,c);
196
197 #undef ub4
198 #undef mix
199
200 /* report the result */
201 return c;
202 }
203
204 /* create the hash table structure */
lh_create(void)205 static lh_t *lh_create(void)
206 {
207 lh_t *h;
208
209 /* allocate hash structure */
210 if ((h = (lh_t *)malloc(sizeof(lh_t))) == NULL)
211 return NULL;
212
213 /* allocate and clear hash table directory */
214 h->h_dirsize = INITDIRSIZE;
215 if ((h->h_dir = (segment_t **)malloc(h->h_dirsize * sizeof(segment_t *))) == NULL) {
216 free(h);
217 return NULL;
218 }
219 memset(h->h_dir, 0, h->h_dirsize * sizeof(segment_t *));
220
221 /* allocate and clear first segment of hash table array */
222 if ((h->h_dir[0] = (segment_t *)malloc(sizeof(segment_t))) == NULL) {
223 free(h->h_dir);
224 free(h);
225 return NULL;
226 }
227 memset(h->h_dir[0], 0, sizeof(segment_t));
228
229 /* initialize hash table control attributes */
230 h->h_p = 0;
231 h->h_pmax = SEGMENTSIZE;
232 h->h_slack = SEGMENTSIZE * MAXLOADFCTR;
233
234 return h;
235 }
236
237 /* expand the hash table */
lh_expand(lh_t * h)238 static void lh_expand(lh_t *h)
239 {
240 unsigned int pmax0;
241 unsigned int newaddr;
242 segment_t *seg;
243 element_t **pelold;
244 element_t *el, *headofold, *headofnew, *next;
245 unsigned int n;
246
247 /* calculate next new address */
248 pmax0 = h->h_pmax;
249 newaddr = pmax0 + h->h_p;
250
251 /* have to enlarge directory? */
252 if (h->h_dirsize <= DIRINDEX(newaddr)) {
253 n = h->h_dirsize * sizeof(segment_t *);
254 h->h_dirsize *= 2;
255 if ((h->h_dir = (segment_t **)realloc(
256 h->h_dir, h->h_dirsize*sizeof(segment_t *))) == NULL)
257 return;
258 memset((char *)h->h_dir+n, 0, n);
259 }
260
261 /* have to create a new table segment? */
262 if (SEGINDEX(newaddr) == 0) {
263 if ((seg = (segment_t *)malloc(sizeof(segment_t))) == NULL)
264 return;
265 memset(seg, 0, sizeof(segment_t));
266 h->h_dir[DIRINDEX(newaddr)] = seg;
267 }
268
269 /* locate P-element */
270 pelold = &h->h_dir[DIRINDEX(h->h_p)]->s_element[SEGINDEX(h->h_p)];
271
272 /* adjust the state variables */
273 if (++(h->h_p) >= h->h_pmax) {
274 h->h_pmax = (h->h_pmax << 1); /* == h->h_pmax * 2 */
275 h->h_p = 0;
276 }
277 h->h_slack += MAXLOADFCTR;
278
279 /* relocate and split between P-element new element */
280 headofold = NULL;
281 headofnew = NULL;
282 for (el = *pelold; el != NULL; el = next) {
283 next = el->e_next;
284 if (el->e_hash & pmax0) {
285 el->e_next = headofnew;
286 headofnew = el;
287 } else {
288 el->e_next = headofold;
289 headofold = el;
290 }
291 }
292 *pelold = headofold;
293 h->h_dir[DIRINDEX(newaddr)]->s_element[SEGINDEX(newaddr)] = headofnew;
294
295 return;
296 }
297
298 /* shrink hash table */
lh_shrink(lh_t * h)299 static void lh_shrink(lh_t *h)
300 {
301 segment_t *lastseg;
302 element_t **pel;
303 unsigned int oldlast;
304 unsigned int dirsize;
305 void *dir;
306
307 /* calculate old last element */
308 oldlast = h->h_p + h->h_pmax - 1;
309
310 /* we cannot shrink below one segment */
311 if (oldlast == 0)
312 return;
313
314 /* adjust the state variables */
315 if (h->h_p == 0) {
316 h->h_pmax = (h->h_pmax >> 1); /* == h->h_pmax / 2 */;
317 h->h_p = h->h_pmax - 1;
318 } else
319 h->h_p--;
320 h->h_slack -= MAXLOADFCTR;
321
322 /* relocate the lost old last element to the end of the P-element */
323 pel = &h->h_dir[DIRINDEX(h->h_p)]->s_element[SEGINDEX(h->h_p)];
324 while (*pel != NULL)
325 pel = &((*pel)->e_next);
326 lastseg = h->h_dir[DIRINDEX(oldlast)];
327 *pel = lastseg->s_element[SEGINDEX(oldlast)];
328 lastseg->s_element[SEGINDEX(oldlast)] = NULL;
329
330 /* if possible, deallocate the last segment */
331 if (SEGINDEX(oldlast) == 0) {
332 h->h_dir[DIRINDEX(oldlast)] = NULL;
333 free(lastseg);
334 }
335
336 /* if possible, deallocate the end of the directory */
337 if (h->h_dirsize > INITDIRSIZE && DIRINDEX(oldlast) < h->h_dirsize/2) {
338 dirsize = (h->h_dirsize >> 1); /* == h->h_dirsize / 2 */
339 if ((dir = (segment_t **)realloc(
340 h->h_dir, dirsize*sizeof(segment_t *))) != NULL) {
341 h->h_dirsize = dirsize;
342 h->h_dir = dir;
343 }
344 }
345 return;
346 }
347
348 /* insert element into hash table */
lh_insert(lh_t * h,const void * keyptr,int keylen,const void * datptr,int datlen,int override)349 static int lh_insert(lh_t *h, const void *keyptr, int keylen, const void *datptr, int datlen, int override)
350 {
351 unsigned int hash, addr;
352 element_t *el, **pel;
353 int bFound;
354 void *vp;
355
356 /* argument consistency check */
357 if (h == NULL || keyptr == NULL || keylen <= 0)
358 return FALSE;
359
360 /* calculate hash address */
361 hash = lh_hash(keyptr, keylen);
362 addr = hash % h->h_pmax; /* unsplit region */
363 if (addr < h->h_p)
364 addr = hash % (h->h_pmax << 1); /* split region */
365
366 /* locate hash element's collision list */
367 pel = &h->h_dir[DIRINDEX(addr)]->s_element[SEGINDEX(addr)];
368
369 /* check whether element is already in the hash table */
370 bFound = FALSE;
371 for (el = *pel; el != NULL; el = el->e_next) {
372 if ( el->e_hash == hash
373 && el_keylen(el) == keylen
374 && memcmp(el->e_keyptr, keyptr, el_keylen(el)) == 0) {
375 bFound = TRUE;
376 break;
377 }
378 }
379
380 /* only override on request */
381 if (bFound && !override)
382 return FALSE;
383
384 /* create a duplicate of key and data */
385 if ((vp = malloc(keylen+datlen)) == NULL)
386 return FALSE;
387 memmove(vp, datptr, datlen);
388 memmove(((char *)vp)+datlen, keyptr, keylen);
389 datptr = vp;
390 keyptr = ((char *)vp)+datlen;
391
392 if (bFound) {
393 /* reuse existing element by freeing old contents */
394 if (el->e_datptr != NULL)
395 free(el->e_datptr);
396 }
397 else {
398 /* allocate new element and chain into list */
399 if ((el = (element_t *)malloc(sizeof(element_t))) == 0) {
400 free(vp);
401 return FALSE;
402 }
403 while (*pel != NULL)
404 pel = &((*pel)->e_next);
405 el->e_next = *pel;
406 *pel = el;
407 }
408
409 /* insert contents into element structure */
410 el->e_keyptr = (void *)keyptr;
411 el->e_datptr = (void *)datptr;
412 el->e_endptr = (char *)keyptr+keylen;
413 el->e_hash = hash;
414
415 /* do we need to expand the table now? */
416 if (--(h->h_slack) < 0)
417 lh_expand(h);
418
419 return TRUE;
420 }
421
422 /* lookup an element in hash table */
lh_lookup(lh_t * h,const void * keyptr,int keylen,void ** datptr,int * datlen)423 static int lh_lookup(lh_t *h, const void *keyptr, int keylen, void **datptr, int *datlen)
424 {
425 unsigned int hash, addr;
426 element_t *el, **pel;
427
428 /* argument consistency check */
429 if (h == NULL || keyptr == NULL || keylen <= 0)
430 return FALSE;
431
432 /* calculate hash address */
433 hash = lh_hash(keyptr, keylen);
434 addr = hash % h->h_pmax; /* unsplit region */
435 if (addr < h->h_p)
436 addr = hash % (h->h_pmax << 1); /* split region */
437
438 /* locate hash element collision list */
439 pel = &h->h_dir[DIRINDEX(addr)]->s_element[SEGINDEX(addr)];
440
441 /* search for element in collision list */
442 for (el = *pel; el != NULL; el = el->e_next) {
443 if ( el->e_hash == hash
444 && el_keylen(el) == keylen
445 && memcmp(el->e_keyptr, keyptr, el_keylen(el)) == 0) {
446 /* provide results */
447 if (datptr != NULL)
448 *datptr = el->e_datptr;
449 if (datlen != NULL)
450 *datlen = el_datlen(el);
451 return TRUE;
452 }
453 }
454 return FALSE;
455 }
456
457 /* delete an element in hash table */
lh_delete(lh_t * h,const void * keyptr,int keylen)458 static int lh_delete(lh_t *h, const void *keyptr, int keylen)
459 {
460 unsigned int hash, addr;
461 element_t *el, *lel, **pel;
462 int rv;
463
464 /* argument consistency check */
465 if (h == NULL || keyptr == NULL || keylen <= 0)
466 return FALSE;
467
468 /* calculate hash address */
469 hash = lh_hash(keyptr, keylen);
470 addr = hash % h->h_pmax; /* unsplit region */
471 if (addr < h->h_p)
472 addr = hash % (h->h_pmax << 1); /* split region */
473
474 /* locate hash element collision chain */
475 pel = &h->h_dir[DIRINDEX(addr)]->s_element[SEGINDEX(addr)];
476
477 /* search for element in collision chain */
478 rv = FALSE;
479 for (lel = NULL, el = *pel; el != NULL; lel = el, el = el->e_next) {
480 if ( el->e_hash == hash
481 && el_keylen(el) == keylen
482 && memcmp(el->e_keyptr, keyptr, el_keylen(el)) == 0) {
483 /* free key+data memory chunk */
484 if (el->e_datptr != NULL)
485 free(el->e_datptr);
486 /* remove element from collision chain */
487 if (lel == NULL)
488 *pel = el->e_next;
489 else
490 lel->e_next = el->e_next;
491 /* deallocate element structure */
492 free(el);
493 rv = TRUE;
494 break;
495 }
496 }
497
498 /* do we need to shrink the table now? */
499 if (++(h->h_slack) > ((h->h_pmax + h->h_p) * (MAXLOADFCTR-MINLOADFCTR)))
500 lh_shrink(h);
501
502 return rv;
503 }
504
505 /* apply a callback for all elements in the hash table */
lh_apply(lh_t * h,lh_cb_t cb,void * ctx)506 static int lh_apply(lh_t *h, lh_cb_t cb, void *ctx)
507 {
508 element_t *el;
509 unsigned int i, j;
510
511 /* argument consistency check */
512 if (h == NULL || cb == NULL)
513 return FALSE;
514
515 /* interate over all segment's entries */
516 for (i = 0; i < h->h_dirsize; i++) {
517 if (h->h_dir[i] == NULL)
518 continue;
519 /* interate over all collision chains */
520 for (j = 0; j < SEGMENTSIZE; j++) {
521 if (h->h_dir[i]->s_element[j] == NULL)
522 continue;
523 /* interate over all elements in collision chain */
524 el = h->h_dir[i]->s_element[j];
525 for (; el != NULL; el = el->e_next) {
526 if (!cb(ctx, el->e_keyptr, el_keylen(el), el->e_datptr, el_datlen(el)))
527 return FALSE;
528 }
529 }
530 }
531 return TRUE;
532 }
533
534 /* destroy the whole hash table */
lh_destroy(lh_t * h)535 static int lh_destroy(lh_t *h)
536 {
537 element_t *el, **pel, *el_next;
538 unsigned int i, j;
539
540 /* argument consistency check */
541 if (h == NULL)
542 return FALSE;
543
544 /* deallocate all segment's entries */
545 for (i = 0; i < h->h_dirsize; i++) {
546 if (h->h_dir[i] == NULL)
547 continue;
548 /* deallocate all collision chains */
549 for (j = 0; j < SEGMENTSIZE; j++) {
550 if (h->h_dir[i]->s_element[j] == NULL)
551 continue;
552 /* deallocate all elements in collision chain */
553 pel = &h->h_dir[i]->s_element[j];
554 for (el = *pel; el != NULL; ) {
555 /* deallocate key+data memory chunk */
556 if (el->e_datptr != NULL)
557 free(el->e_datptr);
558 el_next = el->e_next;
559 free(el);
560 el = el_next;
561 }
562 }
563 free(h->h_dir[i]);
564 }
565
566 /* deallocate hash table directory */
567 free(h->h_dir);
568
569 /* deallocate hash table top-level structure */
570 free(h);
571
572 return TRUE;
573 }
574
575 /*
576 ** ____ ____
577 ** ____ VALUE LIBRARY ____
578 **
579 ** This part implements the actual Value library. Fortunately this
580 ** is now easy because it internally is just based on the above
581 ** full-featured linear hashing library.
582 */
583
584 /*
585 * usually val_object_t.data is a pointer val_object_t.data.p,
586 * but VAL_INLINE signals val_object_t.data is actual data
587 * val_object_t.data.[csilfd].
588 */
589 enum {
590 VAL_INLINE = 1<<31
591 };
592
593 /* the internal representation of a value object */
594 typedef struct {
595 int type;
596 union {
597 val_t *v;
598 void *p;
599 char c;
600 short s;
601 int i;
602 long l;
603 float f;
604 double d;
605 } data;
606 char *desc;
607 } val_object_t;
608
609 /* the val_t internally is just a hash table */
610 struct val_s {
611 lh_t *lh;
612 };
613
614 /* determine address of an object's storage */
val_storage(val_object_t * obj)615 static void *val_storage(val_object_t *obj)
616 {
617 void *storage;
618
619 /* argument consistency check */
620 if (obj == NULL)
621 return NULL;
622
623 /* address determination */
624 if (obj->type & VAL_INLINE) {
625 switch (obj->type & ~VAL_INLINE) {
626 case VAL_TYPE_VAL: storage = &obj->data.v; break;
627 case VAL_TYPE_PTR: storage = &obj->data.p; break;
628 case VAL_TYPE_CHAR: storage = &obj->data.c; break;
629 case VAL_TYPE_SHORT: storage = &obj->data.s; break;
630 case VAL_TYPE_INT: storage = &obj->data.i; break;
631 case VAL_TYPE_LONG: storage = &obj->data.l; break;
632 case VAL_TYPE_FLOAT: storage = &obj->data.f; break;
633 case VAL_TYPE_DOUBLE: storage = &obj->data.d; break;
634 default: storage = NULL; break; /* cannot happen */
635 }
636 }
637 else
638 storage = obj->data.p;
639
640 return storage;
641 }
642
643 /* create object */
val_create(val_t ** pval)644 val_rc_t val_create(val_t **pval)
645 {
646 val_t *val;
647
648 /* argument consistency check */
649 if (pval == NULL)
650 return VAL_RC(VAL_ERR_ARG);
651
652 /* create top-level structure */
653 if ((val = (val_t *)malloc(sizeof(val_t))) == NULL)
654 return VAL_RC(VAL_ERR_SYS);
655
656 /* create hash table */
657 if ((val->lh = lh_create()) == NULL) {
658 free(val);
659 return VAL_RC(VAL_ERR_SYS);
660 }
661
662 /* pass result to caller */
663 *pval = val;
664
665 return VAL_OK;
666 }
667
668 /* internal lh_apply() callback for use with val_destroy() */
val_destroy_cb(void * _ctx,const void * keyptr,int keylen,const void * datptr,int datlen)669 static int val_destroy_cb(void *_ctx,
670 const void *keyptr, int keylen,
671 const void *datptr, int datlen)
672 {
673 val_object_t *obj;
674
675 /* free description string */
676 if ((obj = (val_object_t *)datptr) != NULL)
677 if (obj->desc != NULL)
678 free(obj->desc);
679
680 return TRUE;
681 }
682
683 /* destroy object */
val_destroy(val_t * val)684 val_rc_t val_destroy(val_t *val)
685 {
686 /* argument consistency check */
687 if (val == NULL)
688 return VAL_RC(VAL_ERR_ARG);
689
690 /* destroy all hash table elements */
691 lh_apply(val->lh, val_destroy_cb, NULL);
692
693 /* destroy hash table */
694 if (!lh_destroy(val->lh))
695 return VAL_RC(VAL_ERR_SYS);
696
697 /* destroy top-level structure */
698 free(val);
699
700 return VAL_OK;
701 }
702
703 /* register a value */
val_reg(val_t * val,const char * name,int type,const char * desc,void * storage)704 val_rc_t val_reg(val_t *val, const char *name, int type, const char *desc, void *storage)
705 {
706 val_object_t *obj;
707 val_object_t newobj;
708 const char *cp;
709 val_t *child;
710
711 /* argument consistency check */
712 if (val == NULL || name == NULL || type == 0)
713 return VAL_RC(VAL_ERR_ARG);
714
715 /* recursive step-down on structured name */
716 if ((cp = strchr(name, '.')) != NULL) {
717 if (!lh_lookup(val->lh, name, cp-name, (void **)(void *)&obj, NULL))
718 return VAL_RC(VAL_ERR_ARG);
719 if (!(obj->type & VAL_TYPE_VAL))
720 return VAL_RC(VAL_ERR_USE);
721 child = *(val_t **)(val_storage(obj));
722 return val_reg(child, cp+1, type, desc, storage);
723 }
724
725 /* create a new value object */
726 if (desc != NULL)
727 newobj.desc = strdup(desc);
728 else
729 newobj.desc = NULL;
730 if (storage == NULL) {
731 newobj.type = (type | VAL_INLINE);
732 newobj.data.l = 0;
733 }
734 else {
735 newobj.type = (type & ~VAL_INLINE);
736 newobj.data.p = storage;
737 }
738
739 /* insert value into hash table */
740 if (!lh_insert(val->lh, name, strlen(name), &newobj, sizeof(newobj), 1))
741 return VAL_RC(VAL_ERR_HSH);
742
743 return VAL_OK;
744 }
745
val_unreg(val_t * val,const char * name)746 val_rc_t val_unreg(val_t *val, const char *name)
747 {
748 val_object_t *obj;
749 const char *cp;
750 val_t *child;
751
752 /* argument consistency check */
753 if (val == NULL || name == NULL)
754 return VAL_RC(VAL_ERR_ARG);
755
756 /* recursive step-down on structured name */
757 if ((cp = strchr(name, '.')) != NULL) {
758 if (!lh_lookup(val->lh, name, cp-name, (void **)(void *)&obj, NULL))
759 return VAL_RC(VAL_ERR_ARG);
760 if (!(obj->type & VAL_TYPE_VAL))
761 return VAL_RC(VAL_ERR_USE);
762 child = *(val_t **)(val_storage(obj));
763 return val_unreg(child, cp+1);
764 }
765
766 /* try to lookup object in hash table */
767 if (!lh_lookup(val->lh, name, strlen(name), (void **)(void *)&obj, NULL))
768 return VAL_RC(VAL_ERR_ARG);
769
770 /* destroy value object */
771 if (obj->desc != NULL)
772 free(obj->desc);
773
774 /* delete value from hash table */
775 if (!lh_delete(val->lh, name, strlen(name)))
776 return VAL_RC(VAL_ERR_HSH);
777
778 return VAL_OK;
779 }
780
781 /* query information about a value */
val_query(val_t * val,const char * name,int * ptype,char ** pdesc,void ** pstorage)782 val_rc_t val_query(val_t *val, const char *name,
783 int *ptype, char **pdesc, void **pstorage)
784 {
785 char *cp;
786 val_object_t *obj;
787 val_t *child;
788
789 /* argument consistency check */
790 if (val == NULL || name == NULL)
791 return VAL_RC(VAL_ERR_ARG);
792
793 /* recursive step-down on structured name */
794 if ((cp = strchr(name, '.')) != NULL) {
795 if (!lh_lookup(val->lh, name, cp-name, (void **)(void *)&obj, NULL))
796 return VAL_RC(VAL_ERR_ARG);
797 if (!(obj->type & VAL_TYPE_VAL))
798 return VAL_RC(VAL_ERR_USE);
799 child = *(val_t **)(val_storage(obj));
800 return val_query(child, cp+1, ptype, pdesc, pstorage);
801 }
802
803 /* try to lookup object in hash table */
804 if (!lh_lookup(val->lh, name, strlen(name), (void **)(void *)&obj, NULL))
805 return VAL_RC(VAL_ERR_ARG);
806
807 /* pass queried information to caller */
808 if (ptype != NULL)
809 *ptype = (obj->type & ~VAL_INLINE);
810 if (pdesc != NULL)
811 *pdesc = obj->desc;
812 if (pstorage != NULL)
813 *pstorage = val_storage(obj);
814
815 return VAL_OK;
816 }
817
818 /* set a value (va_list variant) */
val_vset(val_t * val,const char * name,va_list ap)819 val_rc_t val_vset(val_t *val, const char *name, va_list ap)
820 {
821 val_object_t *obj;
822 void *storage;
823 const char *cp;
824 val_t *child;
825
826 /* argument consistency check */
827 if (val == NULL || name == NULL)
828 return VAL_RC(VAL_ERR_ARG);
829
830 /* recursive step-down on structured name */
831 if ((cp = strchr(name, '.')) != NULL) {
832 if (!lh_lookup(val->lh, name, cp-name, (void **)(void *)&obj, NULL))
833 return VAL_RC(VAL_ERR_ARG);
834 if (!(obj->type & VAL_TYPE_VAL))
835 return VAL_RC(VAL_ERR_USE);
836 child = *(val_t **)(val_storage(obj));
837 return val_vset(child, cp+1, ap);
838 }
839
840 /* try to lookup object in hash table */
841 if (!lh_lookup(val->lh, name, strlen(name), (void **)(void *)&obj, NULL))
842 return VAL_RC(VAL_ERR_ARG);
843
844 /* determine value storage */
845 if ((storage = val_storage(obj)) == NULL)
846 return VAL_RC(VAL_ERR_INT);
847
848 /* copy value from variable argument into storage location */
849 switch (obj->type & ~VAL_INLINE) {
850 case VAL_TYPE_VAL: *(val_t **)storage = (val_t *)va_arg(ap, void *); break;
851 case VAL_TYPE_PTR: *(char **)storage = (char *)va_arg(ap, void *); break;
852 case VAL_TYPE_CHAR: *(char *)storage = (char )va_arg(ap, int ); break;
853 case VAL_TYPE_SHORT: *(short *)storage = (short )va_arg(ap, int ); break;
854 case VAL_TYPE_INT: *(int *)storage = (int )va_arg(ap, int ); break;
855 case VAL_TYPE_LONG: *(long *)storage = (long )va_arg(ap, long ); break;
856 case VAL_TYPE_FLOAT: *(float *)storage = (float )va_arg(ap, double); break;
857 case VAL_TYPE_DOUBLE: *(double *)storage = (double )va_arg(ap, double); break;
858 default: break; /* cannot happen */
859 }
860
861 return VAL_OK;
862 }
863
864 /* set a value */
val_set(val_t * val,const char * name,...)865 val_rc_t val_set(val_t *val, const char *name, ...)
866 {
867 val_rc_t rc;
868 va_list ap;
869
870 /* argument consistency check */
871 if (val == NULL || name == NULL)
872 return VAL_RC(VAL_ERR_ARG);
873
874 /* just pass-through to va_list variant */
875 va_start(ap, name);
876 rc = val_vset(val, name, ap);
877 va_end(ap);
878
879 return VAL_RC(rc);
880 }
881
882 /* get a value (va_list variant) */
val_vget(val_t * val,const char * name,va_list ap)883 val_rc_t val_vget(val_t *val, const char *name, va_list ap)
884 {
885 val_object_t *obj;
886 void *storage;
887 const char *cp;
888 val_t *child;
889
890 /* argument consistency check */
891 if (val == NULL || name == NULL)
892 return VAL_RC(VAL_ERR_ARG);
893
894 /* recursive step-down on structured name */
895 if ((cp = strchr(name, '.')) != NULL) {
896 if (!lh_lookup(val->lh, name, cp-name, (void **)(void *)&obj, NULL))
897 return VAL_RC(VAL_ERR_ARG);
898 if (!(obj->type & VAL_TYPE_VAL))
899 return VAL_RC(VAL_ERR_USE);
900 child = *(val_t **)(val_storage(obj));
901 return val_vget(child, cp+1, ap);
902 }
903
904 /* try to lookup object in hash table */
905 if (!lh_lookup(val->lh, name, strlen(name), (void **)(void *)&obj, NULL))
906 return VAL_RC(VAL_ERR_ARG);
907
908 /* determine value storage */
909 if ((storage = val_storage(obj)) == NULL)
910 return VAL_RC(VAL_ERR_INT);
911
912 /* copy value from storage location into variable argument pointer location */
913 switch (obj->type & ~VAL_INLINE) {
914 case VAL_TYPE_VAL: *((val_t **)va_arg(ap, void *)) = *(val_t **)storage; break;
915 case VAL_TYPE_PTR: *((char **)va_arg(ap, void *)) = *(char **)storage; break;
916 case VAL_TYPE_CHAR: *((char *)va_arg(ap, int *)) = *(char *)storage; break;
917 case VAL_TYPE_SHORT: *((short *)va_arg(ap, int *)) = *(short *)storage; break;
918 case VAL_TYPE_INT: *((int *)va_arg(ap, int *)) = *(int *)storage; break;
919 case VAL_TYPE_LONG: *((long *)va_arg(ap, long *)) = *(long *)storage; break;
920 case VAL_TYPE_FLOAT: *((float *)va_arg(ap, double *)) = *(float *)storage; break;
921 case VAL_TYPE_DOUBLE: *((double *)va_arg(ap, double *)) = *(double *)storage; break;
922 default: break; /* cannot happen */
923 }
924
925 return VAL_OK;
926 }
927
928 /* get a value */
val_get(val_t * val,const char * name,...)929 val_rc_t val_get(val_t *val, const char *name, ...)
930 {
931 val_rc_t rc;
932 va_list ap;
933
934 /* argument consistency check */
935 if (val == NULL || name == NULL)
936 return VAL_RC(VAL_ERR_ARG);
937
938 /* just pass-through to va_list variant */
939 va_start(ap, name);
940 rc = val_vget(val, name, ap);
941 va_end(ap);
942
943 return VAL_RC(rc);
944 }
945
946 /* internal lh_apply() recursion callback context structure */
947 typedef struct {
948 val_t *val;
949 char *name;
950 int prefixlen;
951 int depth;
952 val_cb_t cb;
953 void *ctx;
954 val_rc_t rc;
955 } val_apply_ctx_t;
956
957 /* forward declaration */
958 static val_rc_t val_apply_internal(val_t *, const char *, int, int, val_cb_t, void *);
959
960 /* internal lh_apply() recursion callback for use with val_apply() */
961 static int (val_apply_cb)(void *_ctx, const void *keyptr, int keylen, const void *datptr, int datlen)
962 {
963 val_apply_ctx_t *ctx = (val_apply_ctx_t *)_ctx;
964 char name[VAL_MAXNAME+1];
965 int prefixlen;
966
967 /* on-the-fly create NUL-terminated concatenated name string */
968 if ((strlen(ctx->name) + 1 + keylen) > VAL_MAXNAME) {
969 ctx->rc = VAL_ERR_MEM;
970 return FALSE;
971 }
972 if (strlen(ctx->name) > 0) {
973 strcpy(name, ctx->name);
974 strcat(name, ".");
975 prefixlen = ctx->prefixlen + 1;
976 }
977 else {
978 *name = '\0';
979 prefixlen = ctx->prefixlen;
980 }
981 strncat(name, (char *)keyptr, keylen);
982
983 /* recursive step-down */
984 if ((ctx->rc = val_apply_internal(ctx->val, name, prefixlen,
985 ctx->depth, ctx->cb, ctx->ctx)) != VAL_OK)
986 return FALSE;
987
988 return TRUE;
989 }
990
991 /* internal API-increased variant of val_apply() */
val_apply_internal(val_t * val,const char * name,int prefixlen,int depth,val_cb_t cb,void * ctx)992 static val_rc_t val_apply_internal(val_t *val, const char *name, int prefixlen,
993 int depth, val_cb_t cb, void *ctx)
994 {
995 val_object_t *obj;
996 val_t *child;
997 char *cp;
998 val_rc_t rc;
999 val_apply_ctx_t val_ctx;
1000
1001 if (name[prefixlen] == '\0') {
1002 /* CASE 1: apply to all elements
1003 prefix="foo.bar.", remainder="" */
1004 val_ctx.val = val;
1005 val_ctx.name = (char *)name;
1006 val_ctx.prefixlen = prefixlen;
1007 val_ctx.depth = depth;
1008 val_ctx.cb = cb;
1009 val_ctx.ctx = ctx;
1010 val_ctx.rc = VAL_OK;
1011 if (!lh_apply(val->lh, val_apply_cb, &val_ctx))
1012 return VAL_RC(VAL_ERR_SYS);
1013 }
1014 else if ((cp = strchr(name+prefixlen, '.')) != NULL) {
1015 /* CASE 2: still stepping-down for structured name
1016 prefix="foo.bar.", remainder="quux.baz" */
1017 if (!lh_lookup(val->lh, name+prefixlen, cp-(name+prefixlen), (void **)(void *)&obj, NULL))
1018 return VAL_RC(VAL_ERR_ARG);
1019 if (!(obj->type & VAL_TYPE_VAL))
1020 return VAL_RC(VAL_ERR_USE);
1021 child = *(val_t **)(val_storage(obj));
1022 if (depth == 0)
1023 return VAL_OK;
1024 return val_apply_internal(child, name, cp-name+1, depth-1, cb, ctx);
1025 } else {
1026 /* CASE 3: reached last component of structured name
1027 prefix="foo.bar.quux.", remainder="baz" */
1028 if (!lh_lookup(val->lh, name+prefixlen, strlen(name+prefixlen), (void **)(void *)&obj, NULL))
1029 return VAL_RC(VAL_ERR_ARG);
1030 if ((rc = cb(ctx, name, (obj->type & ~VAL_INLINE),
1031 obj->desc, val_storage(obj))) != VAL_OK)
1032 return VAL_RC(rc);
1033 if (obj->type & VAL_TYPE_VAL) {
1034 if (depth == 0)
1035 return VAL_OK;
1036 child = *(val_t **)(val_storage(obj));
1037 return val_apply_internal(child, name, strlen(name), depth-1, cb, ctx);
1038 }
1039 }
1040 return VAL_OK;
1041 }
1042
1043 /* apply a callback to each value */
val_apply(val_t * val,const char * name,int depth,val_cb_t cb,void * ctx)1044 val_rc_t val_apply(val_t *val, const char *name, int depth, val_cb_t cb, void *ctx)
1045 {
1046 /* argument consistency check */
1047 if (val == NULL || name == NULL || depth < 0 || cb == NULL)
1048 return VAL_RC(VAL_ERR_ARG);
1049
1050 /* just pass-through to internal API-extended variant */
1051 return val_apply_internal(val, name, 0, depth, cb, ctx);
1052 }
1053
1054