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