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