types.h

Go to the documentation of this file.

/* types-polylib.h
     COPYRIGHT
          Both this software and its documentation are
 
              Copyright 1993, IRISA /Universite de Rennes I - France
              Copyright 1996,1997,1998, Doran Wilde and Vincent Loechner
              All rights reserved.
 
*/
 
#ifndef _types_polylib_h_
#define _types_polylib_h_
 
#ifdef GNUMP
#include <gmp.h>
#endif
 
#include <limits.h>
 
/*********************** USER DEFINES ******************************/
 
/* first parameter name char.  */
#define FIRST_PARAMETER_NAME 'P'
 
/******************* END OF USER DEFINES ***************************/
 
 
/* ******************** global defines ************************* */
 
#define PCHAR (FIRST_PARAMETER_NAME - 1)
#define MAXNOOFRAYS 200
 
#if defined(LINEAR_VALUE_IS_LONGLONG)
#define P_VALUE_FMT "%4lld "
#elif defined(LINEAR_VALUE_IS_LONG)
#define P_VALUE_FMT "%4ld "
#elif defined(LINEAR_VALUE_IS_CHARS)
#define P_VALUE_FMT "%s "
#elif defined(LINEAR_VALUE_IS_INT)
#define P_VALUE_FMT "%4d "
#else /* GNUMP */
#define P_VALUE_FMT "%4s "
#endif
 
typedef enum { False = 0, True = 1 } Bool;
 
#ifndef FOREVER
#define FOREVER for (;;)
#endif
 
/* Used in lower_upper_bounds */
#define LB_INFINITY 1
#define UB_INFINITY 2
 
/* MSB, TOP, and NEXT are defined over integer type, not on value type */
/* Put a one in the most significant bit of an int (portable) */
#define MSB ((unsigned)(((unsigned)1) << (sizeof(int) * 8 - 1)))
 
/* Largest representable positive number */
#define TOP ((int)(MSB - 1))
 
/* Right shift the one bit in b and increment j if the last bit in b is one */
#define NEXT(j, b)                                                             \
  {                                                                            \
    if (!((b) >>= 1)) {                                                        \
      (b) = MSB;                                                               \
      (j)++;                                                                   \
    }                                                                          \
  }
 
/* Status of last Polyhedron operation */
extern int Pol_status;
 
#define POL_HIGH_BIT (UINT_MAX - (UINT_MAX >> 1))
#define POL_NO_DUAL (POL_HIGH_BIT | 0x0001)
#define POL_INTEGER (POL_HIGH_BIT | 0x0002)
#define POL_ISSET(flags, f) ((flags & f) == f)
 
 
/* ******************** vectors and matrices ************************* */
 
typedef struct {
  unsigned Size;
  Value *p;
  int p_Init_size; /* initial allocated size that will be freed */
} Vector;
 
typedef struct matrix {
  unsigned NbRows, NbColumns;
  Value **p;
  Value *p_Init;
  int p_Init_size; /* needed to free the memory allocated by mpz_init */
} Matrix;
 
 
/* *********************** polyhedra **************************** */
 
/* Macros to init/set/clear/test flags. */
#define FL_INIT(l, f) (l) = (f) /* Specific flags location. */
#define FL_SET(l, f) ((l) |= (f))
#define FL_CLR(l, f) ((l) &= ~(f))
#define FL_ISSET(l, f) ((l) & (f))
 
#define F_INIT(p, f) FL_INIT((p)->flags, f) /* Structure element flags. */
#define F_SET(p, f) FL_SET((p)->flags, f)
#define F_CLR(p, f) FL_CLR((p)->flags, f)
#define F_ISSET(p, f) FL_ISSET((p)->flags, f)
 
typedef struct polyhedron {
  unsigned Dimension, NbConstraints, NbRays, NbEq, NbBid;
  Value **Constraint;
  Value **Ray;
  Value *p_Init;
  int p_Init_size;
  struct polyhedron *next;
#define POL_INEQUALITIES 0x00000001
#define POL_FACETS 0x00000002
#define POL_POINTS 0x00000004
#define POL_VERTICES 0x00000008
/* The flags field contains "valid" information,
 * i.e., the structure was created by PolyLib.
 */
#define POL_VALID 0x00000010
  unsigned flags;
} Polyhedron;
 
typedef struct interval {
  Value MaxN, MaxD;
  Value MinN, MinD;
  int MaxI, MinI;
} Interval;
 
/* Test whether P is an empty polyhedron */
#define emptyQ(P)                                                              \
  ((F_ISSET(P, POL_INEQUALITIES) && P->NbEq > P->Dimension) ||                 \
   (F_ISSET(P, POL_POINTS) && P->NbRays == 0))
 
/* Test whether P is a universe polyhedron */
#define universeQ(P) (P->Dimension == P->NbBid)
 
 
/* ******************** parametric polyhedra ************************* */
 
typedef struct _Param_Vertex {
  Matrix *Vertex;   /* Each row is a coordinate of the vertex. The first  */
                    /* "m" values of each row are the coefficients of the */
                    /* parameters. The (m+1)th value is the constant, the */
                    /* The (m+2)th value is the common denominator.       */
  Matrix *Domain;   /* Constraints on parameters (in Polyhedral format)   */
  unsigned *Facets; /* Bit array of facets defining the vertex.         */
  struct _Param_Vertex *next; /* Pointer to the next structure */
} Param_Vertices;
 
typedef struct _Param_Domain {
  unsigned *F;        /* Bit array of faces */
  Polyhedron *Domain; /* Pointer to Domain (constraints on parameters) */
  struct _Param_Domain *next; /* Pointer to the next structure  */
} Param_Domain;
 
typedef struct _Param_Polyhedron {
  int nbV;             /* Number of parameterized vertices            */
  Param_Vertices *V;   /* Pointer to the list of parameteric vertices */
  Param_Domain *D;     /* Pointer to the list of validity domains     */
  Matrix *Constraints; /* Constraints referred to by V->Facets     */
  Matrix *Rays;        /* Lines/rays (non parametric)                 */
} Param_Polyhedron;
 
#define FORALL_PVertex_in_ParamPolyhedron(_V, _D, _P)                          \
  {                                                                            \
    int _i, _ix;                                                               \
    unsigned _bx;                                                              \
    for (_i = 0, _ix = 0, _bx = MSB, _V = _P->V; _V && (_i < _P->nbV);         \
         _i++, _V = _V->next) {                                                \
      if (_D->F[_ix] & _bx) {
 
#define END_FORALL_PVertex_in_ParamPolyhedron                                  \
  }                                                                            \
  NEXT(_ix, _bx);                                                              \
  }                                                                            \
  }
 
 
/* ******************** pseudo-polynomials ************************* */
 
typedef enum { polynomial, periodic, evector } enode_type;
 
#ifdef CLN
#define POLY_UNION_OR_STRUCT struct
#else
#define POLY_UNION_OR_STRUCT union
#endif
 
typedef struct _evalue {
  Value d; /* denominator */
  POLY_UNION_OR_STRUCT {
    Value n;          /* numerator (if denominator != 0) */
    struct _enode *p; /* pointer   (if denominator == 0) */
  }
  x;
} evalue;
 
typedef struct _enode {
  enode_type type; /* polynomial or periodic or evector */
  int size;        /* number of attached pointers */
  int pos;         /* parameter position */
  evalue arr[1];   /* array of rational/pointer */
} enode;
 
typedef struct _enumeration {
  Polyhedron *ValidityDomain; /* contraints on the parameters     */
  evalue EP;                  /* dimension = combined space       */
  struct _enumeration *next;  /* Ehrhart Polynomial, corresponding
                                 to parameter values inside the
                                 domain ValidityDomain below      */
} Enumeration;
 
/*-----------------------------Example Usage------------------------------*/
/* enode *e                                                               */
/*     e->type = polynomial     e->type = periodic   e->type = evector    */
/*     e->size = degree+1       e->size = period     e->size = length     */
/*     e->pos  = [1..nb_param]                                            */
/*     e->arr[i].d = denominator (Value)                                  */
/*     e->arr[i].x.p = pointer to another enode (if denominator is zero)  */
/*     e->arr[i].x.n = numerator (Value) (if denominator is non-zero)     */
/*------------------------------------------------------------------------*/
 
/*------------------------------------------------------------------------*/
/* This representation has the following advantages:                      */
/*   -- its dynamic, it can grow/shrink easily                            */
/*   -- it is easy to evaluate for a given context (values of parameters) */
/*   -- it allows pseudo-polynomial to be reduced with rules              */
/*   -- it can be constructed recursively                                 */
/*------------------------------------------------------------------------*/
 
 
/* *********************** LBLs **************************** */
// union of lattices (or affine functions):
typedef struct lattice_union {
  Matrix *M;
  struct lattice_union *next;
} LatticeUnion;
 
// The same LBL structure is used to represent a single LBL or a union of LBLs
// as the image of a polyhedral domain ('P') by an affine function ('Lat')
typedef struct lbl {
  Matrix *Lat;
  Polyhedron *P;
  struct lbl *next;
} LBL;
 
 
#endif /* _types_polylib_h_ */