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
87
88
89
90
91
92
93
94
|
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "hashtable.h"
const unsigned int fnvPrime = 16777619;
const unsigned int fnvOffset = 2166136261U;
pair_t init_pair(char* key, void* value) {
pair_t p;
if (key != NULL) {
char* kp = malloc((strlen(key) + 1) * sizeof(char));
strcpy(kp, key);
p.key = kp;
}
else {
p.key = NULL;
}
p.value = value;
return p;
}
hashtable_t* init_hashtable(unsigned int capacity, hashtable_t* parent) {
hashtable_t* ht = malloc(sizeof(hashtable_t));
ht->pairs = calloc(capacity, sizeof(pair_t));
ht->capacity = capacity;
ht->parent = parent;
return ht;
}
void destroy_hashtable(hashtable_t* hashtable) {
for (int i = 0; i < hashtable->capacity; i++) {
if (hashtable->pairs[i].key != NULL) {
free(hashtable->pairs[i].key);
}
}
free(hashtable->pairs);
free(hashtable);
}
//FNV-1a hash
unsigned int get_hash(char* str) {
unsigned int hash = fnvOffset;
while (*str != '\0') {
hash = (hash ^ *str) * fnvPrime;
str++;
}
return hash;
}
unsigned int hashtable_add_pair(hashtable_t* hashtable, pair_t pair) {
unsigned int hash = get_hash(pair.key);
for (int i = 0; i < hashtable->capacity; i++) {
unsigned int ha = hash + i;
unsigned int ia = ha % hashtable->capacity;
pair_t p = hashtable->pairs[ia];
if (p.key == NULL || strcmp(p.key, pair.key) == 0) {
hashtable->pairs[ia] = pair;
return hash;
}
}
return 0;
}
unsigned int hashtable_update_pair_recurse(hashtable_t* origin, pair_t pair) {
pair_t p = hashtable_get_pair(origin, pair.key);
if (p.key != NULL) {
return hashtable_add_pair(origin, pair);
}
if (origin->parent != NULL) {
return hashtable_update_pair_recurse(origin->parent, pair);
}
return 0;
}
pair_t hashtable_get_pair(hashtable_t* hashtable, char* key) {
unsigned int hash = get_hash(key);
for (int i = 0; i < hashtable->capacity; i++) {
unsigned int ha = hash + i;
unsigned int ia = ha % hashtable->capacity;
pair_t p = hashtable->pairs[ia];
if (p.key != NULL && strcmp(p.key, key) == 0) {
return p;
}
else if (p.key == NULL) {
return init_pair(NULL, NULL);
}
}
return hashtable->pairs[(hash) % hashtable->capacity];
}
pair_t hashtable_get_pair_recurse(hashtable_t* origin, char* key) {
pair_t pair = hashtable_get_pair(origin, key);
if (pair.key != NULL) {
return pair;
}
if (origin->parent != NULL) {
return hashtable_get_pair_recurse(origin->parent, key);
}
return pair;
}
|
