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