netbsd/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     #ifdef HTABLE_STATS
  27     htable->ht_grows = 0;
  28     #endif
  29
  30     /* Setup callback functions */
  31     htable->ht_hashf = myhashf;
  32     htable->ht_cmpf = mycmpf;
  33     htable->ht_printf = myprintf;
  34
  35     return HT_OK;
  36 }
  37
  38 void htable_free(htable_t *htable)
  39 {
  40     hhead_t *phead;
  41     hnode_t *pnode;
  42     size_t i;
  43
  44     for (i = 0; i < htable->ht_size; i++) {
  45         phead = &htable->ht_table[i];
  46         while ((pnode = TAILQ_FIRST(phead)) != NULL) {
  47             TAILQ_REMOVE(phead, pnode, hn_next);
  48             free(pnode);
  49         }
  50     }
  51
  52     free(htable->ht_table);
  53 }
  54
  55 htret_t htable_free_obj(htable_t *htable, void *key, htfree_t htfree)
  56 {
  57     hhead_t *phead;
  58     hnode_t *pnode;
  59     size_t hash;
  60
  61     /* Calculate hash */
  62     hash = htable->ht_hashf(key);
  63
  64     /*
  65      * Search across chain if there is an entry with the
  66      * key we are looking for. If there is, free its contents.
  67      */
  68     phead = &htable->ht_table[hash & (htable->ht_size - 1)];
  69     TAILQ_FOREACH(pnode, phead, hn_next) {
  70         if (htable->ht_cmpf(pnode->hn_key, key) == 0) {
  71             TAILQ_REMOVE(phead, pnode, hn_next);
  72             if (htfree & HT_FREEKEY)
  73                 free(pnode->hn_key);
  74             if (htfree & HT_FREEDATA)
  75                 free(pnode->hn_data);
  76             free(pnode);
  77             htable->ht_used--;
  78             return HT_OK;
  79         }
  80     }
  81
  82     return HT_NOTFOUND;
  83 }
  84
  85 void htable_free_all_obj(htable_t *htable, htfree_t htfree)
  86 {
  87     hhead_t *phead;
  88     hnode_t *pnode;
  89     size_t i;
  90
  91     for (i = 0; i < htable->ht_size; i++) {
  92         phead = &htable->ht_table[i];
  93         TAILQ_FOREACH(pnode, phead, hn_next) {
  94             if (htfree & HT_FREEKEY)
  95                 free(pnode->hn_key);
  96             if (htfree & HT_FREEDATA)
  97                 free(pnode->hn_data);
  98         }
  99     }
 100 }
 101
 102 htret_t htable_grow(htable_t *htable)
 103 {
 104     hhead_t *pcurhead, *pnewhead, *poldhead;
 105     hnode_t *pnode;
 106     size_t i, newhash, newsize;
 107
 108     /*
 109      * Allocate memory for new hash table
 110      * The new hash table is 2 times bigger than the old one
 111      */
 112     newsize = htable->ht_size << 1;
 113     if ((pnewhead = malloc(newsize * sizeof *pnewhead)) == NULL)
 114         return HT_NOMEM;
 115
 116     /* Initialize tailqs */
 117     for (i = 0; i < newsize; i++)
 118         TAILQ_INIT(&pnewhead[i]);
 119
 120     poldhead = htable->ht_table;
 121
 122     /*
 123      * Remove the entries from the old hash table,
 124      * rehash them in respect to the new hash table,
 125      * and add them to the new one
 126      */
 127     for (i = 0; i < htable->ht_size; i++) {
 128         pcurhead = &poldhead[i];
 129         while ((pnode = TAILQ_FIRST(pcurhead)) != NULL) {
 130             newhash = htable->ht_hashf(pnode->hn_key);
 131             TAILQ_REMOVE(pcurhead, pnode, hn_next);
 132             TAILQ_INSERT_TAIL(&pnewhead[newhash & (newsize - 1)], pnode, hn_next);
 133         }
 134     }
 135
 136     /* Free old table */
 137     free(htable->ht_table);
 138
 139     /* Set new table parameters */
 140     htable->ht_table = pnewhead;
 141     htable->ht_size = newsize;
 142     htable->ht_limit = htable->ht_factor * newsize;
 143
 144     return HT_OK;
 145 }
 146
 147 htret_t htable_insert(htable_t *htable, void *key, void *data)
 148 {
 149     hhead_t *phead;
 150     hnode_t *pnode;
 151     size_t hash;
 152
 153     /* Calculate hash */
 154     hash = htable->ht_hashf(key);
 155
 156     /* Search across chain if there is already an entry with the same key. */
 157     phead = &htable->ht_table[hash & (htable->ht_size - 1)];
 158     TAILQ_FOREACH(pnode, phead, hn_next)
 159         if (htable->ht_cmpf(pnode->hn_key, key) == 0)
 160             return HT_EXISTS;
 161
 162     /* Allocate memory for new entry */
 163     if ((pnode = malloc(sizeof *pnode)) == NULL)
 164         return HT_NOMEM;
 165     pnode->hn_key = key;
 166     pnode->hn_data = data;
 167
 168     TAILQ_INSERT_TAIL(phead, pnode, hn_next);
 169
 170     /* If used items exceed limit, grow the table */
 171     if (++htable->ht_used > htable->ht_limit) {
 172         htable_grow(htable);
 173         #ifdef HTABLE_STATS
 174         htable->ht_grows++;
 175         #endif
 176     }
 177
 178     return HT_OK;
 179 }
 180
 181 htret_t htable_remove(htable_t *htable, const void *key)
 182 {
 183     hhead_t *phead;
 184     hnode_t *pnode;
 185     size_t hash;
 186
 187     /* Calculate hash */
 188     hash = htable->ht_hashf(key);
 189
 190     /*
 191      * Search across chain if there is an entry with the
 192      * key we are looking. If there is, delete it.
 193      */
 194     phead = &htable->ht_table[hash & (htable->ht_size - 1)];
 195     TAILQ_FOREACH(pnode, phead, hn_next) {
 196         if (htable->ht_cmpf(pnode->hn_key, key) == 0) {
 197             TAILQ_REMOVE(phead, pnode, hn_next);
 198             free(pnode);
 199             htable->ht_used--;
 200             return HT_OK;
 201         }
 202     }
 203
 204     return HT_NOTFOUND;
 205 }
 206
 207 void *htable_search(const htable_t *htable, const void *key)
 208 {
 209     const hhead_t *phead;
 210     const hnode_t *pnode;
 211     size_t hash;
 212
 213     /* Calculate hash */
 214     hash = htable->ht_hashf(key);
 215
 216     phead = &htable->ht_table[hash & (htable->ht_size - 1)];
 217     TAILQ_FOREACH(pnode, phead, hn_next)
 218         if (htable->ht_cmpf(pnode->hn_key, key) == 0)
 219             return pnode->hn_data;
 220
 221     return NULL;
 222 }
 223
 224 void htable_print(const htable_t *htable)
 225 {
 226     const hhead_t *phead;
 227     const hnode_t *pnode;
 228     size_t i;
 229
 230     for (i = 0; i < htable->ht_size; i++) {
 231         phead = &htable->ht_table[i];
 232         TAILQ_FOREACH(pnode, phead, hn_next)
 233              htable->ht_printf(pnode->hn_key, pnode->hn_data);
 234         if (TAILQ_FIRST(&htable->ht_table[i]) != NULL)
 235             printf("\n");
 236     }
 237 }
 238
 239 size_t htable_get_size(const htable_t *htable)
 240 {
 241     return htable->ht_size;
 242 }
 243
 244 size_t htable_get_used(const htable_t *htable)
 245 {
 246     return htable->ht_used;
 247 }
 248
 249 void htable_traverse(const htable_t *htable, void (*pfunc)(void *data))
 250 {
 251     const hhead_t *phead;
 252     const hnode_t *pnode;
 253     size_t i;
 254
 255     for (i = 0; i < htable->ht_size; i++) {
 256         phead = &htable->ht_table[i];
 257         TAILQ_FOREACH(pnode, phead, hn_next)
 258             pfunc(pnode->hn_data);
 259     }
 260 }
 261
 262 const hnode_t *htable_get_next_elm(const htable_t *htable, size_t *pos, const hnode_t *pnode)
 263 {
 264     const hhead_t *phead;
 265     size_t i;
 266
 267     /* Is pos out of bound ? If yes, return immediately */
 268     if (*pos > (htable->ht_size - 1))
 269         return NULL;
 270
 271     /* Find first usable element, if we were not supplied with one */
 272     if (pos == 0 || pnode == NULL) {
 273         for (i = *pos; i < htable->ht_size; i++) {
 274             ++*pos;
 275             phead = &htable->ht_table[i];
 276             if (TAILQ_FIRST(phead) != NULL)
 277                 return TAILQ_FIRST(phead);
 278         }
 279         /* We have traversed all elements. Nothing left. */
 280         return NULL;
 281     }
 282
 283     /* Are we on a chain ? */
 284     if (TAILQ_NEXT(pnode, hn_next) != NULL) {
 285         /*
 286          * Don't increase pos since we are stack in an horizontal chain,
 287          *  being still at the same 'height' which is what pos represents anyway
 288          */
 289         return TAILQ_NEXT(pnode, hn_next);
 290     }
 291     else {
 292         for (i = *pos; i < htable->ht_size; i++) {
 293             ++*pos;
 294             phead = &htable->ht_table[i];
 295             if (TAILQ_FIRST(phead) != NULL)
 296                 return TAILQ_FIRST(phead);
 297         }
 298         /* We have traversed all elements. Nothing left. */
 299         return NULL;
 300     }
 301 }
 302
 303 #ifdef HTABLE_STATS
 304 size_t htable_stat_get_grows(const htable_t *htable)
 305 {
 306     return htable->ht_grows;
 307 }
 308
 309 size_t htable_stat_get_chain_len(const htable_t *htable, size_t pos)
 310 {
 311     const hhead_t *phead;
 312     const hnode_t *pnode;
 313     size_t len;
 314
 315     if (pos >= htable->ht_size)
 316         return 0;    /* FIXME: Better error handling */
 317
 318     len = 0;
 319     phead = &htable->ht_table[pos];
 320     TAILQ_FOREACH(pnode, phead, hn_next)
 321         len++;
 322
 323     return len;
 324 }
 325 #endif