X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=polytope_scan.c;h=959451585fefcfd4c113e701da8bb70bd5511f9d;hb=de51a9bc4da5dd3f1f9f57c2362da6f9752c44e0;hp=a69ba9c40698bb3cdbee70cfbaca68ad2f3f9164;hpb=25bb62bddba1a2724360885854ac3aeefba6947f;p=platform%2Fupstream%2Fisl.git diff --git a/polytope_scan.c b/polytope_scan.c index a69ba9c..9594515 100644 --- a/polytope_scan.c +++ b/polytope_scan.c @@ -1,9 +1,18 @@ +/* + * Copyright 2008-2009 Katholieke Universiteit Leuven + * + * Use of this software is governed by the MIT license + * + * Written by Sven Verdoolaege, K.U.Leuven, Departement + * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium + */ + #include -#include "isl_basis_reduction.h" +#include #include "isl_equalities.h" -#include "isl_seq.h" -#include "isl_tab.h" -#include "isl_vec.h" +#include +#include "isl_scan.h" +#include /* The input of this program is the same as that of the "polytope_scan" * program from the barvinok distribution. @@ -13,170 +22,80 @@ * The input set is assumed to be bounded. */ -static struct isl_mat *isl_basic_set_samples(struct isl_basic_set *bset); - -static struct isl_mat *samples_eq(struct isl_basic_set *bset) -{ - struct isl_mat *T; +struct scan_samples { + struct isl_scan_callback callback; struct isl_mat *samples; +}; - bset = isl_basic_set_remove_equalities(bset, &T, NULL); - samples = isl_basic_set_samples(bset); - return isl_mat_product(samples, isl_mat_transpose(T)); -} - -/* Add the current sample value of the tableau "tab" to the list - * in "samples". - */ -static struct isl_mat *add_solution(struct isl_mat *samples, - struct isl_tab *tab) +static int scan_samples_add_sample(struct isl_scan_callback *cb, + __isl_take isl_vec *sample) { - struct isl_vec *sample; + struct scan_samples *ss = (struct scan_samples *)cb; - if (!samples || !tab) - goto error; - samples = isl_mat_extend(samples, samples->n_row + 1, samples->n_col); - if (!samples) - return NULL; - sample = isl_tab_get_sample_value(tab); - if (!sample) + ss->samples = isl_mat_extend(ss->samples, ss->samples->n_row + 1, + ss->samples->n_col); + if (!ss->samples) goto error; - isl_seq_cpy(samples->row[samples->n_row - 1], sample->el, sample->size); + + isl_seq_cpy(ss->samples->row[ss->samples->n_row - 1], + sample->el, sample->size); + isl_vec_free(sample); - return samples; + return 0; error: - isl_mat_free(samples); - return NULL; + isl_vec_free(sample); + return -1; } -/* Look for and return all integer points in "bset", which is assumed - * to be unbounded. - * - * We first compute a reduced basis for the set and then scan - * the set in the directions of this basis. - * We basically perform a depth first search, where in each level i - * we compute the range in the i-th basis vector direction, given - * fixed values in the directions of the previous basis vector. - * We then add an equality to the tableau fixing the value in the - * direction of the current basis vector to each value in the range - * in turn and then continue to the next level. - * - * The search is implemented iteratively. "level" identifies the current - * basis vector. "init" is true if we want the first value at the current - * level and false if we want the next value. - * Solutions are added in the leaves of the search tree, i.e., after - * we have fixed a value in each direction of the basis. - */ -static struct isl_mat *isl_basic_set_samples(struct isl_basic_set *bset) +static struct isl_mat *isl_basic_set_scan_samples(struct isl_basic_set *bset) { + isl_ctx *ctx; unsigned dim; - struct isl_mat *B = NULL; - struct isl_tab *tab = NULL; - struct isl_vec *min; - struct isl_vec *max; - struct isl_mat *samples; - struct isl_tab_undo **snap; - int level; - int init; - enum isl_lp_result res; - - if (bset->n_eq) - return samples_eq(bset); + struct scan_samples ss; + ctx = isl_basic_set_get_ctx(bset); dim = isl_basic_set_total_dim(bset); - - min = isl_vec_alloc(bset->ctx, dim); - max = isl_vec_alloc(bset->ctx, dim); - samples = isl_mat_alloc(bset->ctx, 0, 1 + dim); - snap = isl_alloc_array(bset->ctx, struct isl_tab_undo *, dim); - - if (!min || !max || !samples || !snap) - goto error; - - tab = isl_tab_from_basic_set(bset); - - if (1) - B = isl_tab_reduced_basis(tab); - else - B = isl_mat_identity(bset->ctx, dim); - B = isl_mat_lin_to_aff(B); - if (!B) + ss.callback.add = scan_samples_add_sample; + ss.samples = isl_mat_alloc(ctx, 0, 1 + dim); + if (!ss.samples) goto error; - level = 0; - init = 1; - - while (level >= 0) { - int empty = 0; - if (init) { - res = isl_tab_min(tab, B->row[1 + level], - bset->ctx->one, &min->el[level], NULL, 0); - if (res == isl_lp_empty) - empty = 1; - if (res == isl_lp_error || res == isl_lp_unbounded) - goto error; - isl_seq_neg(B->row[1 + level] + 1, - B->row[1 + level] + 1, dim); - res = isl_tab_min(tab, B->row[1 + level], - bset->ctx->one, &max->el[level], NULL, 0); - isl_seq_neg(B->row[1 + level] + 1, - B->row[1 + level] + 1, dim); - isl_int_neg(max->el[level], max->el[level]); - if (res == isl_lp_empty) - empty = 1; - if (res == isl_lp_error || res == isl_lp_unbounded) - goto error; - snap[level] = isl_tab_snap(tab); - } else - isl_int_add_ui(min->el[level], min->el[level], 1); - - if (empty || isl_int_gt(min->el[level], max->el[level])) { - level--; - init = 0; - if (level >= 0) - isl_tab_rollback(tab, snap[level]); - continue; - } - isl_int_neg(B->row[1 + level][0], min->el[level]); - tab = isl_tab_add_valid_eq(tab, B->row[1 + level]); - isl_int_set_si(B->row[1 + level][0], 0); - if (level < dim - 1) { - ++level; - init = 1; - continue; - } - samples = add_solution(samples, tab); - init = 0; - isl_tab_rollback(tab, snap[level]); + if (isl_basic_set_scan(bset, &ss.callback) < 0) { + isl_mat_free(ss.samples); + return NULL; } - isl_tab_free(tab); - free(snap); - isl_vec_free(min); - isl_vec_free(max); - isl_basic_set_free(bset); - isl_mat_free(B); - return samples; + return ss.samples; error: - isl_tab_free(tab); - free(snap); - isl_mat_free(samples); - isl_vec_free(min); - isl_vec_free(max); isl_basic_set_free(bset); - isl_mat_free(B); return NULL; } +static struct isl_mat *isl_basic_set_samples(struct isl_basic_set *bset) +{ + struct isl_mat *T; + struct isl_mat *samples; + + if (!bset) + return NULL; + + if (bset->n_eq == 0) + return isl_basic_set_scan_samples(bset); + + bset = isl_basic_set_remove_equalities(bset, &T, NULL); + samples = isl_basic_set_scan_samples(bset); + return isl_mat_product(samples, isl_mat_transpose(T)); +} + int main(int argc, char **argv) { struct isl_ctx *ctx = isl_ctx_alloc(); struct isl_basic_set *bset; struct isl_mat *samples; - bset = isl_basic_set_read_from_file(ctx, stdin, 0, ISL_FORMAT_POLYLIB); + bset = isl_basic_set_read_from_file(ctx, stdin); samples = isl_basic_set_samples(bset); - isl_mat_dump(samples, stdout, 0); + isl_mat_print_internal(samples, stdout, 0); isl_mat_free(samples); isl_ctx_free(ctx);