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_calloc (1, 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 flags)
91{
92 HASH *table = new_hash (nelem);
93 if (flags & MUTT_HASH_STRCASECMP)
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 if (flags & MUTT_HASH_STRDUP_KEYS)
104 table->strdup_keys = 1;
105 if (flags & MUTT_HASH_ALLOW_DUPS)
106 table->allow_dups = 1;
107 return table;
108}
109
110HASH *int_hash_create (int nelem, int flags)
111{
112 HASH *table = new_hash (nelem);
113 table->gen_hash = gen_int_hash;
114 table->cmp_key = cmp_int_key;
115 if (flags & MUTT_HASH_ALLOW_DUPS)
116 table->allow_dups = 1;
117 return table;
118}
119
120/* table hash table to update
121 * key key to hash on
122 * data data to associate with `key'
123 * allow_dup if nonzero, duplicate keys are allowed in the table
124 */
125static int union_hash_insert (HASH * table, union hash_key key, void *data)
126{
127 struct hash_elem *ptr;
128 unsigned int h;
129
130 ptr = (struct hash_elem *) safe_malloc (sizeof (struct hash_elem));
131 h = table->gen_hash (key, table->nelem);
132 ptr->key = key;
133 ptr->data = data;
134
135 if (table->allow_dups)
136 {
137 ptr->next = table->table[h];
138 table->table[h] = ptr;
139 }
140 else
141 {
142 struct hash_elem *tmp, *last;
143 int r;
144
145 for (tmp = table->table[h], last = NULL; tmp; last = tmp, tmp = tmp->next)
146 {
147 r = table->cmp_key (tmp->key, key);
148 if (r == 0)
149 {
150 FREE (&ptr);
151 return (-1);
152 }
153 if (r > 0)
154 break;
155 }
156 if (last)
157 last->next = ptr;
158 else
159 table->table[h] = ptr;
160 ptr->next = tmp;
161 }
162 return h;
163}
164
165int hash_insert (HASH * table, const char *strkey, void *data)
166{
167 union hash_key key;
168 key.strkey = table->strdup_keys ? safe_strdup (strkey) : strkey;
169 return union_hash_insert (table, key, data);
170}
171
172int int_hash_insert (HASH * table, unsigned int intkey, void *data)
173{
174 union hash_key key;
175 key.intkey = intkey;
176 return union_hash_insert (table, key, data);
177}
178
179static struct hash_elem *union_hash_find_elem (const HASH *table, union hash_key key)
180{
181 int hash;
182 struct hash_elem *ptr;
183
184 if (!table)
185 return NULL;
186
187 hash = table->gen_hash (key, table->nelem);
188 ptr = table->table[hash];
189 for (; ptr; ptr = ptr->next)
190 {
191 if (table->cmp_key (key, ptr->key) == 0)
192 return (ptr);
193 }
194 return NULL;
195}
196
197static void *union_hash_find (const HASH *table, union hash_key key)
198{
199 struct hash_elem *ptr = union_hash_find_elem (table, key);
200 if (ptr)
201 return ptr->data;
202 else
203 return NULL;
204}
205
206void *hash_find (const HASH *table, const char *strkey)
207{
208 union hash_key key;
209 key.strkey = strkey;
210 return union_hash_find (table, key);
211}
212
213struct hash_elem *hash_find_elem (const HASH *table, const char *strkey)
214{
215 union hash_key key;
216 key.strkey = strkey;
217 return union_hash_find_elem (table, key);
218}
219
220void *int_hash_find (const HASH *table, unsigned int intkey)
221{
222 union hash_key key;
223 key.intkey = intkey;
224 return union_hash_find (table, key);
225}
226
227struct hash_elem *hash_find_bucket (const HASH *table, const char *strkey)
228{
229 union hash_key key;
230 int hash;
231
232 if (!table)
233 return NULL;
234
235 key.strkey = strkey;
236 hash = table->gen_hash (key, table->nelem);
237 return table->table[hash];
238}
239
240static void union_hash_delete (HASH *table, union hash_key key, const void *data,
241 void (*destroy) (void *))
242{
243 int hash;
244 struct hash_elem *ptr, **last;
245
246 if (!table)
247 return;
248
249 hash = table->gen_hash (key, table->nelem);
250 ptr = table->table[hash];
251 last = &table->table[hash];
252
253 while (ptr)
254 {
255 if ((data == ptr->data || !data)
256 && table->cmp_key (ptr->key, key) == 0)
257 {
258 *last = ptr->next;
259 if (destroy)
260 destroy (ptr->data);
261 if (table->strdup_keys)
262 FREE (&ptr->key.strkey);
263 FREE (&ptr);
264
265 ptr = *last;
266 }
267 else
268 {
269 last = &ptr->next;
270 ptr = ptr->next;
271 }
272 }
273}
274
275void hash_delete (HASH *table, const char *strkey, const void *data,
276 void (*destroy) (void *))
277{
278 union hash_key key;
279 key.strkey = strkey;
280 union_hash_delete (table, key, data, destroy);
281}
282
283void int_hash_delete (HASH *table, unsigned int intkey, const void *data,
284 void (*destroy) (void *))
285{
286 union hash_key key;
287 key.intkey = intkey;
288 union_hash_delete (table, key, data, destroy);
289}
290
291/* ptr pointer to the hash table to be freed
292 * destroy() function to call to free the ->data member (optional)
293 */
294void hash_destroy (HASH **ptr, void (*destroy) (void *))
295{
296 int i;
297 HASH *pptr;
298 struct hash_elem *elem, *tmp;
299
300 if (!ptr || !*ptr)
301 return;
302
303 pptr = *ptr;
304 for (i = 0 ; i < pptr->nelem; i++)
305 {
306 for (elem = pptr->table[i]; elem; )
307 {
308 tmp = elem;
309 elem = elem->next;
310 if (destroy)
311 destroy (tmp->data);
312 if (pptr->strdup_keys)
313 FREE (&tmp->key.strkey);
314 FREE (&tmp);
315 }
316 }
317 FREE (&pptr->table);
318 FREE (ptr); /* __FREE_CHECKED__ */
319}
320
321struct hash_elem *hash_walk(const HASH *table, struct hash_walk_state *state)
322{
323 if (state->last && state->last->next)
324 {
325 state->last = state->last->next;
326 return state->last;
327 }
328
329 if (state->last)
330 state->index++;
331
332 while (state->index < table->nelem)
333 {
334 if (table->table[state->index])
335 {
336 state->last = table->table[state->index];
337 return state->last;
338 }
339 state->index++;
340 }
341
342 state->index = 0;
343 state->last = NULL;
344 return NULL;
345}