113 static void array_extend(array * const a, uint32_t n) {  in array_extend()  argument
115     force_assert(a->size <= INT32_MAX-n);  in array_extend()
116     a->size  += n;  in array_extend()
117     a->data   = ck_realloc_u32((void**)&a->data,  a->size,0,sizeof(*a->data));  in array_extend()
118     a->sorted = ck_realloc_u32((void**)&a->sorted,a->size,0,sizeof(*a->sorted));  in array_extend()
119     memset(a->data+a->used, 0, (a->size-a->used)*sizeof(*a->data));  in array_extend()
123 	array *a = ck_calloc(1, sizeof(*a));  in array_init()  local
124 	if (n) array_extend(a, n);  in array_init()
125 	return a;  in array_init()
128 void array_free_data(array * const a) {  in array_free_data()  argument
129 	if (a->sorted) free(a->sorted);  in array_free_data()
130 	data_unset ** const data = a->data;  in array_free_data()
131 	const uint32_t sz = a->size;  in array_free_data()
136 	a->data = NULL;  in array_free_data()
137 	a->sorted = NULL;  in array_free_data()
138 	a->used = 0;  in array_free_data()
139 	a->size = 0;  in array_free_data()
152 void array_free(array * const a) {  in array_free()  argument
153 	if (!a) return;  in array_free()
154 	array_free_data(a);  in array_free()
155 	free(a);  in array_free()
158 void array_reset_data_strings(array * const a) {  in array_reset_data_strings()  argument
159 	if (!a) return;  in array_reset_data_strings()
161 	data_string ** const data = (data_string **)a->data;  in array_reset_data_strings()
162 	const uint32_t used = a->used;  in array_reset_data_strings()
163 	a->used = 0;  in array_reset_data_strings()
173 data_unset *array_pop(array * const a) {
176 	force_assert(a->used != 0);
178 	a->used --;
179 	du = a->data[a->used];
180 	force_assert(a->sorted[a->used] == du); /* only works on "simple" lists */
181 	a->data[a->used] = NULL;
188 static int array_caseless_compare(const char * const a, const char * const b, const uint32_t len) {  in array_caseless_compare()  argument
190         unsigned int ca = ((unsigned char *)a)[i];  in array_caseless_compare()
205 static int array_keycmp(const char * const a, const uint32_t alen, const char * const b, const uint…  in array_keycmp()  argument
206     return alen < blen ? -1 : alen > blen ? 1 : array_caseless_compare(a, b, blen);  in array_keycmp()
225 static int32_t array_get_index_ext(const array * const a, const int ext, const char * const k, cons…  in array_get_index_ext()  argument
229     uint_fast32_t lower = 0, upper = a->used;  in array_get_index_ext()
232         const int x = ((data_string *)a->sorted[probe])->ext;  in array_get_index_ext()
236           : array_keycmpb(k, klen, &a->sorted[probe]->key);  in array_get_index_ext()
248 data_unset *array_get_element_klen_ext(const array * const a, const int ext, const char *key, const…  in array_get_element_klen_ext()  argument
249     const int32_t ipos = array_get_index_ext(a, ext, key, klen);  in array_get_element_klen_ext()
250     return ipos >= 0 ? a->sorted[ipos] : NULL;  in array_get_element_klen_ext()
259 static int32_t array_get_index(const array * const a, const char * const k, const uint32_t klen) {  in array_get_index()  argument
263     uint_fast32_t lower = 0, upper = a->used;  in array_get_index()
266         const buffer * const b = &a->sorted[probe]->key;  in array_get_index()
284 const data_unset *array_get_element_klen(const array * const a, const char *key, const uint32_t kle…  in array_get_element_klen()  argument
285     const int32_t ipos = array_get_index(a, key, klen);  in array_get_element_klen()
286     return ipos >= 0 ? a->sorted[ipos] : NULL;  in array_get_element_klen()
290 data_unset *array_get_data_unset(const array * const a, const char *key, const uint32_t klen) {  in array_get_data_unset()  argument
291     const int32_t ipos = array_get_index(a, key, klen);  in array_get_data_unset()
292     return ipos >= 0 ? a->sorted[ipos] : NULL;  in array_get_data_unset()
295 data_unset *array_extract_element_klen(array * const a, const char *key, const uint32_t klen) {  in array_extract_element_klen()  argument
296     const int32_t ipos = array_get_index(a, key, klen);  in array_extract_element_klen()
300     data_unset * const entry = a->sorted[ipos];  in array_extract_element_klen()
301     const uint32_t last_ndx = --a->used;  in array_extract_element_klen()
303         data_unset ** const d = a->sorted + ipos;  in array_extract_element_klen()
307     if (entry != a->data[last_ndx]) {  in array_extract_element_klen()
311         while (entry != a->data[ndx]) ++ndx;  in array_extract_element_klen()
312         a->data[ndx] = a->data[last_ndx]; /* swap with last element */  in array_extract_element_klen()
314     a->data[last_ndx] = NULL;  in array_extract_element_klen()
318 static data_unset *array_get_unused_element(array * const a, const data_type_t t) {  in array_get_unused_element()  argument
323     data_unset * const du = (a->used < a->size) ? a->data[a->used] : NULL;  in array_get_unused_element()
325         a->data[a->used] = NULL;/* make empty slot at a->used for next insert */  in array_get_unused_element()
330 	data_unset ** const data = a->data;  in array_get_unused_element()
331 	for (uint32_t i = a->used, sz = a->size; i < sz; ++i) {  in array_get_unused_element()
336 			data[i] = data[a->used];  in array_get_unused_element()
337 			data[a->used] = NULL;  in array_get_unused_element()
348 static data_unset * array_insert_data_at_pos(array * const a, data_unset * const entry, const uint_…  in array_insert_data_at_pos()  argument
349     if (a->used < a->size) {  in array_insert_data_at_pos()
350         data_unset * const prev = a->data[a->used];  in array_insert_data_at_pos()
355         array_extend(a, 16);  in array_insert_data_at_pos()
358     uint_fast32_t ndx = a->used++;  in array_insert_data_at_pos()
359     a->data[ndx] = entry;  in array_insert_data_at_pos()
363     data_unset ** const d = a->sorted + pos;  in array_insert_data_at_pos()
365         memmove(d+1, d, ndx * sizeof(*a->sorted));  in array_insert_data_at_pos()
370 static data_integer * array_insert_integer_at_pos(array * const a, const uint_fast32_t pos) {  in array_insert_integer_at_pos()  argument
372     data_integer *di = (data_integer *)array_get_unused_element(a,TYPE_INTEGER);  in array_insert_integer_at_pos()
377     return (data_integer *)array_insert_data_at_pos(a, (data_unset *)di, pos);  in array_insert_integer_at_pos()
381 static data_string * array_insert_string_at_pos(array * const a, const uint_fast32_t pos) {  in array_insert_string_at_pos()  argument
382     data_string *ds = (data_string *)array_get_unused_element(a, TYPE_STRING);  in array_insert_string_at_pos()
384     return (data_string *)array_insert_data_at_pos(a, (data_unset *)ds, pos);  in array_insert_string_at_pos()
388 buffer * array_get_buf_ptr_ext(array * const a, const int ext, const char * const k, const uint32_t…  in array_get_buf_ptr_ext()  argument
389     int32_t ipos = array_get_index_ext(a, ext, k, klen);  in array_get_buf_ptr_ext()
390     if (ipos >= 0) return &((data_string *)a->sorted[ipos])->value;  in array_get_buf_ptr_ext()
392     data_string * const ds = array_insert_string_at_pos(a, (uint32_t)(-ipos-1));  in array_get_buf_ptr_ext()
399 int * array_get_int_ptr(array * const a, const char * const k, const uint32_t klen) {  in array_get_int_ptr()  argument
400     int32_t ipos = array_get_index(a, k, klen);  in array_get_int_ptr()
401     if (ipos >= 0) return &((data_integer *)a->sorted[ipos])->value;  in array_get_int_ptr()
403     data_integer * const di =array_insert_integer_at_pos(a,(uint32_t)(-ipos-1));  in array_get_int_ptr()
409 buffer * array_get_buf_ptr(array * const a, const char * const k, const uint32_t klen) {  in array_get_buf_ptr()  argument
410     int32_t ipos = array_get_index(a, k, klen);  in array_get_buf_ptr()
411     if (ipos >= 0) return &((data_string *)a->sorted[ipos])->value;  in array_get_buf_ptr()
413     data_string * const ds = array_insert_string_at_pos(a, (uint32_t)(-ipos-1));  in array_get_buf_ptr()
419 void array_insert_value(array * const a, const char * const v, const uint32_t vlen) {  in array_insert_value()  argument
420     data_string * const ds = array_insert_string_at_pos(a, a->used);  in array_insert_value()
427 static data_unset **array_find_or_insert(array * const a, data_unset * const entry) {  in array_find_or_insert()  argument
432         array_insert_data_at_pos(a, entry, a->used);  in array_find_or_insert()
437     const int32_t ipos = array_get_index(a, BUF_PTR_LEN(&entry->key));  in array_find_or_insert()
438     if (ipos >= 0) return &a->sorted[ipos];  in array_find_or_insert()
440     array_insert_data_at_pos(a, entry, (uint32_t)(-ipos - 1));  in array_find_or_insert()
445 void array_replace(array * const a, data_unset * const entry) {  in array_replace()  argument
446     if (NULL == array_find_or_insert(a, entry)) return;  in array_replace()
449     const int32_t ipos = array_get_index(a, BUF_PTR_LEN(&entry->key));  in array_replace()
451     data_unset *old = a->sorted[ipos];  in array_replace()
453     a->sorted[ipos] = entry;  in array_replace()
456     while (i < a->used && a->data[i] != old) ++i;  in array_replace()
457     force_assert(i != a->used);  in array_replace()
458     a->data[i] = entry;  in array_replace()
463 void array_insert_unique(array * const a, data_unset * const entry) {  in array_insert_unique()  argument
466 	if (NULL != (old = array_find_or_insert(a, entry))) {  in array_insert_unique()
475 int array_is_vlist(const array * const a) {  in array_is_vlist()  argument
476 	for (uint32_t i = 0; i < a->used; ++i) {  in array_is_vlist()
477 		data_unset *du = a->data[i];  in array_is_vlist()
483 int array_is_kvany(const array * const a) {  in array_is_kvany()  argument
484 	for (uint32_t i = 0; i < a->used; ++i) {  in array_is_kvany()
485 		data_unset *du = a->data[i];  in array_is_kvany()
491 int array_is_kvarray(const array * const a) {  in array_is_kvarray()  argument
492 	for (uint32_t i = 0; i < a->used; ++i) {  in array_is_kvarray()
493 		data_unset *du = a->data[i];  in array_is_kvarray()
499 int array_is_kvstring(const array * const a) {  in array_is_kvstring()  argument
500 	for (uint32_t i = 0; i < a->used; ++i) {  in array_is_kvstring()
501 		data_unset *du = a->data[i];  in array_is_kvstring()
514 array_match_key_prefix_klen (const array * const a, const char * const s, const uint32_t slen)  in array_match_key_prefix_klen()  argument
516     for (uint32_t i = 0; i < a->used; ++i) {  in array_match_key_prefix_klen()
517         const buffer * const key = &a->data[i]->key;  in array_match_key_prefix_klen()
520             return a->data[i];  in array_match_key_prefix_klen()
526 array_match_key_prefix_nc_klen (const array * const a, const char * const s, const uint32_t slen)  in array_match_key_prefix_nc_klen()  argument
528     for (uint32_t i = 0; i < a->used; ++i) {  in array_match_key_prefix_nc_klen()
529         const buffer * const key = &a->data[i]->key;  in array_match_key_prefix_nc_klen()
532             return a->data[i];  in array_match_key_prefix_nc_klen()
538 array_match_key_prefix (const array * const a, const buffer * const b)  in array_match_key_prefix()  argument
543     return array_match_key_prefix_klen(a, BUF_PTR_LEN(b));  in array_match_key_prefix()
547 array_match_key_prefix_nc (const array * const a, const buffer * const b)  in array_match_key_prefix_nc()  argument
549     return array_match_key_prefix_nc_klen(a, BUF_PTR_LEN(b));  in array_match_key_prefix_nc()
553 array_match_value_prefix (const array * const a, const buffer * const b)  in array_match_value_prefix()  argument
557     for (uint32_t i = 0; i < a->used; ++i) {  in array_match_value_prefix()
558         const buffer * const value = &((data_string *)a->data[i])->value;  in array_match_value_prefix()
567 array_match_value_prefix_nc (const array * const a, const buffer * const b)  in array_match_value_prefix_nc()  argument
571     for (uint32_t i = 0; i < a->used; ++i) {  in array_match_value_prefix_nc()
572         const buffer * const value = &((data_string *)a->data[i])->value;  in array_match_value_prefix_nc()
581 array_match_key_suffix (const array * const a, const buffer * const b)  in array_match_key_suffix()  argument
586     for (uint32_t i = 0; i < a->used; ++i) {  in array_match_key_suffix()
587         const buffer * const key = &a->data[i]->key;  in array_match_key_suffix()
590             return a->data[i];  in array_match_key_suffix()
596 array_match_key_suffix_nc (const array * const a, const buffer * const b)  in array_match_key_suffix_nc()  argument
601     for (uint32_t i = 0; i < a->used; ++i) {  in array_match_key_suffix_nc()
602         const buffer * const key = &a->data[i]->key;  in array_match_key_suffix_nc()
605             return a->data[i];  in array_match_key_suffix_nc()
611 array_match_value_suffix (const array * const a, const buffer * const b)  in array_match_value_suffix()  argument
616     for (uint32_t i = 0; i < a->used; ++i) {  in array_match_value_suffix()
617         const buffer * const value = &((data_string *)a->data[i])->value;  in array_match_value_suffix()
626 array_match_value_suffix_nc (const array * const a, const buffer * const b)  in array_match_value_suffix_nc()  argument
631     for (uint32_t i = 0; i < a->used; ++i) {  in array_match_value_suffix_nc()
632         const buffer * const value = &((data_string *)a->data[i])->value;  in array_match_value_suffix_nc()
641 array_match_path_or_ext (const array * const a, const buffer * const b)  in array_match_path_or_ext()  argument
645     for (uint32_t i = 0; i < a->used; ++i) {  in array_match_path_or_ext()
647         const buffer * const key = &a->data[i]->key;  in array_match_path_or_ext()
652             return a->data[i];  in array_match_path_or_ext()