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