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
391