tools/hashtable.c

   1 #include <stdint.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include <stdio.h>
   5
   6 #include "hashtable.h"
   7
   8 struct HashNode
   9 {
  10     struct HashNode *next;
  11     uint8_t value[];
  12 };
  13
  14 struct HashTable
  15 {
  16     HashFunc func;
  17     HashValueCmpFunc cmp;
  18     int size;
  19     int elemSize;
  20     struct HashNode *table[];
  21 };
  22
  23 struct HashTable *hashtable_new(HashFunc func, HashValueCmpFunc cmp, int size,
  24     int elemSize)
  25 {
  26     struct HashTable *ht = malloc(sizeof(*ht) + size * sizeof(ht->table[0]));
  27
  28     ht->func = func;
  29     ht->cmp = cmp;
  30     ht->size = size;
  31     ht->elemSize = elemSize;
  32     memset(ht->table, 0, ht->size * sizeof(ht->table[0]));
  33     return ht;
  34 }
  35
  36 void hashtable_free(struct HashTable *ht)
  37 {
  38     int i;
  39
  40     for (i = 0; i < ht->size; i++)
  41     {
  42         struct HashNode *node = ht->table[i];
  43
  44         while (node != NULL)
  45         {
  46             struct HashNode *next = node->next;
  47
  48             free(node);
  49             node = next;
  50         }
  51     }
  52     free(ht);
  53 }
  54
  55 void hashtable_insert(struct HashTable *ht, const void *value)
  56 {
  57     unsigned int key = ht->func(value) % ht->size;
  58     struct HashNode *node = malloc(sizeof(*node) + ht->elemSize);
  59
  60     node->next = NULL;
  61     memcpy(node->value, value, ht->elemSize);
  62
  63     if (ht->table[key] == NULL)
  64     {
  65         ht->table[key] = node;
  66     }
  67     else
  68     {
  69         struct HashNode *parent = ht->table[key];
  70
  71         while (parent->next != NULL)
  72             parent = parent->next;
  73         parent->next = node;
  74     }
  75 }
  76
  77 void *hashtable_query(struct HashTable *ht, const void *value)
  78 {
  79     unsigned int key = ht->func(value) % ht->size;
  80     struct HashNode *node = ht->table[key];
  81
  82     while (node != NULL)
  83     {
  84         if (ht->cmp(node->value, value))
  85             return node->value;
  86         node = node->next;
  87     }
  88     return NULL;
  89 }