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
|
#include "bowl.h"
#include "array.h"
#include "hash.h"
#include "utils.h"
#include <malloc.h>
typedef struct {
char *key;
struct bowl *data;
} hash_item;
err_t hash_insert_key(struct bowl *self, char *key, struct bowl *child)
{
CHECK(self, INVALID_STATE)
CHECK(child, INVALID_STATE)
CHECK(key, INVALID_STATE)
// Even though we're a HASH node, we use an array under the hood
struct bowl_arr *arr = self->_pl.array;
CHECK(arr, INVALID_STATE)
size_t idx;
err_t e = _hash(key, arr->size, &idx);
if(e) return e;
// If the index is used, rescale and try again
if(arr->ptr[idx] != NULL) {
struct bowl_arr *prev = arr;
// Allocate new hash array
e = array_malloc(self, arr->size * 2);
if(e) return e;
for(int i = 0; i < arr->size; i++) {
if(arr->ptr[i] != NULL) {
// FIXME: This is horrible
hash_item *item = (hash_item*) arr->ptr[i];
e = hash_insert_key(self, item->key, item->data);
if(e) return e;
}
}
e = hash_insert_key(self, key, child);
if(e) return e;
hash_free_shallow(prev);
} else {
hash_item *item = malloc(sizeof(hash_item));
CHECK(item, MALLOC_FAILED)
item->key = calloc(sizeof(char), REAL_STRLEN(key));
CHECK(item->key, MALLOC_FAILED)
strcpy(item->key, key);
item->data = child;
arr->ptr[idx] = (struct bowl*) item;
arr->used += 1;
}
return OK;
}
err_t hash_remove_key(struct bowl *self, char *key, struct bowl **child)
{
CHECK(self, INVALID_STATE)
CHECK(child, INVALID_STATE)
CHECK(key, INVALID_STATE)
// Even though we're a HASH node, we use an array under the hood
struct bowl_arr *arr = self->_pl.array;
CHECK(arr, INVALID_STATE)
size_t idx;
err_t e = _hash(key, arr->size, &idx);
if(e) return e;
(*child) = arr->ptr[idx];
arr->used -= 1;
arr->ptr[idx] = NULL;
return OK;
}
err_t hash_free(struct bowl *self)
{
CHECK(self, INVALID_PARAMS)
struct bowl_arr *arr = self->_pl.array;
CHECK(arr, INVALID_PARAMS)
err_t e = OK;
for(int i = 0; i < arr->size; i++) {
hash_item *item = (hash_item *) arr->ptr[i];
if(item != NULL) {
CHECK(item->data, INVALID_STATE)
CHECK(item->key, INVALID_STATE)
e = bowl_free(item->data);
if(e) break;
free(item->key);
free(item);
}
}
free(arr->ptr);
free(arr);
return e;
}
err_t hash_free_shallow(struct bowl_arr *arr)
{
CHECK(arr, INVALID_PARAMS);
for(int i = 0; i < arr->size; i++) {
hash_item *item = (hash_item *) arr->ptr[i];
if(item != NULL) {
free(item->key);
free(item);
}
}
free(arr->ptr);
free(arr);
return OK;
}
|
