listes.c File Reference

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

Include dependency graph for listes.c:

Go to the source code of this file.

Functions
bool	contrainte_in_liste (Pcontrainte c, Pcontrainte lc)
	package contrainte - operations sur les listes de contraintes More...
int	constraint_rank (Pcontrainte c, Pcontrainte lc)
	Return the rank of constraint c in constraint list lc. More...
bool	egalite_in_liste (Pcontrainte v, Pcontrainte listev)
	bool egalite_in_liste(Pcontrainte eg, Pcontrainte leg): test si une egalite appartient a une liste d'egalites More...
int	nb_elems_list (Pcontrainte list)
	int nb_elems_list(Pcontrainte list): nombre de contraintes se trouvant dans une liste de contraintes More...
bool	cyclic_constraint_list_p (Pcontrainte l)
	Check if list l contains a cycle. More...
int	safe_nb_elems_list (Pcontrainte list, int n)
	Compute the number of elements in the list if it is less than n. More...
Pcontrainte	contrainte_remove_large_coef (Pcontrainte lc, Value val)

Function Documentation

constraint_rank()

int constraint_rank	(	Pcontrainte	c,
		Pcontrainte	lc
	)

Return the rank of constraint c in constraint list lc.

1 for the first element, and so on, Fortran style. 0 when c is not in lc.

The comparisons are based on the pointers, not on the values of the constraints. It is mainly useful to detect cycles in constraint list.

Parameters

lc

c

Definition at line 75 of file listes.c.

{
  Pcontrainte cc;
  int rank = 0;
 
  assert(!CONTRAINTE_UNDEFINED_P(c));
 
  if (CONTRAINTE_NULLE_P(c))
    ;
  else {
    for (cc=lc; !CONTRAINTE_UNDEFINED_P(cc); cc=cc->succ) {
      rank++;
      // This would be useful to detect duplicate constraints
      // if (vect_equal((c1->vecteur),(c->vecteur))) {
 
      // Physical check
      if(cc==c)
        break;
    }
  }
 
  return rank;
}

References assert, CONTRAINTE_NULLE_P, CONTRAINTE_UNDEFINED_P, rank, and Scontrainte::succ.

Referenced by cyclic_constraint_list_p().

Here is the caller graph for this function:

contrainte_in_liste()

bool contrainte_in_liste	(	Pcontrainte	c,
		Pcontrainte	lc
	)

package contrainte - operations sur les listes de contraintes

listes.c

bool contrainte_in_liste(Pcontrainte c, Pcontrainte lc): test de l'appartenance d'une contrainte c a une liste de contrainte lc

Les contrainte sont supposees normalisees (coefficients reduits par leur PGCD, y compris les termes constants).

On considere que la contrainte nulle, qui ne represente aucune contrainte (elle est toujours verifiee) appartient a toutes les listes de contraintes.

Parameters

lc

c

Definition at line 52 of file listes.c.

{
  Pcontrainte c1;
 
  assert(!CONTRAINTE_UNDEFINED_P(c));
 
  if (CONTRAINTE_NULLE_P(c))
    return true;
 
  for (c1=lc; !CONTRAINTE_UNDEFINED_P(c1); c1=c1->succ) {
    if (vect_equal((c1->vecteur),(c->vecteur))) {
            return true;
    }
  }
  return false;
}

References assert, CONTRAINTE_NULLE_P, CONTRAINTE_UNDEFINED_P, Scontrainte::succ, vect_equal(), and Scontrainte::vecteur.

Referenced by dj_simple_inegs_to_eg(), pa_path_to_few_disjunct_ofl_ctrl(), and sc_supress_same_constraints().

Here is the call graph for this function:

Here is the caller graph for this function:

contrainte_remove_large_coef()

Pcontrainte contrainte_remove_large_coef	(	Pcontrainte	lc,
		Value	val
	)

Returns

a constraint list without constraint with large coeffs

Parameters

lc	list of constraint, which is modified
val	maximum value allowed for coefficients

Parameters

lc	c
val	al

Definition at line 179 of file listes.c.

{
  linear_assert("value must be positive", value_posz_p(val));
 
  Pcontrainte first = lc, previous = NULL;
 
  if (value_zero_p(val)) // nothing to do
    return lc;
 
  while (lc!=NULL)
  {
    if (vect_larger_coef_p(lc->vecteur, val))
    {
      // unlink and free
      Pcontrainte next = lc->succ;
      lc->succ = NULL;
      contrainte_free(lc);
      if (lc==first) first = next;
      if (previous) previous->succ = next;
      // "previous" constraint itself is unchanged
      lc = next;
    }
    else
    {
      previous = lc;
      lc = lc->succ;
    }
  }
  return first;
}

References contrainte_free(), linear_assert, Scontrainte::succ, value_posz_p, value_zero_p, vect_larger_coef_p(), and Scontrainte::vecteur.

Referenced by sc_remove_large_coef().

Here is the call graph for this function:

Here is the caller graph for this function:

cyclic_constraint_list_p()

bool cyclic_constraint_list_p

(

Pcontrainte

l

)

Check if list l contains a cycle.

Definition at line 141 of file listes.c.

{
  int i;
  Pcontrainte c;
  bool cyclic_p = false;
 
  for(i=0, c=l; c!=NULL; i++, c=c->succ) {
    int r = constraint_rank(c, l);
    if(r>0 && r<i) {
      cyclic_p = true;
      break;
    }
  }
 
  return cyclic_p;
}

References constraint_rank(), and Scontrainte::succ.

Referenced by sc_bounded_normalization().

Here is the call graph for this function:

Here is the caller graph for this function:

egalite_in_liste()

bool egalite_in_liste	(	Pcontrainte	v,
		Pcontrainte	listev
	)

bool egalite_in_liste(Pcontrainte eg, Pcontrainte leg): test si une egalite appartient a une liste d'egalites

Une egalite peut avoir ete multipliee par moins 1 mais ses coefficients, comme les coefficients des egalites de la liste, doivent avoir ete reduits par leur PGCD auparavant

Ancien nom: vect_in_liste1()

Parameters

listev

istev

Definition at line 108 of file listes.c.

{
  Pcontrainte v1;
 
  if (v->vecteur == NULL) return(true);
  for (v1=listev;v1!=NULL;v1=v1->succ) {
    if (vect_equal((v1->vecteur),(v->vecteur)) ||
        vect_oppos((v1->vecteur),(v->vecteur))) {
            return true;
    }
  }
  return false;
}

References Scontrainte::succ, vect_equal(), vect_oppos(), and Scontrainte::vecteur.

Here is the call graph for this function:

nb_elems_list()

int nb_elems_list

(

Pcontrainte

list

)

int nb_elems_list(Pcontrainte list): nombre de contraintes se trouvant dans une liste de contraintes

Ancien nom: nb_elems_eq()

Cycles are not detected

Parameters

list

ist

Definition at line 129 of file listes.c.

{
  int i;
  Pcontrainte c;
 
  for(i=0, c=list;c!=NULL;i++,c=c->succ)
    ;
 
        return i;
}

References Scontrainte::succ.

Referenced by bounds_equal_p(), build_third_comb(), combiner_ofl_with_test(), constraints_lexicographic_sort_generic(), constraints_sort_info(), loop_iteration_domaine_to_sc(), prepare_reindexing(), region_sc_minimal(), sc_add_egalites(), sc_add_inegalites(), sc_elim_var(), sc_fix(), sc_make(), sc_projection_optim_along_vecteur_ofl(), sc_remove_large_coef(), and sc_weak_consistent_p().

Here is the caller graph for this function:

safe_nb_elems_list()

int safe_nb_elems_list	(	Pcontrainte	list,
		int	n
	)

Compute the number of elements in the list if it is less than n.

n is assumed positive. A negative value is returned if the number of elements is strictly greater than n, for instance because the list is cyclic.

Parameters

list

ist

Definition at line 162 of file listes.c.

{
  int i;
  Pcontrainte c;
 
  assert(n>=0);
 
  for(i=0, c=list;c!=NULL && i<=n ;i++,c=c->succ)
    ;
 
  return i<=n? i : -1;
}

References assert, and Scontrainte::succ.

Referenced by sc_consistent_p().

Here is the caller graph for this function: