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     phead = &htable->ht_table[hash & (htable->ht_size - 1)];
 115     TAILQ_FOREACH(pnode, phead, hn_next)
 116         if (htable->ht_cmpf(pnode->hn_key, key) == 0) {
 117             pnode->hn_data = data;
 118             return HT_OK;
 119         }
 120
 121     /* Allocate memory for new entry */
 122     if ((pnode = malloc(sizeof *pnode)) == NULL)
 123         return HT_NOMEM;
 124     pnode->hn_key = key;
 125     pnode->hn_data = data;
 126
 127     TAILQ_INSERT_TAIL(phead, pnode, hn_next);
 128
 129     /* If used items exceeds limit, grow the table */
 130     if (++htable->ht_used > htable->ht_limit)
 131         htable_grow(htable);
 132
 133     return HT_OK;
 134 }
 135
 136 htret_t htable_remove(htable_t *htable, const void *key)
 137 {
 138     hhead_t *phead;
 139     hnode_t *pnode, *tmp;
 140     unsigned int hash;
 141
 142     /* Calculate hash */
 143     hash = htable->ht_hashf(key);
 144
 145     /* Search across chain if there is an entry with the
 146     key we are looking. If there is, remove it. */
 147     phead = &htable->ht_table[hash & (htable->ht_size - 1)];
 148     TAILQ_FOREACH(pnode, phead, hn_next) {
 149         if (htable->ht_cmpf(pnode->hn_key, key) == 0) {
 150             tmp = pnode;
 151             TAILQ_REMOVE(phead, pnode, hn_next);
 152             free(pnode);
 153             htable->ht_used--;
 154             return HT_OK;
 155         }
 156     }
 157
 158     return HT_NOTFOUND;
 159 }
 160
 161 void *htable_search(const htable_t *htable, const void *key)
 162 {
 163     const hhead_t *phead;
 164     const hnode_t *pnode;
 165     unsigned int hash;
 166
 167     /* Calculate hash */
 168     hash = htable->ht_hashf(key);
 169
 170     phead = &htable->ht_table[hash & (htable->ht_size - 1)];
 171     TAILQ_FOREACH(pnode, phead, hn_next)
 172         if (htable->ht_cmpf(pnode->hn_key, key) == 0)
 173             return pnode->hn_data;
 174
 175     return NULL;
 176 }
 177
 178 void htable_print(const htable_t *htable)
 179 {
 180     const hhead_t *phead;
 181     const hnode_t *pnode;
 182     unsigned int i;
 183
 184     for (i = 0; i < htable->ht_size; i++) {
 185         phead = &htable->ht_table[i];
 186         TAILQ_FOREACH(pnode, phead, hn_next)
 187              htable->ht_printf(pnode->hn_key, pnode->hn_data);
 188         if (TAILQ_FIRST(&htable->ht_table[i]) != NULL)
 189             printf("\n");
 190     }
 191 }