YAP 7.1.0
tab.tries.h
1/************************************************************************
2** **
3** The YapTab/YapOr/OPTYap systems **
4** **
5** YapTab extends the Yap Prolog engine to support sequential tabling **
6** YapOr extends the Yap Prolog engine to support or-parallelism **
7** OPTYap extends the Yap Prolog engine to support or-parallel tabling **
8** **
9** **
10** Yap Prolog was developed at University of Porto, Portugal **
11** **
12************************************************************************/
13
14/*********************
15** Macros **
16*********************/
17
18#ifdef MODE_GLOBAL_TRIE_ENTRY
19#define INCREMENT_GLOBAL_TRIE_REFERENCE(ENTRY) \
20 { \
21 register gt_node_ptr entry_node = (gt_node_ptr)(ENTRY); \
22 TrNode_child(entry_node) = \
23 (gt_node_ptr)((UInt)TrNode_child(entry_node) + 1); \
24 }
25#define NEW_SUBGOAL_TRIE_NODE(NODE, ENTRY, CHILD, PARENT, NEXT) \
26 INCREMENT_GLOBAL_TRIE_REFERENCE(ENTRY); \
27 new_subgoal_trie_node(NODE, ENTRY, CHILD, PARENT, NEXT)
28#define NEW_ANSWER_TRIE_NODE(NODE, INSTR, ENTRY, CHILD, PARENT, NEXT) \
29 INCREMENT_GLOBAL_TRIE_REFERENCE(ENTRY); \
30 new_answer_trie_node(NODE, INSTR, ENTRY, CHILD, PARENT, NEXT)
31#define NEW_GLOBAL_TRIE_NODE(NODE, ENTRY, CHILD, PARENT, NEXT) \
32 INCREMENT_GLOBAL_TRIE_REFERENCE(ENTRY); \
33 new_global_trie_node(NODE, ENTRY, CHILD, PARENT, NEXT)
34#else
35#define NEW_SUBGOAL_TRIE_NODE(NODE, ENTRY, CHILD, PARENT, NEXT) \
36 new_subgoal_trie_node(NODE, ENTRY, CHILD, PARENT, NEXT)
37#define NEW_ANSWER_TRIE_NODE(NODE, INSTR, ENTRY, CHILD, PARENT, NEXT) \
38 new_answer_trie_node(NODE, INSTR, ENTRY, CHILD, PARENT, NEXT)
39#define NEW_GLOBAL_TRIE_NODE(NODE, ENTRY, CHILD, PARENT, NEXT) \
40 new_global_trie_node(NODE, ENTRY, CHILD, PARENT, NEXT)
41#endif /* MODE_GLOBAL_TRIE_ENTRY */
42
43#ifdef MODE_GLOBAL_TRIE_LOOP
44#define SUBGOAL_CHECK_INSERT_ENTRY(TAB_ENT, NODE, ENTRY) \
45 NODE = global_trie_check_insert_entry(NODE, ENTRY PASS_REGS)
46#define ANSWER_CHECK_INSERT_ENTRY(SG_FR, NODE, ENTRY, INSTR) \
47 NODE = global_trie_check_insert_entry(NODE, ENTRY PASS_REGS)
48#else
49#define SUBGOAL_CHECK_INSERT_ENTRY(TAB_ENT, NODE, ENTRY) \
50 NODE = subgoal_trie_check_insert_entry(TAB_ENT, NODE, ENTRY PASS_REGS)
51#define ANSWER_CHECK_INSERT_ENTRY(SG_FR, NODE, ENTRY, INSTR) \
52 NODE = answer_trie_check_insert_entry(SG_FR, NODE, ENTRY, INSTR PASS_REGS)
53#endif /* MODE_GLOBAL_TRIE_LOOP */
54
55#ifdef INCLUDE_ANSWER_SEARCH_MODE_DIRECTED
56#define ANSWER_SAFE_INSERT_ENTRY(NODE, ENTRY, INSTR) \
57 { \
58 ans_node_ptr new_node; \
59 NEW_ANSWER_TRIE_NODE(new_node, INSTR, ENTRY, NULL, NODE, NULL); \
60 TrNode_child(NODE) = new_node; \
61 NODE = new_node; \
62 }
63#ifdef THREADS
64#define INVALIDATE_ANSWER_TRIE_NODE(NODE, SG_FR) \
65 TrNode_next(NODE) = SgFr_invalid_chain(SG_FR); \
66 SgFr_invalid_chain(SG_FR) = NODE
67#else
68#define INVALIDATE_ANSWER_TRIE_NODE(NODE, SG_FR) FREE_ANSWER_TRIE_NODE(NODE)
69#endif /* THREADS */
70#define INVALIDATE_ANSWER_TRIE_LEAF_NODE(NODE, SG_FR) \
71 TAG_AS_ANSWER_INVALID_NODE(NODE); \
72 TrNode_next(NODE) = SgFr_invalid_chain(SG_FR); \
73 SgFr_invalid_chain(SG_FR) = NODE
74#endif /* INCLUDE_ANSWER_SEARCH_MODE_DIRECTED */
75
76/************************************************************************
77** subgoal_trie_check_insert_(gt)_entry **
78************************************************************************/
79
80#ifdef INCLUDE_SUBGOAL_TRIE_CHECK_INSERT
81#ifndef SUBGOAL_TRIE_LOCK_AT_WRITE_LEVEL /* SUBGOAL_TRIE_LOCK_AT_ENTRY_LEVEL \
82 || SUBGOAL_TRIE_LOCK_AT_NODE_LEVEL \
83 || ! YAPOR */
84#ifdef MODE_GLOBAL_TRIE_ENTRY
85static inline sg_node_ptr
86subgoal_trie_check_insert_gt_entry(tab_ent_ptr tab_ent, sg_node_ptr parent_node,
87 Term t USES_REGS) {
88#else
89static inline sg_node_ptr
90subgoal_trie_check_insert_entry(tab_ent_ptr tab_ent, sg_node_ptr parent_node,
91 Term t USES_REGS) {
92#endif /* MODE_GLOBAL_TRIE_ENTRY */
93 sg_node_ptr child_node;
94
95 LOCK_SUBGOAL_NODE(parent_node);
96 child_node = TrNode_child(parent_node);
97 if (child_node == NULL) {
98 NEW_SUBGOAL_TRIE_NODE(child_node, t, NULL, parent_node, NULL);
99 TrNode_child(parent_node) = child_node;
100 UNLOCK_SUBGOAL_NODE(parent_node);
101 return child_node;
102 }
103
104 if (!IS_SUBGOAL_TRIE_HASH(child_node)) {
105 int count_nodes = 0;
106 do {
107 if (TrNode_entry(child_node) == t) {
108 UNLOCK_SUBGOAL_NODE(parent_node);
109 return child_node;
110 }
111 count_nodes++;
112 child_node = TrNode_next(child_node);
113 } while (child_node);
114 NEW_SUBGOAL_TRIE_NODE(child_node, t, NULL, parent_node,
115 TrNode_child(parent_node));
116 count_nodes++;
117 if (count_nodes >= MAX_NODES_PER_TRIE_LEVEL) {
118 /* alloc a new hash */
119 sg_hash_ptr hash;
120 sg_node_ptr chain_node, next_node, *bucket;
121 new_subgoal_trie_hash(hash, count_nodes, tab_ent);
122 chain_node = child_node;
123 do {
124 bucket = Hash_buckets(hash) +
125 HASH_ENTRY(TrNode_entry(chain_node), BASE_HASH_BUCKETS);
126 next_node = TrNode_next(chain_node);
127 TrNode_next(chain_node) = *bucket;
128 *bucket = chain_node;
129 chain_node = next_node;
130 } while (chain_node);
131 TrNode_child(parent_node) = (sg_node_ptr)hash;
132 } else {
133 TrNode_child(parent_node) = child_node;
134 }
135 UNLOCK_SUBGOAL_NODE(parent_node);
136 return child_node;
137 }
138
139 { /* trie nodes with hashing */
140 sg_hash_ptr hash;
141 sg_node_ptr *bucket;
142 int count_nodes = 0;
143 hash = (sg_hash_ptr)child_node;
144 bucket = Hash_buckets(hash) + HASH_ENTRY(t, Hash_num_buckets(hash));
145 child_node = *bucket;
146 while (child_node) {
147 if (TrNode_entry(child_node) == t) {
148 UNLOCK_SUBGOAL_NODE(parent_node);
149 return child_node;
150 }
151 count_nodes++;
152 child_node = TrNode_next(child_node);
153 }
154 NEW_SUBGOAL_TRIE_NODE(child_node, t, NULL, parent_node, *bucket);
155 *bucket = child_node;
156 Hash_num_nodes(hash)++;
157 count_nodes++;
158 if (count_nodes >= MAX_NODES_PER_BUCKET &&
159 Hash_num_nodes(hash) > Hash_num_buckets(hash)) {
160 /* expand current hash */
161 sg_node_ptr chain_node, next_node, *old_bucket, *old_hash_buckets,
162 *new_hash_buckets;
163 int num_buckets;
164 num_buckets = Hash_num_buckets(hash) * 2;
165 ALLOC_BUCKETS(new_hash_buckets, num_buckets);
166 old_hash_buckets = Hash_buckets(hash);
167 old_bucket = old_hash_buckets + Hash_num_buckets(hash);
168 do {
169 if (*--old_bucket) {
170 chain_node = *old_bucket;
171 do {
172 bucket = new_hash_buckets +
173 HASH_ENTRY(TrNode_entry(chain_node), num_buckets);
174 next_node = TrNode_next(chain_node);
175 TrNode_next(chain_node) = *bucket;
176 *bucket = chain_node;
177 chain_node = next_node;
178 } while (chain_node);
179 }
180 } while (old_bucket != old_hash_buckets);
181 Hash_buckets(hash) = new_hash_buckets;
182 Hash_num_buckets(hash) = num_buckets;
183 FREE_BUCKETS(old_hash_buckets);
184 }
185 UNLOCK_SUBGOAL_NODE(parent_node);
186 return child_node;
187 }
188}
189#else /* SUBGOAL_TRIE_LOCK_AT_WRITE_LEVEL */
190#ifdef MODE_GLOBAL_TRIE_ENTRY
191static inline sg_node_ptr
192subgoal_trie_check_insert_gt_entry(tab_ent_ptr tab_ent, sg_node_ptr parent_node,
193 Term t USES_REGS) {
194#else
195static inline sg_node_ptr
196subgoal_trie_check_insert_entry(tab_ent_ptr tab_ent, sg_node_ptr parent_node,
197 Term t USES_REGS) {
198#endif /* MODE_GLOBAL_TRIE_ENTRY */
199 sg_node_ptr child_node;
200 sg_hash_ptr hash;
201
202 child_node = TrNode_child(parent_node);
203 if (child_node == NULL) {
204#ifdef SUBGOAL_TRIE_ALLOC_BEFORE_CHECK
205 NEW_SUBGOAL_TRIE_NODE(child_node, t, NULL, parent_node, NULL);
206#endif /* SUBGOAL_TRIE_ALLOC_BEFORE_CHECK */
207 LOCK_SUBGOAL_NODE(parent_node);
208 if (TrNode_child(parent_node)) {
209 sg_node_ptr chain_node = TrNode_child(parent_node);
210 if (IS_SUBGOAL_TRIE_HASH(chain_node)) {
211#ifdef SUBGOAL_TRIE_ALLOC_BEFORE_CHECK
212 FREE_SUBGOAL_TRIE_NODE(child_node);
213#endif /* SUBGOAL_TRIE_ALLOC_BEFORE_CHECK */
214 UNLOCK_SUBGOAL_NODE(parent_node);
215 hash = (sg_hash_ptr)chain_node;
216 goto subgoal_trie_hash;
217 }
218 do {
219 if (TrNode_entry(chain_node) == t) {
220#ifdef SUBGOAL_TRIE_ALLOC_BEFORE_CHECK
221 FREE_SUBGOAL_TRIE_NODE(child_node);
222#endif /* SUBGOAL_TRIE_ALLOC_BEFORE_CHECK */
223 UNLOCK_SUBGOAL_NODE(parent_node);
224 return chain_node;
225 }
226 chain_node = TrNode_next(chain_node);
227 } while (chain_node);
228#ifdef SUBGOAL_TRIE_ALLOC_BEFORE_CHECK
229 TrNode_next(child_node) = TrNode_child(parent_node);
230#else
231 NEW_SUBGOAL_TRIE_NODE(child_node, t, NULL, parent_node,
232 TrNode_child(parent_node));
233 } else {
234 NEW_SUBGOAL_TRIE_NODE(child_node, t, NULL, parent_node, NULL);
235#endif /* SUBGOAL_TRIE_ALLOC_BEFORE_CHECK */
236 }
237 TrNode_child(parent_node) = child_node;
238 UNLOCK_SUBGOAL_NODE(parent_node);
239 return child_node;
240 }
241
242 if (!IS_SUBGOAL_TRIE_HASH(child_node)) {
243 sg_node_ptr first_node = child_node;
244 int count_nodes = 0;
245 do {
246 if (TrNode_entry(child_node) == t)
247 return child_node;
248 count_nodes++;
249 child_node = TrNode_next(child_node);
250 } while (child_node);
251#ifdef SUBGOAL_TRIE_ALLOC_BEFORE_CHECK
252 NEW_SUBGOAL_TRIE_NODE(child_node, t, NULL, parent_node, first_node);
253#endif /* SUBGOAL_TRIE_ALLOC_BEFORE_CHECK */
254 LOCK_SUBGOAL_NODE(parent_node);
255 if (first_node != TrNode_child(parent_node)) {
256 sg_node_ptr chain_node = TrNode_child(parent_node);
257 if (IS_SUBGOAL_TRIE_HASH(chain_node)) {
258#ifdef SUBGOAL_TRIE_ALLOC_BEFORE_CHECK
259 FREE_SUBGOAL_TRIE_NODE(child_node);
260#endif /* SUBGOAL_TRIE_ALLOC_BEFORE_CHECK */
261 UNLOCK_SUBGOAL_NODE(parent_node);
262 hash = (sg_hash_ptr)chain_node;
263 goto subgoal_trie_hash;
264 }
265 do {
266 if (TrNode_entry(chain_node) == t) {
267#ifdef SUBGOAL_TRIE_ALLOC_BEFORE_CHECK
268 FREE_SUBGOAL_TRIE_NODE(child_node);
269#endif /* SUBGOAL_TRIE_ALLOC_BEFORE_CHECK */
270 UNLOCK_SUBGOAL_NODE(parent_node);
271 return chain_node;
272 }
273 count_nodes++;
274 chain_node = TrNode_next(chain_node);
275 } while (chain_node != first_node);
276#ifdef SUBGOAL_TRIE_ALLOC_BEFORE_CHECK
277 TrNode_next(child_node) = TrNode_child(parent_node);
278#else
279 NEW_SUBGOAL_TRIE_NODE(child_node, t, NULL, parent_node,
280 TrNode_child(parent_node));
281 } else {
282 NEW_SUBGOAL_TRIE_NODE(child_node, t, NULL, parent_node, first_node);
283#endif /* SUBGOAL_TRIE_ALLOC_BEFORE_CHECK */
284 }
285 count_nodes++;
286 if (count_nodes >= MAX_NODES_PER_TRIE_LEVEL) {
287 /* alloc a new hash */
288 sg_node_ptr chain_node, next_node, *bucket;
289 new_subgoal_trie_hash(hash, count_nodes, tab_ent);
290 chain_node = child_node;
291 do {
292 bucket = Hash_buckets(hash) +
293 HASH_ENTRY(TrNode_entry(chain_node), BASE_HASH_BUCKETS);
294 next_node = TrNode_next(chain_node);
295 TrNode_next(chain_node) = *bucket;
296 *bucket = chain_node;
297 chain_node = next_node;
298 } while (chain_node);
299 TrNode_child(parent_node) = (sg_node_ptr)hash;
300 } else {
301 TrNode_child(parent_node) = child_node;
302 }
303 UNLOCK_SUBGOAL_NODE(parent_node);
304 return child_node;
305 }
306
307 hash = (sg_hash_ptr)child_node;
308subgoal_trie_hash : { /* trie nodes with hashing */
309 sg_node_ptr *bucket, first_node;
310 int num_buckets, count_nodes = 0;
311
312 do {
313 num_buckets = Hash_num_buckets(hash);
314 // __sync_synchronize();
315 bucket = Hash_buckets(hash) + HASH_ENTRY(t, num_buckets);
316 first_node = child_node = *bucket;
317 } while (num_buckets != Hash_num_buckets(hash));
318 while (child_node) {
319 if (TrNode_entry(child_node) == t)
320 return child_node;
321 count_nodes++;
322 child_node = TrNode_next(child_node);
323 }
324#ifdef SUBGOAL_TRIE_ALLOC_BEFORE_CHECK
325 NEW_SUBGOAL_TRIE_NODE(child_node, t, NULL, parent_node, first_node);
326#endif /* SUBGOAL_TRIE_ALLOC_BEFORE_CHECK */
327 LOCK_SUBGOAL_NODE(parent_node);
328 if (num_buckets != Hash_num_buckets(hash)) {
329/* the hash has been expanded */
330#ifdef SUBGOAL_TRIE_ALLOC_BEFORE_CHECK
331 FREE_SUBGOAL_TRIE_NODE(child_node);
332#endif /* SUBGOAL_TRIE_ALLOC_BEFORE_CHECK */
333 UNLOCK_SUBGOAL_NODE(parent_node);
334 goto subgoal_trie_hash;
335 }
336 if (first_node != *bucket) {
337 sg_node_ptr chain_node = *bucket;
338 do {
339 if (TrNode_entry(chain_node) == t) {
340#ifdef SUBGOAL_TRIE_ALLOC_BEFORE_CHECK
341 FREE_SUBGOAL_TRIE_NODE(child_node);
342#endif /* SUBGOAL_TRIE_ALLOC_BEFORE_CHECK */
343 UNLOCK_SUBGOAL_NODE(parent_node);
344 return chain_node;
345 }
346 count_nodes++;
347 chain_node = TrNode_next(chain_node);
348 } while (chain_node != first_node);
349#ifdef SUBGOAL_TRIE_ALLOC_BEFORE_CHECK
350 TrNode_next(child_node) = *bucket;
351#else
352 NEW_SUBGOAL_TRIE_NODE(child_node, t, NULL, parent_node, *bucket);
353 } else {
354 NEW_SUBGOAL_TRIE_NODE(child_node, t, NULL, parent_node, first_node);
355#endif /* SUBGOAL_TRIE_ALLOC_BEFORE_CHECK */
356 }
357 *bucket = child_node;
358 Hash_num_nodes(hash)++;
359 count_nodes++;
360 if (count_nodes >= MAX_NODES_PER_BUCKET &&
361 Hash_num_nodes(hash) > Hash_num_buckets(hash)) {
362 /* expand current hash */
363 sg_node_ptr chain_node, next_node, *old_bucket, *old_hash_buckets,
364 *new_hash_buckets;
365 num_buckets = Hash_num_buckets(hash) * 2;
366 ALLOC_BUCKETS(new_hash_buckets, num_buckets);
367 old_hash_buckets = Hash_buckets(hash);
368 old_bucket = old_hash_buckets + Hash_num_buckets(hash);
369 do {
370 if (*--old_bucket) {
371 chain_node = *old_bucket;
372 do {
373 bucket = new_hash_buckets +
374 HASH_ENTRY(TrNode_entry(chain_node), num_buckets);
375 next_node = TrNode_next(chain_node);
376 TrNode_next(chain_node) = *bucket;
377 *bucket = chain_node;
378 chain_node = next_node;
379 } while (chain_node);
380 }
381 } while (old_bucket != old_hash_buckets);
382 Hash_buckets(hash) = new_hash_buckets;
383 Hash_num_buckets(hash) = num_buckets;
384 FREE_BUCKETS(old_hash_buckets);
385 }
386 UNLOCK_SUBGOAL_NODE(parent_node);
387 return child_node;
388}
389}
390#endif /* SUBGOAL_TRIE_LOCK_LEVEL */
391#endif /* INCLUDE_SUBGOAL_TRIE_CHECK_INSERT */
392
393/************************************************************************
394** answer_trie_check_insert_(gt)_entry **
395************************************************************************/
396
397#ifdef INCLUDE_ANSWER_TRIE_CHECK_INSERT
398#ifndef ANSWER_TRIE_LOCK_AT_WRITE_LEVEL /* ANSWER_TRIE_LOCK_AT_ENTRY_LEVEL || \
399 ANSWER_TRIE_LOCK_AT_NODE_LEVEL || ! \
400 YAPOR */
401#ifdef MODE_GLOBAL_TRIE_ENTRY
402static inline ans_node_ptr
403answer_trie_check_insert_gt_entry(sg_fr_ptr sg_fr, ans_node_ptr parent_node,
404 Term t, int instr USES_REGS) {
405#else
406static inline ans_node_ptr
407answer_trie_check_insert_entry(sg_fr_ptr sg_fr, ans_node_ptr parent_node,
408 Term t, int instr USES_REGS) {
409#endif /* MODE_GLOBAL_TRIE_ENTRY */
410 ans_node_ptr child_node;
411
412 TABLING_ERROR_CHECKING(answer_trie_check_insert_(gt) _entry,
413 IS_ANSWER_LEAF_NODE(parent_node));
414 LOCK_ANSWER_NODE(parent_node);
415 child_node = TrNode_child(parent_node);
416 if (child_node == NULL) {
417 NEW_ANSWER_TRIE_NODE(child_node, instr, t, NULL, parent_node, NULL);
418 TrNode_child(parent_node) = child_node;
419 UNLOCK_ANSWER_NODE(parent_node);
420 return child_node;
421 }
422
423 if (!IS_ANSWER_TRIE_HASH(child_node)) {
424 int count_nodes = 0;
425 do {
426 if (TrNode_entry(child_node) == t) {
427 UNLOCK_ANSWER_NODE(parent_node);
428 return child_node;
429 }
430 count_nodes++;
431 child_node = TrNode_next(child_node);
432 } while (child_node);
433 NEW_ANSWER_TRIE_NODE(child_node, instr, t, NULL, parent_node,
434 TrNode_child(parent_node));
435 count_nodes++;
436 if (count_nodes >= MAX_NODES_PER_TRIE_LEVEL) {
437 /* alloc a new hash */
438 ans_hash_ptr hash;
439 ans_node_ptr chain_node, next_node, *bucket;
440 new_answer_trie_hash(hash, count_nodes, sg_fr);
441 chain_node = child_node;
442 do {
443 bucket = Hash_buckets(hash) +
444 HASH_ENTRY(TrNode_entry(chain_node), BASE_HASH_BUCKETS);
445 next_node = TrNode_next(chain_node);
446 TrNode_next(chain_node) = *bucket;
447 *bucket = chain_node;
448 chain_node = next_node;
449 } while (chain_node);
450 TrNode_child(parent_node) = (ans_node_ptr)hash;
451 } else {
452 TrNode_child(parent_node) = child_node;
453 }
454 UNLOCK_ANSWER_NODE(parent_node);
455 return child_node;
456 }
457
458 { /* trie nodes with hashing */
459 ans_hash_ptr hash;
460 ans_node_ptr *bucket;
461 int count_nodes = 0;
462 hash = (ans_hash_ptr)child_node;
463 bucket = Hash_buckets(hash) + HASH_ENTRY(t, Hash_num_buckets(hash));
464 child_node = *bucket;
465 while (child_node) {
466 if (TrNode_entry(child_node) == t) {
467 UNLOCK_ANSWER_NODE(parent_node);
468 return child_node;
469 }
470 count_nodes++;
471 child_node = TrNode_next(child_node);
472 }
473 NEW_ANSWER_TRIE_NODE(child_node, instr, t, NULL, parent_node, *bucket);
474 *bucket = child_node;
475 Hash_num_nodes(hash)++;
476 count_nodes++;
477 if (count_nodes >= MAX_NODES_PER_BUCKET &&
478 Hash_num_nodes(hash) > Hash_num_buckets(hash)) {
479 /* expand current hash */
480 ans_node_ptr chain_node, next_node, *old_bucket, *old_hash_buckets,
481 *new_hash_buckets;
482 int num_buckets;
483 num_buckets = Hash_num_buckets(hash) * 2;
484 ALLOC_BUCKETS(new_hash_buckets, num_buckets);
485 old_hash_buckets = Hash_buckets(hash);
486 old_bucket = old_hash_buckets + Hash_num_buckets(hash);
487 do {
488 if (*--old_bucket) {
489 chain_node = *old_bucket;
490 do {
491 bucket = new_hash_buckets +
492 HASH_ENTRY(TrNode_entry(chain_node), num_buckets);
493 next_node = TrNode_next(chain_node);
494 TrNode_next(chain_node) = *bucket;
495 *bucket = chain_node;
496 chain_node = next_node;
497 } while (chain_node);
498 }
499 } while (old_bucket != old_hash_buckets);
500 Hash_buckets(hash) = new_hash_buckets;
501 Hash_num_buckets(hash) = num_buckets;
502 FREE_BUCKETS(old_hash_buckets);
503 }
504 UNLOCK_ANSWER_NODE(parent_node);
505 return child_node;
506 }
507}
508#else /* ANSWER_TRIE_LOCK_AT_WRITE_LEVEL */
509#ifdef MODE_GLOBAL_TRIE_ENTRY
510static inline ans_node_ptr
511answer_trie_check_insert_gt_entry(sg_fr_ptr sg_fr, ans_node_ptr parent_node,
512 Term t, int instr USES_REGS) {
513#else
514static inline ans_node_ptr
515answer_trie_check_insert_entry(sg_fr_ptr sg_fr, ans_node_ptr parent_node,
516 Term t, int instr USES_REGS) {
517#endif /* MODE_GLOBAL_TRIE_ENTRY */
518 ans_node_ptr child_node;
519 ans_hash_ptr hash;
520
521 TABLING_ERROR_CHECKING(answer_trie_check_insert_(gt) _entry,
522 IS_ANSWER_LEAF_NODE(parent_node));
523 child_node = TrNode_child(parent_node);
524 if (child_node == NULL) {
525#ifdef ANSWER_TRIE_ALLOC_BEFORE_CHECK
526 NEW_ANSWER_TRIE_NODE(child_node, instr, t, NULL, parent_node, NULL);
527#endif /* ANSWER_TRIE_ALLOC_BEFORE_CHECK */
528 LOCK_ANSWER_NODE(parent_node);
529 if (TrNode_child(parent_node)) {
530 ans_node_ptr chain_node = TrNode_child(parent_node);
531 if (IS_ANSWER_TRIE_HASH(chain_node)) {
532#ifdef ANSWER_TRIE_ALLOC_BEFORE_CHECK
533 FREE_ANSWER_TRIE_NODE(child_node);
534#endif /* ANSWER_TRIE_ALLOC_BEFORE_CHECK */
535 UNLOCK_ANSWER_NODE(parent_node);
536 hash = (ans_hash_ptr)chain_node;
537 goto answer_trie_hash;
538 }
539 do {
540 if (TrNode_entry(chain_node) == t) {
541#ifdef ANSWER_TRIE_ALLOC_BEFORE_CHECK
542 FREE_ANSWER_TRIE_NODE(child_node);
543#endif /* ANSWER_TRIE_ALLOC_BEFORE_CHECK */
544 UNLOCK_ANSWER_NODE(parent_node);
545 return chain_node;
546 }
547 chain_node = TrNode_next(chain_node);
548 } while (chain_node);
549#ifdef ANSWER_TRIE_ALLOC_BEFORE_CHECK
550 TrNode_next(child_node) = TrNode_child(parent_node);
551#else
552 NEW_ANSWER_TRIE_NODE(child_node, instr, t, NULL, parent_node,
553 TrNode_child(parent_node));
554 } else {
555 NEW_ANSWER_TRIE_NODE(child_node, instr, t, NULL, parent_node, NULL);
556#endif /* ANSWER_TRIE_ALLOC_BEFORE_CHECK */
557 }
558 TrNode_child(parent_node) = child_node;
559 UNLOCK_ANSWER_NODE(parent_node);
560 return child_node;
561 }
562
563 if (!IS_ANSWER_TRIE_HASH(child_node)) {
564 ans_node_ptr first_node = child_node;
565 int count_nodes = 0;
566 do {
567 if (TrNode_entry(child_node) == t)
568 return child_node;
569 count_nodes++;
570 child_node = TrNode_next(child_node);
571 } while (child_node);
572#ifdef ANSWER_TRIE_ALLOC_BEFORE_CHECK
573 NEW_ANSWER_TRIE_NODE(child_node, instr, t, NULL, parent_node, first_node);
574#endif /* ANSWER_TRIE_ALLOC_BEFORE_CHECK */
575 LOCK_ANSWER_NODE(parent_node);
576 if (first_node != TrNode_child(parent_node)) {
577 ans_node_ptr chain_node = TrNode_child(parent_node);
578 if (IS_ANSWER_TRIE_HASH(chain_node)) {
579#ifdef ANSWER_TRIE_ALLOC_BEFORE_CHECK
580 FREE_ANSWER_TRIE_NODE(child_node);
581#endif /* ANSWER_TRIE_ALLOC_BEFORE_CHECK */
582 UNLOCK_ANSWER_NODE(parent_node);
583 hash = (ans_hash_ptr)chain_node;
584 goto answer_trie_hash;
585 }
586 do {
587 if (TrNode_entry(chain_node) == t) {
588#ifdef ANSWER_TRIE_ALLOC_BEFORE_CHECK
589 FREE_ANSWER_TRIE_NODE(child_node);
590#endif /* ANSWER_TRIE_ALLOC_BEFORE_CHECK */
591 UNLOCK_ANSWER_NODE(parent_node);
592 return chain_node;
593 }
594 count_nodes++;
595 chain_node = TrNode_next(chain_node);
596 } while (chain_node != first_node);
597#ifdef ANSWER_TRIE_ALLOC_BEFORE_CHECK
598 TrNode_next(child_node) = TrNode_child(parent_node);
599#else
600 NEW_ANSWER_TRIE_NODE(child_node, instr, t, NULL, parent_node,
601 TrNode_child(parent_node));
602 } else {
603 NEW_ANSWER_TRIE_NODE(child_node, instr, t, NULL, parent_node, first_node);
604#endif /* ANSWER_TRIE_ALLOC_BEFORE_CHECK */
605 }
606 count_nodes++;
607 if (count_nodes >= MAX_NODES_PER_TRIE_LEVEL) {
608 /* alloc a new hash */
609 ans_node_ptr chain_node, next_node, *bucket;
610 new_answer_trie_hash(hash, count_nodes, sg_fr);
611 chain_node = child_node;
612 do {
613 bucket = Hash_buckets(hash) +
614 HASH_ENTRY(TrNode_entry(chain_node), BASE_HASH_BUCKETS);
615 next_node = TrNode_next(chain_node);
616 TrNode_next(chain_node) = *bucket;
617 *bucket = chain_node;
618 chain_node = next_node;
619 } while (chain_node);
620 TrNode_child(parent_node) = (ans_node_ptr)hash;
621 } else {
622 TrNode_child(parent_node) = child_node;
623 }
624 UNLOCK_ANSWER_NODE(parent_node);
625 return child_node;
626 }
627
628 hash = (ans_hash_ptr)child_node;
629answer_trie_hash : { /* trie nodes with hashing */
630 ans_node_ptr *bucket, first_node;
631 int num_buckets, count_nodes = 0;
632
633 do {
634 num_buckets = Hash_num_buckets(hash);
635 // __sync_synchronize();
636 bucket = Hash_buckets(hash) + HASH_ENTRY(t, num_buckets);
637 first_node = child_node = *bucket;
638 } while (num_buckets != Hash_num_buckets(hash));
639 while (child_node) {
640 if (TrNode_entry(child_node) == t)
641 return child_node;
642 count_nodes++;
643 child_node = TrNode_next(child_node);
644 }
645#ifdef ANSWER_TRIE_ALLOC_BEFORE_CHECK
646 NEW_ANSWER_TRIE_NODE(child_node, instr, t, NULL, parent_node, first_node);
647#endif /* ANSWER_TRIE_ALLOC_BEFORE_CHECK */
648 LOCK_ANSWER_NODE(parent_node);
649 if (num_buckets != Hash_num_buckets(hash)) {
650/* the hash has been expanded */
651#ifdef ANSWER_TRIE_ALLOC_BEFORE_CHECK
652 FREE_ANSWER_TRIE_NODE(child_node);
653#endif /* ANSWER_TRIE_ALLOC_BEFORE_CHECK */
654 UNLOCK_ANSWER_NODE(parent_node);
655 goto answer_trie_hash;
656 }
657 if (first_node != *bucket) {
658 ans_node_ptr chain_node = *bucket;
659 do {
660 if (TrNode_entry(chain_node) == t) {
661#ifdef ANSWER_TRIE_ALLOC_BEFORE_CHECK
662 FREE_ANSWER_TRIE_NODE(child_node);
663#endif /* ANSWER_TRIE_ALLOC_BEFORE_CHECK */
664 UNLOCK_ANSWER_NODE(parent_node);
665 return chain_node;
666 }
667 count_nodes++;
668 chain_node = TrNode_next(chain_node);
669 } while (chain_node != first_node);
670#ifdef ANSWER_TRIE_ALLOC_BEFORE_CHECK
671 TrNode_next(child_node) = *bucket;
672#else
673 NEW_ANSWER_TRIE_NODE(child_node, instr, t, NULL, parent_node, *bucket);
674 } else {
675 NEW_ANSWER_TRIE_NODE(child_node, instr, t, NULL, parent_node, first_node);
676#endif /* ANSWER_TRIE_ALLOC_BEFORE_CHECK */
677 }
678 *bucket = child_node;
679 Hash_num_nodes(hash)++;
680 count_nodes++;
681 if (count_nodes >= MAX_NODES_PER_BUCKET &&
682 Hash_num_nodes(hash) > Hash_num_buckets(hash)) {
683 /* expand current hash */
684 ans_node_ptr chain_node, next_node, *old_bucket, *old_hash_buckets,
685 *new_hash_buckets;
686 num_buckets = Hash_num_buckets(hash) * 2;
687 ALLOC_BUCKETS(new_hash_buckets, num_buckets);
688 old_hash_buckets = Hash_buckets(hash);
689 old_bucket = old_hash_buckets + Hash_num_buckets(hash);
690 do {
691 if (*--old_bucket) {
692 chain_node = *old_bucket;
693 do {
694 bucket = new_hash_buckets +
695 HASH_ENTRY(TrNode_entry(chain_node), num_buckets);
696 next_node = TrNode_next(chain_node);
697 TrNode_next(chain_node) = *bucket;
698 *bucket = chain_node;
699 chain_node = next_node;
700 } while (chain_node);
701 }
702 } while (old_bucket != old_hash_buckets);
703 Hash_buckets(hash) = new_hash_buckets;
704 Hash_num_buckets(hash) = num_buckets;
705 FREE_BUCKETS(old_hash_buckets);
706 }
707 UNLOCK_ANSWER_NODE(parent_node);
708 return child_node;
709}
710}
711#endif /* ANSWER_TRIE_LOCK_LEVEL */
712#endif /* INCLUDE_ANSWER_TRIE_CHECK_INSERT */
713
714/************************************************************************
715** global_trie_check_insert_(gt)_entry **
716************************************************************************/
717
718#ifdef INCLUDE_GLOBAL_TRIE_CHECK_INSERT
719#ifndef GLOBAL_TRIE_LOCK_AT_WRITE_LEVEL /* GLOBAL_TRIE_LOCK_AT_NODE_LEVEL || ! \
720 YAPOR */
721#ifdef MODE_GLOBAL_TRIE_ENTRY
722static inline gt_node_ptr
723global_trie_check_insert_gt_entry(gt_node_ptr parent_node, Term t USES_REGS) {
724#else
725static inline gt_node_ptr
726global_trie_check_insert_entry(gt_node_ptr parent_node, Term t USES_REGS) {
727#endif /* MODE_GLOBAL_TRIE_ENTRY */
728 gt_node_ptr child_node;
729
730 LOCK_GLOBAL_NODE(parent_node);
731 child_node = TrNode_child(parent_node);
732 if (child_node == NULL) {
733 NEW_GLOBAL_TRIE_NODE(child_node, t, NULL, parent_node, NULL);
734 TrNode_child(parent_node) = child_node;
735 UNLOCK_GLOBAL_NODE(parent_node);
736 return child_node;
737 }
738
739 if (!IS_GLOBAL_TRIE_HASH(child_node)) {
740 int count_nodes = 0;
741 do {
742 if (TrNode_entry(child_node) == t) {
743 UNLOCK_GLOBAL_NODE(parent_node);
744 return child_node;
745 }
746 count_nodes++;
747 child_node = TrNode_next(child_node);
748 } while (child_node);
749 NEW_GLOBAL_TRIE_NODE(child_node, t, NULL, parent_node,
750 TrNode_child(parent_node));
751 count_nodes++;
752 if (count_nodes >= MAX_NODES_PER_TRIE_LEVEL) {
753 /* alloc a new hash */
754 gt_hash_ptr hash;
755 gt_node_ptr chain_node, next_node, *bucket;
756 new_global_trie_hash(hash, count_nodes);
757 chain_node = child_node;
758 do {
759 bucket = Hash_buckets(hash) +
760 HASH_ENTRY(TrNode_entry(chain_node), BASE_HASH_BUCKETS);
761 next_node = TrNode_next(chain_node);
762 TrNode_next(chain_node) = *bucket;
763 *bucket = chain_node;
764 chain_node = next_node;
765 } while (chain_node);
766 TrNode_child(parent_node) = (gt_node_ptr)hash;
767 } else {
768 TrNode_child(parent_node) = child_node;
769 }
770 UNLOCK_GLOBAL_NODE(parent_node);
771 return child_node;
772 }
773
774 { /* trie nodes with hashing */
775 gt_hash_ptr hash;
776 gt_node_ptr *bucket;
777 int count_nodes = 0;
778 hash = (gt_hash_ptr)child_node;
779 bucket = Hash_buckets(hash) + HASH_ENTRY(t, Hash_num_buckets(hash));
780 child_node = *bucket;
781 while (child_node) {
782 if (TrNode_entry(child_node) == t) {
783 UNLOCK_GLOBAL_NODE(parent_node);
784 return child_node;
785 }
786 count_nodes++;
787 child_node = TrNode_next(child_node);
788 }
789 NEW_GLOBAL_TRIE_NODE(child_node, t, NULL, parent_node, *bucket);
790 *bucket = child_node;
791 Hash_num_nodes(hash)++;
792 count_nodes++;
793 if (count_nodes >= MAX_NODES_PER_BUCKET &&
794 Hash_num_nodes(hash) > Hash_num_buckets(hash)) {
795 /* expand current hash */
796 gt_node_ptr chain_node, next_node, *old_bucket, *old_hash_buckets,
797 *new_hash_buckets;
798 int num_buckets;
799 num_buckets = Hash_num_buckets(hash) * 2;
800 ALLOC_BUCKETS(new_hash_buckets, num_buckets);
801 old_hash_buckets = Hash_buckets(hash);
802 old_bucket = old_hash_buckets + Hash_num_buckets(hash);
803 do {
804 if (*--old_bucket) {
805 chain_node = *old_bucket;
806 do {
807 bucket = new_hash_buckets +
808 HASH_ENTRY(TrNode_entry(chain_node), num_buckets);
809 next_node = TrNode_next(chain_node);
810 TrNode_next(chain_node) = *bucket;
811 *bucket = chain_node;
812 chain_node = next_node;
813 } while (chain_node);
814 }
815 } while (old_bucket != old_hash_buckets);
816 Hash_buckets(hash) = new_hash_buckets;
817 Hash_num_buckets(hash) = num_buckets;
818 FREE_BUCKETS(old_hash_buckets);
819 }
820 UNLOCK_GLOBAL_NODE(parent_node);
821 return child_node;
822 }
823}
824#else /* GLOBAL_TRIE_LOCK_AT_WRITE_LEVEL */
825#ifdef MODE_GLOBAL_TRIE_ENTRY
826static inline gt_node_ptr
827global_trie_check_insert_gt_entry(gt_node_ptr parent_node, Term t USES_REGS) {
828#else
829static inline gt_node_ptr
830global_trie_check_insert_entry(gt_node_ptr parent_node, Term t USES_REGS) {
831#endif /* MODE_GLOBAL_TRIE_ENTRY */
832 gt_node_ptr child_node;
833 gt_hash_ptr hash;
834
835 child_node = TrNode_child(parent_node);
836 if (child_node == NULL) {
837#ifdef GLOBAL_TRIE_ALLOC_BEFORE_CHECK
838 NEW_GLOBAL_TRIE_NODE(child_node, t, NULL, parent_node, NULL);
839#endif /* GLOBAL_TRIE_ALLOC_BEFORE_CHECK */
840 LOCK_GLOBAL_NODE(parent_node);
841 if (TrNode_child(parent_node)) {
842 gt_node_ptr chain_node = TrNode_child(parent_node);
843 if (IS_GLOBAL_TRIE_HASH(chain_node)) {
844#ifdef GLOBAL_TRIE_ALLOC_BEFORE_CHECK
845 FREE_GLOBAL_TRIE_NODE(child_node);
846#endif /* GLOBAL_TRIE_ALLOC_BEFORE_CHECK */
847 UNLOCK_GLOBAL_NODE(parent_node);
848 hash = (gt_hash_ptr)chain_node;
849 goto global_trie_hash;
850 }
851 do {
852 if (TrNode_entry(chain_node) == t) {
853#ifdef GLOBAL_TRIE_ALLOC_BEFORE_CHECK
854 FREE_GLOBAL_TRIE_NODE(child_node);
855#endif /* GLOBAL_TRIE_ALLOC_BEFORE_CHECK */
856 UNLOCK_GLOBAL_NODE(parent_node);
857 return chain_node;
858 }
859 chain_node = TrNode_next(chain_node);
860 } while (chain_node);
861#ifdef GLOBAL_TRIE_ALLOC_BEFORE_CHECK
862 TrNode_next(child_node) = TrNode_child(parent_node);
863#else
864 NEW_GLOBAL_TRIE_NODE(child_node, t, NULL, parent_node,
865 TrNode_child(parent_node));
866 } else {
867 NEW_GLOBAL_TRIE_NODE(child_node, t, NULL, parent_node, NULL);
868#endif /* GLOBAL_TRIE_ALLOC_BEFORE_CHECK */
869 }
870 TrNode_child(parent_node) = child_node;
871 UNLOCK_GLOBAL_NODE(parent_node);
872 return child_node;
873 }
874
875 if (!IS_GLOBAL_TRIE_HASH(child_node)) {
876 gt_node_ptr first_node = child_node;
877 int count_nodes = 0;
878 do {
879 if (TrNode_entry(child_node) == t)
880 return child_node;
881 count_nodes++;
882 child_node = TrNode_next(child_node);
883 } while (child_node);
884#ifdef GLOBAL_TRIE_ALLOC_BEFORE_CHECK
885 NEW_GLOBAL_TRIE_NODE(child_node, t, NULL, parent_node, first_node);
886#endif /* GLOBAL_TRIE_ALLOC_BEFORE_CHECK */
887 LOCK_GLOBAL_NODE(parent_node);
888 if (first_node != TrNode_child(parent_node)) {
889 gt_node_ptr chain_node = TrNode_child(parent_node);
890 if (IS_GLOBAL_TRIE_HASH(chain_node)) {
891#ifdef GLOBAL_TRIE_ALLOC_BEFORE_CHECK
892 FREE_GLOBAL_TRIE_NODE(child_node);
893#endif /* GLOBAL_TRIE_ALLOC_BEFORE_CHECK */
894 UNLOCK_GLOBAL_NODE(parent_node);
895 hash = (gt_hash_ptr)chain_node;
896 goto global_trie_hash;
897 }
898 do {
899 if (TrNode_entry(chain_node) == t) {
900#ifdef GLOBAL_TRIE_ALLOC_BEFORE_CHECK
901 FREE_GLOBAL_TRIE_NODE(child_node);
902#endif /* GLOBAL_TRIE_ALLOC_BEFORE_CHECK */
903 UNLOCK_GLOBAL_NODE(parent_node);
904 return chain_node;
905 }
906 count_nodes++;
907 chain_node = TrNode_next(chain_node);
908 } while (chain_node != first_node);
909#ifdef GLOBAL_TRIE_ALLOC_BEFORE_CHECK
910 TrNode_next(child_node) = TrNode_child(parent_node);
911#else
912 NEW_GLOBAL_TRIE_NODE(child_node, t, NULL, parent_node,
913 TrNode_child(parent_node));
914 } else {
915 NEW_GLOBAL_TRIE_NODE(child_node, t, NULL, parent_node, first_node);
916#endif /* GLOBAL_TRIE_ALLOC_BEFORE_CHECK */
917 }
918 count_nodes++;
919 if (count_nodes >= MAX_NODES_PER_TRIE_LEVEL) {
920 /* alloc a new hash */
921 gt_node_ptr chain_node, next_node, *bucket;
922 new_global_trie_hash(hash, count_nodes);
923 chain_node = child_node;
924 do {
925 bucket = Hash_buckets(hash) +
926 HASH_ENTRY(TrNode_entry(chain_node), BASE_HASH_BUCKETS);
927 next_node = TrNode_next(chain_node);
928 TrNode_next(chain_node) = *bucket;
929 *bucket = chain_node;
930 chain_node = next_node;
931 } while (chain_node);
932 TrNode_child(parent_node) = (gt_node_ptr)hash;
933 } else {
934 TrNode_child(parent_node) = child_node;
935 }
936 UNLOCK_GLOBAL_NODE(parent_node);
937 return child_node;
938 }
939
940 hash = (gt_hash_ptr)child_node;
941global_trie_hash : { /* trie nodes with hashing */
942 gt_node_ptr *bucket, first_node;
943 int num_buckets, count_nodes = 0;
944
945 do {
946 num_buckets = Hash_num_buckets(hash);
947 // __sync_synchronize();
948 bucket = Hash_buckets(hash) + HASH_ENTRY(t, num_buckets);
949 first_node = child_node = *bucket;
950 } while (num_buckets != Hash_num_buckets(hash));
951 while (child_node) {
952 if (TrNode_entry(child_node) == t)
953 return child_node;
954 count_nodes++;
955 child_node = TrNode_next(child_node);
956 }
957#ifdef GLOBAL_TRIE_ALLOC_BEFORE_CHECK
958 NEW_GLOBAL_TRIE_NODE(child_node, t, NULL, parent_node, first_node);
959#endif /* GLOBAL_TRIE_ALLOC_BEFORE_CHECK */
960 LOCK_GLOBAL_NODE(parent_node);
961 if (num_buckets != Hash_num_buckets(hash)) {
962/* the hash has been expanded */
963#ifdef GLOBAL_TRIE_ALLOC_BEFORE_CHECK
964 FREE_GLOBAL_TRIE_NODE(child_node);
965#endif /* GLOBAL_TRIE_ALLOC_BEFORE_CHECK */
966 UNLOCK_GLOBAL_NODE(parent_node);
967 goto global_trie_hash;
968 }
969 if (first_node != *bucket) {
970 gt_node_ptr chain_node = *bucket;
971 do {
972 if (TrNode_entry(chain_node) == t) {
973#ifdef GLOBAL_TRIE_ALLOC_BEFORE_CHECK
974 FREE_GLOBAL_TRIE_NODE(child_node);
975#endif /* GLOBAL_TRIE_ALLOC_BEFORE_CHECK */
976 UNLOCK_GLOBAL_NODE(parent_node);
977 return chain_node;
978 }
979 count_nodes++;
980 chain_node = TrNode_next(chain_node);
981 } while (chain_node != first_node);
982#ifdef GLOBAL_TRIE_ALLOC_BEFORE_CHECK
983 TrNode_next(child_node) = *bucket;
984#else
985 NEW_GLOBAL_TRIE_NODE(child_node, t, NULL, parent_node, *bucket);
986 } else {
987 NEW_GLOBAL_TRIE_NODE(child_node, t, NULL, parent_node, first_node);
988#endif /* GLOBAL_TRIE_ALLOC_BEFORE_CHECK */
989 }
990 *bucket = child_node;
991 Hash_num_nodes(hash)++;
992 count_nodes++;
993 if (count_nodes >= MAX_NODES_PER_BUCKET &&
994 Hash_num_nodes(hash) > Hash_num_buckets(hash)) {
995 /* expand current hash */
996 gt_node_ptr chain_node, next_node, *old_bucket, *old_hash_buckets,
997 *new_hash_buckets;
998 num_buckets = Hash_num_buckets(hash) * 2;
999 ALLOC_BUCKETS(new_hash_buckets, num_buckets);
1000 old_hash_buckets = Hash_buckets(hash);
1001 old_bucket = old_hash_buckets + Hash_num_buckets(hash);
1002 do {
1003 if (*--old_bucket) {
1004 chain_node = *old_bucket;
1005 do {
1006 bucket = new_hash_buckets +
1007 HASH_ENTRY(TrNode_entry(chain_node), num_buckets);
1008 next_node = TrNode_next(chain_node);
1009 TrNode_next(chain_node) = *bucket;
1010 *bucket = chain_node;
1011 chain_node = next_node;
1012 } while (chain_node);
1013 }
1014 } while (old_bucket != old_hash_buckets);
1015 Hash_buckets(hash) = new_hash_buckets;
1016 Hash_num_buckets(hash) = num_buckets;
1017 FREE_BUCKETS(old_hash_buckets);
1018 }
1019 UNLOCK_GLOBAL_NODE(parent_node);
1020 return child_node;
1021}
1022}
1023#endif /* GLOBAL_TRIE_LOCK_LEVEL */
1024#endif /* INCLUDE_GLOBAL_TRIE_CHECK_INSERT */
1025
1026/************************************************************************
1027** subgoal_search(_global_trie)(_terms)_loop **
1028************************************************************************/
1029
1030#ifdef INCLUDE_SUBGOAL_SEARCH_LOOP
1031#ifdef MODE_GLOBAL_TRIE_LOOP
1032#ifdef GLOBAL_TRIE_FOR_SUBTERMS
1033static inline gt_node_ptr
1034subgoal_search_global_trie_terms_loop(Term t, int *subs_arity_ptr,
1035 CELL **stack_vars_ptr,
1036 CELL *stack_terms USES_REGS) {
1037#else
1038static inline gt_node_ptr
1039subgoal_search_global_trie_loop(Term t, int *subs_arity_ptr,
1040 CELL **stack_vars_ptr USES_REGS) {
1041#endif /* GLOBAL_TRIE_FOR_SUBTERMS */
1042#else
1043#ifdef MODE_TERMS_LOOP
1044static inline sg_node_ptr
1045subgoal_search_terms_loop(tab_ent_ptr tab_ent, sg_node_ptr current_node, Term t,
1046 int *subs_arity_ptr,
1047 CELL **stack_vars_ptr USES_REGS) {
1048#else
1049static inline sg_node_ptr subgoal_search_loop(tab_ent_ptr tab_ent,
1050 sg_node_ptr current_node, Term t,
1051 int *subs_arity_ptr,
1052 CELL **stack_vars_ptr USES_REGS) {
1053#endif /* MODE_TERMS_LOOP */
1054#endif /* MODE_GLOBAL_TRIE_LOOP */
1055/************************************************************************
1056 ===========
1057 | |
1058 | ... |
1059 | |
1060 -----------
1061 | VAR_N | <-- stack_vars
1062 ----------- *
1063 | ... | /|\
1064 ----------- | subs_arity (N+1)
1065 | VAR_0 | \|/
1066 ----------- *
1067 YENV --> | |
1068 -----------
1069 | |
1070 | ... |
1071 | |
1072 ===========
1073 | |
1074 | ... |
1075 | |
1076 -----------
1077 TR --> | | <-- stack_terms_limit
1078 -----------
1079 | |
1080 | ... |
1081 | |
1082 ----------|
1083 | TERM_N | <-- stack_terms
1084 ----------| *
1085 | ... | /|\
1086 ----------| |
1087 | TERM_1 | |
1088 ----------| |
1089 | NULL | \|/
1090 =========== *
1091 LOCAL_TrailTop --> | |
1092 -----------
1093************************************************************************/
1094#ifdef MODE_GLOBAL_TRIE_LOOP
1095 gt_node_ptr current_node = GLOBAL_root_gt;
1096#endif /* MODE_GLOBAL_TRIE_LOOP */
1097 int subs_arity = *subs_arity_ptr;
1098 CELL *stack_vars = *stack_vars_ptr;
1099#if !defined(MODE_GLOBAL_TRIE_LOOP) || !defined(GLOBAL_TRIE_FOR_SUBTERMS)
1100 CELL *stack_terms = (CELL *)LOCAL_TrailTop;
1101#endif /* ! MODE_GLOBAL_TRIE_LOOP || ! GLOBAL_TRIE_FOR_SUBTERMS */
1102 CELL *stack_terms_limit = (CELL *)TR;
1103 AUX_STACK_CHECK_EXPAND(
1104 stack_terms, stack_terms_limit + 1); /* + 1 because initially we stiil
1105 haven't done any STACK_POP_DOWN */
1106 STACK_PUSH_UP(NULL, stack_terms);
1107
1108#if defined(MODE_GLOBAL_TRIE_LOOP)
1109 /* for the global trie, it is safe to skip the IsVarTerm() and
1110 * IsAtomOrIntTerm() tests in the first iteration */
1111 goto subgoal_search_loop_non_atomic;
1112#endif /* MODE_GLOBAL_TRIE_LOOP */
1113
1114#ifdef TRIE_RATIONAL_TERMS
1115 /* Needed structures, variables to support rational terms */
1116 term_array Ts;
1117 void *CyclicTerm;
1118 term_array_init(&Ts, 10);
1119#endif /* RATIONAL TERM SUPPORT FOR TRIES */
1120
1121 do {
1122 if (IsVarTerm(t)) {
1123 if (IsTableVarTerm(t)) {
1124 t = MakeTableVarTerm(VarIndexOfTerm(t));
1125 SUBGOAL_CHECK_INSERT_ENTRY(tab_ent, current_node, t);
1126 } else {
1127 if (subs_arity == MAX_TABLE_VARS)
1128 Yap_Error(SYSTEM_ERROR_INTERNAL, TermNil,
1129 "subgoal_search_loop: MAX_TABLE_VARS exceeded");
1130 STACK_PUSH_UP(t, stack_vars);
1131 *((CELL *)t) = GLOBAL_table_var_enumerator(subs_arity);
1132 t = MakeTableVarTerm(subs_arity);
1133 subs_arity = subs_arity + 1;
1134 SUBGOAL_CHECK_INSERT_ENTRY(tab_ent, current_node, t);
1135 }
1136 } else if (IsAtomOrIntTerm(t)) {
1137 SUBGOAL_CHECK_INSERT_ENTRY(tab_ent, current_node, t);
1138#ifdef MODE_TERMS_LOOP
1139 } else {
1140 gt_node_ptr entry_node;
1141#ifdef GLOBAL_TRIE_FOR_SUBTERMS
1142 entry_node = subgoal_search_global_trie_terms_loop(
1143 t, &subs_arity, &stack_vars, stack_terms PASS_REGS);
1144#else
1145 entry_node = subgoal_search_global_trie_loop(t, &subs_arity,
1146 &stack_vars PASS_REGS);
1147#endif /* GLOBAL_TRIE_FOR_SUBTERMS */
1148 current_node = subgoal_trie_check_insert_gt_entry(
1149 tab_ent, current_node, (Term)entry_node PASS_REGS);
1150#else /* ! MODE_TERMS_LOOP */
1151 } else
1152#ifdef TRIE_RATIONAL_TERMS
1153 if (IsRationalTerm(t)) {
1154 t = STACK_POP_DOWN(stack_terms);
1155 SUBGOAL_CHECK_INSERT_ENTRY(tab_ent, current_node, t);
1156 } else
1157#endif /* RATIONAL TERM SUPPORT FOR TRIES */
1158#if defined(MODE_GLOBAL_TRIE_LOOP)
1159 /* for the global trie, it is safe to start here in the first iteration */
1160 subgoal_search_loop_non_atomic:
1161#endif /* MODE_GLOBAL_TRIE_LOOP */
1162#ifdef TRIE_COMPACT_PAIRS
1163 if (IsPairTerm(t)) {
1164#ifdef TRIE_RATIONAL_TERMS
1165 CyclicTerm = NULL;
1166#endif /* RATIONAL TERM SUPPORT FOR TRIES */
1167 CELL *aux_pair = RepPair(t);
1168 if (aux_pair == PairTermMark) {
1169 t = STACK_POP_DOWN(stack_terms);
1170#ifdef TRIE_RATIONAL_TERMS
1171 if (IsPairTerm(t) && !IsRationalTerm(t)) {
1172 term_array_push(&Ts, (void *)t, (void *)current_node);
1173#else
1174 if (IsPairTerm(t)) {
1175#endif /* RATIONAL TERM SUPPORT FOR TRIES */
1176 aux_pair = RepPair(t);
1177 t = Deref(aux_pair[1]);
1178#ifdef TRIE_RATIONAL_TERMS
1179 if (IsVarTerm(aux_pair[1]) || IsPairTerm(aux_pair[1])) {
1180 CyclicTerm = term_array_member(Ts, (void *)t);
1181 }
1182 if (CyclicTerm != NULL) {
1183 STACK_PUSH_UP((Term)CyclicTerm, stack_terms);
1184 STACK_PUSH_UP((Term)RationalMark, stack_terms);
1185 STACK_PUSH_UP(AbsPair(PairTermMark), stack_terms);
1186 } else
1187#endif /* RATIONAL TERM SUPPORT FOR TRIES */
1188 if (t == TermNil) {
1189 SUBGOAL_CHECK_INSERT_ENTRY(tab_ent, current_node,
1190 CompactPairEndList);
1191 } else {
1192 /* AUX_STACK_CHECK_EXPAND(stack_terms, stack_terms_limit + 2); */
1193 /* AUX_STACK_CHECK_EXPAND is not necessary here because the
1194 *situation of pushing **
1195 ** up 3 terms has already initially checked for the CompactPairInit
1196 *term */
1197 STACK_PUSH_UP(t, stack_terms);
1198 STACK_PUSH_UP(AbsPair(PairTermMark), stack_terms);
1199 }
1200#ifdef TRIE_RATIONAL_TERMS
1201 CyclicTerm = NULL;
1202 if (IsVarTerm(aux_pair[0]) || IsPairTerm(aux_pair[0]))
1203 CyclicTerm = term_array_member(Ts, (void *)Deref(aux_pair[0]));
1204 if (CyclicTerm != NULL) {
1205 STACK_PUSH_UP((Term)CyclicTerm, stack_terms);
1206 STACK_PUSH_UP((Term)RationalMark, stack_terms);
1207 } else
1208#endif /* RATIONAL TERM SUPPORT FOR TRIES */
1209 STACK_PUSH_UP(Deref(aux_pair[0]), stack_terms);
1210 } else {
1211 SUBGOAL_CHECK_INSERT_ENTRY(tab_ent, current_node, CompactPairEndTerm);
1212 STACK_PUSH_UP(t, stack_terms);
1213 }
1214#if defined(MODE_GLOBAL_TRIE_LOOP) && defined(GLOBAL_TRIE_FOR_SUBTERMS)
1215 } else if (current_node != GLOBAL_root_gt) {
1216 gt_node_ptr entry_node = subgoal_search_global_trie_terms_loop(
1217 t, &subs_arity, &stack_vars, stack_terms PASS_REGS);
1218 current_node = global_trie_check_insert_gt_entry(
1219 current_node, (Term)entry_node PASS_REGS);
1220#endif /* MODE_GLOBAL_TRIE_LOOP && GLOBAL_TRIE_FOR_SUBTERMS */
1221 } else {
1222#ifdef TRIE_RATIONAL_TERMS
1223 term_array_push(&Ts, (void *)t, (void *)current_node);
1224#endif /* RATIONAL TERM SUPPORT FOR TRIES */
1225 SUBGOAL_CHECK_INSERT_ENTRY(tab_ent, current_node, CompactPairInit);
1226 t = Deref(aux_pair[1]);
1227#ifdef TRIE_RATIONAL_TERMS
1228 if (IsVarTerm(aux_pair[1]) || IsPairTerm(aux_pair[1])) {
1229 CyclicTerm = term_array_member(Ts, (void *)t);
1230 }
1231 if (CyclicTerm != NULL) {
1232 STACK_PUSH_UP((Term)CyclicTerm, stack_terms);
1233 STACK_PUSH_UP((Term)RationalMark, stack_terms);
1234 STACK_PUSH_UP(AbsPair(PairTermMark), stack_terms);
1235 } else
1236#endif /* RATIONAL TERM SUPPORT FOR TRIES */
1237 if (t == TermNil) {
1238 SUBGOAL_CHECK_INSERT_ENTRY(tab_ent, current_node, CompactPairEndList);
1239 } else {
1240 AUX_STACK_CHECK_EXPAND(stack_terms, stack_terms_limit + 2);
1241 STACK_PUSH_UP(t, stack_terms);
1242 STACK_PUSH_UP(AbsPair(PairTermMark), stack_terms);
1243 }
1244#ifdef TRIE_RATIONAL_TERMS
1245 CyclicTerm = NULL;
1246 if (IsVarTerm(aux_pair[0]) || IsPairTerm(aux_pair[0]))
1247 CyclicTerm = term_array_member(Ts, (void *)Deref(aux_pair[0]));
1248 if (CyclicTerm != NULL) {
1249 STACK_PUSH_UP((Term)CyclicTerm, stack_terms);
1250 STACK_PUSH_UP((Term)RationalMark, stack_terms);
1251 } else
1252#endif /* RATIONAL TERM SUPPORT FOR TRIES */
1253 STACK_PUSH_UP(Deref(aux_pair[0]), stack_terms);
1254 }
1255#if defined(MODE_GLOBAL_TRIE_LOOP) && defined(GLOBAL_TRIE_FOR_SUBTERMS)
1256 } else if (current_node != GLOBAL_root_gt) {
1257 gt_node_ptr entry_node = subgoal_search_global_trie_terms_loop(
1258 t, &subs_arity, &stack_vars, stack_terms PASS_REGS);
1259 current_node = global_trie_check_insert_gt_entry(
1260 current_node, (Term)entry_node PASS_REGS);
1261#endif /* MODE_GLOBAL_TRIE_LOOP && GLOBAL_TRIE_FOR_SUBTERMS */
1262#else /* ! TRIE_COMPACT_PAIRS */
1263#if defined(MODE_GLOBAL_TRIE_LOOP) && defined(GLOBAL_TRIE_FOR_SUBTERMS)
1264 if (current_node != GLOBAL_root_gt) {
1265 gt_node_ptr entry_node = subgoal_search_global_trie_terms_loop(
1266 t, &subs_arity, &stack_vars, stack_terms PASS_REGS);
1267 current_node = global_trie_check_insert_gt_entry(
1268 current_node, (Term)entry_node PASS_REGS);
1269 } else
1270#endif /* MODE_GLOBAL_TRIE_LOOP && GLOBAL_TRIE_FOR_SUBTERMS */
1271 if (IsPairTerm(t)) {
1272 CELL *aux_pair = RepPair(t);
1273 SUBGOAL_CHECK_INSERT_ENTRY(tab_ent, current_node, AbsPair(NULL));
1274 AUX_STACK_CHECK_EXPAND(stack_terms, stack_terms_limit + 1);
1275 STACK_PUSH_UP(Deref(aux_pair[1]), stack_terms);
1276 STACK_PUSH_UP(Deref(aux_pair[0]), stack_terms);
1277#endif /* TRIE_COMPACT_PAIRS */
1278 } else if (IsApplTerm(t)) {
1279 Functor f = FunctorOfTerm(t);
1280 if (f == FunctorDouble) {
1281 union {
1282 Term t_dbl[sizeof(Float) / sizeof(Term)];
1283 Float dbl;
1284 } u;
1285 u.dbl = FloatOfTerm(t);
1286 SUBGOAL_CHECK_INSERT_ENTRY(tab_ent, current_node, AbsAppl((Term *)f));
1287#if SIZEOF_DOUBLE == 2 * SIZEOF_INT_P
1288 SUBGOAL_CHECK_INSERT_ENTRY(tab_ent, current_node, u.t_dbl[1]);
1289#endif /* SIZEOF_DOUBLE x SIZEOF_INT_P */
1290 SUBGOAL_CHECK_INSERT_ENTRY(tab_ent, current_node, u.t_dbl[0]);
1291#ifdef MODE_GLOBAL_TRIE_LOOP
1292 SUBGOAL_CHECK_INSERT_ENTRY(tab_ent, current_node, AbsAppl((Term *)f));
1293#endif /* MODE_GLOBAL_TRIE_LOOP */
1294 } else if (f == FunctorLongInt) {
1295 Int li = LongIntOfTerm(t);
1296 SUBGOAL_CHECK_INSERT_ENTRY(tab_ent, current_node, AbsAppl((Term *)f));
1297 SUBGOAL_CHECK_INSERT_ENTRY(tab_ent, current_node, li);
1298#ifdef MODE_GLOBAL_TRIE_LOOP
1299 SUBGOAL_CHECK_INSERT_ENTRY(tab_ent, current_node, AbsAppl((Term *)f));
1300#endif /* MODE_GLOBAL_TRIE_LOOP */
1301 } else if (f == FunctorBigInt || f == FunctorString) {
1302 CELL *new = Yap_HeapStoreOpaqueTerm(t);
1303 SUBGOAL_CHECK_INSERT_ENTRY(tab_ent, current_node, AbsAppl((Term *)f));
1304 SUBGOAL_CHECK_INSERT_ENTRY(tab_ent, current_node, (CELL) new);
1305#ifdef MODE_GLOBAL_TRIE_LOOP
1306 SUBGOAL_CHECK_INSERT_ENTRY(tab_ent, current_node, AbsAppl((Term *)f));
1307#endif /* MODE_GLOBAL_TRIE_LOOP */
1308 } else if (f == FunctorDBRef) {
1309 Yap_Error(SYSTEM_ERROR_INTERNAL, TermNil,
1310 "subgoal_search_loop: unsupported type tag FunctorDBRef");
1311 } else {
1312#ifdef TRIE_RATIONAL_TERMS
1313 term_array_push(&Ts, (void *)t, (void *)current_node);
1314#endif /* RATIONAL TERM SUPPORT FOR TRIES */
1315 int i;
1316 CELL *aux_appl = RepAppl(t);
1317 SUBGOAL_CHECK_INSERT_ENTRY(tab_ent, current_node, AbsAppl((Term *)f));
1318 AUX_STACK_CHECK_EXPAND(stack_terms,
1319 stack_terms_limit + ArityOfFunctor(f) - 1);
1320 for (i = ArityOfFunctor(f); i >= 1; i--) {
1321#ifdef TRIE_RATIONAL_TERMS
1322 CyclicTerm = NULL;
1323 if (IsVarTerm(aux_appl[i]) || IsApplTerm(aux_appl[i]))
1324 CyclicTerm = term_array_member(Ts, (void *)Deref(aux_appl[i]));
1325 if (CyclicTerm != NULL) {
1326 STACK_PUSH_UP((Term)CyclicTerm, stack_terms);
1327 STACK_PUSH_UP((Term)RationalMark, stack_terms);
1328 } else
1329#endif /* RATIONAL TERM SUPPORT FOR TRIES */
1330 STACK_PUSH_UP(Deref(aux_appl[i]), stack_terms);
1331 }
1332 }
1333 } else {
1334 Yap_Error(SYSTEM_ERROR_INTERNAL, TermNil,
1335 "subgoal_search_loop: unknown type tag");
1336#endif /* MODE_TERMS_LOOP */
1337 }
1338 t = STACK_POP_DOWN(stack_terms);
1339 } while (t);
1340#ifdef TRIE_RATIONAL_TERMS
1341 term_array_free(&Ts);
1342#endif /* RATIONAL TERM SUPPORT FOR TRIES */
1343 *subs_arity_ptr = subs_arity;
1344 *stack_vars_ptr = stack_vars;
1345 return current_node;
1346}
1347#endif /* INCLUDE_SUBGOAL_SEARCH_LOOP */
1348
1349/************************************************************************
1350** answer_search(_global_trie)(_terms)_loop **
1351************************************************************************/
1352
1353#ifdef INCLUDE_ANSWER_SEARCH_LOOP
1354#ifdef MODE_GLOBAL_TRIE_LOOP
1355#ifdef GLOBAL_TRIE_FOR_SUBTERMS
1356static inline gt_node_ptr
1357answer_search_global_trie_terms_loop(Term t, int *vars_arity_ptr,
1358 CELL *stack_terms USES_REGS) {
1359#else
1360static inline gt_node_ptr
1361answer_search_global_trie_loop(Term t, int *vars_arity_ptr USES_REGS) {
1362#endif /* GLOBAL_TRIE_FOR_SUBTERMS */
1363#else
1364#ifdef MODE_TERMS_LOOP
1365static inline ans_node_ptr
1366answer_search_terms_loop(sg_fr_ptr sg_fr, ans_node_ptr current_node, Term t,
1367 int *vars_arity_ptr USES_REGS) {
1368#else
1369static inline ans_node_ptr answer_search_loop(sg_fr_ptr sg_fr,
1370 ans_node_ptr current_node, Term t,
1371 int *vars_arity_ptr USES_REGS) {
1372#endif /* MODE_TERMS_LOOP */
1373#endif /* MODE_GLOBAL_TRIE_LOOP */
1374/************************************************************************
1375 ===========
1376 | |
1377 | ... |
1378 | |
1379 -----------
1380 TR --> | VAR_0 | <-- stack_vars_base
1381 ----------- *
1382 | ... | /|\
1383 ----------- | vars_arity (N+1)
1384 | VAR_N | \|/
1385 ----------- *
1386 | | <-- stack_terms_limit
1387 -----------
1388 | |
1389 | ... |
1390 | |
1391 ----------|
1392 | TERM_N | <-- stack_terms
1393 ----------| *
1394 | ... | /|\
1395 ----------| |
1396 | TERM_1 | |
1397 ----------| |
1398 | NULL | \|/
1399 =========== *
1400 LOCAL_TrailTop --> | |
1401 -----------
1402************************************************************************/
1403#ifdef MODE_GLOBAL_TRIE_LOOP
1404 gt_node_ptr current_node = GLOBAL_root_gt;
1405#endif /* MODE_GLOBAL_TRIE_LOOP */
1406 int vars_arity = *vars_arity_ptr;
1407#if !defined(MODE_GLOBAL_TRIE_LOOP) || !defined(GLOBAL_TRIE_FOR_SUBTERMS)
1408 CELL *stack_terms = (CELL *)LOCAL_TrailTop;
1409#endif /* ! MODE_GLOBAL_TRIE_LOOP || ! GLOBAL_TRIE_FOR_SUBTERMS */
1410 CELL *stack_vars_base = (CELL *)TR;
1411#define stack_terms_limit (stack_vars_base + vars_arity)
1412#ifdef TRIE_COMPACT_PAIRS
1413 int in_pair = 0;
1414#else
1415#define in_pair 0
1416#endif /* TRIE_COMPACT_PAIRS */
1417 AUX_STACK_CHECK_EXPAND(
1418 stack_terms, stack_terms_limit + 1); /* + 1 because initially we stiil
1419 haven't done any STACK_POP_DOWN */
1420 STACK_PUSH_UP(NULL, stack_terms);
1421
1422#if defined(MODE_GLOBAL_TRIE_LOOP)
1423 /* for the global trie, it is safe to skip the IsVarTerm() and
1424 * IsAtomOrIntTerm() tests in the first iteration */
1425 goto answer_search_loop_non_atomic;
1426#endif /* MODE_GLOBAL_TRIE_LOOP */
1427
1428#ifdef TRIE_RATIONAL_TERMS
1429 term_array Ts;
1430 void *CyclicTerm;
1431 term_array_init(&Ts, 10);
1432#endif /* RATIONAL TERM SUPPORT FOR TRIES */
1433
1434 do {
1435 if (IsVarTerm(t)) {
1436 t = Deref(t);
1437 if (IsTableVarTerm(t)) {
1438 t = MakeTableVarTerm(VarIndexOfTerm(t));
1439 ANSWER_CHECK_INSERT_ENTRY(sg_fr, current_node, t,
1440 _trie_retry_val + in_pair);
1441 } else {
1442 if (vars_arity == MAX_TABLE_VARS)
1443 Yap_Error(SYSTEM_ERROR_INTERNAL, TermNil,
1444 "answer_search_loop: MAX_TABLE_VARS exceeded");
1445 stack_vars_base[vars_arity] = t;
1446 *((CELL *)t) = GLOBAL_table_var_enumerator(vars_arity);
1447 t = MakeTableVarTerm(vars_arity);
1448 ANSWER_CHECK_INSERT_ENTRY(sg_fr, current_node, t,
1449 _trie_retry_var + in_pair);
1450 vars_arity = vars_arity + 1;
1451 }
1452#ifdef TRIE_COMPACT_PAIRS
1453 in_pair = 0;
1454#endif /* TRIE_COMPACT_PAIRS */
1455 } else if (IsAtomOrIntTerm(t)) {
1456 ANSWER_CHECK_INSERT_ENTRY(sg_fr, current_node, t,
1457 _trie_retry_atom + in_pair);
1458#ifdef TRIE_COMPACT_PAIRS
1459 in_pair = 0;
1460#endif /* TRIE_COMPACT_PAIRS */
1461#ifdef MODE_TERMS_LOOP
1462 } else {
1463 gt_node_ptr entry_node;
1464#ifdef GLOBAL_TRIE_FOR_SUBTERMS
1465 entry_node = answer_search_global_trie_terms_loop(t, &vars_arity,
1466 stack_terms PASS_REGS);
1467#else
1468 entry_node = answer_search_global_trie_loop(t, &vars_arity PASS_REGS);
1469#endif /* GLOBAL_TRIE_FOR_SUBTERMS */
1470 current_node = answer_trie_check_insert_gt_entry(
1471 sg_fr, current_node, (Term)entry_node,
1472 _trie_retry_gterm + in_pair PASS_REGS);
1473#else /* ! MODE_TERMS_LOOP */
1474 } else
1475#ifdef TRIE_RATIONAL_TERMS
1476 if (IsRationalTerm(t)) {
1477 t = STACK_POP_DOWN(stack_terms);
1478 ANSWER_CHECK_INSERT_ENTRY(sg_fr, current_node, t,
1479 _trie_retry_var +
1480 in_pair); // TODO create _trie_.._rational
1481 } else
1482#endif /* RATIONAL TERM SUPPORT FOR TRIES */
1483#if defined(MODE_GLOBAL_TRIE_LOOP)
1484 /* for the global trie, it is safe to start here in the first iteration */
1485 answer_search_loop_non_atomic:
1486#endif /* MODE_GLOBAL_TRIE_LOOP */
1487#ifdef TRIE_COMPACT_PAIRS
1488 if (IsPairTerm(t)) {
1489#ifdef TRIE_RATIONAL_TERMS
1490 CyclicTerm = NULL;
1491#endif /* RATIONAL TERM SUPPORT FOR TRIES */
1492 CELL *aux_pair = RepPair(t);
1493 if (aux_pair == PairTermMark) {
1494 t = STACK_POP_DOWN(stack_terms);
1495#ifdef TRIE_RATIONAL_TERMS
1496 if (IsPairTerm(t) && !IsRationalTerm(t)) {
1497 term_array_push(&Ts, (void *)t, (void *)current_node);
1498#else
1499 if (IsPairTerm(t)) {
1500#endif /* RATIONAL TERM SUPPORT FOR TRIES */
1501 aux_pair = RepPair(t);
1502 t = Deref(aux_pair[1]);
1503#ifdef TRIE_RATIONAL_TERMS
1504 if (IsVarTerm(aux_pair[1]) || IsPairTerm(aux_pair[1])) {
1505 CyclicTerm = term_array_member(Ts, (void *)t);
1506 }
1507 if (CyclicTerm != NULL) {
1508 STACK_PUSH_UP((Term)CyclicTerm, stack_terms); // CyclicTerm
1509 STACK_PUSH_UP((Term)RationalMark, stack_terms);
1510 STACK_PUSH_UP(AbsPair(PairTermMark), stack_terms);
1511 in_pair = 4;
1512 } else
1513#endif /* RATIONAL TERM SUPPORT FOR TRIES */
1514 if (t == TermNil) {
1515 ANSWER_CHECK_INSERT_ENTRY(sg_fr, current_node, CompactPairEndList,
1516 _trie_retry_pair);
1517 } else {
1518 /* AUX_STACK_CHECK_EXPAND(stack_terms, stack_terms_limit + 2); */
1519 /* AUX_STACK_CHECK_EXPAND is not necessary here because the
1520 *situation of pushing **
1521 ** up 3 terms has already initially checked for the CompactPairInit
1522 *term */
1523 STACK_PUSH_UP(t, stack_terms);
1524 STACK_PUSH_UP(AbsPair(PairTermMark), stack_terms);
1525 in_pair = 4;
1526 }
1527#ifdef TRIE_RATIONAL_TERMS
1528 CyclicTerm = NULL;
1529 if (IsVarTerm(aux_pair[0]) || IsPairTerm(aux_pair[0]))
1530 CyclicTerm = term_array_member(Ts, (void *)Deref(aux_pair[0]));
1531 if (CyclicTerm != NULL) {
1532 STACK_PUSH_UP((Term)CyclicTerm, stack_terms);
1533 STACK_PUSH_UP((Term)RationalMark, stack_terms);
1534 } else
1535#endif /* RATIONAL TERM SUPPORT FOR TRIES */
1536 STACK_PUSH_UP(Deref(aux_pair[0]), stack_terms);
1537 } else {
1538 ANSWER_CHECK_INSERT_ENTRY(sg_fr, current_node, CompactPairEndTerm,
1539 _trie_retry_null);
1540 STACK_PUSH_UP(t, stack_terms);
1541 }
1542#if defined(MODE_GLOBAL_TRIE_LOOP) && defined(GLOBAL_TRIE_FOR_SUBTERMS)
1543 } else if (current_node != GLOBAL_root_gt) {
1544 gt_node_ptr entry_node = answer_search_global_trie_terms_loop(
1545 t, &vars_arity, stack_terms PASS_REGS);
1546 current_node = global_trie_check_insert_gt_entry(
1547 current_node, (Term)entry_node PASS_REGS);
1548#endif /* MODE_GLOBAL_TRIE_LOOP && GLOBAL_TRIE_FOR_SUBTERMS */
1549 } else {
1550#ifdef TRIE_RATIONAL_TERMS
1551 term_array_push(&Ts, (void *)t, (void *)current_node);
1552#endif /* RATIONAL TERM SUPPORT FOR TRIES */
1553 ANSWER_CHECK_INSERT_ENTRY(sg_fr, current_node, CompactPairInit,
1554 _trie_retry_null + in_pair);
1555 t = Deref(aux_pair[1]);
1556#ifdef TRIE_RATIONAL_TERMS
1557 if (IsVarTerm(aux_pair[1]) || IsPairTerm(aux_pair[1])) {
1558 CyclicTerm = term_array_member(Ts, (void *)t);
1559 }
1560 if (CyclicTerm != NULL) {
1561 STACK_PUSH_UP((Term)CyclicTerm, stack_terms);
1562 STACK_PUSH_UP((Term)RationalMark, stack_terms);
1563 STACK_PUSH_UP(AbsPair(PairTermMark), stack_terms);
1564 in_pair = 4;
1565 } else
1566#endif /* RATIONAL TERM SUPPORT FOR TRIES */
1567 if (t == TermNil) {
1568 ANSWER_CHECK_INSERT_ENTRY(sg_fr, current_node, CompactPairEndList,
1569 _trie_retry_pair);
1570 in_pair = 0;
1571 } else {
1572 AUX_STACK_CHECK_EXPAND(stack_terms, stack_terms_limit + 2);
1573 STACK_PUSH_UP(t, stack_terms);
1574 STACK_PUSH_UP(AbsPair(PairTermMark), stack_terms);
1575 in_pair = 4;
1576 }
1577#ifdef TRIE_RATIONAL_TERMS
1578 CyclicTerm = NULL;
1579 if (IsVarTerm(aux_pair[0]) || IsPairTerm(aux_pair[0]))
1580 CyclicTerm = term_array_member(Ts, (void *)Deref(aux_pair[0]));
1581 if (CyclicTerm != NULL) {
1582 STACK_PUSH_UP((Term)CyclicTerm, stack_terms);
1583 STACK_PUSH_UP((Term)RationalMark, stack_terms);
1584 } else
1585#endif /* RATIONAL TERM SUPPORT FOR TRIES */
1586 STACK_PUSH_UP(Deref(aux_pair[0]), stack_terms);
1587 }
1588#if defined(MODE_GLOBAL_TRIE_LOOP) && defined(GLOBAL_TRIE_FOR_SUBTERMS)
1589 } else if (current_node != GLOBAL_root_gt) {
1590 gt_node_ptr entry_node = answer_search_global_trie_terms_loop(
1591 t, &vars_arity, stack_terms PASS_REGS);
1592 current_node = global_trie_check_insert_gt_entry(
1593 current_node, (Term)entry_node PASS_REGS);
1594#endif /* MODE_GLOBAL_TRIE_LOOP && GLOBAL_TRIE_FOR_SUBTERMS */
1595#else /* ! TRIE_COMPACT_PAIRS */
1596#if defined(MODE_GLOBAL_TRIE_LOOP) && defined(GLOBAL_TRIE_FOR_SUBTERMS)
1597 if (current_node != GLOBAL_root_gt) {
1598 gt_node_ptr entry_node = answer_search_global_trie_terms_loop(
1599 t, &vars_arity, stack_terms PASS_REGS);
1600 current_node = global_trie_check_insert_gt_entry(
1601 current_node, (Term)entry_node PASS_REGS);
1602 } else
1603#endif /* MODE_GLOBAL_TRIE_LOOP && GLOBAL_TRIE_FOR_SUBTERMS */
1604 if (IsPairTerm(t)) {
1605 CELL *aux_pair = RepPair(t);
1606 ANSWER_CHECK_INSERT_ENTRY(sg_fr, current_node, AbsPair(NULL),
1607 _trie_retry_pair);
1608 AUX_STACK_CHECK_EXPAND(stack_terms, stack_terms_limit + 1);
1609 STACK_PUSH_UP(Deref(aux_pair[1]), stack_terms);
1610 STACK_PUSH_UP(Deref(aux_pair[0]), stack_terms);
1611#endif /* TRIE_COMPACT_PAIRS */
1612 } else if (IsApplTerm(t)) {
1613 Functor f = FunctorOfTerm(t);
1614 if (f == FunctorDouble) {
1615 union {
1616 Term t_dbl[sizeof(Float) / sizeof(Term)];
1617 Float dbl;
1618 } u;
1619 u.dbl = FloatOfTerm(t);
1620 ANSWER_CHECK_INSERT_ENTRY(sg_fr, current_node, AbsAppl((Term *)f),
1621 _trie_retry_null + in_pair);
1622#if SIZEOF_DOUBLE == 2 * SIZEOF_INT_P
1623 ANSWER_CHECK_INSERT_ENTRY(sg_fr, current_node, u.t_dbl[1],
1624 _trie_retry_extension);
1625#endif /* SIZEOF_DOUBLE x SIZEOF_INT_P */
1626 ANSWER_CHECK_INSERT_ENTRY(sg_fr, current_node, u.t_dbl[0],
1627 _trie_retry_extension);
1628 ANSWER_CHECK_INSERT_ENTRY(sg_fr, current_node, AbsAppl((Term *)f),
1629 _trie_retry_double);
1630 } else if (f == FunctorLongInt) {
1631 Int li = LongIntOfTerm(t);
1632 ANSWER_CHECK_INSERT_ENTRY(sg_fr, current_node, AbsAppl((Term *)f),
1633 _trie_retry_null + in_pair);
1634 ANSWER_CHECK_INSERT_ENTRY(sg_fr, current_node, li,
1635 _trie_retry_extension);
1636 ANSWER_CHECK_INSERT_ENTRY(sg_fr, current_node, AbsAppl((Term *)f),
1637 _trie_retry_longint);
1638 } else if (f == FunctorBigInt || f == FunctorString) {
1639 CELL *opq = Yap_HeapStoreOpaqueTerm(t);
1640 ANSWER_CHECK_INSERT_ENTRY(sg_fr, current_node, AbsAppl((Term *)f),
1641 _trie_retry_null + in_pair);
1642 ANSWER_CHECK_INSERT_ENTRY(sg_fr, current_node, (CELL)opq,
1643 _trie_retry_extension);
1644 ANSWER_CHECK_INSERT_ENTRY(sg_fr, current_node, AbsAppl((Term *)f),
1645 _trie_retry_bigint);
1646 } else if (f == FunctorDBRef) {
1647 Yap_Error(SYSTEM_ERROR_INTERNAL, TermNil,
1648 "answer_search_loop: unsupported type tag FunctorDBRef");
1649 } else {
1650#ifdef TRIE_RATIONAL_TERMS
1651 term_array_push(&Ts, (void *)t, (void *)current_node);
1652#endif /* RATIONAL TERM SUPPORT FOR TRIES */
1653 int i;
1654 CELL *aux_appl = RepAppl(t);
1655 ANSWER_CHECK_INSERT_ENTRY(sg_fr, current_node, AbsAppl((Term *)f),
1656 _trie_retry_appl + in_pair);
1657 AUX_STACK_CHECK_EXPAND(stack_terms,
1658 stack_terms_limit + ArityOfFunctor(f) - 1);
1659 for (i = ArityOfFunctor(f); i >= 1; i--) {
1660#ifdef TRIE_RATIONAL_TERMS
1661 CyclicTerm = NULL;
1662 if (IsVarTerm(aux_appl[i]) || IsApplTerm(aux_appl[i]))
1663 CyclicTerm = term_array_member(Ts, (void *)Deref(aux_appl[i]));
1664 if (CyclicTerm != NULL) {
1665 STACK_PUSH_UP((Term)CyclicTerm, stack_terms);
1666 STACK_PUSH_UP((Term)RationalMark, stack_terms);
1667 } else
1668#endif /* RATIONAL TERM SUPPORT FOR TRIES */
1669 STACK_PUSH_UP(Deref(aux_appl[i]), stack_terms);
1670 }
1671 }
1672#ifdef TRIE_COMPACT_PAIRS
1673 in_pair = 0;
1674#endif /* TRIE_COMPACT_PAIRS */
1675 } else {
1676 Yap_Error(SYSTEM_ERROR_INTERNAL, TermNil,
1677 "answer_search_loop: unknown type tag");
1678#endif /* MODE_TERMS_LOOP */
1679 }
1680 t = STACK_POP_DOWN(stack_terms);
1681 } while (t);
1682#ifdef TRIE_RATIONAL_TERMS
1683 term_array_free(&Ts);
1684#endif /* RATIONAL TERM SUPPORT FOR TRIES */
1685 *vars_arity_ptr = vars_arity;
1686 return current_node;
1687
1688#undef stack_terms_limit
1689#ifndef TRIE_COMPACT_PAIRS
1690#undef in_pair
1691#endif /* TRIE_COMPACT_PAIRS */
1692}
1693#endif /* INCLUDE_ANSWER_SEARCH_LOOP */
1694
1695/**************************************************************
1696** answer_search_min_max **
1697**************************************************************/
1698
1699#ifdef INCLUDE_ANSWER_SEARCH_MODE_DIRECTED
1700static inline ans_node_ptr answer_search_min_max(sg_fr_ptr sg_fr,
1701 ans_node_ptr current_node,
1702 Term t, int mode USES_REGS) {
1703 ans_node_ptr child_node;
1704 Term child_term;
1705 Term trie_value = 0, term_value = t;
1706 int cmp;
1707
1708 /* start by computing the current value on the trie (trie_value) */
1709 child_node = TrNode_child(current_node);
1710 child_term = TrNode_entry(child_node);
1711 if (IsIntTerm(child_term)) {
1712 trie_value = child_term;
1713 } else if (IsApplTerm(child_term)) {
1714 Functor f = (Functor)RepAppl(child_term);
1715 child_node = TrNode_child(child_node);
1716 if (f == FunctorLongInt) {
1717 trie_value = MkLongIntTerm((Int)TrNode_entry(child_node));
1718 } else if (f == FunctorDouble) {
1719 union {
1720 Term t_dbl[sizeof(Float) / sizeof(Term)];
1721 Float dbl;
1722 } u;
1723 u.t_dbl[0] = TrNode_entry(child_node);
1724#if SIZEOF_DOUBLE == 2 * SIZEOF_INT_P
1725 child_node = TrNode_child(child_node);
1726 u.t_dbl[1] = TrNode_entry(child_node);
1727#endif /* SIZEOF_DOUBLE x SIZEOF_INT_P */
1728 trie_value = MkFloatTerm(u.dbl);
1729 } else if (f == FunctorBigInt) {
1730 trie_value = AbsAppl((CELL *)TrNode_entry(child_node));
1731 } else
1732 Yap_Error(SYSTEM_ERROR_INTERNAL, TermNil,
1733 "answer_search_min_max: invalid arithmetic value");
1734 child_node = TrNode_child(child_node);
1735 }
1736
1737 cmp = Yap_acmp(term_value, trie_value PASS_REGS);
1738 /* worse answer */
1739 if ((mode == MODE_DIRECTED_MIN && cmp > 0) ||
1740 (mode == MODE_DIRECTED_MAX && cmp < 0))
1741 return NULL;
1742 /* equal answer */
1743 if (cmp == 0)
1744 return child_node;
1745 /* better answer */
1746 if (IsAtomOrIntTerm(t)) {
1747 ANSWER_SAFE_INSERT_ENTRY(current_node, t, _trie_retry_atom);
1748 } else if (IsApplTerm(t)) {
1749 Functor f = FunctorOfTerm(t);
1750 if (f == FunctorDouble) {
1751 union {
1752 Term t_dbl[sizeof(Float) / sizeof(Term)];
1753 Float dbl;
1754 } u;
1755 u.dbl = FloatOfTerm(t);
1756 ANSWER_SAFE_INSERT_ENTRY(current_node, AbsAppl((Term *)f),
1757 _trie_retry_null);
1758#if SIZEOF_DOUBLE == 2 * SIZEOF_INT_P
1759 ANSWER_SAFE_INSERT_ENTRY(current_node, u.t_dbl[1], _trie_retry_extension);
1760#endif /* SIZEOF_DOUBLE x SIZEOF_INT_P */
1761 ANSWER_SAFE_INSERT_ENTRY(current_node, u.t_dbl[0], _trie_retry_extension);
1762 ANSWER_SAFE_INSERT_ENTRY(current_node, AbsAppl((Term *)f),
1763 _trie_retry_double);
1764 } else if (f == FunctorLongInt) {
1765 Int li = LongIntOfTerm(t);
1766 ANSWER_SAFE_INSERT_ENTRY(current_node, AbsAppl((Term *)f),
1767 _trie_retry_null);
1768 ANSWER_SAFE_INSERT_ENTRY(current_node, li, _trie_retry_extension);
1769 ANSWER_SAFE_INSERT_ENTRY(current_node, AbsAppl((Term *)f),
1770 _trie_retry_longint);
1771 } else if (f == FunctorBigInt) {
1772 CELL *li = Yap_HeapStoreOpaqueTerm(t);
1773 ANSWER_SAFE_INSERT_ENTRY(current_node, AbsAppl((Term *)f),
1774 _trie_retry_null);
1775 ANSWER_SAFE_INSERT_ENTRY(current_node, (CELL)li, _trie_retry_extension);
1776 ANSWER_SAFE_INSERT_ENTRY(current_node, AbsAppl((Term *)f),
1777 _trie_retry_bigint);
1778 }
1779 }
1780 return current_node;
1781}
1782#endif /* INCLUDE_ANSWER_SEARCH_MODE_DIRECTED */
1783
1784/**********************************************************
1785** answer_search_sum **
1786**********************************************************/
1787
1788#ifdef INCLUDE_ANSWER_SEARCH_MODE_DIRECTED
1789static inline ans_node_ptr answer_search_sum(sg_fr_ptr sg_fr,
1790 ans_node_ptr current_node,
1791 Term t USES_REGS) {
1792 ans_node_ptr child_node;
1793 Term child_term;
1794 Term trie_value = 0, term_value = t, sum_value = 0;
1795
1796 /* start by computing the current value on the trie (trie_value) */
1797 child_node = TrNode_child(current_node);
1798 child_term = TrNode_entry(child_node);
1799 if (IsIntTerm(child_term)) {
1800 trie_value = child_term;
1801 } else if (IsApplTerm(child_term)) {
1802 Functor f = (Functor)RepAppl(child_term);
1803 child_node = TrNode_child(child_node);
1804 if (f == FunctorLongInt) {
1805 trie_value = MkLongIntTerm((Int)TrNode_entry(child_node));
1806 } else if (f == FunctorDouble) {
1807 union {
1808 Term t_dbl[sizeof(Float) / sizeof(Term)];
1809 Float dbl;
1810 } u;
1811 u.t_dbl[0] = TrNode_entry(child_node);
1812#if SIZEOF_DOUBLE == 2 * SIZEOF_INT_P
1813 child_node = TrNode_child(child_node);
1814 u.t_dbl[1] = TrNode_entry(child_node);
1815#endif /* SIZEOF_DOUBLE x SIZEOF_INT_P */
1816 trie_value = MkFloatTerm(u.dbl);
1817 } else if (f == FunctorBigInt) {
1818 trie_value = AbsAppl((CELL *)TrNode_entry(child_node));
1819 } else
1820 Yap_Error(SYSTEM_ERROR_INTERNAL, TermNil,
1821 "answer_search_min_max: invalid arithmetic value");
1822 child_node = TrNode_child(child_node);
1823 }
1824
1825 sum_value = p_plus(trie_value, term_value PASS_REGS);
1826 if (IsAtomOrIntTerm(sum_value)) {
1827 ANSWER_SAFE_INSERT_ENTRY(current_node, sum_value, _trie_retry_atom);
1828 } else if (IsApplTerm(sum_value)) {
1829 Functor f = FunctorOfTerm(sum_value);
1830 if (f == FunctorDouble) {
1831 union {
1832 Term t_dbl[sizeof(Float) / sizeof(Term)];
1833 Float dbl;
1834 } u;
1835 u.dbl = FloatOfTerm(sum_value);
1836 ANSWER_SAFE_INSERT_ENTRY(current_node, AbsAppl((Term *)f),
1837 _trie_retry_null);
1838#if SIZEOF_DOUBLE == 2 * SIZEOF_INT_P
1839 ANSWER_SAFE_INSERT_ENTRY(current_node, u.t_dbl[1], _trie_retry_extension);
1840#endif /* SIZEOF_DOUBLE x SIZEOF_INT_P */
1841 ANSWER_SAFE_INSERT_ENTRY(current_node, u.t_dbl[0], _trie_retry_extension);
1842 ANSWER_SAFE_INSERT_ENTRY(current_node, AbsAppl((Term *)f),
1843 _trie_retry_double);
1844 } else if (f == FunctorLongInt) {
1845 Int li = LongIntOfTerm(sum_value);
1846 ANSWER_SAFE_INSERT_ENTRY(current_node, AbsAppl((Term *)f),
1847 _trie_retry_null);
1848 ANSWER_SAFE_INSERT_ENTRY(current_node, li, _trie_retry_extension);
1849 ANSWER_SAFE_INSERT_ENTRY(current_node, AbsAppl((Term *)f),
1850 _trie_retry_longint);
1851 } else if (f == FunctorBigInt) {
1852 CELL *li = Yap_HeapStoreOpaqueTerm(sum_value);
1853 ANSWER_SAFE_INSERT_ENTRY(current_node, AbsAppl((Term *)f),
1854 _trie_retry_null);
1855 ANSWER_SAFE_INSERT_ENTRY(current_node, (CELL)li, _trie_retry_extension);
1856 ANSWER_SAFE_INSERT_ENTRY(current_node, AbsAppl((Term *)f),
1857 _trie_retry_bigint);
1858 }
1859 }
1860 return current_node;
1861}
1862#endif /* INCLUDE_ANSWER_SEARCH_MODE_DIRECTED */
1863
1864/***************************************************************
1865** invalidate_answer_trie **
1866***************************************************************/
1867
1868#ifdef INCLUDE_ANSWER_SEARCH_MODE_DIRECTED
1869static void invalidate_answer_trie(ans_node_ptr current_node, sg_fr_ptr sg_fr,
1870 int position USES_REGS) {
1871 if (IS_ANSWER_TRIE_HASH(current_node)) {
1872 ans_hash_ptr hash;
1873 ans_node_ptr *bucket, *last_bucket;
1874 hash = (ans_hash_ptr)current_node;
1875 bucket = Hash_buckets(hash);
1876 last_bucket = bucket + Hash_num_buckets(hash);
1877 do {
1878 current_node = *bucket;
1879 if (current_node) {
1880 ans_node_ptr next_node = TrNode_next(current_node);
1881 if (IS_ANSWER_LEAF_NODE(current_node)) {
1882 INVALIDATE_ANSWER_TRIE_LEAF_NODE(current_node, sg_fr);
1883 } else {
1884 invalidate_answer_trie(TrNode_child(current_node), sg_fr,
1885 TRAVERSE_POSITION_FIRST PASS_REGS);
1886 INVALIDATE_ANSWER_TRIE_NODE(current_node, sg_fr);
1887 }
1888 while (next_node) {
1889 current_node = next_node;
1890 next_node = TrNode_next(current_node);
1891 invalidate_answer_trie(current_node, sg_fr,
1892 TRAVERSE_POSITION_NEXT PASS_REGS);
1893 }
1894 }
1895 } while (++bucket != last_bucket);
1896 if (Hash_next(hash))
1897 Hash_previous(Hash_next(hash)) = Hash_previous(hash);
1898 if (Hash_previous(hash))
1899 Hash_next(Hash_previous(hash)) = Hash_next(hash);
1900 else
1901 SgFr_hash_chain(sg_fr) = Hash_next(hash);
1902 FREE_BUCKETS(Hash_buckets(hash));
1903 FREE_ANSWER_TRIE_HASH(hash);
1904 } else {
1905 if (position == TRAVERSE_POSITION_FIRST) {
1906 ans_node_ptr next_node = TrNode_next(current_node);
1907 if (IS_ANSWER_LEAF_NODE(current_node)) {
1908 INVALIDATE_ANSWER_TRIE_LEAF_NODE(current_node, sg_fr);
1909 } else {
1910 invalidate_answer_trie(TrNode_child(current_node), sg_fr,
1911 TRAVERSE_POSITION_FIRST PASS_REGS);
1912 INVALIDATE_ANSWER_TRIE_NODE(current_node, sg_fr);
1913 }
1914 while (next_node) {
1915 current_node = next_node;
1916 next_node = TrNode_next(current_node);
1917 invalidate_answer_trie(current_node, sg_fr,
1918 TRAVERSE_POSITION_NEXT PASS_REGS);
1919 }
1920 } else {
1921 if (IS_ANSWER_LEAF_NODE(current_node)) {
1922 INVALIDATE_ANSWER_TRIE_LEAF_NODE(current_node, sg_fr);
1923 } else {
1924 invalidate_answer_trie(TrNode_child(current_node), sg_fr,
1925 TRAVERSE_POSITION_FIRST PASS_REGS);
1926 INVALIDATE_ANSWER_TRIE_NODE(current_node, sg_fr);
1927 }
1928 }
1929 }
1930 return;
1931}
1932#endif /* INCLUDE_ANSWER_SEARCH_MODE_DIRECTED */
1933
1934/************************************************************************
1935** load_(answer|substitution)_loop **
1936************************************************************************/
1937
1938#ifdef INCLUDE_LOAD_ANSWER_LOOP
1939#ifdef MODE_GLOBAL_TRIE_LOOP
1940static inline CELL *load_substitution_loop(gt_node_ptr current_node,
1941 int *vars_arity_ptr,
1942 CELL *stack_terms USES_REGS) {
1943#else
1944static inline CELL *load_answer_loop(ans_node_ptr current_node USES_REGS) {
1945#endif /* MODE_GLOBAL_TRIE_LOOP */
1946/************************************************************************
1947 ===========
1948 | |
1949 | ... |
1950 | |
1951 -----------
1952 TR --> | VAR_0 | <-- stack_vars_base
1953 ----------- *
1954 | ... | /|\
1955 ----------- | vars_arity (N+1)
1956 | VAR_N | \|/
1957 ----------- *
1958 | | <-- stack_terms_limit
1959 -----------
1960 | |
1961 | ... |
1962 | |
1963 ----------|
1964 | TERM_N | <-- stack_terms
1965 ----------| *
1966 | ... | /|\
1967 ----------| | stack_terms_pair_offset
1968(TRIE_COMPACT_PAIRS)
1969 | TERM_1 | \|/
1970 =========== *
1971 LOCAL_TrailTop --> | | <-- stack_terms_base (TRIE_COMPACT_PAIRS)
1972 -----------
1973************************************************************************/
1974#ifdef MODE_GLOBAL_TRIE_LOOP
1975 int vars_arity = *vars_arity_ptr;
1976#else
1977 int vars_arity = 0;
1978 CELL *stack_terms = (CELL *)LOCAL_TrailTop;
1979#endif /* MODE_GLOBAL_TRIE_LOOP */
1980 CELL *stack_vars_base = (CELL *)TR;
1981#define stack_terms_limit (stack_vars_base + vars_arity)
1982#ifdef TRIE_COMPACT_PAIRS
1983#define stack_terms_base ((CELL *)LOCAL_TrailTop)
1984 int stack_terms_pair_offset = 0;
1985#endif /* TRIE_COMPACT_PAIRS */
1986 Term t = TrNode_entry(current_node);
1987#ifdef MODE_GLOBAL_TRIE_LOOP
1988 current_node = TrNode_parent(current_node);
1989#else
1990 current_node = (ans_node_ptr)UNTAG_ANSWER_NODE(TrNode_parent(current_node));
1991#endif /* MODE_GLOBAL_TRIE_LOOP */
1992
1993#ifdef TRIE_RATIONAL_TERMS
1994 term_array Ts;
1995 void *CyclicTerm;
1996 term_array_init(&Ts, 10);
1997 Term RationalTermTMP; // a temporary temp to be used from the rational code
1998#endif /* RATIONAL TERM SUPPORT FOR TRIES */
1999
2000 do {
2001#ifdef TRIE_RATIONAL_TERMS
2002 CyclicTerm = term_array_member(Ts, (void *)current_node);
2003#endif /* RATIONAL TERM SUPPORT FOR TRIES */
2004 if (IsVarTerm(t)) {
2005#ifdef TRIE_RATIONAL_TERMS
2006 if (t > VarIndexOfTableTerm(MAX_TABLE_VARS) &&
2007 TrNode_child((gt_node_ptr)t) !=
2008 (gt_node_ptr)(1)) { // TODO: substitute the != 1 test to something
2009 // more appropriate
2010 /* Rational term */
2011 RationalTermTMP = (Term)term_array_member(Ts, (void *)t);
2012 if (RationalTermTMP) {
2013 /* rational term is assigned a variable already */
2014 AUX_STACK_CHECK_EXPAND(stack_terms, stack_terms_limit);
2015 STACK_PUSH_UP(RationalTermTMP, stack_terms);
2016 } else {
2017 RationalTermTMP = MkVarTerm();
2018 STACK_PUSH_UP(RationalTermTMP, stack_terms);
2019 /* memorize the rational term and assign it a variable */
2020 term_array_push(&Ts, (void *)t, (void *)RationalTermTMP);
2021 }
2022 } else
2023#endif /* RATIONAL TERM SUPPORT FOR TRIES */
2024 {
2025#if !defined(MODE_GLOBAL_TRIE_LOOP) || defined(GLOBAL_TRIE_FOR_SUBTERMS)
2026 if (t > VarIndexOfTableTerm(MAX_TABLE_VARS)) {
2027 stack_terms = load_substitution_loop((gt_node_ptr)t, &vars_arity,
2028 stack_terms PASS_REGS);
2029 } else
2030#endif /* ! MODE_GLOBAL_TRIE_LOOP || GLOBAL_TRIE_FOR_SUBTERMS */
2031 {
2032 int var_index = VarIndexOfTableTerm(t);
2033 AUX_STACK_CHECK_EXPAND(stack_terms, stack_terms_limit - vars_arity +
2034 var_index + 1);
2035 if (var_index >= vars_arity) {
2036 while (vars_arity < var_index)
2037 stack_vars_base[vars_arity++] = 0;
2038 stack_vars_base[vars_arity++] = MkVarTerm();
2039 } else if (stack_vars_base[var_index] == 0)
2040 stack_vars_base[var_index] = MkVarTerm();
2041 STACK_PUSH_UP(stack_vars_base[var_index], stack_terms);
2042 }
2043 }
2044 } else if (IsAtomOrIntTerm(t)) {
2045 AUX_STACK_CHECK_EXPAND(stack_terms, stack_terms_limit);
2046#ifdef TRIE_RATIONAL_TERMS
2047 if (CyclicTerm) {
2048 AUX_STACK_CHECK_EXPAND(stack_terms, stack_terms_limit + 4);
2049 STACK_PUSH_UP((Term)RationalMark, stack_terms); // Add a rational term
2050 // marker necessary as
2051 // we read both ways the
2052 // stack //
2053 STACK_PUSH_UP(t, stack_terms); // Add the term //
2054 STACK_PUSH_UP(
2055 CyclicTerm,
2056 stack_terms); // Add the variable that the term will unify with //
2057 STACK_PUSH_UP((Term)RationalMark, stack_terms); // Add a rational term
2058 // marker necessary as
2059 // we read both ways the
2060 // stack //
2061 } else
2062#endif /* RATIONAL TERM SUPPORT FOR TRIES */
2063 STACK_PUSH_UP(t, stack_terms);
2064 } else if (IsPairTerm(t)) {
2065#ifdef TRIE_COMPACT_PAIRS
2066 if (t == CompactPairInit) {
2067 Term *stack_aux = stack_terms_base - stack_terms_pair_offset;
2068 Term head, tail = STACK_POP_UP(stack_aux);
2069#ifdef TRIE_RATIONAL_TERMS
2070 if (IsRationalTerm(tail)) {
2071 Yap_Error(SYSTEM_ERROR_INTERNAL, tail, "Rational element of a "
2072 "Rational Term appears as the "
2073 "first Tail of a list");
2074 }
2075#endif /* RATIONAL TERM SUPPORT FOR TRIES */
2076 while (STACK_NOT_EMPTY(stack_aux, stack_terms)) {
2077 head = STACK_POP_UP(stack_aux);
2078#ifdef TRIE_RATIONAL_TERMS
2079 if (IsRationalTerm(head)) {
2080 head = STACK_POP_UP(stack_aux); // thats the rational term
2081 RationalTermTMP =
2082 STACK_POP_UP(stack_aux); // that is the variable to unify with
2083 (void)STACK_POP_UP(stack_aux); // eat the second rational mark
2084 tail = MkPairTerm(head, tail);
2085 Yap_unify(RationalTermTMP, tail);
2086 } else
2087#endif /* RATIONAL TERM SUPPORT FOR TRIES */
2088 tail = MkPairTerm(head, tail);
2089 }
2090 stack_terms = stack_terms_base - stack_terms_pair_offset;
2091 stack_terms_pair_offset = (int)STACK_POP_DOWN(stack_terms);
2092 STACK_PUSH_UP(tail, stack_terms);
2093 } else { /* CompactPairEndList / CompactPairEndTerm */
2094 Term last;
2095 AUX_STACK_CHECK_EXPAND(stack_terms, stack_terms_limit + 1);
2096 last = STACK_POP_DOWN(stack_terms);
2097#ifdef TRIE_RATIONAL_TERMS
2098 RationalTermTMP = TermNil;
2099 if (IsRationalTerm(last)) { // rather unlikely case the rational term is
2100 // the last of a list
2101 RationalTermTMP = STACK_POP_DOWN(stack_terms); // in this case we need
2102 // to invert the term
2103 // with the end of list
2104 last = STACK_POP_DOWN(stack_terms); // variable to unify with
2105 (void)STACK_POP_DOWN(stack_terms); // eat the second rational mark
2106 }
2107#endif /* RATIONAL TERM SUPPORT FOR TRIES */
2108 STACK_PUSH_UP(stack_terms_pair_offset, stack_terms);
2109 stack_terms_pair_offset = (int)(stack_terms_base - stack_terms);
2110 if (t == CompactPairEndList)
2111 STACK_PUSH_UP(TermNil, stack_terms);
2112#ifdef TRIE_RATIONAL_TERMS
2113 if (RationalTermTMP && RationalTermTMP != TermNil) {
2114 /* most probably this never occurs */
2115 STACK_PUSH_UP((Term)RationalMark, stack_terms);
2116 STACK_PUSH_UP(last, stack_terms);
2117 STACK_PUSH_UP(RationalTermTMP, stack_terms);
2118 STACK_PUSH_UP((Term)RationalMark, stack_terms);
2119 } else
2120#endif /* RATIONAL TERM SUPPORT FOR TRIES */
2121 STACK_PUSH_UP(last, stack_terms);
2122 }
2123#else /* ! TRIE_COMPACT_PAIRS */
2124 Term head = STACK_POP_DOWN(stack_terms);
2125 Term tail = STACK_POP_DOWN(stack_terms);
2126 t = MkPairTerm(head, tail);
2127 STACK_PUSH_UP(t, stack_terms);
2128#endif /* TRIE_COMPACT_PAIRS */
2129 } else if (IsApplTerm(t)) {
2130 Functor f = (Functor)RepAppl(t);
2131 if (f == FunctorDouble) {
2132 union {
2133 Term t_dbl[sizeof(Float) / sizeof(Term)];
2134 Float dbl;
2135 } u;
2136 t = TrNode_entry(current_node);
2137 current_node = TrNode_parent(current_node);
2138 u.t_dbl[0] = t;
2139#if SIZEOF_DOUBLE == 2 * SIZEOF_INT_P
2140 t = TrNode_entry(current_node);
2141 current_node = TrNode_parent(current_node);
2142 u.t_dbl[1] = t;
2143#endif /* SIZEOF_DOUBLE x SIZEOF_INT_P */
2144 current_node = TrNode_parent(current_node);
2145 t = MkFloatTerm(u.dbl);
2146 } else if (f == FunctorLongInt) {
2147 Int li = TrNode_entry(current_node);
2148 current_node = TrNode_parent(current_node);
2149 current_node = TrNode_parent(current_node);
2150 t = MkLongIntTerm(li);
2151 } else if (f == FunctorBigInt || f == FunctorString) {
2152 CELL *ptr = (CELL *)TrNode_entry(current_node);
2153 current_node = TrNode_parent(current_node);
2154 current_node = TrNode_parent(current_node);
2155 t = AbsAppl(ptr);
2156 } else {
2157 int f_arity = ArityOfFunctor(f);
2158 t = Yap_MkApplTerm(f, f_arity, stack_terms);
2159 stack_terms += f_arity;
2160 }
2161 AUX_STACK_CHECK_EXPAND(stack_terms, stack_terms_limit);
2162 STACK_PUSH_UP(t, stack_terms);
2163 }
2164#ifdef TRIE_RATIONAL_TERMS
2165 if (CyclicTerm) {
2166 RationalTermTMP = STACK_POP_DOWN(stack_terms);
2167 if
2168 IsRationalTerm(RationalTermTMP) {
2169 // printf("Special Case\n");
2170 }
2171 else if (IsPairTerm(RationalTermTMP)) {
2172 Yap_unify((Term)CyclicTerm, RationalTermTMP);
2173 } else if (IsApplTerm(RationalTermTMP)) {
2174 Yap_unify((Term)CyclicTerm, RationalTermTMP);
2175 }
2176 STACK_PUSH_UP(RationalTermTMP, stack_terms);
2177 }
2178 RationalTermTMP = TermNil;
2179 CyclicTerm = NULL;
2180#endif /* RATIONAL TERM SUPPORT FOR TRIES */
2181 t = TrNode_entry(current_node);
2182 current_node = TrNode_parent(current_node);
2183 } while (current_node);
2184#ifdef TRIE_RATIONAL_TERMS
2185 term_array_free(&Ts);
2186#endif /* RATIONAL TERM SUPPORT FOR TRIES */
2187#ifdef MODE_GLOBAL_TRIE_LOOP
2188 *vars_arity_ptr = vars_arity;
2189#endif /* MODE_GLOBAL_TRIE_LOOP */
2190 return stack_terms;
2191
2192#undef stack_terms_limit
2193#ifdef TRIE_COMPACT_PAIRS
2194#undef stack_terms_base
2195#endif /* TRIE_COMPACT_PAIRS */
2196}
2197#endif /* INCLUDE_LOAD_ANSWER_LOOP */
2198
2199/***************************
2200** Undef Macros **
2201***************************/
2202
2203#undef INCREMENT_GLOBAL_TRIE_REFERENCE
2204#undef NEW_SUBGOAL_TRIE_NODE
2205#undef NEW_ANSWER_TRIE_NODE
2206#undef NEW_GLOBAL_TRIE_NODE
2207#undef SUBGOAL_CHECK_INSERT_ENTRY
2208#undef ANSWER_CHECK_INSERT_ENTRY
answer_trie_hash
Definition: tab.structs.h:140
answer_trie_node
Definition: tab.structs.h:70
bucket
Definition: hash.h:40
global_trie_hash
Definition: tab.structs.h:153
global_trie_node
Definition: tab.structs.h:84
subgoal_frame
Definition: tab.structs.h:296
subgoal_trie_hash
Definition: tab.structs.h:128
subgoal_trie_node
Definition: tab.structs.h:60
table_entry
Definition: tab.structs.h:22
term_array
Definition: tab.rational.h:17