0
|
1 #include "datum.h"
|
|
2 #include "structs.h"
|
|
3 #include "debugmacros.h"
|
|
4 #include <string.h>
|
|
5 #include <stdlib.h>
|
|
6 //Index, Swap, Remove, Set, Length, New
|
|
7
|
|
8 ternary_node * find_node(datum * dict, datum * key, BOOL novalue)
|
|
9 {
|
|
10 int i = 0;
|
|
11 ternary_node * nodes;
|
|
12 ternary_node * current = ((dict_data *)dict->c.generic.data)->nodes;
|
|
13 nodes = current;
|
|
14 if(((dict_data *)dict->c.generic.data)->num_nodes <= 0 || key->c.generic.len <= 1)
|
|
15 return NULL;
|
|
16 while(current >= nodes)
|
|
17 {
|
|
18 DEBUGPRINTF("current->letter: %c, key[%d]: %c\n", current->letter, i, ((char*)key->c.generic.data)[i]);
|
|
19 if(((char*)key->c.generic.data)[i] == current->letter)
|
|
20 if(i == (key->c.generic.len-2))
|
|
21 if(current->payload || novalue)
|
|
22 return current;
|
|
23 else
|
|
24 return NULL;
|
|
25 else
|
|
26 {
|
|
27 current = nodes + current->next;
|
|
28 ++i;
|
|
29 }
|
|
30 else if(((char *)key->c.generic.data)[i] > current->letter)
|
|
31 current = nodes + current->right;
|
|
32 else
|
|
33 current = nodes + current->left;
|
|
34 }
|
|
35 return NULL;
|
|
36 }
|
|
37
|
|
38 int vis_dict_index(datum ** inputlist, queue_entry * worker_entry)
|
|
39 {
|
|
40 datum * output;
|
|
41 int i = 0;
|
|
42 ternary_node * found = find_node(inputlist[0], inputlist[1], FALSE);
|
|
43 release_ref(inputlist[1]);
|
|
44 if(found)
|
|
45 {
|
|
46 DEBUGPRINTF("Found payload: %X\n", found->payload);
|
|
47 /*if(found->payload->type == BUILTIN_TYPE_STRING)
|
|
48 {
|
|
49 DEBUGPRINTF("Payload: %s\n", found->payload->c.generic.data);
|
|
50 }*/
|
|
51
|
|
52 output = add_ref(found->payload);
|
|
53 inputlist[1] = NULL;
|
|
54 }
|
|
55 else
|
|
56 {
|
|
57 inputlist[1] = new_datum(BUILTIN_TYPE_YESNO, 2, 0, worker_entry->instance->def->program);
|
|
58 inputlist[1]->c.integers.num_a = 0;
|
|
59 output = NULL;
|
|
60 }
|
|
61 release_ref(inputlist[0]);
|
|
62 inputlist[0] = output;
|
|
63 return 0;
|
|
64 }
|
|
65
|
|
66 int vis_dict_swap(datum ** inputlist, queue_entry * worker_entry)
|
|
67 {
|
|
68 ternary_node *first, *second;
|
|
69 datum * temp;
|
|
70 inputlist[0] = copy_datum(inputlist[0],0);
|
|
71 first = find_node(inputlist[0], inputlist[1], FALSE);
|
|
72 if(first)
|
|
73 {
|
|
74 second = find_node(inputlist[0], inputlist[2], FALSE);
|
|
75 if(second)
|
|
76 {
|
|
77 temp = first->payload;
|
|
78 first->payload = second->payload;
|
|
79 second->payload = temp;
|
|
80 }
|
|
81 }
|
|
82 release_ref(inputlist[1]);
|
|
83 release_ref(inputlist[2]);
|
|
84 return 0;
|
|
85 }
|
|
86
|
|
87 int vis_dict_remove(datum ** inputlist, queue_entry * worker_entry)
|
|
88 {
|
|
89 //NOTE: Currently optimized for speed not for memory usage
|
|
90 //Doesn't remove ternary_nodes that are no longer needed
|
|
91 ternary_node * found;
|
|
92 dict_data * dict;
|
|
93 inputlist[0] = copy_datum(inputlist[0],0);
|
|
94 found = find_node(inputlist[0], inputlist[1], FALSE);
|
|
95 release_ref(inputlist[1]);
|
|
96 dict = (dict_data *)inputlist[0]->c.generic.data;
|
|
97 if(found)
|
|
98 {
|
|
99 release_ref(found->payload);
|
|
100 found->payload = NULL;
|
|
101 --(dict->num_entries);
|
|
102 }
|
|
103 return 0;
|
|
104 }
|
|
105
|
|
106 int vis_dict_set(datum ** inputlist, queue_entry * worker_entry)
|
|
107 {
|
|
108 ternary_node * found, *current, *last;
|
|
109 dict_data * dict, *new_dict;
|
|
110 int new_node_storage,i,dir;
|
|
111 int newlen;
|
|
112 //DEBUGPRINTF("Payload: %s\n", inputlist[2]->c.generic.data);
|
|
113 inputlist[0] = copy_datum(inputlist[0],0);
|
|
114 found = find_node(inputlist[0], inputlist[1], TRUE);
|
|
115 dict = (dict_data *)inputlist[0]->c.generic.data;
|
|
116 DEBUGPRINTF("key: %s\n", inputlist[1]->c.generic.data);
|
|
117 DEBUGPRINTF("Num nodes: %d, num entries: %d\n", dict->num_nodes, dict->num_entries);
|
|
118 if(found)
|
|
119 {
|
|
120 if(found->payload)
|
|
121 release_ref(found->payload);
|
|
122 else
|
|
123 ++(dict->num_entries);
|
|
124 found->payload = inputlist[2];
|
|
125 }
|
|
126 else if(inputlist[1]->c.generic.len > 1) //FIXME: silently fail on zero-length keys for now
|
|
127 {
|
|
128 if(dict->num_nodes)
|
|
129 {
|
|
130 current = dict->nodes;
|
|
131 i = 0;
|
|
132 while(current >= dict->nodes)
|
|
133 {
|
|
134 DEBUGPRINTF("Current node: %X\n", current);
|
|
135 last = current;
|
|
136 DEBUGPRINTF("Current letter: %c, key letter: %c\n", current->letter,((char *)inputlist[1]->c.generic.data)[i]);
|
|
137 if(((char *)inputlist[1]->c.generic.data)[i] == current->letter)
|
|
138 {
|
|
139 DEBUGPUTS("Went straight\n");
|
|
140 ++i;
|
|
141 current = dict->nodes + current->next;
|
|
142 dir = 0;
|
|
143 }
|
|
144 else if(((char *)inputlist[1]->c.generic.data)[i] > current->letter)
|
|
145 {
|
|
146 DEBUGPUTS("Went right\n");
|
|
147 current = dict->nodes + current->right;
|
|
148 dir = 1;
|
|
149 }
|
|
150 else
|
|
151 {
|
|
152 DEBUGPUTS("Went left\n");
|
|
153 current = dict->nodes + current->left;
|
|
154 dir = 2;
|
|
155 }
|
|
156 }
|
|
157 DEBUGPRINTF("Matched %d out of %d characters\n", i, (inputlist[1]->c.generic.len-1));
|
|
158 DEBUGPRINTF("node_storage: %d, num_nodes: %d\n", dict->node_storage, dict->num_nodes);
|
|
159 if((dict->node_storage-dict->num_nodes) < ((inputlist[1]->c.generic.len-1) - i))
|
|
160 {
|
|
161 DEBUGPUTS("Allocating more storage\n");
|
|
162 new_node_storage = inputlist[1]->c.generic.len - 1 - i + dict->num_nodes;
|
|
163 new_node_storage += new_node_storage >> 1; //1.5 times required storage
|
|
164 newlen = sizeof(dict_data) + sizeof(ternary_node) * (new_node_storage-1);
|
|
165 new_dict = malloc(newlen);
|
|
166 DEBUGPRINTF("After malloc: new_dict = %X, size: %d, new_node_storage: %d\n", new_dict, newlen, new_node_storage);
|
|
167 memcpy(new_dict, dict, sizeof(dict_data) + sizeof(ternary_node) * (dict->num_nodes-1));
|
|
168 DEBUGPUTS("After memcpyy\n");
|
|
169 new_dict->node_storage = new_node_storage;
|
|
170 //new_dict->num_entries = dict->num_entries + 1;
|
|
171 new_dict->num_nodes = dict->num_nodes;
|
|
172 DEBUGPRINTF("last was: %X, dict->nodes was: %X, ", last, dict->nodes);
|
|
173 last = new_dict->nodes + (last - dict->nodes);
|
|
174 DEBUGPRINTF("last is now: %X, dict->nodes is now : %X, ", last, new_dict->nodes);
|
|
175 VIS_FREE(dict, "dictionary object");
|
|
176 DEBUGPUTS("After free\n");
|
|
177 dict = new_dict;
|
|
178 inputlist[0]->c.generic.data = dict;
|
|
179 inputlist[0]->c.generic.len = newlen;
|
|
180 }
|
|
181 ++(dict->num_entries);
|
|
182 DEBUGPRINTF("Setting current to: %X\n", dict->nodes + dict->num_nodes);
|
|
183 current =dict->nodes + dict->num_nodes;
|
|
184 DEBUGPUTS("Setting left, right and next pointer to null\n");
|
|
185 current->left = current->right = current->next = -1;
|
|
186 current->payload = NULL;
|
|
187 current->letter = ((char *)inputlist[1]->c.generic.data)[i];
|
|
188 DEBUGPRINTF("Setting pointer in last node (%X) to current node\n", last);
|
|
189 if(dir == 1)
|
|
190 last->right = dict->num_nodes;
|
|
191 else if(dir == 2)
|
|
192 last->left = dict->num_nodes;
|
|
193 else
|
|
194 last->next = dict->num_nodes;
|
|
195 ++i;
|
|
196 ++(dict->num_nodes);
|
|
197 last = current;
|
|
198 DEBUGPUTS("Entering node add loop\n");
|
|
199 for(;i < (inputlist[1]->c.generic.len-1); ++i)
|
|
200 {
|
|
201 DEBUGPRINTF("Adding node at index %d\n", dict->num_nodes);
|
|
202 current = dict->nodes + dict->num_nodes;
|
|
203 last->next = dict->num_nodes;
|
|
204 current->left = current->right = current->next = -1;
|
|
205 current->payload = NULL;
|
|
206 current->letter = ((char *)inputlist[1]->c.generic.data)[i];
|
|
207 ++(dict->num_nodes);
|
|
208 last = current;
|
|
209 }
|
|
210 DEBUGPUTS("Loop complete\n");
|
|
211 last->payload = inputlist[2];
|
|
212 }
|
|
213 else
|
|
214 {
|
|
215 if(dict->node_storage < (inputlist[1]->c.generic.len-1))
|
|
216 {
|
|
217 VIS_FREE(dict, "dictionary object");
|
|
218 newlen = sizeof(dict_data) + sizeof(ternary_node) * ((inputlist[1]->c.generic.len-1)<<2);
|
|
219 dict = malloc(newlen);
|
|
220 dict->node_storage = ((inputlist[1]->c.generic.len-1)<<2) + 1;
|
|
221 inputlist[0]->c.generic.data = dict;
|
|
222 inputlist[0]->c.generic.len = newlen;
|
|
223
|
|
224 }
|
|
225 dict->num_entries = 1;
|
|
226 dict->num_nodes = (inputlist[1]->c.generic.len-1);
|
|
227 for(i = 0; i < dict->num_nodes; ++i)
|
|
228 {
|
|
229 dict->nodes[i].left = dict->nodes[i].right = -1;
|
|
230 dict->nodes[i].letter = ((char *)inputlist[1]->c.generic.data)[i];
|
|
231 if(i == (dict->num_nodes - 1))
|
|
232 {
|
|
233 dict->nodes[i].next = -1;
|
|
234 dict->nodes[i].payload = inputlist[2];
|
|
235 }
|
|
236 else
|
|
237 {
|
|
238 dict->nodes[i].next = i + 1;
|
|
239 dict->nodes[i].payload = NULL;
|
|
240 }
|
|
241 }
|
|
242 }
|
|
243 }
|
|
244 release_ref(inputlist[1]);
|
|
245 DEBUGPRINTF("Num nodes after set: %d\n", dict->num_nodes);
|
|
246 //DEBUGPRINTF("Payload: %s\n", inputlist[2]->c.generic.data);
|
|
247 return 0;
|
|
248 }
|
|
249
|
|
250 int vis_dict_length(datum ** inputlist, queue_entry * worker_entry)
|
|
251 {
|
|
252 datum * output;
|
|
253 dict_data * dict = ((dict_data *)inputlist[0]->c.generic.data);
|
|
254 output = new_datum(BUILTIN_TYPE_WHOLE, 2, 0, worker_entry->instance->def->program);
|
|
255 output->c.integers.num_a = dict->num_entries;
|
|
256 release_ref(inputlist[0]);
|
|
257 inputlist[0] = output;
|
|
258 return 0;
|
|
259 }
|
|
260
|
|
261 datum * create_dict(program * prog)
|
|
262 {
|
|
263 dict_data * dict;
|
|
264 datum * dat = new_datum(BUILTIN_TYPE_DICT, 1, sizeof(dict_data) + sizeof(ternary_node)*23, prog);
|
|
265 dict = (dict_data *)dat->c.generic.data;
|
|
266 dict->num_entries = 0;
|
|
267 dict->num_nodes = 0;
|
|
268 dict->node_storage = 24;
|
|
269 return dat;
|
|
270 }
|
|
271
|
|
272 int vis_dict_new(datum ** inputlist, queue_entry * worker_entry)
|
|
273 {
|
|
274 inputlist[0] = create_dict(worker_entry->instance->def->program);
|
|
275 return 0;
|
|
276 }
|
|
277
|
|
278 #define APPEND_KEY_STORE(key, key_store, key_size, val) if(key_size == key_store) { key_store = key_store + (key_store>>1); key = realloc(key, key_store); } key[key_size++] = val
|
|
279
|
|
280 int vis_dict_first(datum ** inputlist, queue_entry * worker_entry)
|
|
281 {
|
|
282 dict_data * dict = inputlist[0]->c.generic.data;
|
|
283 char * key;
|
|
284 int key_store = 128;
|
|
285 int key_size = 0;
|
|
286
|
|
287 int i = 0;
|
|
288 ternary_node * nodes;
|
|
289 ternary_node * current = dict->nodes;
|
|
290 nodes = current;
|
|
291 if(dict->num_nodes <= 0)
|
|
292 {
|
|
293 inputlist[1] = inputlist[0];
|
|
294 inputlist[0] = NULL;
|
|
295 }
|
|
296 else
|
|
297 {
|
|
298 key = malloc(128);
|
|
299 while(1)
|
|
300 {
|
|
301 if(current->left >= 0)
|
|
302 {
|
|
303 current = nodes + current->left;
|
|
304 } else if(current->payload) {
|
|
305 APPEND_KEY_STORE(key, key_store, key_size, current->letter);
|
|
306 APPEND_KEY_STORE(key, key_store, key_size, '\0');
|
|
307 release_ref(inputlist[0]);
|
|
308 inputlist[0] = new_datum(BUILTIN_TYPE_STRING, 2, 0, worker_entry->instance->def->program);
|
|
309 inputlist[0]->union_type = 1;
|
|
310 inputlist[0]->c.generic.data = key;
|
|
311 inputlist[0]->c.generic.len = key_size;
|
|
312 inputlist[1] = NULL;
|
|
313 break;
|
|
314 } else if(current->next >= 0) {
|
|
315 APPEND_KEY_STORE(key, key_store, key_size, current->letter);
|
|
316 current = nodes + current->next;
|
|
317 } else if(current->right >= 0) {
|
|
318 current = nodes + current->right;
|
|
319 } else {
|
|
320 inputlist[1] = inputlist[0];
|
|
321 inputlist[0] = NULL;
|
|
322 VIS_FREE(key, "dictionary key store");
|
|
323 break;
|
|
324 }
|
|
325 }
|
|
326 }
|
|
327 return 0;
|
|
328 }
|
|
329
|
|
330 int vis_dict_next(datum ** inputlist, queue_entry * worker_entry)
|
|
331 {
|
|
332 dict_data * dict = inputlist[0]->c.generic.data;
|
|
333 char * key;
|
|
334 char * old_key = inputlist[1]->c.generic.data;
|
|
335 int old_key_len = inputlist[1]->c.generic.len-2;
|
|
336 int key_store = inputlist[1]->c.generic.len;
|
|
337 int key_size = 0;
|
|
338
|
|
339 int i = 0;
|
|
340 ternary_node * nodes;
|
|
341 ternary_node * current = dict->nodes;
|
|
342 ternary_node * decision = NULL;
|
|
343 int decision_key_size;
|
|
344 BOOL next_flag = FALSE;
|
|
345 nodes = current;
|
|
346
|
|
347 if(dict->num_nodes <= 0)
|
|
348 {
|
|
349 release_ref(inputlist[1]);
|
|
350 inputlist[1] = inputlist[0];
|
|
351 inputlist[0] = NULL;
|
|
352 return 0;
|
|
353 }
|
|
354 else
|
|
355 {
|
|
356 key = malloc(key_store);
|
|
357 while(current >= nodes)
|
|
358 {
|
|
359 if(old_key[i] == current->letter)
|
|
360 if(i == (old_key_len))
|
|
361 {
|
|
362 if(current->left >= 0)
|
|
363 {
|
|
364 current = nodes + current->left;
|
|
365 break;
|
|
366 }
|
|
367 else if(current->next >= 0)
|
|
368 {
|
|
369 APPEND_KEY_STORE(key, key_store, key_size, current->letter);
|
|
370 current = nodes + current->next;
|
|
371 break;
|
|
372 }
|
|
373 else if(current->right >= 0)
|
|
374 {
|
|
375 current = nodes + current->right;
|
|
376 break;
|
|
377 }
|
|
378 else
|
|
379 {
|
|
380 if(decision)
|
|
381 {
|
|
382 key_size = decision_key_size;
|
|
383 current = decision;
|
|
384 if(next_flag)
|
|
385 {
|
|
386 APPEND_KEY_STORE(key, key_store, key_size, current->letter);
|
|
387 current = nodes + current->next;
|
|
388 }
|
|
389 break;
|
|
390 }
|
|
391 else
|
|
392 {
|
|
393 VIS_FREE(key, "dictionary key store");
|
|
394 release_ref(inputlist[1]);
|
|
395 inputlist[1] = inputlist[0];
|
|
396 inputlist[0] = NULL;
|
|
397 return 0;
|
|
398 }
|
|
399 }
|
|
400 }
|
|
401 else
|
|
402 {
|
|
403 if(current->right >= 0)
|
|
404 {
|
|
405 decision = nodes + current->right;
|
|
406 decision_key_size = key_size;
|
|
407 next_flag = FALSE;
|
|
408 }
|
|
409 APPEND_KEY_STORE(key, key_store, key_size, current->letter);
|
|
410 ++i;
|
|
411 current = nodes + current->next;
|
|
412 }
|
|
413 else if(old_key[i] > current->letter)
|
|
414 current = nodes + current->right;
|
|
415 else
|
|
416 {
|
|
417 if(current->next >= 0)
|
|
418 {
|
|
419 //APPEND_KEY_STORE(key, key_store, key_size, current->letter);
|
|
420 decision = current;//nodes + current->next;
|
|
421 decision_key_size = key_size;
|
|
422 next_flag = TRUE;
|
|
423 }
|
|
424 else if(current->right >= 0)
|
|
425 {
|
|
426 decision = nodes + current->right;
|
|
427 decision_key_size = key_size;
|
|
428 next_flag = FALSE;
|
|
429 }
|
|
430 current = nodes + current->left;
|
|
431 }
|
|
432 }
|
|
433 if(current < nodes)
|
|
434 {
|
|
435 VIS_FREE(key, "dictionary key store");
|
|
436 release_ref(inputlist[1]);
|
|
437 inputlist[1] = inputlist[0];
|
|
438 inputlist[0] = NULL;
|
|
439 return 0;
|
|
440 }
|
|
441 while(1)
|
|
442 {
|
|
443 if(current->left >= 0)
|
|
444 {
|
|
445 current = nodes + current->left;
|
|
446 } else if(current->payload) {
|
|
447 APPEND_KEY_STORE(key, key_store, key_size, current->letter);
|
|
448 APPEND_KEY_STORE(key, key_store, key_size, '\0');
|
|
449 release_ref(inputlist[0]);
|
|
450 release_ref(inputlist[1]);
|
|
451 inputlist[1] = NULL;
|
|
452 inputlist[0] = new_datum(BUILTIN_TYPE_STRING, 2, 0, worker_entry->instance->def->program);
|
|
453 inputlist[0]->union_type = 1;
|
|
454 inputlist[0]->c.generic.data = key;
|
|
455 inputlist[0]->c.generic.len = key_size;
|
|
456 break;
|
|
457 } else if(current->next >= 0) {
|
|
458 APPEND_KEY_STORE(key, key_store, key_size, current->letter);
|
|
459 current = nodes + current->next;
|
|
460 } else if(current->right >= 0) {
|
|
461 current = nodes + current->right;
|
|
462 } else {
|
|
463 release_ref(inputlist[1]);
|
|
464 inputlist[1] = inputlist[0];
|
|
465 inputlist[0] = NULL;
|
|
466 VIS_FREE(key, "dictionary key store");
|
|
467 break;
|
|
468 }
|
|
469 }
|
|
470 }
|
|
471 return 0;
|
|
472 }
|
|
473
|
|
474
|
|
475
|