hash.c

   1 #include <stdlib.h>
   2 #include <string.h>
   3 #include "hash.h"
   4 #include "utils.h"
   5
   6
   7 struct hash *hash_init(long (*datahash) (void *data),
   8                        long (*keyhash) (void *data),
   9                        int (*datacmp) (void *data, void *key),
  10                        int size)
  11 {
  12         struct hash *hash = xmalloc(sizeof(struct hash));
  13         hash->datahash = datahash;
  14         hash->keyhash = keyhash;
  15         hash->datacmp = datacmp;
  16         hash->size = size;
  17         hash->collisions = 0;
  18         hash->table = xmalloc(size * sizeof(struct entry *));
  19         memset(hash->table, 0, size * sizeof(struct entry *));
  20         return hash;
  21 }
  22
  23 long str_hash(void *p)
  24 {
  25         char *s = p;
  26         long x = *s << 7;
  27         while (*s)
  28                 x = (1000003 * x) ^ *s++;
  29         return x;
  30 }
  31
  32 static long hash_key(struct hash *hash, long value)
  33 {
  34         return (value >= 0 ? value : -value) % hash->size;
  35 }
  36
  37 static void hash_grow(struct hash *hash, int size);
  38
  39 void hash_put(struct hash *hash, void *data)
  40 {
  41         long i = hash_key(hash, hash->datahash(data));
  42         struct entry *newdata = xmalloc(sizeof(struct entry *));
  43         newdata->data = data;
  44         if (hash->table[i])
  45                 hash->collisions++;
  46         newdata->next = hash->table[i];
  47         hash->table[i] = newdata;
  48         if (hash->collisions > hash->size / 2)
  49                 hash_grow(hash, hash->size * 2);
  50 }
  51
  52 void *hash_get(struct hash *hash, void *key)
  53 {
  54         struct entry *cur = hash->table[hash_key(hash, hash->keyhash(key))];
  55         while (cur) {
  56                 if (!hash->datacmp(cur->data, key))
  57                         return cur->data;
  58                 cur = cur->next;
  59         }
  60         return NULL;
  61 }
  62
  63 static void entry_walk(struct hash *hash,
  64                             void (*callback) (struct entry *, void *data),
  65                             void *data)
  66 {
  67         int i;
  68         for (i = 0; i < hash->size; i++) {
  69                 struct entry *cur = hash->table[i];
  70                 while (cur) {
  71                         struct entry *old = cur;
  72                         cur = cur->next;
  73                         callback(old, data);
  74                 }
  75         }
  76 }
  77
  78 static void free_entry(struct entry *entry, void *data)
  79 {
  80         free(entry);
  81 }
  82
  83 void hash_release(struct hash *hash)
  84 {
  85         entry_walk(hash, free_entry, NULL);
  86         free(hash->table);
  87         free(hash);
  88 }
  89
  90 static void copy_and_free_entry(struct entry *entry, void *newhash)
  91 {
  92         hash_put(newhash, entry->data);
  93         free(entry);
  94 }
  95
  96 static void hash_grow(struct hash *hash, int size)
  97 {
  98         struct hash *newhash = hash_init(hash->datahash, hash->keyhash,
  99                                          hash->datacmp, size);
 100         entry_walk(hash, copy_and_free_entry, newhash);
 101         free(hash->table);
 102         memcpy(hash, newhash, sizeof(*hash));
 103         free(newhash);
 104 }
 105
 106 struct walk_data {
 107         void (*walk)(void *data, void *arg)     ;
 108         void *arg;
 109 };
 110
 111 static void call_entry(struct entry *entry, void *data)
 112 {
 113         struct walk_data *walk_data = data;
 114         walk_data->walk(entry->data, walk_data->arg);
 115 }
 116
 117 void hash_walk(struct hash *hash,
 118                 void (*walk)(void *data, void *arg),
 119                 void *arg)
 120 {
 121         struct walk_data walk_data;
 122         walk_data.arg = arg;
 123         walk_data.walk = walk;
 124         entry_walk(hash, call_entry, &walk_data);
 125 }