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 void openscop_relation_list_print_elts(FILE * file,
 147                                        openscop_relation_list_p list,
 148                                        openscop_names_p names) {
 149   int i;
 150   openscop_relation_list_p head = list;
 151
 152   // Count the number of elements in the list with non-NULL content.
 153   i = openscop_relation_list_count(list);
 154
 155   // Print each element of the relation list.
 156   if (i > 0) {
 157     i = 0;
 158     while (head) {
 159       if (head->elt != NULL) {
 160         fprintf(file, "# List element No.%d\n", i);
 161         openscop_relation_print(file, head->elt, names);
 162         i++;
 163       }
 164       head = head->next;
 165     }
 166   }
 167 }
 168
 169 /**
 170  * openscop_relation_list_print function:
 171  * This function prints the content of a openscop_relation_list_t structure
 172  * into a file (file, possibly stdout) in the OpenScop format. It prints
 173  * an element of the list only if it is not NULL.
 174  * \param file  File where informations are printed.
 175  * \param list  The relation list whose information have to be printed.
 176  * \param names The textual names of the various elements. Is is important
 177  *              that names->nb_parameters is exact if the matrix
 178  *              representation is used. Set to NULL if printing comments
 179  *              is not needed.
 180  */
 181 void openscop_relation_list_print(FILE * file,
 182                                   openscop_relation_list_p list,
 183                                   openscop_names_p names) {
 184   int i;
 185
 186   // Count the number of elements in the list with non-NULL content.
 187   i = openscop_relation_list_count(list);
 188
 189   // Print it.
 190   if (i > 1)
 191     fprintf(file,"# List of %d elements\n%d\n", i, i);
 192   else
 193     fprintf(file,"# List of %d element \n%d\n", i, i);
 194
 195   // Print each element of the relation list.
 196   openscop_relation_list_print_elts(file, list, names);
 197 }
 198
 199
 200 /*****************************************************************************
 201  *                               Reading function                            *
 202  *****************************************************************************/
 203
 204
 205 /**
 206  * openscop_relation_list_read function:
 207  * This function reads a list of relations into a file (foo,
 208  * posibly stdin) and returns a pointer this relation list.
 209  * \param file  The input stream.
 210  * \return A pointer to the relation list structure that has been read.
 211  */
 212 openscop_relation_list_p openscop_relation_list_read(FILE * file) {
 213   int i;
 214   openscop_relation_list_p list;
 215   openscop_relation_list_p res;
 216   int nb_mat;
 217
 218   // Read the number of relations to read.
 219   nb_mat = openscop_util_read_int(file, NULL);
 220
 221   if (nb_mat < 0) {
 222     fprintf(stderr, "[OpenScop] Error: negative number of relations.\n");
 223     exit(1);
 224   }
 225
 226   // Allocate the header of the list and start reading each element.
 227   res = list = openscop_relation_list_malloc();
 228   for (i = 0; i < nb_mat; ++i) {
 229     list->elt = openscop_relation_read(file);
 230     if (i < nb_mat - 1)
 231       list->next = openscop_relation_list_malloc();
 232     list = list->next;
 233   }
 234
 235   return res;
 236 }
 237
 238
 239 /*+***************************************************************************
 240  *                    Memory allocation/deallocation function                *
 241  *****************************************************************************/
 242
 243
 244 /**
 245  * openscop_relation_list_malloc function:
 246  * This function allocates the memory space for a openscop_relation_list_t
 247  * structure and sets its fields with default values. Then it returns
 248  * a pointer to the allocated space.
 249  * \return A pointer to an empty relation list with fields set to default
 250  *         values.
 251  */
 252 openscop_relation_list_p openscop_relation_list_malloc() {
 253   openscop_relation_list_p res;
 254   res = (openscop_relation_list_p)malloc(sizeof(openscop_relation_list_t));
 255
 256   if (res == NULL) {
 257     fprintf(stderr, "[OpenScop] Error: memory overflow.\n");
 258     exit(1);
 259   }
 260
 261   res->elt = NULL;
 262   res->next = NULL;
 263
 264   return res;
 265 }
 266
 267
 268
 269 /**
 270  * openscop_relation_list_free function:
 271  * This function frees the allocated memory for a openscop_relation_list_t
 272  * structure, and all the relations stored in the list.
 273  * \param list The pointer to the relation list we want to free.
 274  */
 275 void openscop_relation_list_free(openscop_relation_list_p list) {
 276   openscop_relation_list_p tmp;
 277
 278   if (list == NULL)
 279     return;
 280
 281   while (list) {
 282     if (list->elt)
 283       openscop_relation_free(list->elt);
 284     tmp = list->next;
 285     free(list);
 286     list = tmp;
 287   }
 288 }
 289
 290
 291 /*+***************************************************************************
 292  *                            Processing functions                           *
 293  *****************************************************************************/
 294
 295
 296 /**
 297  * openscop_relation_list_node function:
 298  * This function builds an openscop_relation_list_t node and sets its
 299  * relation element as a copy of the one provided as parameter.
 300  * \param r The pointer to the relation to copy/paste in a list node.
 301  * \return A pointer to a relation list node containing a copy of "relation".
 302  */
 303 openscop_relation_list_p openscop_relation_list_node(openscop_relation_p r) {
 304   openscop_relation_list_p new = openscop_relation_list_malloc();
 305   new->elt = openscop_relation_copy(r);
 306   return new;
 307 }
 308
 309
 310 /**
 311  * openscop_relation_list_copy function:
 312  * This functions builds and returns a quasi-"hard copy" (not a pointer copy)
 313  * of a openscop_relation_list_t data structure provided as parameter.
 314  * \param list  The pointer to the relation list we want to copy.
 315  * \return A pointer to the full copy of the relation list in parameter.
 316  */
 317 openscop_relation_list_p openscop_relation_list_copy(
 318     openscop_relation_list_p list) {
 319
 320   int first = 1;
 321   openscop_relation_list_p copy = NULL, node, previous = NULL;
 322
 323   while (list != NULL) {
 324     node      = openscop_relation_list_malloc();
 325     node->elt = openscop_relation_copy(list->elt);
 326
 327     if (first) {
 328       first = 0;
 329       copy = node;
 330       previous = node;
 331     }
 332     else {
 333       previous->next = node;
 334       previous = previous->next;
 335     }
 336
 337     list = list->next;
 338   }
 339
 340   return copy;
 341 }
 342
 343
 344 /**
 345  * openscop_relation_list_concat function:
 346  * this function builds a new relation list as the concatenation of the
 347  * two lists sent as parameters.
 348  * \param l1  The first relation list.
 349  * \param l2  The second relation list.
 350  * \return A pointer to the relation list resulting from the concatenation of
 351  *         l1 and l2.
 352  */
 353 openscop_relation_list_p openscop_relation_list_concat(
 354     openscop_relation_list_p l1,
 355     openscop_relation_list_p l2) {
 356
 357   openscop_relation_list_p new, end;
 358
 359   if (l1 == NULL)
 360     return openscop_relation_list_copy(l2);
 361
 362   if (l2 == NULL)
 363     return openscop_relation_list_copy(l1);
 364
 365   new = openscop_relation_list_copy(l1);
 366   end = new;
 367   while (end->next != NULL)
 368     end = end->next;
 369   end->next = openscop_relation_list_copy(l2);
 370
 371   return new;
 372 }
 373
 374
 375 /**
 376  * openscop_relation_list_equal function:
 377  * This function returns true if the two relation lists are the same, false
 378  * otherwise..
 379  * \param l1 The first relation list.
 380  * \param l2 The second relation list.
 381  * \return 1 if l1 and l2 are the same (content-wise), 0 otherwise.
 382  */
 383 int openscop_relation_list_equal(openscop_relation_list_p l1,
 384                                  openscop_relation_list_p l2) {
 385   while ((l1 != NULL) && (l2 != NULL)) {
 386     if (l1 == l2)
 387       return 1;
 388
 389     if (!openscop_relation_equal(l1->elt, l2->elt))
 390       return 0;
 391
 392     l1 = l1->next;
 393     l2 = l2->next;
 394   }
 395
 396   if (((l1 == NULL) && (l2 != NULL)) || ((l1 != NULL) && (l2 == NULL)))
 397     return 0;
 398
 399   return 1;
 400 }
 401
 402
 403 /**
 404  * openscop_relation_integrity_check function:
 405  * This function checks that a list of relation is "well formed" according to
 406  * some expected properties (setting an expected value to OPENSCOP_UNDEFINED
 407  * means that we do not expect a specific value) and what the relations are
 408  * supposed to represent (all relations of a list are supposed to have the
 409  * same semantics). It returns 0 if the check failed or 1 if no problem has
 410  * been detected.
 411  * \param list      The relation list we want to check.
 412  * \param type      Semantics about this relation (domain, access...).
 413  * \param expected_nb_output_dims Expected number of output dimensions.
 414  * \param expected_nb_input_dims  Expected number of input dimensions.
 415  * \param expected_nb_parameters  Expected number of parameters.
 416  * \return 0 if the integrity check fails, 1 otherwise.
 417  */
 418 int openscop_relation_list_integrity_check(openscop_relation_list_p list,
 419                                            int type,
 420                                            int expected_nb_output_dims,
 421                                            int expected_nb_input_dims,
 422                                            int expected_nb_parameters) {
 423   while (list != NULL) {
 424     // Check the access function.
 425     if (( openscop_relation_is_matrix(list->elt) &&
 426          !openscop_relation_integrity_check(list->elt,
 427                                             type,
 428                                             OPENSCOP_UNDEFINED,
 429                                             OPENSCOP_UNDEFINED,
 430                                             OPENSCOP_UNDEFINED)) ||
 431         (!openscop_relation_is_matrix(list->elt) &&
 432          !openscop_relation_integrity_check(list->elt,
 433                                             type,
 434                                             expected_nb_output_dims,
 435                                             expected_nb_input_dims,
 436                                             expected_nb_parameters))) {
 437       return 0;
 438     }
 439
 440     list = list->next;
 441   }
 442
 443   return 1;
 444 }
 445
 446
 447 /**
 448  * openscop_relation_list_set_type function:
 449  * this function sets the type of each relation in the relation list to the
 450  * one provided as parameter.
 451  * \param list The list of relations to set the type.
 452  * \param type The type.
 453  */
 454 void openscop_relation_list_set_type(openscop_relation_list_p list, int type) {
 455
 456   while (list != NULL) {
 457     if (list->elt != NULL) {
 458       list->elt->type = type;
 459     }
 460     list = list->next;
 461   }
 462 }
 463
 464
 465 /**
 466  * openscop_relation_list_filter function:
 467  * this function returns a copy of the input relation list, restricted to
 468  * the relations of a given type. The special type OPENSCOP_TYPE_ACCESS
 469  * filters any kind of access (read, write, rdwr etc.).
 470  * \param list The relation list to copy/filter.
 471  * \param type The filtering type.
 472  * \return A copy of the input list with only relation of the given type.
 473  */
 474 openscop_relation_list_p openscop_relation_list_filter(
 475     openscop_relation_list_p list,
 476     int type) {
 477
 478   openscop_relation_list_p copy = openscop_relation_list_copy(list);
 479   openscop_relation_list_p filtered = NULL;
 480   openscop_relation_list_p previous = NULL;
 481   openscop_relation_list_p trash;
 482   int first = 1;
 483
 484   while (copy != NULL) {
 485     if (((type == OPENSCOP_TYPE_ACCESS) &&
 486          (openscop_relation_is_access(copy->elt))) ||
 487         ((type != OPENSCOP_TYPE_ACCESS) &&
 488          (type == copy->elt->type))) {
 489       if (first) {
 490         filtered = copy;
 491         first = 0;
 492       }
 493
 494       previous = copy;
 495       copy = copy->next;
 496     }
 497     else {
 498       trash = copy;
 499       if (!first)
 500         previous->next = copy->next;
 501       copy = copy->next;
 502       trash->next = NULL;
 503       openscop_relation_list_free(trash);
 504     }
 505   }
 506
 507   return filtered;
 508 }
 509
 510
 511 /**
 512  * openscop_relation_list_count function:
 513  * this function returns the number of elements with non-NULL content
 514  * in a relation list.
 515  * \param list The relation list to count the number of elements.
 516  * \return The number of nodes with non-NULL content in the relation list.
 517  */
 518 int openscop_relation_list_count(openscop_relation_list_p list) {
 519   int i = 0;
 520
 521   while (list != NULL) {
 522     if (list->elt != NULL)
 523       i++;
 524     list = list->next;
 525   }
 526
 527   return i;
 528 }
 529
 530