Annotation of embedaddon/lighttpd/src/array.c, revision 1.1.1.3
1.1.1.3 ! misho 1: #include "first.h"
! 2:
1.1 misho 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:
1.1.1.3 ! misho 14: #define ARRAY_NOT_FOUND ((size_t)(-1))
! 15:
1.1 misho 16: array *array_init(void) {
17: array *a;
18:
19: a = calloc(1, sizeof(*a));
1.1.1.2 misho 20: force_assert(a);
1.1 misho 21:
22: return a;
23: }
24:
25: array *array_init_array(array *src) {
26: size_t i;
27: array *a = array_init();
28:
1.1.1.2 misho 29: if (0 == src->size) return a;
30:
1.1 misho 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);
1.1.1.3 ! misho 36: force_assert(NULL != a->data);
1.1 misho 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:
1.1.1.3 ! misho 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);
1.1 misho 45: return a;
46: }
47:
48: void array_free(array *a) {
49: size_t i;
50: if (!a) return;
51:
1.1.1.3 ! misho 52: for (i = 0; i < a->size; i++) {
! 53: if (a->data[i]) a->data[i]->free(a->data[i]);
1.1 misho 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:
1.1.1.3 ! misho 66: for (i = 0; i < a->used; i++) {
! 67: a->data[i]->reset(a->data[i]);
1.1 misho 68: }
69:
70: a->used = 0;
1.1.1.3 ! misho 71: a->unique_ndx = 0;
1.1 misho 72: }
73:
74: data_unset *array_pop(array *a) {
75: data_unset *du;
76:
1.1.1.2 misho 77: force_assert(a->used != 0);
1.1 misho 78:
79: a->used --;
80: du = a->data[a->used];
1.1.1.3 ! misho 81: force_assert(a->sorted[a->used] == a->used); /* only works on "simple" lists */
1.1 misho 82: a->data[a->used] = NULL;
83:
84: return du;
85: }
86:
1.1.1.3 ! misho 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 */
1.1 misho 112: } else {
1.1.1.3 ! misho 113: /* key > [probe] */
! 114: lower = probe + 1; /* still: lower <= upper */
1.1 misho 115: }
116: }
117:
1.1.1.3 ! misho 118: /* not found: [lower-1] < key < [upper] = [lower] ==> insert at [lower] */
! 119: if (rndx) *rndx = lower;
! 120: return ARRAY_NOT_FOUND;
1.1 misho 121: }
122:
123: data_unset *array_get_element(array *a, const char *key) {
1.1.1.3 ! misho 124: size_t ndx;
! 125: force_assert(NULL != key);
1.1 misho 126:
1.1.1.3 ! misho 127: if (ARRAY_NOT_FOUND != (ndx = array_get_index(a, key, strlen(key), NULL))) {
! 128: /* found, return it */
1.1 misho 129: return a->data[ndx];
130: }
131:
132: return NULL;
133: }
134:
1.1.1.3 ! misho 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:
1.1 misho 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:
1.1.1.3 ! misho 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;
1.1 misho 213:
214: /* generate unique index if neccesary */
1.1.1.3 ! misho 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 */
1.1 misho 219: }
220:
1.1.1.3 ! misho 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];
1.1 misho 225: }
226:
227: /* insert */
228:
1.1.1.3 ! misho 229: /* there couldn't possibly be enough memory to store so many entries */
! 230: force_assert(a->used + 1 <= SSIZE_MAX);
1.1 misho 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);
1.1.1.2 misho 236: force_assert(a->data);
237: force_assert(a->sorted);
1.1 misho 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);
1.1.1.2 misho 243: force_assert(a->data);
244: force_assert(a->sorted);
1.1 misho 245: for (j = a->used; j < a->size; j++) a->data[j] = NULL;
246: }
247:
1.1.1.3 ! misho 248: ndx = a->used;
1.1 misho 249:
250: /* make sure there is nothing here */
251: if (a->data[ndx]) a->data[ndx]->free(a->data[ndx]);
252:
1.1.1.3 ! misho 253: a->data[a->used++] = entry;
1.1 misho 254:
1.1.1.3 ! misho 255: /* move everything one step to the right */
1.1 misho 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:
1.1.1.3 ! misho 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;
1.1 misho 269:
1.1.1.3 ! misho 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: }
1.1 misho 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) {
1.1.1.3 ! misho 356: fprintf(stdout, "# %zu\n", i);
1.1 misho 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);
1.1.1.3 ! misho 370: fprintf(stdout, "# %zu\n", i);
1.1 misho 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