isl_tab_add_valid_eq: return int instead of isl_tab *
[platform/upstream/isl.git] / isl_scan.c
1 /*
2  * Copyright 2008-2009 Katholieke Universiteit Leuven
3  *
4  * Use of this software is governed by the GNU LGPLv2.1 license
5  *
6  * Written by Sven Verdoolaege, K.U.Leuven, Departement
7  * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
8  */
9
10 #include "isl_basis_reduction.h"
11 #include "isl_scan.h"
12 #include "isl_seq.h"
13 #include "isl_tab.h"
14 #include <isl_map_private.h>
15
16 struct isl_counter {
17         struct isl_scan_callback callback;
18         isl_int count;
19         isl_int max;
20 };
21
22 static int increment_counter(struct isl_scan_callback *cb,
23         __isl_take isl_vec *sample)
24 {
25         struct isl_counter *cnt = (struct isl_counter *)cb;
26
27         isl_int_add_ui(cnt->count, cnt->count, 1);
28
29         isl_vec_free(sample);
30
31         if (isl_int_is_zero(cnt->max) || isl_int_lt(cnt->count, cnt->max))
32                 return 0;
33         return -1;
34 }
35
36 static int increment_range(struct isl_scan_callback *cb, isl_int min, isl_int max)
37 {
38         struct isl_counter *cnt = (struct isl_counter *)cb;
39
40         isl_int_add(cnt->count, cnt->count, max);
41         isl_int_sub(cnt->count, cnt->count, min);
42         isl_int_add_ui(cnt->count, cnt->count, 1);
43
44         if (isl_int_is_zero(cnt->max) || isl_int_lt(cnt->count, cnt->max))
45                 return 0;
46         isl_int_set(cnt->count, cnt->max);
47         return -1;
48 }
49
50 /* Call callback->add with the current sample value of the tableau "tab".
51  */
52 static int add_solution(struct isl_tab *tab, struct isl_scan_callback *callback)
53 {
54         struct isl_vec *sample;
55
56         if (!tab)
57                 return -1;
58         sample = isl_tab_get_sample_value(tab);
59         if (!sample)
60                 return -1;
61
62         return callback->add(callback, sample);
63 }
64
65 static int scan_0D(struct isl_basic_set *bset,
66         struct isl_scan_callback *callback)
67 {
68         struct isl_vec *sample;
69
70         sample = isl_vec_alloc(bset->ctx, 1);
71         isl_basic_set_free(bset);
72
73         if (!sample)
74                 return -1;
75
76         isl_int_set_si(sample->el[0], 1);
77
78         return callback->add(callback, sample);
79 }
80
81 /* Look for all integer points in "bset", which is assumed to be unbounded,
82  * and call callback->add on each of them.
83  *
84  * We first compute a reduced basis for the set and then scan
85  * the set in the directions of this basis.
86  * We basically perform a depth first search, where in each level i
87  * we compute the range in the i-th basis vector direction, given
88  * fixed values in the directions of the previous basis vector.
89  * We then add an equality to the tableau fixing the value in the
90  * direction of the current basis vector to each value in the range
91  * in turn and then continue to the next level.
92  *
93  * The search is implemented iteratively.  "level" identifies the current
94  * basis vector.  "init" is true if we want the first value at the current
95  * level and false if we want the next value.
96  * Solutions are added in the leaves of the search tree, i.e., after
97  * we have fixed a value in each direction of the basis.
98  */
99 int isl_basic_set_scan(struct isl_basic_set *bset,
100         struct isl_scan_callback *callback)
101 {
102         unsigned dim;
103         struct isl_mat *B = NULL;
104         struct isl_tab *tab = NULL;
105         struct isl_vec *min;
106         struct isl_vec *max;
107         struct isl_tab_undo **snap;
108         int level;
109         int init;
110         enum isl_lp_result res;
111
112         if (!bset)
113                 return -1;
114
115         dim = isl_basic_set_total_dim(bset);
116         if (dim == 0)
117                 return scan_0D(bset, callback);
118
119         min = isl_vec_alloc(bset->ctx, dim);
120         max = isl_vec_alloc(bset->ctx, dim);
121         snap = isl_alloc_array(bset->ctx, struct isl_tab_undo *, dim);
122
123         if (!min || !max || !snap)
124                 goto error;
125
126         tab = isl_tab_from_basic_set(bset);
127         if (!tab)
128                 goto error;
129         if (isl_tab_extend_cons(tab, dim + 1) < 0)
130                 goto error;
131
132         tab->basis = isl_mat_identity(bset->ctx, 1 + dim);
133         if (1)
134                 tab = isl_tab_compute_reduced_basis(tab);
135         if (!tab)
136                 goto error;
137         B = isl_mat_copy(tab->basis);
138         if (!B)
139                 goto error;
140
141         level = 0;
142         init = 1;
143
144         while (level >= 0) {
145                 int empty = 0;
146                 if (init) {
147                         res = isl_tab_min(tab, B->row[1 + level],
148                                     bset->ctx->one, &min->el[level], NULL, 0);
149                         if (res == isl_lp_empty)
150                                 empty = 1;
151                         if (res == isl_lp_error || res == isl_lp_unbounded)
152                                 goto error;
153                         isl_seq_neg(B->row[1 + level] + 1,
154                                     B->row[1 + level] + 1, dim);
155                         res = isl_tab_min(tab, B->row[1 + level],
156                                     bset->ctx->one, &max->el[level], NULL, 0);
157                         isl_seq_neg(B->row[1 + level] + 1,
158                                     B->row[1 + level] + 1, dim);
159                         isl_int_neg(max->el[level], max->el[level]);
160                         if (res == isl_lp_empty)
161                                 empty = 1;
162                         if (res == isl_lp_error || res == isl_lp_unbounded)
163                                 goto error;
164                         snap[level] = isl_tab_snap(tab);
165                 } else
166                         isl_int_add_ui(min->el[level], min->el[level], 1);
167
168                 if (empty || isl_int_gt(min->el[level], max->el[level])) {
169                         level--;
170                         init = 0;
171                         if (level >= 0)
172                                 if (isl_tab_rollback(tab, snap[level]) < 0)
173                                         goto error;
174                         continue;
175                 }
176                 if (level == dim - 1 && callback->add == increment_counter) {
177                         if (increment_range(callback,
178                                             min->el[level], max->el[level]))
179                                 goto error;
180                         level--;
181                         init = 0;
182                         if (level >= 0)
183                                 if (isl_tab_rollback(tab, snap[level]) < 0)
184                                         goto error;
185                         continue;
186                 }
187                 isl_int_neg(B->row[1 + level][0], min->el[level]);
188                 if (isl_tab_add_valid_eq(tab, B->row[1 + level]) < 0)
189                         goto error;
190                 isl_int_set_si(B->row[1 + level][0], 0);
191                 if (level < dim - 1) {
192                         ++level;
193                         init = 1;
194                         continue;
195                 }
196                 if (add_solution(tab, callback) < 0)
197                         goto error;
198                 init = 0;
199                 if (isl_tab_rollback(tab, snap[level]) < 0)
200                         goto error;
201         }
202
203         isl_tab_free(tab);
204         free(snap);
205         isl_vec_free(min);
206         isl_vec_free(max);
207         isl_basic_set_free(bset);
208         isl_mat_free(B);
209         return 0;
210 error:
211         isl_tab_free(tab);
212         free(snap);
213         isl_vec_free(min);
214         isl_vec_free(max);
215         isl_basic_set_free(bset);
216         isl_mat_free(B);
217         return -1;
218 }
219
220 int isl_set_scan(__isl_take isl_set *set, struct isl_scan_callback *callback)
221 {
222         int i;
223
224         if (!set || !callback)
225                 goto error;
226
227         set = isl_set_cow(set);
228         set = isl_set_make_disjoint(set);
229         set = isl_set_compute_divs(set);
230         if (!set)
231                 goto error;
232
233         for (i = 0; i < set->n; ++i)
234                 if (isl_basic_set_scan(isl_basic_set_copy(set->p[i]),
235                                         callback) < 0)
236                         goto error;
237
238         isl_set_free(set);
239         return 0;
240 error:
241         isl_set_free(set);
242         return -1;
243 }
244
245 int isl_set_count_upto(__isl_keep isl_set *set, isl_int max, isl_int *count)
246 {
247         struct isl_counter cnt = { { &increment_counter } };
248
249         if (!set)
250                 return -1;
251
252         isl_int_init(cnt.count);
253         isl_int_init(cnt.max);
254
255         isl_int_set_si(cnt.count, 0);
256         isl_int_set(cnt.max, max);
257         if (isl_set_scan(isl_set_copy(set), &cnt.callback) < 0 &&
258             isl_int_lt(cnt.count, cnt.max))
259                 goto error;
260
261         isl_int_set(*count, cnt.count);
262         isl_int_clear(cnt.max);
263         isl_int_clear(cnt.count);
264
265         return 0;
266 error:
267         isl_int_clear(cnt.count);
268         return -1;
269 }
270
271 int isl_set_count(__isl_keep isl_set *set, isl_int *count)
272 {
273         if (!set)
274                 return -1;
275         return isl_set_count_upto(set, set->ctx->zero, count);
276 }