blob: 2506c5b894c51102c5a656cbbd2dc66aee2be2d2 (
plain)
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
|
#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;
p.key = key;
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) {
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;
}
/* TODO: handle collision
TODO: return 0 if something goes wrong */
unsigned int hashtable_add_pair(hashtable_t* hashtable, pair_t pair) {
unsigned int hash = get_hash(pair.key);
hashtable->pairs[hash % hashtable->capacity] = pair;
return hash;
}
pair_t hashtable_get_pair(hashtable_t* hashtable, char* key) {
unsigned int hash = get_hash(key);
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;
}
|
