jcs.org
mutt stable branch with some hacks
1/*
2 * Copyright (C) 1996-2009 Michael R. Elkins <me@mutt.org>
3 *
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.
8 *
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.
13 *
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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17 */
18
19#if HAVE_CONFIG_H
20# include "config.h"
21#endif
22
23#include <stdlib.h>
24#include <stdio.h>
25#include <string.h>
26#include <ctype.h>
27
28#include "mutt.h"
29
30#define SOMEPRIME 149711
31
32static unsigned int gen_string_hash (union hash_key key, unsigned int n)
33{
34 unsigned int h = 0;
35 unsigned char *s = (unsigned char *)key.strkey;
36
37 while (*s)
38 h += (h << 7) + *s++;
39 h = (h * SOMEPRIME) % n;
40
41 return h;
42}
43
44static int cmp_string_key (union hash_key a, union hash_key b)
45{
46 return mutt_strcmp (a.strkey, b.strkey);
47}
48
49static unsigned int gen_case_string_hash (union hash_key key, unsigned int n)
50{
51 unsigned int h = 0;
52 unsigned char *s = (unsigned char *)key.strkey;
53
54 while (*s)
55 h += (h << 7) + tolower (*s++);
56 h = (h * SOMEPRIME) % n;
57
58 return h;
59}
60
61static int cmp_case_string_key (union hash_key a, union hash_key b)
62{
63 return mutt_strcasecmp (a.strkey, b.strkey);
64}
65
66static unsigned int gen_int_hash (union hash_key key, unsigned int n)
67{
68 return key.intkey % n;
69}
70
71static int cmp_int_key (union hash_key a, union hash_key b)
72{
73 if (a.intkey == b.intkey)
74 return 0;
75 if (a.intkey < b.intkey)
76 return -1;
77 return 1;
78}
79
80static HASH *new_hash (int nelem)
81{
82 HASH *table = safe_malloc (sizeof (HASH));
83 if (nelem == 0)
84 nelem = 2;
85 table->nelem = nelem;
86 table->table = safe_calloc (nelem, sizeof (struct hash_elem *));
87 return table;
88}
89
90HASH *hash_create (int nelem, int lower)
91{
92 HASH *table = new_hash (nelem);
93 if (lower)
94 {
95 table->gen_hash = gen_case_string_hash;
96 table->cmp_key = cmp_case_string_key;
97 }
98 else
99 {
100 table->gen_hash = gen_string_hash;
101 table->cmp_key = cmp_string_key;
102 }
103 return table;
104}
105
106HASH *int_hash_create (int nelem)
107{
108 HASH *table = new_hash (nelem);
109 table->gen_hash = gen_int_hash;
110 table->cmp_key = cmp_int_key;
111 return table;
112}
113
114/* table hash table to update
115 * key key to hash on
116 * data data to associate with `key'
117 * allow_dup if nonzero, duplicate keys are allowed in the table
118 */
119static int union_hash_insert (HASH * table, union hash_key key, void *data, int allow_dup)
120{
121 struct hash_elem *ptr;
122 unsigned int h;
123
124 ptr = (struct hash_elem *) safe_malloc (sizeof (struct hash_elem));
125 h = table->gen_hash (key, table->nelem);
126 ptr->key = key;
127 ptr->data = data;
128
129 if (allow_dup)
130 {
131 ptr->next = table->table[h];
132 table->table[h] = ptr;
133 }
134 else
135 {
136 struct hash_elem *tmp, *last;
137 int r;
138
139 for (tmp = table->table[h], last = NULL; tmp; last = tmp, tmp = tmp->next)
140 {
141 r = table->cmp_key (tmp->key, key);
142 if (r == 0)
143 {
144 FREE (&ptr);
145 return (-1);
146 }
147 if (r > 0)
148 break;
149 }
150 if (last)
151 last->next = ptr;
152 else
153 table->table[h] = ptr;
154 ptr->next = tmp;
155 }
156 return h;
157}
158
159int hash_insert (HASH * table, const char *strkey, void *data, int allow_dup)
160{
161 union hash_key key;
162 key.strkey = strkey;
163 return union_hash_insert (table, key, data, allow_dup);
164}
165
166int int_hash_insert (HASH * table, unsigned int intkey, void *data, int allow_dup)
167{
168 union hash_key key;
169 key.intkey = intkey;
170 return union_hash_insert (table, key, data, allow_dup);
171}
172
173static void *union_hash_find (const HASH *table, union hash_key key)
174{
175 int hash;
176 struct hash_elem *ptr;
177
178 if (!table)
179 return NULL;
180
181 hash = table->gen_hash (key, table->nelem);
182 ptr = table->table[hash];
183 for (; ptr; ptr = ptr->next)
184 {
185 if (table->cmp_key (key, ptr->key) == 0)
186 return (ptr->data);
187 }
188 return NULL;
189}
190
191void *hash_find (const HASH *table, const char *strkey)
192{
193 union hash_key key;
194 key.strkey = strkey;
195 return union_hash_find (table, key);
196}
197
198void *int_hash_find (const HASH *table, unsigned int intkey)
199{
200 union hash_key key;
201 key.intkey = intkey;
202 return union_hash_find (table, key);
203}
204
205struct hash_elem *hash_find_bucket (const HASH *table, const char *strkey)
206{
207 union hash_key key;
208 int hash;
209
210 if (!table)
211 return NULL;
212
213 key.strkey = strkey;
214 hash = table->gen_hash (key, table->nelem);
215 return table->table[hash];
216}
217
218static void union_hash_delete (HASH *table, union hash_key key, const void *data,
219 void (*destroy) (void *))
220{
221 int hash;
222 struct hash_elem *ptr, **last;
223
224 if (!table)
225 return;
226
227 hash = table->gen_hash (key, table->nelem);
228 ptr = table->table[hash];
229 last = &table->table[hash];
230
231 while (ptr)
232 {
233 if ((data == ptr->data || !data)
234 && table->cmp_key (ptr->key, key) == 0)
235 {
236 *last = ptr->next;
237 if (destroy)
238 destroy (ptr->data);
239 FREE (&ptr);
240
241 ptr = *last;
242 }
243 else
244 {
245 last = &ptr->next;
246 ptr = ptr->next;
247 }
248 }
249}
250
251void hash_delete (HASH *table, const char *strkey, const void *data,
252 void (*destroy) (void *))
253{
254 union hash_key key;
255 key.strkey = strkey;
256 union_hash_delete (table, key, data, destroy);
257}
258
259void int_hash_delete (HASH *table, unsigned int intkey, const void *data,
260 void (*destroy) (void *))
261{
262 union hash_key key;
263 key.intkey = intkey;
264 union_hash_delete (table, key, data, destroy);
265}
266
267/* ptr pointer to the hash table to be freed
268 * destroy() function to call to free the ->data member (optional)
269 */
270void hash_destroy (HASH **ptr, void (*destroy) (void *))
271{
272 int i;
273 HASH *pptr;
274 struct hash_elem *elem, *tmp;
275
276 if (!ptr || !*ptr)
277 return;
278
279 pptr = *ptr;
280 for (i = 0 ; i < pptr->nelem; i++)
281 {
282 for (elem = pptr->table[i]; elem; )
283 {
284 tmp = elem;
285 elem = elem->next;
286 if (destroy)
287 destroy (tmp->data);
288 FREE (&tmp);
289 }
290 }
291 FREE (&pptr->table);
292 FREE (ptr); /* __FREE_CHECKED__ */
293}