PIPS
|
#include <stdlib.h>
#include <stdio.h>
#include "boolean.h"
#include "arithmetique.h"
#include "vecteur.h"
#include "ray_dte.h"
#include "sommet.h"
#include "sg.h"
Go to the source code of this file.
Macros | |
#define | ifdebug(n) if((n)<sg_debug_level) |
#define | MALLOC(s, t, f) malloc(s) |
#define | FREE(p, t, f) free(p) |
#define | LESSER_DIRECTION 4 |
Print a generating system as a dependence direction vector. More... | |
#define | GREATER_DIRECTION 1 |
#define | ZERO_DIRECTION 2 |
#define | ANY_DIRECTION 7 |
#define | NO_DIRECTION 0 |
Functions | |
Ptsg | sg_new () |
Ptsg sg_new(): allocation d'un systeme generateur et initialisation a la valeur ensemble vide. More... | |
Ptsg | sg_dup (Ptsg sg_in) |
Ptsg sg_dup(Ptsg sg_in): allocation d'un systeme generateur sg_out et copie sans sharing des ensembles de rayons, de droites et de sommets de l'argument sg_in. More... | |
Ptsg | sg_without_line (Ptsg sg_in) |
Ptsg sg_without_line(Ptsg sg_in): allocation d'un systeme generateur et copie d'un systeme generateur dont on transforme les lignes en rayons. More... | |
Ptsg | sg_add_ray (Ptsg sg, Pray_dte ray) |
Ptsg sg_add_ray(Ptsg sg, Pray_dte ray): ajout d'un rayon a un syteme generateur; aucune allocation n'est affectuee; il y a donc risque de sharing pour le rayon ray; l'argument sg est modifie. More... | |
void | sg_rm_sommets (Ptsg sg) |
void sg_rm_sommets(Ptsg sg): desallocation d'une liste de sommets d'un systeme generateur More... | |
void | sg_rm_rayons (Ptsg sg) |
void sg_rm_rayons(Ptsg sg): desallocation d'une liste de rayons d'un systeme generateur More... | |
void | sg_rm_droites (Ptsg sg) |
void sg_rm_droites(Ptsg sg): desallocation d'une liste de droites d'un systeme generateur More... | |
void | sg_rm (Ptsg sg) |
void sg_rm(Ptsg sg): liberation de l'espace memoire occupe par un systeme generateur More... | |
void | sg_fprint (FILE *f, Ptsg sg, char *(*nom_var)(Variable)) |
void sg_fprint(FILE * f, Ptsg sg, char * (*nom_var)()): impression d'un systeme generateur More... | |
void | sg_print (Ptsg sg, char *(*nom_var)(Variable)) |
For debugging. More... | |
void | sg_dump (Ptsg sg) |
For debugging. More... | |
void | sg_fprint_as_dense (FILE *f, Ptsg sg, Pbase b) |
void sg_fprint_as_dense(FILE * f, Ptsg sg): impression d'un systeme generateur More... | |
void | sg_fprint_as_ddv (FILE *fd, Ptsg sg) |
static bool | egal_soms (Ptsg_soms sgs1, Ptsg_soms sgs2) |
bool egal_soms(Ptsg_soms sgs1, Ptsg_soms sgs2): test de l'egalite de deux listes de sommets associees a un systeme generateur More... | |
static bool | egal_rd (Ptsg_vects rdgs1, Ptsg_vects rdgs2) |
bool egal_rd(Ptsg_vects rdgs1, Ptsg_vects rdgs2): test de de l'egalite des deux objets representes par des structures tsg_vects More... | |
bool | sg_egal (Ptsg sg1, Ptsg sg2) |
bool sg_egal(Ptsg sg1, Ptsg sg2): test de l'egalite de deux systemes generateur sg1 et sg2 More... | |
Ptsg | mk_rn (Pbase b) |
Ptsg mk_rn(Pbase b): construction du systeme generateur du polyedre qui represente l'espace entier; le systeme de contraintes correspondant est vide: il ne contient ni egalite ni inegalite non triviale;. More... | |
Ptsg | ajout_dte (Ptsg sg, Variable v) |
Ptsg ajout_dte(Ptsg sg, Variable v): ajoute une droite dans la direction correspondant a la variable v. More... | |
bool | sommet_in_sg_p (Psommet som, Ptsg sg) |
bool | ray_in_sg_p (Pray_dte ray, Ptsg sg) |
bool | dte_in_sg_p (Pray_dte dte, Ptsg sg) |
Ptsg | sg_union (Ptsg sg1, Ptsg sg2) |
Variables | |
static int | sg_debug_level = 0 |
package pour la structure de donnees tsg (systeme generateur) et pour les deux structures de donnees inclues tsg_vects et tsg_soms qui representent les listes de rayons, de droites et de sommets d'un systeme generateur More... | |
static int | vertex_to_direction [3] = {LESSER_DIRECTION, ZERO_DIRECTION, GREATER_DIRECTION} |
static int | ray_to_direction [3] = {LESSER_DIRECTION, NO_DIRECTION, GREATER_DIRECTION} |
static int | line_to_direction [3] = {ANY_DIRECTION, NO_DIRECTION, ANY_DIRECTION} |
static char * | direction_to_representation [8] = {"?", "<", "=", "<=", ">", "*", ">=", "*"} |
#define ifdebug | ( | n | ) | if((n)<sg_debug_level) |
#define LESSER_DIRECTION 4 |
Ptsg ajout_dte(Ptsg sg, Variable v): ajoute une droite dans la direction correspondant a la variable v.
creation
ajout
sg | g |
Definition at line 487 of file sg.c.
References MALLOC, RAY_DTE, sg, sg_droites, sg_nbre_droites, rdte::succ, VALUE_ONE, vect_new(), and rdte::vecteur.
dte | te |
sg | g |
Definition at line 537 of file sg.c.
References type_sg::dtes_sg, sg, SG_UNDEFINED_P, rdte::succ, vect_equal(), rdte::vecteur, and ttsg_vects::vsg.
Referenced by sg_union().
|
static |
bool egal_rd(Ptsg_vects rdgs1, Ptsg_vects rdgs2): test de de l'egalite des deux objets representes par des structures tsg_vects
Ne doit servir que dans sg_egal()
Definition at line 410 of file sg.c.
References egaliste_rd().
Referenced by sg_egal().
bool egal_soms(Ptsg_soms sgs1, Ptsg_soms sgs2): test de l'egalite de deux listes de sommets associees a un systeme generateur
Malik: on notera que deux polyedres non faisables (nb sommets = 0) seront identiques quelque soit la representation du SC
Francois: comme la structure de donnees tsg_soms n'existe jamais "libre" mais n'est toujours qu'une partie de la structure tsg, je ne pense pas qu'il soit necessaire de rendre cette routine visible de l'exterieur
Definition at line 396 of file sg.c.
References egaliste_s().
Referenced by sg_egal().
Ptsg mk_rn(Pbase b): construction du systeme generateur du polyedre qui represente l'espace entier; le systeme de contraintes correspondant est vide: il ne contient ni egalite ni inegalite non triviale;.
Modifications:
un sommet a l'origine
il n'y a aucun rayon
enfin, une droite par dimension
Definition at line 451 of file sg.c.
References base_dimension, type_sg::dtes_sg, fprintf(), ifdebug, ray_dte_make(), type_sg::rays_sg, sg, sg_fprint(), sg_new(), sommet_make(), type_sg::soms_sg, rdte::succ, Svecteur::succ, VALUE_ONE, variable_dump_name(), vect_new(), VECTEUR_NUL, VECTEUR_NUL_P, and vecteur_var.
ray | ay |
sg | g |
Definition at line 522 of file sg.c.
References type_sg::rays_sg, sg, SG_UNDEFINED_P, rdte::succ, vect_equal(), rdte::vecteur, and ttsg_vects::vsg.
Referenced by sg_union().
Ptsg sg_add_ray(Ptsg sg, Pray_dte ray): ajout d'un rayon a un syteme generateur; aucune allocation n'est affectuee; il y a donc risque de sharing pour le rayon ray; l'argument sg est modifie.
Aucune elimination de redondance pour le moment. On peut en envisager trois niveaux: egalite entre rayons, proportionalite entre rayons et combinaison lineaire positive de rayons.
chainage en tete de la liste des rayons
sg | g |
ray | ay |
Definition at line 189 of file sg.c.
References type_sg::rays_sg, sg, and ttsg_vects::vsg.
void sg_dump | ( | Ptsg | sg | ) |
For debugging.
sg | g |
Definition at line 288 of file sg.c.
References sg, sg_print(), and variable_dump_name().
Ptsg sg_dup(Ptsg sg_in): allocation d'un systeme generateur sg_out et copie sans sharing des ensembles de rayons, de droites et de sommets de l'argument sg_in.
sg_in n'est pas modifie
Autre nom (obsolete): cp_sg()
Extension: duplicate undefined generating systems (FI, 22 May 2009)
sc_dup() has been replaced by sc_copy() which maintains the order in the data structure lists. Maybe we need the same change for generating systems.
duplication de la liste des sommets
duplication de la liste des rayons
duplication de la liste des droites
sg_in | g_in |
Definition at line 84 of file sg.c.
References type_sg::base, base_dup(), type_sg::dtes_sg, ttsg_soms::nb_s, ttsg_vects::nb_v, ray_dte_dup(), type_sg::rays_sg, sg_new(), SG_UNDEFINED, SG_UNDEFINED_P, sommet_dup(), type_sg::soms_sg, ttsg_soms::ssg, rdte::succ, typ_som::succ, and ttsg_vects::vsg.
Referenced by conflict_dup(), initialize_newgen(), sg_union(), and sg_without_line().
bool sg_egal(Ptsg sg1, Ptsg sg2): test de l'egalite de deux systemes generateur sg1 et sg2
Ce test suppose que les deux systemes ont ete prealablement normalises:
Ancien nom: sg_egal()
sg1 | g1 |
sg2 | g2 |
Definition at line 434 of file sg.c.
References egal_rd(), egal_soms(), and sg_nbre_sommets.
void sg_fprint(FILE * f, Ptsg sg, char * (*nom_var)()): impression d'un systeme generateur
Definition at line 262 of file sg.c.
References f(), fprint_lray_dte(), fprint_lsom(), fprintf(), nom_var, sg, sg_droites, sg_nbre_droites, sg_nbre_rayons, sg_nbre_sommets, sg_rayons, and sg_sommets.
Referenced by adg_print_graph(), main(), mk_rn(), sg_print(), and sg_without_line().
void sg_fprint_as_ddv | ( | FILE * | fd, |
Ptsg | sg | ||
) |
For each coordinate
For all vertices
For all rays
For all lines
fd | d |
sg | g |
Definition at line 341 of file sg.c.
References type_sg::base, BASE_NULLE, BASE_NULLE_P, direction_to_representation, fprintf(), line_to_direction, ray_to_direction, sg, sg_droites, sg_rayons, sg_sommets, rdte::succ, typ_som::succ, Svecteur::succ, value_sign, vect_coeff(), rdte::vecteur, typ_som::vecteur, vecteur_var, and vertex_to_direction.
Referenced by check_for_conflict(), prettyprint_dependence_graph(), and prettyprint_dot_dependence_graph().
void sg_fprint_as_dense(FILE * f, Ptsg sg): impression d'un systeme generateur
Note: b could/should be sg->base
sg | g |
Definition at line 298 of file sg.c.
References f(), fprint_lray_dte_as_dense(), fprint_lsom_as_dense(), fprintf(), sg, sg_droites, sg_nbre_droites, sg_nbre_rayons, sg_nbre_sommets, sg_rayons, and sg_sommets.
Referenced by legal_point_p(), prettyprint_dependence_graph(), and prettyprint_dependence_graph_view().
Ptsg sg_new | ( | void | ) |
Ptsg sg_new(): allocation d'un systeme generateur et initialisation a la valeur ensemble vide.
Obsolete macros of Malik Imadache #define soms_of_sg(sg) (((sg).soms_sg).ssg) #define rays_of_sg(sg) (((sg).rays_sg).vsg) #define dtes_of_sg(sg) (((sg).dtes_sg).vsg)
Definition at line 55 of file sg.c.
References type_sg::base, type_sg::dtes_sg, MALLOC, ttsg_soms::nb_s, ttsg_vects::nb_v, type_sg::rays_sg, sg, type_sg::soms_sg, ttsg_soms::ssg, TSG, and ttsg_vects::vsg.
Referenced by dependence_cone_positive(), main(), mk_rn(), sg_dup(), and sg_of_rays().
void sg_rm | ( | Ptsg | sg | ) |
void sg_rm(Ptsg sg): liberation de l'espace memoire occupe par un systeme generateur
Ne pas oublier de remettre le pointeur correspondant a NULL dans le programme appelant
Ancien nom: elim_sg()
sg | g |
Definition at line 249 of file sg.c.
References type_sg::base, base_rm, FREE, sg, sg_rm_droites(), sg_rm_rayons(), sg_rm_sommets(), and TSG.
Referenced by dependence_cone_positive(), initialize_newgen(), sg_of_sc(), and TestDependence().
void sg_rm_droites | ( | Ptsg | sg | ) |
void sg_rm_droites(Ptsg sg): desallocation d'une liste de droites d'un systeme generateur
sg | g |
Definition at line 233 of file sg.c.
References elim_tt_rd(), ttsg_vects::nb_v, type_sg::rays_sg, sg, and ttsg_vects::vsg.
Referenced by sg_rm().
void sg_rm_rayons | ( | Ptsg | sg | ) |
void sg_rm_rayons(Ptsg sg): desallocation d'une liste de rayons d'un systeme generateur
sg | g |
Definition at line 222 of file sg.c.
References elim_tt_rd(), ttsg_vects::nb_v, type_sg::rays_sg, sg, and ttsg_vects::vsg.
Referenced by sg_rm().
void sg_rm_sommets | ( | Ptsg | sg | ) |
void sg_rm_sommets(Ptsg sg): desallocation d'une liste de sommets d'un systeme generateur
Ex-fonction elim_tt_som() qui prenait en argument une liste de sommets
sg | g |
Definition at line 205 of file sg.c.
References ttsg_soms::nb_s, s1, sg, SOMMET_RM, type_sg::soms_sg, ttsg_soms::ssg, and typ_som::succ.
Referenced by sg_rm().
union des sommets
union des rayons
nion des droites
sg1 | g1 |
sg2 | g2 |
Definition at line 552 of file sg.c.
References type_sg::base, base_rm, base_union(), dte_in_sg_p(), type_sg::dtes_sg, ttsg_soms::nb_s, ttsg_vects::nb_v, ray_dte_dup(), ray_in_sg_p(), type_sg::rays_sg, sg, sg_dup(), sg_nbre_droites, sg_nbre_rayons, sg_nbre_sommets, sommet_dup(), sommet_in_sg_p(), type_sg::soms_sg, ttsg_soms::ssg, rdte::succ, typ_som::succ, and ttsg_vects::vsg.
Referenced by main().
Ptsg sg_without_line(Ptsg sg_in): allocation d'un systeme generateur et copie d'un systeme generateur dont on transforme les lignes en rayons.
Aucune elimination de redondance pour le moment. On peut en envisager trois niveaux: egalite entre rayons, proportionalite entre rayons et combinaison lineaire positive de rayons.
ajout des l'oppose des vecteurs directeur des droites a la liste des rayons
allocation et calcul du vecteur opppose
chainage en tete de la liste des rayons
ajout (sans duplication en memoire) de la liste des vecteurs directeurs des droites a la liste des rayons, si l'ensemble des droites n'est pas vide
ajout de l'ensemble des rayons a l'ensemble des droites
transfert de la liste des droites a la liste des rayons
mise a jour des nombres de droites et de vecteurs
sg_in | g_in |
Definition at line 132 of file sg.c.
References type_sg::dtes_sg, fprintf(), ifdebug, ttsg_vects::nb_v, ray_oppose(), type_sg::rays_sg, sg_dup(), sg_fprint(), rdte::succ, variable_dump_name(), and ttsg_vects::vsg.
som | om |
sg | g |
Definition at line 507 of file sg.c.
References sg, SG_UNDEFINED_P, type_sg::soms_sg, ttsg_soms::ssg, typ_som::succ, vect_equal(), and typ_som::vecteur.
Referenced by sg_union().
|
static |
Definition at line 338 of file sg.c.
Referenced by sg_fprint_as_ddv().
|
static |
Definition at line 336 of file sg.c.
Referenced by sg_fprint_as_ddv().
|
static |
Definition at line 334 of file sg.c.
Referenced by sg_fprint_as_ddv().
|
static |
|
static |
Definition at line 332 of file sg.c.
Referenced by sg_fprint_as_ddv().