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 ** Includes & Prototypes **
16 ************************************/
17
18 #include <stdlib.h>
19 #if HAVE_STRING_H
20 #include <string.h>
21 #endif /* HAVE_STRING_H */
22 #include "opt.mavar.h"
23
24 static inline Int freeze_current_cp(void);
25 static inline void wake_frozen_cp(Int);
26 static inline void abolish_frozen_cps_until(Int);
27 static inline void abolish_frozen_cps_all(void);
28 static inline void adjust_freeze_registers(void);
29 static inline void mark_as_completed(sg_fr_ptr);
30 static inline void unbind_variables(tr_fr_ptr, tr_fr_ptr);
31 static inline void rebind_variables(tr_fr_ptr, tr_fr_ptr);
32 static inline void restore_bindings(tr_fr_ptr, tr_fr_ptr);
33 static inline CELL *expand_auxiliary_stack(CELL *);
34 static inline void abolish_incomplete_subgoals(choiceptr);
35 #ifdef YAPOR
36 static inline void pruning_over_tabling_data_structures(void);
37 static inline void collect_suspension_frames(or_fr_ptr);
38 #ifdef TIMESTAMP_CHECK
39 static inline susp_fr_ptr suspension_frame_to_resume(or_fr_ptr, long);
40 #else
41 static inline susp_fr_ptr suspension_frame_to_resume(or_fr_ptr);
42 #endif /* TIMESTAMP_CHECK */
43 #endif /* YAPOR */
44 #ifdef TABLING_INNER_CUTS
45 static inline void CUT_store_tg_answer(or_fr_ptr, ans_node_ptr, choiceptr, int);
46 static inline tg_sol_fr_ptr CUT_store_tg_answers(or_fr_ptr, tg_sol_fr_ptr, int);
47 static inline void CUT_validate_tg_answers(tg_sol_fr_ptr);
48 static inline void CUT_join_tg_solutions(tg_sol_fr_ptr *, tg_sol_fr_ptr);
49 static inline void CUT_join_solution_frame_tg_answers(tg_sol_fr_ptr);
50 static inline void CUT_join_solution_frames_tg_answers(tg_sol_fr_ptr);
51 static inline void CUT_free_tg_solution_frame(tg_sol_fr_ptr);
52 static inline void CUT_free_tg_solution_frames(tg_sol_fr_ptr);
53 static inline tg_sol_fr_ptr CUT_prune_tg_solution_frames(tg_sol_fr_ptr, int);
54 #endif /* TABLING_INNER_CUTS */
55
56
57
58 /*********************************
59 ** Tabling mode flags **
60 *********************************/
61
62 #define Flag_Batched 0x001
63 #define Flag_Local 0x002
64 #define Flags_SchedulingMode (Flag_Batched | Flag_Local)
65 #define Flag_ExecAnswers 0x010
66 #define Flag_LoadAnswers 0x020
67 #define Flags_AnswersMode (Flag_ExecAnswers | Flag_LoadAnswers)
68 #define Flag_LocalTrie 0x100
69 #define Flag_GlobalTrie 0x200
70 #define Flags_TrieMode (Flag_LocalTrie | Flag_GlobalTrie)
71
72 #define SetMode_Batched(X) (X) = ((X) & ~Flags_SchedulingMode) | Flag_Batched
73 #define SetMode_Local(X) (X) = ((X) & ~Flags_SchedulingMode) | Flag_Local
74 #define SetMode_ExecAnswers(X) (X) = ((X) & ~Flags_AnswersMode) | Flag_ExecAnswers
75 #define SetMode_LoadAnswers(X) (X) = ((X) & ~Flags_AnswersMode) | Flag_LoadAnswers
76 #define SetMode_LocalTrie(X) (X) = ((X) & ~Flags_TrieMode) | Flag_LocalTrie
77 #define SetMode_GlobalTrie(X) (X) = ((X) & ~Flags_TrieMode) | Flag_GlobalTrie
78 #define IsMode_Batched(X) ((X) & Flag_Batched)
79 #define IsMode_Local(X) ((X) & Flag_Local)
80 #define IsMode_ExecAnswers(X) ((X) & Flag_ExecAnswers)
81 #define IsMode_LoadAnswers(X) ((X) & Flag_LoadAnswers)
82 #define IsMode_LocalTrie(X) ((X) & Flag_LocalTrie)
83 #define IsMode_GlobalTrie(X) ((X) & Flag_GlobalTrie)
84
85
86
87 /******************************
88 ** Tabling defines **
89 ******************************/
90
91 #define SHOW_MODE_STRUCTURE 0
92 #define SHOW_MODE_STATISTICS 1
93 #define TRAVERSE_MODE_NORMAL 0
94 #define TRAVERSE_MODE_DOUBLE 1
95 #define TRAVERSE_MODE_DOUBLE2 2
96 #define TRAVERSE_MODE_DOUBLE_END 3
97 #define TRAVERSE_MODE_LONGINT 4
98 #define TRAVERSE_MODE_LONGINT_END 5
99 /* do not change order !!! */
100 #define TRAVERSE_TYPE_SUBGOAL 0
101 #define TRAVERSE_TYPE_ANSWER 1
102 #define TRAVERSE_TYPE_GT_SUBGOAL 2
103 #define TRAVERSE_TYPE_GT_ANSWER 3
104 /* do not change order !!! */
105 #define TRAVERSE_POSITION_NEXT 0
106 #define TRAVERSE_POSITION_FIRST 1
107 #define TRAVERSE_POSITION_LAST 2
108
109 /* LowTagBits is 3 for 32 bit-machines and 7 for 64 bit-machines */
110 #define NumberOfLowTagBits (LowTagBits == 3 ? 2 : 3)
111 #define MakeTableVarTerm(INDEX) ((INDEX) << NumberOfLowTagBits)
112 #define VarIndexOfTableTerm(TERM) (((unsigned int) (TERM)) >> NumberOfLowTagBits)
113 #define VarIndexOfTerm(TERM) \
114 ((((CELL) (TERM)) - GLOBAL_table_var_enumerator(0)) / sizeof(CELL))
115 #define IsTableVarTerm(TERM) \
116 ((CELL) (TERM)) >= GLOBAL_table_var_enumerator(0) && \
117 ((CELL) (TERM)) <= GLOBAL_table_var_enumerator(MAX_TABLE_VARS - 1)
118 #ifdef TRIE_COMPACT_PAIRS
119 #define PairTermMark NULL
120 #define CompactPairInit AbsPair((Term *) 0)
121 #define CompactPairEndTerm AbsPair((Term *) (LowTagBits + 1))
122 #define CompactPairEndList AbsPair((Term *) (2*(LowTagBits + 1)))
123 #endif /* TRIE_COMPACT_PAIRS */
124
125 #define NORM_CP(CP) ((choiceptr)(CP))
126 #define GEN_CP(CP) ((struct generator_choicept *)(CP))
127 #define CONS_CP(CP) ((struct consumer_choicept *)(CP))
128 #define LOAD_CP(CP) ((struct loader_choicept *)(CP))
129 #ifdef DETERMINISTIC_TABLING
130 #define DET_GEN_CP(CP) ((struct deterministic_generator_choicept *)(CP))
131 #define IS_DET_GEN_CP(CP) (*(CELL*)(DET_GEN_CP(CP) + 1) <= MAX_TABLE_VARS)
132 #define IS_BATCHED_NORM_GEN_CP(CP) (GEN_CP(CP)->cp_dep_fr == NULL)
133 #define IS_BATCHED_GEN_CP(CP) (IS_DET_GEN_CP(CP) || IS_BATCHED_NORM_GEN_CP(CP))
134 #else
135 #define IS_BATCHED_GEN_CP(CP) (GEN_CP(CP)->cp_dep_fr == NULL)
136 #endif /* DETERMINISTIC_TABLING */
137
138 #define TAG_AS_SUBGOAL_LEAF_NODE(NODE) TrNode_child(NODE) = (sg_node_ptr)((unsigned long int) TrNode_child(NODE) | 0x1)
139 #define UNTAG_SUBGOAL_LEAF_NODE(NODE) ((sg_fr_ptr)((unsigned long int) (NODE) & ~(0x1)))
140 #define IS_SUBGOAL_LEAF_NODE(NODE) ((unsigned long int) TrNode_child(NODE) & 0x1)
141 #define TAG_AS_ANSWER_LEAF_NODE(NODE) TrNode_parent(NODE) = (ans_node_ptr)((unsigned long int) TrNode_parent(NODE) | 0x1)
142 #define UNTAG_ANSWER_LEAF_NODE(NODE) ((ans_node_ptr)((unsigned long int) (NODE) & ~(0x1)))
143 #define IS_ANSWER_LEAF_NODE(NODE) ((unsigned long int) TrNode_parent(NODE) & 0x1)
144
145 #define MAX_NODES_PER_TRIE_LEVEL 8
146 #define MAX_NODES_PER_BUCKET (MAX_NODES_PER_TRIE_LEVEL / 2)
147 #define BASE_HASH_BUCKETS 64
148 #define HASH_ENTRY(ENTRY, SEED) ((((unsigned long int) ENTRY) >> NumberOfLowTagBits) & (SEED))
149 #define SUBGOAL_TRIE_HASH_MARK ((Term) MakeTableVarTerm(MAX_TABLE_VARS))
150 #define IS_SUBGOAL_TRIE_HASH(NODE) (TrNode_entry(NODE) == SUBGOAL_TRIE_HASH_MARK)
151 #define ANSWER_TRIE_HASH_MARK 0
152 #define IS_ANSWER_TRIE_HASH(NODE) (TrNode_instr(NODE) == ANSWER_TRIE_HASH_MARK)
153 #define GLOBAL_TRIE_HASH_MARK ((Term) MakeTableVarTerm(MAX_TABLE_VARS))
154 #define IS_GLOBAL_TRIE_HASH(NODE) (TrNode_entry(NODE) == GLOBAL_TRIE_HASH_MARK)
155
156 #define HASH_TABLE_LOCK(NODE) ((((unsigned long int) (NODE)) >> 5) & (TABLE_LOCK_BUCKETS - 1))
157 #define LOCK_TABLE(NODE) LOCK(GLOBAL_table_lock(HASH_TABLE_LOCK(NODE)))
158 #define UNLOCK_TABLE(NODE) UNLOCK(GLOBAL_table_lock(HASH_TABLE_LOCK(NODE)))
159
160 #define STACK_PUSH_UP(ITEM, STACK) *--(STACK) = (CELL)(ITEM)
161 #define STACK_POP_UP(STACK) *--(STACK)
162 #define STACK_PUSH_DOWN(ITEM, STACK) *(STACK)++ = (CELL)(ITEM)
163 #define STACK_POP_DOWN(STACK) *(STACK)++
164 #define STACK_NOT_EMPTY(STACK, STACK_BASE) (STACK) != (STACK_BASE)
165 #define AUX_STACK_CHECK_EXPAND(STACK, STACK_LIMIT) if ((STACK_LIMIT) >= (STACK)) EXPAND_AUX_STACK(STACK)
166 #define STACK_CHECK_EXPAND(STACK, STACK_LIMIT) if ((STACK_LIMIT) >= (STACK)+4096) EXPAND_STACK(STACK)
167 #if defined(YAPOR) && !defined(THREADS)
168 #define EXPAND_AUX_STACK(STACK) Yap_Error(INTERNAL_ERROR, TermNil, "stack full (AUX_STACK_CHECK_EXPAND)");
169 #define EXPAND_STACK(STACK) Yap_Error(INTERNAL_ERROR, TermNil, "stack full (STACK_CHECK_EXPAND)");
170 #else
171 #define EXPAND_AUX_STACK(STACK) STACK = expand_auxiliary_stack(STACK)
172 #define EXPAND_STACK(STACK) Yap_Error(INTERNAL_ERROR, TermNil, "stack full (STACK_CHECK_EXPAND)");
173 #endif /* YAPOR */
174 #define OPTYAP_ERROR_MESSAGE(OP, COND)
175
176
177
178 /*************************************
179 ** Data structures macros **
180 *************************************/
181
182 #ifdef YAPOR
183 #define frame_with_suspensions_not_collected(OR_FR) \
184 (OrFr_nearest_suspnode(OR_FR) == NULL)
185 #define find_dependency_node(SG_FR, LEADER_CP, DEP_ON_STACK) \
186 if (SgFr_gen_worker(SG_FR) == worker_id) { \
187 LEADER_CP = SgFr_gen_cp(SG_FR); \
188 DEP_ON_STACK = TRUE; \
189 } else { \
190 or_fr_ptr aux_or_fr = SgFr_gen_top_or_fr(SG_FR); \
191 while (! BITMAP_member(OrFr_members(aux_or_fr), worker_id)) \
192 aux_or_fr = OrFr_next(aux_or_fr); \
193 LEADER_CP = GetOrFr_node(aux_or_fr); \
194 DEP_ON_STACK = (LEADER_CP == SgFr_gen_cp(SG_FR)); \
195 }
196 #define find_leader_node(LEADER_CP, DEP_ON_STACK) \
197 { dep_fr_ptr chain_dep_fr = LOCAL_top_dep_fr; \
198 while (YOUNGER_CP(DepFr_cons_cp(chain_dep_fr), LEADER_CP)) { \
199 if (LEADER_CP == DepFr_leader_cp(chain_dep_fr)) { \
200 DEP_ON_STACK |= DepFr_leader_dep_is_on_stack(chain_dep_fr); \
201 break; \
202 } else if (YOUNGER_CP(LEADER_CP, DepFr_leader_cp(chain_dep_fr))) { \
203 LEADER_CP = DepFr_leader_cp(chain_dep_fr); \
204 DEP_ON_STACK = DepFr_leader_dep_is_on_stack(chain_dep_fr); \
205 break; \
206 } \
207 chain_dep_fr = DepFr_next(chain_dep_fr); \
208 } \
209 }
210 #ifdef TIMESTAMP
211 #define DepFr_init_timestamp_field(DEP_FR) DepFr_timestamp(DEP_FR) = 0
212 #else
213 #define DepFr_init_timestamp_field(DEP_FR)
214 #endif /* TIMESTAMP */
215 #define YAPOR_SET_LOAD(CP_PTR) SCH_set_load(CP_PTR)
216 #define SgFr_init_yapor_fields(SG_FR) \
217 SgFr_gen_worker(SG_FR) = worker_id; \
218 SgFr_gen_top_or_fr(SG_FR) = LOCAL_top_or_fr
219 #define DepFr_init_yapor_fields(DEP_FR, DEP_ON_STACK, TOP_OR_FR) \
220 DepFr_leader_dep_is_on_stack(DEP_FR) = DEP_ON_STACK; \
221 DepFr_top_or_fr(DEP_FR) = TOP_OR_FR; \
222 DepFr_init_timestamp_field(DEP_FR)
223 #else
224 #define find_dependency_node(SG_FR, LEADER_CP, DEP_ON_STACK) \
225 LEADER_CP = SgFr_gen_cp(SG_FR); \
226 DEP_ON_STACK = TRUE
227 #define find_leader_node(LEADER_CP, DEP_ON_STACK) \
228 { dep_fr_ptr chain_dep_fr = LOCAL_top_dep_fr; \
229 while (YOUNGER_CP(DepFr_cons_cp(chain_dep_fr), LEADER_CP)) { \
230 if (EQUAL_OR_YOUNGER_CP(LEADER_CP, DepFr_leader_cp(chain_dep_fr))) { \
231 LEADER_CP = DepFr_leader_cp(chain_dep_fr); \
232 break; \
233 } \
234 chain_dep_fr = DepFr_next(chain_dep_fr); \
235 } \
236 }
237 #define YAPOR_SET_LOAD(CP_PTR)
238 #define SgFr_init_yapor_fields(SG_FR)
239 #define DepFr_init_yapor_fields(DEP_FR, DEP_ON_STACK, TOP_OR_FR)
240 #endif /* YAPOR */
241
242 #ifdef TABLE_LOCK_AT_ENTRY_LEVEL
243 #define TabEnt_init_lock_field(TAB_ENT) \
244 INIT_LOCK(TabEnt_lock(TAB_ENT))
245 #define SgHash_init_next_field(HASH, TAB_ENT) \
246 Hash_next(HASH) = TabEnt_hash_chain(TAB_ENT); \
247 TabEnt_hash_chain(TAB_ENT) = HASH
248 #define AnsHash_init_next_field(HASH, SG_FR) \
249 Hash_next(HASH) = SgFr_hash_chain(SG_FR); \
250 SgFr_hash_chain(SG_FR) = HASH
251 #else
252 #define TabEnt_init_lock_field(TAB_ENT)
253 #define SgHash_init_next_field(HASH, TAB_ENT) \
254 LOCK(TabEnt_lock(TAB_ENT)); \
255 Hash_next(HASH) = TabEnt_hash_chain(TAB_ENT); \
256 TabEnt_hash_chain(TAB_ENT) = HASH; \
257 UNLOCK(TabEnt_lock(TAB_ENT))
258 #define AnsHash_init_next_field(HASH, SG_FR) \
259 LOCK(SgFr_lock(SG_FR)); \
260 Hash_next(HASH) = SgFr_hash_chain(SG_FR); \
261 SgFr_hash_chain(SG_FR) = HASH; \
262 UNLOCK(SgFr_lock(SG_FR))
263 #endif /* TABLE_LOCK_AT_ENTRY_LEVEL */
264
265 #ifdef TABLE_LOCK_AT_NODE_LEVEL
266 #define TrNode_init_lock_field(NODE) \
267 INIT_LOCK(TrNode_lock(NODE))
268 #else
269 #define TrNode_init_lock_field(NODE)
270 #endif /* TABLE_LOCK_AT_NODE_LEVEL */
271
272 #define new_table_entry(TAB_ENT, PRED_ENTRY, ATOM, ARITY) \
273 { register sg_node_ptr sg_node; \
274 new_subgoal_trie_node(sg_node, 0, NULL, NULL, NULL); \
275 ALLOC_TABLE_ENTRY(TAB_ENT); \
276 TabEnt_init_lock_field(TAB_ENT); \
277 TabEnt_pe(TAB_ENT) = PRED_ENTRY; \
278 TabEnt_atom(TAB_ENT) = ATOM; \
279 TabEnt_arity(TAB_ENT) = ARITY; \
280 TabEnt_flags(TAB_ENT) = 0; \
281 SetMode_Batched(TabEnt_flags(TAB_ENT)); \
282 SetMode_ExecAnswers(TabEnt_flags(TAB_ENT)); \
283 SetMode_LocalTrie(TabEnt_flags(TAB_ENT)); \
284 TabEnt_mode(TAB_ENT) = TabEnt_flags(TAB_ENT); \
285 if (IsMode_Local(yap_flags[TABLING_MODE_FLAG])) \
286 SetMode_Local(TabEnt_mode(TAB_ENT)); \
287 if (IsMode_LoadAnswers(yap_flags[TABLING_MODE_FLAG])) \
288 SetMode_LoadAnswers(TabEnt_mode(TAB_ENT)); \
289 if (IsMode_GlobalTrie(yap_flags[TABLING_MODE_FLAG])) \
290 SetMode_GlobalTrie(TabEnt_mode(TAB_ENT)); \
291 TabEnt_subgoal_trie(TAB_ENT) = sg_node; \
292 TabEnt_hash_chain(TAB_ENT) = NULL; \
293 TabEnt_next(TAB_ENT) = GLOBAL_root_tab_ent; \
294 GLOBAL_root_tab_ent = TAB_ENT; \
295 }
296
297 #define new_subgoal_frame(SG_FR, CODE) \
298 { register ans_node_ptr ans_node; \
299 new_answer_trie_node(ans_node, 0, 0, NULL, NULL, NULL); \
300 ALLOC_SUBGOAL_FRAME(SG_FR); \
301 INIT_LOCK(SgFr_lock(SG_FR)); \
302 SgFr_code(SG_FR) = CODE; \
303 SgFr_state(SG_FR) = ready; \
304 SgFr_hash_chain(SG_FR) = NULL; \
305 SgFr_answer_trie(SG_FR) = ans_node; \
306 SgFr_first_answer(SG_FR) = NULL; \
307 SgFr_last_answer(SG_FR) = NULL; \
308 }
309 #define init_subgoal_frame(SG_FR) \
310 { SgFr_init_yapor_fields(SG_FR); \
311 SgFr_state(SG_FR) = evaluating; \
312 SgFr_next(SG_FR) = LOCAL_top_sg_fr; \
313 LOCAL_top_sg_fr = SG_FR; \
314 }
315
316 #define new_dependency_frame(DEP_FR, DEP_ON_STACK, TOP_OR_FR, LEADER_CP, CONS_CP, SG_FR, NEXT) \
317 ALLOC_DEPENDENCY_FRAME(DEP_FR); \
318 INIT_LOCK(DepFr_lock(DEP_FR)); \
319 DepFr_init_yapor_fields(DEP_FR, DEP_ON_STACK, TOP_OR_FR); \
320 DepFr_backchain_cp(DEP_FR) = NULL; \
321 DepFr_leader_cp(DEP_FR) = NORM_CP(LEADER_CP); \
322 DepFr_cons_cp(DEP_FR) = NORM_CP(CONS_CP); \
323 /* start with TrNode_child(DepFr_last_answer(DEP_FR)) pointing to SgFr_first_answer(SG_FR) */ \
324 DepFr_last_answer(DEP_FR) = (ans_node_ptr) ((unsigned long int) (SG_FR) + \
325 (unsigned long int) (&SgFr_first_answer((sg_fr_ptr)DEP_FR)) - \
326 (unsigned long int) (&TrNode_child((ans_node_ptr)DEP_FR))); \
327 DepFr_next(DEP_FR) = NEXT
328
329 #define new_suspension_frame(SUSP_FR, TOP_OR_FR_ON_STACK, TOP_DEP, TOP_SG, \
330 H_REG, B_REG, TR_REG, H_SIZE, B_SIZE, TR_SIZE) \
331 ALLOC_SUSPENSION_FRAME(SUSP_FR); \
332 SuspFr_top_or_fr_on_stack(SUSP_FR) = TOP_OR_FR_ON_STACK; \
333 SuspFr_top_dep_fr(SUSP_FR) = TOP_DEP; \
334 SuspFr_top_sg_fr(SUSP_FR) = TOP_SG; \
335 SuspFr_global_reg(SUSP_FR) = (void *) (H_REG); \
336 SuspFr_local_reg(SUSP_FR) = (void *) (B_REG); \
337 SuspFr_trail_reg(SUSP_FR) = (void *) (TR_REG); \
338 ALLOC_BLOCK(SuspFr_global_start(SUSP_FR), H_SIZE + B_SIZE + TR_SIZE, void *); \
339 SuspFr_local_start(SUSP_FR) = SuspFr_global_start(SUSP_FR) + H_SIZE; \
340 SuspFr_trail_start(SUSP_FR) = SuspFr_local_start(SUSP_FR) + B_SIZE; \
341 SuspFr_global_size(SUSP_FR) = H_SIZE; \
342 SuspFr_local_size(SUSP_FR) = B_SIZE; \
343 SuspFr_trail_size(SUSP_FR) = TR_SIZE; \
344 memcpy(SuspFr_global_start(SUSP_FR), SuspFr_global_reg(SUSP_FR), H_SIZE); \
345 memcpy(SuspFr_local_start(SUSP_FR), SuspFr_local_reg(SUSP_FR), B_SIZE); \
346 memcpy(SuspFr_trail_start(SUSP_FR), SuspFr_trail_reg(SUSP_FR), TR_SIZE)
347
348 #define new_subgoal_trie_node(NODE, ENTRY, CHILD, PARENT, NEXT) \
349 ALLOC_SUBGOAL_TRIE_NODE(NODE); \
350 TrNode_entry(NODE) = ENTRY; \
351 TrNode_init_lock_field(NODE); \
352 TrNode_child(NODE) = CHILD; \
353 TrNode_parent(NODE) = PARENT; \
354 TrNode_next(NODE) = NEXT
355
356 #define new_answer_trie_node(NODE, INSTR, ENTRY, CHILD, PARENT, NEXT) \
357 ALLOC_ANSWER_TRIE_NODE(NODE); \
358 TrNode_instr(NODE) = INSTR; \
359 TrNode_entry(NODE) = ENTRY; \
360 TrNode_init_lock_field(NODE); \
361 TrNode_child(NODE) = CHILD; \
362 TrNode_parent(NODE) = PARENT; \
363 TrNode_next(NODE) = NEXT
364
365 #define new_global_trie_node(NODE, ENTRY, CHILD, PARENT, NEXT) \
366 ALLOC_GLOBAL_TRIE_NODE(NODE); \
367 TrNode_entry(NODE) = ENTRY; \
368 TrNode_child(NODE) = CHILD; \
369 TrNode_parent(NODE) = PARENT; \
370 TrNode_next(NODE) = NEXT
371
372 #define new_subgoal_trie_hash(HASH, NUM_NODES, TAB_ENT) \
373 ALLOC_SUBGOAL_TRIE_HASH(HASH); \
374 Hash_mark(HASH) = SUBGOAL_TRIE_HASH_MARK; \
375 Hash_num_buckets(HASH) = BASE_HASH_BUCKETS; \
376 ALLOC_HASH_BUCKETS(Hash_buckets(HASH), BASE_HASH_BUCKETS); \
377 Hash_num_nodes(HASH) = NUM_NODES; \
378 SgHash_init_next_field(HASH, TAB_ENT)
379
380 #define new_answer_trie_hash(HASH, NUM_NODES, SG_FR) \
381 ALLOC_ANSWER_TRIE_HASH(HASH); \
382 Hash_mark(HASH) = ANSWER_TRIE_HASH_MARK; \
383 Hash_num_buckets(HASH) = BASE_HASH_BUCKETS; \
384 ALLOC_HASH_BUCKETS(Hash_buckets(HASH), BASE_HASH_BUCKETS); \
385 Hash_num_nodes(HASH) = NUM_NODES; \
386 AnsHash_init_next_field(HASH, SG_FR)
387
388 #define new_global_trie_hash(HASH, NUM_NODES) \
389 ALLOC_GLOBAL_TRIE_HASH(HASH); \
390 Hash_mark(HASH) = GLOBAL_TRIE_HASH_MARK; \
391 Hash_num_buckets(HASH) = BASE_HASH_BUCKETS; \
392 ALLOC_HASH_BUCKETS(Hash_buckets(HASH), BASE_HASH_BUCKETS); \
393 Hash_num_nodes(HASH) = NUM_NODES
394
395 #ifdef LIMIT_TABLING
396 #define insert_into_global_sg_fr_list(SG_FR) \
397 SgFr_previous(SG_FR) = GLOBAL_last_sg_fr; \
398 SgFr_next(SG_FR) = NULL; \
399 if (GLOBAL_first_sg_fr == NULL) \
400 GLOBAL_first_sg_fr = SG_FR; \
401 else \
402 SgFr_next(GLOBAL_last_sg_fr) = SG_FR; \
403 GLOBAL_last_sg_fr = SG_FR
404 #define remove_from_global_sg_fr_list(SG_FR) \
405 if (SgFr_previous(SG_FR)) { \
406 if ((SgFr_next(SgFr_previous(SG_FR)) = SgFr_next(SG_FR)) != NULL) \
407 SgFr_previous(SgFr_next(SG_FR)) = SgFr_previous(SG_FR); \
408 else \
409 GLOBAL_last_sg_fr = SgFr_previous(SG_FR); \
410 } else { \
411 if ((GLOBAL_first_sg_fr = SgFr_next(SG_FR)) != NULL) \
412 SgFr_previous(SgFr_next(SG_FR)) = NULL; \
413 else \
414 GLOBAL_last_sg_fr = NULL; \
415 } \
416 if (GLOBAL_check_sg_fr == SG_FR) \
417 GLOBAL_check_sg_fr = SgFr_previous(SG_FR)
418 #else
419 #define insert_into_global_sg_fr_list(SG_FR)
420 #define remove_from_global_sg_fr_list(SG_FR)
421 #endif /* LIMIT_TABLING */
422
423
424
425 /******************************
426 ** Inline funcions **
427 ******************************/
428
freeze_current_cp(void)429 static inline Int freeze_current_cp(void) {
430 choiceptr freeze_cp = B;
431
432 B_FZ = freeze_cp;
433 H_FZ = freeze_cp->cp_h;
434 TR_FZ = freeze_cp->cp_tr;
435 B = B->cp_b;
436 HB = B->cp_h;
437 return (Yap_LocalBase - (ADDR)freeze_cp);
438 }
439
440
wake_frozen_cp(Int frozen_offset)441 static inline void wake_frozen_cp(Int frozen_offset) {
442 choiceptr frozen_cp = (choiceptr)(Yap_LocalBase - frozen_offset);
443
444 restore_bindings(TR, frozen_cp->cp_tr);
445 B = frozen_cp;
446 TR = TR_FZ;
447 TRAIL_LINK(B->cp_tr);
448 return;
449 }
450
451
abolish_frozen_cps_until(Int frozen_offset)452 static inline void abolish_frozen_cps_until(Int frozen_offset) {
453 choiceptr frozen_cp = (choiceptr)(Yap_LocalBase - frozen_offset);
454
455 B_FZ = frozen_cp;
456 H_FZ = frozen_cp->cp_h;
457 TR_FZ = frozen_cp->cp_tr;
458 return;
459 }
460
461
abolish_frozen_cps_all(void)462 static inline void abolish_frozen_cps_all(void) {
463 B_FZ = (choiceptr) Yap_LocalBase;
464 H_FZ = (CELL *) Yap_GlobalBase;
465 TR_FZ = (tr_fr_ptr) Yap_TrailBase;
466 return;
467 }
468
469
adjust_freeze_registers(void)470 static inline void adjust_freeze_registers(void) {
471 B_FZ = DepFr_cons_cp(LOCAL_top_dep_fr);
472 H_FZ = B_FZ->cp_h;
473 TR_FZ = B_FZ->cp_tr;
474 return;
475 }
476
477
mark_as_completed(sg_fr_ptr sg_fr)478 static inline void mark_as_completed(sg_fr_ptr sg_fr) {
479 LOCK(SgFr_lock(sg_fr));
480 SgFr_state(sg_fr) = complete;
481 UNLOCK(SgFr_lock(sg_fr));
482 return;
483 }
484
485
unbind_variables(tr_fr_ptr unbind_tr,tr_fr_ptr end_tr)486 static inline void unbind_variables(tr_fr_ptr unbind_tr, tr_fr_ptr end_tr) {
487 TABLING_ERROR_CHECKING(unbind_variables, unbind_tr < end_tr);
488 /* unbind loop */
489 while (unbind_tr != end_tr) {
490 CELL ref = (CELL) TrailTerm(--unbind_tr);
491 /* check for global or local variables */
492 if (IsVarTerm(ref)) {
493 /* unbind variable */
494 RESET_VARIABLE(ref);
495 } else if (IsPairTerm(ref)) {
496 ref = (CELL) RepPair(ref);
497 if (IN_BETWEEN(Yap_TrailBase, ref, Yap_TrailTop)) {
498 /* avoid frozen segments */
499 unbind_tr = (tr_fr_ptr) ref;
500 TABLING_ERROR_CHECKING(unbind_variables, unbind_tr > (tr_fr_ptr) Yap_TrailTop);
501 TABLING_ERROR_CHECKING(unbind_variables, unbind_tr < end_tr);
502 }
503 #ifdef MULTI_ASSIGNMENT_VARIABLES
504 } else {
505 CELL *aux_ptr = RepAppl(ref);
506 --unbind_tr;
507 Term aux_val = TrailVal(unbind_tr);
508 *aux_ptr = aux_val;
509 #endif /* MULTI_ASSIGNMENT_VARIABLES */
510 }
511 }
512 return;
513 }
514
515
rebind_variables(tr_fr_ptr rebind_tr,tr_fr_ptr end_tr)516 static inline void rebind_variables(tr_fr_ptr rebind_tr, tr_fr_ptr end_tr) {
517 TABLING_ERROR_CHECKING(rebind_variables, rebind_tr < end_tr);
518 /* rebind loop */
519 Yap_NEW_MAHASH((ma_h_inner_struct *)H);
520 while (rebind_tr != end_tr) {
521 CELL ref = (CELL) TrailTerm(--rebind_tr);
522 /* check for global or local variables */
523 if (IsVarTerm(ref)) {
524 /* rebind variable */
525 *((CELL *)ref) = TrailVal(rebind_tr);
526 } else if (IsPairTerm(ref)) {
527 ref = (CELL) RepPair(ref);
528 if (IN_BETWEEN(Yap_TrailBase, ref, Yap_TrailTop)) {
529 /* avoid frozen segments */
530 rebind_tr = (tr_fr_ptr) ref;
531 TABLING_ERROR_CHECKING(rebind_variables, rebind_tr > (tr_fr_ptr) Yap_TrailTop);
532 TABLING_ERROR_CHECKING(rebind_variables, rebind_tr < end_tr);
533 }
534 #ifdef MULTI_ASSIGNMENT_VARIABLES
535 } else {
536 CELL *cell_ptr = RepAppl(ref);
537 if (!Yap_lookup_ma_var(cell_ptr)) {
538 /* first time we found the variable, let's put the new value */
539 *cell_ptr = TrailVal(rebind_tr);
540 }
541 --rebind_tr;
542 #endif /* MULTI_ASSIGNMENT_VARIABLES */
543 }
544 }
545 return;
546 }
547
548
restore_bindings(tr_fr_ptr unbind_tr,tr_fr_ptr rebind_tr)549 static inline void restore_bindings(tr_fr_ptr unbind_tr, tr_fr_ptr rebind_tr) {
550 CELL ref;
551 tr_fr_ptr end_tr;
552
553 TABLING_ERROR_CHECKING(restore_variables, unbind_tr < rebind_tr);
554 end_tr = rebind_tr;
555 Yap_NEW_MAHASH((ma_h_inner_struct *)H);
556 while (unbind_tr != end_tr) {
557 /* unbind loop */
558 while (unbind_tr > end_tr) {
559 ref = (CELL) TrailTerm(--unbind_tr);
560 if (IsVarTerm(ref)) {
561 RESET_VARIABLE(ref);
562 } else if (IsPairTerm(ref)) {
563 ref = (CELL) RepPair(ref);
564 if (IN_BETWEEN(Yap_TrailBase, ref, Yap_TrailTop)) {
565 /* avoid frozen segments */
566 unbind_tr = (tr_fr_ptr) ref;
567 TABLING_ERROR_CHECKING(restore_variables, unbind_tr > (tr_fr_ptr) Yap_TrailTop);
568 }
569 #ifdef MULTI_ASSIGNMENT_VARIABLES
570 } else if (IsApplTerm(ref)) {
571 CELL *pt = RepAppl(ref);
572
573 /* AbsAppl means */
574 /* multi-assignment variable */
575 /* so that the upper cell is the old value */
576 --unbind_tr;
577 if (!Yap_lookup_ma_var(pt)) {
578 pt[0] = TrailVal(unbind_tr);
579 }
580 #endif /* MULTI_ASSIGNMENT_VARIABLES */
581 }
582 }
583 /* look for end */
584 while (unbind_tr < end_tr) {
585 ref = (CELL) TrailTerm(--end_tr);
586 if (IsPairTerm(ref)) {
587 ref = (CELL) RepPair(ref);
588 if (IN_BETWEEN(Yap_TrailBase, ref, Yap_TrailTop)) {
589 /* avoid frozen segments */
590 end_tr = (tr_fr_ptr) ref;
591 TABLING_ERROR_CHECKING(restore_variables, end_tr > (tr_fr_ptr) Yap_TrailTop);
592 }
593 }
594 }
595 }
596 /* rebind loop */
597 while (rebind_tr != end_tr) {
598 ref = (CELL) TrailTerm(--rebind_tr);
599 if (IsVarTerm(ref)) {
600 *((CELL *)ref) = TrailVal(rebind_tr);
601 } else if (IsPairTerm(ref)) {
602 ref = (CELL) RepPair(ref);
603 if (IN_BETWEEN(Yap_TrailBase, ref, Yap_TrailTop)) {
604 /* avoid frozen segments */
605 rebind_tr = (tr_fr_ptr) ref;
606 TABLING_ERROR_CHECKING(restore_variables, rebind_tr > (tr_fr_ptr) Yap_TrailTop);
607 TABLING_ERROR_CHECKING(restore_variables, rebind_tr < end_tr);
608 }
609 #ifdef MULTI_ASSIGNMENT_VARIABLES
610 } else {
611 CELL *cell_ptr = RepAppl(ref);
612 /* first time we found the variable, let's put the new value */
613 *cell_ptr = TrailVal(rebind_tr);
614 --rebind_tr;
615 #endif /* MULTI_ASSIGNMENT_VARIABLES */
616 }
617 }
618 return;
619 }
620
621
expand_auxiliary_stack(CELL * stack)622 static inline CELL *expand_auxiliary_stack(CELL *stack) {
623 void *old_top = Yap_TrailTop;
624 INFORMATION_MESSAGE("Expanding trail in 64 Kbytes");
625 if (! Yap_growtrail(K64, TRUE)) { /* TRUE means 'contiguous_only' */
626 Yap_Error(OUT_OF_TRAIL_ERROR, TermNil, "stack full (STACK_CHECK_EXPAND)");
627 return NULL;
628 } else {
629 UInt diff = (void *)Yap_TrailTop - old_top;
630 CELL *new_stack = (CELL *)((void *)stack + diff);
631 memmove((void *)new_stack, (void *)stack, old_top - (void *)stack);
632 return new_stack;
633 }
634 }
635
636
abolish_incomplete_subgoals(choiceptr prune_cp)637 static inline void abolish_incomplete_subgoals(choiceptr prune_cp) {
638 #ifdef YAPOR
639 if (EQUAL_OR_YOUNGER_CP(GetOrFr_node(LOCAL_top_susp_or_fr), prune_cp))
640 pruning_over_tabling_data_structures();
641 #endif /* YAPOR */
642
643 if (EQUAL_OR_YOUNGER_CP(DepFr_cons_cp(LOCAL_top_dep_fr), prune_cp)) {
644 #ifdef YAPOR
645 if (PARALLEL_EXECUTION_MODE)
646 pruning_over_tabling_data_structures();
647 #endif /* YAPOR */
648 do {
649 dep_fr_ptr dep_fr = LOCAL_top_dep_fr;
650 LOCAL_top_dep_fr = DepFr_next(dep_fr);
651 FREE_DEPENDENCY_FRAME(dep_fr);
652 } while (EQUAL_OR_YOUNGER_CP(DepFr_cons_cp(LOCAL_top_dep_fr), prune_cp));
653 adjust_freeze_registers();
654 }
655
656 while (LOCAL_top_sg_fr && EQUAL_OR_YOUNGER_CP(SgFr_gen_cp(LOCAL_top_sg_fr), prune_cp)) {
657 sg_fr_ptr sg_fr;
658 #ifdef YAPOR
659 if (PARALLEL_EXECUTION_MODE)
660 pruning_over_tabling_data_structures();
661 #endif /* YAPOR */
662 sg_fr = LOCAL_top_sg_fr;
663 LOCAL_top_sg_fr = SgFr_next(sg_fr);
664 LOCK(SgFr_lock(sg_fr));
665 if (SgFr_first_answer(sg_fr) == NULL) {
666 /* no answers --> ready */
667 SgFr_state(sg_fr) = ready;
668 UNLOCK(SgFr_lock(sg_fr));
669 } else if (SgFr_first_answer(sg_fr) == SgFr_answer_trie(sg_fr)) {
670 /* yes answer --> complete */
671 #ifndef TABLING_EARLY_COMPLETION
672 /* with early completion, at this point the subgoal should be already completed */
673 SgFr_state(sg_fr) = complete;
674 #endif /* TABLING_EARLY_COMPLETION */
675 UNLOCK(SgFr_lock(sg_fr));
676 } else {
677 /* answers --> incomplete/ready */
678 #ifdef INCOMPLETE_TABLING
679 SgFr_state(sg_fr) = incomplete;
680 UNLOCK(SgFr_lock(sg_fr));
681 #else
682 ans_node_ptr node;
683 SgFr_state(sg_fr) = ready;
684 free_answer_hash_chain(SgFr_hash_chain(sg_fr));
685 SgFr_hash_chain(sg_fr) = NULL;
686 SgFr_first_answer(sg_fr) = NULL;
687 SgFr_last_answer(sg_fr) = NULL;
688 node = TrNode_child(SgFr_answer_trie(sg_fr));
689 TrNode_child(SgFr_answer_trie(sg_fr)) = NULL;
690 UNLOCK(SgFr_lock(sg_fr));
691 free_answer_trie(node, TRAVERSE_MODE_NORMAL, TRAVERSE_POSITION_FIRST);
692 #endif /* INCOMPLETE_TABLING */
693 }
694 #ifdef LIMIT_TABLING
695 insert_into_global_sg_fr_list(sg_fr);
696 #endif /* LIMIT_TABLING */
697 }
698
699 return;
700 }
701
702
703 #ifdef YAPOR
pruning_over_tabling_data_structures(void)704 static inline void pruning_over_tabling_data_structures(void) {
705 Yap_Error(INTERNAL_ERROR, TermNil, "pruning over tabling data structures");
706 return;
707 }
708
709
collect_suspension_frames(or_fr_ptr or_fr)710 static inline void collect_suspension_frames(or_fr_ptr or_fr) {
711 int depth;
712 or_fr_ptr *susp_ptr;
713
714 OPTYAP_ERROR_CHECKING(collect_suspension_frames, IS_UNLOCKED(or_fr));
715 OPTYAP_ERROR_CHECKING(collect_suspension_frames, OrFr_suspensions(or_fr) == NULL);
716
717 /* order collected suspension frames by depth */
718 depth = OrFr_depth(or_fr);
719 susp_ptr = & LOCAL_top_susp_or_fr;
720 while (OrFr_depth(*susp_ptr) > depth)
721 susp_ptr = & OrFr_nearest_suspnode(*susp_ptr);
722 OrFr_nearest_suspnode(or_fr) = *susp_ptr;
723 *susp_ptr = or_fr;
724 return;
725 }
726
727
728 static inline
729 #ifdef TIMESTAMP_CHECK
suspension_frame_to_resume(or_fr_ptr susp_or_fr,long timestamp)730 susp_fr_ptr suspension_frame_to_resume(or_fr_ptr susp_or_fr, long timestamp) {
731 #else
732 susp_fr_ptr suspension_frame_to_resume(or_fr_ptr susp_or_fr) {
733 #endif /* TIMESTAMP_CHECK */
734 choiceptr top_cp;
735 susp_fr_ptr *susp_ptr, susp_fr;
736 dep_fr_ptr dep_fr;
737
738 top_cp = GetOrFr_node(susp_or_fr);
739 susp_ptr = & OrFr_suspensions(susp_or_fr);
740 susp_fr = *susp_ptr;
741 while (susp_fr) {
742 dep_fr = SuspFr_top_dep_fr(susp_fr);
743 do {
744 if (TrNode_child(DepFr_last_answer(dep_fr))) {
745 /* unconsumed answers in susp_fr */
746 *susp_ptr = SuspFr_next(susp_fr);
747 return susp_fr;
748 }
749 #ifdef TIMESTAMP_CHECK
750 DepFr_timestamp(dep_fr) = timestamp;
751 #endif /* TIMESTAMP_CHECK */
752 dep_fr = DepFr_next(dep_fr);
753 #ifdef TIMESTAMP_CHECK
754 } while (timestamp > DepFr_timestamp(dep_fr) && YOUNGER_CP(DepFr_cons_cp(dep_fr), top_cp));
755 #else
756 } while (YOUNGER_CP(DepFr_cons_cp(dep_fr), top_cp));
757 #endif /* TIMESTAMP_CHECK */
758 susp_ptr = & SuspFr_next(susp_fr);
759 susp_fr = *susp_ptr;
760 }
761 /* no suspension frame with unconsumed answers */
762 return NULL;
763 }
764 #endif /* YAPOR */
765
766
767 #ifdef TABLING_INNER_CUTS
CUT_store_tg_answer(or_fr_ptr or_frame,ans_node_ptr ans_node,choiceptr gen_cp,int ltt)768 static inline void CUT_store_tg_answer(or_fr_ptr or_frame, ans_node_ptr ans_node, choiceptr gen_cp, int ltt) {
769 tg_sol_fr_ptr tg_sol_fr, *solution_ptr, next, ltt_next;
770 tg_ans_fr_ptr tg_ans_fr;
771
772 solution_ptr = & OrFr_tg_solutions(or_frame);
773 while (*solution_ptr && YOUNGER_CP(gen_cp, TgSolFr_gen_cp(*solution_ptr))) {
774 solution_ptr = & TgSolFr_next(*solution_ptr);
775 }
776 if (*solution_ptr && gen_cp == TgSolFr_gen_cp(*solution_ptr)) {
777 if (ltt >= TgSolFr_ltt(*solution_ptr)) {
778 while (*solution_ptr && ltt > TgSolFr_ltt(*solution_ptr)) {
779 solution_ptr = & TgSolFr_ltt_next(*solution_ptr);
780 }
781 if (*solution_ptr && ltt == TgSolFr_ltt(*solution_ptr)) {
782 tg_ans_fr = TgSolFr_first(*solution_ptr);
783 if (TgAnsFr_free_slot(tg_ans_fr) == TG_ANSWER_SLOTS) {
784 ALLOC_TG_ANSWER_FRAME(tg_ans_fr);
785 TgAnsFr_free_slot(tg_ans_fr) = 1;
786 TgAnsFr_answer(tg_ans_fr, 0) = ans_node;
787 TgAnsFr_next(tg_ans_fr) = TgSolFr_first(*solution_ptr);
788 TgSolFr_first(*solution_ptr) = tg_ans_fr;
789 } else {
790 TgAnsFr_answer(tg_ans_fr, TgAnsFr_free_slot(tg_ans_fr)) = ans_node;
791 TgAnsFr_free_slot(tg_ans_fr)++;
792 }
793 return;
794 }
795 ltt_next = *solution_ptr;
796 next = NULL;
797 } else {
798 ltt_next = *solution_ptr;
799 next = TgSolFr_next(*solution_ptr);
800 }
801 } else {
802 ltt_next = NULL;
803 next = *solution_ptr;
804 }
805 ALLOC_TG_ANSWER_FRAME(tg_ans_fr);
806 TgAnsFr_free_slot(tg_ans_fr) = 1;
807 TgAnsFr_answer(tg_ans_fr, 0) = ans_node;
808 TgAnsFr_next(tg_ans_fr) = NULL;
809 ALLOC_TG_SOLUTION_FRAME(tg_sol_fr);
810 TgSolFr_gen_cp(tg_sol_fr) = gen_cp;
811 TgSolFr_ltt(tg_sol_fr) = ltt;
812 TgSolFr_first(tg_sol_fr) = tg_ans_fr;
813 TgSolFr_last(tg_sol_fr) = tg_ans_fr;
814 TgSolFr_ltt_next(tg_sol_fr) = ltt_next;
815 TgSolFr_next(tg_sol_fr) = next;
816 *solution_ptr = tg_sol_fr;
817 return;
818 }
819
820
CUT_store_tg_answers(or_fr_ptr or_frame,tg_sol_fr_ptr new_solution,int ltt)821 static inline tg_sol_fr_ptr CUT_store_tg_answers(or_fr_ptr or_frame, tg_sol_fr_ptr new_solution, int ltt) {
822 tg_sol_fr_ptr *old_solution_ptr, next_new_solution;
823 choiceptr node, gen_cp;
824
825 old_solution_ptr = & OrFr_tg_solutions(or_frame);
826 node = GetOrFr_node(or_frame);
827 while (new_solution && YOUNGER_CP(node, TgSolFr_gen_cp(new_solution))) {
828 next_new_solution = TgSolFr_next(new_solution);
829 gen_cp = TgSolFr_gen_cp(new_solution);
830 while (*old_solution_ptr && YOUNGER_CP(gen_cp, TgSolFr_gen_cp(*old_solution_ptr))) {
831 old_solution_ptr = & TgSolFr_next(*old_solution_ptr);
832 }
833 if (*old_solution_ptr && gen_cp == TgSolFr_gen_cp(*old_solution_ptr)) {
834 if (ltt >= TgSolFr_ltt(*old_solution_ptr)) {
835 tg_sol_fr_ptr *ltt_next_old_solution_ptr;
836 ltt_next_old_solution_ptr = old_solution_ptr;
837 while (*ltt_next_old_solution_ptr && ltt > TgSolFr_ltt(*ltt_next_old_solution_ptr)) {
838 ltt_next_old_solution_ptr = & TgSolFr_ltt_next(*ltt_next_old_solution_ptr);
839 }
840 if (*ltt_next_old_solution_ptr && ltt == TgSolFr_ltt(*ltt_next_old_solution_ptr)) {
841 TgAnsFr_next(TgSolFr_last(*ltt_next_old_solution_ptr)) = TgSolFr_first(new_solution);
842 TgSolFr_last(*ltt_next_old_solution_ptr) = TgSolFr_last(new_solution);
843 FREE_TG_SOLUTION_FRAME(new_solution);
844 } else {
845 TgSolFr_ltt(new_solution) = ltt;
846 TgSolFr_ltt_next(new_solution) = *ltt_next_old_solution_ptr;
847 TgSolFr_next(new_solution) = NULL;
848 *ltt_next_old_solution_ptr = new_solution;
849 }
850 } else {
851 TgSolFr_ltt(new_solution) = ltt;
852 TgSolFr_ltt_next(new_solution) = *old_solution_ptr;
853 TgSolFr_next(new_solution) = TgSolFr_next(*old_solution_ptr);
854 *old_solution_ptr = new_solution;
855 }
856 } else {
857 TgSolFr_ltt(new_solution) = ltt;
858 TgSolFr_ltt_next(new_solution) = NULL;
859 TgSolFr_next(new_solution) = *old_solution_ptr;
860 *old_solution_ptr = new_solution;
861 }
862 old_solution_ptr = & TgSolFr_next(*old_solution_ptr);
863 new_solution = next_new_solution;
864 }
865 return new_solution;
866 }
867
868
CUT_validate_tg_answers(tg_sol_fr_ptr valid_solutions)869 static inline void CUT_validate_tg_answers(tg_sol_fr_ptr valid_solutions) {
870 tg_ans_fr_ptr valid_answers, free_answer;
871 tg_sol_fr_ptr ltt_valid_solutions, free_solution;
872 ans_node_ptr first_answer, last_answer, ans_node;
873 sg_fr_ptr sg_fr;
874 int slots;
875
876 while (valid_solutions) {
877 first_answer = last_answer = NULL;
878 #ifdef DETERMINISTIC_TABLING
879 if (IS_DET_GEN_CP(TgSolFr_gen_cp(valid_solutions)))
880 sg_fr = DET_GEN_CP(TgSolFr_gen_cp(valid_solutions))->cp_sg_fr;
881 else
882 #endif /* DETERMINISTIC_TABLING */
883 sg_fr = GEN_CP(TgSolFr_gen_cp(valid_solutions))->cp_sg_fr;
884 ltt_valid_solutions = valid_solutions;
885 valid_solutions = TgSolFr_next(valid_solutions);
886 do {
887 valid_answers = TgSolFr_first(ltt_valid_solutions);
888 do {
889 slots = TgAnsFr_free_slot(valid_answers);
890 do {
891 ans_node = TgAnsFr_answer(valid_answers, --slots);
892 #if defined(TABLE_LOCK_AT_ENTRY_LEVEL)
893 LOCK(SgFr_lock(sg_fr));
894 #elif defined(TABLE_LOCK_AT_NODE_LEVEL)
895 LOCK(TrNode_lock(ans_node));
896 #elif defined(TABLE_LOCK_AT_WRITE_LEVEL)
897 LOCK_TABLE(ans_node);
898 #endif /* TABLE_LOCK_LEVEL */
899 if (! IS_ANSWER_LEAF_NODE(ans_node)) {
900 TAG_AS_ANSWER_LEAF_NODE(ans_node);
901 if (first_answer == NULL)
902 first_answer = ans_node;
903 else
904 TrNode_child(last_answer) = ans_node;
905 last_answer = ans_node;
906 }
907 #if defined(TABLE_LOCK_AT_ENTRY_LEVEL)
908 UNLOCK(SgFr_lock(sg_fr));
909 #elif defined(TABLE_LOCK_AT_NODE_LEVEL)
910 UNLOCK(TrNode_lock(ans_node));
911 #elif defined(TABLE_LOCK_AT_WRITE_LEVEL)
912 UNLOCK_TABLE(ans_node);
913 #endif /* TABLE_LOCK_LEVEL */
914 } while (slots);
915 free_answer = valid_answers;
916 valid_answers = TgAnsFr_next(valid_answers);
917 FREE_TG_ANSWER_FRAME(free_answer);
918 } while (valid_answers);
919 free_solution = ltt_valid_solutions;
920 ltt_valid_solutions = TgSolFr_ltt_next(ltt_valid_solutions);
921 FREE_TG_SOLUTION_FRAME(free_solution);
922 } while (ltt_valid_solutions);
923 if (first_answer) {
924 LOCK(SgFr_lock(sg_fr));
925 if (SgFr_first_answer(sg_fr) == NULL) {
926 SgFr_first_answer(sg_fr) = first_answer;
927 } else {
928 TrNode_child(SgFr_last_answer(sg_fr)) = first_answer;
929 }
930 SgFr_last_answer(sg_fr) = last_answer;
931 UNLOCK(SgFr_lock(sg_fr));
932 }
933 }
934 return;
935 }
936
937
CUT_join_tg_solutions(tg_sol_fr_ptr * old_solution_ptr,tg_sol_fr_ptr new_solution)938 static inline void CUT_join_tg_solutions(tg_sol_fr_ptr *old_solution_ptr, tg_sol_fr_ptr new_solution) {
939 tg_sol_fr_ptr next_old_solution, next_new_solution;
940 choiceptr gen_cp;
941
942 do {
943 gen_cp = TgSolFr_gen_cp(new_solution);
944 while (*old_solution_ptr && YOUNGER_CP(gen_cp, TgSolFr_gen_cp(*old_solution_ptr))) {
945 old_solution_ptr = & TgSolFr_next(*old_solution_ptr);
946 }
947 if (*old_solution_ptr) {
948 next_old_solution = *old_solution_ptr;
949 *old_solution_ptr = new_solution;
950 CUT_join_solution_frame_tg_answers(new_solution);
951 if (gen_cp == TgSolFr_gen_cp(next_old_solution)) {
952 tg_sol_fr_ptr free_solution;
953 TgAnsFr_next(TgSolFr_last(new_solution)) = TgSolFr_first(next_old_solution);
954 TgSolFr_last(new_solution) = TgSolFr_last(next_old_solution);
955 free_solution = next_old_solution;
956 next_old_solution = TgSolFr_next(next_old_solution);
957 FREE_TG_SOLUTION_FRAME(free_solution);
958 if (! next_old_solution) {
959 if ((next_new_solution = TgSolFr_next(new_solution))) {
960 CUT_join_solution_frames_tg_answers(next_new_solution);
961 }
962 return;
963 }
964 }
965 gen_cp = TgSolFr_gen_cp(next_old_solution);
966 next_new_solution = TgSolFr_next(new_solution);
967 while (next_new_solution && YOUNGER_CP(gen_cp, TgSolFr_gen_cp(next_new_solution))) {
968 new_solution = next_new_solution;
969 next_new_solution = TgSolFr_next(new_solution);
970 CUT_join_solution_frame_tg_answers(new_solution);
971 }
972 old_solution_ptr = & TgSolFr_next(new_solution);
973 TgSolFr_next(new_solution) = next_old_solution;
974 new_solution = next_new_solution;
975 } else {
976 *old_solution_ptr = new_solution;
977 CUT_join_solution_frames_tg_answers(new_solution);
978 return;
979 }
980 } while (new_solution);
981 return;
982 }
983
984
CUT_join_solution_frame_tg_answers(tg_sol_fr_ptr join_solution)985 static inline void CUT_join_solution_frame_tg_answers(tg_sol_fr_ptr join_solution) {
986 tg_sol_fr_ptr next_solution;
987
988 while ((next_solution = TgSolFr_ltt_next(join_solution))) {
989 TgAnsFr_next(TgSolFr_last(join_solution)) = TgSolFr_first(next_solution);
990 TgSolFr_last(join_solution) = TgSolFr_last(next_solution);
991 TgSolFr_ltt_next(join_solution) = TgSolFr_ltt_next(next_solution);
992 FREE_TG_SOLUTION_FRAME(next_solution);
993 }
994 return;
995 }
996
997
CUT_join_solution_frames_tg_answers(tg_sol_fr_ptr join_solution)998 static inline void CUT_join_solution_frames_tg_answers(tg_sol_fr_ptr join_solution) {
999 do {
1000 CUT_join_solution_frame_tg_answers(join_solution);
1001 join_solution = TgSolFr_next(join_solution);
1002 } while (join_solution);
1003 return;
1004 }
1005
1006
CUT_free_tg_solution_frame(tg_sol_fr_ptr solution)1007 static inline void CUT_free_tg_solution_frame(tg_sol_fr_ptr solution) {
1008 tg_ans_fr_ptr current_answer, next_answer;
1009
1010 current_answer = TgSolFr_first(solution);
1011 do {
1012 next_answer = TgAnsFr_next(current_answer);
1013 FREE_TG_ANSWER_FRAME(current_answer);
1014 current_answer = next_answer;
1015 } while (current_answer);
1016 FREE_TG_SOLUTION_FRAME(solution);
1017 return;
1018 }
1019
1020
CUT_free_tg_solution_frames(tg_sol_fr_ptr current_solution)1021 static inline void CUT_free_tg_solution_frames(tg_sol_fr_ptr current_solution) {
1022 tg_sol_fr_ptr ltt_solution, next_solution;
1023
1024 while (current_solution) {
1025 ltt_solution = TgSolFr_ltt_next(current_solution);
1026 while (ltt_solution) {
1027 next_solution = TgSolFr_ltt_next(ltt_solution);
1028 CUT_free_tg_solution_frame(ltt_solution);
1029 ltt_solution = next_solution;
1030 }
1031 next_solution = TgSolFr_next(current_solution);
1032 CUT_free_tg_solution_frame(current_solution);
1033 current_solution = next_solution;
1034 }
1035 return;
1036 }
1037
1038
CUT_prune_tg_solution_frames(tg_sol_fr_ptr solutions,int ltt)1039 static inline tg_sol_fr_ptr CUT_prune_tg_solution_frames(tg_sol_fr_ptr solutions, int ltt) {
1040 tg_sol_fr_ptr ltt_next_solution, return_solution;
1041
1042 if (! solutions) return NULL;
1043 return_solution = CUT_prune_tg_solution_frames(TgSolFr_next(solutions), ltt);
1044 while (solutions && ltt > TgSolFr_ltt(solutions)) {
1045 ltt_next_solution = TgSolFr_ltt_next(solutions);
1046 CUT_free_tg_solution_frame(solutions);
1047 solutions = ltt_next_solution;
1048 }
1049 if (solutions) {
1050 TgSolFr_next(solutions) = return_solution;
1051 return solutions;
1052 } else {
1053 return return_solution;
1054 }
1055 }
1056 #endif /* TABLING_INNER_CUTS */
1057