mrsh/hashtable.c -rw-r--r-- 2.8 KiB View raw
                                                                                
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
#define _POSIX_C_SOURCE 200809L
#include <mrsh/hashtable.h>
#include <stdlib.h>
#include <string.h>

static unsigned int djb2(const char *str) {
3 references
unsigned int hash = 5381; char c; while ((c = *str++)) { hash = ((hash << 5) + hash) + c; } return hash; } void *mrsh_hashtable_get(struct mrsh_hashtable *table, const char *key) {
7 references
unsigned int hash = djb2(key); unsigned int bucket = hash % MRSH_HASHTABLE_BUCKETS; struct mrsh_hashtable_entry *entry = table->buckets[bucket]; while (entry != NULL) { if (entry->hash == hash && strcmp(entry->key, key) == 0) { return entry->value; } entry = entry->next; } return NULL; } void *mrsh_hashtable_set(struct mrsh_hashtable *table, const char *key,
3 references
void *value) { unsigned int hash = djb2(key); unsigned int bucket = hash % MRSH_HASHTABLE_BUCKETS; struct mrsh_hashtable_entry *entry = table->buckets[bucket]; struct mrsh_hashtable_entry *previous = NULL; while (entry != NULL) { if (entry->hash == hash && strcmp(entry->key, key) == 0) { break; } previous = entry; entry = entry->next; } if (entry == NULL) { entry = calloc(1, sizeof(struct mrsh_hashtable_entry)); entry->hash = hash; entry->key = strdup(key); if (previous != NULL) { previous->next = entry; } else { table->buckets[bucket] = entry; } } void *old_value = entry->value; entry->value = value; return old_value; } static void hashtable_entry_destroy(struct mrsh_hashtable_entry *entry) {
2 references
if (entry == NULL) { return; } free(entry->key); free(entry); } void *mrsh_hashtable_del(struct mrsh_hashtable *table, const char *key) {
4 references
unsigned int hash = djb2(key); unsigned int bucket = hash % MRSH_HASHTABLE_BUCKETS; struct mrsh_hashtable_entry *entry = table->buckets[bucket]; struct mrsh_hashtable_entry *previous = NULL; while (entry != NULL) { if (entry->hash == hash && strcmp(entry->key, key) == 0) { break; } previous = entry; entry = entry->next; } if (entry == NULL) { return NULL; } if (previous != NULL) { previous->next = entry->next; } else { table->buckets[bucket] = entry->next; } void *old_value = entry->value; hashtable_entry_destroy(entry); return old_value; } void mrsh_hashtable_finish(struct mrsh_hashtable *table) {
3 references
for (size_t i = 0; i < MRSH_HASHTABLE_BUCKETS; ++i) { struct mrsh_hashtable_entry *entry = table->buckets[i]; while (entry != NULL) { struct mrsh_hashtable_entry *next = entry->next; hashtable_entry_destroy(entry); entry = next; } } } void mrsh_hashtable_for_each(struct mrsh_hashtable *table,
7 references
mrsh_hashtable_iterator_func iterator, void *user_data) { for (size_t i = 0; i < MRSH_HASHTABLE_BUCKETS; ++i) { struct mrsh_hashtable_entry *entry = table->buckets[i]; while (entry != NULL) { struct mrsh_hashtable_entry *next = entry->next; iterator(entry->key, entry->value, user_data); entry = next; } } }