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, unsigned int factor,
   8                     unsigned int (*myhashf)(const void *key),
   9                     int (*mycmpf)(const void *arg1, const void *arg2),
  10                     void (*myprintf)(const void *key, const void *data))
  11 {
  12     unsigned int 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     unsigned int i;
  40
  41     for (i = 0; i < htable->ht_size; i++) {
  42         phead = &htable->ht_table[i];
  43         while (TAILQ_FIRST(phead) != NULL) {
  44             pnode = TAILQ_FIRST(phead);
  45             TAILQ_REMOVE(phead, TAILQ_FIRST(phead), hn_next);
  46             free(pnode);
  47         }
  48     }
  49
  50     free(htable->ht_table);
  51 }
  52
  53 htret_t htable_free_obj(htable_t *htable, void *key, htfree_t htfree)
  54 {
  55     hhead_t *phead;
  56     hnode_t *pnode;
  57     unsigned int hash;
  58
  59     /* Calculate hash */
  60     hash = htable->ht_hashf(key);
  61
  62     /* Search across chain if there is an entry with the
  63        key we are looking. If there is, free its contents. */
  64     phead = &htable->ht_table[hash & (htable->ht_size - 1)];
  65     TAILQ_FOREACH(pnode, phead, hn_next) {
  66         if (htable->ht_cmpf(pnode->hn_key, key) == 0) {
  67             TAILQ_REMOVE(phead, pnode, hn_next);
  68             if (htfree & HT_FREEKEY)
  69                 free(pnode->hn_key);
  70             if (htfree & HT_FREEDATA)
  71                 free(pnode->hn_data);
  72             free(pnode);
  73             htable->ht_used--;
  74             return HT_OK;
  75         }
  76     }
  77
  78     return HT_NOTFOUND;
  79 }
  80
  81 void htable_free_all_obj(htable_t *htable, htfree_t htfree)
  82 {
  83     hhead_t *phead;
  84     hnode_t *pnode;
  85     unsigned int i;
  86
  87     for (i = 0; i < htable->ht_size; i++) {
  88         phead = &htable->ht_table[i];
  89         TAILQ_FOREACH(pnode, phead, hn_next) {
  90             if (htfree & HT_FREEKEY)
  91                 free(pnode->hn_key);
  92             if (htfree & HT_FREEDATA)
  93                 free(pnode->hn_data);
  94         }
  95     }
  96 }
  97
  98 htret_t htable_grow(htable_t *htable)
  99 {
 100     hhead_t *pcurhead, *pnewhead, *poldhead;
 101     hnode_t *pnode;
 102     unsigned int i, newhash, newsize;
 103
 104     /* Allocate memory for new hash table */
 105     newsize = 2 * htable->ht_size;
 106     if ((pnewhead = malloc(newsize * sizeof *pnewhead)) == NULL)
 107         return HT_NOMEM;
 108
 109     /* Initialize tailqs */
 110     for (i = 0; i < newsize; i++)
 111         TAILQ_INIT(&pnewhead[i]);
 112
 113     poldhead = htable->ht_table;
 114
 115     for (i = 0; i < htable->ht_size; i++) {
 116         pcurhead = &poldhead[i];
 117         while ((pnode = TAILQ_FIRST(pcurhead)) != NULL) {
 118             newhash = htable->ht_hashf(pnode->hn_key);
 119             TAILQ_REMOVE(pcurhead, pnode, hn_next);
 120             TAILQ_INSERT_TAIL(&pnewhead[newhash & (newsize - 1)], pnode, hn_next);
 121         }
 122     }
 123
 124     /* Free old table */
 125     free(htable->ht_table);
 126
 127     /* Set new table parameters */
 128     htable->ht_table = pnewhead;
 129     htable->ht_size = newsize;
 130     htable->ht_limit = htable->ht_factor * newsize;
 131
 132     return HT_OK;
 133 }
 134
 135 htret_t htable_insert(htable_t *htable, void *key, void *data)
 136 {
 137     hhead_t *phead;
 138     hnode_t *pnode;
 139     unsigned int hash;
 140
 141     /* Calculate hash */
 142     hash = htable->ht_hashf(key);
 143
 144     /* Search across chain if there is already an entry with the same key. */
 145     phead = &htable->ht_table[hash & (htable->ht_size - 1)];
 146     TAILQ_FOREACH(pnode, phead, hn_next)
 147         if (htable->ht_cmpf(pnode->hn_key, key) == 0)
 148             return HT_EXISTS;
 149
 150     /* Allocate memory for new entry */
 151     if ((pnode = malloc(sizeof *pnode)) == NULL)
 152         return HT_NOMEM;
 153     pnode->hn_key = key;
 154     pnode->hn_data = data;
 155
 156     TAILQ_INSERT_TAIL(phead, pnode, hn_next);
 157
 158     /* If used items exceeds limit, grow the table */
 159     if (++htable->ht_used > htable->ht_limit)
 160         htable_grow(htable);
 161
 162     return HT_OK;
 163 }
 164
 165 htret_t htable_remove(htable_t *htable, const void *key)
 166 {
 167     hhead_t *phead;
 168     hnode_t *pnode;
 169     unsigned int hash;
 170
 171     /* Calculate hash */
 172     hash = htable->ht_hashf(key);
 173
 174     /* Search across chain if there is an entry with the
 175     key we are looking. If there is, remove it. */
 176     phead = &htable->ht_table[hash & (htable->ht_size - 1)];
 177     TAILQ_FOREACH(pnode, phead, hn_next) {
 178         if (htable->ht_cmpf(pnode->hn_key, key) == 0) {
 179             TAILQ_REMOVE(phead, pnode, hn_next);
 180             free(pnode);
 181             htable->ht_used--;
 182             return HT_OK;
 183         }
 184     }
 185
 186     return HT_NOTFOUND;
 187 }
 188
 189 void *htable_search(const htable_t *htable, const void *key)
 190 {
 191     const hhead_t *phead;
 192     const hnode_t *pnode;
 193     unsigned int hash;
 194
 195     /* Calculate hash */
 196     hash = htable->ht_hashf(key);
 197
 198     phead = &htable->ht_table[hash & (htable->ht_size - 1)];
 199     TAILQ_FOREACH(pnode, phead, hn_next)
 200         if (htable->ht_cmpf(pnode->hn_key, key) == 0)
 201             return pnode->hn_data;
 202
 203     return NULL;
 204 }
 205
 206 void htable_print(const htable_t *htable)
 207 {
 208     const hhead_t *phead;
 209     const hnode_t *pnode;
 210     unsigned int i;
 211
 212     for (i = 0; i < htable->ht_size; i++) {
 213         phead = &htable->ht_table[i];
 214         TAILQ_FOREACH(pnode, phead, hn_next)
 215              htable->ht_printf(pnode->hn_key, pnode->hn_data);
 216         if (TAILQ_FIRST(&htable->ht_table[i]) != NULL)
 217             printf("\n");
 218     }
 219 }
 220
 221 size_t htable_get_size(const htable_t *htable)
 222 {
 223     return htable->ht_size;
 224 }
 225
 226 unsigned int htable_get_used(const htable_t *htable)
 227 {
 228     return htable->ht_used;
 229 }
 230
 231 void htable_traverse(const htable_t *htable, void (*pfunc)(void *data))
 232 {
 233     const hhead_t *phead;
 234     const hnode_t *pnode;
 235     unsigned int i;
 236
 237     for (i = 0; i < htable->ht_size; i++) {
 238         phead = &htable->ht_table[i];
 239         TAILQ_FOREACH(pnode, phead, hn_next)
 240             pfunc(pnode->hn_data);
 241     }
 242 }
 243
 244 const hnode_t *htable_get_first_elm(const htable_t *htable, unsigned int *pos)
 245 {
 246     const hhead_t *phead;
 247     unsigned int i;
 248
 249     for (i = 0; i < htable->ht_size; i++) {
 250         ++*pos;
 251         phead = &htable->ht_table[i];
 252         if (TAILQ_FIRST(phead) != NULL)
 253             return TAILQ_FIRST(phead);
 254     }
 255
 256     /* We have traversed all elements. Nothing left. */
 257     return NULL;
 258 }
 259
 260 const hnode_t *htable_get_next_elm(const htable_t *htable, unsigned int *pos, const hnode_t *pnode)
 261 {
 262     const hhead_t *phead;
 263     unsigned int i;
 264
 265     if (TAILQ_NEXT(pnode, hn_next) != NULL) {
 266         /* Don't increase pos since we are stack in an horizontal chain,
 267            being still at the same 'height' which is what pos represents anyway  */
 268         return TAILQ_NEXT(pnode, hn_next);
 269     }
 270     else {
 271         for (i = *pos; i < htable->ht_size; i++) {
 272             ++*pos;
 273             phead = &htable->ht_table[i];
 274             if (TAILQ_FIRST(phead) != NULL)
 275                 return TAILQ_FIRST(phead);
 276         }
 277         /* We have traversed all elements. Nothing left. */
 278         return NULL;
 279     }
 280 }