2 * This program is free software; you can redistribute it and/or modify
3 * it under the terms of the GNU General Public License as published by
4 * the Free Software Foundation; either version 2 of the License, or (at
5 * your option) any later version.
7 * This program is distributed in the hope that it will be useful, but
8 * WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
10 * General Public License for more details.
12 * You should have received a copy of the GNU General Public License
13 * along with this program; if not, write to the Free Software
14 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
17 * Copyright © 2006 Pierre Habouzit
21 * Copyright notice from original mutt:
22 * Copyright (C) 1996-2000 Michael R. Elkins <me@mutt.org>
27 #define SOMEPRIME 149711
29 int hash_string(const unsigned char *s, int n)
37 return (h * SOMEPRIME) % n;
40 hash_t *hash_init(hash_t *table, int nelem, int allow_dup)
42 table->dupes = allow_dup;
43 table->nelem = MAX(nelem, 2);
45 table->table = p_new(struct hash_elem *, table->nelem);
49 /* ptr pointer to the hash table to be freed
50 * destroy() function to call to free the ->data member (optional)
52 void hash_wipe(hash_t *h, void (*dtor)(void *))
56 for (i = 0; i < h->nelem; i++) {
57 struct hash_elem *elem, *tmp;
59 for (elem = h->table[i]; elem;) {
70 void hash_resize(hash_t *ptr, int nelem)
75 /* XXX hack: we know the has was correct, no dupe checks is fater */
76 hash_init(&table, nelem, 1);
78 for (i = 0; i < ptr->nelem; i++) {
79 struct hash_elem *elem, *tmp;
80 for (elem = ptr->table[i]; elem;) {
83 hash_insert(&table, tmp->key, tmp->data);
88 p_delete(&ptr->table);
89 ptr->nelem = table.nelem;
90 ptr->table = table.table;
93 /* table hash table to update
95 * data data to associate with `key'
96 * allow_dup if nonzero, duplicate keys are allowed in the table
98 int hash_insert(hash_t *table, const char *key, void *data)
100 struct hash_elem *ptr;
103 ptr = p_new(struct hash_elem, 1);
104 h = hash_string((unsigned char *)key, table->nelem);
109 ptr->next = table->table[h];
110 table->table[h] = ptr;
113 struct hash_elem **e;
115 for (e = &table->table[h]; *e; e = &(*e)->next) {
116 int r = m_strcmp((*e)->key, key);
132 void *hash_find(const hash_t *table, const char *key)
134 int hash = hash_string((unsigned char*)key, table->nelem);
135 struct hash_elem *ptr;
137 for (ptr = table->table[hash]; ptr; ptr = ptr->next) {
138 if (m_strcmp(key, ptr->key) == 0)
144 void hash_remove(hash_t *table, const char *key, const void *data,
145 void (*destroy)(void *))
147 int hash = hash_string((unsigned char*)key, table->nelem);
148 struct hash_elem *ptr = table->table[hash];
149 struct hash_elem **last = &table->table[hash];
152 if ((data == ptr->data || !data) && m_strcmp(ptr->key, key) == 0) {
166 void hash_map(hash_t *table,
167 void (*mapfunc)(const char* key, void* data, unsigned long more),
172 if (!table || !mapfunc)
175 for (i = 0; i < table->nelem; i++) {
176 struct hash_elem *elem;
178 for (elem = table->table[i]; elem; elem = elem->next) {
179 mapfunc (elem->key, elem->data, more);