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
 171     return HT_OK;
 172 }
 173
 174 htret_t htable_remove(htable_t *htable, const void *key)
 175 {
 176     hhead_t *phead;
 177     hnode_t *pnode;
 178     size_t hash;
 179
 180     /* Calculate hash */
 181     hash = htable->ht_hashf(key);
 182
 183     /* Search across chain if there is an entry with the
 184     key we are looking. If there is, remove it. */
 185     phead = &htable->ht_table[hash & (htable->ht_size - 1)];
 186     TAILQ_FOREACH(pnode, phead, hn_next) {
 187         if (htable->ht_cmpf(pnode->hn_key, key) == 0) {
 188             TAILQ_REMOVE(phead, pnode, hn_next);
 189             free(pnode);
 190             htable->ht_used--;
 191             return HT_OK;
 192         }
 193     }
 194
 195     return HT_NOTFOUND;
 196 }
 197
 198 void *htable_search(const htable_t *htable, const void *key)
 199 {
 200     const hhead_t *phead;
 201     const hnode_t *pnode;
 202     size_t hash;
 203
 204     /* Calculate hash */
 205     hash = htable->ht_hashf(key);
 206
 207     phead = &htable->ht_table[hash & (htable->ht_size - 1)];
 208     TAILQ_FOREACH(pnode, phead, hn_next)
 209         if (htable->ht_cmpf(pnode->hn_key, key) == 0)
 210             return pnode->hn_data;
 211
 212     return NULL;
 213 }
 214
 215 void htable_print(const htable_t *htable)
 216 {
 217     const hhead_t *phead;
 218     const hnode_t *pnode;
 219     size_t i;
 220
 221     for (i = 0; i < htable->ht_size; i++) {
 222         phead = &htable->ht_table[i];
 223         TAILQ_FOREACH(pnode, phead, hn_next)
 224              htable->ht_printf(pnode->hn_key, pnode->hn_data);
 225         if (TAILQ_FIRST(&htable->ht_table[i]) != NULL)
 226             printf("\n");
 227     }
 228 }
 229
 230 size_t htable_get_size(const htable_t *htable)
 231 {
 232     return htable->ht_size;
 233 }
 234
 235 size_t htable_get_used(const htable_t *htable)
 236 {
 237     return htable->ht_used;
 238 }
 239
 240 void htable_traverse(const htable_t *htable, void (*pfunc)(void *data))
 241 {
 242     const hhead_t *phead;
 243     const hnode_t *pnode;
 244     size_t i;
 245
 246     for (i = 0; i < htable->ht_size; i++) {
 247         phead = &htable->ht_table[i];
 248         TAILQ_FOREACH(pnode, phead, hn_next)
 249             pfunc(pnode->hn_data);
 250     }
 251 }
 252
 253 const hnode_t *htable_get_next_elm(const htable_t *htable, size_t *pos, const hnode_t *pnode)
 254 {
 255     const hhead_t *phead;
 256     size_t i;
 257
 258     /* Is pos out of bound ? If yes, return immediately */
 259     if (*pos > (htable->ht_size - 1))
 260         return NULL;
 261
 262     /* Find first usable element, if we were not supplied with one */
 263     if (pos == 0 || pnode == NULL) {
 264         for (i = *pos; i < htable->ht_size; i++) {
 265             ++*pos;
 266             phead = &htable->ht_table[i];
 267             if (TAILQ_FIRST(phead) != NULL)
 268                 return TAILQ_FIRST(phead);
 269         }
 270     }
 271
 272     /* Are we on a chain ? */
 273     if (TAILQ_NEXT(pnode, hn_next) != NULL) {
 274         /* Don't increase pos since we are stack in an horizontal chain,
 275            being still at the same 'height' which is what pos represents anyway  */
 276         return TAILQ_NEXT(pnode, hn_next);
 277     }
 278     else {
 279         for (i = *pos; i < htable->ht_size; i++) {
 280             ++*pos;
 281             phead = &htable->ht_table[i];
 282             if (TAILQ_FIRST(phead) != NULL)
 283                 return TAILQ_FIRST(phead);
 284         }
 285         /* We have traversed all elements. Nothing left. */
 286         return NULL;
 287     }
 288 }