genstructs/htable/htable.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include <sys/queue.h>
   5
   6 #include "htable.h"
   7
   8 void htable_init(htable_t *htable, size_t size)
   9 {
  10     u_int i;
  11
  12     /* Allocate memory for `size' tailq headers */
  13     if ((htable->ht_table = malloc(size * sizeof *htable->ht_table)) == NULL) {
  14         perror("malloc");
  15         exit(EXIT_FAILURE);
  16     }
  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 }
  25
  26 void htable_insert(htable_t *htable, const void *key, void *data)
  27 {
  28     struct htablehead *phead;
  29     hnode_t *pnode;
  30     u_int hash;
  31
  32     /* Calculate hash */
  33     hash = htable->ht_hashf(key);
  34
  35     /* Search across chain if there is already an entry
  36        with the same key. If there is, replace it. */
  37     phead = &htable->ht_table[hash & (htable->ht_size - 1)];
  38     TAILQ_FOREACH(pnode, phead, hn_next)
  39         if (htable->ht_cmpf(pnode->hn_key, key) == 0) {
  40             pnode->hn_data = data;
  41             return;
  42         }
  43
  44     /* Allocate memory for new entry */
  45     if ((pnode = malloc(sizeof *pnode)) == NULL)
  46         return;
  47     pnode->hn_key = key;
  48     pnode->hn_data = data;
  49
  50     TAILQ_INSERT_TAIL(phead, pnode, hn_next);
  51     htable->ht_used++;
  52 }
  53
  54 void htable_delete(htable_t *htable, const void *key)
  55 {
  56     struct htablehead *phead;
  57     hnode_t *pnode;
  58     u_int hash;
  59
  60     /* Calculate hash */
  61     hash = htable->ht_hashf(key);
  62
  63     /* Search across chain if there is an entry with the
  64     key we are looking. If there is, delete it. */
  65     phead = &htable->ht_table[hash & (htable->ht_size - 1)];
  66
  67     TAILQ_FOREACH(pnode, phead, hn_next)
  68         if (htabl->ht_cmpf(pnode->hn_key, key) == 0) {
  69             TAILQ_REMOVE(phead, pnode, hn_next);
  70             return;
  71         }
  72 }
  73
  74 void *htable_search(const htable_t *htable, const void *key)
  75 {
  76     hnode_t *pnode;
  77     u_int hash;
  78
  79     /* Calculate hash */
  80     hash = htable->ht_hashf(key);
  81
  82     TAILQ_FOREACH(pnode, &htable->ht_table[hash & (htable->ht_size - 1)], hn_next)
  83         if (htable->ht_cmpf(pnode->hn_key, key) == 0)
  84             return pnode->hn_data;
  85
  86     return NULL;
  87 }
  88
  89 void htable_print(const htable_t *htable)
  90 {
  91     const hnode_t *pnode;
  92     u_int i;
  93
  94     for (i = 0; i < htable->ht_size; i++) {
  95         TAILQ_FOREACH(pnode, &htable->ht_table[i], hn_next)
  96              htable->ht_printf(pnode->hn_key, pnode->hn_data);
  97         if (TAILQ_FIRST(&htable->ht_table[i]) != NULL)
  98             printf("\n");
  99     }
 100 }
 101
 102 u_int djb_hash(const void *key)
 103 {
 104     /* DJB hashing */
 105     u_int i, hash = 5381;
 106
 107     for (i = 0; i < strlen((char*)key); i++)
 108         hash = ((hash << 5) + hash) + ((char*)key)[i];
 109
 110     return (hash & 0x7FFFFFFF);
 111 }
 112
 113 int mycmp(const void *arg1, const void *arg2)
 114 {
 115     return (strcmp((char *) arg1, (char *) arg2));
 116 }
 117
 118 void myprintf(const void *key, const void *data)
 119 {
 120     printf("%s(%s) ", (char *)key, (char *)data);
 121 }
 122
 123 int main(void)
 124 {
 125     htable_t ptable;
 126
 127     /* Initialize table */
 128     htable_init(&ptable, 10);
 129
 130     /* Setup callback functions */
 131     ptable.ht_hashf = djb_hash;
 132     ptable.ht_cmpf = mycmp;
 133     ptable.ht_printf = myprintf;
 134
 135     htable_insert(&ptable, "stathis", "stathis");
 136     htable_insert(&ptable, "maria", "maria");
 137     htable_insert(&ptable, "kostas", "kostas");
 138     htable_insert(&ptable, "panagiotopoulos", "panagiotopoulos");
 139     htable_insert(&ptable, "eleni", "eleni");
 140
 141     htable_print(&ptable);
 142
 143     return EXIT_SUCCESS;
 144 }