Merge pull request #10090 from ydb-platform/mergelibs-241004-1110

Library import 241004-1110

1 files changed, 104 insertions, 71 deletions

diff --git a/contrib/libs/curl/lib/hash.c b/contrib/libs/curl/lib/hash.c
index 30f28e2352..1910ac5dc4 100644
--- a/contrib/libs/curl/lib/hash.c
+++ b/contrib/libs/curl/lib/hash.c
@@ -33,6 +33,10 @@
 /* The last #include file should be: */
 #include "memdebug.h"
 
+/* random patterns for API verification */
+#define HASHINIT 0x7017e781
+#define ITERINIT 0x5FEDCBA9
+
 static void
 hash_element_dtor(void *user, void *element)
 {
@@ -40,7 +44,10 @@ hash_element_dtor(void *user, void *element)
   struct Curl_hash_element *e = (struct Curl_hash_element *) element;
 
   if(e->ptr) {
-    h->dtor(e->ptr);
+    if(e->dtor)
+      e->dtor(e->key, e->key_len, e->ptr);
+    else
+      h->dtor(e->ptr);
     e->ptr = NULL;
   }
 
@@ -57,7 +64,7 @@ hash_element_dtor(void *user, void *element)
  */
 void
 Curl_hash_init(struct Curl_hash *h,
-               int slots,
+               size_t slots,
                hash_function hfunc,
                comp_function comparator,
                Curl_hash_dtor dtor)
@@ -74,10 +81,14 @@ Curl_hash_init(struct Curl_hash *h,
   h->dtor = dtor;
   h->size = 0;
   h->slots = slots;
+#ifdef DEBUGBUILD
+  h->init = HASHINIT;
+#endif
 }
 
 static struct Curl_hash_element *
-mk_hash_element(const void *key, size_t key_len, const void *p)
+mk_hash_element(const void *key, size_t key_len, const void *p,
+                Curl_hash_elem_dtor dtor)
 {
   /* allocate the struct plus memory after it to store the key */
   struct Curl_hash_element *he = malloc(sizeof(struct Curl_hash_element) +
@@ -87,31 +98,25 @@ mk_hash_element(const void *key, size_t key_len, const void *p)
     memcpy(he->key, key, key_len);
     he->key_len = key_len;
     he->ptr = (void *) p;
+    he->dtor = dtor;
   }
   return he;
 }
 
 #define FETCH_LIST(x,y,z) &x->table[x->hash_func(y, z, x->slots)]
 
-/* Insert the data in the hash. If there already was a match in the hash, that
- * data is replaced. This function also "lazily" allocates the table if
- * needed, as it isn't done in the _init function (anymore).
- *
- * @unittest: 1305
- * @unittest: 1602
- * @unittest: 1603
- */
-void *
-Curl_hash_add(struct Curl_hash *h, void *key, size_t key_len, void *p)
+void *Curl_hash_add2(struct Curl_hash *h, void *key, size_t key_len, void *p,
+                     Curl_hash_elem_dtor dtor)
 {
   struct Curl_hash_element  *he;
-  struct Curl_llist_element *le;
+  struct Curl_llist_node *le;
   struct Curl_llist *l;
 
   DEBUGASSERT(h);
   DEBUGASSERT(h->slots);
+  DEBUGASSERT(h->init == HASHINIT);
   if(!h->table) {
-    int i;
+    size_t i;
     h->table = malloc(h->slots * sizeof(struct Curl_llist));
     if(!h->table)
       return NULL; /* OOM */
@@ -121,18 +126,18 @@ Curl_hash_add(struct Curl_hash *h, void *key, size_t key_len, void *p)
 
   l = FETCH_LIST(h, key, key_len);
 
-  for(le = l->head; le; le = le->next) {
-    he = (struct Curl_hash_element *) le->ptr;
+  for(le = Curl_llist_head(l); le; le = Curl_node_next(le)) {
+    he = (struct Curl_hash_element *) Curl_node_elem(le);
     if(h->comp_func(he->key, he->key_len, key, key_len)) {
-      Curl_llist_remove(l, le, (void *)h);
+      Curl_node_uremove(le, (void *)h);
       --h->size;
       break;
     }
   }
 
-  he = mk_hash_element(key, key_len, p);
+  he = mk_hash_element(key, key_len, p, dtor);
   if(he) {
-    Curl_llist_insert_next(l, l->tail, he, &he->list);
+    Curl_llist_append(l, he, &he->list);
     ++h->size;
     return p; /* return the new entry */
   }
@@ -140,6 +145,20 @@ Curl_hash_add(struct Curl_hash *h, void *key, size_t key_len, void *p)
   return NULL; /* failure */
 }
 
+/* Insert the data in the hash. If there already was a match in the hash, that
+ * data is replaced. This function also "lazily" allocates the table if
+ * needed, as it is not done in the _init function (anymore).
+ *
+ * @unittest: 1305
+ * @unittest: 1602
+ * @unittest: 1603
+ */
+void *
+Curl_hash_add(struct Curl_hash *h, void *key, size_t key_len, void *p)
+{
+  return Curl_hash_add2(h, key, key_len, p, NULL);
+}
+
 /* Remove the identified hash entry.
  * Returns non-zero on failure.
  *
@@ -147,18 +166,17 @@ Curl_hash_add(struct Curl_hash *h, void *key, size_t key_len, void *p)
  */
 int Curl_hash_delete(struct Curl_hash *h, void *key, size_t key_len)
 {
-  struct Curl_llist_element *le;
-  struct Curl_llist *l;
-
   DEBUGASSERT(h);
   DEBUGASSERT(h->slots);
+  DEBUGASSERT(h->init == HASHINIT);
   if(h->table) {
-    l = FETCH_LIST(h, key, key_len);
+    struct Curl_llist_node *le;
+    struct Curl_llist *l = FETCH_LIST(h, key, key_len);
 
-    for(le = l->head; le; le = le->next) {
-      struct Curl_hash_element *he = le->ptr;
+    for(le = Curl_llist_head(l); le; le = Curl_node_next(le)) {
+      struct Curl_hash_element *he = Curl_node_elem(le);
       if(h->comp_func(he->key, he->key_len, key, key_len)) {
-        Curl_llist_remove(l, le, (void *) h);
+        Curl_node_uremove(le, (void *) h);
         --h->size;
         return 0;
       }
@@ -174,15 +192,15 @@ int Curl_hash_delete(struct Curl_hash *h, void *key, size_t key_len)
 void *
 Curl_hash_pick(struct Curl_hash *h, void *key, size_t key_len)
 {
-  struct Curl_llist_element *le;
-  struct Curl_llist *l;
-
   DEBUGASSERT(h);
+  DEBUGASSERT(h->init == HASHINIT);
   if(h->table) {
+    struct Curl_llist_node *le;
+    struct Curl_llist *l;
     DEBUGASSERT(h->slots);
     l = FETCH_LIST(h, key, key_len);
-    for(le = l->head; le; le = le->next) {
-      struct Curl_hash_element *he = le->ptr;
+    for(le = Curl_llist_head(l); le; le = Curl_node_next(le)) {
+      struct Curl_hash_element *he = Curl_node_elem(le);
       if(h->comp_func(he->key, he->key_len, key, key_len)) {
         return he->ptr;
       }
@@ -192,25 +210,6 @@ Curl_hash_pick(struct Curl_hash *h, void *key, size_t key_len)
   return NULL;
 }
 
-#if defined(DEBUGBUILD) && defined(AGGRESSIVE_TEST)
-void
-Curl_hash_apply(Curl_hash *h, void *user,
-                void (*cb)(void *user, void *ptr))
-{
-  struct Curl_llist_element  *le;
-  int                  i;
-
-  for(i = 0; i < h->slots; ++i) {
-    for(le = (h->table[i])->head;
-        le;
-        le = le->next) {
-      Curl_hash_element *el = le->ptr;
-      cb(user, el->ptr);
-    }
-  }
-}
-#endif
-
 /* Destroys all the entries in the given hash and resets its attributes,
  * prepping the given hash for [static|dynamic] deallocation.
  *
@@ -221,8 +220,9 @@ Curl_hash_apply(Curl_hash *h, void *user,
 void
 Curl_hash_destroy(struct Curl_hash *h)
 {
+  DEBUGASSERT(h->init == HASHINIT);
   if(h->table) {
-    int i;
+    size_t i;
     for(i = 0; i < h->slots; ++i) {
       Curl_llist_destroy(&h->table[i], (void *) h);
     }
@@ -242,28 +242,33 @@ Curl_hash_clean(struct Curl_hash *h)
   Curl_hash_clean_with_criterium(h, NULL, NULL);
 }
 
+size_t Curl_hash_count(struct Curl_hash *h)
+{
+  DEBUGASSERT(h->init == HASHINIT);
+  return h->size;
+}
+
 /* Cleans all entries that pass the comp function criteria. */
 void
 Curl_hash_clean_with_criterium(struct Curl_hash *h, void *user,
                                int (*comp)(void *, void *))
 {
-  struct Curl_llist_element *le;
-  struct Curl_llist_element *lnext;
-  struct Curl_llist *list;
-  int i;
+  size_t i;
 
   if(!h || !h->table)
     return;
 
+  DEBUGASSERT(h->init == HASHINIT);
   for(i = 0; i < h->slots; ++i) {
-    list = &h->table[i];
-    le = list->head; /* get first list entry */
+    struct Curl_llist *list = &h->table[i];
+    struct Curl_llist_node *le =
+      Curl_llist_head(list); /* get first list entry */
     while(le) {
-      struct Curl_hash_element *he = le->ptr;
-      lnext = le->next;
+      struct Curl_hash_element *he = Curl_node_elem(le);
+      struct Curl_llist_node *lnext = Curl_node_next(le);
       /* ask the callback function if we shall remove this entry or not */
       if(!comp || comp(user, he->ptr)) {
-        Curl_llist_remove(list, le, (void *) h);
+        Curl_node_uremove(le, (void *) h);
         --h->size; /* one less entry in the hash now */
       }
       le = lnext;
@@ -278,8 +283,9 @@ size_t Curl_hash_str(void *key, size_t key_length, size_t slots_num)
   size_t h = 5381;
 
   while(key_str < end) {
+    size_t j = (size_t)*key_str++;
     h += h << 5;
-    h ^= *key_str++;
+    h ^= j;
   }
 
   return (h % slots_num);
@@ -297,29 +303,34 @@ size_t Curl_str_key_compare(void *k1, size_t key1_len,
 void Curl_hash_start_iterate(struct Curl_hash *hash,
                              struct Curl_hash_iterator *iter)
 {
+  DEBUGASSERT(hash->init == HASHINIT);
   iter->hash = hash;
   iter->slot_index = 0;
   iter->current_element = NULL;
+#ifdef DEBUGBUILD
+  iter->init = ITERINIT;
+#endif
 }
 
 struct Curl_hash_element *
 Curl_hash_next_element(struct Curl_hash_iterator *iter)
 {
-  struct Curl_hash *h = iter->hash;
-
+  struct Curl_hash *h;
+  DEBUGASSERT(iter->init == ITERINIT);
+  h = iter->hash;
   if(!h->table)
     return NULL; /* empty hash, nothing to return */
 
   /* Get the next element in the current list, if any */
   if(iter->current_element)
-    iter->current_element = iter->current_element->next;
+    iter->current_element = Curl_node_next(iter->current_element);
 
   /* If we have reached the end of the list, find the next one */
   if(!iter->current_element) {
-    int i;
+    size_t i;
     for(i = iter->slot_index; i < h->slots; i++) {
-      if(h->table[i].head) {
-        iter->current_element = h->table[i].head;
+      if(Curl_llist_head(&h->table[i])) {
+        iter->current_element = Curl_llist_head(&h->table[i]);
         iter->slot_index = i + 1;
         break;
       }
@@ -327,7 +338,7 @@ Curl_hash_next_element(struct Curl_hash_iterator *iter)
   }
 
   if(iter->current_element) {
-    struct Curl_hash_element *he = iter->current_element->ptr;
+    struct Curl_hash_element *he = Curl_node_elem(iter->current_element);
     return he;
   }
   return NULL;
@@ -339,7 +350,7 @@ void Curl_hash_print(struct Curl_hash *h,
 {
   struct Curl_hash_iterator iter;
   struct Curl_hash_element *he;
-  int last_index = -1;
+  size_t last_index = ~0;
 
   if(!h)
     return;
@@ -352,7 +363,7 @@ void Curl_hash_print(struct Curl_hash *h,
   while(he) {
     if(iter.slot_index != last_index) {
       fprintf(stderr, "index %d:", iter.slot_index);
-      if(last_index >= 0) {
+      if(last_index != ~0) {
         fprintf(stderr, "\n");
       }
       last_index = iter.slot_index;
@@ -368,3 +379,25 @@ void Curl_hash_print(struct Curl_hash *h,
   fprintf(stderr, "\n");
 }
 #endif
+
+void Curl_hash_offt_init(struct Curl_hash *h,
+                         size_t slots,
+                         Curl_hash_dtor dtor)
+{
+  Curl_hash_init(h, slots, Curl_hash_str, Curl_str_key_compare, dtor);
+}
+
+void *Curl_hash_offt_set(struct Curl_hash *h, curl_off_t id, void *elem)
+{
+  return Curl_hash_add(h, &id, sizeof(id), elem);
+}
+
+int Curl_hash_offt_remove(struct Curl_hash *h, curl_off_t id)
+{
+  return Curl_hash_delete(h, &id, sizeof(id));
+}
+
+void *Curl_hash_offt_get(struct Curl_hash *h, curl_off_t id)
+{
+  return Curl_hash_pick(h, &id, sizeof(id));
+}