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
150
151
152
153
154
155
156
157
|
/*
* strmap.c
*
* A closed-addressing based string -> string hash map
* for CISC 301: Operating Systems
*/
#include "strmap.h"
struct node {
char *key;
char *value;
struct node *next;
};
struct bucket {
struct node *node;
};
struct strmap {
struct bucket *buckets;
size_t bucket_cnt;
size_t node_cnt;
hash_func hash;
};
static const size_t BCKT_CNT = 101;
static void _destroy_node(struct node *nd) {
free(nd->key);
free(nd->value);
free(nd);
}
strmap *strmap_create(hash_func hash) {
strmap *map = calloc(1, sizeof(*map));
if (!map)
return NULL;
map->buckets = calloc(BCKT_CNT, sizeof(struct bucket));
if (!map->buckets) {
free(map);
return NULL;
}
map->bucket_cnt = BCKT_CNT;
map->node_cnt = 0;
map->hash = hash;
return map;
}
void strmap_destroy(strmap *map) {
for (size_t i = 0; i < map->bucket_cnt; i++) {
struct node *nd = map->buckets[i].node;
while (nd) {
struct node *nd2 = nd->next;
_destroy_node(nd);
nd = nd2;
}
}
free(map->buckets);
free(map);
}
strmap_status strmap_put(strmap *map, const char *key, const char *value) {
if (!key || !value)
return STRMAP_ERR;
struct bucket *bckt = map->buckets + map->hash(key, map->bucket_cnt);
/*
* check if the key already exists in the bucket, in which case we
* do an update, rather than allocating a new node
*/
for (struct node *nd = bckt->node; nd; nd = nd->next) {
if (!strcmp(nd->key, key)) {
char *old_value = nd->value;
nd->value = strdup(value);
/* if the allocation fails, put the old value back */
if (!nd->value) {
nd->value = old_value;
return STRMAP_ERR;
}
free(old_value);
return STRMAP_OK;
}
}
struct node *nd = malloc(sizeof(struct node));
if (!nd) {
/* node allocation failed */
goto error_nodealloc;
}
nd->key = strdup(key);
nd->value = strdup(value);
if (nd->key == NULL || nd->value == NULL) {
/* string allocation failed */
goto error_stringalloc;
}
nd->next = bckt->node;
bckt->node = nd;
map->node_cnt++;
return STRMAP_OK;
error_stringalloc:
free(nd->key);
free(nd->value);
error_nodealloc:
free(nd);
return STRMAP_ERR;
}
strmap_status strmap_get(const strmap *map, const char *key,
const char **value) {
if (!key)
return STRMAP_NOTFOUND;
size_t idx = map->hash(key, map->bucket_cnt);
struct node *nd;
for (nd = map->buckets[idx].node; nd; nd = nd->next) {
if (!strcmp(nd->key, key)) {
*value = nd->value;
return STRMAP_OK;
}
}
return STRMAP_NOTFOUND;
}
strmap_status strmap_delete(strmap *map, const char *key) {
if (!key)
return STRMAP_NOTFOUND;
struct node **nd_ptr = &(map->buckets[map->hash(key, map->bucket_cnt)].node);
while (*nd_ptr) {
struct node *nd = *nd_ptr;
if (!strcmp(nd->key, key)) {
*nd_ptr = nd->next;
_destroy_node(nd);
map->node_cnt--;
return STRMAP_OK;
}
nd_ptr = &nd->next;
}
return STRMAP_NOTFOUND;
}
size_t strmap_size(const strmap *map) { return map->node_cnt; }
|