source/tab.c

   1 /******************************************************************************
   2  *                     PIP : Parametric Integer Programming                   *
   3  ******************************************************************************
   4  *                                   tab.h                                    *
   5  ******************************************************************************
   6  *                                                                            *
   7  * Copyright Paul Feautrier, 1988, 1993, 1994, 1996, 2002                     *
   8  *                                                                            *
   9  * This is free software; you can redistribute it and/or modify it under the  *
  10  * terms of the GNU General Public License as published by the Free Software  *
  11  * Foundation; either version 2 of the License, or (at your option) any later *
  12  * version.                                                                   *
  13  *                                                                            *
  14  * This software is distributed in the hope that it will be useful, but       *
  15  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY *
  16  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License   *
  17  * for more details.                                                          *
  18  *                                                                            *
  19  * You should have received a copy of the GNU General Public License along    *
  20  * with software; if not, write to the Free Software Foundation, Inc.,        *
  21  * 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA                     *
  22  *                                                                            *
  23  * Written by Paul Feautrier and Cedric Bastoul                                                  *
  24  *                                                                            *
  25  ******************************************************************************/
  26
  27
  28 #include <stdio.h>
  29 #include <stdlib.h>
  30
  31 #include <piplib/piplib.h>
  32
  33 #define TAB_CHUNK 4096*sizeof(Entier)
  34
  35 static char *tab_free, *tab_top;
  36 static struct A *tab_base;
  37
  38 extern int allocation;
  39 extern long int cross_product, limit;
  40 static int chunk_count;
  41
  42 int dgetc(FILE *);
  43 #if defined(LINEAR_VALUE_IS_MP)
  44 int dscanf(FILE *, int    *);
  45 #else
  46 int dscanf(FILE *, Entier *);
  47 #endif
  48
  49 extern FILE * dump;
  50
  51 void tab_init(void)
  52 {
  53  tab_free = malloc(sizeof (struct A));
  54  if(tab_free == NULL)
  55      {fprintf(stderr, "Your computer doesn't have enough memory\n");
  56       exit(1);
  57      }
  58  allocation = 1;
  59  tab_top = tab_free + sizeof (struct A);
  60  tab_base = (struct A *)tab_free;
  61  tab_free += sizeof(struct A);
  62  tab_base->precedent = NULL;
  63  tab_base->bout = tab_top;
  64  chunk_count = 1;
  65 }
  66
  67 struct high_water_mark tab_hwm(void)
  68 {struct high_water_mark p;
  69  p.chunk = chunk_count;
  70  p.top = tab_free;
  71  return p;
  72 }
  73
  74
  75 #if defined(LINEAR_VALUE_IS_MP)
  76 /* the clear_tab routine clears the GMP objects which may be referenced
  77    in the given Tableau.
  78 */
  79 void tab_clear(Tableau *tp)
  80 {
  81   int i, j;
  82   /* clear the determinant */
  83   mpz_clear(tp->determinant);
  84
  85   for(i=0; i<tp->height; i++){
  86     /* clear the denominator */
  87     mpz_clear(Denom(tp, i));
  88     if((Flag(tp, i) & Unit) == 0)
  89       for(j=0; j<tp->width; j++)
  90         mpz_clear(Index(tp,i,j));
  91   }
  92 }
  93 #endif
  94
  95 void tab_reset(struct high_water_mark by_the_mark)
  96
  97 {struct A *g;
  98  char *p;
  99  while(chunk_count > by_the_mark.chunk)
 100      {
 101       g = tab_base->precedent;
 102
 103       #if defined(LINEAR_VALUE_IS_MP)
 104       /* Before actually freeing the memory, one has to clear the
 105        * included Tableaux. If this is not done, the GMP objects
 106        * referenced in the Tableaux will be orphaned.
 107        */
 108
 109       /* Enumerate the included tableaux. */
 110       p = (char *)tab_base + sizeof(struct A);
 111       while(p < tab_free){
 112         Tableau *pt;
 113         pt = (Tableau *) p;
 114         tab_clear(pt);
 115         p += pt->taille;
 116       }
 117       #endif
 118
 119       free(tab_base);
 120       tab_base = g;
 121       tab_top = tab_base->bout;
 122       chunk_count--;
 123      }
 124  if(chunk_count > 0) tab_free = by_the_mark.top;
 125  else {
 126      fprintf(stderr, "Syserr: tab_reset : error in memory allocation\n");
 127      exit(1);
 128      }
 129 }
 130
 131 Tableau * tab_alloc(int h, int w, int n)
 132
 133 /* h : le nombre de ligne reelles;
 134    n : le nombre de lignes virtuelles
 135 */
 136 {
 137  char *p; Tableau *tp;
 138  Entier *q;
 139  unsigned long taille;
 140  int i, j;
 141  taille = sizeof(struct T) + (h+n-1) * sizeof (struct L)
 142           + h * w * sizeof (Entier);
 143  if(tab_free + taille >= tab_top)
 144      {struct A * g;
 145       unsigned long d;
 146       d = taille + sizeof(struct A);
 147       if(d < TAB_CHUNK) d = TAB_CHUNK;
 148       tab_free = malloc(d);
 149       if(tab_free == NULL)
 150           {printf("Memory overflow\n");
 151            exit(23);
 152           }
 153       chunk_count++;
 154       g = (struct A *)tab_free;
 155       g->precedent = tab_base;
 156       tab_top = tab_free + d;
 157       tab_free += sizeof(struct A);
 158       tab_base = g;
 159       g->bout = tab_top;
 160      }
 161  p = tab_free;
 162  tab_free += taille;
 163  tp = (Tableau *)p;
 164  q = (Entier *)(p +  sizeof(struct T) + (h+n-1) * sizeof (struct L));
 165  #if defined(LINEAR_VALUE_IS_MP)
 166  mpz_init_set_ui(tp->determinant,1);
 167  #else
 168  tp->determinant[0] = (Entier) 1;
 169  tp->l_determinant = 1;
 170  #endif
 171  for(i = 0; i<n ; i++){
 172    tp->row[i].flags = Unit;
 173    tp->row[i].objet.unit = i;
 174    #if defined(LINEAR_VALUE_IS_MP)
 175    mpz_init_set_ui(Denom(tp, i), 1);
 176    #else
 177    Denom(tp, i) = UN ;
 178    #endif
 179  }
 180  for(i = n; i < (h+n); i++){
 181    tp->row[i].flags = 0;
 182    tp->row[i].objet.val = q;
 183    for(j = 0; j < w; j++)
 184    #if defined(LINEAR_VALUE_IS_MP)
 185    mpz_init_set_ui(*q++, 0); /* loop body. */
 186    mpz_init_set_ui(Denom(tp, i), 0);
 187    #else
 188    *q++ = 0;                 /* loop body. */
 189    Denom(tp, i) = ZERO ;
 190    #endif
 191  }
 192  tp->height = h + n; tp->width = w;
 193  #if defined(LINEAR_VALUE_IS_MP)
 194  tp->taille = taille ;
 195  #endif
 196
 197  return(tp);
 198 }
 199
 200 Tableau * tab_get(foo, h, w, n)
 201 FILE * foo;
 202 int h, w, n;
 203 {
 204  Tableau *p;
 205  int i, j, c;
 206  #if defined(LINEAR_VALUE_IS_MP)
 207  int x ;
 208  #else
 209  Entier x;
 210  #endif
 211
 212  p = tab_alloc(h, w, n);
 213  while((c = dgetc(foo)) != EOF)
 214       if(c == '(')break;
 215  for(i = n; i<h+n; i++)
 216      {p->row[i].flags = Unknown;
 217       #if defined(LINEAR_VALUE_IS_MP)
 218       mpz_set_ui(Denom(p, i), 1);
 219       #else
 220       Denom(p, i) = UN;
 221       #endif
 222       while((c = dgetc(foo)) != EOF)if(c == '[')break;
 223       for(j = 0; j<w; j++){
 224         if(dscanf(foo, &x) < 0)
 225                 return NULL;
 226         else
 227         #if defined(LINEAR_VALUE_IS_MP)
 228         mpz_set_si(p->row[i].objet.val[j], x);
 229         #else
 230         p->row[i].objet.val[j] = x;
 231         #endif
 232         }
 233       }
 234       while((c = dgetc(foo)) != EOF)if(c == ']')break;
 235
 236  return(p);
 237 }
 238
 239
 240 /* Fonction tab_Matrix2Tableau :
 241  * Cette fonction effectue la conversion du format de matrice de la polylib
 242  * vers le format de traitement de Pip. matrix est la matrice a convertir.
 243  * Nineq est le nombre d'inequations necessaires (dans le format de la
 244  * polylib, le premier element d'une ligne indique si l'equation decrite
 245  * est une inequation ou une egalite. Pip ne gere que les inequations. On
 246  * compte donc le nombre d'inequations total pour reserver la place
 247  * necessaire, et on scinde toute egalite p(x)=0 en p(x)>=0 et -p(x)>=0).
 248  * Nv est le nombre de variables dans la premiere serie de variables (c'est
 249  * a dire que si les premiers coefficients dans les lignes de la matrice
 250  * sont ceux des inconnues, Nv est le nombre d'inconnues, resp. parametres).
 251  * n est le nombre de lignes 'virtuelles' contenues dans la matrice (c'est
 252  * a dire en fait le nombre d'inconnues).
 253  * 27 juillet 2001 : Premiere version, Ced.
 254  * 30 juillet 2001 : Nombreuses modifications. Le calcul du nombre total
 255  *                   d'inequations (Nineq) se fait a present a l'exterieur.
 256  *  3 octobre 2001 : Pas mal d'ameliorations.
 257  */
 258 Tableau * tab_Matrix2Tableau(PipMatrix * matrix, int Nineq, int Nv, int n)
 259 { Tableau * p ;
 260   unsigned i, j, end, current, new, nb_columns, decal=0 ;
 261   Entier * entier, inequality ;
 262
 263   #if defined(LINEAR_VALUE_IS_MP)
 264   mpz_init(inequality) ;
 265   #endif
 266   nb_columns = matrix->NbColumns - 1 ;
 267   p = tab_alloc(Nineq,nb_columns,n) ;
 268
 269   /* La variable decal sert a prendre en compte les lignes supplementaires
 270    * issues des egalites.
 271    */
 272   end = matrix->NbRows + n ;
 273   for (i=n;i<end;i++)
 274   { current = i + decal ;
 275     Flag(p,current) = Unknown ;
 276     #if defined(LINEAR_VALUE_IS_MP)
 277     mpz_set_ui(Denom(p,current),1) ;
 278     #else
 279     Denom(p,current) = UN ;
 280     #endif
 281     entier = *(matrix->p + i - n) ;
 282     /* Pour passer l'indicateur d'egalite/inegalite. */
 283     #if defined(LINEAR_VALUE_IS_MP)
 284     mpz_set(inequality,*entier) ;
 285     #else
 286     inequality = *entier ;
 287     #endif
 288     entier ++ ;
 289
 290     /* Dans le format de la polylib, l'element constant est place en
 291      * dernier. Dans le format de Pip, il se trouve apres la premiere
 292      * serie de variables (inconnues ou parametres). On remet donc les
 293      * choses dans l'ordre de Pip. Ici pour p(x) >= 0.
 294      */
 295     for (j=0;j<Nv;j++)
 296     #if defined(LINEAR_VALUE_IS_MP)
 297     mpz_set(*(p->row[current].objet.val + j),*entier++) ;
 298     #else
 299     *(p->row[current].objet.val + j) = *entier++ ;
 300     #endif
 301     for (j=Nv+1;j<nb_columns;j++)
 302     #if defined(LINEAR_VALUE_IS_MP)
 303     mpz_set(*(p->row[current].objet.val + j),*entier++) ;
 304     mpz_set(*(p->row[current].objet.val + Nv),*entier) ;
 305     #else
 306     *(p->row[current].objet.val + j) = *entier++ ;
 307     *(p->row[current].objet.val + Nv) = *entier ;
 308     #endif
 309
 310     /* Et ici lors de l'ajout de -p(x) >= 0 quand on traite une egalite. */
 311     if (!inequality)
 312     { decal ++ ;
 313       new = current + 1 ;
 314       Flag(p,new)= Unknown ;
 315       #if defined(LINEAR_VALUE_IS_MP)
 316       mpz_set(Denom(p,new),UN) ;
 317       #else
 318       Denom(p,new) = UN ;
 319       #endif
 320
 321       for (j=0;j<nb_columns;j++)
 322       #if defined(LINEAR_VALUE_IS_MP)
 323       mpz_neg(*(p->row[new].objet.val + j),*(p->row[current].objet.val + j)) ;
 324       #else
 325       *(p->row[new].objet.val + j) = -(*(p->row[current].objet.val + j)) ;
 326       #endif
 327     }
 328   }
 329   #if defined(LINEAR_VALUE_IS_MP)
 330   mpz_clear(inequality);
 331   #endif
 332   return(p);
 333 }
 334
 335
 336 char *Attr[] = {"Unit", "+", "-", "0", "*", "?"};
 337
 338 void tab_display(p, foo)
 339 FILE *foo;
 340 Tableau *p;
 341 {
 342
 343  int i, j, ff, fff, n;
 344  Entier x, d;
 345  #if defined(LINEAR_VALUE_IS_MP)
 346  mpz_init(d);
 347  #endif
 348
 349  fprintf(foo, "%ld/[%d * %d]\n", cross_product, p->height, p->width);
 350  for(i = 0; i<p->height; i++){
 351    fff = ff = p->row[i].flags;
 352    /* if(fff ==0) continue; */
 353    #if defined(LINEAR_VALUE_IS_MP)
 354    mpz_set(d, Denom(p, i));
 355    #else
 356    d = Denom(p, i);
 357    #endif
 358    n = 0;
 359    while(fff){
 360      if(fff & 1) fprintf(foo, "%s ",Attr[n]);
 361      n++; fff >>= 1;
 362    }
 363    fprintf(foo, "%f #[", p->row[i].size);
 364    if(ff & Unit)
 365      for(j = 0; j<p->width; j++)
 366        fprintf(foo, " /%d/",(j == p->row[i].objet.unit)? 1: 0);
 367    else
 368      for(j = 0; j<p->width; j++){
 369        #if defined(LINEAR_VALUE_IS_MP)
 370        mpz_out_str(foo, 10, Index(p, i, j));
 371        putc(' ', foo);
 372        #else
 373        x = Index(p,i,j);
 374        fprintf(foo, FORMAT, x);
 375        fprintf(foo, " ");
 376        #endif
 377      }
 378    fprintf(foo, "]/");
 379    #if defined(LINEAR_VALUE_IS_MP)
 380    mpz_out_str(foo, 10, d);
 381    #else
 382    fprintf(foo, "%d", (int)d);
 383    #endif
 384    putc('\n', foo);
 385  }
 386  #if defined(LINEAR_VALUE_IS_MP)
 387  mpz_clear(d);
 388  #endif
 389 }