-
Notifications
You must be signed in to change notification settings - Fork 0
/
hashtable.c
86 lines (77 loc) · 2.11 KB
/
hashtable.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h>
#include "yynode.h"
#include "linkedlist.h"
#include "hashtable.h"
HashTable createHashTable() {
HashTable table = {NULL};
return table;
}
void insertToHashTable(HashTable *table, const char *key, YYNode node) {
int hash = murmur3_32(key, strlen(key), HASH_SEED) % HASH_TABLE_SIZE;
node.sParam[7] = malloc(BUF_SIZE);
strncpy(node.sParam[7], key, BUF_SIZE);
appendToList(&(table->list[hash]), node);
}
YYNode *findFromHashTable(HashTable *table, const char *key) {
int hash = murmur3_32(key, strlen(key), HASH_SEED) % HASH_TABLE_SIZE;
List L = table->list[hash];
ListNode *curr = L;
while (curr) {
if (strcmp(curr->data.sParam[7], key) == 0) {
return &(curr->data);
}
curr = nextNode(L, curr);
}
return NULL;
}
int removeFromHashTable(HashTable *table, const char *key) {
int hash = murmur3_32(key, strlen(key), HASH_SEED) % HASH_TABLE_SIZE;
ListNode *curr = table->list[hash];
while (curr) {
if (strcmp(curr->data.sParam[7], key) == 0) {
removeFromList(&(table->list[hash]), curr);
return 1;
}
curr = nextNode(table->list[hash], curr);
}
return 0;
}
uint32_t murmur3_32(const uint8_t* key, size_t len, uint32_t seed) {
uint32_t h = seed;
if (len > 3) {
size_t i = len >> 2;
do {
uint32_t k;
memcpy(&k, key, sizeof(uint32_t));
key += sizeof(uint32_t);
k *= 0xcc9e2d51;
k = (k << 15) | (k >> 17);
k *= 0x1b873593;
h ^= k;
h = (h << 13) | (h >> 19);
h = h * 5 + 0xe6546b64;
} while (--i);
}
if (len & 3) {
size_t i = len & 3;
uint32_t k = 0;
do {
k <<= 8;
k |= key[i - 1];
} while (--i);
k *= 0xcc9e2d51;
k = (k << 15) | (k >> 17);
k *= 0x1b873593;
h ^= k;
}
h ^= len;
h ^= h >> 16;
h *= 0x85ebca6b;
h ^= h >> 13;
h *= 0xc2b2ae35;
h ^= h >> 16;
return h;
}