src/hashtable.c

   1 /*
   2  * Copyright (c) 2009 Petri Lehtinen <petri@digip.org>
   3  *
   4  * This library is free software; you can redistribute it and/or modify
   5  * it under the terms of the MIT license. See LICENSE for details.
   6  */
   7
   8 #include <stdlib.h>
   9 #include "hashtable.h"
  10
  11 typedef struct hashtable_list list_t;
  12 typedef struct hashtable_pair pair_t;
  13 typedef struct hashtable_bucket bucket_t;
  14
  15 #define container_of(ptr_, type_, member_)                      \
  16     ((type_ *)((char *)ptr_ - (size_t)&((type_ *)0)->member_))
  17
  18 #define list_to_pair(list_)  container_of(list_, pair_t, list)
  19
  20 static inline void list_init(list_t *list)
  21 {
  22     list->next = list;
  23     list->prev = list;
  24 }
  25
  26 static inline void list_insert(list_t *list, list_t *node)
  27 {
  28     node->next = list;
  29     node->prev = list->prev;
  30     list->prev->next = node;
  31     list->prev = node;
  32 }
  33
  34 static inline void list_remove(list_t *list)
  35 {
  36     list->prev->next = list->next;
  37     list->next->prev = list->prev;
  38 }
  39
  40 static inline int bucket_is_empty(hashtable_t *hashtable, bucket_t *bucket)
  41 {
  42     return bucket->first == &hashtable->list && bucket->first == bucket->last;
  43 }
  44
  45 static void insert_to_bucket(hashtable_t *hashtable, bucket_t *bucket,
  46                              list_t *list)
  47 {
  48     if(bucket_is_empty(hashtable, bucket))
  49     {
  50         list_insert(&hashtable->list, list);
  51         bucket->first = bucket->last = list;
  52     }
  53     else
  54     {
  55         list_insert(bucket->first, list);
  56         bucket->first = list;
  57     }
  58 }
  59
  60 static unsigned int primes[] = {
  61     5, 13, 23, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
  62     49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
  63     12582917, 25165843, 50331653, 100663319, 201326611, 402653189,
  64     805306457, 1610612741
  65 };
  66 static const unsigned int num_primes = sizeof(primes) / sizeof(unsigned int);
  67
  68 static inline unsigned int num_buckets(hashtable_t *hashtable)
  69 {
  70     return primes[hashtable->num_buckets];
  71 }
  72
  73
  74 static pair_t *hashtable_find_pair(hashtable_t *hashtable, bucket_t *bucket,
  75                                    const void *key, unsigned int hash)
  76 {
  77     list_t *list;
  78     pair_t *pair;
  79
  80     if(bucket_is_empty(hashtable, bucket))
  81         return NULL;
  82
  83     list = bucket->first;
  84     while(1)
  85     {
  86         pair = list_to_pair(list);
  87         if(pair->hash == hash && hashtable->cmp_keys(pair->key, key))
  88             return pair;
  89
  90         if(list == bucket->last)
  91             break;
  92
  93         list = list->next;
  94     }
  95
  96     return NULL;
  97 }
  98
  99 /* returns 0 on success, -1 if key was not found */
 100 static int hashtable_do_del(hashtable_t *hashtable,
 101                             const void *key, unsigned int hash)
 102 {
 103     pair_t *pair;
 104     bucket_t *bucket;
 105     unsigned int index;
 106
 107     index = hash % num_buckets(hashtable);
 108     bucket = &hashtable->buckets[index];
 109
 110     pair = hashtable_find_pair(hashtable, bucket, key, hash);
 111     if(!pair)
 112         return -1;
 113
 114     if(&pair->list == bucket->first && &pair->list == bucket->last)
 115         bucket->first = bucket->last = &hashtable->list;
 116
 117     else if(&pair->list == bucket->first)
 118         bucket->first = pair->list.next;
 119
 120     else if(&pair->list == bucket->last)
 121         bucket->last = pair->list.prev;
 122
 123     list_remove(&pair->list);
 124
 125     if(hashtable->free_key)
 126         hashtable->free_key(pair->key);
 127     if(hashtable->free_value)
 128         hashtable->free_value(pair->value);
 129
 130     free(pair);
 131     hashtable->size--;
 132
 133     return 0;
 134 }
 135
 136 static int hashtable_do_rehash(hashtable_t *hashtable)
 137 {
 138     list_t *list, *next;
 139     pair_t *pair;
 140     unsigned int i, index, new_size;
 141
 142     free(hashtable->buckets);
 143
 144     hashtable->num_buckets++;
 145     new_size = num_buckets(hashtable);
 146
 147     hashtable->buckets = malloc(new_size * sizeof(bucket_t));
 148     if(!hashtable->buckets)
 149         return -1;
 150
 151     for(i = 0; i < num_buckets(hashtable); i++)
 152     {
 153         hashtable->buckets[i].first = hashtable->buckets[i].last =
 154             &hashtable->list;
 155     }
 156
 157     list = hashtable->list.next;
 158     list_init(&hashtable->list);
 159
 160     for(; list != &hashtable->list; list = next) {
 161         next = list->next;
 162         pair = list_to_pair(list);
 163         index = pair->hash % new_size;
 164         insert_to_bucket(hashtable, &hashtable->buckets[index], &pair->list);
 165     }
 166
 167     return 0;
 168 }
 169
 170
 171 hashtable_t *hashtable_create(key_hash_fn hash_key, key_cmp_fn cmp_keys,
 172                               free_fn free_key, free_fn free_value)
 173 {
 174     hashtable_t *hashtable = malloc(sizeof(hashtable_t));
 175     if(!hashtable)
 176         return NULL;
 177
 178     if(hashtable_init(hashtable, hash_key, cmp_keys, free_key, free_value))
 179     {
 180         free(hashtable);
 181         return NULL;
 182     }
 183
 184     return hashtable;
 185 }
 186
 187 void hashtable_destroy(hashtable_t *hashtable)
 188 {
 189     hashtable_close(hashtable);
 190     free(hashtable);
 191 }
 192
 193 int hashtable_init(hashtable_t *hashtable,
 194                    key_hash_fn hash_key, key_cmp_fn cmp_keys,
 195                    free_fn free_key, free_fn free_value)
 196 {
 197     unsigned int i;
 198
 199     hashtable->size = 0;
 200     hashtable->num_buckets = 0;  /* index to primes[] */
 201     hashtable->buckets = malloc(num_buckets(hashtable) * sizeof(bucket_t));
 202     if(!hashtable->buckets)
 203         return -1;
 204
 205     list_init(&hashtable->list);
 206
 207     hashtable->hash_key = hash_key;
 208     hashtable->cmp_keys = cmp_keys;
 209     hashtable->free_key = free_key;
 210     hashtable->free_value = free_value;
 211
 212     for(i = 0; i < num_buckets(hashtable); i++)
 213     {
 214         hashtable->buckets[i].first = hashtable->buckets[i].last =
 215             &hashtable->list;
 216     }
 217
 218     return 0;
 219 }
 220
 221 void hashtable_close(hashtable_t *hashtable)
 222 {
 223     list_t *list, *next;
 224     pair_t *pair;
 225     for(list = hashtable->list.next; list != &hashtable->list; list = next)
 226     {
 227         next = list->next;
 228         pair = list_to_pair(list);
 229         if(hashtable->free_key)
 230             hashtable->free_key(pair->key);
 231         if(hashtable->free_value)
 232             hashtable->free_value(pair->value);
 233         free(pair);
 234     }
 235
 236     free(hashtable->buckets);
 237 }
 238
 239 int hashtable_set(hashtable_t *hashtable, void *key, void *value)
 240 {
 241     pair_t *pair;
 242     bucket_t *bucket;
 243     unsigned int hash, index;
 244
 245     hash = hashtable->hash_key(key);
 246
 247     /* if the key already exists, delete it */
 248     hashtable_do_del(hashtable, key, hash);
 249
 250     /* rehash if the load ratio exceeds 1 */
 251     if(hashtable->size >= num_buckets(hashtable))
 252         if(hashtable_do_rehash(hashtable))
 253             return -1;
 254
 255     pair = malloc(sizeof(pair_t));
 256     if(!pair)
 257         return -1;
 258
 259     pair->key = key;
 260     pair->value = value;
 261     pair->hash = hash;
 262     list_init(&pair->list);
 263
 264     index = hash % num_buckets(hashtable);
 265     bucket = &hashtable->buckets[index];
 266
 267     insert_to_bucket(hashtable, bucket, &pair->list);
 268
 269     hashtable->size++;
 270     return 0;
 271 }
 272
 273 void *hashtable_get(hashtable_t *hashtable, const void *key)
 274 {
 275     pair_t *pair;
 276     unsigned int hash;
 277     bucket_t *bucket;
 278
 279     hash = hashtable->hash_key(key);
 280     bucket = &hashtable->buckets[hash % num_buckets(hashtable)];
 281
 282     pair = hashtable_find_pair(hashtable, bucket, key, hash);
 283     if(!pair)
 284         return NULL;
 285
 286     return pair->value;
 287 }
 288
 289 int hashtable_del(hashtable_t *hashtable, const void *key)
 290 {
 291     unsigned int hash = hashtable->hash_key(key);
 292     return hashtable_do_del(hashtable, key, hash);
 293 }
 294
 295 void *hashtable_iter(hashtable_t *hashtable)
 296 {
 297     return hashtable_iter_next(hashtable, &hashtable->list);
 298 }
 299
 300 void *hashtable_iter_next(hashtable_t *hashtable, void *iter)
 301 {
 302     list_t *list = (list_t *)iter;
 303     if(list->next == &hashtable->list)
 304         return NULL;
 305     return list->next;
 306 }
 307
 308 void *hashtable_iter_key(void *iter)
 309 {
 310     pair_t *pair = list_to_pair((list_t *)iter);
 311     return pair->key;
 312 }
 313
 314 void *hashtable_iter_value(void *iter)
 315 {
 316     pair_t *pair = list_to_pair((list_t *)iter);
 317     return pair->value;
 318 }