13 #define ARRAY_NOT_FOUND ((size_t)(-1))
15 array
*array_init(void) {
18 a
= calloc(1, sizeof(*a
));
24 array
*array_init_array(array
*src
) {
26 array
*a
= array_init();
28 if (0 == src
->size
) return a
;
32 a
->unique_ndx
= src
->unique_ndx
;
34 a
->data
= malloc(sizeof(*src
->data
) * src
->size
);
35 force_assert(NULL
!= a
->data
);
36 for (i
= 0; i
< src
->size
; i
++) {
37 if (src
->data
[i
]) a
->data
[i
] = src
->data
[i
]->fn
->copy(src
->data
[i
]);
38 else a
->data
[i
] = NULL
;
41 a
->sorted
= malloc(sizeof(*src
->sorted
) * src
->size
);
42 force_assert(NULL
!= a
->sorted
);
43 memcpy(a
->sorted
, src
->sorted
, sizeof(*src
->sorted
) * src
->size
);
47 void array_free(array
*a
) {
51 for (i
= 0; i
< a
->size
; i
++) {
52 if (a
->data
[i
]) a
->data
[i
]->fn
->free(a
->data
[i
]);
55 if (a
->data
) free(a
->data
);
56 if (a
->sorted
) free(a
->sorted
);
61 void array_reset(array
*a
) {
65 for (i
= 0; i
< a
->used
; i
++) {
66 a
->data
[i
]->fn
->reset(a
->data
[i
]);
67 a
->data
[i
]->is_index_key
= 0;
74 void array_reset_data_strings(array
*a
) {
77 for (size_t i
= 0; i
< a
->used
; ++i
) {
78 data_string
* const ds
= (data_string
*)a
->data
[i
];
79 /*force_assert(ds->type == TYPE_STRING);*/
81 buffer_reset(ds
->key
);
82 buffer_reset(ds
->value
);
89 data_unset
*array_pop(array
*a
) {
92 force_assert(a
->used
!= 0);
95 du
= a
->data
[a
->used
];
96 force_assert(a
->sorted
[a
->used
] == a
->used
); /* only works on "simple" lists */
97 a
->data
[a
->used
] = NULL
;
102 static int array_keycmp(const char *a
, size_t alen
, const char *b
, size_t blen
) {
103 return alen
< blen
? -1 : alen
> blen
? 1 : buffer_caseless_compare(a
, alen
, b
, blen
);
106 /* returns index of element or ARRAY_NOT_FOUND
107 * if rndx != NULL it stores the position in a->sorted[] where the key needs
110 static size_t array_get_index(const array
*a
, const char *key
, size_t keylen
, size_t *rndx
) {
111 /* invariant: [lower-1] < key < [upper]
112 * "virtual elements": [-1] = -INFTY, [a->used] = +INFTY
113 * also an invariant: 0 <= lower <= upper <= a->used
115 size_t lower
= 0, upper
= a
->used
;
116 force_assert(upper
<= SSIZE_MAX
); /* (lower + upper) can't overflow */
118 while (lower
!= upper
) {
119 size_t probe
= (lower
+ upper
) / 2;
120 const buffer
*b
= a
->data
[a
->sorted
[probe
]]->key
;
121 int cmp
= array_keycmp(key
, keylen
, CONST_BUF_LEN(b
));
125 if (rndx
) *rndx
= probe
;
126 return a
->sorted
[probe
];
127 } else if (cmp
< 0) {
129 upper
= probe
; /* still: lower <= upper */
132 lower
= probe
+ 1; /* still: lower <= upper */
136 /* not found: [lower-1] < key < [upper] = [lower] ==> insert at [lower] */
137 if (rndx
) *rndx
= lower
;
138 return ARRAY_NOT_FOUND
;
141 data_unset
*array_get_element_klen(const array
*a
, const char *key
, size_t klen
) {
143 force_assert(NULL
!= key
);
145 if (ARRAY_NOT_FOUND
!= (ndx
= array_get_index(a
, key
, klen
, NULL
))) {
146 /* found, return it */
153 data_unset
*array_extract_element_klen(array
*a
, const char *key
, size_t klen
) {
155 force_assert(NULL
!= key
);
157 if (ARRAY_NOT_FOUND
!= (ndx
= array_get_index(a
, key
, klen
, &pos
))) {
159 const size_t last_ndx
= a
->used
- 1;
160 data_unset
*entry
= a
->data
[ndx
];
162 /* now we need to swap it with the last element (if it isn't already the last element) */
163 if (ndx
!= last_ndx
) {
164 /* to swap we also need to modify the index in a->sorted - find pos of last_elem there */
165 size_t last_elem_pos
;
166 /* last element must be present at the expected position */
167 force_assert(last_ndx
== array_get_index(a
, CONST_BUF_LEN(a
->data
[last_ndx
]->key
), &last_elem_pos
));
169 /* move entry from last_ndx to ndx */
170 a
->data
[ndx
] = a
->data
[last_ndx
];
171 a
->data
[last_ndx
] = NULL
;
173 /* fix index entry for moved entry */
174 a
->sorted
[last_elem_pos
] = ndx
;
179 /* remove entry in a->sorted: move everything after pos one step to the left */
180 if (pos
!= last_ndx
) {
181 memmove(a
->sorted
+ pos
, a
->sorted
+ pos
+ 1, (last_ndx
- pos
) * sizeof(*a
->sorted
));
183 a
->sorted
[last_ndx
] = ARRAY_NOT_FOUND
;
192 static data_unset
*array_get_unused_element(array
*a
, data_type_t t
) {
193 data_unset
*ds
= NULL
;
196 for (i
= a
->used
; i
< a
->size
; i
++) {
197 if (a
->data
[i
] && a
->data
[i
]->type
== t
) {
200 /* make empty slot at a->used for next insert */
201 a
->data
[i
] = a
->data
[a
->used
];
202 a
->data
[a
->used
] = NULL
;
211 void array_set_key_value(array
*hdrs
, const char *key
, size_t key_len
, const char *value
, size_t val_len
) {
214 if (NULL
!= (ds
= (data_string
*)array_get_element_klen(hdrs
, key
, key_len
))) {
215 buffer_copy_string_len(ds
->value
, value
, val_len
);
219 array_insert_key_value(hdrs
, key
, key_len
, value
, val_len
);
222 void array_insert_key_value(array
*hdrs
, const char *key
, size_t key_len
, const char *value
, size_t val_len
) {
225 if (NULL
== (ds
= (data_string
*)array_get_unused_element(hdrs
, TYPE_STRING
))) {
226 ds
= data_string_init();
229 buffer_copy_string_len(ds
->key
, key
, key_len
);
230 buffer_copy_string_len(ds
->value
, value
, val_len
);
231 array_insert_unique(hdrs
, (data_unset
*)ds
);
234 void array_insert_value(array
*hdrs
, const char *value
, size_t val_len
) {
237 if (NULL
== (ds
= (data_string
*)array_get_unused_element(hdrs
, TYPE_STRING
))) {
238 ds
= data_string_init();
241 buffer_copy_string_len(ds
->value
, value
, val_len
);
242 array_insert_unique(hdrs
, (data_unset
*)ds
);
245 int * array_get_int_ptr(array
*a
, const char *k
, size_t klen
) {
246 data_integer
*di
= (data_integer
*)array_get_element_klen(a
, k
, klen
);
249 di
= (data_integer
*)array_get_unused_element(a
, TYPE_INTEGER
);
250 if (NULL
== di
) di
= data_integer_init();
251 buffer_copy_string_len(di
->key
, k
, klen
);
252 array_insert_unique(a
, (data_unset
*)di
);
258 /* if entry already exists return pointer to existing entry, otherwise insert entry and return NULL */
259 static data_unset
**array_find_or_insert(array
*a
, data_unset
*entry
) {
262 /* generate unique index if neccesary */
263 if (buffer_is_empty(entry
->key
) || entry
->is_index_key
) {
264 buffer_copy_int(entry
->key
, a
->unique_ndx
++);
265 entry
->is_index_key
= 1;
266 force_assert(0 != a
->unique_ndx
); /* must not wrap or we'll get problems */
269 /* try to find the entry */
270 if (ARRAY_NOT_FOUND
!= (ndx
= array_get_index(a
, CONST_BUF_LEN(entry
->key
), &pos
))) {
271 /* found collision, return it */
272 return &a
->data
[ndx
];
277 /* there couldn't possibly be enough memory to store so many entries */
278 force_assert(a
->used
+ 1 <= SSIZE_MAX
);
280 if (a
->size
== a
->used
) {
282 a
->data
= realloc(a
->data
, sizeof(*a
->data
) * a
->size
);
283 a
->sorted
= realloc(a
->sorted
, sizeof(*a
->sorted
) * a
->size
);
284 force_assert(a
->data
);
285 force_assert(a
->sorted
);
286 for (j
= a
->used
; j
< a
->size
; j
++) a
->data
[j
] = NULL
;
291 /* make sure there is nothing here */
292 if (a
->data
[ndx
]) a
->data
[ndx
]->fn
->free(a
->data
[ndx
]);
294 a
->data
[a
->used
++] = entry
;
296 /* move everything one step to the right */
298 memmove(a
->sorted
+ (pos
+ 1), a
->sorted
+ (pos
), (ndx
- pos
) * sizeof(*a
->sorted
));
302 a
->sorted
[pos
] = ndx
;
307 /* replace or insert data (free existing entry) */
308 void array_replace(array
*a
, data_unset
*entry
) {
311 force_assert(NULL
!= entry
);
312 if (NULL
!= (old
= array_find_or_insert(a
, entry
))) {
313 force_assert(*old
!= entry
);
314 (*old
)->fn
->free(*old
);
319 void array_insert_unique(array
*a
, data_unset
*entry
) {
322 force_assert(NULL
!= entry
);
323 if (NULL
!= (old
= array_find_or_insert(a
, entry
))) {
324 force_assert((*old
)->type
== entry
->type
);
325 entry
->fn
->insert_dup(*old
, entry
);
329 int array_is_vlist(array
*a
) {
330 for (size_t i
= 0; i
< a
->used
; ++i
) {
331 data_unset
*du
= a
->data
[i
];
332 if (!du
->is_index_key
|| du
->type
!= TYPE_STRING
) return 0;
337 int array_is_kvany(array
*a
) {
338 for (size_t i
= 0; i
< a
->used
; ++i
) {
339 data_unset
*du
= a
->data
[i
];
340 if (du
->is_index_key
) return 0;
345 int array_is_kvarray(array
*a
) {
346 for (size_t i
= 0; i
< a
->used
; ++i
) {
347 data_unset
*du
= a
->data
[i
];
348 if (du
->is_index_key
|| du
->type
!= TYPE_ARRAY
) return 0;
353 int array_is_kvstring(array
*a
) {
354 for (size_t i
= 0; i
< a
->used
; ++i
) {
355 data_unset
*du
= a
->data
[i
];
356 if (du
->is_index_key
|| du
->type
!= TYPE_STRING
) return 0;
361 /* array_match_*() routines follow very similar pattern, but operate on slightly
362 * different data: array key/value, prefix/suffix match, case-insensitive or not
363 * While these could be combined into fewer routines with flags to modify the
364 * behavior, the interface distinctions are useful to add clarity to the code,
365 * and the specialized routines run slightly faster */
368 array_match_key_prefix_klen (const array
* const a
, const char * const s
, const size_t slen
)
370 for (size_t i
= 0; i
< a
->used
; ++i
) {
371 const buffer
* const key
= a
->data
[i
]->key
;
372 const size_t klen
= buffer_string_length(key
);
373 if (klen
<= slen
&& 0 == memcmp(s
, key
->ptr
, klen
))
380 array_match_key_prefix_nc_klen (const array
* const a
, const char * const s
, const size_t slen
)
382 for (size_t i
= 0; i
< a
->used
; ++i
) {
383 const buffer
* const key
= a
->data
[i
]->key
;
384 const size_t klen
= buffer_string_length(key
);
385 if (klen
<= slen
&& 0 == strncasecmp(s
, key
->ptr
, klen
))
392 array_match_key_prefix (const array
* const a
, const buffer
* const b
)
394 return array_match_key_prefix_klen(a
, CONST_BUF_LEN(b
));
398 array_match_key_prefix_nc (const array
* const a
, const buffer
* const b
)
400 return array_match_key_prefix_nc_klen(a
, CONST_BUF_LEN(b
));
404 array_match_value_prefix (const array
* const a
, const buffer
* const b
)
406 const size_t blen
= buffer_string_length(b
);
408 for (size_t i
= 0; i
< a
->used
; ++i
) {
409 const buffer
* const value
= ((data_string
*)a
->data
[i
])->value
;
410 const size_t vlen
= buffer_string_length(value
);
411 if (vlen
<= blen
&& 0 == memcmp(b
->ptr
, value
->ptr
, vlen
))
418 array_match_value_prefix_nc (const array
* const a
, const buffer
* const b
)
420 const size_t blen
= buffer_string_length(b
);
422 for (size_t i
= 0; i
< a
->used
; ++i
) {
423 const buffer
* const value
= ((data_string
*)a
->data
[i
])->value
;
424 const size_t vlen
= buffer_string_length(value
);
425 if (vlen
<= blen
&& 0 == strncasecmp(b
->ptr
, value
->ptr
, vlen
))
432 array_match_key_suffix (const array
* const a
, const buffer
* const b
)
434 const size_t blen
= buffer_string_length(b
);
435 const char * const end
= b
->ptr
+ blen
;
437 for (size_t i
= 0; i
< a
->used
; ++i
) {
438 const buffer
* const key
= a
->data
[i
]->key
;
439 const size_t klen
= buffer_string_length(key
);
440 if (klen
<= blen
&& 0 == memcmp(end
- klen
, key
->ptr
, klen
))
447 array_match_key_suffix_nc (const array
* const a
, const buffer
* const b
)
449 const size_t blen
= buffer_string_length(b
);
450 const char * const end
= b
->ptr
+ blen
;
452 for (size_t i
= 0; i
< a
->used
; ++i
) {
453 const buffer
* const key
= a
->data
[i
]->key
;
454 const size_t klen
= buffer_string_length(key
);
455 if (klen
<= blen
&& 0 == strncasecmp(end
- klen
, key
->ptr
, klen
))
462 array_match_value_suffix (const array
* const a
, const buffer
* const b
)
464 const size_t blen
= buffer_string_length(b
);
465 const char * const end
= b
->ptr
+ blen
;
467 for (size_t i
= 0; i
< a
->used
; ++i
) {
468 const buffer
* const value
= ((data_string
*)a
->data
[i
])->value
;
469 const size_t vlen
= buffer_string_length(value
);
470 if (vlen
<= blen
&& 0 == memcmp(end
- vlen
, value
->ptr
, vlen
))
477 array_match_value_suffix_nc (const array
* const a
, const buffer
* const b
)
479 const size_t blen
= buffer_string_length(b
);
480 const char * const end
= b
->ptr
+ blen
;
482 for (size_t i
= 0; i
< a
->used
; ++i
) {
483 const buffer
* const value
= ((data_string
*)a
->data
[i
])->value
;
484 const size_t vlen
= buffer_string_length(value
);
485 if (vlen
<= blen
&& 0 == strncasecmp(end
- vlen
, value
->ptr
, vlen
))
492 array_match_path_or_ext (const array
* const a
, const buffer
* const b
)
494 const size_t blen
= buffer_string_length(b
);
496 for (size_t i
= 0; i
< a
->used
; ++i
) {
497 /* check extension in the form "^/path" or ".ext$" */
498 const buffer
* const key
= a
->data
[i
]->key
;
499 const size_t klen
= buffer_string_length(key
);
501 && 0 == memcmp((*(key
->ptr
) == '/' ? b
->ptr
: b
->ptr
+ blen
- klen
),
514 void array_print_indent(int depth
) {
516 for (i
= 0; i
< depth
; i
++) {
517 fprintf(stdout
, " ");
521 size_t array_get_max_key_length(array
*a
) {
525 for (i
= 0; i
< a
->used
; i
++) {
526 data_unset
*du
= a
->data
[i
];
527 size_t len
= buffer_string_length(du
->key
);
536 int array_print(array
*a
, int depth
) {
544 for (i
= 0; i
< a
->used
&& oneline
; i
++) {
545 data_unset
*du
= a
->data
[i
];
546 if (!du
->is_index_key
) {
560 fprintf(stdout
, "(");
561 for (i
= 0; i
< a
->used
; i
++) {
562 data_unset
*du
= a
->data
[i
];
564 fprintf(stdout
, ", ");
566 du
->fn
->print(du
, depth
+ 1);
568 fprintf(stdout
, ")");
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 (!du
->is_index_key
) {
580 if (i
&& (i
% 5) == 0) {
581 fprintf(stdout
, "# %zu\n", i
);
582 array_print_indent(depth
+ 1);
584 fprintf(stdout
, "\"%s\"", du
->key
->ptr
);
585 for (j
= maxlen
- buffer_string_length(du
->key
); j
> 0; j
--) {
586 fprintf(stdout
, " ");
588 fprintf(stdout
, " => ");
590 du
->fn
->print(du
, depth
+ 1);
591 fprintf(stdout
, ",\n");
593 if (!(i
&& (i
- 1 % 5) == 0)) {
594 array_print_indent(depth
+ 1);
595 fprintf(stdout
, "# %zu\n", i
);
597 array_print_indent(depth
);
598 fprintf(stdout
, ")");