YAP 7.1.0
core_tries.c
1/*********************************************
2 File: core_tries.c
3 Author: Ricardo Rocha
4 Comments: Tries core module for Yap Prolog
5 version: $ID$
6*********************************************/
7
8/* -------------------------- */
9/* Includes */
10/* -------------------------- */
11
12#include "core_tries.h"
13#include <stdio.h>
14#include <stdlib.h>
15#include <string.h>
16
17/* -------------------------- */
18/* Local Procedures */
19/* -------------------------- */
20
21static TrNode put_entry(TrNode node, YAP_Term entry);
22static TrNode check_entry(TrNode node, YAP_Term entry);
23static YAP_Term get_entry(TrNode node, YAP_Term *stack_list, TrNode *cur_node);
24static void remove_entry(TrNode node);
25static void remove_child_nodes(TrNode node);
26static TrNode copy_child_nodes(TrNode parent_dest, TrNode node_source);
27static void traverse_and_add(TrNode parent_dest, TrNode parent_source);
28static void traverse_and_join(TrNode parent_dest, TrNode parent_source);
29static void traverse_and_intersect(TrNode parent_dest, TrNode parent_source);
30static YAP_Int traverse_and_count_common_entries(TrNode parent1,
31 TrNode parent2);
32static YAP_Int traverse_and_count_entries(TrNode node);
33static void traverse_and_get_usage(TrNode node, YAP_Int depth);
34static void traverse_and_save(TrNode node, FILE *file, int float_block);
35static void traverse_and_load(TrNode parent, FILE *file);
36static void traverse_and_print(TrNode node, int *arity, char *str,
37 int str_index, int mode);
38
39static YAP_Term trie_to_list(TrNode node);
40static YAP_Term trie_to_list_node(TrNode node);
41static YAP_Term trie_to_list_floats(TrNode node);
42
43/* -------------------------- */
44/* Local Variables */
45/* -------------------------- */
46
47static TrEngine CURRENT_TRIE_ENGINE;
48
49static YAP_Int USAGE_ENTRIES, USAGE_NODES, USAGE_VIRTUAL_NODES;
50static YAP_Int CURRENT_AUXILIARY_TERM_STACK_SIZE, CURRENT_TRIE_MODE,
51 CURRENT_LOAD_VERSION, CURRENT_DEPTH, CURRENT_INDEX;
52static YAP_Term *AUXILIARY_TERM_STACK;
53YAP_Term *stack_args, *stack_args_base, *stack_vars, *stack_vars_base;
54static YAP_Functor FunctorComma;
55static void (*DATA_SAVE_FUNCTION)(TrNode, FILE *);
56static void (*DATA_LOAD_FUNCTION)(TrNode, YAP_Int, FILE *);
57static void (*DATA_PRINT_FUNCTION)(TrNode);
58static void (*DATA_ADD_FUNCTION)(TrNode, TrNode);
59static void (*DATA_COPY_FUNCTION)(TrNode, TrNode);
60static void (*DATA_DESTRUCT_FUNCTION)(TrNode);
61
62static YAP_Int TRIE_DISABLE_HASH_TABLE = 0;
63
64/* -------------------------- */
65/* Inline Procedures */
66/* -------------------------- */
67
68static TrNode trie_node_check_insert(TrNode parent, YAP_Term t) {
69 TrNode child;
70
71 CURRENT_DEPTH++;
72 child = TrNode_child(parent);
73 if (child == NULL) {
74 new_trie_node(child, t, parent, NULL, NULL, NULL);
75 TrNode_child(parent) = child;
76 } else if (IS_HASH_NODE(child)) {
77 TrHash hash;
78 TrNode *bucket;
79 int count;
80 hash = (TrHash)child;
81 bucket = TrHash_bucket(hash, HASH_TERM(t, TrHash_seed(hash)));
82 child = *bucket;
83 count = 0;
84 while (child) {
85 if ((TrNode_entry(child) == t) ||
86 (((TrNode_entry(child) == PairEndTermTag) ||
87 (TrNode_entry(child) == PairEndEmptyTag)) &&
88 ((CURRENT_TRIE_MODE & TRIE_MODE_MINIMAL) == TRIE_MODE_MINIMAL)))
89 return child;
90 count++;
91 child = TrNode_next(child);
92 }
93 while (child)
94 ;
95 TrHash_num_nodes(hash)++;
96 new_trie_node(child, t, parent, NULL, *bucket, AS_TR_NODE_NEXT(bucket));
97 if (*bucket)
98 TrNode_previous(*bucket) = child;
99 *bucket = child;
100 if (count > MAX_NODES_PER_BUCKET &&
101 TrHash_num_nodes(hash) > TrHash_num_buckets(hash)) {
102 /* expand trie hash */
103 TrNode chain, next, *first_bucket, *new_bucket;
104 int seed;
105 first_bucket = TrHash_buckets(hash);
106 bucket = first_bucket + TrHash_num_buckets(hash);
107 TrHash_num_buckets(hash) *= 2;
108 new_hash_buckets(hash, TrHash_num_buckets(hash));
109 seed = TrHash_num_buckets(hash) - 1;
110 do {
111 if (*--bucket) {
112 chain = *bucket;
113 do {
114 new_bucket =
115 TrHash_bucket(hash, HASH_TERM(TrNode_entry(chain), seed));
116 next = TrNode_next(chain);
117 TrNode_next(chain) = *new_bucket;
118 TrNode_previous(chain) = AS_TR_NODE_NEXT(bucket);
119 if (*new_bucket)
120 TrNode_previous(*new_bucket) = chain;
121 *new_bucket = chain;
122 chain = next;
123 } while (chain);
124 }
125 } while (bucket != first_bucket);
126 free_hash_buckets(first_bucket, TrHash_num_buckets(hash) / 2);
127 }
128 } else {
129 int count = 0;
130 do {
131 if ((TrNode_entry(child) == t) ||
132 (((TrNode_entry(child) == PairEndTermTag) ||
133 (TrNode_entry(child) == PairEndEmptyTag)) &&
134 ((CURRENT_TRIE_MODE & TRIE_MODE_MINIMAL) == TRIE_MODE_MINIMAL)))
135 return child;
136 count++;
137 child = TrNode_next(child);
138 } while (child);
139 new_trie_node(child, t, parent, NULL, TrNode_child(parent), NULL);
140 TrNode_previous(TrNode_child(parent)) = child;
141 if ((++count > MAX_NODES_PER_TRIE_LEVEL) &&
142 (TRIE_DISABLE_HASH_TABLE == 0)) {
143 /* alloc a new trie hash */
144 TrHash hash;
145 TrNode chain, next, *bucket;
146 new_trie_hash(hash, count, BASE_HASH_BUCKETS);
147 chain = child;
148 do {
149 bucket = TrHash_bucket(
150 hash, HASH_TERM(TrNode_entry(chain), BASE_HASH_BUCKETS - 1));
151 next = TrNode_next(chain);
152 TrNode_next(chain) = *bucket;
153 TrNode_previous(chain) = AS_TR_NODE_NEXT(bucket);
154 if (*bucket)
155 TrNode_previous(*bucket) = chain;
156 *bucket = chain;
157 chain = next;
158 } while (chain);
159 TrNode_child(parent) = (TrNode)hash;
160 } else
161 TrNode_child(parent) = child;
162 }
163 return child;
164}
165
166static TrNode trie_node_insert(TrNode parent, YAP_Term t, TrHash hash) {
167 TrNode child;
168
169 CURRENT_DEPTH++;
170 if (hash) {
171 /* is trie hash */
172 TrNode *bucket;
173 TrHash_num_nodes(hash)++;
174 bucket = TrHash_bucket(hash, HASH_TERM(t, TrHash_seed(hash)));
175 new_trie_node(child, t, parent, NULL, *bucket, AS_TR_NODE_NEXT(bucket));
176 if (*bucket)
177 TrNode_previous(*bucket) = child;
178 *bucket = child;
179 } else {
180 new_trie_node(child, t, parent, NULL, TrNode_child(parent), NULL);
181 if (TrNode_child(parent))
182 TrNode_previous(TrNode_child(parent)) = child;
183 TrNode_child(parent) = child;
184 }
185 return child;
186}
187
188static TrNode trie_node_check(TrNode parent, YAP_Term t) {
189 TrNode child;
190
191 child = TrNode_child(parent);
192 if (IS_HASH_NODE(child)) {
193 TrHash hash;
194 TrNode *bucket;
195 hash = (TrHash)child;
196 bucket = TrHash_bucket(hash, HASH_TERM(t, TrHash_seed(hash)));
197 child = *bucket;
198 if (!child)
199 return NULL;
200 }
201 do {
202 if (TrNode_entry(child) == t)
203 return child;
204 child = TrNode_next(child);
205 } while (child);
206 return NULL;
207}
208
209static YAP_Term trie_to_list_create_simple(const char *atom_name, TrNode node) {
210 YAP_Functor f = YAP_MkFunctor(YAP_LookupAtom(atom_name), 1);
211 YAP_Term child = trie_to_list(TrNode_child(node));
212
213 return YAP_MkApplTerm(f, 1, &child);
214}
215
216static YAP_Term trie_to_list_create_simple_end(const char *atom_name,
217 TrNode node) {
218 YAP_Atom atom = YAP_LookupAtom(atom_name);
219
220 if (IS_LEAF_TRIE_NODE(node)) {
221 return YAP_MkAtomTerm(atom);
222 } else {
223 YAP_Functor f = YAP_MkFunctor(atom, 1);
224 YAP_Term child = trie_to_list(TrNode_child(node));
225 return YAP_MkApplTerm(f, 1, &child);
226 }
227}
228
229static YAP_Term trie_to_list_create_two(const char *atom_name, TrNode node,
230 YAP_Term operand) {
231 YAP_Atom atom = YAP_LookupAtom(atom_name);
232
233 if (IS_LEAF_TRIE_NODE(node)) {
234 YAP_Functor f = YAP_MkFunctor(atom, 1);
235 return YAP_MkApplTerm(f, 1, &operand);
236 } else {
237 YAP_Functor f = YAP_MkFunctor(atom, 2);
238 YAP_Term args[2] = {operand, trie_to_list(TrNode_child(node))};
239 return YAP_MkApplTerm(f, 2, args);
240 }
241}
242
243/* -------------------------- */
244/* API */
245/* -------------------------- */
246
247TrEngine core_trie_init_module(void) {
248 static int init_once = 1;
249 TrEngine engine;
250
251 if (init_once) {
252 new_struct(AUXILIARY_TERM_STACK, YAP_Term,
253 BASE_AUXILIARY_TERM_STACK_SIZE * sizeof(YAP_Term));
254 CURRENT_AUXILIARY_TERM_STACK_SIZE = BASE_AUXILIARY_TERM_STACK_SIZE;
255 CURRENT_TRIE_MODE = TRIE_MODE_STANDARD;
256 FunctorComma = YAP_MkFunctor(YAP_LookupAtom(","), 2);
257 init_once = 0;
258 }
259 new_trie_engine(engine);
260 return engine;
261}
262
263TrNode core_trie_open(TrEngine engine) {
264 TrNode node;
265
266 CURRENT_TRIE_ENGINE = engine;
267 new_trie_node(node, 0, NULL, NULL, TrEngine_trie(engine),
268 AS_TR_NODE_NEXT(&TrEngine_trie(engine)));
269 if (TrEngine_trie(engine))
270 TrNode_previous(TrEngine_trie(engine)) = node;
271 TrEngine_trie(engine) = node;
272 INCREMENT_TRIES(CURRENT_TRIE_ENGINE);
273 return node;
274}
275
276void core_trie_close(TrEngine engine, TrNode node,
277 void (*destruct_function)(TrNode)) {
278 CURRENT_TRIE_ENGINE = engine;
279 DATA_DESTRUCT_FUNCTION = destruct_function;
280 if (TrNode_child(node))
281 remove_child_nodes(TrNode_child(node));
282 if (TrNode_next(node)) {
283 TrNode_previous(TrNode_next(node)) = TrNode_previous(node);
284 TrNode_next(TrNode_previous(node)) = TrNode_next(node);
285 } else
286 TrNode_next(TrNode_previous(node)) = NULL;
287 free_trie_node(node);
288 DECREMENT_TRIES(CURRENT_TRIE_ENGINE);
289 return;
290}
291
292void core_trie_close_all(TrEngine engine, void (*destruct_function)(TrNode)) {
293 while (TrEngine_trie(engine))
294 core_trie_close(engine, TrEngine_trie(engine), destruct_function);
295 return;
296}
297
298void core_trie_set_mode(YAP_Int mode) {
299 CURRENT_TRIE_MODE = mode;
300 return;
301}
302
303YAP_Int core_trie_get_mode(void) { return CURRENT_TRIE_MODE; }
304
305TrNode core_trie_put_entry(TrEngine engine, TrNode node, YAP_Term entry,
306 YAP_Int *depth) {
307 CURRENT_TRIE_ENGINE = engine;
308 CURRENT_DEPTH = 0;
309 stack_args_base = stack_args = AUXILIARY_TERM_STACK;
310 stack_vars_base = stack_vars =
311 AUXILIARY_TERM_STACK + CURRENT_AUXILIARY_TERM_STACK_SIZE - 1;
312 node = put_entry(node, entry);
313 if (!IS_LEAF_TRIE_NODE(node)) {
314 MARK_AS_LEAF_TRIE_NODE(node);
315 INCREMENT_ENTRIES(CURRENT_TRIE_ENGINE);
316 }
317 /* reset var terms */
318 while (STACK_NOT_EMPTY(stack_vars++, stack_vars_base)) {
319 (void)POP_DOWN(stack_vars);
320 *((YAP_Term *)*stack_vars) = *stack_vars;
321 }
322 if (depth)
323 *depth = CURRENT_DEPTH;
324 return node;
325}
326
327TrNode core_trie_check_entry(TrNode node, YAP_Term entry) {
328 if (!TrNode_child(node))
329 return NULL;
330 stack_args_base = stack_args = AUXILIARY_TERM_STACK;
331 stack_vars_base = stack_vars =
332 AUXILIARY_TERM_STACK + CURRENT_AUXILIARY_TERM_STACK_SIZE - 1;
333 node = check_entry(node, entry);
334 /* reset var terms */
335 while (STACK_NOT_EMPTY(stack_vars++, stack_vars_base)) {
336 (void)POP_DOWN(stack_vars);
337 *((YAP_Term *)*stack_vars) = *stack_vars;
338 }
339 return node;
340}
341
342YAP_Term core_trie_get_entry(TrNode node) {
343 CURRENT_INDEX = -1;
344 stack_vars_base = stack_vars = AUXILIARY_TERM_STACK;
345 stack_args_base = stack_args =
346 AUXILIARY_TERM_STACK + CURRENT_AUXILIARY_TERM_STACK_SIZE - 1;
347 return get_entry(node, stack_args, &node);
348}
349
350void core_trie_remove_entry(TrEngine engine, TrNode node,
351 void (*destruct_function)(TrNode)) {
352 CURRENT_TRIE_ENGINE = engine;
353 DATA_DESTRUCT_FUNCTION = destruct_function;
354 if (DATA_DESTRUCT_FUNCTION)
355 (*DATA_DESTRUCT_FUNCTION)(node);
356 DECREMENT_ENTRIES(CURRENT_TRIE_ENGINE);
357 remove_entry(node);
358 return;
359}
360
361void core_trie_remove_subtree(TrEngine engine, TrNode node,
362 void (*destruct_function)(TrNode)) {
363 TrNode parent;
364
365 CURRENT_TRIE_ENGINE = engine;
366 DATA_DESTRUCT_FUNCTION = destruct_function;
367 parent = TrNode_parent(node);
368 remove_child_nodes(TrNode_child(parent));
369 remove_entry(parent);
370 return;
371}
372
373void core_trie_add(TrNode node_dest, TrNode node_source,
374 void (*add_function)(TrNode, TrNode)) {
375 DATA_ADD_FUNCTION = add_function;
376 if (TrNode_child(node_dest) && TrNode_child(node_source))
377 traverse_and_add(node_dest, node_source);
378 return;
379}
380
381void core_trie_join(TrEngine engine, TrNode node_dest, TrNode node_source,
382 void (*add_function)(TrNode, TrNode),
383 void (*copy_function)(TrNode, TrNode)) {
384 CURRENT_TRIE_ENGINE = engine;
385 DATA_ADD_FUNCTION = add_function;
386 DATA_COPY_FUNCTION = copy_function;
387 if (TrNode_child(node_dest)) {
388 if (TrNode_child(node_source))
389 traverse_and_join(node_dest, node_source);
390 } else if (TrNode_child(node_source))
391 TrNode_child(node_dest) =
392 copy_child_nodes(node_dest, TrNode_child(node_source));
393 return;
394}
395
396void core_trie_intersect(TrEngine engine, TrNode node_dest, TrNode node_source,
397 void (*add_function)(TrNode, TrNode),
398 void (*destruct_function)(TrNode)) {
399 CURRENT_TRIE_ENGINE = engine;
400 DATA_ADD_FUNCTION = add_function;
401 DATA_DESTRUCT_FUNCTION = destruct_function;
402 if (TrNode_child(node_dest)) {
403 if (TrNode_child(node_source))
404 traverse_and_intersect(node_dest, node_source);
405 else {
406 remove_child_nodes(TrNode_child(node_dest));
407 TrNode_child(node_dest) = NULL;
408 }
409 }
410 return;
411}
412
413YAP_Int core_trie_count_join(TrNode node1, TrNode node2) {
414 YAP_Int count = 0;
415
416 if (TrNode_child(node1)) {
417 count += traverse_and_count_entries(TrNode_child(node1));
418 if (TrNode_child(node2)) {
419 count += traverse_and_count_entries(TrNode_child(node2));
420 count -= traverse_and_count_common_entries(node1, node2);
421 }
422 } else if (TrNode_child(node2))
423 count += traverse_and_count_entries(TrNode_child(node2));
424 return count;
425}
426
427YAP_Int core_trie_count_intersect(TrNode node1, TrNode node2) {
428 YAP_Int count = 0;
429
430 if (TrNode_child(node1))
431 if (TrNode_child(node2))
432 count = traverse_and_count_common_entries(node1, node2);
433 return count;
434}
435
436void core_trie_save(TrNode node, FILE *file,
437 void (*save_function)(TrNode, FILE *)) {
438 CURRENT_INDEX = -1;
439 DATA_SAVE_FUNCTION = save_function;
440 if (TrNode_child(node)) {
441 fprintf(file, "BEGIN_TRIE_v2 ");
442 traverse_and_save(TrNode_child(node), file, 0);
443 fprintf(file, "END_TRIE_v2");
444 fflush(file);
445 }
446 return;
447}
448
449TrNode core_trie_load(TrEngine engine, FILE *file,
450 void (*load_function)(TrNode, YAP_Int, FILE *)) {
451 TrNode node;
452 char version[15];
453 fpos_t curpos;
454 int n;
455
456 n = fscanf(file, "%14s", version);
457 if (fgetpos(file, &curpos))
458 return NULL;
459
460 if (!strcmp(version, "BEGIN_TRIE_v2")) {
461 fseek(file, -11, SEEK_END);
462 n = fscanf(file, "%s", version);
463 if (strcmp(version, "END_TRIE_v2")) {
464 fprintf(stderr, "******************************************\n");
465 fprintf(stderr, " Tries core module: trie file corrupted\n");
466 fprintf(stderr, "******************************************\n");
467 fflush(stderr);
468 return NULL;
469 }
470 if (fsetpos(file, &curpos))
471 return NULL;
472 CURRENT_LOAD_VERSION = 2;
473 } else if (!strcmp(version, "BEGIN_TRIE")) {
474 fseek(file, -8, SEEK_END);
475 n = fscanf(file, "%s", version);
476 if (strcmp(version, "END_TRIE")) {
477 fprintf(stderr, "******************************************\n");
478 fprintf(stderr, " Tries core module: trie file corrupted\n");
479 fprintf(stderr, "******************************************\n");
480 fflush(stderr);
481 return NULL;
482 }
483 if (fsetpos(file, &curpos))
484 return NULL;
485 CURRENT_LOAD_VERSION = 1;
486 } else {
487 fprintf(stderr, "****************************************\n");
488 fprintf(stderr, " Tries core module: invalid trie file\n");
489 fprintf(stderr, "****************************************\n");
490 fflush(stderr);
491 return NULL;
492 }
493 CURRENT_TRIE_ENGINE = engine;
494 CURRENT_INDEX = -1;
495 CURRENT_DEPTH = 0;
496 DATA_LOAD_FUNCTION = load_function;
497 node = core_trie_open(engine);
498 traverse_and_load(node, file);
499 if (n)
500 n = 0; // just added to remove the warning of not used!
501 return node;
502}
503
504void core_trie_stats(TrEngine engine, YAP_Int *memory, YAP_Int *tries,
505 YAP_Int *entries, YAP_Int *nodes) {
506 *memory = TrEngine_memory(engine);
507 *tries = TrEngine_tries(engine);
508 *entries = TrEngine_entries(engine);
509 *nodes = TrEngine_nodes(engine);
510 return;
511}
512
513void core_trie_max_stats(TrEngine engine, YAP_Int *memory, YAP_Int *tries,
514 YAP_Int *entries, YAP_Int *nodes) {
515 *memory = TrEngine_memory_max(engine);
516 *tries = TrEngine_tries_max(engine);
517 *entries = TrEngine_entries_max(engine);
518 *nodes = TrEngine_nodes_max(engine);
519 return;
520}
521
522void core_trie_usage(TrNode node, YAP_Int *entries, YAP_Int *nodes,
523 YAP_Int *virtual_nodes) {
524 USAGE_ENTRIES = 0;
525 USAGE_NODES = 0;
526 USAGE_VIRTUAL_NODES = 0;
527 if (TrNode_child(node))
528 traverse_and_get_usage(TrNode_child(node), 0);
529 *entries = USAGE_ENTRIES;
530 *nodes = USAGE_NODES;
531 *virtual_nodes = USAGE_VIRTUAL_NODES;
532 return;
533}
534
535void core_trie_print(TrNode node, void (*print_function)(TrNode)) {
536 DATA_PRINT_FUNCTION = print_function;
537 if (TrNode_child(node)) {
538 int arity[1000];
539 char str[10000];
540 arity[0] = 0;
541 traverse_and_print(TrNode_child(node), arity, str, 0, TRIE_PRINT_NORMAL);
542 } else
543 fprintf(stdout, "(empty)\n");
544 fflush(stdout);
545 return;
546}
547
548void core_disable_hash_table(void) { TRIE_DISABLE_HASH_TABLE = 1; }
549
550void core_enable_hash_table(void) { TRIE_DISABLE_HASH_TABLE = 0; }
551
552YAP_Term core_trie_to_list(TrNode node) {
553 TrNode root = TrNode_child(node);
554
555 if (root)
556 return trie_to_list(root);
557 else
558 return YAP_MkAtomTerm(YAP_LookupAtom("empty"));
559}
560
561/* -------------------------- */
562/* Local Procedures */
563/* -------------------------- */
564
565static TrNode put_entry(TrNode node, YAP_Term entry) {
566 YAP_Term t = YAP_Deref(entry);
567 if (YAP_IsVarTerm(t)) {
568 if (IsTrieVar(t, stack_vars, stack_vars_base)) {
569 node = trie_node_check_insert(
570 node, MkTrieVar((stack_vars_base - 1 - (YAP_Term *)t) / 2));
571 } else {
572 node = trie_node_check_insert(
573 node, MkTrieVar((stack_vars_base - stack_vars) / 2));
574 PUSH_UP(stack_vars, t, stack_args);
575 *((YAP_Term *)t) = (YAP_Term)stack_vars;
576 PUSH_UP(stack_vars, stack_vars, stack_args);
577 }
578 } else if (YAP_IsAtomTerm(t)) {
579 node = trie_node_check_insert(node, t);
580 } else if (YAP_IsIntTerm(t)) {
581 node = trie_node_check_insert(node, t);
582 } else if (YAP_IsFloatTerm(t)) {
583 volatile union {
584 double f;
585 YAP_Term p[SIZE_FLOAT_AS_TERM];
586 } tf; /* to avoid gcc warning */
587 tf.f = YAP_FloatOfTerm(t);
588 node = trie_node_check_insert(node, FloatInitTag);
589 node = trie_node_check_insert(node, tf.p[0]);
590#ifdef TAG_LOW_BITS_32
591 node = trie_node_check_insert(node, tf.p[1]);
592#endif /* TAG_LOW_BITS_32 */
593 node = trie_node_check_insert(node, FloatEndTag);
594 } else if (YAP_IsPairTerm(t)) {
595 node = trie_node_check_insert(node, PairInitTag);
596 if ((CURRENT_TRIE_MODE & TRIE_MODE_REVERSE) == TRIE_MODE_STANDARD) {
597 do {
598 node = put_entry(node, YAP_HeadOfTerm(t));
599 t = YAP_Deref(YAP_TailOfTerm(t));
600 } while (YAP_IsPairTerm(t));
601 if (t == YAP_TermNil()) {
602 node = trie_node_check_insert(node, PairEndEmptyTag);
603 } else {
604 node = put_entry(node, t);
605 node = trie_node_check_insert(node, PairEndTermTag);
606 }
607 } else if (CURRENT_TRIE_MODE & TRIE_MODE_REVERSE) { /* TRIE_MODE_REVERSE */
608 YAP_Term *stack_list = stack_args;
609 do {
610 PUSH_DOWN(stack_args, YAP_HeadOfTerm(t), stack_vars);
611 t = YAP_Deref(YAP_TailOfTerm(t));
612 } while (YAP_IsPairTerm(t));
613 if (t == YAP_TermNil()) {
614 while (STACK_NOT_EMPTY(stack_args, stack_list))
615 node = put_entry(node, POP_UP(stack_args));
616 node = trie_node_check_insert(node, PairEndEmptyTag);
617 } else {
618 PUSH_DOWN(stack_args, t, stack_vars);
619 while (STACK_NOT_EMPTY(stack_args, stack_list))
620 node = put_entry(node, POP_UP(stack_args));
621 node = trie_node_check_insert(node, PairEndTermTag);
622 }
623 }
624 } else if (YAP_IsApplTerm(t)) {
625 YAP_Functor f = YAP_FunctorOfTerm(t);
626 if (f == FunctorComma) {
627 node = trie_node_check_insert(node, CommaInitTag);
628 do {
629 node = put_entry(node, YAP_ArgOfTerm(1, t));
630 t = YAP_Deref(YAP_ArgOfTerm(2, t));
631 } while (YAP_IsApplTerm(t) && YAP_FunctorOfTerm(t) == FunctorComma);
632 node = put_entry(node, t);
633 node = trie_node_check_insert(node, CommaEndTag);
634 } else {
635 int i;
636 node = trie_node_check_insert(node, ApplTag | ((YAP_Term)f));
637 for (i = 1; i <= YAP_ArityOfFunctor(f); i++)
638 node = put_entry(node, YAP_ArgOfTerm(i, t));
639 }
640 } else {
641 fprintf(stderr, "***************************************\n");
642 fprintf(stderr, " Tries core module: unknown type tag\n");
643 fprintf(stderr, "***************************************\n");
644 fflush(stderr);
645 }
646
647 return node;
648}
649
650static TrNode check_entry(TrNode node, YAP_Term entry) {
651 YAP_Term t = YAP_Deref(entry);
652 if (YAP_IsVarTerm(t)) {
653 if (IsTrieVar(t, stack_vars, stack_vars_base)) {
654 if (!(node = trie_node_check(
655 node, MkTrieVar((stack_vars_base - 1 - (YAP_Term *)t) / 2))))
656 return NULL;
657 } else {
658 if (!(node = trie_node_check(
659 node, MkTrieVar((stack_vars_base - stack_vars) / 2))))
660 return NULL;
661 PUSH_UP(stack_vars, t, stack_args);
662 *((YAP_Term *)t) = (YAP_Term)stack_vars;
663 PUSH_UP(stack_vars, stack_vars, stack_args);
664 }
665 } else if (YAP_IsAtomTerm(t)) {
666 if (!(node = trie_node_check(node, t)))
667 return NULL;
668 } else if (YAP_IsIntTerm(t)) {
669 if (!(node = trie_node_check(node, t)))
670 return NULL;
671 } else if (YAP_IsFloatTerm(t)) {
672 volatile union {
673 double f;
674 YAP_Term p[SIZE_FLOAT_AS_TERM];
675 } tf; /* to avoid gcc warning */
676 tf.f = YAP_FloatOfTerm(t);
677 if (!(node = trie_node_check(node, FloatInitTag)))
678 return NULL;
679 if (!(node = trie_node_check(node, tf.p[0])))
680 return NULL;
681#ifdef TAG_LOW_BITS_32
682 if (!(node = trie_node_check(node, tf.p[1])))
683 return NULL;
684#endif /* TAG_LOW_BITS_32 */
685 if (!(node = trie_node_check(node, FloatEndTag)))
686 return NULL;
687 } else if (YAP_IsPairTerm(t)) {
688 if (!(node = trie_node_check(node, PairInitTag)))
689 return NULL;
690 if ((CURRENT_TRIE_MODE & TRIE_MODE_REVERSE) == TRIE_MODE_STANDARD) {
691 do {
692 if (!(node = check_entry(node, YAP_HeadOfTerm(t))))
693 return NULL;
694 t = YAP_Deref(YAP_TailOfTerm(t));
695 } while (YAP_IsPairTerm(t));
696 if (t == YAP_TermNil()) {
697 if (!(node = trie_node_check(node, PairEndEmptyTag)))
698 return NULL;
699 } else {
700 if (!(node = check_entry(node, t)))
701 return NULL;
702 if (!(node = trie_node_check(node, PairEndTermTag)))
703 return NULL;
704 }
705 } else if (CURRENT_TRIE_MODE & TRIE_MODE_REVERSE) { /* TRIE_MODE_REVERSE */
706 YAP_Term *stack_list = stack_args;
707 do {
708 PUSH_DOWN(stack_args, YAP_HeadOfTerm(t), stack_vars);
709 t = YAP_Deref(YAP_TailOfTerm(t));
710 } while (YAP_IsPairTerm(t));
711 if (t == YAP_TermNil()) {
712 while (STACK_NOT_EMPTY(stack_args, stack_list))
713 if (!(node = check_entry(node, POP_UP(stack_args))))
714 return NULL;
715 if (!(node = trie_node_check(node, PairEndEmptyTag)))
716 return NULL;
717 } else {
718 PUSH_DOWN(stack_args, t, stack_vars);
719 while (STACK_NOT_EMPTY(stack_args, stack_list))
720 if (!(node = check_entry(node, POP_UP(stack_args))))
721 return NULL;
722 if (!(node = trie_node_check(node, PairEndTermTag)))
723 return NULL;
724 }
725 }
726 } else if (YAP_IsApplTerm(t)) {
727 YAP_Functor f = YAP_FunctorOfTerm(t);
728 if (f == FunctorComma) {
729 if (!(node = trie_node_check(node, CommaInitTag)))
730 return NULL;
731 do {
732 if (!(node = check_entry(node, YAP_ArgOfTerm(1, t))))
733 return NULL;
734 t = YAP_Deref(YAP_ArgOfTerm(2, t));
735 } while (YAP_IsApplTerm(t) && YAP_FunctorOfTerm(t) == FunctorComma);
736 if (!(node = check_entry(node, t)))
737 return NULL;
738 if (!(node = trie_node_check(node, CommaEndTag)))
739 return NULL;
740 } else {
741 int i;
742 if (!(node = trie_node_check(node, ApplTag | ((YAP_Term)f))))
743 return NULL;
744 for (i = 1; i <= YAP_ArityOfFunctor(f); i++)
745 if (!(node = check_entry(node, YAP_ArgOfTerm(i, t))))
746 return NULL;
747 }
748 } else {
749 fprintf(stderr, "***************************************\n");
750 fprintf(stderr, " Tries core module: unknown type tag\n");
751 fprintf(stderr, "***************************************\n");
752 fflush(stderr);
753 }
754
755 return node;
756}
757static int vv;
758static YAP_Term get_entry(TrNode node, YAP_Term *stack_mark, TrNode *cur_node) {
759 vv++; YAP_Term t = (YAP_Term)&t;
760 while (TrNode_parent(node)) {
761 t = TrNode_entry(node);
762 if (YAP_IsVarTerm(t)) {
763 int index = TrieVarIndex(t);
764 if (index > CURRENT_INDEX) {
765 int i;
766 stack_vars = &stack_vars_base[index + 1];
767 if (stack_vars > stack_args + 1) {
768 fprintf(stderr, "**************************************\n");
769 fprintf(stderr, " Tries core module: term stack full\n");
770 fprintf(stderr, "**************************************\n");
771 fflush(stderr);
772 }
773 for (i = index; i > CURRENT_INDEX; i--)
774 stack_vars_base[i] = 0;
775 CURRENT_INDEX = index;
776 }
777 if (stack_vars_base[index]) {
778 t = stack_vars_base[index];
779 } else {
780 t = YAP_MkVarTerm();
781 stack_vars_base[index] = t;
782 }
783 PUSH_UP(stack_args, t, stack_vars);
784 } else if (YAP_IsAtomTerm(t)) {
785 PUSH_UP(stack_args, t, stack_vars);
786 } else if (YAP_IsIntTerm(t)) {
787 PUSH_UP(stack_args, t, stack_vars);
788 } else if (YAP_IsPairTerm(t)) {
789 if (t == PairInitTag) {
790 YAP_Term t2;
791 if ((CURRENT_TRIE_MODE & TRIE_MODE_REVERSE) == TRIE_MODE_STANDARD) {
792 YAP_Term *stack_aux = stack_mark;
793 t = *stack_aux--;
794 while (STACK_NOT_EMPTY(stack_aux, stack_args)) {
795 t2 = *stack_aux--;
796 t = YAP_MkPairTerm(t2, t);
797 }
798 } else if (CURRENT_TRIE_MODE &
799 TRIE_MODE_REVERSE) { /* TRIE_MODE_REVERSE */
800 YAP_Term *stack_aux = stack_mark;
801 t = *stack_aux;
802 if (t == YAP_TermNil())
803 stack_aux--;
804 else
805 t = POP_DOWN(stack_args);
806 while (STACK_NOT_EMPTY(stack_args, stack_aux)) {
807 t2 = POP_DOWN(stack_args);
808 t = YAP_MkPairTerm(t2, t);
809 }
810 }
811 stack_args = stack_mark;
812 *cur_node = node;
813 return t;
814 } else if (t == PairEndEmptyTag) {
815 t = YAP_TermNil();
816 PUSH_UP(stack_args, t, stack_vars);
817 node = TrNode_parent(node);
818 t = get_entry(node, &stack_args[1], &node);
819 PUSH_UP(stack_args, t, stack_vars);
820 } else if (t == PairEndTermTag) {
821 node = TrNode_parent(node);
822 t = get_entry(node, stack_args, &node);
823 PUSH_UP(stack_args, t, stack_vars);
824 } else if (t == CommaEndTag) {
825 node = TrNode_parent(node);
826 t = get_entry(node, stack_args, &node);
827 PUSH_UP(stack_args, t, stack_vars);
828 } else if (t == CommaInitTag) {
829 YAP_Term *stack_aux = stack_mark;
830 stack_aux--;
831 while (STACK_NOT_EMPTY(stack_aux, stack_args)) {
832 t = YAP_MkApplTerm(FunctorComma, 2, stack_aux);
833 *stack_aux = t;
834 stack_aux--;
835 }
836 stack_args = stack_mark;
837 *cur_node = node;
838 return t;
839 } else if (t == FloatEndTag) {
840 volatile union {
841 double f;
842 YAP_Term p[SIZE_FLOAT_AS_TERM];
843 } tf; /* to avoid gcc warning */
844#ifdef TAG_LOW_BITS_32
845 node = TrNode_parent(node);
846 tf.p[1] = TrNode_entry(node);
847#endif /* TAG_LOW_BITS_32 */
848 node = TrNode_parent(node);
849 tf.p[0] = TrNode_entry(node);
850 node = TrNode_parent(node); /* ignore FloatInitTag */
851 t = YAP_MkFloatTerm(tf.f);
852 PUSH_UP(stack_args, t, stack_vars);
853 } else if (t == FloatInitTag) {
854 }
855 } else if (ApplTag & t) {
856 YAP_Functor f = (YAP_Functor)(~ApplTag & t);
857 int arity = YAP_ArityOfFunctor(f);
858 t = YAP_MkApplTerm(f, arity, &stack_args[1]);
859 stack_args += arity;
860 PUSH_UP(stack_args, t, stack_vars);
861 } else {
862 fprintf(stderr, "***************************************\n");
863 fprintf(stderr, " Tries core module: unknown type tag\n");
864 fprintf(stderr, "***************************************\n");
865 fflush(stderr);
866 }
867 node = TrNode_parent(node);
868 }
869 *cur_node = node;
870 return t;
871}
872
873static void remove_entry(TrNode node) {
874 TrNode parent = TrNode_parent(node);
875 while (parent) {
876 if (TrNode_previous(node)) {
877 if (IS_HASH_NODE(TrNode_child(parent))) {
878 TrHash hash = (TrHash)TrNode_child(parent);
879 TrHash_num_nodes(hash)--;
880 if (TrHash_num_nodes(hash)) {
881 if (TrNode_next(node)) {
882 TrNode_next(TrNode_previous(node)) = TrNode_next(node);
883 TrNode_previous(TrNode_next(node)) = TrNode_previous(node);
884 } else {
885 TrNode_next(TrNode_previous(node)) = NULL;
886 }
887 free_trie_node(node);
888 return;
889 }
890 free_hash_buckets(TrHash_buckets(hash), TrHash_num_buckets(hash));
891 free_trie_hash(hash);
892 } else {
893 if (TrNode_next(node)) {
894 TrNode_next(TrNode_previous(node)) = TrNode_next(node);
895 TrNode_previous(TrNode_next(node)) = TrNode_previous(node);
896 } else {
897 TrNode_next(TrNode_previous(node)) = NULL;
898 }
899 free_trie_node(node);
900 return;
901 }
902 } else if (TrNode_next(node)) {
903 TrNode_child(parent) = TrNode_next(node);
904 TrNode_previous(TrNode_next(node)) = NULL;
905 free_trie_node(node);
906 return;
907 }
908 free_trie_node(node);
909 node = parent;
910 parent = TrNode_parent(node);
911 }
912 TrNode_child(node) = NULL;
913 return;
914}
915
916static void remove_child_nodes(TrNode node) {
917 if (IS_HASH_NODE(node)) {
918 TrNode *first_bucket, *bucket;
919 TrHash hash = (TrHash)node;
920 first_bucket = TrHash_buckets(hash);
921 bucket = first_bucket + TrHash_num_buckets(hash);
922 do {
923 if (*--bucket)
924 remove_child_nodes(*bucket);
925 } while (bucket != first_bucket);
926 free_hash_buckets(first_bucket, TrHash_num_buckets(hash));
927 free_trie_hash(hash);
928 return;
929 }
930 if (TrNode_next(node))
931 remove_child_nodes(TrNode_next(node));
932 if (!IS_LEAF_TRIE_NODE(node)) {
933 remove_child_nodes(TrNode_child(node));
934 } else {
935 if (DATA_DESTRUCT_FUNCTION)
936 (*DATA_DESTRUCT_FUNCTION)(node);
937 DECREMENT_ENTRIES(CURRENT_TRIE_ENGINE);
938 }
939 free_trie_node(node);
940 return;
941}
942
943static TrNode copy_child_nodes(TrNode parent_dest, TrNode child_source) {
944 TrNode child_dest, next_dest;
945
946 if (IS_HASH_NODE(child_source)) {
947 TrNode *bucket_dest, *first_bucket_source, *bucket_source;
948 TrHash hash_dest, hash_source;
949 hash_source = (TrHash)child_source;
950 first_bucket_source = TrHash_buckets(hash_source);
951 bucket_source = first_bucket_source + TrHash_num_buckets(hash_source);
952 new_trie_hash(hash_dest, TrHash_num_nodes(hash_source),
953 TrHash_num_buckets(hash_source));
954 bucket_dest = TrHash_buckets(hash_dest) + TrHash_num_buckets(hash_dest);
955 do {
956 bucket_dest--;
957 if (*--bucket_source) {
958 *bucket_dest = copy_child_nodes(parent_dest, *bucket_source);
959 TrNode_previous(*bucket_dest) = AS_TR_NODE_NEXT(bucket_dest);
960 } else
961 *bucket_dest = NULL;
962 } while (bucket_source != first_bucket_source);
963 return (TrNode)hash_dest;
964 }
965
966 if (TrNode_next(child_source))
967 next_dest = copy_child_nodes(parent_dest, TrNode_next(child_source));
968 else
969 next_dest = NULL;
970 new_trie_node(child_dest, TrNode_entry(child_source), parent_dest, NULL,
971 next_dest, NULL);
972 if (next_dest)
973 TrNode_previous(next_dest) = child_dest;
974 if (IS_LEAF_TRIE_NODE(child_source)) {
975 MARK_AS_LEAF_TRIE_NODE(child_dest);
976 INCREMENT_ENTRIES(CURRENT_TRIE_ENGINE);
977 if (DATA_COPY_FUNCTION)
978 (*DATA_COPY_FUNCTION)(child_dest, child_source);
979 } else
980 TrNode_child(child_dest) =
981 copy_child_nodes(child_dest, TrNode_child(child_source));
982 return child_dest;
983}
984
985static void traverse_and_add(TrNode parent_dest, TrNode parent_source) {
986 TrNode child_dest, child_source;
987
988 /* parent_source is not a leaf node */
989 child_source = TrNode_child(parent_source);
990 if (IS_HASH_NODE(child_source)) {
991 TrNode *first_bucket_source, *bucket_source;
992 TrHash hash_source;
993 hash_source = (TrHash)child_source;
994 first_bucket_source = TrHash_buckets(hash_source);
995 bucket_source = first_bucket_source + TrHash_num_buckets(hash_source);
996 do {
997 child_source = *--bucket_source;
998 while (child_source) {
999 /* parent_dest is not a leaf node */
1000 child_dest = trie_node_check(parent_dest, TrNode_entry(child_source));
1001 if (child_dest) {
1002 if (IS_LEAF_TRIE_NODE(child_dest)) {
1003 /* child_source is a leaf node */
1004 if (DATA_ADD_FUNCTION)
1005 (*DATA_ADD_FUNCTION)(child_dest, child_source);
1006 } else
1007 /* child_dest and child_source are not leaf nodes */
1008 traverse_and_add(child_dest, child_source);
1009 }
1010 child_source = TrNode_next(child_source);
1011 }
1012 } while (bucket_source != first_bucket_source);
1013 return;
1014 }
1015 while (child_source) {
1016 /* parent_dest is not a leaf node */
1017 child_dest = trie_node_check(parent_dest, TrNode_entry(child_source));
1018 if (child_dest) {
1019 if (IS_LEAF_TRIE_NODE(child_dest)) {
1020 /* child_source is a leaf node */
1021 if (DATA_ADD_FUNCTION)
1022 (*DATA_ADD_FUNCTION)(child_dest, child_source);
1023 } else
1024 /* child_dest and child_source are not leaf nodes */
1025 traverse_and_add(child_dest, child_source);
1026 }
1027 child_source = TrNode_next(child_source);
1028 }
1029 return;
1030}
1031
1032static void traverse_and_join(TrNode parent_dest, TrNode parent_source) {
1033 TrNode child_dest, child_source;
1034
1035 /* parent_source is not a leaf node */
1036 child_source = TrNode_child(parent_source);
1037 if (IS_HASH_NODE(child_source)) {
1038 TrNode *first_bucket_source, *bucket_source;
1039 TrHash hash_source;
1040 hash_source = (TrHash)child_source;
1041 first_bucket_source = TrHash_buckets(hash_source);
1042 bucket_source = first_bucket_source + TrHash_num_buckets(hash_source);
1043 do {
1044 child_source = *--bucket_source;
1045 while (child_source) {
1046 /* parent_dest is not a leaf node */
1047 child_dest = trie_node_check(parent_dest, TrNode_entry(child_source));
1048 if (child_dest) {
1049 if (IS_LEAF_TRIE_NODE(child_dest)) {
1050 /* child_source is a leaf node */
1051 if (DATA_ADD_FUNCTION)
1052 (*DATA_ADD_FUNCTION)(child_dest, child_source);
1053 } else
1054 /* child_dest and child_source are not leaf nodes */
1055 traverse_and_join(child_dest, child_source);
1056 } else {
1057 child_dest =
1058 trie_node_check_insert(parent_dest, TrNode_entry(child_source));
1059 if (IS_LEAF_TRIE_NODE(child_source)) {
1060 MARK_AS_LEAF_TRIE_NODE(child_dest);
1061 INCREMENT_ENTRIES(CURRENT_TRIE_ENGINE);
1062 if (DATA_COPY_FUNCTION)
1063 (*DATA_COPY_FUNCTION)(child_dest, child_source);
1064 } else
1065 TrNode_child(child_dest) =
1066 copy_child_nodes(child_dest, TrNode_child(child_source));
1067 }
1068 child_source = TrNode_next(child_source);
1069 }
1070 } while (bucket_source != first_bucket_source);
1071 return;
1072 }
1073 while (child_source) {
1074 /* parent_dest is not a leaf node */
1075 child_dest = trie_node_check(parent_dest, TrNode_entry(child_source));
1076 if (child_dest) {
1077 if (IS_LEAF_TRIE_NODE(child_dest)) {
1078 /* child_source is a leaf node */
1079 if (DATA_ADD_FUNCTION)
1080 (*DATA_ADD_FUNCTION)(child_dest, child_source);
1081 } else
1082 /* child_dest and child_source are not leaf nodes */
1083 traverse_and_join(child_dest, child_source);
1084 } else {
1085 child_dest =
1086 trie_node_check_insert(parent_dest, TrNode_entry(child_source));
1087 if (IS_LEAF_TRIE_NODE(child_source)) {
1088 MARK_AS_LEAF_TRIE_NODE(child_dest);
1089 INCREMENT_ENTRIES(CURRENT_TRIE_ENGINE);
1090 if (DATA_COPY_FUNCTION)
1091 (*DATA_COPY_FUNCTION)(child_dest, child_source);
1092 } else
1093 TrNode_child(child_dest) =
1094 copy_child_nodes(child_dest, TrNode_child(child_source));
1095 }
1096 child_source = TrNode_next(child_source);
1097 }
1098 return;
1099}
1100
1101static void traverse_and_intersect(TrNode parent_dest, TrNode parent_source) {
1102 TrNode child_dest, child_source, child_next;
1103
1104 /* parent_dest is not a leaf node */
1105 child_dest = TrNode_child(parent_dest);
1106 if (IS_HASH_NODE(child_dest)) {
1107 TrNode *first_bucket_dest, *bucket_dest;
1108 TrHash hash_dest;
1109 hash_dest = (TrHash)child_dest;
1110 first_bucket_dest = TrHash_buckets(hash_dest);
1111 bucket_dest = first_bucket_dest + TrHash_num_buckets(hash_dest);
1112 do {
1113 child_dest = *--bucket_dest;
1114 while (child_dest) {
1115 child_next = TrNode_next(child_dest);
1116 /* parent_source is not a leaf node */
1117 child_source = trie_node_check(parent_source, TrNode_entry(child_dest));
1118 if (child_source) {
1119 if (IS_LEAF_TRIE_NODE(child_dest)) {
1120 /* child_source is a leaf node */
1121 if (DATA_ADD_FUNCTION)
1122 (*DATA_ADD_FUNCTION)(child_dest, child_source);
1123 } else
1124 /* child_dest and child_source are not leaf nodes */
1125 traverse_and_intersect(child_dest, child_source);
1126 } else {
1127 if (IS_LEAF_TRIE_NODE(child_dest)) {
1128 if (DATA_DESTRUCT_FUNCTION)
1129 (*DATA_DESTRUCT_FUNCTION)(child_dest);
1130 DECREMENT_ENTRIES(CURRENT_TRIE_ENGINE);
1131 } else
1132 remove_child_nodes(TrNode_child(child_dest));
1133 remove_entry(child_dest);
1134 }
1135 child_dest = child_next;
1136 }
1137 } while (bucket_dest != first_bucket_dest);
1138 return;
1139 }
1140 while (child_dest) {
1141 child_next = TrNode_next(child_dest);
1142 /* parent_source is not a leaf node */
1143 child_source = trie_node_check(parent_source, TrNode_entry(child_dest));
1144 if (child_source) {
1145 if (IS_LEAF_TRIE_NODE(child_dest)) {
1146 /* child_source is a leaf node */
1147 if (DATA_ADD_FUNCTION)
1148 (*DATA_ADD_FUNCTION)(child_dest, child_source);
1149 } else
1150 /* child_dest and child_source are not leaf nodes */
1151 traverse_and_intersect(child_dest, child_source);
1152 } else {
1153 if (IS_LEAF_TRIE_NODE(child_dest)) {
1154 if (DATA_DESTRUCT_FUNCTION)
1155 (*DATA_DESTRUCT_FUNCTION)(child_dest);
1156 DECREMENT_ENTRIES(CURRENT_TRIE_ENGINE);
1157 } else
1158 remove_child_nodes(TrNode_child(child_dest));
1159 remove_entry(child_dest);
1160 }
1161 child_dest = child_next;
1162 }
1163 return;
1164}
1165
1166static YAP_Int traverse_and_count_common_entries(TrNode parent1,
1167 TrNode parent2) {
1168 TrNode child1, child2;
1169 YAP_Int count = 0;
1170
1171 /* parent1 is not a leaf node */
1172 child1 = TrNode_child(parent1);
1173 if (IS_HASH_NODE(child1)) {
1174 TrNode *first_bucket, *bucket;
1175 TrHash hash;
1176 hash = (TrHash)child1;
1177 first_bucket = TrHash_buckets(hash);
1178 bucket = first_bucket + TrHash_num_buckets(hash);
1179 do {
1180 child1 = *--bucket;
1181 while (child1) {
1182 /* parent2 is not a leaf node */
1183 child2 = trie_node_check(parent2, TrNode_entry(child1));
1184 if (child2) {
1185 if (IS_LEAF_TRIE_NODE(child1))
1186 /* child2 is a leaf node */
1187 count++;
1188 else
1189 /* child1 and child2 are not leaf nodes */
1190 count += traverse_and_count_common_entries(child1, child2);
1191 }
1192 child1 = TrNode_next(child1);
1193 }
1194 } while (bucket != first_bucket);
1195 return count;
1196 }
1197 while (child1) {
1198 /* parent2 is not a leaf node */
1199 child2 = trie_node_check(parent2, TrNode_entry(child1));
1200 if (child2) {
1201 if (IS_LEAF_TRIE_NODE(child1))
1202 /* child2 is a leaf node */
1203 count++;
1204 else
1205 /* child1 and child2 are not leaf nodes */
1206 count += traverse_and_count_common_entries(child1, child2);
1207 }
1208 child1 = TrNode_next(child1);
1209 }
1210 return count;
1211}
1212
1213static YAP_Int traverse_and_count_entries(TrNode node) {
1214 YAP_Int count = 0;
1215
1216 if (IS_HASH_NODE(node)) {
1217 TrNode *first_bucket, *bucket;
1218 TrHash hash;
1219 hash = (TrHash)node;
1220 first_bucket = TrHash_buckets(hash);
1221 bucket = first_bucket + TrHash_num_buckets(hash);
1222 do {
1223 if (*--bucket) {
1224 node = *bucket;
1225 count += traverse_and_count_entries(node);
1226 }
1227 } while (bucket != first_bucket);
1228 return count;
1229 }
1230
1231 if (TrNode_next(node))
1232 count += traverse_and_count_entries(TrNode_next(node));
1233 if (!IS_LEAF_TRIE_NODE(node))
1234 count += traverse_and_count_entries(TrNode_child(node));
1235 else
1236 count++;
1237 return count;
1238}
1239
1240static void traverse_and_get_usage(TrNode node, YAP_Int depth) {
1241 if (IS_HASH_NODE(node)) {
1242 TrNode *first_bucket, *bucket;
1243 TrHash hash;
1244 hash = (TrHash)node;
1245 first_bucket = TrHash_buckets(hash);
1246 bucket = first_bucket + TrHash_num_buckets(hash);
1247 do {
1248 if (*--bucket) {
1249 node = *bucket;
1250 traverse_and_get_usage(node, depth);
1251 }
1252 } while (bucket != first_bucket);
1253 return;
1254 }
1255
1256 USAGE_NODES++;
1257 if (TrNode_next(node))
1258 traverse_and_get_usage(TrNode_next(node), depth);
1259 depth++;
1260 if (!IS_LEAF_TRIE_NODE(node)) {
1261 traverse_and_get_usage(TrNode_child(node), depth);
1262 } else {
1263 USAGE_ENTRIES++;
1264 USAGE_VIRTUAL_NODES += depth;
1265 }
1266 return;
1267}
1268
1269static void traverse_and_save(TrNode node, FILE *file, int float_block) {
1270 YAP_Term t;
1271
1272 if (IS_HASH_NODE(node)) {
1273 TrNode *first_bucket, *bucket;
1274 TrHash hash;
1275 hash = (TrHash)node;
1276 fprintf(file, UInt_FORMAT " %d ", HASH_SAVE_MARK, TrHash_num_buckets(hash));
1277 first_bucket = TrHash_buckets(hash);
1278 bucket = first_bucket + TrHash_num_buckets(hash);
1279 do {
1280 if (*--bucket) {
1281 node = *bucket;
1282 traverse_and_save(node, file, float_block);
1283 }
1284 } while (bucket != first_bucket);
1285 return;
1286 }
1287
1288 if (TrNode_next(node))
1289 traverse_and_save(TrNode_next(node), file, float_block);
1290
1291 t = TrNode_entry(node);
1292 if (float_block) {
1293 float_block--;
1294 fprintf(file, UInt_FORMAT " " UInt_FORMAT " ", FLOAT_SAVE_MARK, t);
1295 } else if (YAP_IsPairTerm(t)) {
1296 if (t == FloatInitTag) {
1297#ifdef TAG_LOW_BITS_32
1298 float_block++;
1299#endif /* TAG_LOW_BITS_32 */
1300 float_block++;
1301 }
1302 fprintf(file, UInt_FORMAT " ", t);
1303 } else if (YAP_IsVarTerm(t) || YAP_IsIntTerm(t))
1304 fprintf(file, UInt_FORMAT " ", t);
1305 else {
1306 int index;
1307 for (index = 0; index <= CURRENT_INDEX; index++)
1308 if (AUXILIARY_TERM_STACK[index] == t)
1309 break;
1310 if (index > CURRENT_INDEX) {
1311 CURRENT_INDEX = index;
1312 if (CURRENT_INDEX == CURRENT_AUXILIARY_TERM_STACK_SIZE)
1313 expand_auxiliary_term_stack();
1314 AUXILIARY_TERM_STACK[CURRENT_INDEX] = t;
1315 if (YAP_IsAtomTerm(t))
1316 fprintf(file, UInt_FORMAT " %d %s%c ", ATOM_SAVE_MARK, index,
1317 YAP_AtomName(YAP_AtomOfTerm(t)), '\0');
1318 else /* (ApplTag & t) */
1319 fprintf(file, UInt_FORMAT " %d %s " UInt_FORMAT " ", FUNCTOR_SAVE_MARK,
1320 index,
1321 YAP_AtomName(YAP_NameOfFunctor((YAP_Functor)(~ApplTag & t))),
1322 YAP_ArityOfFunctor((YAP_Functor)(~ApplTag & t)));
1323 } else if (YAP_IsAtomTerm(t))
1324 fprintf(file, UInt_FORMAT " %d ", ATOM_SAVE_MARK, index);
1325 else
1326 fprintf(file, UInt_FORMAT " %d ", FUNCTOR_SAVE_MARK, index);
1327 }
1328 if (IS_LEAF_TRIE_NODE(node)) {
1329 fprintf(file, "- ");
1330 if (DATA_SAVE_FUNCTION)
1331 (*DATA_SAVE_FUNCTION)(node, file);
1332 } else {
1333 traverse_and_save(TrNode_child(node), file, float_block);
1334 fprintf(file, "- ");
1335 }
1336 return;
1337}
1338
1339static void traverse_and_load(TrNode parent, FILE *file) {
1340 TrHash hash = NULL;
1341 YAP_Term t;
1342 int n;
1343
1344 if (!fscanf(file, UInt_FORMAT, &t)) {
1345 MARK_AS_LEAF_TRIE_NODE(parent);
1346 INCREMENT_ENTRIES(CURRENT_TRIE_ENGINE);
1347 if (DATA_LOAD_FUNCTION)
1348 (*DATA_LOAD_FUNCTION)(parent, CURRENT_DEPTH, file);
1349 CURRENT_DEPTH--;
1350 return;
1351 }
1352 if (t == HASH_SAVE_MARK) {
1353 /* alloc a new trie hash */
1354 int num_buckets;
1355 n = fscanf(file, "%d", &num_buckets);
1356 new_trie_hash(hash, 0, num_buckets);
1357 TrNode_child(parent) = (TrNode)hash;
1358 n = fscanf(file, UInt_FORMAT, &t);
1359 }
1360 do {
1361 TrNode child;
1362 if (t == ATOM_SAVE_MARK) {
1363 int index;
1364 n = fscanf(file, "%d", &index);
1365 if (index > CURRENT_INDEX) {
1366 char atom[1000];
1367 if (CURRENT_LOAD_VERSION == 2) {
1368 char *ptr, ch;
1369 ptr = atom;
1370 fgetc(file); /* skip the first empty space */
1371 while ((ch = fgetc(file)))
1372 *ptr++ = ch;
1373 *ptr = '\0';
1374 } else if (CURRENT_LOAD_VERSION == 1) {
1375 n = fscanf(file, "%s", atom);
1376 }
1377 CURRENT_INDEX = index;
1378 if (CURRENT_INDEX == CURRENT_AUXILIARY_TERM_STACK_SIZE)
1379 expand_auxiliary_term_stack();
1380 AUXILIARY_TERM_STACK[CURRENT_INDEX] =
1381 YAP_MkAtomTerm(YAP_LookupAtom(atom));
1382 }
1383 t = AUXILIARY_TERM_STACK[index];
1384 } else if (t == FUNCTOR_SAVE_MARK) {
1385 int index;
1386 n = fscanf(file, "%d", &index);
1387 if (index > CURRENT_INDEX) {
1388 char atom[1000];
1389 int arity;
1390 n = fscanf(file, "%s %d", atom, &arity);
1391 CURRENT_INDEX = index;
1392 if (CURRENT_INDEX == CURRENT_AUXILIARY_TERM_STACK_SIZE)
1393 expand_auxiliary_term_stack();
1394 AUXILIARY_TERM_STACK[CURRENT_INDEX] =
1395 ApplTag | ((YAP_Term)YAP_MkFunctor(YAP_LookupAtom(atom), arity));
1396 }
1397 t = AUXILIARY_TERM_STACK[index];
1398 } else if (t == FLOAT_SAVE_MARK)
1399 n = fscanf(file, UInt_FORMAT, &t);
1400 child = trie_node_insert(parent, t, hash);
1401 traverse_and_load(child, file);
1402 } while (fscanf(file, UInt_FORMAT, &t));
1403 CURRENT_DEPTH--;
1404 if (n)
1405 n = 0; // just added to remove the warning of not used!
1406 return;
1407}
1408
1409static void traverse_and_print(TrNode node, int *arity, char *str,
1410 int str_index, int mode) {
1411 YAP_Term t;
1412 int last_pair_mark = -arity[arity[0]];
1413
1414 if (IS_HASH_NODE(node)) {
1415 int *current_arity = (int *)malloc(sizeof(int) * (arity[0] + 1));
1416 TrNode *first_bucket, *bucket;
1417 TrHash hash;
1418 hash = (TrHash)node;
1419 first_bucket = TrHash_buckets(hash);
1420 bucket = first_bucket + TrHash_num_buckets(hash);
1421 memmove(current_arity, arity, sizeof(int) * (arity[0] + 1));
1422 do {
1423 if (*--bucket) {
1424 node = *bucket;
1425 traverse_and_print(node, arity, str, str_index, mode);
1426 memmove(arity, current_arity, sizeof(int) * (current_arity[0] + 1));
1427 if (mode != TRIE_PRINT_FLOAT2 && arity[arity[0]] < 0) {
1428 /* restore possible PairEndEmptyTag/PairEndTermTag/CommaEndTag
1429 * side-effect */
1430 if (str_index > 0 && str[str_index - 1] != '[')
1431 str[str_index - 1] = ',';
1432 /* restore possible PairEndTermTag side-effect */
1433 if (str[last_pair_mark] == '|')
1434 str[last_pair_mark] = ',';
1435 }
1436 }
1437 } while (bucket != first_bucket);
1438 free(current_arity);
1439 return;
1440 }
1441
1442 if (TrNode_next(node)) {
1443 int *current_arity = (int *)malloc(sizeof(int) * (arity[0] + 1));
1444 memmove(current_arity, arity, sizeof(int) * (arity[0] + 1));
1445 traverse_and_print(TrNode_next(node), arity, str, str_index, mode);
1446 memmove(arity, current_arity, sizeof(int) * (current_arity[0] + 1));
1447 if (mode != TRIE_PRINT_FLOAT2 && arity[arity[0]] < 0) {
1448 /* restore possible PairEndEmptyTag/PairEndTermTag/CommaEndTag side-effect
1449 */
1450 if (str_index > 0 && str[str_index - 1] != '[')
1451 str[str_index - 1] = ',';
1452 /* restore possible PairEndTermTag side-effect */
1453 if (str[last_pair_mark] == '|')
1454 str[last_pair_mark] = ',';
1455 }
1456 free(current_arity);
1457 }
1458
1459 /* update position for possible PairEndTermTag side-effect */
1460 if (mode != TRIE_PRINT_FLOAT2 && arity[arity[0]] < 0 && str_index > 1)
1461 arity[arity[0]] = -str_index + 1;
1462
1463 t = TrNode_entry(node);
1464 if (mode == TRIE_PRINT_FLOAT) {
1465#ifdef TAG_LOW_BITS_32
1466 arity[arity[0]] = (YAP_Int)t;
1467 mode = TRIE_PRINT_FLOAT2;
1468 } else if (mode == TRIE_PRINT_FLOAT2) {
1469 volatile union {
1470 double f;
1471 YAP_Term p[SIZE_FLOAT_AS_TERM];
1472 } tf; /* to avoid gcc warning */
1473 tf.p[1] = t;
1474 tf.p[0] = (YAP_Term)arity[arity[0]];
1475 arity[arity[0]] = -1;
1476#else /* TAG_64BITS */
1477 volatile union {
1478 double f;
1479 YAP_Term p[SIZE_FLOAT_AS_TERM];
1480 } tf; /* to avoid gcc warning */
1481 tf.p[0] = t;
1482#endif /* TAG_SCHEME */
1483 str_index += sprintf(&str[str_index], "%.15g", tf.f);
1484 mode = TRIE_PRINT_FLOAT_END;
1485 } else if (mode == TRIE_PRINT_FLOAT_END) {
1486 arity[0]--;
1487 while (arity[0]) {
1488 if (arity[arity[0]] == 1) {
1489 str_index += sprintf(&str[str_index], ")");
1490 arity[0]--;
1491 } else {
1492 if (arity[arity[0]] > 1)
1493 arity[arity[0]]--;
1494 str_index += sprintf(&str[str_index], ",");
1495 break;
1496 }
1497 }
1498 mode = TRIE_PRINT_NORMAL;
1499 } else if (YAP_IsVarTerm(t)) {
1500 str_index += sprintf(&str[str_index], "VAR" UInt_FORMAT, TrieVarIndex(t));
1501 while (arity[0]) {
1502 if (arity[arity[0]] == 1) {
1503 str_index += sprintf(&str[str_index], ")");
1504 arity[0]--;
1505 } else {
1506 if (arity[arity[0]] > 1)
1507 arity[arity[0]]--;
1508 str_index += sprintf(&str[str_index], ",");
1509 break;
1510 }
1511 }
1512 } else if (YAP_IsAtomTerm(t)) {
1513 str_index +=
1514 sprintf(&str[str_index], "%s", YAP_AtomName(YAP_AtomOfTerm(t)));
1515 while (arity[0]) {
1516 if (arity[arity[0]] == 1) {
1517 str_index += sprintf(&str[str_index], ")");
1518 arity[0]--;
1519 } else {
1520 if (arity[arity[0]] > 1)
1521 arity[arity[0]]--;
1522 str_index += sprintf(&str[str_index], ",");
1523 break;
1524 }
1525 }
1526 } else if (YAP_IsIntTerm(t)) {
1527 str_index += sprintf(&str[str_index], UInt_FORMAT, YAP_IntOfTerm(t));
1528 while (arity[0]) {
1529 if (arity[arity[0]] == 1) {
1530 str_index += sprintf(&str[str_index], ")");
1531 arity[0]--;
1532 } else {
1533 if (arity[arity[0]] > 1)
1534 arity[arity[0]]--;
1535 str_index += sprintf(&str[str_index], ",");
1536 break;
1537 }
1538 }
1539 } else if (YAP_IsPairTerm(t)) {
1540 if (t == FloatInitTag) {
1541 mode = TRIE_PRINT_FLOAT;
1542 arity[0]++;
1543 arity[arity[0]] = -1;
1544 } else if (t == PairInitTag) {
1545 str_index += sprintf(&str[str_index], "[");
1546 arity[0]++;
1547 arity[arity[0]] = -1;
1548 } else if (t == CommaInitTag) {
1549 str_index += sprintf(&str[str_index], "(");
1550 arity[0]++;
1551 arity[arity[0]] = -1;
1552 } else {
1553 if (t == PairEndEmptyTag)
1554 str[str_index - 1] = ']';
1555 else if (t == PairEndTermTag) {
1556 str[last_pair_mark] = '|';
1557 str[str_index - 1] = ']';
1558 } else /* (t == CommaEndTag) */
1559 str[str_index - 1] = ')';
1560 arity[0]--;
1561 while (arity[0]) {
1562 if (arity[arity[0]] == 1) {
1563 str_index += sprintf(&str[str_index], ")");
1564 arity[0]--;
1565 } else {
1566 if (arity[arity[0]] > 1)
1567 arity[arity[0]]--;
1568 str_index += sprintf(&str[str_index], ",");
1569 break;
1570 }
1571 }
1572 }
1573 } else if (ApplTag & t) {
1574 str_index +=
1575 sprintf(&str[str_index], "%s(",
1576 YAP_AtomName(YAP_NameOfFunctor((YAP_Functor)(~ApplTag & t))));
1577 arity[0]++;
1578 arity[arity[0]] = YAP_ArityOfFunctor((YAP_Functor)(~ApplTag & t));
1579 } else {
1580 fprintf(stderr, "***************************************\n");
1581 fprintf(stderr, " Tries core module: unknown type tag\n");
1582 fprintf(stderr, "***************************************\n");
1583 fflush(stderr);
1584 }
1585
1586 if (arity[0]) {
1587 traverse_and_print(TrNode_child(node), arity, str, str_index, mode);
1588 } else {
1589 str[str_index] = 0;
1590 fprintf(stdout, "%s\n", str);
1591 if (DATA_PRINT_FUNCTION)
1592 (*DATA_PRINT_FUNCTION)(node);
1593 }
1594 return;
1595}
1596
1597static YAP_Term trie_to_list(TrNode node) {
1598 YAP_Term tail = YAP_MkAtomTerm(YAP_LookupAtom("[]"));
1599
1600#define CONSUME_NODE_LIST \
1601 do { \
1602 /* add node result to list */ \
1603 tail = YAP_MkPairTerm(trie_to_list_node(node), tail); \
1604 } while ((node = TrNode_next(node)));
1605
1606 if (IS_HASH_NODE(node)) {
1607 TrNode *first_bucket, *bucket;
1608 TrHash hash = (TrHash)node;
1609
1610 first_bucket = TrHash_buckets(hash);
1611 bucket = first_bucket + TrHash_num_buckets(hash);
1612
1613 /* iterate through valid hash positions and consume each list */
1614 do {
1615 if (*--bucket) {
1616 node = *bucket;
1617 CONSUME_NODE_LIST;
1618 }
1619 } while (bucket != first_bucket);
1620 } else {
1621 CONSUME_NODE_LIST;
1622 }
1623#undef CONSUME_NODE_LIST
1624
1625 /* return list of trie options at this level */
1626 return tail;
1627}
1628
1629static YAP_Term trie_to_list_node(TrNode node) {
1630 YAP_Term t = TrNode_entry(node);
1631
1632 if (YAP_IsIntTerm(t) || YAP_IsAtomTerm(t)) {
1633 return trie_to_list_create_two(YAP_IsIntTerm(t) ? "int" : "atom", node, t);
1634 } else if (YAP_IsVarTerm(t)) {
1635 int index = TrieVarIndex(t);
1636 YAP_Term index_term = YAP_MkIntTerm((YAP_Int)index);
1637 return trie_to_list_create_two("var", node, index_term);
1638 } else if (YAP_IsPairTerm(t)) {
1639 if (t == FloatInitTag) {
1640 node = TrNode_child(node); /* consume FloatInitTag */
1641 YAP_Functor f = YAP_MkFunctor(YAP_LookupAtom("floats"), 1);
1642 YAP_Term child = trie_to_list_floats(node);
1643 return YAP_MkApplTerm(f, 1, &child);
1644 } else if (t == PairInitTag) {
1645 return trie_to_list_create_simple("list", node);
1646 } else if (t == PairEndEmptyTag) {
1647 return trie_to_list_create_simple_end("endlist", node);
1648 } else if (t == CommaInitTag) {
1649 return trie_to_list_create_simple("comma", node);
1650 } else if (t == CommaEndTag) {
1651 return trie_to_list_create_simple_end("endcomma", node);
1652 }
1653 } else if (ApplTag & t) {
1654 YAP_Functor f = (YAP_Functor)(~ApplTag & t);
1655 int arity = YAP_ArityOfFunctor(f);
1656 YAP_Functor new_f = YAP_MkFunctor(YAP_LookupAtom("functor"), 3);
1657 YAP_Term args[3] = {YAP_MkAtomTerm(YAP_NameOfFunctor(f)),
1658 YAP_MkIntTerm((YAP_Int)arity),
1659 trie_to_list(TrNode_child(node))};
1660 return YAP_MkApplTerm(new_f, 3, args);
1661 }
1662 fprintf(stderr, "***************************************\n");
1663 fprintf(stderr, " Tries core module: unknown type tag\n");
1664 fprintf(stderr, "***************************************\n");
1665 fflush(stderr);
1666
1667 return YAP_MkAtomTerm(YAP_LookupAtom("fail"));
1668}
1669
1670#define PUSH_NEW_FLOAT_TERM(val) \
1671 result = YAP_MkPairTerm(trie_to_list_create_two("float", TrNode_child(node), \
1672 YAP_MkFloatTerm(val)), \
1673 result);
1674
1675#ifdef TAG_LOW_BITS_32
1676
1677YAP_Term trie_to_list_floats_tag_low_32(YAP_Term result, TrNode node,
1678 volatile YAP_Term *p,
1679 volatile double *f) {
1680 if (IS_HASH_NODE(node)) {
1681 TrNode *first_bucket, *bucket;
1682 TrHash hash = (TrHash)node;
1683
1684 first_bucket = TrHash_buckets(hash);
1685 bucket = first_bucket + TrHash_num_buckets(hash);
1686
1687 do {
1688 if (*--bucket) {
1689 node = *bucket;
1690 do {
1691 p[1] = TrNode_entry(node);
1692 PUSH_NEW_FLOAT_TERM(*f);
1693 } while ((node = TrNode_next(node)));
1694 }
1695 } while (bucket != first_bucket);
1696 } else {
1697 do {
1698 p[1] = TrNode_entry(node);
1699 PUSH_NEW_FLOAT_TERM(*f);
1700 } while ((node = TrNode_next(node)));
1701 }
1702
1703 return result;
1704}
1705#endif /* TAG_LOW_BITS_32 */
1706
1707static YAP_Term trie_to_list_floats(TrNode node) {
1708 volatile union {
1709 double f;
1710 YAP_Term p[SIZE_FLOAT_AS_TERM];
1711 } tf; /* to avoid gcc warning */
1712 YAP_Term result = YAP_MkAtomTerm(YAP_LookupAtom("[]"));
1713
1714 if (IS_HASH_NODE(node)) {
1715 TrNode *first_bucket, *bucket;
1716 TrHash hash = (TrHash)node;
1717 first_bucket = TrHash_buckets(hash);
1718 bucket = first_bucket + TrHash_num_buckets(hash);
1719 do {
1720 if (*--bucket) {
1721 node = *bucket;
1722 do {
1723 tf.p[0] = TrNode_entry(node);
1724#ifdef TAG_LOW_BITS_32
1725 result = trie_to_list_floats_tag_low_32(result, TrNode_child(node),
1726 &tf.p, &tf.f);
1727#else
1728 PUSH_NEW_FLOAT_TERM(tf.f);
1729#endif /* TAG_LOW_BITS_32 */
1730 } while ((node = TrNode_next(node)));
1731 }
1732 } while (bucket != first_bucket);
1733 } else {
1734 do {
1735 tf.p[0] = TrNode_entry(node);
1736#ifdef TAG_LOW_BITS_32
1737 result = trie_to_list_floats_tag_low_32(result, TrNode_child(node), &tf.p,
1738 &tf.f);
1739#else
1740 PUSH_NEW_FLOAT_TERM(tf.f);
1741#endif /* TAG_LOW_BITS_32 */
1742 } while ((node = TrNode_next(node)));
1743 }
1744
1745 return result;
1746}
1747#undef PUSH_NEW_FLOAT_TERM
1748
1749#include "core_dbtries.c"
YAP_Deref
#define YAP_Deref(t)
X_API macro.
Definition: YapInterface.h:86
index
@ index
index
Definition: YapGFlagInfo.h:354
bucket
Definition: hash.h:40
trie_engine
Definition: core_tries.h:56
trie_hash
Definition: core_tries.h:94
trie_node
Definition: core_tries.h:80