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 
prune_shared_branch(choiceptr prune_cp)33 void prune_shared_branch(choiceptr prune_cp) {
34   int i, ltt, depth;
35   bitmap members;
36   choiceptr leftmost_cp;
37   or_fr_ptr leftmost_or_fr;
38   qg_sol_fr_ptr qg_solutions, aux_qg_solutions;
39 #ifdef TABLING_INNER_CUTS
40   tg_sol_fr_ptr tg_solutions, aux_tg_solutions;
41 #endif /* TABLING_INNER_CUTS */
42 
43   leftmost_or_fr = CUT_leftmost_or_frame();
44   leftmost_cp = GetOrFr_node(leftmost_or_fr);
45   qg_solutions = NULL;
46 #ifdef TABLING_INNER_CUTS
47   tg_solutions = NULL;
48 #endif /* TABLING_INNER_CUTS */
49   if (EQUAL_OR_YOUNGER_CP(prune_cp, leftmost_cp)) {
50     /* pruning being leftmost */
51     or_fr_ptr prune_or_fr;
52 
53     /* send prune requests */
54     prune_or_fr = prune_cp->cp_or_fr;
55     depth = OrFr_depth(prune_or_fr);
56     ltt = BRANCH_LTT(worker_id, depth);
57     LOCK_OR_FRAME(prune_or_fr);
58     members = OrFr_members(prune_or_fr);
59     BITMAP_delete(members, worker_id);
60     for (i = 0; i < number_workers; i++) {
61       if (BITMAP_member(members, i) && ltt == BRANCH_LTT(i, depth)) {
62         CUT_send_prune_request(i, prune_cp);
63       }
64     }
65     UNLOCK_OR_FRAME(prune_or_fr);
66 
67     /* move up to prune_cp */
68     do {
69       ltt = BRANCH_LTT(worker_id, OrFr_depth(LOCAL_top_or_fr));
70       LOCK_OR_FRAME(LOCAL_top_or_fr);
71       aux_qg_solutions = OrFr_qg_solutions(LOCAL_top_or_fr);
72 #ifdef TABLING_INNER_CUTS
73       aux_tg_solutions = OrFr_tg_solutions(LOCAL_top_or_fr);
74 #endif /* TABLING_INNER_CUTS */
75       if (BITMAP_alone(OrFr_members(LOCAL_top_or_fr), worker_id)) {
76 #ifdef TABLING
77         if (OrFr_suspensions(LOCAL_top_or_fr) || OrFr_owners(LOCAL_top_or_fr) != 1)
78           pruning_over_tabling_data_structures();
79 #endif /* TABLING */
80         FREE_OR_FRAME(LOCAL_top_or_fr);
81       } else {
82         OrFr_qg_solutions(LOCAL_top_or_fr) = NULL;
83 #ifdef TABLING_INNER_CUTS
84         OrFr_tg_solutions(LOCAL_top_or_fr) = NULL;
85 #endif /* TABLING_INNER_CUTS */
86         OrFr_alternative(LOCAL_top_or_fr) = NULL;
87         BITMAP_delete(OrFr_members(LOCAL_top_or_fr), worker_id);
88 #ifdef TABLING
89         OrFr_owners(LOCAL_top_or_fr)--;
90 #endif /* TABLING */
91         UNLOCK_OR_FRAME(LOCAL_top_or_fr);
92       }
93       if ((aux_qg_solutions = CUT_prune_solution_frames(aux_qg_solutions, ltt))) {
94         CUT_join_answers_in_an_unique_frame(aux_qg_solutions);
95         SolFr_next(aux_qg_solutions) = qg_solutions;
96         qg_solutions = aux_qg_solutions;
97       }
98 #ifdef TABLING_INNER_CUTS
99       if ((aux_tg_solutions = CUT_prune_tg_solution_frames(aux_tg_solutions, ltt))) {
100         CUT_join_tg_solutions(& tg_solutions, aux_tg_solutions);
101       }
102 #endif /* TABLING_INNER_CUTS */
103       SCH_update_local_or_tops();
104     } while (Get_LOCAL_top_cp() != prune_cp);
105 
106     YAPOR_ERROR_CHECKING(prune_shared_branch, Get_LOCAL_prune_request() && EQUAL_OR_YOUNGER_CP(Get_LOCAL_prune_request(), Get_LOCAL_top_cp()));
107     /* store answers not pruned */
108     if (qg_solutions)
109       CUT_join_answers_in_an_unique_frame(qg_solutions);
110     LOCK_OR_FRAME(leftmost_or_fr);
111     if (Get_LOCAL_prune_request()) {
112       UNLOCK_OR_FRAME(leftmost_or_fr);
113       if (qg_solutions)
114         CUT_free_solution_frame(qg_solutions);
115 #ifdef TABLING_INNER_CUTS
116       CUT_free_tg_solution_frames(tg_solutions);
117 #endif /* TABLING_INNER_CUTS */
118     } else {
119       if (qg_solutions)
120         CUT_store_answers(leftmost_or_fr, qg_solutions);
121 #ifdef TABLING_INNER_CUTS
122       if (tg_solutions)
123         tg_solutions = CUT_store_tg_answers(leftmost_or_fr, tg_solutions, BRANCH_LTT(worker_id, OrFr_depth(leftmost_or_fr)));
124 #endif /* TABLING_INNER_CUTS */
125       UNLOCK_OR_FRAME(leftmost_or_fr);
126 #ifdef TABLING_INNER_CUTS
127       CUT_validate_tg_answers(tg_solutions);
128 #endif /* TABLING_INNER_CUTS */
129     }
130   } else {
131     /* pruning not being leftmost */
132     int prune_more;
133     prune_more = 1;
134 
135     /* send prune requests */
136     depth = OrFr_depth(leftmost_or_fr);
137     ltt = BRANCH_LTT(worker_id, depth);
138     LOCK_OR_FRAME(leftmost_or_fr);
139     members = OrFr_members(leftmost_or_fr);
140     BITMAP_delete(members, worker_id);
141     for (i = 0; i < number_workers; i++) {
142       if (BITMAP_member(members, i)) {
143         if (ltt >= BRANCH_LTT(i, depth)) {
144           CUT_send_prune_request(i, leftmost_cp->cp_b);
145         } else if (BRANCH_CUT(i, depth)) {
146           prune_more = 0;
147         }
148       }
149     }
150     UNLOCK_OR_FRAME(leftmost_or_fr);
151 
152     /* move up to leftmost_cp */
153     while (Get_LOCAL_top_cp() != leftmost_cp) {
154       ltt = BRANCH_LTT(worker_id, OrFr_depth(LOCAL_top_or_fr));
155       LOCK_OR_FRAME(LOCAL_top_or_fr);
156       if (Get_OrFr_pend_prune_cp(LOCAL_top_or_fr))
157         prune_more = 0;
158       aux_qg_solutions = OrFr_qg_solutions(LOCAL_top_or_fr);
159 #ifdef TABLING_INNER_CUTS
160       aux_tg_solutions = OrFr_tg_solutions(LOCAL_top_or_fr);
161 #endif /* TABLING_INNER_CUTS */
162       if (BITMAP_alone(OrFr_members(LOCAL_top_or_fr), worker_id)) {
163 #ifdef TABLING
164         if (OrFr_suspensions(LOCAL_top_or_fr) || OrFr_owners(LOCAL_top_or_fr) != 1)
165           pruning_over_tabling_data_structures();
166 #endif /* TABLING */
167         FREE_OR_FRAME(LOCAL_top_or_fr);
168       } else {
169         OrFr_qg_solutions(LOCAL_top_or_fr) = NULL;
170 #ifdef TABLING_INNER_CUTS
171         OrFr_tg_solutions(LOCAL_top_or_fr) = NULL;
172 #endif /* TABLING_INNER_CUTS */
173         OrFr_alternative(LOCAL_top_or_fr) = NULL;
174         BITMAP_delete(OrFr_members(LOCAL_top_or_fr), worker_id);
175 #ifdef TABLING
176         OrFr_owners(LOCAL_top_or_fr)--;
177 #endif /* TABLING */
178         UNLOCK_OR_FRAME(LOCAL_top_or_fr);
179       }
180       if ((aux_qg_solutions = CUT_prune_solution_frames(aux_qg_solutions, ltt))) {
181         CUT_join_answers_in_an_unique_frame(aux_qg_solutions);
182         SolFr_next(aux_qg_solutions) = qg_solutions;
183         qg_solutions = aux_qg_solutions;
184       }
185 #ifdef TABLING_INNER_CUTS
186       if ((aux_tg_solutions = CUT_prune_tg_solution_frames(aux_tg_solutions, ltt))) {
187         CUT_join_tg_solutions(& tg_solutions, aux_tg_solutions);
188       }
189 #endif /* TABLING_INNER_CUTS */
190       SCH_update_local_or_tops();
191     }
192 
193     YAPOR_ERROR_CHECKING(prune_shared_branch, Get_LOCAL_prune_request() && EQUAL_OR_YOUNGER_CP(Get_LOCAL_prune_request(), Get_LOCAL_top_cp()));
194     /* store answers not pruned */
195     if (qg_solutions)
196       CUT_join_answers_in_an_unique_frame(qg_solutions);
197     LOCK_OR_FRAME(leftmost_or_fr);
198     if (Get_LOCAL_prune_request()) {
199       UNLOCK_OR_FRAME(leftmost_or_fr);
200       if (qg_solutions)
201         CUT_free_solution_frame(qg_solutions);
202 #ifdef TABLING_INNER_CUTS
203       CUT_free_tg_solution_frames(tg_solutions);
204 #endif /* TABLING_INNER_CUTS */
205     } else {
206       ltt = BRANCH_LTT(worker_id, depth);
207       if (qg_solutions)
208         CUT_store_answers(leftmost_or_fr, qg_solutions);
209 #ifdef TABLING_INNER_CUTS
210       if (tg_solutions)
211         tg_solutions = CUT_store_tg_answers(leftmost_or_fr, tg_solutions, ltt);
212 #endif /* TABLING_INNER_CUTS */
213       if (Get_OrFr_pend_prune_cp(leftmost_or_fr))
214         prune_more = 0;
215       OrFr_alternative(leftmost_or_fr) = NULL;
216       Set_OrFr_pend_prune_cp(leftmost_or_fr, prune_cp);
217       OrFr_pend_prune_ltt(leftmost_or_fr) = ltt;
218       UNLOCK_OR_FRAME(leftmost_or_fr);
219 #ifdef TABLING_INNER_CUTS
220       CUT_validate_tg_answers(tg_solutions);
221 #endif /* TABLING_INNER_CUTS */
222 
223       /* continue pruning to prune_cp */
224       if (prune_more) {
225         BITMAP_copy(members, OrFr_members(leftmost_or_fr));
226         leftmost_cp = leftmost_cp->cp_b;
227         while (leftmost_cp != prune_cp) {
228           leftmost_or_fr = leftmost_cp->cp_or_fr;
229           depth = OrFr_depth(leftmost_or_fr);
230           ltt = BRANCH_LTT(worker_id, depth);
231           LOCK_OR_FRAME(leftmost_or_fr);
232           BITMAP_difference(members, OrFr_members(leftmost_or_fr), members);
233           for (i = 0; i < number_workers; i++) {
234             if (BITMAP_member(members, i)) {
235               if (ltt > BRANCH_LTT(i, depth)) {
236                 CUT_send_prune_request(i, leftmost_cp->cp_b);
237               } else if (BRANCH_CUT(i, depth)) {
238                 UNLOCK_OR_FRAME(leftmost_or_fr);
239                 goto end_prune_more;
240               }
241 	    }
242 	  }
243           OrFr_alternative(leftmost_or_fr) = NULL;
244           UNLOCK_OR_FRAME(leftmost_or_fr);
245           BITMAP_copy(members, OrFr_members(leftmost_or_fr));
246           leftmost_cp = leftmost_cp->cp_b;
247         }
248       }
249     }
250   }
251 
252 end_prune_more:
253   CUT_reset_prune_request();
254 #ifdef TABLING
255   Set_LOCAL_top_cp_on_stack(Get_LOCAL_top_cp());
256 #endif /* TABLING */
257 
258   return;
259 }
260 #endif /* YAPOR */
261