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