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