dict.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include <assert.h>
   5
   6 #include "common.h"
   7
   8 /*
   9   Dictionary based on code by Morten Eriksen <mortene@sim.no>.
  10 */
  11
  12 struct dict_entry {
  13         unsigned int hash;
  14         void *key;
  15         void *value;
  16         struct dict_entry *next;
  17 };
  18
  19 /* #define DICTTABLESIZE 97 */
  20 #define DICTTABLESIZE 997       /* Semi-randomly selected prime number. */
  21 /* #define DICTTABLESIZE 9973 */
  22 /* #define DICTTABLESIZE 99991 */
  23 /* #define DICTTABLESIZE 999983 */
  24
  25 struct dict {
  26         struct dict_entry *buckets[DICTTABLESIZE];
  27         unsigned int (*key2hash) (void *);
  28         int (*key_cmp) (void *, void *);
  29 };
  30
  31 Dict *
  32 dict_init(unsigned int (*key2hash) (void *),
  33                        int (*key_cmp) (void *, void *)) {
  34         Dict *d;
  35         int i;
  36
  37         debug(DEBUG_FUNCTION, "dict_init()");
  38
  39         d = malloc(sizeof(Dict));
  40         if (!d) {
  41                 perror("malloc()");
  42                 exit(1);
  43         }
  44         for (i = 0; i < DICTTABLESIZE; i++) {   /* better use memset()? */
  45                 d->buckets[i] = NULL;
  46         }
  47         d->key2hash = key2hash;
  48         d->key_cmp = key_cmp;
  49         return d;
  50 }
  51
  52 void
  53 dict_clear(Dict *d) {
  54         int i;
  55         struct dict_entry *entry, *nextentry;
  56
  57         debug(DEBUG_FUNCTION, "dict_clear()");
  58         assert(d);
  59         for (i = 0; i < DICTTABLESIZE; i++) {
  60                 for (entry = d->buckets[i]; entry != NULL; entry = nextentry) {
  61                         nextentry = entry->next;
  62                         free(entry);
  63                 }
  64                 d->buckets[i] = NULL;
  65         }
  66         free(d);
  67 }
  68
  69 int
  70 dict_enter(Dict *d, void *key, void *value) {
  71         struct dict_entry *entry, *newentry;
  72         unsigned int hash;
  73         unsigned int bucketpos;
  74
  75         debug(DEBUG_FUNCTION, "dict_enter()");
  76
  77         hash = d->key2hash(key);
  78         bucketpos = hash % DICTTABLESIZE;
  79
  80         assert(d);
  81         newentry = malloc(sizeof(struct dict_entry));
  82         if (!newentry) {
  83                 perror("malloc");
  84                 exit(1);
  85         }
  86
  87         newentry->hash = hash;
  88         newentry->key = key;
  89         newentry->value = value;
  90         newentry->next = NULL;
  91
  92         entry = d->buckets[bucketpos];
  93         while (entry && entry->next)
  94                 entry = entry->next;
  95
  96         if (entry)
  97                 entry->next = newentry;
  98         else
  99                 d->buckets[bucketpos] = newentry;
 100
 101         debug(3, "new dict entry at %p[%d]: (%p,%p)", d, bucketpos, key, value);
 102         return 0;
 103 }
 104
 105 void *
 106 dict_find_entry(Dict *d, void *key) {
 107         unsigned int hash;
 108         unsigned int bucketpos;
 109         struct dict_entry *entry;
 110
 111         debug(DEBUG_FUNCTION, "dict_find_entry()");
 112
 113         hash = d->key2hash(key);
 114         bucketpos = hash % DICTTABLESIZE;
 115
 116         assert(d);
 117         for (entry = d->buckets[bucketpos]; entry; entry = entry->next) {
 118                 if (hash != entry->hash) {
 119                         continue;
 120                 }
 121                 if (!d->key_cmp(key, entry->key)) {
 122                         break;
 123                 }
 124         }
 125         return entry ? entry->value : NULL;
 126 }
 127
 128 void
 129 dict_apply_to_all(Dict *d,
 130                   void (*func) (void *key, void *value, void *data), void *data) {
 131         int i;
 132
 133         debug(DEBUG_FUNCTION, "dict_apply_to_all()");
 134
 135         if (!d) {
 136                 return;
 137         }
 138         for (i = 0; i < DICTTABLESIZE; i++) {
 139                 struct dict_entry *entry = d->buckets[i];
 140                 while (entry) {
 141                         func(entry->key, entry->value, data);
 142                         entry = entry->next;
 143                 }
 144         }
 145 }
 146
 147 /*****************************************************************************/
 148
 149 unsigned int
 150 dict_key2hash_string(void *key) {
 151         const char *s = (const char *)key;
 152         unsigned int total = 0, shift = 0;
 153
 154         assert(key);
 155         while (*s) {
 156                 total = total ^ ((*s) << shift);
 157                 shift += 5;
 158                 if (shift > 24)
 159                         shift -= 24;
 160                 s++;
 161         }
 162         return total;
 163 }
 164
 165 int
 166 dict_key_cmp_string(void *key1, void *key2) {
 167         assert(key1);
 168         assert(key2);
 169         return strcmp((const char *)key1, (const char *)key2);
 170 }
 171
 172 unsigned int
 173 dict_key2hash_int(void *key) {
 174         return (unsigned long)key;
 175 }
 176
 177 int
 178 dict_key_cmp_int(void *key1, void *key2) {
 179         return key1 - key2;
 180 }
 181
 182 Dict *
 183 dict_clone(Dict *old, void * (*key_clone)(void*), void * (*value_clone)(void*)) {
 184         Dict *d;
 185         int i;
 186
 187         debug(DEBUG_FUNCTION, "dict_clone()");
 188
 189         d = malloc(sizeof(Dict));
 190         if (!d) {
 191                 perror("malloc()");
 192                 exit(1);
 193         }
 194         memcpy(d, old, sizeof(Dict));
 195         for (i = 0; i < DICTTABLESIZE; i++) {   /* better use memset()? */
 196                 struct dict_entry *de_old;
 197                 struct dict_entry **de_new;
 198
 199                 de_old = old->buckets[i];
 200                 de_new = &d->buckets[i];
 201                 while (de_old) {
 202                         *de_new = malloc(sizeof(struct dict_entry));
 203                         if (!*de_new) {
 204                                 perror("malloc()");
 205                                 exit(1);
 206                         }
 207                         memcpy(*de_new, de_old, sizeof(struct dict_entry));
 208                         (*de_new)->key = key_clone(de_old->key);
 209                         (*de_new)->value = value_clone(de_old->value);
 210                         de_new = &(*de_new)->next;
 211                         de_old = de_old->next;
 212                 }
 213         }
 214         return d;
 215 }