1// This file is part of SmallBASIC
2//
3// Support for dictionary/associative array variables
4//
5// This program is distributed under the terms of the GPL v2.0 or later
6// Download the GNU Public License (GPL) from www.gnu.org
7//
8// Copyright(C) 2007-2016 Chris Warren-Smith.
9
10#include "config.h"
11
12#include "common/sys.h"
13#include "common/var.h"
14#include "common/smbas.h"
15#include "common/hashmap.h"
16
17#define MAP_SIZE 32
18
19/**
20 * Our internal tree element node
21 */
22typedef struct Node {
23 var_p_t key;
24 var_p_t value;
25 struct Node *left, *right;
26} Node;
27
28/**
29 * Returns a new tree node
30 */
31Node *tree_create_node(var_p_t key) {
32 Node *node = (Node *)malloc(sizeof(Node));
33 node->key = key;
34 node->value = NULL;
35 node->left = NULL;
36 node->right = NULL;
37 return node;
38}
39
40/**
41 * cleanup the given element
42 */
43void tree_delete_node(Node *node) {
44 // cleanup v_new
45 v_free(node->key);
46 v_detach(node->key);
47
48 // cleanup v_new
49 if (node->value) {
50 v_free(node->value);
51 v_detach(node->value);
52 }
53
54 // cleanup the node
55 free(node);
56}
57
58static inline int tree_compare(const char *key, int length, var_p_t vkey) {
59 int len1 = length;
60 if (len1 && key[len1 - 1] == '\0') {
61 len1--;
62 }
63 int len2 = vkey->v.p.length;
64 if (len2 && vkey->v.p.ptr[len2 - 1] == '\0') {
65 len2--;
66 }
67 return strcaselessn(key, len1, vkey->v.p.ptr, len2);
68}
69
70void tree_destroy(Node *node) {
71 if (node->left != NULL) {
72 tree_destroy(node->left);
73 }
74 if (node->right != NULL) {
75 tree_destroy(node->right);
76 }
77 tree_delete_node(node);
78}
79
80Node *tree_search(Node **rootp, const char *key, int length) {
81 while (*rootp != NULL) {
82 int r = tree_compare(key, length, (*rootp)->key);
83 if (r == 0) {
84 return *rootp;
85 }
86 rootp = (r < 0) ? &(*rootp)->left : &(*rootp)->right;
87 }
88 Node *result = tree_create_node(NULL);
89 *rootp = result;
90 return result;
91}
92
93Node *tree_find(Node **rootp, const char *key, int length) {
94 while (*rootp != NULL) {
95 int r = tree_compare(key, length, (*rootp)->key);
96 if (r == 0) {
97 return *rootp;
98 }
99 rootp = (r < 0) ? &(*rootp)->left : &(*rootp)->right;
100 }
101 return NULL;
102}
103
104int tree_foreach(const Node *nodep, hashmap_foreach_func func, hashmap_cb *data) {
105 if (nodep != NULL) {
106 if (nodep->left != NULL && !tree_foreach(nodep->left, func, data)) {
107 return 0;
108 }
109
110 if (func(data, nodep->key, nodep->value)) {
111 return 0;
112 }
113
114 if (nodep->right != NULL && !tree_foreach(nodep->right, func, data)) {
115 return 0;
116 }
117 }
118 return 1;
119}
120
121/**
122 * initialise the variable as a map
123 */
124void hashmap_create(var_p_t map, int size) {
125 v_free(map);
126 map->type = V_MAP;
127 map->v.m.count = 0;
128 map->v.m.id = -1;
129 if (size == 0) {
130 map->v.m.size = MAP_SIZE;
131 } else {
132 map->v.m.size = (size * 100) / 75;
133 }
134 map->v.m.map = calloc(map->v.m.size, sizeof(Node *));
135}
136
137int hashmap_destroy(var_p_t var_p) {
138 if (var_p->type == V_MAP && var_p->v.m.map != NULL) {
139 Node **table = (Node **)var_p->v.m.map;
140 for (int i = 0; i < var_p->v.m.size; i++) {
141 if (table[i] != NULL) {
142 tree_destroy(table[i]);
143 }
144 }
145 free(var_p->v.m.map);
146 }
147 return 0;
148}
149
150int hashmap_get_hash(const char *key, int length) {
151 int hash = 1, i;
152 for (i = 0; i < length && key[i] != '\0'; i++) {
153 hash += to_lower(key[i]);
154 hash <<= 3;
155 hash ^= (hash >> 3);
156 }
157 return hash;
158}
159
160static inline Node *hashmap_search(var_p_t map, const char *key, int length) {
161 int index = hashmap_get_hash(key, length) % map->v.m.size;
162 Node **table = (Node **)map->v.m.map;
163 Node *result = table[index];
164 if (result == NULL) {
165 // new entry
166 result = table[index] = tree_create_node(NULL);
167 } else {
168 int r = tree_compare(key, length, result->key);
169 if (r < 0) {
170 result = tree_search(&result->left, key, length);
171 } else if (r > 0) {
172 result = tree_search(&result->right, key, length);
173 }
174 }
175 return result;
176}
177
178static inline Node *hashmap_find(var_p_t map, const char *key) {
179 int length = strlen(key);
180 int index = hashmap_get_hash(key, length) % map->v.m.size;
181 Node **table = (Node **)map->v.m.map;
182 Node *result = table[index];
183 if (result != NULL) {
184 int r = tree_compare(key, length, result->key);
185 if (r < 0 && result->left != NULL) {
186 result = tree_find(&result->left, key, length);
187 } else if (r > 0 && result->right != NULL) {
188 result = tree_find(&result->right, key, length);
189 } else if (r != 0) {
190 result = NULL;
191 }
192 }
193 return result;
194}
195
196var_p_t hashmap_put(var_p_t map, const char *key, int length) {
197 Node *node = hashmap_search(map, key, length);
198 if (node->key == NULL) {
199 node->key = v_new();
200 node->value = v_new();
201 v_setstrn(node->key, key, length);
202 map->v.m.count++;
203 }
204 return node->value;
205}
206
207var_p_t hashmap_putc(var_p_t map, const char *key, int length) {
208 Node *node = hashmap_search(map, key, length);
209 if (node->key == NULL) {
210 var_t *var_key = v_new();
211 var_key->type = V_STR;
212 var_key->v.p.length = length;
213 var_key->v.p.ptr = (char *)key;
214 var_key->v.p.owner = 0;
215 node->key = var_key;
216 node->value = v_new();
217 map->v.m.count++;
218 }
219 return node->value;
220}
221
222var_p_t hashmap_putv(var_p_t map, const var_p_t key) {
223 // hashmap takes ownership of key
224 if (key->type != V_STR) {
225 // keys are always strings
226 v_tostr(key);
227 }
228
229 Node *node = hashmap_search(map, key->v.p.ptr, key->v.p.length);
230 if (node->key == NULL) {
231 node->key = key;
232 node->value = v_new();
233 map->v.m.count++;
234 } else {
235 // discard unused key
236 v_free(key);
237 v_detach(key);
238 }
239 return node->value;
240}
241
242var_p_t hashmap_get(var_p_t map, const char *key) {
243 var_p_t result;
244 Node *node = hashmap_find(map, key);
245 if (node != NULL) {
246 result = node->value;
247 } else {
248 result = NULL;
249 }
250 return result;
251}
252
253void hashmap_foreach(var_p_t map, hashmap_foreach_func func, hashmap_cb *data) {
254 if (map && map->type == V_MAP) {
255 Node **table = (Node **)map->v.m.map;
256 for (int i = 0; i < map->v.m.size; i++) {
257 if (table[i] != NULL) {
258 if (!tree_foreach(table[i], func, data)) {
259 break;
260 }
261 }
262 }
263 }
264}
265