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)
   8 {
   9     unsigned int i;
  10
  11     /* Allocate memory for `size' tailq headers */
  12     if ((htable->ht_table = malloc(size * sizeof *htable->ht_table)) == NULL)
  13         return HT_NOMEM;
  14
  15     /* Initialize tailqs */
  16     for (i = 0; i < size; i++)
  17         TAILQ_INIT(&htable->ht_table[i]);
  18
  19     htable->ht_size = size;    /* size must be a power of 2 */
  20     htable->ht_used = 0;
  21
  22     return HT_OK;
  23 }
  24
  25 void htable_free(htable_t *htable)
  26 {
  27     hhead_t *phead;
  28     hnode_t *pnode;
  29     unsigned int i;
  30
  31     for (i = 0; i < htable->ht_size; i++) {
  32         phead = &htable->ht_table[i];
  33         while (TAILQ_FIRST(phead) != NULL) {
  34             pnode = TAILQ_FIRST(phead);
  35             TAILQ_REMOVE(phead, TAILQ_FIRST(phead), hn_next);
  36             free(pnode);
  37         }
  38     }
  39
  40     free(htable->ht_table);
  41 }
  42
  43 htret_t htable_insert(htable_t *htable, const void *key, void *data)
  44 {
  45     hhead_t *phead;
  46     hnode_t *pnode;
  47     unsigned int hash;
  48
  49     /* Calculate hash */
  50     hash = htable->ht_hashf(key);
  51
  52     /* Search across chain if there is already an entry
  53        with the same key. If there is, replace it. */
  54     phead = &htable->ht_table[hash & (htable->ht_size - 1)];
  55     TAILQ_FOREACH(pnode, phead, hn_next)
  56         if (htable->ht_cmpf(pnode->hn_key, key) == 0) {
  57             pnode->hn_data = data;
  58             return HT_OK;
  59         }
  60
  61     /* Allocate memory for new entry */
  62     if ((pnode = malloc(sizeof *pnode)) == NULL)
  63         return HT_NOMEM;
  64     pnode->hn_key = key;
  65     pnode->hn_data = data;
  66
  67     TAILQ_INSERT_TAIL(phead, pnode, hn_next);
  68     htable->ht_used++;
  69
  70     return HT_OK;
  71 }
  72
  73 htret_t htable_remove(htable_t *htable, const void *key)
  74 {
  75     hhead_t *phead;
  76     hnode_t *pnode, *tmp;
  77     unsigned int hash;
  78
  79     /* Calculate hash */
  80     hash = htable->ht_hashf(key);
  81
  82     /* Search across chain if there is an entry with the
  83     key we are looking. If there is, delete it. */
  84     phead = &htable->ht_table[hash & (htable->ht_size - 1)];
  85     TAILQ_FOREACH(pnode, phead, hn_next)
  86         if (htable->ht_cmpf(pnode->hn_key, key) == 0) {
  87             tmp = pnode;
  88             TAILQ_REMOVE(phead, pnode, hn_next);
  89             free(pnode);
  90             htable->ht_size--;
  91             return HT_OK;
  92         }
  93
  94     return HT_NOTFOUND;
  95 }
  96
  97 void *htable_search(const htable_t *htable, const void *key)
  98 {
  99     const hhead_t *phead;
 100     const hnode_t *pnode;
 101     unsigned int hash;
 102
 103     /* Calculate hash */
 104     hash = htable->ht_hashf(key);
 105
 106     phead = &htable->ht_table[hash & (htable->ht_size - 1)];
 107     TAILQ_FOREACH(pnode, phead, hn_next)
 108         if (htable->ht_cmpf(pnode->hn_key, key) == 0)
 109             return pnode->hn_data;
 110
 111     return NULL;
 112 }
 113
 114 void htable_print(const htable_t *htable)
 115 {
 116     const hnode_t *pnode;
 117     unsigned int i;
 118
 119     for (i = 0; i < htable->ht_size; i++) {
 120         TAILQ_FOREACH(pnode, &htable->ht_table[i], hn_next)
 121              htable->ht_printf(pnode->hn_key, pnode->hn_data);
 122         if (TAILQ_FIRST(&htable->ht_table[i]) != NULL)
 123             printf("\n");
 124     }
 125 }