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_search(const htable_t *htable, const void *key)
  55 {
  56     hnode_t *pnode;
  57     u_int hash;
  58
  59     /* Calculate hash */
  60     hash = htable->ht_hashf(key);
  61
  62     TAILQ_FOREACH(pnode, &htable->ht_table[hash & (htable->ht_size - 1)], hn_next)
  63         if (htable->ht_cmpf(pnode->hn_key, key) == 0)
  64             return pnode->hn_data;
  65
  66     return NULL;
  67 }
  68
  69 void htable_print(const htable_t *htable)
  70 {
  71     const hnode_t *pnode;
  72     u_int i;
  73
  74     for (i = 0; i < htable->ht_size; i++) {
  75         TAILQ_FOREACH(pnode, &htable->ht_table[i], hn_next)
  76              htable->ht_printf(pnode->hn_key, pnode->hn_data);
  77         if (TAILQ_FIRST(&htable->ht_table[i]) != NULL)
  78             printf("\n");
  79     }
  80 }
  81
  82 u_int djb_hash(const void *str)
  83 {
  84     /* DJB hashing */
  85     u_int i, hash = 5381;
  86
  87     for (i = 0; i < strlen((char*)str); i++)
  88         hash = ((hash << 5) + hash) + ((char*)str)[i];
  89
  90     return (hash & 0x7FFFFFFF);
  91 }
  92
  93 int mycmp(const void *arg1, const void *arg2)
  94 {
  95     return (strcmp((char *) arg1, (char *) arg2));
  96 }
  97
  98 void myprintf(const void *key, const void *data)
  99 {
 100     printf("%s(%s) ", (char *)key, (char *)data);
 101 }
 102
 103 int main(void)
 104 {
 105     htable_t ptable;
 106
 107     /* Initialize table */
 108     htable_init(&ptable, 10);
 109
 110     /* Setup callback functions */
 111     ptable.ht_hashf = djb_hash;
 112     ptable.ht_cmpf = mycmp;
 113     ptable.ht_printf = myprintf;
 114
 115     htable_insert(&ptable, "stathis", "stathis");
 116     htable_insert(&ptable, "maria", "maria");
 117     htable_insert(&ptable, "kostas", "kostas");
 118     htable_insert(&ptable, "panagiotopoulos", "panagiotopoulos");
 119     htable_insert(&ptable, "eleni", "eleni");
 120
 121     htable_print(&ptable);
 122
 123     return EXIT_SUCCESS;
 124 }