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)
36 h = (h * SOMEPRIME) % n;
37 h = (h >= 0) ? h : h + n;
42 HASH *hash_create(int nelem)
44 HASH *table = p_new(HASH, 1);
51 table->table = p_new(struct hash_elem *, nelem);
55 HASH *hash_resize(HASH *ptr, int nelem)
58 struct hash_elem *elem, *tmp;
61 table = hash_create (nelem);
63 for (i = 0; i < ptr->nelem; i++) {
64 for (elem = ptr->table[i]; elem;) {
67 hash_insert(table, tmp->key, tmp->data, 1);
71 p_delete(&ptr->table);
77 /* table hash table to update
79 * data data to associate with `key'
80 * allow_dup if nonzero, duplicate keys are allowed in the table
82 int hash_insert(HASH *table, const char *key, void *data, int allow_dup)
84 struct hash_elem *ptr;
87 ptr = p_new(struct hash_elem, 1);
88 h = hash_string((unsigned char *)key, table->nelem);
93 ptr->next = table->table[h];
94 table->table[h] = ptr;
99 for (e = &table->table[h]; *e; e = &(*e)->next) {
100 int r = m_strcmp((*e)->key, key);
116 void *hash_find_hash(const HASH *table, int hash, const char *key)
118 struct hash_elem *ptr;
120 for (ptr = table->table[hash]; ptr; ptr = ptr->next) {
121 if (m_strcmp(key, ptr->key) == 0)
127 void hash_delete_hash(HASH *table, int hash, const char *key, const void *data,
128 void (*destroy)(void *))
130 struct hash_elem *ptr = table->table[hash];
131 struct hash_elem **last = &table->table[hash];
134 if ((data == ptr->data || !data) && m_strcmp(ptr->key, key) == 0) {
148 /* ptr pointer to the hash table to be freed
149 * destroy() function to call to free the ->data member (optional)
151 void hash_destroy(HASH **ptr, void (*destroy)(void *))
155 struct hash_elem *elem, *tmp;
157 for (i = 0; i < pptr->nelem; i++) {
158 for (elem = pptr->table[i]; elem;) {
166 p_delete(&pptr->table);
170 void hash_map(HASH *table,
171 void (*mapfunc)(const char* key, void* data, unsigned long more),
176 if (!table || !mapfunc)
179 for (i = 0; i < table->nelem; i++) {
180 struct hash_elem *elem;
182 for (elem = table->table[i]; elem; elem = elem->next) {
183 mapfunc (elem->key, elem->data, more);