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));
16: assert(a);
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:
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:
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:
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:
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:
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:
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:
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:
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 */
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:
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:
252: void array_print_indent(int depth) {
253: int i;
254: for (i = 0; i < depth; i ++) {
255: fprintf(stdout, " ");
256: }
257: }
258:
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:
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
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
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