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