genstructs/htable.c

   1 #include <assert.h>
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include <string.h>
   5
   6 #define HTABLE_SIZE 10
   7
   8 typedef struct hnode {
   9     char *str;
  10     struct hnode *next;
  11 } hnode_t;
  12
  13 /* Function prototypes */
  14 hnode_t *htable_alloc(unsigned int size);
  15 void htable_free(hnode_t *htable, unsigned int size);
  16 void htable_insert(hnode_t *htable, char *str, unsigned int pos);
  17 unsigned int htable_search(hnode_t *htable, unsigned int size, char *str);
  18 void htable_print(hnode_t *htable, unsigned int size);
  19 unsigned int htable_mkhash(char *str, unsigned int size);
  20
  21 int main(void)
  22 {
  23     hnode_t *myhtable;
  24
  25     myhtable = htable_alloc(HTABLE_SIZE);
  26
  27     htable_insert(myhtable, "stathis", htable_mkhash("stathis", HTABLE_SIZE));
  28     htable_insert(myhtable, "kostas", htable_mkhash("kostas", HTABLE_SIZE));
  29     htable_insert(myhtable, "petros", htable_mkhash("petros", HTABLE_SIZE));
  30     htable_insert(myhtable, "maria", htable_mkhash("maria", HTABLE_SIZE));
  31
  32     printf("%d\n", htable_search(myhtable, HTABLE_SIZE, "stathis"));
  33     printf("%d\n", htable_search(myhtable, HTABLE_SIZE, "kostas"));
  34     printf("%d\n", htable_search(myhtable, HTABLE_SIZE, "petros"));
  35     printf("%d\n", htable_search(myhtable, HTABLE_SIZE, "maria"));
  36
  37     htable_print(myhtable, HTABLE_SIZE);
  38
  39     htable_free(myhtable, HTABLE_SIZE);
  40
  41     return EXIT_SUCCESS;
  42 }
  43
  44 hnode_t *htable_alloc(unsigned int size)
  45 {
  46     hnode_t *pnode;
  47     unsigned int i;
  48
  49     /* Allocate memory for `size' hnode_t structures */
  50     if ((pnode = malloc(size * sizeof *pnode)) == NULL) {
  51         perror("malloc");
  52         exit(EXIT_FAILURE);
  53     }
  54
  55     /* Initialize hnode_t fields */
  56     for (i = 0; i < size; i++) {
  57         pnode[i].str = NULL;
  58         pnode[i].next = NULL;
  59     }
  60
  61     return pnode;
  62 }
  63
  64 void htable_free(hnode_t *htable, unsigned int size)
  65 {
  66     hnode_t *pnode, *tmp;
  67     unsigned int i;
  68
  69     for (i = 0; i < size; i++) {
  70         pnode = htable[i].next;
  71         /* Does this pnode have a chain ? If yes, free it */
  72         while (pnode != NULL) {
  73             tmp = pnode->next;
  74             free(pnode->str);
  75             free(pnode);
  76             pnode = tmp;
  77         }
  78         if (htable[i].str != NULL)
  79             free(htable[i].str);
  80     }
  81
  82     free(htable);
  83 }
  84
  85 void htable_insert(hnode_t *htable, char *str, unsigned int pos)
  86 {
  87     hnode_t *pnode;
  88
  89     /* Is `pos' available in the hash table ? */
  90     if (htable[pos].str == NULL) {
  91         if ((htable[pos].str = malloc(sizeof(strlen(str)))) == NULL)
  92             goto OUT;
  93         strcpy(htable[pos].str, str);
  94     }
  95     else {
  96         /* Collision resolution */
  97         for (pnode = &htable[pos]; pnode->next != NULL; pnode = pnode->next)
  98             ;
  99         pnode->next = htable_alloc(1);
 100         if ((pnode->next->str = malloc(sizeof(strlen(str)))) == NULL)
 101             goto OUT;
 102         strcpy(pnode->next->str, str);
 103     }
 104  OUT:;
 105 }
 106
 107 unsigned int htable_search(hnode_t *htable, unsigned int size, char *str)
 108 {
 109     hnode_t *pnode;
 110     unsigned int pos;
 111
 112     /* Get the hash */
 113     pos = htable_mkhash(str, size);
 114
 115     /* Is the `str' in the hash table ? */
 116     if (strcmp(htable[pos].str, str) == 0)
 117         return pos;
 118     else {
 119         /* Search across the chain */
 120         for (pnode = htable[pos].next; pnode != NULL; pnode = pnode->next)
 121             if (strcmp(pnode->str, str) == 0)
 122                 return pos;
 123     }
 124
 125     return -1;    /* Not found */
 126 }
 127
 128 void htable_print(hnode_t *htable, unsigned int size)
 129 {
 130     hnode_t *pnode;
 131     unsigned int i;
 132
 133     for (i = 0; i < size; i++) {
 134         pnode = &htable[i];
 135         if (pnode->str != NULL) {
 136             printf("%s ", pnode->str);
 137             /* Does this pnode have a chain ? If yes, print it */
 138             while (pnode->next != NULL) {
 139                 printf("%s ", pnode->next->str);
 140                 pnode = pnode->next;
 141             }
 142             printf("\n");
 143         }
 144     }
 145 }
 146
 147 unsigned int htable_mkhash(char *str, unsigned int size)
 148 {
 149     /* DJB hashing */
 150     unsigned int i, hash = 5381;
 151
 152     for (i = 0; i < strlen(str); i++)
 153         hash = ((hash << 5) + hash) + str[i];
 154
 155     return (hash & 0x7FFFFFFF) % size;
 156 }