hashtable.c (1784B)
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 }