lib-lib/hash.c

   1 /*
   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.
   6  *
   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.
  11  *
  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,
  15  *  MA 02110-1301, USA.
  16  *
  17  *  Copyright © 2006 Pierre Habouzit
  18  */
  19
  20 /*
  21  * Copyright notice from original mutt:
  22  * Copyright (C) 1996-2000 Michael R. Elkins <me@mutt.org>
  23  */
  24
  25 #include "lib-lib.h"
  26
  27 #define SOMEPRIME 149711
  28
  29 int hash_string(const unsigned char *s, int n)
  30 {
  31     unsigned h = 0;
  32
  33     while (*s) {
  34         h += (h << 7) + *s++;
  35     }
  36
  37     return (h * SOMEPRIME) % n;
  38 }
  39
  40 hash_t *hash_init(hash_t *table, int nelem, int allow_dup)
  41 {
  42     table->dupes    = allow_dup;
  43     table->nelem    = MIN(nelem, 2);
  44     table->curnelem = 0;
  45     table->table    = p_new(struct hash_elem *, table->nelem);
  46     return table;
  47 }
  48
  49 /* ptr          pointer to the hash table to be freed
  50  * destroy()    function to call to free the ->data member (optional)
  51  */
  52 void hash_wipe(hash_t *h, void (*dtor)(void *))
  53 {
  54     int i;
  55
  56     for (i = 0; i < h->nelem; i++) {
  57         struct hash_elem *elem, *tmp;
  58
  59         for (elem = h->table[i]; elem;) {
  60             tmp = elem;
  61             elem = elem->next;
  62             if (dtor)
  63                 dtor(tmp->data);
  64             p_delete(&tmp);
  65         }
  66     }
  67     p_delete(&h->table);
  68 }
  69
  70 void hash_resize(hash_t *ptr, int nelem)
  71 {
  72     hash_t table;
  73     int i;
  74
  75     /* XXX hack: we know the has was correct, no dupe checks is fater */
  76     hash_init(&table, nelem, 1);
  77
  78     for (i = 0; i < ptr->nelem; i++) {
  79         struct hash_elem *elem, *tmp;
  80         for (elem = ptr->table[i]; elem;) {
  81             tmp = elem;
  82             elem = elem->next;
  83             hash_insert(&table, tmp->key, tmp->data);
  84             p_delete(&tmp);
  85         }
  86     }
  87
  88     p_delete(&ptr->table);
  89     ptr->nelem = table.nelem;
  90     ptr->table = table.table;
  91 }
  92
  93 /* table        hash table to update
  94  * key          key to hash on
  95  * data         data to associate with `key'
  96  * allow_dup    if nonzero, duplicate keys are allowed in the table
  97  */
  98 int hash_insert(hash_t *table, const char *key, void *data)
  99 {
 100     struct hash_elem *ptr;
 101     int h;
 102
 103     ptr = p_new(struct hash_elem, 1);
 104     h = hash_string((unsigned char *)key, table->nelem);
 105     ptr->key = key;
 106     ptr->data = data;
 107
 108     if (table->dupes) {
 109         ptr->next = table->table[h];
 110         table->table[h] = ptr;
 111         table->curnelem++;
 112     } else {
 113         struct hash_elem **e;
 114
 115         for (e = &table->table[h]; *e; e = &(*e)->next) {
 116             int r = m_strcmp((*e)->key, key);
 117
 118             if (r == 0) {
 119                 p_delete(&ptr);
 120                 return (-1);
 121             }
 122             if (r > 0)
 123                 break;
 124         }
 125         ptr->next = *e;
 126         *e = ptr;
 127         table->curnelem++;
 128     }
 129     return h;
 130 }
 131
 132 void *hash_find(const hash_t *table, const char *key)
 133 {
 134     int hash = hash_string((unsigned char*)key, table->nelem);
 135     struct hash_elem *ptr;
 136
 137     for (ptr = table->table[hash]; ptr; ptr = ptr->next) {
 138         if (m_strcmp(key, ptr->key) == 0)
 139             return (ptr->data);
 140     }
 141     return NULL;
 142 }
 143
 144 void hash_remove(hash_t *table, const char *key, const void *data,
 145                  void (*destroy)(void *))
 146 {
 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];
 150
 151     while (ptr) {
 152         if ((data == ptr->data || !data) && m_strcmp(ptr->key, key) == 0) {
 153             *last = ptr->next;
 154             if (destroy)
 155                 destroy (ptr->data);
 156             p_delete(&ptr);
 157
 158             ptr = *last;
 159         } else {
 160             last = &ptr->next;
 161             ptr = ptr->next;
 162         }
 163     }
 164 }
 165
 166 void hash_map(hash_t *table,
 167               void (*mapfunc)(const char* key, void* data, unsigned long more),
 168               unsigned long more)
 169 {
 170     int i;
 171
 172     if (!table || !mapfunc)
 173         return;
 174
 175     for (i = 0; i < table->nelem; i++) {
 176         struct hash_elem *elem;
 177
 178         for (elem = table->table[i]; elem; elem = elem->next) {
 179             mapfunc (elem->key, elem->data, more);
 180         }
 181     }
 182 }