xref: /lighttpd1.4/src/array.c (revision 5722574d) 
1 #include "first.h"
2 
3 #include "array.h"
4 #include "buffer.h"
5 #include "settings.h"   /* BUFFER_MAX_REUSE_SIZE */
6 
7 #include <string.h>
8 #include <stdlib.h>
9 #include <limits.h>
10 
11 __attribute_cold__
12 static void array_extend(array * const a, uint32_t n) {
13     a->size  += n;
14     a->data   = realloc(a->data,   sizeof(*a->data)   * a->size);
15     a->sorted = realloc(a->sorted, sizeof(*a->sorted) * a->size);
16     force_assert(a->data);
17     force_assert(a->sorted);
18     memset(a->data+a->used, 0, (a->size-a->used)*sizeof(*a->data));
19 }
20 
21 array *array_init(uint32_t n) {
22 	array *a;
23 
24 	a = calloc(1, sizeof(*a));
25 	force_assert(a);
26 	if (n) array_extend(a, n);
27 
28 	return a;
29 }
30 
31 void array_free_data(array * const a) {
32 	if (a->sorted) free(a->sorted);
33 	data_unset ** const data = a->data;
34 	const uint32_t sz = a->size;
35 	for (uint32_t i = 0; i < sz; ++i) {
36 		if (data[i]) data[i]->fn->free(data[i]);
37 	}
38 	free(data);
39 	a->data = NULL;
40 	a->sorted = NULL;
41 	a->used = 0;
42 	a->size = 0;
43 }
44 
45 void array_copy_array(array * const dst, const array * const src) {
46 	array_free_data(dst);
47 	if (0 == src->size) return;
48 
49 	dst->used = src->used;
50 	dst->size = src->size;
51 
52 	dst->data = calloc(src->size, sizeof(*src->data));
53 	force_assert(NULL != dst->data);
54 	dst->sorted = malloc(sizeof(*src->sorted) * src->size);
55 	force_assert(NULL != dst->sorted);
56 	memcpy(dst->sorted, src->sorted, sizeof(*src->sorted) * src->used);
57 	for (uint32_t i = 0; i < src->used; ++i) {
58 		dst->data[i] = src->data[i]->fn->copy(src->data[i]);
59 	}
60 }
61 
62 void array_free(array * const a) {
63 	if (!a) return;
64 	array_free_data(a);
65 	free(a);
66 }
67 
68 void array_reset_data_strings(array * const a) {
69 	if (!a) return;
70 
71 	data_string ** const data = (data_string **)a->data;
72 	const uint32_t used = a->used;
73 	a->used = 0;
74 	for (uint32_t i = 0; i < used; ++i) {
75 		data_string * const ds = data[i];
76 		/*force_assert(ds->type == TYPE_STRING);*/
77 		buffer * const k = &ds->key;
78 		buffer * const v = &ds->value;
79 		if (k->size > BUFFER_MAX_REUSE_SIZE) buffer_reset(k);
80 		if (v->size > BUFFER_MAX_REUSE_SIZE) buffer_reset(v);
81 	}
82 }
83 
84 #if 0 /*(unused; see array_extract_element_klen())*/
85 data_unset *array_pop(array * const a) {
86 	data_unset *du;
87 
88 	force_assert(a->used != 0);
89 
90 	a->used --;
91 	du = a->data[a->used];
92 	force_assert(a->sorted[a->used] == du); /* only works on "simple" lists */
93 	a->data[a->used] = NULL;
94 
95 	return du;
96 }
97 #endif
98 
99 __attribute_pure__
100 static int array_caseless_compare(const char * const a, const char * const b, const size_t len) {
101     for (size_t i = 0; i < len; ++i) {
102         unsigned int ca = ((unsigned char *)a)[i];
103         unsigned int cb = ((unsigned char *)b)[i];
104         if (ca == cb) continue;
105 
106         /* always lowercase for transitive results */
107         if (ca >= 'A' && ca <= 'Z') ca |= 32;
108         if (cb >= 'A' && cb <= 'Z') cb |= 32;
109 
110         if (ca == cb) continue;
111         return (int)(ca - cb);
112     }
113     return 0;
114 }
115 
116 __attribute_pure__
117 static int array_keycmp(const char * const a, const size_t alen, const char * const b, const size_t blen) {
118     return alen < blen ? -1 : alen > blen ? 1 : array_caseless_compare(a, b, blen);
119 }
120 
121 /* returns pos into a->sorted[] which contains copy of data (ptr) in a->data[]
122  * if pos >= 0, or returns -pos-1 if that is the position-1 in a->sorted[]
123  * where the key needs to be inserted (-1 to avoid -0)
124  */
125 __attribute_hot__
126 __attribute_pure__
127 static int32_t array_get_index(const array * const a, const char * const k, const size_t klen) {
128     /* invariant: [lower-1] < probe < [upper]
129      * invariant: 0 <= lower <= upper <= a->used
130      */
131     uint32_t lower = 0, upper = a->used;
132     while (lower != upper) {
133         uint32_t probe = (lower + upper) / 2;
134         const buffer * const b = &a->sorted[probe]->key;
135         /* key is non-empty (0==b->used), though possibly blank (1==b->used),
136          * if inserted into key-value array */
137         /*force_assert(b && b->used);*/
138         int cmp = array_keycmp(k, klen, b->ptr, b->used-1);
139         /*int cmp = array_keycmp(k, klen, CONST_BUF_LEN(b));*/
140         if (cmp < 0)           /* key < [probe] */
141             upper = probe;     /* still: lower <= upper */
142         else if (cmp > 0)      /* key > [probe] */
143             lower = probe + 1; /* still: lower <= upper */
144         else  /*(cmp == 0)*/   /* found */
145             return (int32_t)probe;
146     }
147     /* not found: [lower-1] < key < [upper] = [lower] ==> insert at [lower] */
148     return -(int)lower - 1;
149 }
150 
151 __attribute_hot__
152 data_unset *array_get_element_klen(const array * const a, const char *key, const size_t klen) {
153     const int32_t ipos = array_get_index(a, key, klen);
154     return ipos >= 0 ? a->sorted[ipos] : NULL;
155 }
156 
157 /* non-const (data_config *) for configparser.y (not array_get_element_klen())*/
158 data_unset *array_get_data_unset(const array * const a, const char *key, const size_t klen) {
159     const int32_t ipos = array_get_index(a, key, klen);
160     return ipos >= 0 ? a->sorted[ipos] : NULL;
161 }
162 
163 data_unset *array_extract_element_klen(array * const a, const char *key, const size_t klen) {
164     const int32_t ipos = array_get_index(a, key, klen);
165     if (ipos < 0) return NULL;
166 
167     /* remove entry from a->sorted: move everything after pos one step left */
168     data_unset * const entry = a->sorted[ipos];
169     const uint32_t last_ndx = --a->used;
170     if (last_ndx != (uint32_t)ipos) {
171         data_unset ** const d = a->sorted + ipos;
172         memmove(d, d+1, (last_ndx - (uint32_t)ipos) * sizeof(*d));
173     }
174 
175     if (entry != a->data[last_ndx]) {
176         /* walk a->data[] to find data ptr */
177         /* (not checking (ndx <= last_ndx) since entry must be in a->data[]) */
178         uint32_t ndx = 0;
179         while (entry != a->data[ndx]) ++ndx;
180         a->data[ndx] = a->data[last_ndx]; /* swap with last element */
181     }
182     a->data[last_ndx] = NULL;
183     return entry;
184 }
185 
186 static data_unset *array_get_unused_element(array * const a, const data_type_t t) {
187     /* After initial startup and config, most array usage is of homogeneous types
188      * and arrays are cleared once per request, so check only the first unused
189      * element to see if it can be reused */
190   #if 1
191     data_unset * const du = (a->used < a->size) ? a->data[a->used] : NULL;
192     if (NULL != du && du->type == t) {
193         a->data[a->used] = NULL;/* make empty slot at a->used for next insert */
194         return du;
195     }
196     return NULL;
197   #else
198 	data_unset ** const data = a->data;
199 	for (uint32_t i = a->used, sz = a->size; i < sz; ++i) {
200 		if (data[i] && data[i]->type == t) {
201 			data_unset * const ds = data[i];
202 
203 			/* make empty slot at a->used for next insert */
204 			data[i] = data[a->used];
205 			data[a->used] = NULL;
206 
207 			return ds;
208 		}
209 	}
210 
211 	return NULL;
212   #endif
213 }
214 
215 static void array_insert_data_at_pos(array * const a, data_unset * const entry, const uint32_t pos) {
216     /* This data structure should not be used for nearly so many entries */
217     force_assert(a->used + 1 <= INT32_MAX);
218 
219     if (a->size == a->used) {
220         array_extend(a, 16);
221     }
222 
223     const uint32_t ndx = a->used++;
224     data_unset * const prev = a->data[ndx];
225     a->data[ndx] = entry;
226 
227     /* move everything one step to the right */
228     if (pos != ndx) {
229         data_unset ** const d = a->sorted + pos;
230         memmove(d+1, d, (ndx - pos) * sizeof(*a->sorted));
231     }
232     a->sorted[pos] = entry;
233 
234     if (prev) prev->fn->free(prev); /* free prior data, if any, from slot */
235 }
236 
237 static data_integer * array_insert_integer_at_pos(array * const a, const uint32_t pos) {
238   #if 0 /*(not currently used by lighttpd in way that reuse would occur)*/
239     data_integer *di = (data_integer *)array_get_unused_element(a,TYPE_INTEGER);
240     if (NULL == di) di = data_integer_init();
241   #else
242     data_integer * const di = data_integer_init();
243   #endif
244     array_insert_data_at_pos(a, (data_unset *)di, pos);
245     return di;
246 }
247 
248 static data_string * array_insert_string_at_pos(array * const a, const uint32_t pos) {
249     data_string *ds = (data_string *)array_get_unused_element(a, TYPE_STRING);
250     if (NULL == ds) ds = data_string_init();
251     array_insert_data_at_pos(a, (data_unset *)ds, pos);
252     return ds;
253 }
254 
255 int * array_get_int_ptr(array * const a, const char * const k, const size_t klen) {
256     int32_t ipos = array_get_index(a, k, klen);
257     if (ipos >= 0) return &((data_integer *)a->sorted[ipos])->value;
258 
259     data_integer * const di =array_insert_integer_at_pos(a,(uint32_t)(-ipos-1));
260     buffer_copy_string_len(&di->key, k, klen);
261     di->value = 0;
262     return &di->value;
263 }
264 
265 buffer * array_get_buf_ptr(array * const a, const char * const k, const size_t klen) {
266     int32_t ipos = array_get_index(a, k, klen);
267     if (ipos >= 0) return &((data_string *)a->sorted[ipos])->value;
268 
269     data_string * const ds = array_insert_string_at_pos(a, (uint32_t)(-ipos-1));
270     buffer_copy_string_len(&ds->key, k, klen);
271     buffer_clear(&ds->value);
272     return &ds->value;
273 }
274 
275 void array_insert_value(array * const a, const char * const v, const size_t vlen) {
276     data_string * const ds = array_insert_string_at_pos(a, a->used);
277     buffer_clear(&ds->key);
278     buffer_copy_string_len(&ds->value, v, vlen);
279 }
280 
281 /* if entry already exists return pointer to existing entry, otherwise insert entry and return NULL */
282 __attribute_cold__
283 static data_unset **array_find_or_insert(array * const a, data_unset * const entry) {
284     force_assert(NULL != entry);
285 
286     /* push value onto end of array if there is no key */
287     if (buffer_is_empty(&entry->key)) {
288         array_insert_data_at_pos(a, entry, a->used);
289         return NULL;
290     }
291 
292     /* try to find the entry */
293     const int32_t ipos = array_get_index(a, CONST_BUF_LEN(&entry->key));
294     if (ipos >= 0) return &a->sorted[ipos];
295 
296     array_insert_data_at_pos(a, entry, (uint32_t)(-ipos - 1));
297     return NULL;
298 }
299 
300 /* replace or insert data (free existing entry) */
301 void array_replace(array * const a, data_unset * const entry) {
302     if (NULL == array_find_or_insert(a, entry)) return;
303 
304     /* find the entry (array_find_or_insert() returned non-NULL) */
305     const int32_t ipos = array_get_index(a, CONST_BUF_LEN(&entry->key));
306     force_assert(ipos >= 0);
307     data_unset *old = a->sorted[ipos];
308     force_assert(old != entry);
309     a->sorted[ipos] = entry;
310 
311     uint32_t i = 0;
312     while (i < a->used && a->data[i] != old) ++i;
313     force_assert(i != a->used);
314     a->data[i] = entry;
315 
316     old->fn->free(old);
317 }
318 
319 void array_insert_unique(array * const a, data_unset * const entry) {
320 	data_unset **old;
321 
322 	if (NULL != (old = array_find_or_insert(a, entry))) {
323 		force_assert((*old)->type == entry->type);
324 		entry->fn->insert_dup(*old, entry);
325 	}
326 }
327 
328 int array_is_vlist(const array * const a) {
329 	for (uint32_t i = 0; i < a->used; ++i) {
330 		data_unset *du = a->data[i];
331 		if (!buffer_is_empty(&du->key) || du->type != TYPE_STRING) return 0;
332 	}
333 	return 1;
334 }
335 
336 int array_is_kvany(const array * const a) {
337 	for (uint32_t i = 0; i < a->used; ++i) {
338 		data_unset *du = a->data[i];
339 		if (buffer_is_empty(&du->key)) return 0;
340 	}
341 	return 1;
342 }
343 
344 int array_is_kvarray(const array * const a) {
345 	for (uint32_t i = 0; i < a->used; ++i) {
346 		data_unset *du = a->data[i];
347 		if (buffer_is_empty(&du->key) || du->type != TYPE_ARRAY) return 0;
348 	}
349 	return 1;
350 }
351 
352 int array_is_kvstring(const array * const a) {
353 	for (uint32_t i = 0; i < a->used; ++i) {
354 		data_unset *du = a->data[i];
355 		if (buffer_is_empty(&du->key) || du->type != TYPE_STRING) return 0;
356 	}
357 	return 1;
358 }
359 
360 /* array_match_*() routines follow very similar pattern, but operate on slightly
361  * different data: array key/value, prefix/suffix match, case-insensitive or not
362  * While these could be combined into fewer routines with flags to modify the
363  * behavior, the interface distinctions are useful to add clarity to the code,
364  * and the specialized routines run slightly faster */
365 
366 data_unset *
367 array_match_key_prefix_klen (const array * const a, const char * const s, const size_t slen)
368 {
369     for (uint32_t i = 0; i < a->used; ++i) {
370         const buffer * const key = &a->data[i]->key;
371         const size_t klen = buffer_string_length(key);
372         if (klen <= slen && 0 == memcmp(s, key->ptr, klen))
373             return a->data[i];
374     }
375     return NULL;
376 }
377 
378 data_unset *
379 array_match_key_prefix_nc_klen (const array * const a, const char * const s, const size_t slen)
380 {
381     for (uint32_t i = 0; i < a->used; ++i) {
382         const buffer * const key = &a->data[i]->key;
383         const size_t klen = buffer_string_length(key);
384         if (klen <= slen && buffer_eq_icase_ssn(s, key->ptr, klen))
385             return a->data[i];
386     }
387     return NULL;
388 }
389 
390 data_unset *
391 array_match_key_prefix (const array * const a, const buffer * const b)
392 {
393   #ifdef __clang_analyzer__
394     force_assert(b);
395   #endif
396     return array_match_key_prefix_klen(a, CONST_BUF_LEN(b));
397 }
398 
399 data_unset *
400 array_match_key_prefix_nc (const array * const a, const buffer * const b)
401 {
402     return array_match_key_prefix_nc_klen(a, CONST_BUF_LEN(b));
403 }
404 
405 const buffer *
406 array_match_value_prefix (const array * const a, const buffer * const b)
407 {
408     const size_t blen = buffer_string_length(b);
409 
410     for (uint32_t i = 0; i < a->used; ++i) {
411         const buffer * const value = &((data_string *)a->data[i])->value;
412         const size_t vlen = buffer_string_length(value);
413         if (vlen <= blen && 0 == memcmp(b->ptr, value->ptr, vlen))
414             return value;
415     }
416     return NULL;
417 }
418 
419 const buffer *
420 array_match_value_prefix_nc (const array * const a, const buffer * const b)
421 {
422     const size_t blen = buffer_string_length(b);
423 
424     for (uint32_t i = 0; i < a->used; ++i) {
425         const buffer * const value = &((data_string *)a->data[i])->value;
426         const size_t vlen = buffer_string_length(value);
427         if (vlen <= blen && buffer_eq_icase_ssn(b->ptr, value->ptr, vlen))
428             return value;
429     }
430     return NULL;
431 }
432 
433 data_unset *
434 array_match_key_suffix (const array * const a, const buffer * const b)
435 {
436     const size_t blen = buffer_string_length(b);
437     const char * const end = b->ptr + blen;
438 
439     for (uint32_t i = 0; i < a->used; ++i) {
440         const buffer * const key = &a->data[i]->key;
441         const size_t klen = buffer_string_length(key);
442         if (klen <= blen && 0 == memcmp(end - klen, key->ptr, klen))
443             return a->data[i];
444     }
445     return NULL;
446 }
447 
448 data_unset *
449 array_match_key_suffix_nc (const array * const a, const buffer * const b)
450 {
451     const size_t blen = buffer_string_length(b);
452     const char * const end = b->ptr + blen;
453 
454     for (uint32_t i = 0; i < a->used; ++i) {
455         const buffer * const key = &a->data[i]->key;
456         const size_t klen = buffer_string_length(key);
457         if (klen <= blen && buffer_eq_icase_ssn(end - klen, key->ptr, klen))
458             return a->data[i];
459     }
460     return NULL;
461 }
462 
463 const buffer *
464 array_match_value_suffix (const array * const a, const buffer * const b)
465 {
466     const size_t blen = buffer_string_length(b);
467     const char * const end = b->ptr + blen;
468 
469     for (uint32_t i = 0; i < a->used; ++i) {
470         const buffer * const value = &((data_string *)a->data[i])->value;
471         const size_t vlen = buffer_string_length(value);
472         if (vlen <= blen && 0 == memcmp(end - vlen, value->ptr, vlen))
473             return value;
474     }
475     return NULL;
476 }
477 
478 const buffer *
479 array_match_value_suffix_nc (const array * const a, const buffer * const b)
480 {
481     const size_t blen = buffer_string_length(b);
482     const char * const end = b->ptr + blen;
483 
484     for (uint32_t i = 0; i < a->used; ++i) {
485         const buffer * const value = &((data_string *)a->data[i])->value;
486         const size_t vlen = buffer_string_length(value);
487         if (vlen <= blen && buffer_eq_icase_ssn(end - vlen, value->ptr, vlen))
488             return value;
489     }
490     return NULL;
491 }
492 
493 data_unset *
494 array_match_path_or_ext (const array * const a, const buffer * const b)
495 {
496     const size_t blen = buffer_string_length(b);
497 
498     for (uint32_t i = 0; i < a->used; ++i) {
499         /* check extension in the form "^/path" or ".ext$" */
500         const buffer * const key = &a->data[i]->key;
501         const size_t klen = buffer_string_length(key);
502         if (klen <= blen
503             && 0 == memcmp((*(key->ptr) == '/' ? b->ptr : b->ptr + blen - klen),
504                            key->ptr, klen))
505             return a->data[i];
506     }
507     return NULL;
508 }
509 
510 
511 
512 
513 
514 #include <stdio.h>
515 
516 void array_print_indent(int depth) {
517 	int i;
518 	for (i = 0; i < depth; i ++) {
519 		fprintf(stdout, "    ");
520 	}
521 }
522 
523 size_t array_get_max_key_length(const array * const a) {
524 	size_t maxlen = 0;
525 	for (uint32_t i = 0; i < a->used; ++i) {
526 		const buffer * const k = &a->data[i]->key;
527 		size_t len = buffer_string_length(k);
528 
529 		if (len > maxlen) {
530 			maxlen = len;
531 		}
532 	}
533 	return maxlen;
534 }
535 
536 int array_print(const array * const a, int depth) {
537 	uint32_t i;
538 	size_t maxlen;
539 	int oneline = 1;
540 
541 	if (a->used > 5) {
542 		oneline = 0;
543 	}
544 	for (i = 0; i < a->used && oneline; i++) {
545 		data_unset *du = a->data[i];
546 		if (!buffer_is_empty(&du->key)) {
547 			oneline = 0;
548 			break;
549 		}
550 		switch (du->type) {
551 			case TYPE_INTEGER:
552 			case TYPE_STRING:
553 				break;
554 			default:
555 				oneline = 0;
556 				break;
557 		}
558 	}
559 	if (oneline) {
560 		fprintf(stdout, "(");
561 		for (i = 0; i < a->used; i++) {
562 			data_unset *du = a->data[i];
563 			if (i != 0) {
564 				fprintf(stdout, ", ");
565 			}
566 			du->fn->print(du, depth + 1);
567 		}
568 		fprintf(stdout, ")");
569 		return 0;
570 	}
571 
572 	maxlen = array_get_max_key_length(a);
573 	fprintf(stdout, "(\n");
574 	for (i = 0; i < a->used; i++) {
575 		data_unset *du = a->data[i];
576 		array_print_indent(depth + 1);
577 		if (!buffer_is_empty(&du->key)) {
578 			int j;
579 
580 			if (i && (i % 5) == 0) {
581 				fprintf(stdout, "# %u\n", i);
582 				array_print_indent(depth + 1);
583 			}
584 			fprintf(stdout, "\"%s\"", du->key.ptr);
585 			for (j = maxlen - buffer_string_length(&du->key); j > 0; j--) {
586 				fprintf(stdout, " ");
587 			}
588 			fprintf(stdout, " => ");
589 		}
590 		du->fn->print(du, depth + 1);
591 		fprintf(stdout, ",\n");
592 	}
593 	if (!(i && (i - 1 % 5) == 0)) {
594 		array_print_indent(depth + 1);
595 		fprintf(stdout, "# %u\n", i);
596 	}
597 	array_print_indent(depth);
598 	fprintf(stdout, ")");
599 
600 	return 0;
601 }
602