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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
#include "hashmap.h"
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define MONS_HASHMAP_MAX_LOAD_FACTOR 3.0f
unsigned int djb2_hash(unsigned char *str, unsigned int bucket_count) {
unsigned long hash = 5381;
int c;
while ((c = *str++)) {
hash = ((hash << 5) + hash) + c;
}
return hash % bucket_count;
}
mons_hashmap mons_hashmap_new(unsigned int member_size, unsigned int buckets) {
mons_hashmap result = {
.member_size = member_size,
.bucket_count = buckets,
.data = calloc(buckets, sizeof(mons_hashmap_pair *)),
};
return result;
}
int mons_hashmap_rehash(mons_hashmap *map) {
// TODO: Expand number of buckets, re-hash all entries
return EXIT_SUCCESS;
}
int mons_hashmap_insert(mons_hashmap *map, char *key, void *value) {
unsigned int bucket = djb2_hash((unsigned char*)key, map->bucket_count);
mons_hashmap_pair *tail = map->data[bucket];
if (tail == NULL) {
map->data[bucket] = calloc(1, sizeof(mons_hashmap_pair *));
tail = map->data[bucket];
} else {
mons_hashmap_pair *node = tail;
while(1) {
if(strcmp(key, node->key) == 0) {
memcpy(node->value, value, map->member_size);
return EXIT_SUCCESS;
}
if(node->next == NULL) {
tail = node;
break;
}
node = node->next;
}
tail->next = calloc(1, sizeof(mons_hashmap_pair *));
tail = tail->next;
}
tail->key = calloc(strlen(key) + 1, 1);
strcpy(tail->key, key);
tail->value = calloc(1, map->member_size);
memcpy(tail->value, value, map->member_size);
map->len++;
if (map->len / map->bucket_count > MONS_HASHMAP_MAX_LOAD_FACTOR) {
mons_hashmap_rehash(map);
}
return EXIT_SUCCESS;
}
int mons_hashmap_get(mons_hashmap map, char *key, void *out) {
unsigned int bucket = djb2_hash((unsigned char*)key, map.bucket_count);
mons_hashmap_pair *tail = map.data[bucket];
while(tail != NULL) {
if(strcmp(key, tail->key) == 0) {
memcpy(out, tail->value, map.member_size);
return EXIT_SUCCESS;
}
tail = tail->next;
}
return EXIT_FAILURE;
}
int mons_hashmap_remove(mons_hashmap *map, char *key) {
unsigned int bucket = djb2_hash((unsigned char*)key, map->bucket_count);
mons_hashmap_pair *tail = map->data[bucket];
mons_hashmap_pair *prev = NULL;
while(tail != NULL) {
if(strcmp(key, tail->key) == 0) {
if (prev == NULL) {
map->data[bucket] = tail->next;
} else {
prev->next = tail->next;
}
free(tail->key);
free(tail->value);
free(tail);
map->len--;
return EXIT_SUCCESS;
}
prev = tail;
tail = tail->next;
}
return EXIT_FAILURE;
}
void mons_hashmap_free(mons_hashmap *hashmap) {
for (int i = 0; i < hashmap->bucket_count; i++) {
mons_hashmap_pair *node = hashmap->data[i];
while(node != NULL) {
mons_hashmap_pair *next = node->next;
free(node->key);
free(node->value);
free(node);
node = next;
}
}
free(hashmap->data);
hashmap->data = NULL;
hashmap->bucket_count = 0;
hashmap->member_size = 0;
hashmap->len = 0;
}
int mons_hashmap_at(mons_hashmap map, unsigned int index, mons_hashmap_pair *out) {
mons_hashmap_pair **bucket = map.data;
mons_hashmap_pair *node = *bucket;
while(node == NULL) {
bucket++;
node = *bucket;
}
for(int i = 0; i < index; i++) {
if (node == NULL || node->next == NULL) {
bucket++;
node = *bucket;
while(node == NULL) {
bucket++;
node = *bucket;
}
} else {
node = node->next;
}
}
*out = *node;
return EXIT_SUCCESS;
}
|
