1 #include "array.h"
2 #include "buffer.h"
3
4 #include <string.h>
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <limits.h>
8
9 #include <errno.h>
10 #include <assert.h>
11
array_init(void)12 array *array_init(void) {
13 array *a;
14
15 a = calloc(1, sizeof(*a));
16 assert(a);
17
18 a->next_power_of_2 = 1;
19
20 return a;
21 }
22
array_init_array(array * src)23 array *array_init_array(array *src) {
24 size_t i;
25 array *a = array_init();
26
27 a->used = src->used;
28 a->size = src->size;
29 a->next_power_of_2 = src->next_power_of_2;
30 a->unique_ndx = src->unique_ndx;
31
32 a->data = malloc(sizeof(*src->data) * src->size);
33 for (i = 0; i < src->size; i++) {
34 if (src->data[i]) a->data[i] = src->data[i]->copy(src->data[i]);
35 else a->data[i] = NULL;
36 }
37
38 a->sorted = malloc(sizeof(*src->sorted) * src->size);
39 memcpy(a->sorted, src->sorted, sizeof(*src->sorted) * src->size);
40 return a;
41 }
42
array_free(array * a)43 void array_free(array *a) {
44 size_t i;
45 if (!a) return;
46
47 if (!a->is_weakref) {
48 for (i = 0; i < a->size; i++) {
49 if (a->data[i]) a->data[i]->free(a->data[i]);
50 }
51 }
52
53 if (a->data) free(a->data);
54 if (a->sorted) free(a->sorted);
55
56 free(a);
57 }
58
array_reset(array * a)59 void array_reset(array *a) {
60 size_t i;
61 if (!a) return;
62
63 if (!a->is_weakref) {
64 for (i = 0; i < a->used; i++) {
65 a->data[i]->reset(a->data[i]);
66 }
67 }
68
69 a->used = 0;
70 }
71
array_pop(array * a)72 data_unset *array_pop(array *a) {
73 data_unset *du;
74
75 assert(a->used != 0);
76
77 a->used --;
78 du = a->data[a->used];
79 a->data[a->used] = NULL;
80
81 return du;
82 }
83
array_get_index(array * a,const char * key,size_t keylen,int * rndx)84 static int array_get_index(array *a, const char *key, size_t keylen, int *rndx) {
85 int ndx = -1;
86 int i, pos = 0;
87
88 if (key == NULL) return -1;
89
90 /* try to find the string */
91 for (i = pos = a->next_power_of_2 / 2; ; i >>= 1) {
92 int cmp;
93
94 if (pos < 0) {
95 pos += i;
96 } else if (pos >= (int)a->used) {
97 pos -= i;
98 } else {
99 cmp = buffer_caseless_compare(key, keylen, a->data[a->sorted[pos]]->key->ptr, a->data[a->sorted[pos]]->key->used);
100
101 if (cmp == 0) {
102 /* found */
103 ndx = a->sorted[pos];
104 break;
105 } else if (cmp < 0) {
106 pos -= i;
107 } else {
108 pos += i;
109 }
110 }
111 if (i == 0) break;
112 }
113
114 if (rndx) *rndx = pos;
115
116 return ndx;
117 }
118
array_get_element(array * a,const char * key)119 data_unset *array_get_element(array *a, const char *key) {
120 int ndx;
121
122 if (-1 != (ndx = array_get_index(a, key, strlen(key) + 1, NULL))) {
123 /* found, leave here */
124
125 return a->data[ndx];
126 }
127
128 return NULL;
129 }
130
array_get_unused_element(array * a,data_type_t t)131 data_unset *array_get_unused_element(array *a, data_type_t t) {
132 data_unset *ds = NULL;
133 unsigned int i;
134
135 for (i = a->used; i < a->size; i++) {
136 if (a->data[i] && a->data[i]->type == t) {
137 ds = a->data[i];
138
139 /* make empty slot at a->used for next insert */
140 a->data[i] = a->data[a->used];
141 a->data[a->used] = NULL;
142
143 return ds;
144 }
145 }
146
147 return NULL;
148 }
149
array_set_key_value(array * hdrs,const char * key,size_t key_len,const char * value,size_t val_len)150 void array_set_key_value(array *hdrs, const char *key, size_t key_len, const char *value, size_t val_len) {
151 data_string *ds_dst;
152
153 if (NULL != (ds_dst = (data_string *)array_get_element(hdrs, key))) {
154 buffer_copy_string_len(ds_dst->value, value, val_len);
155 return;
156 }
157
158 if (NULL == (ds_dst = (data_string *)array_get_unused_element(hdrs, TYPE_STRING))) {
159 ds_dst = data_string_init();
160 }
161
162 buffer_copy_string_len(ds_dst->key, key, key_len);
163 buffer_copy_string_len(ds_dst->value, value, val_len);
164 array_insert_unique(hdrs, (data_unset *)ds_dst);
165 }
166
167 /* replace or insert data, return the old one with the same key */
array_replace(array * a,data_unset * du)168 data_unset *array_replace(array *a, data_unset *du) {
169 int ndx;
170
171 if (-1 == (ndx = array_get_index(a, du->key->ptr, du->key->used, NULL))) {
172 array_insert_unique(a, du);
173 return NULL;
174 } else {
175 data_unset *old = a->data[ndx];
176 a->data[ndx] = du;
177 return old;
178 }
179 }
180
array_insert_unique(array * a,data_unset * str)181 int array_insert_unique(array *a, data_unset *str) {
182 int ndx = -1;
183 int pos = 0;
184 size_t j;
185
186 /* generate unique index if neccesary */
187 if (str->key->used == 0 || str->is_index_key) {
188 buffer_copy_long(str->key, a->unique_ndx++);
189 str->is_index_key = 1;
190 }
191
192 /* try to find the string */
193 if (-1 != (ndx = array_get_index(a, str->key->ptr, str->key->used, &pos))) {
194 /* found, leave here */
195 if (a->data[ndx]->type == str->type) {
196 str->insert_dup(a->data[ndx], str);
197 } else {
198 SEGFAULT();
199 }
200 return 0;
201 }
202
203 /* insert */
204
205 if (a->used+1 > INT_MAX) {
206 /* we can't handle more then INT_MAX entries: see array_get_index() */
207 return -1;
208 }
209
210 if (a->size == 0) {
211 a->size = 16;
212 a->data = malloc(sizeof(*a->data) * a->size);
213 a->sorted = malloc(sizeof(*a->sorted) * a->size);
214 assert(a->data);
215 assert(a->sorted);
216 for (j = a->used; j < a->size; j++) a->data[j] = NULL;
217 } else if (a->size == a->used) {
218 a->size += 16;
219 a->data = realloc(a->data, sizeof(*a->data) * a->size);
220 a->sorted = realloc(a->sorted, sizeof(*a->sorted) * a->size);
221 assert(a->data);
222 assert(a->sorted);
223 for (j = a->used; j < a->size; j++) a->data[j] = NULL;
224 }
225
226 ndx = (int) a->used;
227
228 /* make sure there is nothing here */
229 if (a->data[ndx]) a->data[ndx]->free(a->data[ndx]);
230
231 a->data[a->used++] = str;
232
233 if (pos != ndx &&
234 ((pos < 0) ||
235 buffer_caseless_compare(str->key->ptr, str->key->used, a->data[a->sorted[pos]]->key->ptr, a->data[a->sorted[pos]]->key->used) > 0)) {
236 pos++;
237 }
238
239 /* move everything on step to the right */
240 if (pos != ndx) {
241 memmove(a->sorted + (pos + 1), a->sorted + (pos), (ndx - pos) * sizeof(*a->sorted));
242 }
243
244 /* insert */
245 a->sorted[pos] = ndx;
246
247 if (a->next_power_of_2 == (size_t)ndx) a->next_power_of_2 <<= 1;
248
249 return 0;
250 }
251
array_print_indent(int depth)252 void array_print_indent(int depth) {
253 int i;
254 for (i = 0; i < depth; i ++) {
255 fprintf(stdout, " ");
256 }
257 }
258
array_get_max_key_length(array * a)259 size_t array_get_max_key_length(array *a) {
260 size_t maxlen, i;
261
262 maxlen = 0;
263 for (i = 0; i < a->used; i ++) {
264 data_unset *du = a->data[i];
265 size_t len = strlen(du->key->ptr);
266
267 if (len > maxlen) {
268 maxlen = len;
269 }
270 }
271 return maxlen;
272 }
273
array_print(array * a,int depth)274 int array_print(array *a, int depth) {
275 size_t i;
276 size_t maxlen;
277 int oneline = 1;
278
279 if (a->used > 5) {
280 oneline = 0;
281 }
282 for (i = 0; i < a->used && oneline; i++) {
283 data_unset *du = a->data[i];
284 if (!du->is_index_key) {
285 oneline = 0;
286 break;
287 }
288 switch (du->type) {
289 case TYPE_INTEGER:
290 case TYPE_STRING:
291 case TYPE_COUNT:
292 break;
293 default:
294 oneline = 0;
295 break;
296 }
297 }
298 if (oneline) {
299 fprintf(stdout, "(");
300 for (i = 0; i < a->used; i++) {
301 data_unset *du = a->data[i];
302 if (i != 0) {
303 fprintf(stdout, ", ");
304 }
305 du->print(du, depth + 1);
306 }
307 fprintf(stdout, ")");
308 return 0;
309 }
310
311 maxlen = array_get_max_key_length(a);
312 fprintf(stdout, "(\n");
313 for (i = 0; i < a->used; i++) {
314 data_unset *du = a->data[i];
315 array_print_indent(depth + 1);
316 if (!du->is_index_key) {
317 int j;
318
319 if (i && (i % 5) == 0) {
320 fprintf(stdout, "# %zd\n", i);
321 array_print_indent(depth + 1);
322 }
323 fprintf(stdout, "\"%s\"", du->key->ptr);
324 for (j = maxlen - strlen(du->key->ptr); j > 0; j --) {
325 fprintf(stdout, " ");
326 }
327 fprintf(stdout, " => ");
328 }
329 du->print(du, depth + 1);
330 fprintf(stdout, ",\n");
331 }
332 if (!(i && (i - 1 % 5) == 0)) {
333 array_print_indent(depth + 1);
334 fprintf(stdout, "# %zd\n", i);
335 }
336 array_print_indent(depth);
337 fprintf(stdout, ")");
338
339 return 0;
340 }
341
342 #ifdef DEBUG_ARRAY
main(int argc,char ** argv)343 int main (int argc, char **argv) {
344 array *a;
345 data_string *ds;
346 data_count *dc;
347
348 UNUSED(argc);
349 UNUSED(argv);
350
351 a = array_init();
352
353 ds = data_string_init();
354 buffer_copy_string_len(ds->key, CONST_STR_LEN("abc"));
355 buffer_copy_string_len(ds->value, CONST_STR_LEN("alfrag"));
356
357 array_insert_unique(a, (data_unset *)ds);
358
359 ds = data_string_init();
360 buffer_copy_string_len(ds->key, CONST_STR_LEN("abc"));
361 buffer_copy_string_len(ds->value, CONST_STR_LEN("hameplman"));
362
363 array_insert_unique(a, (data_unset *)ds);
364
365 ds = data_string_init();
366 buffer_copy_string_len(ds->key, CONST_STR_LEN("123"));
367 buffer_copy_string_len(ds->value, CONST_STR_LEN("alfrag"));
368
369 array_insert_unique(a, (data_unset *)ds);
370
371 dc = data_count_init();
372 buffer_copy_string_len(dc->key, CONST_STR_LEN("def"));
373
374 array_insert_unique(a, (data_unset *)dc);
375
376 dc = data_count_init();
377 buffer_copy_string_len(dc->key, CONST_STR_LEN("def"));
378
379 array_insert_unique(a, (data_unset *)dc);
380
381 array_print(a, 0);
382
383 array_free(a);
384
385 fprintf(stderr, "%d\n",
386 buffer_caseless_compare(CONST_STR_LEN("Content-Type"), CONST_STR_LEN("Content-type")));
387
388 return 0;
389 }
390 #endif
391