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>
33 #define SOMEPRIME 149711
35 int hash_string(const unsigned char *s, int n)
42 h = (h * SOMEPRIME) % n;
43 h = (h >= 0) ? h : h + n;
48 HASH *hash_create(int nelem)
50 HASH *table = p_new(HASH, 1);
57 table->table = p_new(struct hash_elem *, nelem);
61 HASH *hash_resize(HASH *ptr, int nelem)
64 struct hash_elem *elem, *tmp;
67 table = hash_create (nelem);
69 for (i = 0; i < ptr->nelem; i++) {
70 for (elem = ptr->table[i]; elem;) {
73 hash_insert(table, tmp->key, tmp->data, 1);
77 p_delete(&ptr->table);
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 = p_new(struct hash_elem, 1);
94 h = hash_string((unsigned char *)key, table->nelem);
99 ptr->next = table->table[h];
100 table->table[h] = ptr;
103 struct hash_elem *tmp, *last;
106 for (tmp = table->table[h], last = NULL; tmp; last = tmp, tmp = tmp->next) {
107 r = m_strcmp(tmp->key, key);
118 table->table[h] = ptr;
126 void *hash_find_hash(const HASH *table, int hash, const char *key)
128 struct hash_elem *ptr;
130 for (ptr = table->table[hash]; ptr; ptr = ptr->next) {
131 if (m_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];
144 if ((data == ptr->data || !data) && m_strcmp(ptr->key, key) == 0) {
158 /* ptr pointer to the hash table to be freed
159 * destroy() function to call to free the ->data member (optional)
161 void hash_destroy(HASH **ptr, void (*destroy)(void *))
165 struct hash_elem *elem, *tmp;
167 for (i = 0; i < pptr->nelem; i++) {
168 for (elem = pptr->table[i]; elem;) {
176 p_delete(&pptr->table);
180 void hash_map(HASH *table,
181 void (*mapfunc)(const char* key, void* data, unsigned long more),
186 if (!table || !mapfunc)
189 for (i = 0; i < table->nelem; i++) {
190 struct hash_elem *elem;
192 for (elem = table->table[i]; elem; elem = elem->next) {
193 mapfunc (elem->key, elem->data, more);