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