Port over ht.h improvements from Libevent.

There is a facility (not used now in Tor) to avoid storing the hash
of a given type if it is a fast-to-calculate hash.

There are also a few ancient-openbsd compilation issues fixed here.

The fact that Tor says INLINE while Libevent says inline remains
unaddressed.

1 files changed, 36 insertions, 18 deletions

diff --git a/src/common/ht.h b/src/common/ht.h
index 3f374b491..12977cbb7 100644
--- a/src/common/ht.h
+++ b/src/common/ht.h
@@ -25,19 +25,22 @@
 #define HT_INITIALIZER()                        \
   { NULL, 0, 0, 0, -1 }
 
+#ifdef HT_NO_CACHE_HASH_VALUES
+#define HT_ENTRY(type)                          \
+  struct {                                      \
+    struct type *hte_next;                      \
+  }
+#else
 #define HT_ENTRY(type)                          \
   struct {                                      \
     struct type *hte_next;                      \
     unsigned hte_hash;                          \
   }
+#endif
 
 #define HT_EMPTY(head)                          \
   ((head)->hth_n_entries == 0)
 
-/* Helper: alias for the bucket containing 'elm'. */
-#define _HT_BUCKET(head, field, elm)                                    \
-  ((head)->hth_table[elm->field.hte_hash % head->hth_table_length])
-
 /* How many elements in 'head'? */
 #define HT_SIZE(head)                           \
   ((head)->hth_n_entries)
@@ -98,8 +101,25 @@ ht_string_hash(const char *s)
   return h;
 }
 
+#ifndef HT_NO_CACHE_HASH_VALUES
 #define _HT_SET_HASH(elm, field, hashfn)        \
-    (elm)->field.hte_hash = hashfn(elm)
+	do { (elm)->field.hte_hash = hashfn(elm); } while (0)
+#define _HT_SET_HASHVAL(elm, field, val)	\
+	do { (elm)->field.hte_hash = (val); } while (0)
+#define _HT_ELT_HASH(elm, field, hashfn)	\
+	((elm)->field.hte_hash)
+#else
+#define _HT_SET_HASH(elm, field, hashfn)	\
+	((void)0)
+#define _HT_ELT_HASH(elm, field, hashfn)	\
+	(hashfn(elm))
+#define _HT_SET_HASHVAL(elm, field, val)	\
+        ((void)0)
+#endif
+
+/* Helper: alias for the bucket containing 'elm'. */
+#define _HT_BUCKET(head, field, elm, hashfn)				\
+	((head)->hth_table[_HT_ELT_HASH(elm,field,hashfn) % head->hth_table_length])
 
 #define HT_FOREACH(x, name, head)                 \
   for ((x) = HT_START(name, head);                \
@@ -126,7 +146,7 @@ ht_string_hash(const char *s)
     struct type **p;                                                    \
     if (!head->hth_table)                                               \
       return NULL;                                                      \
-    p = &_HT_BUCKET(head, field, elm);                                  \
+    p = &_HT_BUCKET(head, field, elm, hashfn);				\
     while (*p) {                                                        \
       if (eqfn(*p, elm))                                                \
         return p;                                                       \
@@ -155,7 +175,7 @@ ht_string_hash(const char *s)
       name##_HT_GROW(head, head->hth_n_entries+1);                      \
     ++head->hth_n_entries;                                              \
     _HT_SET_HASH(elm, field, hashfn);                                   \
-    p = &_HT_BUCKET(head, field, elm);                                  \
+    p = &_HT_BUCKET(head, field, elm, hashfn);				\
     elm->field.hte_next = *p;                                           \
     *p = elm;                                                           \
   }                                                                     \
@@ -207,7 +227,6 @@ ht_string_hash(const char *s)
                        void *data)                                      \
   {                                                                     \
     unsigned idx;                                                       \
-    int remove;                                                         \
     struct type **p, **nextp, *next;                                    \
     if (!head->hth_table)                                               \
       return;                                                           \
@@ -216,8 +235,7 @@ ht_string_hash(const char *s)
       while (*p) {                                                      \
         nextp = &(*p)->field.hte_next;                                  \
         next = *nextp;                                                  \
-        remove = fn(*p, data);                                          \
-        if (remove) {                                                   \
+        if (fn(*p, data)) {                                             \
           --head->hth_n_entries;                                        \
           *p = next;                                                    \
         } else {                                                        \
@@ -251,7 +269,7 @@ ht_string_hash(const char *s)
     if ((*elm)->field.hte_next) {                                       \
       return &(*elm)->field.hte_next;                                   \
     } else {                                                            \
-      unsigned b = ((*elm)->field.hte_hash % head->hth_table_length)+1; \
+      unsigned b = (_HT_ELT_HASH(*elm, field, hashfn) % head->hth_table_length)+1; \
       while (b < head->hth_table_length) {                              \
         if (head->hth_table[b])                                         \
           return &head->hth_table[b];                                   \
@@ -263,7 +281,7 @@ ht_string_hash(const char *s)
   static INLINE struct type **                                          \
   name##_HT_NEXT_RMV(struct name *head, struct type **elm)              \
   {                                                                     \
-    unsigned h = (*elm)->field.hte_hash;                                \
+    unsigned h = _HT_ELT_HASH(*elm, field, hashfn);		        \
     *elm = (*elm)->field.hte_next;                                      \
     --head->hth_n_entries;                                              \
     if (*elm) {                                                         \
@@ -320,7 +338,7 @@ ht_string_hash(const char *s)
         elm = head->hth_table[b];                                       \
         while (elm) {                                                   \
           next = elm->field.hte_next;                                   \
-          b2 = elm->field.hte_hash % new_len;                           \
+          b2 = _HT_ELT_HASH(elm, field, hashfn) % new_len;              \
           elm->field.hte_next = new_table[b2];                          \
           new_table[b2] = elm;                                          \
           elm = next;                                                   \
@@ -338,7 +356,7 @@ ht_string_hash(const char *s)
       for (b=0; b < head->hth_table_length; ++b) {                      \
         struct type *e, **pE;                                           \
         for (pE = &new_table[b], e = *pE; e != NULL; e = *pE) {         \
-          b2 = e->field.hte_hash % new_len;                             \
+          b2 = _HT_ELT_HASH(e, field, hashfn) % new_len;                \
           if (b2 == b) {                                                \
             pE = &e->field.hte_next;                                    \
           } else {                                                      \
@@ -390,9 +408,9 @@ ht_string_hash(const char *s)
       return 5;                                                         \
     for (n = i = 0; i < head->hth_table_length; ++i) {                  \
       for (elm = head->hth_table[i]; elm; elm = elm->field.hte_next) {  \
-        if (elm->field.hte_hash != hashfn(elm))                         \
+        if (_HT_ELT_HASH(elm, field, hashfn) != hashfn(elm))	        \
           return 1000 + i;                                              \
-        if ((elm->field.hte_hash % head->hth_table_length) != i)        \
+        if ((_HT_ELT_HASH(elm, field, hashfn) % head->hth_table_length) != i) \
           return 10000 + i;                                             \
         ++n;                                                            \
       }                                                                 \
@@ -408,7 +426,7 @@ ht_string_hash(const char *s)
 #define _HT_FIND_OR_INSERT(name, field, hashfn, head, eltype, elm, var, y, n) \
   {                                                                     \
     struct name *_##var##_head = head;                                  \
-    eltype **var;                                                       \
+    struct eltype **var;												\
     if (!_##var##_head->hth_table ||                                    \
         _##var##_head->hth_n_entries >= _##var##_head->hth_load_limit)  \
       name##_HT_GROW(_##var##_head, _##var##_head->hth_n_entries+1);     \
@@ -422,7 +440,7 @@ ht_string_hash(const char *s)
   }
 #define _HT_FOI_INSERT(field, head, elm, newent, var)       \
   {                                                         \
-    newent->field.hte_hash = (elm)->field.hte_hash;         \
+    _HT_SET_HASHVAL(newent, field, (elm)->field.hte_hash);  \
     newent->field.hte_next = NULL;                          \
     *var = newent;                                          \
     ++((head)->hth_n_entries);                              \