X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;ds=sidebyside;f=lib%2Fhashtable.h;h=c2c3c42d0869d73052cdc299b7867f5dfb6bbf9e;hb=9f87c6fe6552ce8b2236a07307d2f825b0e4c439;hp=f96a07fd1f9aa61f685ed260619e36a1044e63ed;hpb=b23db618057b5aa8905c41df963d6fa865d82c8c;p=libucw.git

diff --git a/lib/hashtable.h b/lib/hashtable.h
index f96a07fd..c2c3c42d 100644
--- 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