From 3e611c4b53a33408955152e1c9336f8643ea096e Mon Sep 17 00:00:00 2001 From: Pierre Habouzit Date: Sun, 29 Oct 2006 19:42:37 +0100 Subject: [PATCH] move hash.[hc] into lib-lib/ Signed-off-by: Pierre Habouzit --- Makefile.am | 4 +- hash.c | 184 ----------------------------------------- hash.h | 43 ---------- lib-lib/Makefile.am | 6 +- lib-lib/hash.c | 196 ++++++++++++++++++++++++++++++++++++++++++++ lib-lib/hash.h | 58 +++++++++++++ lib-lib/str.c | 2 + lib-lib/str.h | 8 +- lib/str.h | 2 - mutt.h | 2 +- 10 files changed, 269 insertions(+), 236 deletions(-) delete mode 100644 hash.c delete mode 100644 hash.h create mode 100644 lib-lib/hash.c create mode 100644 lib-lib/hash.h diff --git a/Makefile.am b/Makefile.am index afee72e..24747a0 100644 --- a/Makefile.am +++ b/Makefile.am @@ -34,7 +34,7 @@ muttng_SOURCES = $(BUILT_SOURCES) \ edit.c editmsg.c enter.c \ flags.c filter.c from.c \ getdomain.c \ - handler.c hash.c hcache.c hdrline.c headers.c help.c history.c hook.c \ + handler.c hcache.c hdrline.c headers.c help.c history.c hook.c \ init.c \ keymap.c \ lib.c list.c \ @@ -96,7 +96,7 @@ EXTRA_DIST = config.rpath COPYRIGHT GPL OPS OPS.PGP OPS.CRYPT OPS.SMIME TODO \ dotlock.h functions.h gen_defs \ enter.h recvattach.h handler.h thread.h \ list.h \ - globals.h hash.h history.h init.h keymap.h mutt_crypt.h \ + globals.h history.h init.h keymap.h mutt_crypt.h \ mapping.h md5.h mime.h mutt.h mutt_curses.h mutt_menu.h \ mutt_sasl.h mutt_socket.h mutt_ssl.h mutt_tunnel.h \ mbox.h mh.h mx.h pager.h pgp.h protos.h reldate.h rfc1524.h rfc2047.h \ diff --git a/hash.c b/hash.c deleted file mode 100644 index ef9346d..0000000 --- a/hash.c +++ /dev/null @@ -1,184 +0,0 @@ -/* - * Copyright notice from original mutt: - * Copyright (C) 1996-2000 Michael R. Elkins - * - * This file is part of mutt-ng, see http://www.muttng.org/. - * It's licensed under the GNU General Public License, - * please see the file GPL in the top level source directory. - */ - -#if HAVE_CONFIG_H -# include "config.h" -#endif - -#include -#include -#include - -#include - -#include "mutt.h" - -#define SOMEPRIME 149711 - -int hash_string (const unsigned char *s, int n) -{ - int h = 0; - -#if 0 - while (*s) - h += *s++; -#else - while (*s) - h += (h << 7) + *s++; - h = (h * SOMEPRIME) % n; - h = (h >= 0) ? h : h + n; -#endif - - return (h % n); -} - -HASH *hash_create (int nelem) -{ - HASH *table = p_new(HASH, 1); - - if (nelem == 0) - nelem = 2; - table->nelem = nelem; - table->curnelem = 0; - table->table = p_new(struct hash_elem *, nelem); - return table; -} - -HASH *hash_resize(HASH *ptr, int nelem) -{ - HASH *table; - struct hash_elem *elem, *tmp; - int i; - - table = hash_create (nelem); - - for (i = 0; i < ptr->nelem; i++) { - for (elem = ptr->table[i]; elem;) { - tmp = elem; - elem = elem->next; - hash_insert (table, tmp->key, tmp->data, 1); - p_delete(&tmp); - } - } - p_delete(&ptr->table); - p_delete(&ptr); - - 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) -{ - struct hash_elem *ptr; - int h; - - ptr = p_new(struct hash_elem, 1); - h = hash_string ((unsigned char *) key, table->nelem); - ptr->key = key; - ptr->data = data; - - if (allow_dup) { - ptr->next = table->table[h]; - table->table[h] = ptr; - table->curnelem++; - } - else { - struct hash_elem *tmp, *last; - int r; - - for (tmp = table->table[h], last = NULL; tmp; last = tmp, tmp = tmp->next) { - r = str_cmp (tmp->key, key); - if (r == 0) { - p_delete(&ptr); - return (-1); - } - if (r > 0) - break; - } - if (last) - last->next = ptr; - else - table->table[h] = ptr; - ptr->next = tmp; - table->curnelem++; - } - return h; -} - -void *hash_find_hash (const HASH * table, int hash, const char *key) -{ - struct hash_elem *ptr = table->table[hash]; - - for (; ptr; ptr = ptr->next) { - if (str_cmp (key, ptr->key) == 0) - return (ptr->data); - } - return NULL; -} - -void hash_delete_hash (HASH * table, int hash, const char *key, const void *data, - void (*destroy) (void *)) -{ - struct hash_elem *ptr = table->table[hash]; - struct hash_elem **last = &table->table[hash]; - - while (ptr) { - if ((data == ptr->data || !data) && str_cmp (ptr->key, key) == 0) { - *last = ptr->next; - if (destroy) - destroy (ptr->data); - p_delete(&ptr); - - ptr = *last; - } else { - last = &ptr->next; - ptr = ptr->next; - } - } -} - -/* 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; - struct hash_elem *elem, *tmp; - - for (i = 0; i < pptr->nelem; i++) { - for (elem = pptr->table[i]; elem;) { - tmp = elem; - elem = elem->next; - if (destroy) - destroy (tmp->data); - p_delete(&tmp); - } - } - p_delete(&pptr->table); - p_delete(ptr); -} - -void hash_map (HASH* table, void (*mapfunc) (const char* key, void* data, - unsigned long more), - unsigned long more) { - int i = 0; - struct hash_elem* elem = NULL; - - if (!table || !mapfunc) - return; - - for (i = 0; i < table->nelem; i++) - for (elem = table->table[i]; elem; elem = elem->next) - mapfunc (elem->key, elem->data, more); -} diff --git a/hash.h b/hash.h deleted file mode 100644 index 2e3f98d..0000000 --- a/hash.h +++ /dev/null @@ -1,43 +0,0 @@ -/* - * Copyright notice from original mutt: - * Copyright (C) 1996-2000 Michael R. Elkins - * - * This file is part of mutt-ng, see http://www.muttng.org/. - * It's licensed under the GNU General Public License, - * please see the file GPL in the top level source directory. - */ - -#ifndef _HASH_H -#define _HASH_H - -struct hash_elem { - const char *key; - void *data; - struct hash_elem *next; -}; - -typedef struct { - int nelem, curnelem; - struct hash_elem **table; -} HASH; - -#define hash_find(table, key) \ - hash_find_hash(table, hash_string((unsigned char *)key, table->nelem), key) - -#define hash_delete(table,key,data,destroy) \ - hash_delete_hash(table, hash_string((unsigned char *)key, table->nelem), key, data, destroy) - -HASH *hash_create(int nelem); -int hash_string(const unsigned char *s, int n); -int hash_insert(HASH * table, const char *key, void *data, int allow_dup); -HASH *hash_resize(HASH * table, int nelem); -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 *)); -void hash_destroy(HASH ** hash, void (*destroy) (void *)); - -void hash_map(HASH* table, - void (*mapfunc) (const char* key, void* data, unsigned long more), - unsigned long more); - -#endif diff --git a/lib-lib/Makefile.am b/lib-lib/Makefile.am index 2b844c1..fe73d73 100644 --- a/lib-lib/Makefile.am +++ b/lib-lib/Makefile.am @@ -1,7 +1,7 @@ noinst_LIBRARIES = liblib.a -liblib_a_SOURCES = mem.h str.h ascii.h buffer.h \ - str.c ascii.c buffer.c +liblib_a_SOURCES = mem.h str.h ascii.h buffer.h hash.h \ + str.c ascii.c buffer.c hash.c -noinst_HEADERS = mem.h str.h ascii.h +noinst_HEADERS = mem.h str.h ascii.h buffer.h hash.h diff --git a/lib-lib/hash.c b/lib-lib/hash.c new file mode 100644 index 0000000..61e2e4f --- /dev/null +++ b/lib-lib/hash.c @@ -0,0 +1,196 @@ +/* + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or (at + * your option) any later version. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, + * MA 02110-1301, USA. + * + * Copyright © 2006 Pierre Habouzit + */ + +/* + * Copyright notice from original mutt: + * Copyright (C) 1996-2000 Michael R. Elkins + */ + +#include +#include +#include + +#include "mem.h" +#include "str.h" +#include "hash.h" + +#define SOMEPRIME 149711 + +int hash_string(const unsigned char *s, int n) +{ + int h = 0; + + while (*s) { + h += (h << 7) + *s++; + } + h = (h * SOMEPRIME) % n; + h = (h >= 0) ? h : h + n; + + return (h % n); +} + +HASH *hash_create(int nelem) +{ + HASH *table = p_new(HASH, 1); + + if (nelem == 0) + nelem = 2; + + table->nelem = nelem; + table->curnelem = 0; + table->table = p_new(struct hash_elem *, nelem); + return table; +} + +HASH *hash_resize(HASH *ptr, int nelem) +{ + HASH *table; + struct hash_elem *elem, *tmp; + int i; + + table = hash_create (nelem); + + for (i = 0; i < ptr->nelem; i++) { + for (elem = ptr->table[i]; elem;) { + tmp = elem; + elem = elem->next; + hash_insert(table, tmp->key, tmp->data, 1); + p_delete(&tmp); + } + } + p_delete(&ptr->table); + p_delete(&ptr); + + 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) +{ + struct hash_elem *ptr; + int h; + + ptr = p_new(struct hash_elem, 1); + h = hash_string((unsigned char *)key, table->nelem); + ptr->key = key; + ptr->data = data; + + if (allow_dup) { + ptr->next = table->table[h]; + table->table[h] = ptr; + table->curnelem++; + } else { + struct hash_elem *tmp, *last; + int r; + + for (tmp = table->table[h], last = NULL; tmp; last = tmp, tmp = tmp->next) { + r = m_strcmp(tmp->key, key); + if (r == 0) { + p_delete(&ptr); + return (-1); + } + if (r > 0) + break; + } + if (last) { + last->next = ptr; + } else { + table->table[h] = ptr; + } + ptr->next = tmp; + table->curnelem++; + } + return h; +} + +void *hash_find_hash(const HASH *table, int hash, const char *key) +{ + struct hash_elem *ptr; + + for (ptr = table->table[hash]; ptr; ptr = ptr->next) { + if (m_strcmp(key, ptr->key) == 0) + return (ptr->data); + } + return NULL; +} + +void hash_delete_hash(HASH *table, int hash, const char *key, const void *data, + void (*destroy)(void *)) +{ + struct hash_elem *ptr = table->table[hash]; + struct hash_elem **last = &table->table[hash]; + + while (ptr) { + if ((data == ptr->data || !data) && m_strcmp(ptr->key, key) == 0) { + *last = ptr->next; + if (destroy) + destroy (ptr->data); + p_delete(&ptr); + + ptr = *last; + } else { + last = &ptr->next; + ptr = ptr->next; + } + } +} + +/* 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; + struct hash_elem *elem, *tmp; + + for (i = 0; i < pptr->nelem; i++) { + for (elem = pptr->table[i]; elem;) { + tmp = elem; + elem = elem->next; + if (destroy) + destroy (tmp->data); + p_delete(&tmp); + } + } + p_delete(&pptr->table); + p_delete(ptr); +} + +void hash_map(HASH *table, + void (*mapfunc)(const char* key, void* data, unsigned long more), + unsigned long more) +{ + int i; + + if (!table || !mapfunc) + return; + + for (i = 0; i < table->nelem; i++) { + struct hash_elem *elem; + + for (elem = table->table[i]; elem; elem = elem->next) { + mapfunc (elem->key, elem->data, more); + } + } +} diff --git a/lib-lib/hash.h b/lib-lib/hash.h new file mode 100644 index 0000000..3fdba21 --- /dev/null +++ b/lib-lib/hash.h @@ -0,0 +1,58 @@ +/* + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or (at + * your option) any later version. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, + * MA 02110-1301, USA. + * + * Copyright © 2006 Pierre Habouzit + */ + +/* + * Copyright notice from original mutt: + * Copyright (C) 1996-2000 Michael R. Elkins + */ + +#ifndef MUTT_LIB_LIB_HASH_H +#define MUTT_LIB_LIB_HASH_H + +struct hash_elem { + const char *key; + void *data; + struct hash_elem *next; +}; + +typedef struct { + int nelem, curnelem; + struct hash_elem **table; +} HASH; + +#define hash_find(table, key) \ + hash_find_hash(table, hash_string((unsigned char *)key, table->nelem), key) + +#define hash_delete(table,key,data,destroy) \ + hash_delete_hash(table, hash_string((unsigned char *)key, table->nelem), key, data, destroy) + +HASH *hash_create(int nelem); +int hash_string(const unsigned char *s, int n); +int hash_insert(HASH *table, const char *key, void *data, int allow_dup); +HASH *hash_resize(HASH *table, int nelem); +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 *)); +void hash_destroy(HASH **hash, void (*destroy)(void *)); + +void hash_map(HASH *table, + void (*mapfunc)(const char *key, void *data, unsigned long more), + unsigned long more); + +#endif /* MUTT_LIB_LIB_HASH_H */ diff --git a/lib-lib/str.c b/lib-lib/str.c index 25e17af..ca0aff7 100644 --- a/lib-lib/str.c +++ b/lib-lib/str.c @@ -16,3 +16,5 @@ * * Copyright © 2006 Pierre Habouzit */ + +#include "str.h" diff --git a/lib-lib/str.h b/lib-lib/str.h index d28c814..d21e120 100644 --- a/lib-lib/str.h +++ b/lib-lib/str.h @@ -25,12 +25,18 @@ #include "mem.h" +#define NONULL(x) (x?x:"") + static inline ssize_t m_strlen(const char *s) { return s ? strlen(s) : 0; } -static inline char* m_strdup(const char *s) { +static inline char *m_strdup(const char *s) { return p_dupstr(s, m_strlen(s)); } +static inline int m_strcmp(const char *a, const char *b) { + return strcmp(NONULL(a), NONULL(b)); +} + #endif /* MUTT_LIB_LIB_STR_H */ diff --git a/lib/str.h b/lib/str.h index 249ca20..8629d15 100644 --- a/lib/str.h +++ b/lib/str.h @@ -12,8 +12,6 @@ #include -#define NONULL(x) x?x:"" - # define HUGE_STRING 5120 # define LONG_STRING 1024 # define STRING 256 diff --git a/mutt.h b/mutt.h index 2913432..20b04c8 100644 --- a/mutt.h +++ b/mutt.h @@ -42,10 +42,10 @@ #include #include +#include #include "rfc822.h" #include "list.h" -#include "hash.h" #include "charset.h" #include "lib/rx.h" -- 2.20.1