#include <stdlib.h>
#include <stdio.h>
#include "boolean.h"
#include "linear_assert.h"
#include "arithmetique.h"
#include "vecteur.h"
#include "ray_dte.h"
#include "sommet.h"

Include dependency graph for sommet.c:

Macros
#define	MALLOC(s, t, f) malloc(s)
	package pour la structure de donnees sommet (sommet d'un systeme generateur) More...

#define	FREE(s, t, f) free(s)

Functions
Psommet	sommet_new ()
	Creation d'un sommet More...

Psommet	sommet_make (Value d, Pvecteur v)
	Psommet sommet_make(int d, Pvecteur v): allocation et initialisation d'un sommet de denominateur d et de vecteur v; le vecteur v est utilise directement; ca peut introduire du sharing;. More...

Psommet	sommet_dup (Psommet s_in)
	Psommet sommet_dup(Psommet s_in): allocation et copie de la valeur d'un sommet. More...

void	sommet_rm (Psommet s)
	void sommet_rm(Psommet s): desallocation complete d'une structure sommet More...

void	dbg_sommet_rm (Psommet s, char *f)

void	sommet_fprint (FILE f, Psommet s, char (*nom_var)(Variable))
	void sommet_fprint(FILE * f, Psommet s, char * (*nom_var)()): impression d'un sommet More...

void	sommet_fprint_as_dense (FILE *f, Psommet s, Pbase b)
	void sommet_fprint_as_dense(FILE * f, Psommet s): impression d'un sommet More...

void	sommet_dump (Psommet s)
	void sommet_dump(Psommet s): impression d'un sommet sur stderr avec variable_debug_name() More...

void	fprint_lsom (FILE f, Psommet ls, char (*nom_var)(Variable))
	void fprint_lsom(FILE * f, Psommet s, char * (*nom_var)()): impression d'une liste de sommets More...

void	fprint_lsom_as_dense (FILE *f, Psommet ls, Pbase b)
	void fprint_lsom_as_dense(FILE * f, Psommet s): impression d'une liste de sommets More...

void	sommet_normalize (Psommet ns)
	void sommet_normalize(Psommet ns): normalisation des coordonnees d'un sommet par le pgcd des coordonnees et du denominateur More...

bool	som_in_liste (Psommet s, Psommet listes)
	bool som_in_liste(Psommet s, Psommet l): test de l'appartenance du sommet s a la liste de sommets l More...

bool	sommet_egal (Psommet s1, Psommet s2)
	bool sommet_egal(Psommet s1, Psommet s2): test de l'egalite de representation de deux sommets More...

bool	egaliste_s (Psommet l1, Psommet *ad_l2)
	bool egaliste_s(Psommet l1, Psommet * ad_l2): test d'egalite de listes de sommets More...

void	sommet_add (Psommet ps, Psommet som, int nb_som)
	void sommet_add(Psommet ps, Psommet som, int nb_soms): Ajout d'un sommet a une liste de sommets Le sommet est ajoute a la fin de la liste. More...

Macro Definition Documentation

◆ FREE

#define FREE	(	s,
		t,
		f
	)	free(s)

Definition at line 46 of file sommet.c.

◆ MALLOC

#define MALLOC	(	s,
		t,
		f
	)	malloc(s)

package pour la structure de donnees sommet (sommet d'un systeme generateur)

Francois Irigoin, Mai 1989

Definition at line 45 of file sommet.c.

Function Documentation

◆ dbg_sommet_rm()

void dbg_sommet_rm	(	Psommet	s,
		char *	f
	)

Definition at line 117 of file sommet.c.

 {
     (void) fprintf(stderr,"destruction de sommet dans %s : ",f);
     sommet_fprint(stderr, s, variable_debug_name);
     dbg_vect_rm(s->vecteur,f);
     FREE((char *)s,SOMMET,f);
 }

References dbg_vect_rm(), f(), fprintf(), FREE, SOMMET, sommet_fprint(), and variable_debug_name.

Here is the call graph for this function:

◆ egaliste_s()

bool egaliste_s	(	Psommet	l1,
		Psommet*	ad_l2
	)

bool egaliste_s(Psommet l1, Psommet * ad_l2): test d'egalite de listes de sommets

 nous proposons un test direct au lieu d'un test en deux etapes 
 d'inclusion dans les deux sens; ceci justifie le second parametre
 qui est l'adresse du pointeur de liste (Malik Imadache)

elements pour lesquels il reste a trouver un "jumeau" dans l1

adresse a laquelle il faudra raccrocher les elements de l2 successivement testes

on a trouve un element (eq21) de eq2 egal a l'element courant de l1; on remet donc eq21 dans l2, en distingant 2 cas suivant qu'il est en tete de eq2 ou pas

eq23 est le predecesseur de eq21 dans eq2 il faut le conserver pour enlever eq21 de eq2

eq21 est different de l'element de l1 qui est teste; il faut voir le reste de la liste eq2

on a trouve un element de l1 qui n'a pas de "jumeau" dans l2 => reformer l2 et sortir

tous les elements de l1 ont un jumeau (=> l1 est inclus dans l2) si tous les elements de l2 sont jumeaux (inclusion inverse) => egalite

dans le cas inverse reformer l2 et sortir

Parameters

l1	1
ad_l2	d_l2

Definition at line 258 of file sommet.c.

 {
     int egalite;
     Psommet eq1,eq2,eq21,eq23,*ad_aux;
  
     if (l1==(*ad_l2)) return(true);
  
     /* elements pour lesquels il reste a trouver un "jumeau" dans l1 */
     eq2 = *ad_l2;
     /* adresse a laquelle il faudra raccrocher les elements de l2
        successivement testes */
     ad_aux = ad_l2;
  
     (*ad_l2) = NULL;
  
     for(eq1=l1;eq1!=NULL;eq1=eq1->succ)  {
         egalite = 0;
         for(eq21=eq2,eq23=eq2;eq21!=NULL;) {
             if (sommet_egal(eq21,eq1)) {
                 /* on a trouve un element (eq21) de eq2 egal a
                    l'element courant de l1; on remet donc
                    eq21 dans l2, en distingant 2
                    cas suivant qu'il est en tete de
                    eq2 ou pas
                    */
                 /* eq23 est le predecesseur de eq21 dans eq2
                    il faut le conserver pour enlever eq21
                    de eq2
                    */
                 if (eq21==eq2) {
                     eq2=eq2->succ;
                     eq21->succ = NULL;
                     (*ad_aux) = eq21;
                     ad_aux = &(eq21->succ);
                     eq21 = eq23 = eq2;
                 }
                 else {
                     eq23->succ = eq21->succ;
                     eq21->succ = NULL;
                     (*ad_aux) = eq21;
                     ad_aux = &(eq21->succ);
                     eq21 = eq23->succ;
                 }
                 egalite = 1;
                 break;
             }
             else {
                 /* eq21 est different de l'element de l1
                    qui est teste; il faut voir le reste de
                    la liste eq2
                    */
                 eq23 = eq21;
                 eq21 = eq21->succ;
             }
         }
         if (egalite == 0) {
             /* on a trouve un element de l1 qui n'a pas
                de "jumeau" dans l2 => reformer l2 et sortir
                */
             (* ad_aux) = eq2;
             return(false);
         }
         else egalite = 0;
     }
     if (eq2==NULL)
         /* tous les elements de l1 ont un jumeau
            (=> l1 est inclus dans l2)
            si tous les elements de l2 sont jumeaux
            (inclusion inverse) => egalite
            */
         return(true);
     else 
         /* dans le cas inverse reformer l2 et sortir */
         (*ad_aux) = eq2;
     return(false);
 }

References sommet_egal(), and typ_som::succ.

Referenced by egal_soms().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fprint_lsom()

void fprint_lsom	(	FILE *	f,
		Psommet	ls,
		char * (*)(Variable)	nom_var
	)

void fprint_lsom(FILE * f, Psommet s, char * (*nom_var)()): impression d'une liste de sommets

Definition at line 177 of file sommet.c.

 {
     Psommet e;
     for (e = ls; e != NULL; e = e->succ) {
         sommet_fprint(f, e, nom_var);
     }
 }

References f(), nom_var, sommet_fprint(), and typ_som::succ.

Referenced by sg_fprint().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fprint_lsom_as_dense()

void fprint_lsom_as_dense	(	FILE *	f,
		Psommet	ls,
		Pbase	b
	)

void fprint_lsom_as_dense(FILE * f, Psommet s): impression d'une liste de sommets

Parameters

ls s

Definition at line 191 of file sommet.c.

 {
     Psommet e;
     for (e = ls; e != NULL; e = e->succ) {
         sommet_fprint_as_dense(f, e, b);
     }
 }

References f(), sommet_fprint_as_dense(), and typ_som::succ.

Referenced by prettyprint_dependence_graph(), prettyprint_dot_dependence_graph(), and sg_fprint_as_dense().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ som_in_liste()

bool som_in_liste	(	Psommet	s,
		Psommet	listes
	)

bool som_in_liste(Psommet s, Psommet l): test de l'appartenance du sommet s a la liste de sommets l

Les coordonnees du sommet s et des sommets de la liste l sont supposees normalisees (fractions reduites)

Parameters

listes istes

Definition at line 222 of file sommet.c.

 {
     Psommet s1;
  
     for (s1=listes;s1!=NULL;s1=s1->succ) {
         if ((s1->denominateur)==(s->denominateur)) {
             if (vect_equal((s1->vecteur),(s->vecteur))) return(true);
         }
     }
     return(false);
 }

References typ_som::denominateur, s1, vect_equal(), and typ_som::vecteur.

Here is the call graph for this function:

◆ sommet_add()

void sommet_add	(	Psommet *	ps,
		Psommet	som,
		int *	nb_som
	)

void sommet_add(Psommet *ps, Psommet som, int *nb_soms): Ajout d'un sommet a une liste de sommets Le sommet est ajoute a la fin de la liste.

Parameters

ps	s
som	om
nb_som	b_som

Definition at line 342 of file sommet.c.

 {
  
     if (som != NULL)
     {
         Psommet pred,ps1;
  
         pred = *ps;
         for (ps1 = pred; ps1 != NULL; pred = ps1, ps1 = ps1->succ);
         pred->succ = som;
         som->succ = NULL;
         *nb_som = (*nb_som) +1;
     }
 }

References typ_som::succ.

Referenced by eq_in_ineq(), plint_degen(), and plint_pas().

Here is the caller graph for this function:

◆ sommet_dump()

void sommet_dump ( Psommet s )

void sommet_dump(Psommet s): impression d'un sommet sur stderr avec variable_debug_name()

Definition at line 168 of file sommet.c.

 {
     sommet_fprint(stderr, s, variable_debug_name);
 }

References sommet_fprint(), and variable_debug_name.

Here is the call graph for this function:

◆ sommet_dup()

Psommet sommet_dup ( Psommet s_in )

Psommet sommet_dup(Psommet s_in): allocation et copie de la valeur d'un sommet.

Parameters

s_in _in

Definition at line 82 of file sommet.c.

 {
     Psommet s_out;
  
     s_out = (Psommet) MALLOC(sizeof(Ssommet), SOMMET, "sommet_dup");
  
     if(s_in->eq_sat!=NULL) {
         (void) fprintf(stderr,
                        "sommet_dup: warning eq_sat is not duplicated\n");
     }
  
     if(s_in->denominateur==0) {
         (void) fprintf(stderr,"sommet_dup: denominateur nul\n");
         abort();
     }
  
     s_out = (Psommet) MALLOC(sizeof(Ssommet),SOMMET,"sommet_dup");
     s_out->succ = NULL;
     s_out->eq_sat = NULL;
     s_out->vecteur = vect_dup(s_in->vecteur);
     s_out->denominateur = s_in->denominateur;
  
     return s_out;
 }

References abort, typ_som::denominateur, typ_som::eq_sat, fprintf(), MALLOC, SOMMET, typ_som::succ, vect_dup(), and typ_som::vecteur.

Referenced by sg_dup(), sg_union(), sommets_dup(), and sommets_dupc().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ sommet_egal()

bool sommet_egal	(	Psommet	s1,
		Psommet	s2
	)

bool sommet_egal(Psommet s1, Psommet s2): test de l'egalite de representation de deux sommets

Il faut en normaliser les coordonnees d'abord si on veut une egalite de valeur

Parameters

s1	1
s2	2

Definition at line 242 of file sommet.c.

 {
     if (sommet_denominateur(s1)!=sommet_denominateur(s2))
         return(false);
     else
         return(vect_equal(s1->vecteur,s2->vecteur));
 }

References s1, sommet_denominateur, and vect_equal().

Referenced by egaliste_s().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ sommet_fprint()

void sommet_fprint	(	FILE *	f,
		Psommet	s,
		char * (*)(Variable)	nom_var
	)

void sommet_fprint(FILE * f, Psommet s, char * (*nom_var)()): impression d'un sommet

malgre le clash de type, je kludge...

ray_dte_fprint(f, s, nom_var);

Definition at line 130 of file sommet.c.

 {
     if(value_notone_p(s->denominateur)) {
         (void) fprintf(f,"denominator = ");
         fprint_Value(f,s->denominateur);
         (void) fprintf(f, "\t");
     }
     if (s->vecteur)
         vect_fprint(f,s->vecteur,nom_var); 
     else
         fprintf(f, "0\n");
  
     /* malgre le clash de type, je kludge... */
    /* ray_dte_fprint(f, s, nom_var);*/
 }

References typ_som::denominateur, f(), fprint_Value(), fprintf(), nom_var, value_notone_p, vect_fprint(), and typ_som::vecteur.

Referenced by dbg_sommet_rm(), fprint_lsom(), and sommet_dump().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ sommet_fprint_as_dense()

void sommet_fprint_as_dense	(	FILE *	f,
		Psommet	s,
		Pbase	b
	)

void sommet_fprint_as_dense(FILE * f, Psommet s): impression d'un sommet

Definition at line 152 of file sommet.c.

 {
     if(value_notone_p(s->denominateur)) {
         (void) fprintf(f,"denominator = ");
         fprint_Value(f,s->denominateur);
         (void) fprintf(f, "\t");
     }
     vect_fprint_as_dense(f,s->vecteur, b);
 }

References typ_som::denominateur, f(), fprint_Value(), fprintf(), value_notone_p, vect_fprint_as_dense(), and typ_som::vecteur.

Referenced by fprint_lsom_as_dense().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ sommet_make()

Psommet sommet_make	(	Value	d,
		Pvecteur	v
	)

Psommet sommet_make(int d, Pvecteur v): allocation et initialisation d'un sommet de denominateur d et de vecteur v; le vecteur v est utilise directement; ca peut introduire du sharing;.

Definition at line 67 of file sommet.c.

 {
     Psommet s;
  
     s = sommet_new();
     s->denominateur = d;
     s->vecteur = v;
     return (s);
 }

References typ_som::denominateur, sommet_new(), and typ_som::vecteur.

Referenced by mk_rn(), and sg_of_rays().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ sommet_new()

Psommet sommet_new ( void )

Creation d'un sommet

SOMMET.

Definition at line 51 of file sommet.c.

 {
     Psommet s;
  
     s = (Psommet) MALLOC(sizeof(Ssommet), SOMMET, "sommet_dup");
     s->denominateur =0;
     s->vecteur = NULL;
     s->eq_sat =NULL;
     s->succ = NULL;
     return (s);
 }

References typ_som::denominateur, typ_som::eq_sat, MALLOC, SOMMET, typ_som::succ, and typ_som::vecteur.

Referenced by fonct_init(), fonct_max(), fonct_max_all(), fonct_max_d(), fonct_min(), fonct_min_all(), fonct_min_d(), fonct_read(), and sommet_make().

Here is the caller graph for this function:

◆ sommet_normalize()

void sommet_normalize ( Psommet ns )

void sommet_normalize(Psommet ns): normalisation des coordonnees d'un sommet par le pgcd des coordonnees et du denominateur

Parameters

ns s

Definition at line 205 of file sommet.c.

 {
     Value div = vect_pgcd_all(ns->vecteur);
  
     assert(value_pos_p(div));
     div = pgcd(div, ns->denominateur);
     value_division(ns->denominateur,div);
     (void) vect_div(ns->vecteur, div);
 }

References assert, pgcd, value_division, value_pos_p, vect_div(), and vect_pgcd_all().

Referenced by sommets_normalize().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ sommet_rm()

void sommet_rm ( Psommet s )

void sommet_rm(Psommet s): desallocation complete d'une structure sommet

Definition at line 110 of file sommet.c.

 {
     vect_rm(s->vecteur);
     FREE((char *)s,SOMMET,"sommet_rm");
 }

References FREE, SOMMET, and vect_rm().

Here is the call graph for this function:

Macros

Functions

Macro Definition Documentation

◆ FREE

◆ MALLOC

Function Documentation

◆ dbg_sommet_rm()

◆ egaliste_s()

◆ fprint_lsom()

◆ fprint_lsom_as_dense()

◆ som_in_liste()

◆ sommet_add()

◆ sommet_dump()

◆ sommet_dup()

◆ sommet_egal()

◆ sommet_fprint()

◆ sommet_fprint_as_dense()

◆ sommet_make()

◆ sommet_new()

◆ sommet_normalize()

◆ sommet_rm()