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, int allow_dup)
44 HASH *table = p_new(HASH, 1);
46 table->dupes = allow_dup;
47 table->nelem = MIN(nelem, 2);
49 table->table = p_new(struct hash_elem *, table->nelem);
54 void hash_resize(HASH *ptr, int nelem)
57 struct hash_elem *elem, *tmp;
60 /* XXX hack: we know the has was correct, no dupe checks is fater */
61 table = hash_create(nelem, 1);
63 for (i = 0; i < ptr->nelem; i++) {
64 for (elem = ptr->table[i]; elem;) {
67 hash_insert(table, tmp->key, tmp->data);
72 p_delete(&ptr->table);
73 ptr->nelem = table->nelem;
74 ptr->table = table->table;
78 /* table hash table to update
80 * data data to associate with `key'
81 * allow_dup if nonzero, duplicate keys are allowed in the table
83 int hash_insert(HASH *table, const char *key, void *data)
85 struct hash_elem *ptr;
88 ptr = p_new(struct hash_elem, 1);
89 h = hash_string((unsigned char *)key, table->nelem);
94 ptr->next = table->table[h];
95 table->table[h] = ptr;
100 for (e = &table->table[h]; *e; e = &(*e)->next) {
101 int r = m_strcmp((*e)->key, key);
117 void *hash_find_hash(const HASH *table, int hash, const char *key)
119 struct hash_elem *ptr;
121 for (ptr = table->table[hash]; ptr; ptr = ptr->next) {
122 if (m_strcmp(key, ptr->key) == 0)
128 void hash_delete_hash(HASH *table, int hash, const char *key, const void *data,
129 void (*destroy)(void *))
131 struct hash_elem *ptr = table->table[hash];
132 struct hash_elem **last = &table->table[hash];
135 if ((data == ptr->data || !data) && m_strcmp(ptr->key, key) == 0) {
149 /* ptr pointer to the hash table to be freed
150 * destroy() function to call to free the ->data member (optional)
152 void hash_destroy(HASH **ptr, void (*destroy)(void *))
156 struct hash_elem *elem, *tmp;
158 for (i = 0; i < pptr->nelem; i++) {
159 for (elem = pptr->table[i]; elem;) {
167 p_delete(&pptr->table);
171 void hash_map(HASH *table,
172 void (*mapfunc)(const char* key, void* data, unsigned long more),
177 if (!table || !mapfunc)
180 for (i = 0; i < table->nelem; i++) {
181 struct hash_elem *elem;
183 for (elem = table->table[i]; elem; elem = elem->next) {
184 mapfunc (elem->key, elem->data, more);