ref: d28f531c7f502fb0d9693b0d46ea08cce3da93fc 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
#define _POSIX_C_SOURCE 200809L
#include <mrsh/hashtable.h>
#include <stdlib.h>
#include <string.h>

static unsigned int djb2(const char *str) {
	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) {
	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,
		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) {
	if (entry == NULL) {
		return;
	}
	free(entry->key);
	free(entry);
}

void *mrsh_hashtable_del(struct mrsh_hashtable *table, const char *key) {
	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] = NULL;
	}
	void *old_value = entry->value;
	hashtable_entry_destroy(entry);
	return old_value;
}

void mrsh_hashtable_finish(struct mrsh_hashtable *table) {
	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,
		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;
		}
	}
}