source/relation_list.c

   1
   2     /*+-----------------------------------------------------------------**
   3      **                       OpenScop Library                          **
   4      **-----------------------------------------------------------------**
   5      **                        relation_list.c                          **
   6      **-----------------------------------------------------------------**
   7      **                   First version: 08/10/2010                     **
   8      **-----------------------------------------------------------------**
   9
  10
  11  *****************************************************************************
  12  * OpenScop: Structures and formats for polyhedral tools to talk together    *
  13  *****************************************************************************
  14  *    ,___,,_,__,,__,,__,,__,,_,__,,_,__,,__,,___,_,__,,_,__,                *
  15  *    /   / /  //  //  //  // /   / /  //  //   / /  // /  /|,_,             *
  16  *   /   / /  //  //  //  // /   / /  //  //   / /  // /  / / /\             *
  17  *  |~~~|~|~~~|~~~|~~~|~~~|~|~~~|~|~~~|~~~|~~~|~|~~~|~|~~~|/_/  \            *
  18  *  | G |C| P | = | L | P |=| = |C| = | = | = |=| = |=| C |\  \ /\           *
  19  *  | R |l| o | = | e | l |=| = |a| = | = | = |=| = |=| L | \# \ /\          *
  20  *  | A |a| l | = | t | u |=| = |n| = | = | = |=| = |=| o | |\# \  \         *
  21  *  | P |n| l | = | s | t |=| = |d| = | = | = | |   |=| o | | \# \  \        *
  22  *  | H | | y |   | e | o | | = |l|   |   | = | |   | | G | |  \  \  \       *
  23  *  | I | |   |   | e |   | |   | |   |   |   | |   | |   | |   \  \  \      *
  24  *  | T | |   |   |   |   | |   | |   |   |   | |   | |   | |    \  \  \     *
  25  *  | E | |   |   |   |   | |   | |   |   |   | |   | |   | |     \  \  \    *
  26  *  | * |*| * | * | * | * |*| * |*| * | * | * |*| * |*| * | /      \* \  \   *
  27  *  | O |p| e | n | S | c |o| p |-| L | i | b |r| a |r| y |/        \  \ /   *
  28  *  '---'-'---'---'---'---'-'---'-'---'---'---'-'---'-'---'          '--'    *
  29  *                                                                           *
  30  * Copyright (C) 2008 University Paris-Sud 11 and INRIA                      *
  31  *                                                                           *
  32  * (3-clause BSD license)                                                    *
  33  * Redistribution and use in source  and binary forms, with or without       *
  34  * modification, are permitted provided that the following conditions        *
  35  * are met:                                                                  *
  36  *                                                                           *
  37  * 1. Redistributions of source code must retain the above copyright notice, *
  38  *    this list of conditions and the following disclaimer.                  *
  39  * 2. Redistributions in binary form must reproduce the above copyright      *
  40  *    notice, this list of conditions and the following disclaimer in the    *
  41  *    documentation and/or other materials provided with the distribution.   *
  42  * 3. The name of the author may not be used to endorse or promote products  *
  43  *    derived from this software without specific prior written permission.  *
  44  *                                                                           *
  45  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR      *
  46  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES *
  47  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.   *
  48  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,          *
  49  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT  *
  50  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, *
  51  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY     *
  52  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT       *
  53  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF  *
  54  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.         *
  55  *                                                                           *
  56  * OpenScop Library, a library to manipulate OpenScop formats and data       *
  57  * structures. Written by:                                                   *
  58  * Cedric Bastoul     <Cedric.Bastoul@u-psud.fr> and                         *
  59  * Louis-Noel Pouchet <Louis-Noel.pouchet@inria.fr>                          *
  60  *                                                                           *
  61  *****************************************************************************/
  62
  63
  64 # include <stdlib.h>
  65 # include <stdio.h>
  66 # include <string.h>
  67 # include <ctype.h>
  68 # include <openscop/relation_list.h>
  69
  70
  71 /*+***************************************************************************
  72  *                          Structure display function                       *
  73  *****************************************************************************/
  74
  75
  76 /**
  77  * openscop_relation_list_idump function:
  78  * Displays a openscop_relation_list_t structure (a list of relations) into a
  79  * file (file, possibly stdout). See openscop_relation_print_structure for
  80  * more details.
  81  * \param file   File where informations are printed.
  82  * \param l      The list of relations whose information have to be printed.
  83  * \param level  Number of spaces before printing, for each line.
  84  */
  85 void openscop_relation_list_idump(FILE * file,
  86                                   openscop_relation_list_p l,
  87                                   int level) {
  88   int j, first = 1;
  89
  90   // Go to the right level.
  91   for (j = 0; j < level; j++)
  92     fprintf(file,"|\t");
  93
  94   if (l != NULL)
  95     fprintf(file, "+-- openscop_relation_list_t\n");
  96   else
  97     fprintf(file, "+-- NULL relation list\n");
  98
  99   while (l != NULL) {
 100     if (!first) {
 101       // Go to the right level.
 102       for (j = 0; j < level; j++)
 103         fprintf(file, "|\t");
 104       fprintf(file, "|   openscop_relation_list_t\n");
 105     }
 106     else
 107       first = 0;
 108
 109     // A blank line.
 110     for (j = 0; j <= level+1; j++)
 111       fprintf(file, "|\t");
 112     fprintf(file, "\n");
 113
 114     // Print a relation.
 115     openscop_relation_idump(file, l->elt, level+1);
 116
 117     l = l->next;
 118
 119     // Next line.
 120     if (l != NULL) {
 121       for (j = 0; j <= level; j++)
 122         fprintf(file, "|\t");
 123       fprintf(file, "V\n");
 124     }
 125   }
 126
 127   // The last line.
 128   for (j = 0; j <= level; j++)
 129     fprintf(file, "|\t");
 130   fprintf(file, "\n");
 131 }
 132
 133
 134 /**
 135  * openscop_relation_dump function:
 136  * This function prints the content of a openscop_relation_list_t into
 137  * a file (file, possibly stdout).
 138  * \param file File where informations are printed.
 139  * \param list The relation whose information have to be printed.
 140  */
 141 void openscop_relation_list_dump(FILE * file, openscop_relation_list_p list) {
 142   openscop_relation_list_idump(file, list, 0);
 143 }
 144
 145
 146 /**
 147  * openscop_relation_list_print function:
 148  * This function prints the content of a openscop_relation_list_t structure
 149  * into a file (file, possibly stdout) in the OpenScop format. It prints
 150  * an element of the list only if it is not NULL.
 151  * \param file  File where informations are printed.
 152  * \param list  The relation list whose information have to be printed.
 153  * \param names The textual names of the various elements. Is is important
 154  *              that names->nb_parameters is exact if the matrix
 155  *              representation is used. Set to NULL if printing comments
 156  *              is not needed.
 157  */
 158 void openscop_relation_list_print(FILE * file,
 159                                   openscop_relation_list_p list,
 160                                   openscop_names_p names) {
 161   int i;
 162   openscop_relation_list_p head = list;
 163
 164   // Count the number of elements in the list with non-NULL content.
 165   i = 0;
 166   while (list != NULL) {
 167     if (list->elt != NULL)
 168       i++;
 169     list = list->next;
 170   }
 171
 172   // Print it.
 173   if (i > 1)
 174     fprintf(file,"# List of %d elements\n%d\n", i, i);
 175   else
 176     fprintf(file,"# List of %d element \n%d\n", i, i);
 177
 178   // Print each element of the relation list.
 179   if (i > 0) {
 180     i = 0;
 181     while (head) {
 182       if (head->elt != NULL) {
 183         fprintf(file, "# List element No.%d\n", i);
 184         openscop_relation_print(file, head->elt, names);
 185         i++;
 186       }
 187       head = head->next;
 188     }
 189   }
 190 }
 191
 192
 193 /*****************************************************************************
 194  *                               Reading function                            *
 195  *****************************************************************************/
 196
 197
 198 /**
 199  * openscop_relation_list_read function:
 200  * This function reads a list of relations into a file (foo,
 201  * posibly stdin) and returns a pointer this relation list.
 202  * \param file  The input stream.
 203  * \return A pointer to the relation list structure that has been read.
 204  */
 205 openscop_relation_list_p openscop_relation_list_read(FILE* file) {
 206   char s[OPENSCOP_MAX_STRING];
 207   int i;
 208   openscop_relation_list_p list;
 209   openscop_relation_list_p res;
 210   int nb_mat;
 211
 212   // Skip blank/commented lines.
 213   while (fgets(s, OPENSCOP_MAX_STRING, file) == 0 || s[0] == '#' ||
 214       isspace(s[0]))
 215     continue;
 216
 217   // Read the number of relations to read.
 218   if (sscanf(s, "%d", &nb_mat) != 1) {
 219     fprintf(stderr, "[OpenScop] Error: not possible to read the "
 220                     "number of relations.\n");
 221     exit(1);
 222   }
 223
 224   if (nb_mat < 0) {
 225     fprintf(stderr, "[OpenScop] Error: negative number of relations.\n");
 226     exit(1);
 227   }
 228
 229   // Allocate the header of the list and start reading each element.
 230   res = list = openscop_relation_list_malloc();
 231   for (i = 0; i < nb_mat; ++i) {
 232     list->elt = openscop_relation_read(file);
 233     if (i < nb_mat - 1)
 234       list->next = openscop_relation_list_malloc();
 235     list = list->next;
 236   }
 237
 238   return res;
 239 }
 240
 241
 242 /*+***************************************************************************
 243  *                    Memory allocation/deallocation function                *
 244  *****************************************************************************/
 245
 246
 247 /**
 248  * openscop_relation_list_malloc function:
 249  * This function allocates the memory space for a openscop_relation_list_t
 250  * structure and sets its fields with default values. Then it returns
 251  * a pointer to the allocated space.
 252  * \return A pointer to an empty relation list with fields set to default
 253  *         values.
 254  */
 255 openscop_relation_list_p openscop_relation_list_malloc() {
 256   openscop_relation_list_p res;
 257   res = (openscop_relation_list_p)malloc(sizeof(openscop_relation_list_t));
 258
 259   if (res == NULL) {
 260     fprintf(stderr, "[OpenScop] Error: memory overflow.\n");
 261     exit(1);
 262   }
 263
 264   res->elt = NULL;
 265   res->next = NULL;
 266
 267   return res;
 268 }
 269
 270
 271
 272 /**
 273  * openscop_relation_list_free function:
 274  * This function frees the allocated memory for a openscop_relation_list_t
 275  * structure, and all the relations stored in the list.
 276  * \param list The pointer to the relation list we want to free.
 277  */
 278 void openscop_relation_list_free(openscop_relation_list_p list) {
 279   openscop_relation_list_p tmp;
 280
 281   if (list == NULL)
 282     return;
 283
 284   while (list) {
 285     if (list->elt)
 286       openscop_relation_free(list->elt);
 287     tmp = list->next;
 288     free(list);
 289     list = tmp;
 290   }
 291 }
 292
 293
 294 /*+***************************************************************************
 295  *                            Processing functions                           *
 296  *****************************************************************************/
 297
 298
 299 /**
 300  * openscop_relation_list_node function:
 301  * This function builds an openscop_relation_list_t node and sets its
 302  * relation element as a copy of the one provided as parameter.
 303  * \param r The pointer to the relation to copy/paste in a list node.
 304  * \return A pointer to a relation list node containing a copy of "relation".
 305  */
 306 openscop_relation_list_p openscop_relation_list_node(openscop_relation_p r) {
 307   openscop_relation_list_p new = openscop_relation_list_malloc();
 308   new->elt = openscop_relation_copy(r);
 309   return new;
 310 }
 311
 312
 313 /**
 314  * openscop_relation_list_copy function:
 315  * This functions builds and returns a quasi-"hard copy" (not a pointer copy)
 316  * of a openscop_relation_list_t data structure provided as parameter.
 317  * \param list  The pointer to the relation list we want to copy.
 318  * \return A pointer to the full copy of the relation list in parameter.
 319  */
 320 openscop_relation_list_p openscop_relation_list_copy(
 321     openscop_relation_list_p list) {
 322
 323   int first = 1;
 324   openscop_relation_list_p copy = NULL, node, previous = NULL;
 325
 326   while (list != NULL) {
 327     node      = openscop_relation_list_malloc();
 328     node->elt = openscop_relation_copy(list->elt);
 329
 330     if (first) {
 331       first = 0;
 332       copy = node;
 333       previous = node;
 334     }
 335     else {
 336       previous->next = node;
 337       previous = previous->next;
 338     }
 339
 340     list = list->next;
 341   }
 342
 343   return copy;
 344 }
 345
 346
 347 /**
 348  * openscop_relation_list_concat function:
 349  * this function builds a new relation list as the concatenation of the
 350  * two lists sent as parameters.
 351  * \param l1  The first relation list.
 352  * \param l2  The second relation list.
 353  * \return A pointer to the relation list resulting from the concatenation of
 354  *         l1 and l2.
 355  */
 356 openscop_relation_list_p openscop_relation_list_concat(
 357     openscop_relation_list_p l1,
 358     openscop_relation_list_p l2) {
 359
 360   openscop_relation_list_p new, end;
 361
 362   if (l1 == NULL)
 363     return openscop_relation_list_copy(l2);
 364
 365   if (l2 == NULL)
 366     return openscop_relation_list_copy(l1);
 367
 368   new = openscop_relation_list_copy(l1);
 369   end = new;
 370   while (end->next != NULL)
 371     end = end->next;
 372   end->next = openscop_relation_list_copy(l2);
 373
 374   return new;
 375 }
 376
 377
 378 /**
 379  * openscop_relation_list_equal function:
 380  * This function returns true if the two relation lists are the same, false
 381  * otherwise..
 382  * \param l1 The first relation list.
 383  * \param l2 The second relation list.
 384  * \return 1 if l1 and l2 are the same (content-wise), 0 otherwise.
 385  */
 386 int openscop_relation_list_equal(openscop_relation_list_p l1,
 387                                  openscop_relation_list_p l2) {
 388   while ((l1 != NULL) && (l2 != NULL)) {
 389     if (l1 == l2)
 390       return 1;
 391
 392     if (!openscop_relation_equal(l1->elt, l2->elt))
 393       return 0;
 394
 395     l1 = l1->next;
 396     l2 = l2->next;
 397   }
 398
 399   if (((l1 == NULL) && (l2 != NULL)) || ((l1 != NULL) && (l2 == NULL)))
 400     return 0;
 401
 402   return 1;
 403 }
 404
 405
 406 /**
 407  * openscop_relation_integrity_check function:
 408  * This function checks that a list of relation is "well formed" according to
 409  * some expected properties (setting an expected value to OPENSCOP_UNDEFINED
 410  * means that we do not expect a specific value) and what the relations are
 411  * supposed to represent (all relations of a list are supposed to have the
 412  * same semantics). It returns 0 if the check failed or 1 if no problem has
 413  * been detected.
 414  * \param list      The relation list we want to check.
 415  * \param type      Semantics about this relation (domain, access...).
 416  * \param expected_nb_output_dims Expected number of output dimensions.
 417  * \param expected_nb_input_dims  Expected number of input dimensions.
 418  * \param expected_nb_parameters  Expected number of parameters.
 419  * \return 0 if the integrity check fails, 1 otherwise.
 420  */
 421 int openscop_relation_list_integrity_check(openscop_relation_list_p list,
 422                                            int type,
 423                                            int expected_nb_output_dims,
 424                                            int expected_nb_input_dims,
 425                                            int expected_nb_parameters) {
 426   while (list != NULL) {
 427     // Check the access function.
 428     if (( openscop_relation_is_matrix(list->elt) &&
 429          !openscop_relation_integrity_check(list->elt,
 430                                             type,
 431                                             OPENSCOP_UNDEFINED,
 432                                             OPENSCOP_UNDEFINED,
 433                                             OPENSCOP_UNDEFINED)) ||
 434         (!openscop_relation_is_matrix(list->elt) &&
 435          !openscop_relation_integrity_check(list->elt,
 436                                             type,
 437                                             expected_nb_output_dims,
 438                                             expected_nb_input_dims,
 439                                             expected_nb_parameters))) {
 440       return 0;
 441     }
 442
 443     list = list->next;
 444   }
 445
 446   return 1;
 447 }
 448
 449
 450 /**
 451  * openscop_relation_list_set_type function:
 452  * this function sets the type of each relation in the relation list to the
 453  * one provided as parameter.
 454  * \param list The list of relations to set the type.
 455  * \param type The type.
 456  */
 457 void openscop_relation_list_set_type(openscop_relation_list_p list, int type) {
 458
 459   while (list != NULL) {
 460     if (list->elt != NULL) {
 461       list->elt->type = type;
 462     }
 463     list = list->next;
 464   }
 465 }
 466
 467