source/util.c

   1
   2     /*+-----------------------------------------------------------------**
   3      **                       OpenScop Library                          **
   4      **-----------------------------------------------------------------**
   5      **                            util.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 # include <stdlib.h>
  64 # include <stdio.h>
  65 # include <ctype.h>
  66 # include <string.h>
  67 # include <openscop/util.h>
  68
  69
  70 /*+***************************************************************************
  71  *                       Functions on arrays of strings                      *
  72  *****************************************************************************/
  73
  74
  75 /**
  76  * openscop_util_strings_idump function:
  77  * this function displays an array of strings into a file (file, possibly
  78  * stdout) in a way that trends to be understandable. It includes an
  79  * 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 strings    The array of strings that has to be printed.
  83  * \param nb_strings The number of strings in the array of strings.
  84  * \param level      Number of spaces before printing, for each line.
  85  * \param title      A string to use as a title for the array of strings.
  86  */
  87 void openscop_util_strings_idump(FILE * file,
  88                                  char ** strings, int nb_strings,
  89                                  int level,
  90                                  char * title) {
  91   int i;
  92
  93   // Print the original parameter names.
  94   for (i = 0; i <= level; i++)
  95     fprintf(file, "|\t");
  96   if ((strings != NULL) && (nb_strings > 0)) {
  97     fprintf(file, "+-- %s:", title);
  98     for (i = 0; i < nb_strings; i++)
  99       fprintf(file, " %s", strings[i]);
 100     fprintf(file, "\n");
 101   }
 102   else
 103     fprintf(file, "+-- No %s\n", title);
 104
 105   // A blank line.
 106   for (i = 0; i <= level+1; i++)
 107     fprintf(file, "|\t");
 108   fprintf(file, "\n");
 109 }
 110
 111
 112 /**
 113  * openscop_util_strings_print function:
 114  * this function prints the content of an array of strings
 115  * into a file (file, possibly stdout) in the OpenScop textual format.
 116  * \param file       The file where the information has to be printed.
 117  * \param strings    The array of strings that has to be printed.
 118  * \param nb_strings The number of strings in the array of strings.
 119  * \param print      Boolean not set to 0 to print the names, 0 otherwise.
 120  * \param title      A string to use as a title for the array of strings.
 121  */
 122 void openscop_util_strings_print(FILE * file,
 123                                  char ** strings, int nb_strings,
 124                                  int print,
 125                                  char * title) {
 126   int i;
 127
 128   if ((print != 0) && (strings != NULL) && (nb_strings > 0)) {
 129     fprintf(file, "# %s are provided\n", title);
 130     fprintf(file, "1\n");
 131     fprintf(file, "# %s\n", title);
 132     for (i = 0; i < nb_strings; i++)
 133       fprintf(file, "%s ", strings[i]);
 134     fprintf(file, "\n\n");
 135   }
 136   else {
 137     fprintf(file, "# %s are not provided\n", title);
 138     fprintf(file, "0\n\n");
 139   }
 140 }
 141
 142
 143 /**
 144  * openscop_util_strings_read function.
 145  * this function reads an array of strings from a file (possibly stdin)
 146  * complying to the OpenScop textual format and returns a pointer to this
 147  * array as well as the number of elements of this array (through the
 148  * parameter nb_strings).
 149  * \param file       The file where to read the array of strings.
 150  * \param nb_strings Pointer to where to store the number of strings (output).
 151  * \return The array of strings that has been read.
 152  */
 153 char ** openscop_util_strings_read(FILE * file, int * nb_strings) {
 154   char str[OPENSCOP_MAX_STRING];
 155   char tmp[OPENSCOP_MAX_STRING];
 156   char * s, * start;
 157   char ** strings = NULL;
 158   int i, count;
 159
 160   // Skip blank/commented lines and spaces.
 161   start = openscop_util_skip_blank_and_comments(file, str);
 162
 163   // Count the actual number of strings.
 164   *nb_strings = 0;
 165   s = start;
 166   while (1) {
 167     for (count = 0; *s && ! isspace(*s) && *s != '#'; ++count)
 168       s++;
 169
 170     if (count != 0)
 171       (*nb_strings)++;
 172
 173     if ((*s == '#') || (*s == '\n'))
 174       break;
 175     else
 176       ++s;
 177   }
 178
 179   if (*nb_strings > 0) {
 180     // Allocate the array of strings. Make it NULL-terminated.
 181     strings = (char **) malloc(sizeof(char *) * ((*nb_strings) + 1));
 182     if (strings == NULL) {
 183       fprintf(stderr, "[OpenScop] Error: memory overflow.\n");
 184       exit(1);
 185     }
 186     strings[*nb_strings] = NULL;
 187
 188     // Read the desired number of strings.
 189     s = start;
 190     for (i = 0; i < *nb_strings; ++i) {
 191       for (count = 0; *s && ! isspace(*s) && *s != '#'; ++count)
 192         tmp[count] = *(s++);
 193       tmp[count] = '\0';
 194       strings[i] = strdup(tmp);
 195       if (strings[i] == NULL) {
 196         fprintf(stderr, "[OpenScop] Error: memory overflow.\n");
 197         exit(1);
 198       }
 199       if (*s != '#')
 200         ++s;
 201     }
 202   }
 203
 204   return strings;
 205 }
 206
 207
 208 /**
 209  * openscop_util_strings_generate function:
 210  * This function generates an array of size 'nb' of strings of the form
 211  * "prefixXX" where XX goes from 1 to nb.
 212  * \param prefix     The prefix of the generated names.
 213  * \param nb_strings The number of strings to generate.
 214  * \return An array of 'nb' generated strings.
 215  */
 216 char ** openscop_util_strings_generate(char * prefix, int nb_strings) {
 217   char ** strings = NULL;
 218   char buff[strlen(prefix) + 16]; // TODO: better (log10(INT_MAX) ?) :-D.
 219   int i;
 220
 221   if (nb_strings) {
 222     strings = (char **)malloc(sizeof(char *) * nb_strings);
 223     if (strings == NULL) {
 224       fprintf(stderr, "[OpenScop] Error: memory overflow.\n");
 225       exit(1);
 226     }
 227     for (i = 0; i < nb_strings; i++) {
 228       sprintf(buff, "%s%d", prefix, i + 1);
 229       strings[i] = strdup(buff);
 230       if (strings[i] == NULL) {
 231         fprintf(stderr, "[OpenScop] Error: memory overflow.\n");
 232         exit(1);
 233       }
 234     }
 235   }
 236
 237   return strings;
 238 }
 239
 240
 241 /**
 242  * openscop_util_strings_complete function:
 243  * this function completes an array of strings with generated strings.
 244  * \param strings     Pointer to the initial array of strings (modified).
 245  * \param nb_strings  Pointer to the initial number of strings (modified).
 246  * \param prefix      The prefix of the generated names.
 247  * \param nb_complete The desired number of strings in the new array.
 248  */
 249 void openscop_util_strings_complete(char *** strings, int * nb_strings,
 250                                     char *   prefix,  int   nb_complete) {
 251   int i, nb_new;
 252   char ** completion;
 253
 254   nb_new = nb_complete - *nb_strings;
 255   if (nb_new < 0) {
 256     fprintf(stderr, "[OpenScop] Error: asked to complete the following "
 257                     "string array but it would be smaller than the original "
 258                     "(desired length: %d):\n", nb_complete);
 259     openscop_util_strings_idump(stderr, *strings, *nb_strings, -1,
 260                                 "To be completed");
 261     exit(1);
 262   }
 263
 264   if (nb_new > 0) {
 265     *strings = (char **)realloc(*strings, nb_complete * sizeof(char *));
 266     completion = openscop_util_strings_generate(prefix, nb_new);
 267     for (i = 0; i < nb_new; i++)
 268       (*strings)[i + *nb_strings] = completion[i];
 269     free(completion);
 270     *nb_strings = nb_complete;
 271   }
 272 }
 273
 274
 275 /**
 276  * openscop_util_strings_free function:
 277  * this function frees the allocated memory for an array of strings.
 278  * \param strings The array of strings we want to free.
 279  * \param nb_strings The number of strings in the array of strings.
 280  */
 281 void openscop_util_strings_free(char ** strings, int nb_strings) {
 282   int i;
 283
 284   if (strings != NULL) {
 285     for (i = 0; i < nb_strings; i++)
 286       if (strings[i] != NULL)
 287         free(strings[i]);
 288     free(strings);
 289   }
 290 }
 291
 292
 293 /**
 294  * openscop_util_copy_strings internal function.
 295  * this function builds and return a "hard copy" (not a pointer copy) of an
 296  * array of strings provided as parameter.
 297  * \param strings    The array of strings to copy.
 298  * \param nb_strings The number of strings in the array to copy.
 299  * \return The copy of the array of strings.
 300  */
 301 char ** openscop_util_strings_copy(char ** strings, int nb_strings) {
 302   int i;
 303   char ** copy;
 304
 305   if ((strings == NULL) || (nb_strings == 0))
 306     return NULL;
 307
 308   copy = (char **)malloc(nb_strings * sizeof(char *));
 309   if (copy == NULL)  {
 310     fprintf(stderr, "[OpenScop] Error: memory overflow.\n");
 311     exit(1);
 312   }
 313   for (i = 0; i < nb_strings; i++) {
 314     copy[i] = strdup(strings[i]);
 315     if (copy[i] == NULL) {
 316       fprintf(stderr, "[OpenScop] Error: memory overflow.\n");
 317       exit(1);
 318     }
 319   }
 320
 321   return copy;
 322 }
 323
 324
 325 /**
 326  * openscop_util_strings_equal function:
 327  * this function returns true if the two arrays of strings are the same
 328  * (content-wise), false otherwise.
 329  * \param s1    The first array of strings.
 330  * \param nb_s1 The number of strings in the first array of string.
 331  * \param s2    The second array of strings.
 332  * \param nb_s2 The number of strings in the second array of string.
 333  * \return 1 if s1 and s2 are the same (content-wise), 0 otherwise.
 334  */
 335 int openscop_util_strings_equal(char ** s1, int nb_s1, char ** s2, int nb_s2) {
 336   int i;
 337
 338   if (s1 == s2)
 339     return 1;
 340
 341   if (((s1 == NULL) && (s2 != NULL)) ||
 342       ((s1 != NULL) && (s2 == NULL)) ||
 343       (nb_s1 != nb_s2))
 344     return 0;
 345
 346   for (i = 0; i < nb_s1; i++)
 347     if (strcmp(s1[i], s2[i]) != 0)
 348       return 0;
 349
 350   return 1;
 351 }
 352
 353
 354 /*+***************************************************************************
 355  *                             Utility functions                             *
 356  *****************************************************************************/
 357
 358
 359 /**
 360  * openscop_util_skip_blank_and_comments internal function.
 361  * This function reads the open file 'file' line by line and skips
 362  * blank/comment lines and spaces. The first line where there is some
 363  * useful information is stored at the address 'str' (the memory to
 364  * store the line must be allocated before the call to this function
 365  * and must be at least OPENSCOP_MAX_STRING*sizeof(char)). The pointer
 366  * to the first useful information in this line is returned by the
 367  * function.
 368  * \param file The (opened) file to read.
 369  * \param str  Address of an allocated space to store the first line
 370  *             that contains useful information.
 371  * \return The address of the the first useful digit in str.
 372  */
 373 char * openscop_util_skip_blank_and_comments(FILE * file, char * str) {
 374   char * start;
 375
 376   do {
 377     start = fgets(str, OPENSCOP_MAX_STRING, file);
 378     while ((start != NULL) && isspace(*start) && (*start != '\n'))
 379       start++;
 380   }
 381   while (start != NULL && (*start == '#' || *start == '\n'));
 382
 383   return start;
 384 }
 385
 386
 387 /**
 388  * openscop_util_read_int internal function.
 389  * Read an int on the input 'file' or the input string 'str' depending on
 390  * which one is not NULL (exactly one of them must not be NULL).
 391  * \param file The file where to read an int (if not NULL).
 392  * \param str  The string where to read an int (if not NULL). This pointer
 393  *             is updated to reflect the read and points after the int.
 394  * \return The int that have been read.
 395  */
 396 int openscop_util_read_int(FILE * file, char ** str) {
 397   char s[OPENSCOP_MAX_STRING], * start;
 398   int res;
 399   int i = 0;
 400   int read_int = 0;
 401
 402   if ((file != NULL && str != NULL) || (file == NULL && str == NULL)) {
 403     fprintf(stderr, "[OpenScop] Error: one and only one of the two parameters"
 404                     " of util_read_int can be non-NULL\n");
 405     exit (1);
 406   }
 407
 408   if (file != NULL) {
 409     // Parse from a file.
 410     start = openscop_util_skip_blank_and_comments(file, s);
 411     if (sscanf(start, " %d", &res) != 1) {
 412       fprintf(stderr, "[OpenScop] Error: an int was expected.\n");
 413       exit(1);
 414     }
 415   }
 416   if (str != NULL) {
 417     // Parse from a string.
 418     // Skip blank/commented lines.
 419     do {
 420       while (*str && **str && isspace(**str))
 421         ++(*str);
 422       if (**str == '#') {
 423         while (**str && **str != '\n')
 424           ++(*str);
 425       }
 426       else {
 427         // Build the chain to analyze.
 428         while (**str && !isspace(**str) && **str != '\n')
 429           s[i++] = *((*str)++);
 430         s[i] = '\0';
 431         if (sscanf(s, "%d", &res) != 1) {
 432           fprintf(stderr, "[OpenScop] Error: an int was expected.\n");
 433           exit(1);
 434         }
 435         read_int = 1;
 436       }
 437     }
 438     while (! read_int);
 439   }
 440
 441   return res;
 442 }
 443
 444
 445 /**
 446  * openscop_util_read_tail function:
 447  * this function puts the remainder of a file (from the current file pointer to
 448  * the end of the file) to a string and returns this string. This excepts the
 449  * first blank or commented lines (commented according to the OpenScop textual
 450  * format).
 451  * \param  file The file where to read the tail.
 452  * \return The string corresponding to the tail of the input file.
 453  */
 454 char * openscop_util_read_tail(FILE * file) {
 455   int high_water_mark = OPENSCOP_MAX_STRING;
 456   int nb_chars = 0;
 457   char buff[OPENSCOP_MAX_STRING], *c;
 458   char * extensions;
 459
 460   // - Skip blank/commented lines and spaces.
 461   c = openscop_util_skip_blank_and_comments(file, buff);
 462   if (c ==  NULL)
 463     return NULL;
 464
 465   extensions = (char *)malloc(high_water_mark * sizeof(char));
 466   if (extensions == NULL) {
 467     fprintf(stderr, "[OpenScop] Error: memory overflow.\n");
 468     exit(1);
 469   }
 470
 471   strcpy(extensions, c);
 472   nb_chars = strlen(c);
 473
 474   // - Copy everything else to the option tags field.
 475   while (!feof(file)) {
 476     extensions[nb_chars] = fgetc(file);
 477     nb_chars++;
 478
 479     if (nb_chars >= high_water_mark) {
 480       high_water_mark += high_water_mark;
 481       extensions = (char *)realloc(extensions, high_water_mark * sizeof(char));
 482       if (extensions == NULL) {
 483         fprintf(stderr, "[OpenScop] Error: memory overflow.\n");
 484         exit(1);
 485       }
 486     }
 487   }
 488
 489   // - 0-terminate the string.
 490   extensions = (char *)realloc(extensions, nb_chars * sizeof(char));
 491   extensions[nb_chars - 1] = '\0';
 492
 493   return extensions;
 494 }
 495
 496
 497 /**
 498  * openscop_util_tag_content function:
 499  * This function returns a freshly allocated string containing the
 500  * content, in the given string 'str', between the tag 'tag' and
 501  * the tag 'endtag'. If the tag 'tag' is not found, returns NULL.
 502  * \param str    The string where to find a given content.
 503  * \param tag    The string that marks the beginning of the content.
 504  * \param endtag The string that marks the end of the content.
 505  * \return The string between 'tag' and 'endtag' in 'str'.
 506  */
 507 char * openscop_util_tag_content(char * str, char * tag, char * endtag) {
 508   int i;
 509   char * start;
 510   char * stop;
 511   int size = 0;
 512   int lentag;
 513   char * res = NULL;
 514
 515   if (str) {
 516     start = str;
 517     lentag = strlen(tag);
 518     for (; start && *start && strncmp(start, tag, lentag); ++start)
 519       continue;
 520
 521     // The tag 'tag' was not found.
 522     if (! *start)
 523       return NULL;
 524     start += lentag;
 525     stop = start;
 526     lentag = strlen(endtag);
 527     for (size = 0; *stop && strncmp(stop, endtag, lentag); ++stop, ++size)
 528       continue;
 529
 530     // the tag 'endtag' was not found.
 531     if (! *stop)
 532       return NULL;
 533     res = (char *)malloc((size + 1) * sizeof(char));
 534     if (res == NULL) {
 535       fprintf(stderr, "[OpenScop] Error: memory overflow.\n");
 536       exit(1);
 537     }
 538
 539     // Copy the chain between the two tags.
 540     for (++start, i = 0; start != stop; ++start, ++i)
 541       res[i] = *start;
 542     res[i] = '\0';
 543   }
 544
 545   return res;
 546 }
 547
 548
 549 /**
 550  * openscop_util_safe_strcat function:
 551  * this function concatenates the string src to the string *dst
 552  * and reallocates *dst if necessary. The current size of the
 553  * *dst buffer must be *hwm (high water mark), if there is some
 554  * reallocation, this value is updated.
 555  * \param dst pointer to the destination string (may be reallocated).
 556  * \param src string to concatenate to dst.
 557  * \param hwm pointer to the size of the *dst buffer (may be updated).
 558  * TODO: This function is not that safe, improve it !
 559  */
 560 void openscop_util_safe_strcat(char ** dst, char * src, int * hwm) {
 561
 562   if (strlen(src) >= OPENSCOP_MAX_STRING) {
 563     fprintf(stderr, "[OpenScop] Error: string to concatenate is too long.\n");
 564     exit(1);
 565   }
 566
 567   if (strlen(*dst) + strlen(src) >= *hwm) {
 568     *hwm += OPENSCOP_MAX_STRING;
 569     *dst = (char *)realloc(*dst, *hwm * sizeof(char));
 570     if (*dst == NULL) {
 571       fprintf(stderr, "[OpenScop] Error: memory overflow.\n");
 572       exit(1);
 573     }
 574   }
 575
 576   strcat(*dst, src);
 577 }