genstructs/htable/htable.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <sys/queue.h>
   4
   5 #include "htable.h"
   6
   7 htret_t htable_init(htable_t *htable, size_t size, size_t factor,
   8                     hashf_t *myhashf,
   9                     cmpf_t *mycmpf,
  10                     printf_t *myprintf)
  11 {
  12     size_t i;
  13
  14     /* Allocate memory for `size' tailq headers */
  15     if ((htable->ht_table = malloc(size * sizeof *htable->ht_table)) == NULL)
  16         return HT_NOMEM;
  17
  18     /* Initialize tailqs */
  19     for (i = 0; i < size; i++)
  20         TAILQ_INIT(&htable->ht_table[i]);
  21
  22     htable->ht_size = size;    /* size must be a power of 2 */
  23     htable->ht_used = 0;
  24     htable->ht_factor = factor;
  25     htable->ht_limit = factor * size;
  26
  27     /* Setup callback functions */
  28     htable->ht_hashf = myhashf;
  29     htable->ht_cmpf = mycmpf;
  30     htable->ht_printf = myprintf;
  31
  32     return HT_OK;
  33 }
  34
  35 void htable_free(htable_t *htable)
  36 {
  37     hhead_t *phead;
  38     hnode_t *pnode;
  39     size_t i;
  40
  41     for (i = 0; i < htable->ht_size; i++) {
  42         phead = &htable->ht_table[i];
  43         while ((pnode = TAILQ_FIRST(phead)) != NULL) {
  44             TAILQ_REMOVE(phead, pnode, hn_next);
  45             free(pnode);
  46         }
  47     }
  48
  49     free(htable->ht_table);
  50 }
  51
  52 htret_t htable_free_obj(htable_t *htable, void *key, htfree_t htfree)
  53 {
  54     hhead_t *phead;
  55     hnode_t *pnode;
  56     size_t hash;
  57
  58     /* Calculate hash */
  59     hash = htable->ht_hashf(key);
  60
  61     /*
  62      * Search across chain if there is an entry with the
  63      * key we are looking for. If there is, free its contents.
  64      */
  65     phead = &htable->ht_table[hash & (htable->ht_size - 1)];
  66     TAILQ_FOREACH(pnode, phead, hn_next) {
  67         if (htable->ht_cmpf(pnode->hn_key, key) == 0) {
  68             TAILQ_REMOVE(phead, pnode, hn_next);
  69             if (htfree & HT_FREEKEY)
  70                 free(pnode->hn_key);
  71             if (htfree & HT_FREEDATA)
  72                 free(pnode->hn_data);
  73             free(pnode);
  74             htable->ht_used--;
  75             return HT_OK;
  76         }
  77     }
  78
  79     return HT_NOTFOUND;
  80 }
  81
  82 void htable_free_all_obj(htable_t *htable, htfree_t htfree)
  83 {
  84     hhead_t *phead;
  85     hnode_t *pnode;
  86     size_t i;
  87
  88     for (i = 0; i < htable->ht_size; i++) {
  89         phead = &htable->ht_table[i];
  90         TAILQ_FOREACH(pnode, phead, hn_next) {
  91             if (htfree & HT_FREEKEY)
  92                 free(pnode->hn_key);
  93             if (htfree & HT_FREEDATA)
  94                 free(pnode->hn_data);
  95         }
  96     }
  97 }
  98
  99 htret_t htable_grow(htable_t *htable)
 100 {
 101     hhead_t *pcurhead, *pnewhead, *poldhead;
 102     hnode_t *pnode;
 103     size_t i, newhash, newsize;
 104
 105     /*
 106      * Allocate memory for new hash table
 107      * The new hash table is 2 times bigger than the old one
 108      */
 109     newsize = htable->ht_size << 1;
 110     if ((pnewhead = malloc(newsize * sizeof *pnewhead)) == NULL)
 111         return HT_NOMEM;
 112
 113     /* Initialize tailqs */
 114     for (i = 0; i < newsize; i++)
 115         TAILQ_INIT(&pnewhead[i]);
 116
 117     poldhead = htable->ht_table;
 118
 119     /*
 120      * Remove the entries from the old hash table,
 121      * rehash them in respect to the new hash table,
 122      * and add them to the new one
 123      */
 124     for (i = 0; i < htable->ht_size; i++) {
 125         pcurhead = &poldhead[i];
 126         while ((pnode = TAILQ_FIRST(pcurhead)) != NULL) {
 127             newhash = htable->ht_hashf(pnode->hn_key);
 128             TAILQ_REMOVE(pcurhead, pnode, hn_next);
 129             TAILQ_INSERT_TAIL(&pnewhead[newhash & (newsize - 1)], pnode, hn_next);
 130         }
 131     }
 132
 133     /* Free old table */
 134     free(htable->ht_table);
 135
 136     /* Set new table parameters */
 137     htable->ht_table = pnewhead;
 138     htable->ht_size = newsize;
 139     htable->ht_limit = htable->ht_factor * newsize;
 140
 141     return HT_OK;
 142 }
 143
 144 htret_t htable_insert(htable_t *htable, void *key, void *data)
 145 {
 146     hhead_t *phead;
 147     hnode_t *pnode;
 148     size_t hash;
 149
 150     /* Calculate hash */
 151     hash = htable->ht_hashf(key);
 152
 153     /* Search across chain if there is already an entry with the same key. */
 154     phead = &htable->ht_table[hash & (htable->ht_size - 1)];
 155     TAILQ_FOREACH(pnode, phead, hn_next)
 156         if (htable->ht_cmpf(pnode->hn_key, key) == 0)
 157             return HT_EXISTS;
 158
 159     /* Allocate memory for new entry */
 160     if ((pnode = malloc(sizeof *pnode)) == NULL)
 161         return HT_NOMEM;
 162     pnode->hn_key = key;
 163     pnode->hn_data = data;
 164
 165     TAILQ_INSERT_TAIL(phead, pnode, hn_next);
 166
 167     /* If used items exceed limit, grow the table */
 168     if (++htable->ht_used > htable->ht_limit) {
 169         htable_grow(htable);
 170         #ifdef HTABLE_STATS
 171         htable->ht_grows++;
 172         #endif
 173     }
 174
 175     return HT_OK;
 176 }
 177
 178 htret_t htable_remove(htable_t *htable, const void *key)
 179 {
 180     hhead_t *phead;
 181     hnode_t *pnode;
 182     size_t hash;
 183
 184     /* Calculate hash */
 185     hash = htable->ht_hashf(key);
 186
 187     /*
 188      * Search across chain if there is an entry with the
 189      * key we are looking. If there is, delete it.
 190      */
 191     phead = &htable->ht_table[hash & (htable->ht_size - 1)];
 192     TAILQ_FOREACH(pnode, phead, hn_next) {
 193         if (htable->ht_cmpf(pnode->hn_key, key) == 0) {
 194             TAILQ_REMOVE(phead, pnode, hn_next);
 195             free(pnode);
 196             htable->ht_used--;
 197             return HT_OK;
 198         }
 199     }
 200
 201     return HT_NOTFOUND;
 202 }
 203
 204 void *htable_search(const htable_t *htable, const void *key)
 205 {
 206     const hhead_t *phead;
 207     const hnode_t *pnode;
 208     size_t hash;
 209
 210     /* Calculate hash */
 211     hash = htable->ht_hashf(key);
 212
 213     phead = &htable->ht_table[hash & (htable->ht_size - 1)];
 214     TAILQ_FOREACH(pnode, phead, hn_next)
 215         if (htable->ht_cmpf(pnode->hn_key, key) == 0)
 216             return pnode->hn_data;
 217
 218     return NULL;
 219 }
 220
 221 void htable_print(const htable_t *htable)
 222 {
 223     const hhead_t *phead;
 224     const hnode_t *pnode;
 225     size_t i;
 226
 227     for (i = 0; i < htable->ht_size; i++) {
 228         phead = &htable->ht_table[i];
 229         TAILQ_FOREACH(pnode, phead, hn_next)
 230              htable->ht_printf(pnode->hn_key, pnode->hn_data);
 231         if (TAILQ_FIRST(&htable->ht_table[i]) != NULL)
 232             printf("\n");
 233     }
 234 }
 235
 236 size_t htable_get_size(const htable_t *htable)
 237 {
 238     return htable->ht_size;
 239 }
 240
 241 size_t htable_get_used(const htable_t *htable)
 242 {
 243     return htable->ht_used;
 244 }
 245
 246 void htable_traverse(const htable_t *htable, void (*pfunc)(void *data))
 247 {
 248     const hhead_t *phead;
 249     const hnode_t *pnode;
 250     size_t i;
 251
 252     for (i = 0; i < htable->ht_size; i++) {
 253         phead = &htable->ht_table[i];
 254         TAILQ_FOREACH(pnode, phead, hn_next)
 255             pfunc(pnode->hn_data);
 256     }
 257 }
 258
 259 const hnode_t *htable_get_next_elm(const htable_t *htable, size_t *pos, const hnode_t *pnode)
 260 {
 261     const hhead_t *phead;
 262     size_t i;
 263
 264     /* Is pos out of bound ? If yes, return immediately */
 265     if (*pos > (htable->ht_size - 1))
 266         return NULL;
 267
 268     /* Find first usable element, if we were not supplied with one */
 269     if (pos == 0 || pnode == NULL) {
 270         for (i = *pos; i < htable->ht_size; i++) {
 271             ++*pos;
 272             phead = &htable->ht_table[i];
 273             if (TAILQ_FIRST(phead) != NULL)
 274                 return TAILQ_FIRST(phead);
 275         }
 276         /* We have traversed all elements. Nothing left. */
 277         return NULL;
 278     }
 279
 280     /* Are we on a chain ? */
 281     if (TAILQ_NEXT(pnode, hn_next) != NULL) {
 282         /* Don't increase pos since we are stack in an horizontal chain,
 283            being still at the same 'height' which is what pos represents anyway  */
 284         return TAILQ_NEXT(pnode, hn_next);
 285     }
 286     else {
 287         for (i = *pos; i < htable->ht_size; i++) {
 288             ++*pos;
 289             phead = &htable->ht_table[i];
 290             if (TAILQ_FIRST(phead) != NULL)
 291                 return TAILQ_FIRST(phead);
 292         }
 293         /* We have traversed all elements. Nothing left. */
 294         return NULL;
 295     }
 296 }
 297
 298 #ifdef HTABLE_STATS
 299 size_t htable_get_grows(const htable_t *htable)
 300 {
 301     return htable->ht_grows;
 302 }
 303 #endif