From 1347022e3863deb97d670d63d48c937f12a9abd1 Mon Sep 17 00:00:00 2001 From: Vsevolod Stakhov Date: Sun, 22 Aug 2021 18:23:31 +0100 Subject: [PATCH] [Fix] Libucl: Fix deletion from ucl objects --- contrib/libucl/ucl_hash.c | 96 ++++++++++++++------------------------- 1 file changed, 35 insertions(+), 61 deletions(-) diff --git a/contrib/libucl/ucl_hash.c b/contrib/libucl/ucl_hash.c index dbd19c928..e67d682b6 100644 --- a/contrib/libucl/ucl_hash.c +++ b/contrib/libucl/ucl_hash.c @@ -24,7 +24,7 @@ #include "ucl_internal.h" #include "ucl_hash.h" #include "khash.h" -#include "kvec.h" +#include "utlist.h" #include "cryptobox.h" #include "libutil/str_util.h" @@ -35,12 +35,12 @@ struct ucl_hash_elt { const ucl_object_t *obj; - size_t ar_idx; + struct ucl_hash_elt *prev, *next; }; struct ucl_hash_struct { void *hash; - kvec_t(const ucl_object_t *) ar; + struct ucl_hash_elt *head; bool caseless; }; @@ -48,7 +48,6 @@ static uint64_t ucl_hash_seed (void) { static uint64_t seed; - if (seed == 0) { #ifdef UCL_RANDOM_FUNCTION seed = UCL_RANDOM_FUNCTION; @@ -149,8 +148,7 @@ ucl_hash_create (bool ignore_case) new = UCL_ALLOC (sizeof (ucl_hash_t)); if (new != NULL) { void *h; - kv_init (new->ar); - + new->head = NULL; new->caseless = ignore_case; if (ignore_case) { h = (void *)kh_init (ucl_hash_caseless_node); @@ -204,7 +202,6 @@ void ucl_hash_destroy (ucl_hash_t* hashlin, ucl_hash_free_func func) kh_destroy (ucl_hash_node, h); } - kv_destroy (hashlin->ar); UCL_FREE (sizeof (*hashlin), hashlin); } @@ -226,9 +223,8 @@ ucl_hash_insert (ucl_hash_t* hashlin, const ucl_object_t *obj, k = kh_put (ucl_hash_caseless_node, h, obj, &ret); if (ret > 0) { elt = &kh_value (h, k); - kv_push_safe (const ucl_object_t *, hashlin->ar, obj, e0); + DL_APPEND(hashlin->head, elt); elt->obj = obj; - elt->ar_idx = kv_size (hashlin->ar) - 1; } } else { @@ -237,9 +233,8 @@ ucl_hash_insert (ucl_hash_t* hashlin, const ucl_object_t *obj, k = kh_put (ucl_hash_node, h, obj, &ret); if (ret > 0) { elt = &kh_value (h, k); - kv_push_safe (const ucl_object_t *, hashlin->ar, obj, e0); + DL_APPEND(hashlin->head, elt); elt->obj = obj; - elt->ar_idx = kv_size (hashlin->ar) - 1; } else if (ret < 0) { goto e0; } @@ -270,8 +265,7 @@ void ucl_hash_replace (ucl_hash_t* hashlin, const ucl_object_t *old, k = kh_put (ucl_hash_caseless_node, h, new, &ret); pelt = &kh_value (h, k); pelt->obj = new; - pelt->ar_idx = elt.ar_idx; - kv_A (hashlin->ar, elt.ar_idx) = new; + DL_REPLACE_ELEM(hashlin->head, &elt, pelt); } } else { @@ -284,15 +278,13 @@ void ucl_hash_replace (ucl_hash_t* hashlin, const ucl_object_t *old, k = kh_put (ucl_hash_node, h, new, &ret); pelt = &kh_value (h, k); pelt->obj = new; - pelt->ar_idx = elt.ar_idx; - kv_A (hashlin->ar, elt.ar_idx) = new; + DL_REPLACE_ELEM(hashlin->head, &elt, pelt); } } } struct ucl_hash_real_iter { - const ucl_object_t **cur; - const ucl_object_t **end; + const struct ucl_hash_elt *cur; }; #define UHI_SETERR(ep, ern) {if (ep != NULL) *ep = (ern);} @@ -316,13 +308,13 @@ ucl_hash_iterate2 (ucl_hash_t *hashlin, ucl_hash_iter_t *iter, int *ep) return NULL; } - it->cur = &hashlin->ar.a[0]; - it->end = it->cur + hashlin->ar.n; + it->cur = hashlin->head; } UHI_SETERR(ep, 0); - if (it->cur < it->end) { - ret = *it->cur++; + if (it->cur) { + ret = it->cur->obj; + it->cur = it->cur->next; } else { UCL_FREE (sizeof (*it), it); @@ -340,7 +332,7 @@ ucl_hash_iter_has_next (ucl_hash_t *hashlin, ucl_hash_iter_t iter) { struct ucl_hash_real_iter *it = (struct ucl_hash_real_iter *)(iter); - return it->cur < it->end - 1; + return it->cur != NULL; } @@ -387,7 +379,6 @@ ucl_hash_delete (ucl_hash_t* hashlin, const ucl_object_t *obj) { khiter_t k; struct ucl_hash_elt *elt; - size_t i; if (hashlin == NULL) { return; @@ -400,15 +391,8 @@ ucl_hash_delete (ucl_hash_t* hashlin, const ucl_object_t *obj) k = kh_get (ucl_hash_caseless_node, h, obj); if (k != kh_end (h)) { elt = &kh_value (h, k); - i = elt->ar_idx; - kv_del (const ucl_object_t *, hashlin->ar, elt->ar_idx); + DL_DELETE(hashlin->head, elt); kh_del (ucl_hash_caseless_node, h, k); - - /* Update subsequent elts */ - for (; i < hashlin->ar.n; i ++) { - elt = &kh_value (h, i); - elt->ar_idx --; - } } } else { @@ -417,15 +401,8 @@ ucl_hash_delete (ucl_hash_t* hashlin, const ucl_object_t *obj) k = kh_get (ucl_hash_node, h, obj); if (k != kh_end (h)) { elt = &kh_value (h, k); - i = elt->ar_idx; - kv_del (const ucl_object_t *, hashlin->ar, elt->ar_idx); + DL_DELETE(hashlin->head, elt); kh_del (ucl_hash_node, h, k); - - /* Update subsequent elts */ - for (; i < hashlin->ar.n; i ++) { - elt = &kh_value (h, i); - elt->ar_idx --; - } } } } @@ -437,9 +414,7 @@ ucl_hash_reserve (ucl_hash_t *hashlin, size_t sz) return false; } - if (sz > hashlin->ar.m) { - kv_resize_safe (const ucl_object_t *, hashlin->ar, sz, e0); - + if (sz > kh_size((khash_t(ucl_hash_node) *)hashlin->hash)) { if (hashlin->caseless) { khash_t(ucl_hash_caseless_node) *h = (khash_t( ucl_hash_caseless_node) *) @@ -451,35 +426,34 @@ ucl_hash_reserve (ucl_hash_t *hashlin, size_t sz) kh_resize (ucl_hash_node, h, sz * 2); } } + return true; - e0: - return false; } static int ucl_hash_cmp_icase (const void *a, const void *b) { - const ucl_object_t *oa = *(const ucl_object_t **)a, - *ob = *(const ucl_object_t **)b; + const struct ucl_hash_elt *oa = (const struct ucl_hash_elt *)a, + *ob = (const struct ucl_hash_elt *)b; - if (oa->keylen == ob->keylen) { - return rspamd_lc_cmp (oa->key, ob->key, oa->keylen); + if (oa->obj->keylen == ob->obj->keylen) { + return rspamd_lc_cmp (oa->obj->key, ob->obj->key, oa->obj->keylen); } - return ((int)(oa->keylen)) - ob->keylen; + return ((int)(oa->obj->keylen)) - ob->obj->keylen; } static int ucl_hash_cmp_case_sens (const void *a, const void *b) { - const ucl_object_t *oa = *(const ucl_object_t **)a, - *ob = *(const ucl_object_t **)b; + const struct ucl_hash_elt *oa = (const struct ucl_hash_elt *)a, + *ob = (const struct ucl_hash_elt *)b; - if (oa->keylen == ob->keylen) { - return memcmp (oa->key, ob->key, oa->keylen); + if (oa->obj->keylen == ob->obj->keylen) { + return memcmp (oa->obj->key, ob->obj->key, oa->obj->keylen); } - return ((int)(oa->keylen)) - ob->keylen; + return ((int)(oa->obj->keylen)) - ob->obj->keylen; } void @@ -487,18 +461,18 @@ ucl_hash_sort (ucl_hash_t *hashlin, enum ucl_object_keys_sort_flags fl) { if (fl & UCL_SORT_KEYS_ICASE) { - qsort (hashlin->ar.a, hashlin->ar.n, sizeof (ucl_object_t *), - ucl_hash_cmp_icase); + DL_SORT(hashlin->head, ucl_hash_cmp_icase); } else { - qsort (hashlin->ar.a, hashlin->ar.n, sizeof (ucl_object_t *), - ucl_hash_cmp_case_sens); + DL_SORT(hashlin->head, ucl_hash_cmp_case_sens); } if (fl & UCL_SORT_KEYS_RECURSIVE) { - for (size_t i = 0; i < hashlin->ar.n; i ++) { - if (ucl_object_type (hashlin->ar.a[i]) == UCL_OBJECT) { - ucl_hash_sort (hashlin->ar.a[i]->value.ov, fl); + struct ucl_hash_elt *elt; + + DL_FOREACH(hashlin->head, elt) { + if (ucl_object_type (elt->obj) == UCL_OBJECT) { + ucl_hash_sort (elt->obj->value.ov, fl); } } } -- 2.39.5