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 (*hashf)(const void *key),
   9                     int (*cmpf)(const void *arg1, const void *arg2),
  10                     void (*printf)(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 = hashf;
  29     htable->ht_cmpf = cmpf;
  30     htable->ht_printf = printf;
  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 void htable_free_objects(htable_t *htable)
  54 {
  55     hhead_t *phead;
  56     hnode_t *pnode;
  57     unsigned int i;
  58
  59     for (i = 0; i < htable->ht_size; i++) {
  60         phead = &htable->ht_table[i];
  61         TAILQ_FOREACH(pnode, phead, hn_next) {
  62             free(pnode->hn_key);
  63             free(pnode->hn_data);
  64         }
  65     }
  66 }
  67
  68 htret_t htable_grow(htable_t *htable)
  69 {
  70     hhead_t *pcurhead, *pnewhead, *poldhead;
  71     hnode_t *pnode;
  72     unsigned int i, newhash, newsize;
  73
  74     /* Allocate memory for new hash table */
  75     newsize = 2 * htable->ht_size;
  76     if ((pnewhead = malloc(newsize * sizeof *pnewhead)) == NULL)
  77         return HT_NOMEM;
  78
  79     /* Initialize tailqs */
  80     for (i = 0; i < newsize; i++)
  81         TAILQ_INIT(&pnewhead[i]);
  82
  83     poldhead = htable->ht_table;
  84
  85     for (i = 0; i < htable->ht_size; i++) {
  86         pcurhead = &poldhead[i];
  87         while ((pnode = TAILQ_FIRST(pcurhead)) != NULL) {
  88             newhash = htable->ht_hashf(pnode->hn_key);
  89             TAILQ_REMOVE(pcurhead, pnode, hn_next);
  90             TAILQ_INSERT_TAIL(&pnewhead[newhash & (newsize - 1)], pnode, hn_next);
  91         }
  92     }
  93
  94     /* Free old table */
  95     free(htable->ht_table);
  96
  97     /* Set new table parameters */
  98     htable->ht_table = pnewhead;
  99     htable->ht_size = newsize;
 100     htable->ht_limit = htable->ht_factor * newsize;
 101
 102     return HT_OK;
 103 }
 104
 105 htret_t htable_insert(htable_t *htable, const void *key, void *data)
 106 {
 107     hhead_t *phead;
 108     hnode_t *pnode;
 109     unsigned int hash;
 110
 111     /* Calculate hash */
 112     hash = htable->ht_hashf(key);
 113
 114     /* Search across chain if there is already an entry
 115        with the same key. If there is, replace it.
 116        Don't forget to free the old data, before overwriting
 117        the pointer or else we will leak. */
 118     phead = &htable->ht_table[hash & (htable->ht_size - 1)];
 119     TAILQ_FOREACH(pnode, phead, hn_next)
 120         if (htable->ht_cmpf(pnode->hn_key, key) == 0) {
 121             free(pnode->hn_key);
 122             free(pnode->hn_data);
 123             pnode->hn_key = key;
 124             pnode->hn_data = data;
 125             return HT_OK;
 126         }
 127
 128     /* Allocate memory for new entry */
 129     if ((pnode = malloc(sizeof *pnode)) == NULL)
 130         return HT_NOMEM;
 131     pnode->hn_key = key;
 132     pnode->hn_data = data;
 133
 134     TAILQ_INSERT_TAIL(phead, pnode, hn_next);
 135
 136     /* If used items exceeds limit, grow the table */
 137     if (++htable->ht_used > htable->ht_limit)
 138         htable_grow(htable);
 139
 140     return HT_OK;
 141 }
 142
 143 htret_t htable_remove(htable_t *htable, const void *key)
 144 {
 145     hhead_t *phead;
 146     hnode_t *pnode, *tmp;
 147     unsigned int hash;
 148
 149     /* Calculate hash */
 150     hash = htable->ht_hashf(key);
 151
 152     /* Search across chain if there is an entry with the
 153     key we are looking. If there is, remove it. */
 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             tmp = pnode;
 158             TAILQ_REMOVE(phead, pnode, hn_next);
 159             free(pnode);
 160             htable->ht_used--;
 161             return HT_OK;
 162         }
 163     }
 164
 165     return HT_NOTFOUND;
 166 }
 167
 168 void *htable_search(const htable_t *htable, const void *key)
 169 {
 170     const hhead_t *phead;
 171     const hnode_t *pnode;
 172     unsigned int hash;
 173
 174     /* Calculate hash */
 175     hash = htable->ht_hashf(key);
 176
 177     phead = &htable->ht_table[hash & (htable->ht_size - 1)];
 178     TAILQ_FOREACH(pnode, phead, hn_next)
 179         if (htable->ht_cmpf(pnode->hn_key, key) == 0)
 180             return pnode->hn_data;
 181
 182     return NULL;
 183 }
 184
 185 void htable_print(const htable_t *htable)
 186 {
 187     const hhead_t *phead;
 188     const hnode_t *pnode;
 189     unsigned int i;
 190
 191     for (i = 0; i < htable->ht_size; i++) {
 192         phead = &htable->ht_table[i];
 193         TAILQ_FOREACH(pnode, phead, hn_next)
 194              htable->ht_printf(pnode->hn_key, pnode->hn_data);
 195         if (TAILQ_FIRST(&htable->ht_table[i]) != NULL)
 196             printf("\n");
 197     }
 198 }