1 /*** alist.c -- bog standard associative lists
2 *
3 * Copyright (C) 2010-2016 Sebastian Freundt
4 *
5 * Author: Sebastian Freundt <freundt@ga-group.nl>
6 *
7 * This file is part of dateutils.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 *
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 *
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 *
20 * 3. Neither the name of the author nor the names of any contributors
21 * may be used to endorse or promote products derived from this
22 * software without specific prior written permission.
23 *
24 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR "AS IS" AND ANY EXPRESS OR
25 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
26 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
27 * DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
29 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
30 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
31 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
32 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
33 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
34 * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
35 *
36 ***/
37 #if defined HAVE_CONFIG_H
38 # include "config.h"
39 #endif /* HAVE_CONFIG_H */
40 #include <stddef.h>
41 #include <stdlib.h>
42 #include <stdbool.h>
43 #include <string.h>
44 #include "alist.h"
45 #include "nifty.h"
46
47 /* our alist is a simple flat char array with pointers behind every key
48 * aligned to void* boundaries. */
49
50 static const void**
__assoc(alist_t al,const char * key)51 __assoc(alist_t al, const char *key)
52 {
53 for (const char *ap = al->data, *const ep = ap + al->dend; ap < ep;) {
54 const char *kp;
55 const void **res = (const void**)al->data;
56
57 /* unrolled strcmp */
58 for (kp = key; *ap && *ap == *kp; ap++, kp++);
59
60 /* fast forward to void** boundary */
61 res += (ap - al->data) / sizeof(res) + 1U;
62
63 if (*ap == *kp) {
64 /* match! invariant: ap == kp == '\0' */
65 return res;
66 } else if (*ap) {
67 /* fast forward in void** increments */
68 for (; ((const char*)res)[-1]; res++);
69 }
70 /* skip over ptr, start again */
71 ap = (const char*)++res;
72 }
73 return NULL;
74 }
75
76 static bool
__fitsp(alist_t al,size_t keylen)77 __fitsp(alist_t al, size_t keylen)
78 {
79 return al->dend + keylen + 2 * sizeof(void**) < al->allz;
80 }
81
82 static int
__chk_resz(alist_t al,size_t keylen)83 __chk_resz(alist_t al, size_t keylen)
84 {
85 if (UNLIKELY(!__fitsp(al, keylen))) {
86 size_t ol = al->allz;
87 void *tmp;
88
89 al->allz = (al->allz * 2U) ?: 64U;
90 if (UNLIKELY((tmp = realloc(al->data, al->allz)) == NULL)) {
91 free_alist(al);
92 return -1;
93 }
94 al->data = tmp;
95 memset(al->data + ol, 0, al->allz - ol);
96 }
97 return 0;
98 }
99
100
101 /* public api */
102 void
free_alist(alist_t al)103 free_alist(alist_t al)
104 {
105 if (LIKELY(al->data != NULL)) {
106 free(al->data);
107 memset(al, 0, sizeof(*al));
108 }
109 return;
110 }
111
112 const void*
alist_assoc(alist_t al,const char * key)113 alist_assoc(alist_t al, const char *key)
114 {
115 const void **res;
116
117 if (UNLIKELY(al->data == NULL)) {
118 goto nada;
119 } else if ((res = __assoc(al, key)) == NULL) {
120 goto nada;
121 }
122 return *res;
123 nada:
124 return NULL;
125 }
126
127 void
alist_put(alist_t al,const char * key,const void * val)128 alist_put(alist_t al, const char *key, const void *val)
129 {
130 size_t klen = strlen(key);
131
132 __chk_resz(al, klen);
133 memcpy(al->data + al->dend, key, klen);
134 /* round up to void** boundary */
135 with (const void **data = (const void**)al->data) {
136 data += (al->dend + klen) / sizeof(data) + 1U;
137 *data++ = val;
138 al->dend = (const char*)data - al->data;
139 }
140 return;
141 }
142
143 void
alist_set(alist_t al,const char * key,const void * val)144 alist_set(alist_t al, const char *key, const void *val)
145 {
146 const void **ass;
147
148 if ((ass = __assoc(al, key)) != NULL) {
149 *ass = val;
150 return;
151 }
152 alist_put(al, key, val);
153 return;
154 }
155
156 acons_t
alist_next(alist_t al)157 alist_next(alist_t al)
158 {
159 acons_t res;
160
161 if (UNLIKELY((const char*)al->iter >= al->data + al->dend)) {
162 al->iter = NULL;
163 res = (acons_t){NULL, NULL};
164 } else {
165 const char *p = al->iter ?: al->data;
166 size_t klen = strlen(p);
167
168 with (const void *const *d = (const void*)p) {
169 d += klen / sizeof(d) + 1U;
170 res.key = p;
171 res.val = *d++;
172 al->iter = d;
173 }
174 }
175 return res;
176 }
177
178 /* alist.c ends here */
179