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
142
143
144
145
146
147
148
149
|
#ifndef HASHTABLE_H
#define HASHTABLE_H
typedef unsigned long (*table_hash_func)(void *key);
typedef int (*table_compare_func)(void *key_a, void *key_b);
struct bucket
{
void *key;
void *value;
struct bucket *next;
};
struct table
{
int count;
int capacity;
table_hash_func hash;
table_compare_func compare;
struct bucket **buckets;
};
void table_init(struct table *table, int capacity, table_hash_func hash, table_compare_func compare);
void table_free(struct table *table);
void *table_find(struct table *table, void *key);
void table_add(struct table *table, void *key, void *value);
void *table_remove(struct table *table, void *key);
void *table_reset(struct table *table, int *count);
#endif
#ifdef HASHTABLE_IMPLEMENTATION
#include <stdlib.h>
#include <string.h>
#define internal static
internal struct bucket *
table_new_bucket(void *key, void *value)
{
struct bucket *bucket = malloc(sizeof(struct bucket));
bucket->key = key;
bucket->value = value;
bucket->next = NULL;
return bucket;
}
internal struct bucket **
table_get_bucket(struct table *table, void *key)
{
struct bucket **bucket = table->buckets + (table->hash(key) % table->capacity);
while (*bucket) {
if (table->compare((*bucket)->key, key)) {
break;
}
bucket = &(*bucket)->next;
}
return bucket;
}
#undef internal
void table_init(struct table *table, int capacity, table_hash_func hash, table_compare_func compare)
{
table->count = 0;
table->capacity = capacity;
table->hash = hash;
table->compare = compare;
table->buckets = malloc(sizeof(struct bucket *) * capacity);
memset(table->buckets, 0, sizeof(struct bucket *) * capacity);
}
void table_free(struct table *table)
{
for (int i = 0; i < table->capacity; ++i) {
struct bucket *next, *bucket = table->buckets[i];
while (bucket) {
next = bucket->next;
free(bucket);
bucket = next;
}
}
if (table->buckets) {
free(table->buckets);
table->buckets = NULL;
}
}
void *table_find(struct table *table, void *key)
{
struct bucket *bucket = *table_get_bucket(table, key);
return bucket ? bucket->value : NULL;
}
void table_add(struct table *table, void *key, void *value)
{
struct bucket **bucket = table_get_bucket(table, key);
if (*bucket) {
if (!(*bucket)->value) {
(*bucket)->value = value;
}
} else {
*bucket = table_new_bucket(key, value);
++table->count;
}
}
void *table_remove(struct table *table, void *key)
{
void *result = NULL;
struct bucket *next, **bucket = table_get_bucket(table, key);
if (*bucket) {
result = (*bucket)->value;
next = (*bucket)->next;
free(*bucket);
*bucket = next;
--table->count;
}
return result;
}
void *table_reset(struct table *table, int *count)
{
void **values;
int capacity;
int index;
int item;
capacity = table->capacity;
*count = table->count;
values = malloc(sizeof(void *) * table->count);
item = 0;
for (index = 0; index < capacity; ++index) {
struct bucket *next, **bucket = table->buckets + index;
while (*bucket) {
values[item++] = (*bucket)->value;
next = (*bucket)->next;
free(*bucket);
*bucket = next;
--table->count;
}
}
return values;
}
#undef HASHTABLE_IMPLEMENTATION
#endif
|
