Convert HASH to be indexable by unsigned int. (see #3905)

Convert the HASH to be usable for either string or unsigned int keys,
so that a uid hash can be added for imap.

To keep hash-usage code disruption to a minimum, this introduces new
create/insert/find/delete functions for the int hash, but keeps the
old function names for string keys.

This implementation makes the key a union.  It may have been a better
idea to introduce a whole new structure, but this way allows minimum
changes to and maximum reuse of the existing hash code.

3 files changed, 159 insertions, 34 deletions

diff --git a/hash.c b/hash.c
index 08f71717..bbe31629 100644
--- a/hash.c
+++ b/hash.c
@@ -29,9 +29,10 @@
 
 #define SOMEPRIME 149711
 
-static unsigned int hash_string (const unsigned char *s, unsigned int n)
+static unsigned int gen_string_hash (union hash_key key, unsigned int n)
 {
   unsigned int h = 0;
+  unsigned char *s = (unsigned char *)key.strkey;
 
   while (*s)
     h += (h << 7) + *s++;
@@ -40,9 +41,15 @@ static unsigned int hash_string (const unsigned char *s, unsigned int n)
   return h;
 }
 
-static unsigned int hash_case_string (const unsigned char *s, unsigned int n)
+static int cmp_string_key (union hash_key a, union hash_key b)
+{
+  return mutt_strcmp (a.strkey, b.strkey);
+}
+
+static unsigned int gen_case_string_hash (union hash_key key, unsigned int n)
 {
   unsigned int h = 0;
+  unsigned char *s = (unsigned char *)key.strkey;
 
   while (*s)
     h += (h << 7) + tolower (*s++);
@@ -51,38 +58,71 @@ static unsigned int hash_case_string (const unsigned char *s, unsigned int n)
   return h;
 }
 
-HASH *hash_create (int nelem, int lower)
+static int cmp_case_string_key (union hash_key a, union hash_key b)
+{
+  return mutt_strcasecmp (a.strkey, b.strkey);
+}
+
+static unsigned int gen_int_hash (union hash_key key, unsigned int n)
+{
+  return key.intkey % n;
+}
+
+static int cmp_int_key (union hash_key a, union hash_key b)
+{
+  if (a.intkey == b.intkey)
+    return 0;
+  if (a.intkey < b.intkey)
+    return -1;
+  return 1;
+}
+
+static HASH *new_hash (int nelem)
 {
   HASH *table = safe_malloc (sizeof (HASH));
   if (nelem == 0)
     nelem = 2;
   table->nelem = nelem;
   table->table = safe_calloc (nelem, sizeof (struct hash_elem *));
+  return table;
+}
+
+HASH *hash_create (int nelem, int lower)
+{
+  HASH *table = new_hash (nelem);
   if (lower)
   {
-    table->hash_string = hash_case_string;
-    table->cmp_string = mutt_strcasecmp;
+    table->gen_hash = gen_case_string_hash;
+    table->cmp_key = cmp_case_string_key;
   }
   else
   {
-    table->hash_string = hash_string;
-    table->cmp_string = mutt_strcmp;
+    table->gen_hash = gen_string_hash;
+    table->cmp_key = cmp_string_key;
   }
   return table;
 }
 
+HASH *int_hash_create (int nelem)
+{
+  HASH *table = new_hash (nelem);
+  table->gen_hash = gen_int_hash;
+  table->cmp_key = cmp_int_key;
+  return table;
+}
+
 /* table        hash table to update
  * key          key to hash on
  * data         data to associate with `key'
  * allow_dup    if nonzero, duplicate keys are allowed in the table 
  */
-int hash_insert (HASH * table, const char *key, void *data, int allow_dup)
+static int union_hash_insert (HASH * table, union hash_key key, void *data, int allow_dup)
 {
   struct hash_elem *ptr;
   unsigned int h;
 
   ptr = (struct hash_elem *) safe_malloc (sizeof (struct hash_elem));
-  h = table->hash_string ((unsigned char *) key, table->nelem);
+  h = table->gen_hash (key, table->nelem);
   ptr->key = key;
   ptr->data = data;
 
@@ -98,7 +138,7 @@ int hash_insert (HASH * table, const char *key, void *data, int allow_dup)
 
     for (tmp = table->table[h], last = NULL; tmp; last = tmp, tmp = tmp->next)
     {
-      r = table->cmp_string (tmp->key, key);
+      r = table->cmp_key (tmp->key, key);
       if (r == 0)
       {
 	FREE (&ptr);
@@ -116,33 +156,88 @@ int hash_insert (HASH * table, const char *key, void *data, int allow_dup)
   return h;
 }
 
-void *hash_find_hash (const HASH * table, int hash, const char *key)
+int hash_insert (HASH * table, const char *strkey, void *data, int allow_dup)
+{
+  union hash_key key;
+  key.strkey = strkey;
+  return union_hash_insert (table, key, data, allow_dup);
+}
+
+int int_hash_insert (HASH * table, unsigned int intkey, void *data, int allow_dup)
+{
+  union hash_key key;
+  key.intkey = intkey;
+  return union_hash_insert (table, key, data, allow_dup);
+}
+
+static void *union_hash_find (const HASH *table, union hash_key key)
 {
-  struct hash_elem *ptr = table->table[hash];
+  int hash;
+  struct hash_elem *ptr;
+
+  if (!table)
+    return NULL;
+
+  hash = table->gen_hash (key, table->nelem);
+  ptr = table->table[hash];
   for (; ptr; ptr = ptr->next)
   {
-    if (table->cmp_string (key, ptr->key) == 0)
+    if (table->cmp_key (key, ptr->key) == 0)
       return (ptr->data);
   }
   return NULL;
 }
 
-void hash_delete_hash (HASH * table, int hash, const char *key, const void *data,
+void *hash_find (const HASH *table, const char *strkey)
+{
+  union hash_key key;
+  key.strkey = strkey;
+  return union_hash_find (table, key);
+}
+
+void *int_hash_find (const HASH *table, unsigned int intkey)
+{
+  union hash_key key;
+  key.intkey = intkey;
+  return union_hash_find (table, key);
+}
+
+struct hash_elem *hash_find_bucket (const HASH *table, const char *strkey)
+{
+  union hash_key key;
+  int hash;
+
+  if (!table)
+    return NULL;
+
+  key.strkey = strkey;
+  hash = table->gen_hash (key, table->nelem);
+  return table->table[hash];
+}
+
+static void union_hash_delete (HASH *table, union hash_key key, const void *data,
 		       void (*destroy) (void *))
 {
-  struct hash_elem *ptr = table->table[hash];
-  struct hash_elem **last = &table->table[hash];
+  int hash;
+  struct hash_elem *ptr, **last;
+
+  if (!table)
+    return;
 
-  while (ptr) 
+  hash = table->gen_hash (key, table->nelem);
+  ptr = table->table[hash];
+  last = &table->table[hash];
+
+  while (ptr)
   {
     if ((data == ptr->data || !data)
-	&& table->cmp_string (ptr->key, key) == 0)
+	&& table->cmp_key (ptr->key, key) == 0)
     {
       *last = ptr->next;
       if (destroy)
 	destroy (ptr->data);
       FREE (&ptr);
-      
+
       ptr = *last;
     }
     else
@@ -153,15 +248,35 @@ void hash_delete_hash (HASH * table, int hash, const char *key, const void *data
   }
 }
 
+void hash_delete (HASH *table, const char *strkey, const void *data,
+                  void (*destroy) (void *))
+{
+  union hash_key key;
+  key.strkey = strkey;
+  union_hash_delete (table, key, data, destroy);
+}
+
+void int_hash_delete (HASH *table, unsigned int intkey, const void *data,
+                  void (*destroy) (void *))
+{
+  union hash_key key;
+  key.intkey = intkey;
+  union_hash_delete (table, key, data, destroy);
+}
+
 /* ptr		pointer to the hash table to be freed
  * destroy()	function to call to free the ->data member (optional) 
  */
 void hash_destroy (HASH **ptr, void (*destroy) (void *))
 {
   int i;
-  HASH *pptr = *ptr;
+  HASH *pptr;
   struct hash_elem *elem, *tmp;
 
+  if (!ptr || !*ptr)
+    return;
+
+  pptr = *ptr;
   for (i = 0 ; i < pptr->nelem; i++)
   {
     for (elem = pptr->table[i]; elem; )
diff --git a/hash.h b/hash.h
index fb77d0c1..60dc6394 100644
--- a/hash.h
+++ b/hash.h
@@ -19,9 +19,15 @@
 #ifndef _HASH_H
 #define _HASH_H
 
+union hash_key
+{
+  const char *strkey;
+  unsigned int intkey;
+};
+
 struct hash_elem
 {
-  const char *key;
+  union hash_key key;
   void *data;
   struct hash_elem *next;
 };
@@ -30,20 +36,27 @@ typedef struct
 {
   int nelem;
   struct hash_elem **table;
-  unsigned int (*hash_string)(const unsigned char *, unsigned int);
-  int (*cmp_string)(const char *, const char *);
+  unsigned int (*gen_hash)(union hash_key, unsigned int);
+  int (*cmp_key)(union hash_key, union hash_key);
 }
 HASH;
 
-#define hash_find(table, key) hash_find_hash(table, table->hash_string ((unsigned char *)key, table->nelem), key)
-
-#define hash_delete(table,key,data,destroy) hash_delete_hash(table, table->hash_string ((unsigned char *)key, table->nelem), key, data, destroy)
-
 HASH *hash_create (int nelem, int lower);
+HASH *int_hash_create (int nelem);
+
 int hash_insert (HASH * table, const char *key, void *data, int allow_dup);
-void *hash_find_hash (const HASH * table, int hash, const char *key);
-void hash_delete_hash (HASH * table, int hash, const char *key, const void *data,
-		       void (*destroy) (void *));
+int int_hash_insert (HASH *table, unsigned int key, void *data, int allow_dup);
+
+void *hash_find (const HASH *table, const char *key);
+void *int_hash_find (const HASH *table, unsigned int key);
+
+struct hash_elem *hash_find_bucket (const HASH *table, const char *key);
+
+void hash_delete (HASH * table, const char *key, const void *data,
+                  void (*destroy) (void *));
+void int_hash_delete (HASH * table, unsigned int key, const void *data,
+                  void (*destroy) (void *));
+
 void hash_destroy (HASH ** hash, void (*destroy) (void *));
 
 #endif
diff --git a/thread.c b/thread.c
index 2e247c09..27ce5160 100644
--- a/thread.c
+++ b/thread.c
@@ -416,7 +416,6 @@ static THREAD *find_subject (CONTEXT *ctx, THREAD *cur)
 {
   struct hash_elem *ptr;
   THREAD *tmp, *last = NULL;
-  unsigned int hash;
   LIST *subjects = NULL, *oldlist;
   time_t date = 0;  
 
@@ -424,9 +423,7 @@ static THREAD *find_subject (CONTEXT *ctx, THREAD *cur)
 
   while (subjects)
   {
-    hash = ctx->subj_hash->hash_string ((unsigned char *) subjects->data,
-					ctx->subj_hash->nelem);
-    for (ptr = ctx->subj_hash->table[hash]; ptr; ptr = ptr->next)
+    for (ptr = hash_find_bucket (ctx->subj_hash, subjects->data); ptr; ptr = ptr->next)
     {
       tmp = ((HEADER *) ptr->data)->thread;
       if (tmp != cur &&			   /* don't match the same message */