Mercurial > repos > rhope

comparison dict.c @ 0:76568becd6d6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Rhope Alpha 2a source import
author Mike Pavone <pavone@retrodev.com>
date Tue, 28 Apr 2009 23:06:07 +0000
parents
children 94c885692eb5
comparison
equal deleted inserted replaced
-1:000000000000 0:76568becd6d6
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