+/*
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or (at
+ * your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02110-1301, USA.
+ *
+ * Copyright © 2006 Pierre Habouzit
+ */
+
+/*
+ * Copyright notice from original mutt:
+ * Copyright (C) 1996-2000 Michael R. Elkins <me@mutt.org>
+ */
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+
+#include "mem.h"
+#include "str.h"
+#include "hash.h"
+
+#define SOMEPRIME 149711
+
+int hash_string(const unsigned char *s, int n)
+{
+ int h = 0;
+
+ while (*s) {
+ h += (h << 7) + *s++;
+ }
+ h = (h * SOMEPRIME) % n;
+ h = (h >= 0) ? h : h + n;
+
+ return (h % n);
+}
+
+HASH *hash_create(int nelem)
+{
+ HASH *table = p_new(HASH, 1);
+
+ if (nelem == 0)
+ nelem = 2;
+
+ table->nelem = nelem;
+ table->curnelem = 0;
+ table->table = p_new(struct hash_elem *, nelem);
+ return table;
+}
+
+HASH *hash_resize(HASH *ptr, int nelem)
+{
+ HASH *table;
+ struct hash_elem *elem, *tmp;
+ int i;
+
+ table = hash_create (nelem);
+
+ for (i = 0; i < ptr->nelem; i++) {
+ for (elem = ptr->table[i]; elem;) {
+ tmp = elem;
+ elem = elem->next;
+ hash_insert(table, tmp->key, tmp->data, 1);
+ p_delete(&tmp);
+ }
+ }
+ p_delete(&ptr->table);
+ p_delete(&ptr);
+
+ return table;
+}
+
+/* table hash table to update
+ * key key to hash on
+ * data data to associate with `key'
+ * allow_dup if nonzero, duplicate keys are allowed in the table
+ */
+int hash_insert(HASH *table, const char *key, void *data, int allow_dup)
+{
+ struct hash_elem *ptr;
+ int h;
+
+ ptr = p_new(struct hash_elem, 1);
+ h = hash_string((unsigned char *)key, table->nelem);
+ ptr->key = key;
+ ptr->data = data;
+
+ if (allow_dup) {
+ ptr->next = table->table[h];
+ table->table[h] = ptr;
+ table->curnelem++;
+ } else {
+ struct hash_elem *tmp, *last;
+ int r;
+
+ for (tmp = table->table[h], last = NULL; tmp; last = tmp, tmp = tmp->next) {
+ r = m_strcmp(tmp->key, key);
+ if (r == 0) {
+ p_delete(&ptr);
+ return (-1);
+ }
+ if (r > 0)
+ break;
+ }
+ if (last) {
+ last->next = ptr;
+ } else {
+ table->table[h] = ptr;
+ }
+ ptr->next = tmp;
+ table->curnelem++;
+ }
+ return h;
+}
+
+void *hash_find_hash(const HASH *table, int hash, const char *key)
+{
+ struct hash_elem *ptr;
+
+ for (ptr = table->table[hash]; ptr; ptr = ptr->next) {
+ if (m_strcmp(key, ptr->key) == 0)
+ return (ptr->data);
+ }
+ return NULL;
+}
+
+void hash_delete_hash(HASH *table, int hash, const char *key, const void *data,
+ void (*destroy)(void *))
+{
+ struct hash_elem *ptr = table->table[hash];
+ struct hash_elem **last = &table->table[hash];
+
+ while (ptr) {
+ if ((data == ptr->data || !data) && m_strcmp(ptr->key, key) == 0) {
+ *last = ptr->next;
+ if (destroy)
+ destroy (ptr->data);
+ p_delete(&ptr);
+
+ ptr = *last;
+ } else {
+ last = &ptr->next;
+ ptr = ptr->next;
+ }
+ }
+}
+
+/* ptr pointer to the hash table to be freed
+ * destroy() function to call to free the ->data member (optional)
+ */
+void hash_destroy(HASH **ptr, void (*destroy)(void *))
+{
+ int i;
+ HASH *pptr = *ptr;
+ struct hash_elem *elem, *tmp;
+
+ for (i = 0; i < pptr->nelem; i++) {
+ for (elem = pptr->table[i]; elem;) {
+ tmp = elem;
+ elem = elem->next;
+ if (destroy)
+ destroy (tmp->data);
+ p_delete(&tmp);
+ }
+ }
+ p_delete(&pptr->table);
+ p_delete(ptr);
+}
+
+void hash_map(HASH *table,
+ void (*mapfunc)(const char* key, void* data, unsigned long more),
+ unsigned long more)
+{
+ int i;
+
+ if (!table || !mapfunc)
+ return;
+
+ for (i = 0; i < table->nelem; i++) {
+ struct hash_elem *elem;
+
+ for (elem = table->table[i]; elem; elem = elem->next) {
+ mapfunc (elem->key, elem->data, more);
+ }
+ }
+}