YAP 7.1.0
or.cut.c
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 **
16** ------------------ */
17
18#include "Yap.h"
19#ifdef YAPOR
20#include "Yatom.h"
21#include "YapHeap.h"
22#include "or.macros.h"
23#ifdef TABLING
24#include "tab.macros.h"
25#endif /* TABLING */
26
27
28
29/* -------------------------- **
30** Global functions **
31** -------------------------- */
32
33void prune_shared_branch(choiceptr prune_cp, int* pend_ltt) {
34 CACHE_REGS
35 int i, ltt, depth;
36 bitmap members;
37 choiceptr leftmost_cp;
38 or_fr_ptr leftmost_or_fr;
39 qg_sol_fr_ptr qg_solutions, aux_qg_solutions;
40#ifdef TABLING_INNER_CUTS
41 tg_sol_fr_ptr tg_solutions, aux_tg_solutions;
42#endif /* TABLING_INNER_CUTS */
43 leftmost_or_fr = CUT_leftmost_or_frame();
44 if (Get_LOCAL_prune_request())
45 return;
46 leftmost_cp = GetOrFr_node(leftmost_or_fr);
47 qg_solutions = NULL;
48#ifdef TABLING_INNER_CUTS
49 tg_solutions = NULL;
50#endif /* TABLING_INNER_CUTS */
51 if (EQUAL_OR_YOUNGER_CP(prune_cp, leftmost_cp)) {
52 /* pruning being leftmost */
53 or_fr_ptr prune_or_fr;
54
55
56 bitmap members2;
57 or_fr_ptr old_LOCAL_top_or_fr = LOCAL_top_or_fr;
58
59 if(pend_ltt){
60 LOCK_OR_FRAME(LOCAL_top_or_fr);
61 int depth2 = OrFr_depth(LOCAL_top_or_fr);
62 members2 = OrFr_members(LOCAL_top_or_fr);
63 for (i = 0; i < GLOBAL_number_workers; i++) {
64 if (BITMAP_member(members2, i) && *pend_ltt != BRANCH_LTT(i,depth2)){
65 BITMAP_delete(members2,i);
66 }
67 }
68 }
69
70 /* send prune requests */
71 prune_or_fr = prune_cp->cp_or_fr;
72 depth = OrFr_depth(prune_or_fr);
73 ltt = BRANCH_LTT(worker_id, depth);
74 LOCK_OR_FRAME(prune_or_fr);
75 members = OrFr_members(prune_or_fr);
76
77 if(pend_ltt){
78 BITMAP_minus(members,members2);
79 }
80
81
82 BITMAP_delete(members, worker_id);
83
84 for (i = 0; i < GLOBAL_number_workers; i++) {
85 if (BITMAP_member(members, i) && ltt == BRANCH_LTT(i, depth)) {
86 CUT_send_prune_request(i, prune_cp);
87 }
88 }
89 UNLOCK_OR_FRAME(prune_or_fr);
90
91 /* move up to prune_cp */
92 do {
93 ltt = BRANCH_LTT(worker_id, OrFr_depth(LOCAL_top_or_fr));
94 if(!pend_ltt || LOCAL_top_or_fr != old_LOCAL_top_or_fr)
95 LOCK_OR_FRAME(LOCAL_top_or_fr);
96 if (Get_OrFr_pend_prune_cp(LOCAL_top_or_fr)){
97 Set_OrFr_pend_prune_cp(LOCAL_top_or_fr, NULL);
98 }
99 aux_qg_solutions = OrFr_qg_solutions(LOCAL_top_or_fr);
100#ifdef TABLING_INNER_CUTS
101 aux_tg_solutions = OrFr_tg_solutions(LOCAL_top_or_fr);
102#endif /* TABLING_INNER_CUTS */
103 if (BITMAP_alone(OrFr_members(LOCAL_top_or_fr), worker_id)) {
104#ifdef TABLING
105 if (OrFr_suspensions(LOCAL_top_or_fr) || OrFr_owners(LOCAL_top_or_fr) != 1)
106 pruning_over_tabling_data_structures();
107#endif /* TABLING */
108 if(!pend_ltt || LOCAL_top_or_fr != old_LOCAL_top_or_fr){
109 FREE_OR_FRAME(LOCAL_top_or_fr);
110 }
111 } else {
112 OrFr_qg_solutions(LOCAL_top_or_fr) = NULL;
113#ifdef TABLING_INNER_CUTS
114 OrFr_tg_solutions(LOCAL_top_or_fr) = NULL;
115#endif /* TABLING_INNER_CUTS */
116 OrFr_alternative(LOCAL_top_or_fr) = NULL;
117 BITMAP_delete(OrFr_members(LOCAL_top_or_fr), worker_id);
118#ifdef TABLING
119 OrFr_owners(LOCAL_top_or_fr)--;
120#endif /* TABLING */
121 if(!pend_ltt || LOCAL_top_or_fr != old_LOCAL_top_or_fr)
122 UNLOCK_OR_FRAME(LOCAL_top_or_fr);
123 }
124 if ((aux_qg_solutions = CUT_prune_solution_frames(aux_qg_solutions, ltt))) {
125 CUT_join_answers_in_an_unique_frame(aux_qg_solutions);
126 SolFr_next(aux_qg_solutions) = qg_solutions;
127 qg_solutions = aux_qg_solutions;
128 }
129#ifdef TABLING_INNER_CUTS
130 if ((aux_tg_solutions = CUT_prune_tg_solution_frames(aux_tg_solutions, ltt))) {
131 CUT_join_tg_solutions(& tg_solutions, aux_tg_solutions);
132 }
133#endif /* TABLING_INNER_CUTS */
134 SCH_update_local_or_tops();
135 } while (Get_LOCAL_top_cp() != prune_cp);
136
137
138 if(pend_ltt){
139 UNLOCK_OR_FRAME(old_LOCAL_top_or_fr);
140 if (BITMAP_alone(OrFr_members(old_LOCAL_top_or_fr), worker_id)){
141 FREE_OR_FRAME(old_LOCAL_top_or_fr);
142 }
143 }
144
145
146 YAPOR_ERROR_CHECKING(prune_shared_branch, Get_LOCAL_prune_request() && EQUAL_OR_YOUNGER_CP(Get_LOCAL_prune_request(), Get_LOCAL_top_cp()));
147 /* store answers not pruned */
148 if (qg_solutions)
149 CUT_join_answers_in_an_unique_frame(qg_solutions);
150 LOCK_OR_FRAME(leftmost_or_fr);
151 if (Get_LOCAL_prune_request()) {
152 UNLOCK_OR_FRAME(leftmost_or_fr);
153 if (qg_solutions)
154 CUT_free_solution_frame(qg_solutions);
155#ifdef TABLING_INNER_CUTS
156 CUT_free_tg_solution_frames(tg_solutions);
157#endif /* TABLING_INNER_CUTS */
158 } else {
159 if (qg_solutions)
160 CUT_store_answers(leftmost_or_fr, qg_solutions);
161#ifdef TABLING_INNER_CUTS
162 if (tg_solutions)
163 tg_solutions = CUT_store_tg_answers(leftmost_or_fr, tg_solutions, BRANCH_LTT(worker_id, OrFr_depth(leftmost_or_fr)));
164#endif /* TABLING_INNER_CUTS */
165 UNLOCK_OR_FRAME(leftmost_or_fr);
166#ifdef TABLING_INNER_CUTS
167 CUT_validate_tg_answers(tg_solutions);
168#endif /* TABLING_INNER_CUTS */
169 }
170 } else {
171 /* pruning not being leftmost */
172 int prune_more;
173 prune_more = 1;
174
175 bitmap members2;
176 or_fr_ptr old_LOCAL_top_or_fr = LOCAL_top_or_fr;
177
178 if(pend_ltt){
179 LOCK_OR_FRAME(LOCAL_top_or_fr);
180 int depth2 = OrFr_depth(LOCAL_top_or_fr);
181 members2 = OrFr_members(LOCAL_top_or_fr);
182 for (i = 0; i < GLOBAL_number_workers; i++) {
183 if (BITMAP_member(members2, i) && *pend_ltt != BRANCH_LTT(i,depth2)){
184 BITMAP_delete(members2,i);
185 }
186 }
187 }
188
189
190 /* send prune requests */
191 depth = OrFr_depth(leftmost_or_fr);
192 ltt = BRANCH_LTT(worker_id, depth);
193 if(!pend_ltt || LOCAL_top_or_fr != leftmost_or_fr)
194 LOCK_OR_FRAME(leftmost_or_fr);
195 members = OrFr_members(leftmost_or_fr);
196
197 if(pend_ltt){
198 BITMAP_minus(members,members2);
199 }
200
201
202 BITMAP_delete(members, worker_id);
203 for (i = 0; i < GLOBAL_number_workers; i++) {
204 if (BITMAP_member(members, i)) {
205 if (ltt >= BRANCH_LTT(i, depth)) {
206 CUT_send_prune_request(i, leftmost_cp->cp_b);
207 } else if (BRANCH_CUT(i, depth)) {
208 prune_more = 0;
209 }
210 }
211 }
212 if(!pend_ltt || LOCAL_top_or_fr != leftmost_or_fr)
213 UNLOCK_OR_FRAME(leftmost_or_fr);
214
215 /* move up to leftmost_cp */
216 while (Get_LOCAL_top_cp() != leftmost_cp) {
217 ltt = BRANCH_LTT(worker_id, OrFr_depth(LOCAL_top_or_fr));
218 if(!pend_ltt || LOCAL_top_or_fr != old_LOCAL_top_or_fr)
219 LOCK_OR_FRAME(LOCAL_top_or_fr);
220 if (Get_OrFr_pend_prune_cp(LOCAL_top_or_fr))
221 prune_more = 0;
222 if (Get_OrFr_pend_prune_cp(LOCAL_top_or_fr)){
223 Set_OrFr_pend_prune_cp(LOCAL_top_or_fr, NULL);
224 }
225 aux_qg_solutions = OrFr_qg_solutions(LOCAL_top_or_fr);
226#ifdef TABLING_INNER_CUTS
227 aux_tg_solutions = OrFr_tg_solutions(LOCAL_top_or_fr);
228#endif /* TABLING_INNER_CUTS */
229 if (BITMAP_alone(OrFr_members(LOCAL_top_or_fr), worker_id)) {
230#ifdef TABLING
231 if (OrFr_suspensions(LOCAL_top_or_fr) || OrFr_owners(LOCAL_top_or_fr) != 1)
232 pruning_over_tabling_data_structures();
233#endif /* TABLING */
234 if(!pend_ltt || LOCAL_top_or_fr != old_LOCAL_top_or_fr){
235 FREE_OR_FRAME(LOCAL_top_or_fr);
236 }
237 } else {
238 OrFr_qg_solutions(LOCAL_top_or_fr) = NULL;
239#ifdef TABLING_INNER_CUTS
240 OrFr_tg_solutions(LOCAL_top_or_fr) = NULL;
241#endif /* TABLING_INNER_CUTS */
242 OrFr_alternative(LOCAL_top_or_fr) = NULL;
243 BITMAP_delete(OrFr_members(LOCAL_top_or_fr), worker_id);
244#ifdef TABLING
245 OrFr_owners(LOCAL_top_or_fr)--;
246#endif /* TABLING */
247 if(!pend_ltt || LOCAL_top_or_fr != old_LOCAL_top_or_fr)
248 UNLOCK_OR_FRAME(LOCAL_top_or_fr);
249 }
250 if ((aux_qg_solutions = CUT_prune_solution_frames(aux_qg_solutions, ltt))) {
251 CUT_join_answers_in_an_unique_frame(aux_qg_solutions);
252 SolFr_next(aux_qg_solutions) = qg_solutions;
253 qg_solutions = aux_qg_solutions;
254 }
255#ifdef TABLING_INNER_CUTS
256 if ((aux_tg_solutions = CUT_prune_tg_solution_frames(aux_tg_solutions, ltt))) {
257 CUT_join_tg_solutions(& tg_solutions, aux_tg_solutions);
258 }
259#endif /* TABLING_INNER_CUTS */
260 SCH_update_local_or_tops();
261 }
262
263 if(pend_ltt){
264 UNLOCK_OR_FRAME(old_LOCAL_top_or_fr);
265 if (BITMAP_alone(OrFr_members(old_LOCAL_top_or_fr), worker_id)){
266 FREE_OR_FRAME(old_LOCAL_top_or_fr);
267 }
268 }
269
270 YAPOR_ERROR_CHECKING(prune_shared_branch, Get_LOCAL_prune_request() && EQUAL_OR_YOUNGER_CP(Get_LOCAL_prune_request(), Get_LOCAL_top_cp()));
271 /* store answers not pruned */
272 if (qg_solutions)
273 CUT_join_answers_in_an_unique_frame(qg_solutions);
274 LOCK_OR_FRAME(leftmost_or_fr);
275 if (Get_LOCAL_prune_request()) {
276 UNLOCK_OR_FRAME(leftmost_or_fr);
277 if (qg_solutions)
278 CUT_free_solution_frame(qg_solutions);
279#ifdef TABLING_INNER_CUTS
280 CUT_free_tg_solution_frames(tg_solutions);
281#endif /* TABLING_INNER_CUTS */
282 } else {
283 ltt = BRANCH_LTT(worker_id, depth);
284 if (qg_solutions)
285 CUT_store_answers(leftmost_or_fr, qg_solutions);
286#ifdef TABLING_INNER_CUTS
287 if (tg_solutions)
288 tg_solutions = CUT_store_tg_answers(leftmost_or_fr, tg_solutions, ltt);
289#endif /* TABLING_INNER_CUTS */
290 if (Get_OrFr_pend_prune_cp(leftmost_or_fr))
291 prune_more = 0;
292 OrFr_alternative(leftmost_or_fr) = NULL;
293 if (!Get_LOCAL_prune_request()){
294 Set_OrFr_pend_prune_cp(leftmost_or_fr, prune_cp);
295 OrFr_pend_prune_ltt(leftmost_or_fr) = ltt;
296 }
297 UNLOCK_OR_FRAME(leftmost_or_fr);
298#ifdef TABLING_INNER_CUTS
299 CUT_validate_tg_answers(tg_solutions);
300#endif /* TABLING_INNER_CUTS */
301
302 /* continue pruning to prune_cp */
303 if (prune_more) {
304 BITMAP_copy(members, OrFr_members(leftmost_or_fr));
305 leftmost_cp = leftmost_cp->cp_b;
306 while (leftmost_cp != prune_cp) {
307 leftmost_or_fr = leftmost_cp->cp_or_fr;
308 depth = OrFr_depth(leftmost_or_fr);
309 ltt = BRANCH_LTT(worker_id, depth);
310 LOCK_OR_FRAME(leftmost_or_fr);
311 BITMAP_difference(members, OrFr_members(leftmost_or_fr), members);
312 for (i = 0; i < GLOBAL_number_workers; i++) {
313 if (BITMAP_member(members, i)) {
314 if (ltt > BRANCH_LTT(i, depth)) {
315 CUT_send_prune_request(i, leftmost_cp->cp_b);
316 } else if (BRANCH_CUT(i, depth)) {
317 UNLOCK_OR_FRAME(leftmost_or_fr);
318 goto end_prune_more;
319 }
320 }
321 }
322 OrFr_alternative(leftmost_or_fr) = NULL;
323 UNLOCK_OR_FRAME(leftmost_or_fr);
324 BITMAP_copy(members, OrFr_members(leftmost_or_fr));
325 leftmost_cp = leftmost_cp->cp_b;
326 }
327 }
328 }
329 }
330
331end_prune_more:
332 CUT_reset_prune_request();
333#ifdef TABLING
334 Set_LOCAL_top_cp_on_stack(Get_LOCAL_top_cp());
335#endif /* TABLING */
336 return;
337}
338#endif /* YAPOR */
Yap.h
Main definitions.
or_frame
Definition: or.structs.h:61
query_goal_solution_frame
Definition: or.structs.h:135