PIPS
|
#include <stdlib.h>
#include <stdio.h>
#include <errno.h>
#include <string.h>
#include <limits.h>
#include <unistd.h>
#include "assert.h"
#include "boolean.h"
#include "vecteur.h"
#include "contrainte.h"
#include "sc.h"
#include "sommet.h"
#include "ray_dte.h"
#include "sg.h"
#include "polyedre.h"
#include "polynome.h"
#include <signal.h>
Go to the source code of this file.
Data Structures | |
struct | zmat_s |
struct | bmat_s |
Macros | |
#define | FPRINT_NBDIGITS 6 |
#define | _STRINGOF(str) #str |
#define | STRINGOF(str) _STRINGOF(str) |
#define | BSWAP(a, b, l) |
#define | SWAP(a, b, t) |
#define | TIMEOUT_ENV "LINEAR_CONVEX_HULL_TIMEOUT" |
#define | WSIZE (8 * sizeof(int)) |
#define | MSB ((unsigned) (((unsigned) 1) << (WSIZE - 1))) |
#define | NEXT(j, b) |
#define | bvec_copy(bvec1, bvec2, nbvals) (memcpy((char*) (bvec2), (char*) (bvec1), (int) ((nbvals) * sizeof(int)))) |
#define | bvec_init(bvec, nbvals) (memset((char*) (bvec), 0, (int) ((nbvals) * sizeof(int)))) |
#define | NBMAXRAYS (20000) |
#define | NBMAXCONSTRS (20000) |
Typedefs | |
typedef struct zmat_s * | zmat_p |
typedef zmat_s | zmat_t[1] |
typedef struct bmat_s * | bmat_p |
typedef bmat_s | bmat_t[1] |
Functions | |
static void *NOWUNUSED | safe_malloc (size_t size) |
static void *NOWUNUSED | safe_realloc (void *ptr, size_t size) |
static void NOWUNUSED | safe_free (void *ptr) |
static int | get_linear_convex_hull_timeout () |
static void | catch_alarm_sc_convex_hull (int sig NOWUNUSED) |
static zval_t * | zvec_alloc (unsigned nbvals) |
static void | zvec_free (zval_t *zvec, unsigned nbvals) |
static void NOWUNUSED | zvec_safe_free (zval_t *zvec, unsigned nbvals) |
static void | zvec_swap (zval_t *zvec1, zval_t *zvec2, unsigned nbvals) |
static void | zvec_set_i (zval_t *zvec, long val, unsigned nbvals) |
static void | zvec_copy (zval_t *zvec1, zval_t *zvec2, unsigned nbvals) |
static void | zvec_combine (zval_t *zvec1, zval_t *zvec2, zval_t *zvec3, zval_t lambda, zval_t mu, unsigned nbvals) |
static void | zvec_antiscale (zval_t *zvec1, zval_t *zvec2, zval_t lambda, unsigned nbvals) |
static void | zvec_neg (zval_t *zvec1, zval_t *zvec2, unsigned nbvals) |
static int | zvec_index_first_notzero (zval_t *zvec, unsigned nbvals) |
static void | zvec_min_notzero (zval_t *zvec, unsigned nbvals, int *pindex, zval_t *pmin) |
static void | zvec_gcd (zval_t *zvec, unsigned nbvals, zval_t *pgcd) |
static void | zvec_normalize (zval_t *zvec, unsigned nbvals) |
static int NOWUNUSED | zvec_fprint (FILE *stream, zval_t *zvec, unsigned nbvals) |
static zmat_p | zmat_alloc (unsigned nbrows, unsigned nbcols) |
static void | zmat_free (zmat_p zmat) |
static void NOWUNUSED | zmat_safe_free (zmat_p zmat) |
static void | zmat_extend (zmat_p zmat, unsigned nbrows) |
static void NOWUNUSED | zmat_fprint (FILE *stream, zmat_p zmat) |
static void | bvec_lor (int *bvec1, int *bvec2, int *bvec3, unsigned nbvals) |
static bmat_p | bmat_alloc (int nbrows, int nbcols) |
static void | bmat_free (bmat_p bmat) |
static void NOWUNUSED | bmat_safe_free (bmat_p bmat) |
static void | bmat_extend (bmat_p bmat, zmat_p zmat, unsigned nbrows) |
static void NOWUNUSED | bmat_fprint (FILE *stream, bmat_p bmat) |
static void | combine (zval_t *zvec1, zval_t *zvec2, zval_t *zvec3, int pos, unsigned nbvals) |
static void | sort_rays (zmat_p rays, bmat_p sat, int nbbrays, int nbrays, int *equal_bound, int *sup_bound, unsigned nbcols1, unsigned nbcols2, unsigned bx, unsigned jx) |
static int | chernikova (zmat_p constrs, zmat_p rays, bmat_p sat, volatile unsigned nbbrays, volatile unsigned nbmaxrays, bool dual) |
static int | gauss (zmat_p zmat, int nbeqs, int nbdims) |
static void | remove_redundants (zmat_p *pconstrs, zmat_p *prays, bmat_p sat) |
static bmat_p | transpose_sat (zmat_p constrs, zmat_p rays, bmat_p sat) |
static zmat_p | rays_of_constrs (zmat_p *pconstrs, unsigned nbmaxrays) |
static zmat_p | constrs_of_rays (zmat_p *prays, unsigned nbmaxconstrs) |
static void | zmat_set_row (zmat_p zmat, unsigned i, int first, Pvecteur pv, int last, Pbase base) |
static Pvecteur | vecteur_of_zvec (zval_t *zvec, Pbase base) |
static zmat_p | constrs_of_sc (Psysteme sc) |
static Psysteme | sc_of_constrs (zmat_p constrs, Pbase base) |
static zmat_p | rays_of_sg (Ptsg sg) |
static Ptsg | sg_of_rays (zmat_p rays, Pbase base) |
static zmat_p NOWUNUSED | rays_of_sc (Psysteme sc, unsigned nbmaxrays) |
static Psysteme NOWUNUSED | sc_of_rays (zmat_p *prays, Pbase base, unsigned nbmaxconstrs) |
static zmat_p NOWUNUSED | constrs_of_sg (Ptsg sg, unsigned nbmaxconstrs) |
static Ptsg NOWUNUSED | sg_of_constrs (zmat_p *pconstrs, Pbase base, unsigned nbmaxrays) |
static Ptsg | sg_of_sc (Psysteme sc) |
static Psysteme | sc_of_sg (Ptsg sg) |
static Psysteme | sc_union (Psysteme sc1, Psysteme sc2) |
Variables | |
static bool | sc_convex_hull_timeout = false |
#define _STRINGOF | ( | str | ) | #str |
Definition at line 50 of file chernikova.h.
#define BSWAP | ( | a, | |
b, | |||
l | |||
) |
Definition at line 80 of file chernikova.h.
#define bvec_copy | ( | bvec1, | |
bvec2, | |||
nbvals | |||
) | (memcpy((char*) (bvec2), (char*) (bvec1), (int) ((nbvals) * sizeof(int)))) |
Definition at line 441 of file chernikova.h.
Definition at line 444 of file chernikova.h.
#define FPRINT_NBDIGITS 6 |
Definition at line 48 of file chernikova.h.
#define MSB ((unsigned) (((unsigned) 1) << (WSIZE - 1))) |
Definition at line 414 of file chernikova.h.
#define NBMAXCONSTRS (20000) |
Definition at line 1436 of file chernikova.h.
#define NBMAXRAYS (20000) |
Definition at line 1435 of file chernikova.h.
#define NEXT | ( | j, | |
b | |||
) |
Definition at line 416 of file chernikova.h.
#define STRINGOF | ( | str | ) | _STRINGOF(str) |
Definition at line 51 of file chernikova.h.
#define SWAP | ( | a, | |
b, | |||
t | |||
) |
Definition at line 88 of file chernikova.h.
#define TIMEOUT_ENV "LINEAR_CONVEX_HULL_TIMEOUT" |
Definition at line 102 of file chernikova.h.
#define WSIZE (8 * sizeof(int)) |
Definition at line 412 of file chernikova.h.
typedef bmat_s bmat_t[1] |
Definition at line 457 of file chernikova.h.
typedef zmat_s zmat_t[1] |
Definition at line 328 of file chernikova.h.
Definition at line 459 of file chernikova.h.
References bmat_s::nbcols, bmat_s::nbrows, bmat_s::rawvals, safe_malloc(), and bmat_s::vals.
Referenced by constrs_of_rays(), rays_of_constrs(), and transpose_sat().
Definition at line 493 of file chernikova.h.
References int, zmat_s::nbrows, bmat_s::nbrows, bmat_s::rawvals, safe_realloc(), bmat_s::vals, and WSIZE.
Referenced by chernikova().
Definition at line 504 of file chernikova.h.
References fprintf(), int, bmat_s::nbcols, bmat_s::nbrows, and bmat_s::vals.
|
static |
Definition at line 479 of file chernikova.h.
References free(), bmat_s::rawvals, and bmat_s::vals.
Referenced by bmat_safe_free(), constrs_of_rays(), and rays_of_constrs().
Definition at line 487 of file chernikova.h.
References bmat_free().
Definition at line 427 of file chernikova.h.
References int.
Referenced by chernikova().
|
static |
Definition at line 123 of file chernikova.h.
References fprintf(), sc_convex_hull_timeout, THROW, and timeout_error.
Referenced by sc_union().
|
static |
Definition at line 618 of file chernikova.h.
References any_exception_error, aux, bmat_extend(), bvec_copy, bvec_lor(), CATCH, combine(), dual(), free(), int, MSB, zmat_s::nbcols, bmat_s::nbcols, zmat_s::nbrows, bmat_s::nbrows, NEXT, redundant(), RETHROW, safe_malloc(), sort_rays(), TRY, UNCATCH, zmat_s::vals, bmat_s::vals, zmat_extend(), zval_addmul, zval_cmp_i, zval_equal_i, zval_mul, zval_neg, zvec_copy(), and zvec_swap().
Referenced by constrs_of_rays(), and rays_of_constrs().
|
static |
Definition at line 553 of file chernikova.h.
References zval_abs, zval_clear, zval_div, zval_gcd, zval_init, zval_neg, zval_set, zvec_combine(), and zvec_normalize().
Referenced by chernikova(), and gauss().
Definition at line 1195 of file chernikova.h.
References bmat_alloc(), bmat_free(), bvec_init, chernikova(), zmat_s::nbcols, zmat_s::nbrows, bmat_s::nbrows, zmat_s::rawvals, bmat_s::rawvals, remove_redundants(), transpose_sat(), zmat_s::vals, WSIZE, zmat_alloc(), and zval_set_i.
Referenced by constrs_of_sg(), and sc_of_rays().
Definition at line 1251 of file chernikova.h.
References Ssysteme::base, Ssysteme::dimension, Ssysteme::egalites, Ssysteme::inegalites, int, Ssysteme::nb_eq, Ssysteme::nb_ineq, Scontrainte::succ, Svecteur::succ, TCST, zmat_s::vals, vect_coeff(), Scontrainte::vecteur, vecteur_var, zmat_alloc(), and zval_set_i.
Referenced by rays_of_sc().
Definition at line 1418 of file chernikova.h.
References constrs_of_rays(), rays_of_sg(), sg, and zmat_free().
Referenced by sc_of_sg().
Definition at line 789 of file chernikova.h.
References any_exception_error, CATCH, combine(), free(), zmat_s::nbrows, pivot(), rank, RETHROW, safe_free(), safe_malloc(), TRY, UNCATCH, zmat_s::vals, zval_clear, zval_cmp_i, zval_equal_i, zval_init, zvec_antiscale(), zvec_gcd(), zvec_neg(), and zvec_swap().
Referenced by remove_redundants().
|
static |
Definition at line 106 of file chernikova.h.
References env, and TIMEOUT_ENV.
Referenced by sc_union().
Definition at line 1170 of file chernikova.h.
References bmat_alloc(), bmat_free(), bvec_init, chernikova(), zmat_s::nbcols, zmat_s::nbrows, bmat_s::nbrows, zmat_s::rawvals, bmat_s::rawvals, remove_redundants(), zmat_s::vals, WSIZE, zmat_alloc(), and zval_set_i.
Referenced by rays_of_sc(), and sg_of_constrs().
Definition at line 1404 of file chernikova.h.
References constrs_of_sc(), rays_of_constrs(), and zmat_free().
Referenced by sc_union(), and sg_of_sc().
Definition at line 1330 of file chernikova.h.
References type_sg::base, base_dimension, typ_som::denominateur, type_sg::dtes_sg, type_sg::rays_sg, sg, sg_nbre_droites, sg_nbre_rayons, sg_nbre_sommets, type_sg::soms_sg, ttsg_soms::ssg, rdte::succ, typ_som::succ, rdte::vecteur, typ_som::vecteur, ttsg_vects::vsg, zmat_alloc(), and zmat_set_row().
Referenced by constrs_of_sg().
mone
zval_set_i(mone, -1);
Definition at line 850 of file chernikova.h.
References any_exception_error, aux, BSWAP, CATCH, empty, free(), gauss(), int, MSB, zmat_s::nbcols, bmat_s::nbcols, zmat_s::nbrows, NEXT, redundant(), RETHROW, safe_free(), safe_malloc(), SWAP, TRY, UNCATCH, zmat_s::vals, bmat_s::vals, zmat_alloc(), zmat_free(), zmat_safe_free(), zval_add, zval_clear, zval_cmp_i, zval_equal_i, zval_get_i, zval_init, zval_set_i, zvec_alloc(), zvec_copy(), zvec_free(), zvec_index_first_notzero(), zvec_set_i(), and zvec_swap().
Referenced by constrs_of_rays(), and rays_of_constrs().
|
static |
Definition at line 74 of file chernikova.h.
References free().
Referenced by gauss(), and remove_redundants().
Definition at line 56 of file chernikova.h.
References abort, fprintf(), and malloc().
Referenced by bmat_alloc(), chernikova(), gauss(), remove_redundants(), zmat_alloc(), zvec_alloc(), and zvec_gcd().
Definition at line 65 of file chernikova.h.
References abort, and fprintf().
Referenced by bmat_extend(), and zmat_extend().
Definition at line 1286 of file chernikova.h.
References assert, Ssysteme::base, base, base_copy(), base_dimension, contrainte_make(), Ssysteme::dimension, Ssysteme::egalites, Ssysteme::inegalites, Ssysteme::nb_eq, Ssysteme::nb_ineq, zmat_s::nbcols, zmat_s::nbrows, sc_new(), sc_normalize(), Scontrainte::succ, TCST, zmat_s::vals, vect_add_elem(), vect_chg_sgn(), vecteur_of_zvec(), zval_equal_i, and zval_get_i.
Referenced by sc_of_rays(), and sc_of_sg().
Definition at line 1411 of file chernikova.h.
References base, constrs_of_rays(), sc_of_constrs(), and zmat_free().
Referenced by sc_union().
Definition at line 1457 of file chernikova.h.
References any_exception_error, type_sg::base, CATCH, constrs_of_sg(), NBMAXCONSTRS, RETHROW, sc_of_constrs(), sc_rm(), sg, TRY, UNCATCH, zmat_free(), and zmat_safe_free().
Referenced by sg_to_sc_chernikova_fixprec().
Definition at line 1476 of file chernikova.h.
References any_exception_error, assert, Ssysteme::base, bases_strictly_equal_p(), CATCH, catch_alarm_sc_convex_hull(), get_linear_convex_hull_timeout(), zmat_s::nbcols, NBMAXCONSTRS, NBMAXRAYS, zmat_s::nbrows, rays_of_sc(), RETHROW, sc_convex_hull_timeout, sc_of_rays(), sc_rm(), TRY, UNCATCH, zmat_s::vals, zmat_alloc(), zmat_free(), zmat_safe_free(), zval_equal_i, and zval_set.
Referenced by sc_convex_hull_fixprec().
Definition at line 1425 of file chernikova.h.
References base, rays_of_constrs(), sg, sg_of_rays(), and zmat_free().
Definition at line 1350 of file chernikova.h.
References assert, type_sg::base, base, base_copy(), type_sg::dtes_sg, ttsg_soms::nb_s, ttsg_vects::nb_v, zmat_s::nbcols, zmat_s::nbrows, ray_dte_make(), type_sg::rays_sg, sg, sg_new(), sommet_make(), type_sg::soms_sg, ttsg_soms::ssg, rdte::succ, typ_som::succ, zmat_s::vals, vecteur_of_zvec(), ttsg_vects::vsg, zval_equal_i, and zval_get_i.
Referenced by sg_of_constrs(), and sg_of_sc().
Definition at line 1438 of file chernikova.h.
References any_exception_error, Ssysteme::base, CATCH, NBMAXRAYS, rays_of_sc(), RETHROW, sg, sg_of_rays(), sg_rm(), TRY, UNCATCH, zmat_free(), and zmat_safe_free().
Referenced by sc_to_sg_chernikova_fixprec().
|
static |
Definition at line 573 of file chernikova.h.
References BSWAP, zmat_s::vals, bmat_s::vals, zval_cmp_i, zval_equal_i, and zvec_swap().
Referenced by chernikova().
Definition at line 1145 of file chernikova.h.
References bmat_alloc(), bvec_init, MSB, zmat_s::nbrows, NEXT, bmat_s::rawvals, bmat_s::vals, and WSIZE.
Referenced by constrs_of_rays().
Definition at line 1234 of file chernikova.h.
References base, vect_add_elem(), vect_new(), vecteur_var, zval_equal_i, and zval_get_i.
Referenced by sc_of_constrs(), and sg_of_rays().
|
static |
Definition at line 330 of file chernikova.h.
References int, zmat_s::nbcols, zmat_s::nbrows, zmat_s::nbvals, zmat_s::rawvals, safe_malloc(), zmat_s::vals, and zvec_alloc().
Referenced by constrs_of_rays(), constrs_of_sc(), rays_of_constrs(), rays_of_sg(), remove_redundants(), and sc_union().
|
static |
Definition at line 371 of file chernikova.h.
References int, zmat_s::nbcols, zmat_s::nbrows, zmat_s::nbvals, zmat_s::rawvals, safe_realloc(), zmat_s::vals, zval_init, and zvec_set_i().
Referenced by chernikova().
Definition at line 393 of file chernikova.h.
References FPRINT_NBDIGITS, fprintf(), int, zmat_s::nbcols, zmat_s::nbrows, STRINGOF, zmat_s::vals, and zval_get_i.
|
static |
Definition at line 354 of file chernikova.h.
References free(), zmat_s::nbvals, zmat_s::rawvals, zmat_s::vals, and zvec_free().
Referenced by constrs_of_sg(), rays_of_sc(), remove_redundants(), sc_of_rays(), sc_of_sg(), sc_union(), sg_of_constrs(), sg_of_sc(), and zmat_safe_free().
Definition at line 364 of file chernikova.h.
References zmat_free().
Referenced by remove_redundants(), sc_of_sg(), sc_union(), and sg_of_sc().
|
static |
Definition at line 1223 of file chernikova.h.
References base, Svecteur::succ, zmat_s::vals, vect_coeff(), vecteur_var, and zval_set_i.
Referenced by rays_of_sg().
|
static |
Definition at line 133 of file chernikova.h.
References int, safe_malloc(), and zval_init.
Referenced by remove_redundants(), and zmat_alloc().
|
static |
Definition at line 200 of file chernikova.h.
References zval_div.
Referenced by gauss(), and zvec_normalize().
|
static |
Definition at line 186 of file chernikova.h.
References zval_addmul, zval_clear, zval_init, zval_mul, and zval_set.
Referenced by combine().
Definition at line 175 of file chernikova.h.
References zval_set.
Referenced by chernikova(), and remove_redundants().
Definition at line 303 of file chernikova.h.
References fprintf(), and zval_fprint.
|
static |
Definition at line 142 of file chernikova.h.
References free(), int, and zval_clear.
Referenced by remove_redundants(), zmat_free(), and zvec_safe_free().
Definition at line 255 of file chernikova.h.
References free(), int, pgcd, safe_malloc(), zval_abs, zval_clear, zval_equal_i, zval_init, zval_mod, and zvec_min_notzero().
Referenced by gauss(), and zvec_normalize().
Definition at line 215 of file chernikova.h.
References int, and zval_equal_i.
Referenced by remove_redundants(), and zvec_min_notzero().
Definition at line 230 of file chernikova.h.
References aux, int, zval_abs, zval_clear, zval_cmp, zval_equal_i, zval_init, zval_set, zval_set_i, and zvec_index_first_notzero().
Referenced by zvec_gcd().
Definition at line 208 of file chernikova.h.
References zval_neg.
Referenced by gauss().
|
static |
Definition at line 293 of file chernikova.h.
References zval_clear, zval_equal_i, zval_init, zvec_antiscale(), and zvec_gcd().
Referenced by combine().
Definition at line 150 of file chernikova.h.
References zvec_free().
|
static |
Definition at line 168 of file chernikova.h.
References zval_set_i.
Referenced by remove_redundants(), and zmat_extend().
Definition at line 156 of file chernikova.h.
References zval_clear, zval_init, and zval_set.
Referenced by chernikova(), gauss(), remove_redundants(), and sort_rays().
Definition at line 104 of file chernikova.h.
Referenced by catch_alarm_sc_convex_hull(), and sc_union().