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));
55 table->table = safe_calloc (nelem, sizeof (struct hash_elem *));
59 HASH *hash_resize (HASH *ptr, int nelem)
62 struct hash_elem *elem, *tmp;
65 table = hash_create (nelem);
67 for (i = 0; i < ptr->nelem; i++)
69 for (elem = ptr->table[i]; elem; )
73 hash_insert (table, tmp->key, tmp->data, 1);
83 /* table hash table to update
85 * data data to associate with `key'
86 * allow_dup if nonzero, duplicate keys are allowed in the table
88 int hash_insert (HASH * table, const char *key, void *data, int allow_dup)
90 struct hash_elem *ptr;
93 ptr = (struct hash_elem *) safe_malloc (sizeof (struct hash_elem));
94 h = hash_string ((unsigned char *) key, table->nelem);
100 ptr->next = table->table[h];
101 table->table[h] = ptr;
106 struct hash_elem *tmp, *last;
109 for (tmp = table->table[h], last = NULL; tmp; last = tmp, tmp = tmp->next)
111 r = mutt_strcmp (tmp->key, key);
123 table->table[h] = ptr;
130 void *hash_find_hash (const HASH * table, int hash, const char *key)
132 struct hash_elem *ptr = table->table[hash];
133 for (; ptr; ptr = ptr->next)
135 if (mutt_strcmp (key, ptr->key) == 0)
141 void hash_delete_hash (HASH * table, int hash, const char *key, const void *data,
142 void (*destroy) (void *))
144 struct hash_elem *ptr = table->table[hash];
145 struct hash_elem **last = &table->table[hash];
147 for (; ptr; last = &ptr->next, ptr = ptr->next)
149 /* if `data' is given, look for a matching ->data member. this is
150 * required for the case where we have multiple entries with the same
153 if ((data == ptr->data) || (!data && mutt_strcmp (ptr->key, key) == 0))
156 if (destroy) destroy (ptr->data);
164 /* ptr pointer to the hash table to be freed
165 * destroy() function to call to free the ->data member (optional)
167 void hash_destroy (HASH **ptr, void (*destroy) (void *))
171 struct hash_elem *elem, *tmp;
173 for (i = 0 ; i < pptr->nelem; i++)
175 for (elem = pptr->table[i]; elem; )