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
|
#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "hashtable.h"
struct {
char* key;
void* data;
int deleted;
} typedef HashTableData;
struct {
HashTableData* data;
size_t length;
} typedef HashTableBucket;
struct {
HashTableBucket* buckets;
size_t capacity;
} typedef HashTableImpl;
static int hash(char* key, size_t bucket_len) {
int sum = 0;
while(*key != '\0') {
sum += *key++;
}
return sum % bucket_len;
}
HashTable hashtable_init(size_t capacity) {
HashTableImpl* ht = (HashTableImpl*) malloc(sizeof(HashTableImpl));
ht->buckets = (HashTableBucket*) calloc(sizeof(HashTableBucket), capacity);
ht->capacity = capacity;
return (HashTable) ht;
}
int hashtable_deinit(HashTable* ht) {
HashTableImpl* ht_impl = (HashTableImpl*) *ht;
for (int i = 0; i < ht_impl->capacity; ++i) {
HashTableBucket bucket = ht_impl->buckets[i];
free(bucket.data);
}
free(ht_impl->buckets);
free(ht_impl);
ht = NULL;
return 0;
}
void* hashtable_get(HashTable ht, char* key) {
HashTableImpl* ht_impl = (HashTableImpl*) ht;
int index = hash(key, ht_impl->capacity);
HashTableBucket bucket = ht_impl->buckets[index];
for (int i = 0; i < bucket.length; ++i) {
HashTableData data = bucket.data[i];
if (!data.deleted && strcmp(data.key, key) == 0) return data.data;
}
return NULL;
}
int hashtable_put(HashTable ht, char* key, void* val) {
HashTableImpl* ht_impl = (HashTableImpl*) ht;
int index = hash(key, ht_impl->capacity);
HashTableBucket* bucket = &ht_impl->buckets[index];
//TODO: reuse the deleted?
for (int i = 0; i < bucket->length; ++i) {
HashTableData* data = &bucket->data[i];
if (strcmp(data->key, key) == 0) {
data->data = val;
data->deleted = 0;
return 0;
}
}
//otherwise, realloc
bucket->length++;
bucket->data = realloc(bucket->data, sizeof(HashTableData) * bucket->length);
HashTableData newData = {
.key = key,
.data = val,
.deleted = 0
};
bucket->data[bucket->length - 1] = newData;
return 0;
}
int hashtable_remove(HashTable ht, char* key) {
HashTableImpl* ht_impl = (HashTableImpl*) ht;
int index = hash(key, ht_impl->capacity);
HashTableBucket* bucket = &ht_impl->buckets[index];
for (int i = 0; i < bucket->length; ++i) {
HashTableData* data = &bucket->data[i];
if (!data->deleted && strcmp(data->key, key) == 0) {
data->deleted = 1;
return 1;
}
}
return 0;
}
|
