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.
25 #define SOMEPRIME 149711
27 int hash_string (const unsigned char *s, int n)
37 h = (h * SOMEPRIME) % n;
38 h = (h >= 0) ? h : h + n;
44 HASH *hash_create (int nelem)
46 HASH *table = safe_malloc (sizeof (HASH));
51 table->table = safe_calloc (nelem, sizeof (struct hash_elem *));
55 HASH *hash_resize (HASH *ptr, int nelem)
58 struct hash_elem *elem, *tmp;
61 table = hash_create (nelem);
63 for (i = 0; i < ptr->nelem; i++)
65 for (elem = ptr->table[i]; elem; )
69 hash_insert (table, tmp->key, tmp->data, 1);
79 /* table hash table to update
81 * data data to associate with `key'
82 * allow_dup if nonzero, duplicate keys are allowed in the table
84 int hash_insert (HASH * table, const char *key, void *data, int allow_dup)
86 struct hash_elem *ptr;
89 ptr = (struct hash_elem *) safe_malloc (sizeof (struct hash_elem));
90 h = hash_string ((unsigned char *) key, table->nelem);
96 ptr->next = table->table[h];
97 table->table[h] = ptr;
102 struct hash_elem *tmp, *last;
105 for (tmp = table->table[h], last = NULL; tmp; last = tmp, tmp = tmp->next)
107 r = mutt_strcmp (tmp->key, key);
119 table->table[h] = ptr;
126 void *hash_find_hash (const HASH * table, int hash, const char *key)
128 struct hash_elem *ptr = table->table[hash];
129 for (; ptr; ptr = ptr->next)
131 if (mutt_strcmp (key, ptr->key) == 0)
137 void hash_delete_hash (HASH * table, int hash, const char *key, const void *data,
138 void (*destroy) (void *))
140 struct hash_elem *ptr = table->table[hash];
141 struct hash_elem **last = &table->table[hash];
143 for (; ptr; last = &ptr->next, ptr = ptr->next)
145 /* if `data' is given, look for a matching ->data member. this is
146 * required for the case where we have multiple entries with the same
149 if ((data == ptr->data) || (!data && mutt_strcmp (ptr->key, key) == 0))
152 if (destroy) destroy (ptr->data);
160 /* ptr pointer to the hash table to be freed
161 * destroy() function to call to free the ->data member (optional)
163 void hash_destroy (HASH **ptr, void (*destroy) (void *))
167 struct hash_elem *elem, *tmp;
169 for (i = 0 ; i < pptr->nelem; i++)
171 for (elem = pptr->table[i]; elem; )