From c90a4d013d046684841a02c5e05e95baa996a231 Mon Sep 17 00:00:00 2001 From: Kevin McCarthy Date: Fri, 6 Jan 2017 14:17:10 -0800 Subject: [PATCH] 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. --- hash.c | 162 +++++++++++++++++++++++++++++++++++++++++++++++-------- hash.h | 33 ++++++++---- init.c | 2 +- thread.c | 5 +- 4 files changed, 165 insertions(+), 37 deletions(-) diff --git a/hash.c b/hash.c index a3586d8e2..457acfe79 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,7 +58,26 @@ 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) @@ -59,19 +85,33 @@ HASH *hash_create (int nelem, int lower) table->nelem = nelem; table->curnelem = 0; 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; +} + HASH *hash_resize (HASH *ptr, int nelem, int lower) { HASH *table; @@ -86,7 +126,7 @@ HASH *hash_resize (HASH *ptr, int nelem, int lower) { tmp = elem; elem = elem->next; - hash_insert (table, tmp->key, tmp->data, 1); + hash_insert (table, tmp->key.strkey, tmp->data, 1); FREE (&tmp); } } @@ -100,13 +140,13 @@ HASH *hash_resize (HASH *ptr, int nelem, int lower) * 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 = 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; @@ -123,7 +163,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); @@ -142,12 +182,33 @@ 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) { - struct hash_elem *ptr = table->table[hash]; + 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) +{ + 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; @@ -158,7 +219,10 @@ void hash_set_data (HASH *table, const char *key, void *data) if (!table) return; - unsigned int hash = table->hash_string ((unsigned char *) key, table->nelem); + union hash_key k; + k.strkey = key; + + unsigned int hash = table->gen_hash (k, table->nelem); struct hash_elem *ptr = table->table[hash]; if (!ptr) @@ -167,23 +231,57 @@ void hash_set_data (HASH *table, const char *key, void *data) ptr->data = data; } -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; + + hash = table->gen_hash (key, table->nelem); + ptr = table->table[hash]; + last = &table->table[hash]; - while (ptr) + 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); table->curnelem--; - + ptr = *last; } else @@ -194,15 +292,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 5dbdb7e92..455e3a19f 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,21 +36,28 @@ typedef struct { int nelem, curnelem; 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); HASH *hash_resize (HASH * table, int nelem, int lower); -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 *)); void hash_set_data (HASH *table, const char *key, void *data); diff --git a/init.c b/init.c index a6e02ceed..8637beb4d 100644 --- a/init.c +++ b/init.c @@ -4077,7 +4077,7 @@ int mutt_label_complete (char *buffer, size_t len, int pos, int numtabs) memset (Completed, 0, sizeof (Completed)); memset (&state, 0, sizeof(state)); while ((entry = hash_walk(Labels, &state))) - candidate (Completed, User_typed, entry->key, sizeof (Completed)); + candidate (Completed, User_typed, entry->key.strkey, sizeof (Completed)); matches_ensure_morespace (Num_matched); qsort(Matches, Num_matched, sizeof(char *), (sort_t *) mutt_strcasecmp); Matches[Num_matched++] = User_typed; diff --git a/thread.c b/thread.c index 99b54e0fa..3130e0856 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 */ -- 2.40.0