Mercurial > repos > rhope
comparison dict.c @ 0:76568becd6d6
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 |