source/extensions/arrays.c

   1
   2     /*+-----------------------------------------------------------------**
   3      **                       OpenScop Library                          **
   4      **-----------------------------------------------------------------**
   5      **                      extensions/arrays.c                        **
   6      **-----------------------------------------------------------------**
   7      **                   First version: 07/12/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 # include <stdlib.h>
  64 # include <stdio.h>
  65 # include <string.h>
  66 # include <ctype.h>
  67 # include <openscop/extension.h>
  68
  69
  70 /*+***************************************************************************
  71  *                          Structure display function                       *
  72  *****************************************************************************/
  73
  74
  75 /**
  76  * openscop_arrays_print_structure function:
  77  * this function displays a openscop_arrays_t structure (*arrays) into a file
  78  * (file, possibly stdout) in a way that trends to be understandable. It
  79  * includes an indentation level (level) in order to work with others
  80  * print_structure functions.
  81  * \param file   The file where the information has to be printed.
  82  * \param arrays The arrays structure whose information has to be printed.
  83  * \param level  Number of spaces before printing, for each line.
  84  */
  85 void
  86 openscop_arrays_print_structure(FILE * file, openscop_arrays_p arrays,
  87                                 int level)
  88 {
  89   int i, j;
  90
  91   // Go to the right level.
  92   for (j = 0; j < level; j++)
  93     fprintf(file, "|\t");
  94
  95   if (arrays != NULL)
  96     fprintf(file, "+-- openscop_arrays_t\n");
  97   else
  98     fprintf(file, "+-- NULL arrays\n");
  99
 100   if (arrays != NULL)
 101   {
 102     // Go to the right level.
 103     for(j = 0; j <= level; j++)
 104       fprintf(file, "|\t");
 105
 106     // Display the number of names.
 107     fprintf(file, "nb_names: %d\n", arrays->nb_names);
 108
 109     // Display the id/name.
 110     for(i = 0; i < arrays->nb_names; i++)
 111     {
 112       // Go to the right level.
 113       for(j = 0; j <= level; j++)
 114         fprintf(file, "|\t");
 115
 116       fprintf(file, "id: %2d, name: %s\n", arrays->id[i], arrays->names[i]);
 117     }
 118   }
 119
 120   // The last line.
 121   for (j = 0; j <= level; j++)
 122     fprintf(file, "|\t");
 123   fprintf(file, "\n");
 124 }
 125
 126
 127 /**
 128  * openscop_arrays_print function:
 129  * this function prints the content of an openscop_arrays_t structure
 130  * (*arrays) into a file (file, possibly stdout).
 131  * \param file   The file where the information has to be printed.
 132  * \param arrays The arrays structure whose information has to be printed.
 133  */
 134 void
 135 openscop_arrays_print(FILE * file, openscop_arrays_p arrays)
 136 {
 137   openscop_arrays_print_structure(file, arrays, 0);
 138 }
 139
 140
 141 /**
 142  * openscop_arrays_print_openscop function:
 143  * this function prints the content of an openscop_arrays_t structure
 144  * (*arrays) into a string (returned) in the OpenScop textual format.
 145  * \param  arrays The arrays structure whose information has to be printed.
 146  * \return A string containing the OpenScop dump of the arrays structure.
 147  */
 148 char *
 149 openscop_arrays_print_openscop(openscop_arrays_p arrays)
 150 {
 151   int i;
 152   int high_water_mark = OPENSCOP_MAX_STRING;
 153   char * string = NULL;
 154   char * buffer;
 155
 156   if (arrays != NULL)
 157   {
 158     string = (char *)malloc(high_water_mark * sizeof(char));
 159     buffer = (char *)malloc(OPENSCOP_MAX_STRING * sizeof(char));
 160     if ((string == NULL) || (buffer == NULL))
 161     {
 162       fprintf(stderr, "[OpenScop] Error: memory overflow.\n");
 163       exit(1);
 164     }
 165     string[0] = '\0';
 166
 167     sprintf(buffer, OPENSCOP_TAG_ARRAY_START);
 168     openscop_util_safe_strcat(&string, buffer, &high_water_mark);
 169
 170     sprintf(buffer, "\n%d\n", arrays->nb_names);
 171     openscop_util_safe_strcat(&string, buffer, &high_water_mark);
 172
 173     for (i = 0; i < arrays->nb_names; i++)
 174     {
 175       sprintf(buffer, "%d %s\n", arrays->id[i], arrays->names[i]);
 176       openscop_util_safe_strcat(&string, buffer, &high_water_mark);
 177     }
 178     sprintf(buffer, OPENSCOP_TAG_ARRAY_STOP"\n");
 179     openscop_util_safe_strcat(&string, buffer, &high_water_mark);
 180
 181     string = (char *)realloc(string, (strlen(string) + 1) * sizeof(char));
 182     free(buffer);
 183   }
 184
 185   return string;
 186 }
 187
 188
 189 /*****************************************************************************
 190  *                               Reading function                            *
 191  *****************************************************************************/
 192
 193
 194 /**
 195  * openscop_arrays_read function:
 196  * this function reads an arrays structure from a string complying to the
 197  * OpenScop textual format and returns a pointer to this arrays structure.
 198  * The string should contain only one textual format of an arrays structure.
 199  * \param  extensions The input string where to find an arrays structure.
 200  * \return A pointer to the arrays structure that has been read.
 201  */
 202 openscop_arrays_p
 203 openscop_arrays_read(char * extensions)
 204 {
 205   int i, k, array_id;
 206   int  nb_names;
 207   int  *  id;
 208   char ** names;
 209   char * content, * content_backup;
 210   char buff[OPENSCOP_MAX_STRING];
 211   openscop_arrays_p arrays;
 212
 213   content = openscop_util_tag_content(extensions, OPENSCOP_TAG_ARRAY_START,
 214                                                   OPENSCOP_TAG_ARRAY_STOP);
 215
 216   if (content == NULL)
 217   {
 218     fprintf(stderr, "[OpenScop] Info: no array optional tag.\n");
 219     return NULL;
 220   }
 221   content_backup = content;
 222
 223   // Find the number of names provided.
 224   nb_names = openscop_util_read_int(NULL, &content);
 225
 226   // Allocate the array of id and names.
 227   id = (int *)malloc(nb_names * sizeof(int));
 228   names = (char **)malloc(nb_names * sizeof(char *));
 229   for (i = 0; i < nb_names; i++)
 230     names[i] = NULL;
 231
 232   // Get each array name.
 233   for (k = 0; k < nb_names; k++)
 234   {
 235     // Skip blank or commented lines.
 236     while (*content == '#' || *content == '\n')
 237     {
 238       for (; *content != '\n'; ++content)
 239         continue;
 240       ++content;
 241     }
 242
 243     // Get the array name id.
 244     for (i = 0; *content && ! isspace(*content); ++i, ++content)
 245       buff[i] = *content;
 246     buff[i] = '\0';
 247     sscanf(buff, "%d", &array_id);
 248     if (array_id <= 0)
 249     {
 250       fprintf(stderr, "[OpenScop] Error: array id must be > 0.\n");
 251       exit(1);
 252     }
 253     id[k] = array_id;
 254
 255     // Get the array name string.
 256     while (*content && isspace(*content))
 257       ++content;
 258     for (i = 0; *content && ! isspace(*content); ++i, ++content)
 259       buff[i] = *content;
 260     buff[i] = '\0';
 261     names[k] = strdup(buff);
 262
 263     // Go to the end of line.
 264     while (*content && *content != '\n')
 265       ++content;
 266   }
 267   free(content_backup);
 268
 269   arrays = openscop_arrays_malloc();
 270   arrays->nb_names = nb_names;
 271   arrays->id       = id;
 272   arrays->names    = names;
 273
 274   return arrays;
 275 }
 276
 277
 278 /*+***************************************************************************
 279  *                    Memory allocation/deallocation function                *
 280  *****************************************************************************/
 281
 282
 283 /**
 284  * openscop_arrays_malloc function:
 285  * This function allocates the memory space for an openscop_arrays_t
 286  * structure and sets its fields with default values. Then it returns a
 287  * pointer to the allocated space.
 288  * \return A pointer to an empty arrays structure with fields set to
 289  *         default values.
 290  */
 291 openscop_arrays_p
 292 openscop_arrays_malloc()
 293 {
 294   openscop_arrays_p arrays;
 295
 296   arrays = (openscop_arrays_p)malloc(sizeof(openscop_arrays_t));
 297   if (arrays == NULL)
 298   {
 299     fprintf(stderr, "[OpenScop] Error: memory overflow.\n");
 300     exit(1);
 301   }
 302
 303   arrays->nb_names = 0;
 304   arrays->id       = NULL;
 305   arrays->names    = NULL;
 306
 307   return arrays;
 308 }
 309
 310
 311 /**
 312  * openscop_arrays_free function:
 313  * This function frees the allocated memory for an arrays structure.
 314  * \param arrays The pointer to the arrays structure we want to free.
 315  */
 316 void
 317 openscop_arrays_free(openscop_arrays_p arrays)
 318 {
 319   int i;
 320
 321   if (arrays != NULL)
 322   {
 323     if (arrays->names != NULL)
 324     {
 325       free(arrays->id);
 326       for (i = 0; i < arrays->nb_names; i++)
 327         free(arrays->names[i]);
 328       free(arrays->names);
 329     }
 330
 331     free(arrays);
 332   }
 333 }
 334
 335
 336 /*+***************************************************************************
 337  *                            Processing functions                           *
 338  *****************************************************************************/
 339
 340
 341 /**
 342  * openscop_arrays_copy function:
 343  * This function builds and returns a "hard copy" (not a pointer copy) of an
 344  * openscop_arrays_t data structure.
 345  * \param arrays The pointer to the arrays structure we want to copy.
 346  * \return A pointer to the copy of the arrays structure.
 347  */
 348 openscop_arrays_p
 349 openscop_arrays_copy(openscop_arrays_p arrays)
 350 {
 351   openscop_arrays_p copy;
 352   int i;
 353
 354   if (arrays == NULL)
 355     return NULL;
 356
 357   copy = openscop_arrays_malloc();
 358   if (copy != NULL)
 359   {
 360     copy->nb_names = arrays->nb_names;
 361     copy->id = (int *)malloc(arrays->nb_names * sizeof(int));
 362     copy->names = (char **)malloc(arrays->nb_names * sizeof(char*));
 363     if ((copy->id == NULL) || (copy->names == NULL))
 364     {
 365       fprintf(stderr, "[OpenScop] Error: memory overflow.\n");
 366       exit(1);
 367     }
 368     for (i = 0; i < arrays->nb_names; i++)
 369     {
 370       copy->id[i] = arrays->id[i];
 371       copy->names[i] = strdup(arrays->names[i]);
 372       if ((copy->names[i] == NULL) && (arrays->names[i] != NULL))
 373       {
 374         fprintf(stderr, "[OpenScop] Error: memory overflow.\n");
 375         exit(1);
 376       }
 377     }
 378   }
 379
 380   return copy;
 381 }
 382
 383
 384 /**
 385  * openscop_arrays_equal function:
 386  * this function returns true if the two arrays structures are the same
 387  * (content-wise), false otherwise. This functions considers two arrays
 388  * structures as equal if the order of the array names differ, however the
 389  * identifiers and names must be the same.
 390  * \param a1  The first arrays structure.
 391  * \param a2  The second arrays structure.
 392  * \return 1 if a1 and a2 are the same (content-wise), 0 otherwise.
 393  */
 394 int
 395 openscop_arrays_equal(openscop_arrays_p a1, openscop_arrays_p a2)
 396 {
 397   int i, j, found;
 398
 399   if ((a1 == NULL) && (a2 == NULL))
 400     return 1;
 401
 402   if (((a1 == NULL) && (a2 != NULL)) || ((a1 != NULL) && (a2 == NULL)))
 403     return 0;
 404
 405   // Check whether the number of names is the same.
 406   if (a1->nb_names != a2->nb_names)
 407     return 0;
 408
 409   // We accept a different order of the names, as long as the identifiers
 410   // are the same.
 411   for (i = 0; i < a1->nb_names; i++)
 412   {
 413     found = 0;
 414     for (j = 0; j < a2->nb_names; j++)
 415     {
 416       if ((a1->id[i] == a2->id[j]) && (!strcmp(a1->names[i], a2->names[j])))
 417       {
 418         found = 1;
 419         break;
 420       }
 421     }
 422     if (found != 1)
 423       return 0;
 424   }
 425
 426   return 1;
 427 }
 428
 429
 430 /**
 431  * openscop_arrays_generate_names function:
 432  * This function generates an array of strings corresponding to array names.
 433  * The ith string will correspond to the array name with identifier i in the
 434  * arrays structure. If some identifiers are missing, the corresponding names
 435  * will be generated. The size of the array of strings corresponds to the
 436  * maximum identifier, it is returned using the parameter nb_names.
 437  * \param arrays   The source of some array names.
 438  * \param nb_names Pointer to the location to store the number of names.
 439  * \return An array of strings corresponding to the array names.
 440  */
 441 char **
 442 openscop_arrays_generate_names(openscop_arrays_p arrays, int * nb_names)
 443 {
 444   char ** names = NULL;
 445   char ** tmpnames;
 446   int i;
 447
 448   *nb_names = 0;
 449
 450   if (arrays != NULL)
 451   {
 452     // Get the maximum id (it will be nb_names).
 453     for (i = 0; i < arrays->nb_names; i++)
 454       if (arrays->id[i] > *nb_names)
 455         *nb_names = arrays->id[i];
 456
 457     // Allocate the array of names and store the existing names.
 458     names = (char **)malloc(*nb_names * sizeof(char *));
 459     if (names == NULL)
 460     {
 461       fprintf(stderr, "[OpenScop] Error: memory overflow.\n");
 462       exit(1);
 463     }
 464     for (i = 0; i < arrays->nb_names; i++)
 465     {
 466       names[arrays->id[i] - 1] = strdup(arrays->names[i]);
 467       if (names[arrays->id[i] - 1] == NULL)
 468       {
 469         fprintf(stderr, "[OpenScop] Error: memory overflow.\n");
 470         exit(1);
 471       }
 472     }
 473
 474     // Fill the missing names.
 475     tmpnames = openscop_util_strings_generate("A_", *nb_names);
 476     for (i = 0; i < *nb_names; i++)
 477     {
 478       if (names[i] == NULL || names[i][0] == '\0')
 479         names[i] = tmpnames[i]; // Use a generated name.
 480       else
 481         free(tmpnames[i]);      // Use a read name.
 482     }
 483     free(tmpnames);
 484   }
 485
 486   return names;
 487 }
 488
 489