Fix escaping of "+" characters in outgoing parameters. (BTW: when Galeon

[libucw.git] / lib / hashtable.h

diff --git a/lib/hashtable.h b/lib/hashtable.h
index f96a07fd1f9aa61f685ed260619e36a1044e63ed..c2c3c42d0869d73052cdc299b7867f5dfb6bbf9e 100644 (file)
--- a/lib/hashtable.h
+++ b/lib/hashtable.h
@@ -2,6 +2,10 @@
  *     Sherlock Library -- Universal Hash Table
  *
  *     (c) 2002 Martin Mares <mj@ucw.cz>
+ *     (c) 2002 Robert Spalek <robert@ucw.cz>
+ *
+ *     This software may be freely distributed and used according to the terms
+ *     of the GNU Lesser General Public License.
  */
 
 /*
@@ -41,8 +45,10 @@
  *
  *  <always defined>   init() -- initialize the hash table.
  *  HASH_WANT_CLEANUP  cleanup() -- deallocate the hash table.
- *  HASH_WANT_FIND     node *find(key) -- find node with the specified
+ *  HASH_WANT_FIND     node *find(key) -- find first node with the specified
  *                     key, return NULL if no such node exists.
+ *  HASH_WANT_FIND_NEXT        node *find(node *start) -- find next node with the
+ *                     specified key, return NULL if no such node exists.
  *  HASH_WANT_NEW      node *new(key) -- create new node with given key.
  *                     Doesn't check whether it already exists.
  *  HASH_WANT_LOOKUP   node *lookup(key) -- find node with given key,
@@ -76,8 +82,7 @@
  *  ... and a couple of extra parameters:
  *
  *  HASH_NOCASE                string comparisons should be case-insensitive.
- *  HASH_DEFAULT_SIZE=n        initially, use hash table of `n' entries.
- *                     The `n' has to be a power of two.
+ *  HASH_DEFAULT_SIZE=n        initially, use hash table of approx. `n' entries.
  *  HASH_CONSERVE_SPACE        use as little space as possible.
  *  HASH_FN_BITS=n     The hash function gives only `n' significant bits.
  *  HASH_ATOMIC_TYPE=t Atomic values are of type `t' instead of int.
@@ -128,7 +133,7 @@ typedef struct P(bucket) {
 
 struct P(table) {
   uns hash_size;
-  uns hash_count, hash_max, hash_min, hash_hard_max, hash_mask;
+  uns hash_count, hash_max, hash_min, hash_hard_max;
   P(bucket) **ht;
 } P(table);
 
@@ -284,13 +289,17 @@ static inline void P(free) (void *x)
 
 static void P(alloc_table) (void)
 {
+  T.hash_size = nextprime(T.hash_size);
   T.ht = xmalloc(sizeof(void *) * T.hash_size);
   bzero(T.ht, sizeof(void *) * T.hash_size);
-  T.hash_max = T.hash_size * 2;
-  if (T.hash_max > T.hash_hard_max)
-    T.hash_max = T.hash_hard_max;
-  T.hash_min = T.hash_size / 4;
-  T.hash_mask = T.hash_size - 1;
+  if (2*T.hash_size < T.hash_hard_max)
+    T.hash_max = 2*T.hash_size;
+  else
+    T.hash_max = ~0U;
+  if (T.hash_size/2 > HASH_DEFAULT_SIZE)
+    T.hash_min = T.hash_size/4;
+  else
+    T.hash_min = 0;
 }
 
 static void P(init) (void)
@@ -349,7 +358,7 @@ static void P(rehash) (uns size)
       while (b)
        {
          nb = b->next;
-         h = P(bucket_hash)(b) & T.hash_mask;
+         h = P(bucket_hash)(b) % T.hash_size;
          b->next = newt[h];
          newt[h] = b;
          b = nb;
@@ -362,7 +371,7 @@ static void P(rehash) (uns size)
 static P(node) * P(find) (HASH_KEY_DECL)
 {
   uns h0 = P(hash) (HASH_KEY( ));
-  uns h = h0 & T.hash_mask;
+  uns h = h0 % T.hash_size;
   P(bucket) *b;
 
   for (b=T.ht[h]; b; b=b->next)
@@ -378,6 +387,27 @@ static P(node) * P(find) (HASH_KEY_DECL)
 }
 #endif
 
+#ifdef HASH_WANT_FIND_NEXT
+static P(node) * P(find_next) (P(node) *start)
+{
+#ifndef HASH_CONSERVE_SPACE
+  uns h0 = P(hash) (HASH_KEY(start->));
+#endif
+  P(bucket) *b = SKIP_BACK(P(bucket), n, start);
+
+  for (b=b->next; b; b=b->next)
+    {
+      if (
+#ifndef HASH_CONSERVE_SPACE
+         b->hash == h0 &&
+#endif
+         P(eq)(HASH_KEY(start->), HASH_KEY(b->n.)))
+       return &b->n;
+    }
+  return NULL;
+}
+#endif
+
 #ifdef HASH_WANT_NEW
 static P(node) * P(new) (HASH_KEY_DECL)
 {
@@ -385,7 +415,7 @@ static P(node) * P(new) (HASH_KEY_DECL)
   P(bucket) *b;
 
   h0 = P(hash) (HASH_KEY( ));
-  h = h0 & T.hash_mask;
+  h = h0 % T.hash_size;
   b = P(alloc) (sizeof(struct P(bucket)) + HASH_EXTRA_SIZE(HASH_KEY( )));
   b->next = T.ht[h];
   T.ht[h] = b;
@@ -404,7 +434,7 @@ static P(node) * P(new) (HASH_KEY_DECL)
 static P(node) * P(lookup) (HASH_KEY_DECL)
 {
   uns h0 = P(hash) (HASH_KEY( ));
-  uns h = h0 & T.hash_mask;
+  uns h = h0 % T.hash_size;
   P(bucket) *b;
 
   for (b=T.ht[h]; b; b=b->next)
@@ -435,7 +465,7 @@ static P(node) * P(lookup) (HASH_KEY_DECL)
 static int P(delete) (HASH_KEY_DECL)
 {
   uns h0 = P(hash) (HASH_KEY( ));
-  uns h = h0 & T.hash_mask;
+  uns h = h0 % T.hash_size;
   P(bucket) *b, **bb;
 
   for (bb=&T.ht[h]; b=*bb; bb=&b->next)
@@ -462,7 +492,7 @@ static void P(remove) (P(node) *n)
 {
   P(bucket) *x = SKIP_BACK(struct P(bucket), n, n);
   uns h0 = P(bucket_hash)(x);
-  uns h = h0 & T.hash_mask;
+  uns h = h0 % T.hash_size;
   P(bucket) *b, **bb;
 
   for (bb=&T.ht[h]; (b=*bb) && b != x; bb=&b->next)
@@ -523,6 +553,7 @@ do {                                                                                        \
 #undef HASH_WANT_CLEANUP
 #undef HASH_WANT_DELETE
 #undef HASH_WANT_FIND
+#undef HASH_WANT_FIND_NEXT
 #undef HASH_WANT_LOOKUP
 #undef HASH_WANT_NEW
 #undef HASH_WANT_REMOVE