genstructs/htable.c

   1 #include <assert.h>
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include <string.h>
   5
   6 #define HTABLE_SIZE 100
   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[], char *str);
  18 unsigned int htable_mkhash(char *str);
  19
  20 int main(void)
  21 {
  22     hnode_t *myhtable;
  23
  24     myhtable = htable_alloc(HTABLE_SIZE);
  25
  26     printf("=========================\n");
  27     fflush(NULL);
  28     htable_insert(&myhtable, "stathis", htable_mkhash("stathis"));
  29
  30     return 0;
  31     printf("%d\n", htable_search(&myhtable, "stathis"));
  32
  33
  34     htable_free(&myhtable, HTABLE_SIZE);
  35
  36     return EXIT_SUCCESS;
  37 }
  38
  39 hnode_t *htable_alloc(unsigned int size)
  40 {
  41     hnode_t *pnode;
  42     unsigned int i;
  43
  44     if ((pnode = malloc(size * sizeof *pnode)) == NULL) {
  45         perror("malloc");
  46         exit(EXIT_FAILURE);
  47     }
  48
  49     for (i = 0; i < size; i++) {
  50         pnode[i].str = NULL;
  51         pnode[i].next = NULL;
  52     }
  53
  54     return pnode;
  55 }
  56
  57 void htable_free(hnode_t *htable[], unsigned int size)
  58 {
  59     unsigned int i;
  60
  61     for (i = 0; i < size; i++) {
  62     }
  63 }
  64
  65 void htable_insert(hnode_t *htable[], char *str, unsigned int pos)
  66 {
  67     hnode_t *pnode;
  68     unsigned int i;
  69
  70     if (htable[pos]->str == NULL) {
  71         htable[pos] = htable_alloc(1);
  72         if ((htable[pos]->next->str = malloc(sizeof(strlen(str)))) == NULL)
  73             goto OUT;
  74         strcpy(htable[pos]->next->str, str);
  75     }
  76     else {
  77         /* Collision resolution */
  78         for (pnode = htable[pos]; pnode != NULL; pnode = pnode->next) {
  79             if (pnode->next == NULL) {
  80                 pnode->next = htable_alloc(1);
  81                 if ((pnode->next->str = malloc(sizeof(strlen(str)))) == NULL)
  82                     goto OUT;
  83                 strcpy(pnode->next->str, str);
  84             }
  85         }
  86     }
  87     OUT:;
  88 }
  89
  90 unsigned int htable_search(hnode_t *htable[], char *str)
  91 {
  92     hnode_t *pnode;
  93     unsigned int pos;
  94
  95     pos = htable_mkhash(str);
  96
  97     if (strcmp(htable[pos]->str, str) == 0)
  98         return pos;
  99     else {
 100         /* Search across the chain */
 101         for (pnode = htable[pos]; pnode != NULL; pnode = pnode->next)
 102             if (strcmp(pnode->str, str))
 103                 return pos;
 104     }
 105
 106     return -1;
 107 }
 108
 109 unsigned int htable_mkhash(char *str)
 110 {
 111     /* DJB hashing */
 112     unsigned int i, hash = 5381;
 113
 114     for (i = 0; i < strlen(str); i++)
 115         hash = ((hash << 5) + hash) + str[i];
 116
 117     return (hash & 0x7FFFFFFF) % HTABLE_SIZE;
 118 }