2 * Copyright (C) 1996-2000 Michael R. Elkins <me@mutt.org>
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111, USA.
29 #define SOMEPRIME 149711
31 int hash_string (const unsigned char *s, int n)
41 h = (h * SOMEPRIME) % n;
42 h = (h >= 0) ? h : h + n;
48 HASH *hash_create (int nelem)
50 HASH *table = safe_malloc (sizeof (HASH));
56 table->table = safe_calloc (nelem, sizeof (struct hash_elem *));
60 HASH *hash_resize (HASH * ptr, int nelem)
63 struct hash_elem *elem, *tmp;
66 table = hash_create (nelem);
68 for (i = 0; i < ptr->nelem; i++) {
69 for (elem = ptr->table[i]; elem;) {
72 hash_insert (table, tmp->key, tmp->data, 1);
82 /* table hash table to update
84 * data data to associate with `key'
85 * allow_dup if nonzero, duplicate keys are allowed in the table
87 int hash_insert (HASH * table, const char *key, void *data, int allow_dup)
89 struct hash_elem *ptr;
92 ptr = (struct hash_elem *) safe_malloc (sizeof (struct hash_elem));
93 h = hash_string ((unsigned char *) key, table->nelem);
98 ptr->next = table->table[h];
99 table->table[h] = ptr;
103 struct hash_elem *tmp, *last;
106 for (tmp = table->table[h], last = NULL; tmp; last = tmp, tmp = tmp->next) {
107 r = mutt_strcmp (tmp->key, key);
118 table->table[h] = ptr;
125 void *hash_find_hash (const HASH * table, int hash, const char *key)
127 struct hash_elem *ptr = table->table[hash];
129 for (; ptr; ptr = ptr->next) {
130 if (mutt_strcmp (key, ptr->key) == 0)
136 void hash_delete_hash (HASH * table, int hash, const char *key,
137 const void *data, void (*destroy) (void *))
139 struct hash_elem *ptr = table->table[hash];
140 struct hash_elem **last = &table->table[hash];
142 for (; ptr; last = &ptr->next, ptr = ptr->next) {
143 /* if `data' is given, look for a matching ->data member. this is
144 * required for the case where we have multiple entries with the same
147 if ((data == ptr->data) || (!data && mutt_strcmp (ptr->key, key) == 0)) {
158 /* ptr pointer to the hash table to be freed
159 * destroy() function to call to free the ->data member (optional)
161 void hash_destroy (HASH ** ptr, void (*destroy) (void *))
165 struct hash_elem *elem, *tmp;
167 for (i = 0; i < pptr->nelem; i++) {
168 for (elem = pptr->table[i]; elem;) {