1: #include "first.h"
2:
3: #include "array.h"
4: #include "buffer.h"
5:
6: #include <string.h>
7: #include <stdio.h>
8: #include <stdlib.h>
9: #include <limits.h>
10:
11: #include <errno.h>
12: #include <assert.h>
13:
14: #define ARRAY_NOT_FOUND ((size_t)(-1))
15:
16: array *array_init(void) {
17: array *a;
18:
19: a = calloc(1, sizeof(*a));
20: force_assert(a);
21:
22: return a;
23: }
24:
25: array *array_init_array(array *src) {
26: size_t i;
27: array *a = array_init();
28:
29: if (0 == src->size) return a;
30:
31: a->used = src->used;
32: a->size = src->size;
33: a->unique_ndx = src->unique_ndx;
34:
35: a->data = malloc(sizeof(*src->data) * src->size);
36: force_assert(NULL != a->data);
37: for (i = 0; i < src->size; i++) {
38: if (src->data[i]) a->data[i] = src->data[i]->copy(src->data[i]);
39: else a->data[i] = NULL;
40: }
41:
42: a->sorted = malloc(sizeof(*src->sorted) * src->size);
43: force_assert(NULL != a->sorted);
44: memcpy(a->sorted, src->sorted, sizeof(*src->sorted) * src->size);
45: return a;
46: }
47:
48: void array_free(array *a) {
49: size_t i;
50: if (!a) return;
51:
52: for (i = 0; i < a->size; i++) {
53: if (a->data[i]) a->data[i]->free(a->data[i]);
54: }
55:
56: if (a->data) free(a->data);
57: if (a->sorted) free(a->sorted);
58:
59: free(a);
60: }
61:
62: void array_reset(array *a) {
63: size_t i;
64: if (!a) return;
65:
66: for (i = 0; i < a->used; i++) {
67: a->data[i]->reset(a->data[i]);
68: }
69:
70: a->used = 0;
71: a->unique_ndx = 0;
72: }
73:
74: data_unset *array_pop(array *a) {
75: data_unset *du;
76:
77: force_assert(a->used != 0);
78:
79: a->used --;
80: du = a->data[a->used];
81: force_assert(a->sorted[a->used] == a->used); /* only works on "simple" lists */
82: a->data[a->used] = NULL;
83:
84: return du;
85: }
86:
87: /* returns index of element or ARRAY_NOT_FOUND
88: * if rndx != NULL it stores the position in a->sorted[] where the key needs
89: * to be inserted
90: */
91: static size_t array_get_index(array *a, const char *key, size_t keylen, size_t *rndx) {
92: /* invariant: [lower-1] < key < [upper]
93: * "virtual elements": [-1] = -INFTY, [a->used] = +INFTY
94: * also an invariant: 0 <= lower <= upper <= a->used
95: */
96: size_t lower = 0, upper = a->used;
97: force_assert(upper <= SSIZE_MAX); /* (lower + upper) can't overflow */
98:
99: while (lower != upper) {
100: size_t probe = (lower + upper) / 2;
101: int cmp = buffer_caseless_compare(key, keylen, CONST_BUF_LEN(a->data[a->sorted[probe]]->key));
102: assert(lower < upper); /* from loop invariant (lower <= upper) + (lower != upper) */
103: assert((lower <= probe) && (probe < upper)); /* follows from lower < upper */
104:
105: if (cmp == 0) {
106: /* found */
107: if (rndx) *rndx = probe;
108: return a->sorted[probe];
109: } else if (cmp < 0) {
110: /* key < [probe] */
111: upper = probe; /* still: lower <= upper */
112: } else {
113: /* key > [probe] */
114: lower = probe + 1; /* still: lower <= upper */
115: }
116: }
117:
118: /* not found: [lower-1] < key < [upper] = [lower] ==> insert at [lower] */
119: if (rndx) *rndx = lower;
120: return ARRAY_NOT_FOUND;
121: }
122:
123: data_unset *array_get_element(array *a, const char *key) {
124: size_t ndx;
125: force_assert(NULL != key);
126:
127: if (ARRAY_NOT_FOUND != (ndx = array_get_index(a, key, strlen(key), NULL))) {
128: /* found, return it */
129: return a->data[ndx];
130: }
131:
132: return NULL;
133: }
134:
135: data_unset *array_extract_element(array *a, const char *key) {
136: size_t ndx, pos;
137: force_assert(NULL != key);
138:
139: if (ARRAY_NOT_FOUND != (ndx = array_get_index(a, key, strlen(key), &pos))) {
140: /* found */
141: const size_t last_ndx = a->used - 1;
142: data_unset *entry = a->data[ndx];
143:
144: /* now we need to swap it with the last element (if it isn't already the last element) */
145: if (ndx != last_ndx) {
146: /* to swap we also need to modify the index in a->sorted - find pos of last_elem there */
147: size_t last_elem_pos;
148: /* last element must be present at the expected position */
149: force_assert(last_ndx == array_get_index(a, CONST_BUF_LEN(a->data[last_ndx]->key), &last_elem_pos));
150:
151: /* move entry from last_ndx to ndx */
152: a->data[ndx] = a->data[last_ndx];
153: a->data[last_ndx] = NULL;
154:
155: /* fix index entry for moved entry */
156: a->sorted[last_elem_pos] = ndx;
157: } else {
158: a->data[ndx] = NULL;
159: }
160:
161: /* remove entry in a->sorted: move everything after pos one step to the left */
162: if (pos != last_ndx) {
163: memmove(a->sorted + pos, a->sorted + pos + 1, (last_ndx - pos) * sizeof(*a->sorted));
164: }
165: a->sorted[last_ndx] = ARRAY_NOT_FOUND;
166: --a->used;
167:
168: return entry;
169: }
170:
171: return NULL;
172: }
173:
174: data_unset *array_get_unused_element(array *a, data_type_t t) {
175: data_unset *ds = NULL;
176: unsigned int i;
177:
178: for (i = a->used; i < a->size; i++) {
179: if (a->data[i] && a->data[i]->type == t) {
180: ds = a->data[i];
181:
182: /* make empty slot at a->used for next insert */
183: a->data[i] = a->data[a->used];
184: a->data[a->used] = NULL;
185:
186: return ds;
187: }
188: }
189:
190: return NULL;
191: }
192:
193: void array_set_key_value(array *hdrs, const char *key, size_t key_len, const char *value, size_t val_len) {
194: data_string *ds_dst;
195:
196: if (NULL != (ds_dst = (data_string *)array_get_element(hdrs, key))) {
197: buffer_copy_string_len(ds_dst->value, value, val_len);
198: return;
199: }
200:
201: if (NULL == (ds_dst = (data_string *)array_get_unused_element(hdrs, TYPE_STRING))) {
202: ds_dst = data_string_init();
203: }
204:
205: buffer_copy_string_len(ds_dst->key, key, key_len);
206: buffer_copy_string_len(ds_dst->value, value, val_len);
207: array_insert_unique(hdrs, (data_unset *)ds_dst);
208: }
209:
210: /* if entry already exists return pointer to existing entry, otherwise insert entry and return NULL */
211: static data_unset **array_find_or_insert(array *a, data_unset *entry) {
212: size_t ndx, pos, j;
213:
214: /* generate unique index if neccesary */
215: if (buffer_is_empty(entry->key) || entry->is_index_key) {
216: buffer_copy_int(entry->key, a->unique_ndx++);
217: entry->is_index_key = 1;
218: force_assert(0 != a->unique_ndx); /* must not wrap or we'll get problems */
219: }
220:
221: /* try to find the entry */
222: if (ARRAY_NOT_FOUND != (ndx = array_get_index(a, CONST_BUF_LEN(entry->key), &pos))) {
223: /* found collision, return it */
224: return &a->data[ndx];
225: }
226:
227: /* insert */
228:
229: /* there couldn't possibly be enough memory to store so many entries */
230: force_assert(a->used + 1 <= SSIZE_MAX);
231:
232: if (a->size == 0) {
233: a->size = 16;
234: a->data = malloc(sizeof(*a->data) * a->size);
235: a->sorted = malloc(sizeof(*a->sorted) * a->size);
236: force_assert(a->data);
237: force_assert(a->sorted);
238: for (j = a->used; j < a->size; j++) a->data[j] = NULL;
239: } else if (a->size == a->used) {
240: a->size += 16;
241: a->data = realloc(a->data, sizeof(*a->data) * a->size);
242: a->sorted = realloc(a->sorted, sizeof(*a->sorted) * a->size);
243: force_assert(a->data);
244: force_assert(a->sorted);
245: for (j = a->used; j < a->size; j++) a->data[j] = NULL;
246: }
247:
248: ndx = a->used;
249:
250: /* make sure there is nothing here */
251: if (a->data[ndx]) a->data[ndx]->free(a->data[ndx]);
252:
253: a->data[a->used++] = entry;
254:
255: /* move everything one step to the right */
256: if (pos != ndx) {
257: memmove(a->sorted + (pos + 1), a->sorted + (pos), (ndx - pos) * sizeof(*a->sorted));
258: }
259:
260: /* insert */
261: a->sorted[pos] = ndx;
262:
263: return NULL;
264: }
265:
266: /* replace or insert data (free existing entry) */
267: void array_replace(array *a, data_unset *entry) {
268: data_unset **old;
269:
270: force_assert(NULL != entry);
271: if (NULL != (old = array_find_or_insert(a, entry))) {
272: force_assert(*old != entry);
273: (*old)->free(*old);
274: *old = entry;
275: }
276: }
277:
278: void array_insert_unique(array *a, data_unset *entry) {
279: data_unset **old;
280:
281: force_assert(NULL != entry);
282: if (NULL != (old = array_find_or_insert(a, entry))) {
283: force_assert((*old)->type == entry->type);
284: entry->insert_dup(*old, entry);
285: }
286: }
287:
288: void array_print_indent(int depth) {
289: int i;
290: for (i = 0; i < depth; i ++) {
291: fprintf(stdout, " ");
292: }
293: }
294:
295: size_t array_get_max_key_length(array *a) {
296: size_t maxlen, i;
297:
298: maxlen = 0;
299: for (i = 0; i < a->used; i ++) {
300: data_unset *du = a->data[i];
301: size_t len = strlen(du->key->ptr);
302:
303: if (len > maxlen) {
304: maxlen = len;
305: }
306: }
307: return maxlen;
308: }
309:
310: int array_print(array *a, int depth) {
311: size_t i;
312: size_t maxlen;
313: int oneline = 1;
314:
315: if (a->used > 5) {
316: oneline = 0;
317: }
318: for (i = 0; i < a->used && oneline; i++) {
319: data_unset *du = a->data[i];
320: if (!du->is_index_key) {
321: oneline = 0;
322: break;
323: }
324: switch (du->type) {
325: case TYPE_INTEGER:
326: case TYPE_STRING:
327: case TYPE_COUNT:
328: break;
329: default:
330: oneline = 0;
331: break;
332: }
333: }
334: if (oneline) {
335: fprintf(stdout, "(");
336: for (i = 0; i < a->used; i++) {
337: data_unset *du = a->data[i];
338: if (i != 0) {
339: fprintf(stdout, ", ");
340: }
341: du->print(du, depth + 1);
342: }
343: fprintf(stdout, ")");
344: return 0;
345: }
346:
347: maxlen = array_get_max_key_length(a);
348: fprintf(stdout, "(\n");
349: for (i = 0; i < a->used; i++) {
350: data_unset *du = a->data[i];
351: array_print_indent(depth + 1);
352: if (!du->is_index_key) {
353: int j;
354:
355: if (i && (i % 5) == 0) {
356: fprintf(stdout, "# %zu\n", i);
357: array_print_indent(depth + 1);
358: }
359: fprintf(stdout, "\"%s\"", du->key->ptr);
360: for (j = maxlen - strlen(du->key->ptr); j > 0; j --) {
361: fprintf(stdout, " ");
362: }
363: fprintf(stdout, " => ");
364: }
365: du->print(du, depth + 1);
366: fprintf(stdout, ",\n");
367: }
368: if (!(i && (i - 1 % 5) == 0)) {
369: array_print_indent(depth + 1);
370: fprintf(stdout, "# %zu\n", i);
371: }
372: array_print_indent(depth);
373: fprintf(stdout, ")");
374:
375: return 0;
376: }
377:
378: #ifdef DEBUG_ARRAY
379: int main (int argc, char **argv) {
380: array *a;
381: data_string *ds;
382: data_count *dc;
383:
384: UNUSED(argc);
385: UNUSED(argv);
386:
387: a = array_init();
388:
389: ds = data_string_init();
390: buffer_copy_string_len(ds->key, CONST_STR_LEN("abc"));
391: buffer_copy_string_len(ds->value, CONST_STR_LEN("alfrag"));
392:
393: array_insert_unique(a, (data_unset *)ds);
394:
395: ds = data_string_init();
396: buffer_copy_string_len(ds->key, CONST_STR_LEN("abc"));
397: buffer_copy_string_len(ds->value, CONST_STR_LEN("hameplman"));
398:
399: array_insert_unique(a, (data_unset *)ds);
400:
401: ds = data_string_init();
402: buffer_copy_string_len(ds->key, CONST_STR_LEN("123"));
403: buffer_copy_string_len(ds->value, CONST_STR_LEN("alfrag"));
404:
405: array_insert_unique(a, (data_unset *)ds);
406:
407: dc = data_count_init();
408: buffer_copy_string_len(dc->key, CONST_STR_LEN("def"));
409:
410: array_insert_unique(a, (data_unset *)dc);
411:
412: dc = data_count_init();
413: buffer_copy_string_len(dc->key, CONST_STR_LEN("def"));
414:
415: array_insert_unique(a, (data_unset *)dc);
416:
417: array_print(a, 0);
418:
419: array_free(a);
420:
421: fprintf(stderr, "%d\n",
422: buffer_caseless_compare(CONST_STR_LEN("Content-Type"), CONST_STR_LEN("Content-type")));
423:
424: return 0;
425: }
426: #endif
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to array.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / lighttpd / src