src/xbt/xbt_str.c

   1
   2 /* xbt_str.c - various helping functions to deal with strings               */
   3
   4 /* Copyright (C) 2005-2007 Malek Cherier, Martin Quinson.                   */
   5 /* All rights reserved.                                                     */
   6
   7 /* This program is free software; you can redistribute it and/or modify it
   8  * under the terms of the license (GNU LGPL) which comes with this package.
   9  */
  10
  11 /* Returns the string without leading whitespaces (xbt_str_ltrim),
  12  * trailing whitespaces (xbt_str_rtrim),
  13  * or both leading and trailing whitespaces (xbt_str_trim).
  14  * (in-place modification of the string)
  15  */
  16
  17 #include "xbt/misc.h"
  18 #include "xbt/sysdep.h"
  19 #include "xbt/str.h" /* headers of these functions */
  20 #include "portable.h"
  21 #include "xbt/matrix.h" /* for the diff */
  22
  23 static void free_string(void *d){
  24   free(*(void**)d);
  25 }
  26
  27 /**  @brief Strip whitespace (or other characters) from the end of a string.
  28  *
  29  * Strips the whitespaces from the end of s.
  30  * By default (when char_list=NULL), these characters get stripped:
  31  *
  32  *      - " "           (ASCII 32       (0x20)) space.
  33  *      - "\t"          (ASCII 9        (0x09)) tab.
  34  *      - "\n"          (ASCII 10       (0x0A)) line feed.
  35  *      - "\r"          (ASCII 13       (0x0D)) carriage return.
  36  *      - "\0"          (ASCII 0        (0x00)) NULL.
  37  *      - "\x0B"        (ASCII 11       (0x0B)) vertical tab.
  38  *
  39  * @param s The string to strip. Modified in place.
  40  * @param char_list A string which contains the characters you want to strip.
  41  *
  42  */
  43 void
  44 xbt_str_rtrim(char* s, const char* char_list)
  45 {
  46         char* cur = s;
  47         const char* __char_list = " \t\n\r\x0B";
  48         char white_char[256] = {1,0};
  49
  50         if(!s)
  51                 return;
  52
  53         if(!char_list){
  54                 while(*__char_list) {
  55                         white_char[(unsigned char)*__char_list++] = 1;
  56                 }
  57         }else{
  58                 while(*char_list) {
  59                         white_char[(unsigned char)*char_list++] = 1;
  60                 }
  61         }
  62
  63         while(*cur)
  64                 ++cur;
  65
  66         while((cur >= s) && white_char[(unsigned char)*cur])
  67                 --cur;
  68
  69         *++cur = '\0';
  70 }
  71
  72 /**  @brief Strip whitespace (or other characters) from the beginning of a string.
  73  *
  74  * Strips the whitespaces from the begining of s.
  75  * By default (when char_list=NULL), these characters get stripped:
  76  *
  77  *      - " "           (ASCII 32       (0x20)) space.
  78  *      - "\t"          (ASCII 9        (0x09)) tab.
  79  *      - "\n"          (ASCII 10       (0x0A)) line feed.
  80  *      - "\r"          (ASCII 13       (0x0D)) carriage return.
  81  *      - "\0"          (ASCII 0        (0x00)) NULL.
  82  *      - "\x0B"        (ASCII 11       (0x0B)) vertical tab.
  83  *
  84  * @param s The string to strip. Modified in place.
  85  * @param char_list A string which contains the characters you want to strip.
  86  *
  87  */
  88 void
  89 xbt_str_ltrim( char* s, const char* char_list)
  90 {
  91         char* cur = s;
  92         const char* __char_list = " \t\n\r\x0B";
  93         char white_char[256] = {1,0};
  94
  95         if(!s)
  96                 return;
  97
  98         if(!char_list){
  99                 while(*__char_list) {
 100                         white_char[(unsigned char)*__char_list++] = 1;
 101                 }
 102         }else{
 103                 while(*char_list) {
 104                         white_char[(unsigned char)*char_list++] = 1;
 105                 }
 106         }
 107
 108         while(*cur && white_char[(unsigned char)*cur])
 109                 ++cur;
 110
 111         memmove(s,cur, strlen(cur));
 112 }
 113
 114 /**  @brief Strip whitespace (or other characters) from the end and the begining of a string.
 115  *
 116  * Strips the whitespaces from both the beginning and the end of s.
 117  * By default (when char_list=NULL), these characters get stripped:
 118  *
 119  *      - " "           (ASCII 32       (0x20)) space.
 120  *      - "\t"          (ASCII 9        (0x09)) tab.
 121  *      - "\n"          (ASCII 10       (0x0A)) line feed.
 122  *      - "\r"          (ASCII 13       (0x0D)) carriage return.
 123  *      - "\0"          (ASCII 0        (0x00)) NULL.
 124  *      - "\x0B"        (ASCII 11       (0x0B)) vertical tab.
 125  *
 126  * @param s The string to strip.
 127  * @param char_list A string which contains the characters you want to strip.
 128  *
 129  */
 130 void
 131 xbt_str_trim(char* s, const char* char_list ){
 132
 133         if(!s)
 134                 return;
 135
 136     xbt_str_rtrim(s,char_list);
 137     xbt_str_ltrim(s,char_list);
 138 }
 139
 140 /**  @brief Replace double whitespaces (but no other characters) from the string.
 141  *
 142  * The function modifies the string so that each time that several spaces appear,
 143  * they are replaced by a single space. It will only do so for spaces (ASCII 32, 0x20).
 144  *
 145  * @param s The string to strip. Modified in place.
 146  *
 147  */
 148 void
 149 xbt_str_strip_spaces(char *s) {
 150   char *p = s;
 151   int   e = 0;
 152
 153   if (!s)
 154     return;
 155
 156   while (1) {
 157     if (!*p)
 158       goto end;
 159
 160     if (*p != ' ')
 161       break;
 162
 163     p++;
 164   }
 165
 166   e = 1;
 167
 168   do {
 169     if (e)
 170       *s++ = *p;
 171
 172     if (!*++p)
 173       goto end;
 174
 175     if (e ^ (*p!=' '))
 176       if ((e = !e))
 177         *s++ = ' ';
 178   } while (1);
 179
 180  end:
 181   *s = '\0';
 182 }
 183
 184 /** @brief Splits a string into a dynar of strings
 185  *
 186  * @param s: the string to split
 187  * @param sep: a string of all chars to consider as separator.
 188  *
 189  * By default (with sep=NULL), these characters are used as separator:
 190  *
 191  *      - " "           (ASCII 32       (0x20)) space.
 192  *      - "\t"          (ASCII 9        (0x09)) tab.
 193  *      - "\n"          (ASCII 10       (0x0A)) line feed.
 194  *      - "\r"          (ASCII 13       (0x0D)) carriage return.
 195  *      - "\0"          (ASCII 0        (0x00)) NULL.
 196  *      - "\x0B"        (ASCII 11       (0x0B)) vertical tab.
 197  */
 198
 199 xbt_dynar_t xbt_str_split(const char *s, const char *sep) {
 200   xbt_dynar_t res = xbt_dynar_new(sizeof(char*), free_string);
 201   const char *p, *q;
 202   int done;
 203   const char* sep_dflt = " \t\n\r\x0B";
 204   char is_sep[256] = {1,0};
 205
 206   /* check what are the separators */
 207   memset(is_sep,0,sizeof(is_sep));
 208   if (!sep) {
 209     while (*sep_dflt)
 210       is_sep[(unsigned char) *sep_dflt++] = 1;
 211   } else {
 212     while (*sep)
 213       is_sep[(unsigned char) *sep++] = 1;
 214   }
 215   is_sep[0] = 1; /* End of string is also separator */
 216
 217   /* Do the job */
 218   p=q=s;
 219   done=0;
 220
 221   if (s[0] == '\0')
 222     return res;
 223
 224   while (!done) {
 225     char *topush;
 226     while (!is_sep[(unsigned char)*q]) {
 227       q++;
 228     }
 229     if (*q == '\0')
 230       done = 1;
 231
 232     topush=xbt_malloc(q-p+1);
 233     memcpy(topush,p,q-p);
 234     topush[q - p] = '\0';
 235     xbt_dynar_push(res,&topush);
 236     p = ++q;
 237   }
 238
 239   return res;
 240 }
 241
 242 /** @brief Join a set of strings as a single string */
 243
 244 char *xbt_str_join(xbt_dynar_t dyn, const char*sep) {
 245   int len=2;
 246   int cpt;
 247   char *cursor;
 248   char *res,*p;
 249   /* compute the length */
 250   xbt_dynar_foreach(dyn,cpt,cursor) {
 251     len+=strlen(cursor);
 252   }
 253   len+=strlen(sep)*(xbt_dynar_length(dyn)-1);
 254   /* Do the job */
 255   res = xbt_malloc(len);
 256   p=res;
 257   xbt_dynar_foreach(dyn,cpt,cursor) {
 258     p+=sprintf(p,"%s%s",cursor,sep);
 259   }
 260   return res;
 261 }
 262
 263 #ifndef HAVE_GETLINE
 264 long getline(char **buf, size_t *n, FILE *stream) {
 265
 266    int i, ch;
 267
 268    if (!*buf) {
 269      *buf = xbt_malloc(512);
 270      *n = 512;
 271    }
 272
 273    if (feof(stream))
 274      return (ssize_t)-1;
 275
 276    for (i=0; (ch = fgetc(stream)) != EOF; i++)  {
 277
 278       if (i >= (*n) + 1)
 279         *buf = xbt_realloc(*buf, *n += 512);
 280
 281       (*buf)[i] = ch;
 282
 283       if ((*buf)[i] == '\n')  {
 284          i++;
 285          (*buf)[i] = '\0';
 286          break;
 287       }
 288    }
 289
 290    if (i == *n)
 291      *buf = xbt_realloc(*buf, *n += 1);
 292
 293    (*buf)[i] = '\0';
 294
 295    return (ssize_t)i;
 296 }
 297
 298 #endif /* HAVE_GETLINE */
 299
 300 /*
 301  * Diff related functions
 302  */
 303 static xbt_matrix_t diff_build_LCS(xbt_dynar_t da, xbt_dynar_t db) {
 304   xbt_matrix_t C = xbt_matrix_new(xbt_dynar_length(da),xbt_dynar_length(db),
 305                                   sizeof(int),NULL);
 306   int i,j;
 307   /* Compute the LCS */
 308   /*
 309     C = array(0..m, 0..n)
 310     for i := 0..m
 311        C[i,0] = 0
 312     for j := 1..n
 313        C[0,j] = 0
 314     for i := 1..m
 315         for j := 1..n
 316             if X[i] = Y[j]
 317                 C[i,j] := C[i-1,j-1] + 1
 318             else:
 319                 C[i,j] := max(C[i,j-1], C[i-1,j])
 320     return C[m,n]
 321           */
 322   for (i=0; i<xbt_dynar_length(da); i++)
 323     *((int*) xbt_matrix_get_ptr(C,i,0) ) = 0;
 324
 325   for (j=0; j<xbt_dynar_length(db); j++)
 326     *((int*) xbt_matrix_get_ptr(C,0,j) ) = 0;
 327
 328   for (i=1; i<xbt_dynar_length(da); i++)
 329     for (j=1; j<xbt_dynar_length(db); j++) {
 330
 331       if (!strcmp(xbt_dynar_get_as(da,i,char*), xbt_dynar_get_as(db,j,char*)))
 332         *((int*) xbt_matrix_get_ptr(C,i,j) ) = xbt_matrix_get_as(C,i-1,j-1,int) + 1;
 333       else
 334         *((int*) xbt_matrix_get_ptr(C,i,j) ) = max(xbt_matrix_get_as(C,i  ,j-1,int),
 335                                                    xbt_matrix_get_as(C,i-1,j,int));
 336     }
 337   return C;
 338 }
 339
 340 static void diff_build_diff(xbt_dynar_t res,
 341                             xbt_matrix_t C,
 342                             xbt_dynar_t da, xbt_dynar_t db,
 343                             int i,int j) {
 344   char *topush;
 345   /* Construct the diff
 346   function printDiff(C[0..m,0..n], X[1..m], Y[1..n], i, j)
 347     if i > 0 and j > 0 and X[i] = Y[j]
 348         printDiff(C, X, Y, i-1, j-1)
 349         print "  " + X[i]
 350     else
 351         if j > 0 and (i = 0 or C[i,j-1] >= C[i-1,j])
 352             printDiff(C, X, Y, i, j-1)
 353             print "+ " + Y[j]
 354         else if i > 0 and (j = 0 or C[i,j-1] < C[i-1,j])
 355             printDiff(C, X, Y, i-1, j)
 356             print "- " + X[i]
 357   */
 358
 359   if (i>=0 && j >= 0 && !strcmp(xbt_dynar_get_as(da,i,char*),
 360                                 xbt_dynar_get_as(db,j,char*))) {
 361     diff_build_diff(res,C,da,db,i-1,j-1);
 362     topush = bprintf("  %s",xbt_dynar_get_as(da,i,char*));
 363     xbt_dynar_push(res, &topush);
 364   } else if (j>=0 &&
 365              (i<=0 || xbt_matrix_get_as(C,i,j-1,int) >= xbt_matrix_get_as(C,i-1,j,int))) {
 366     diff_build_diff(res,C,da,db,i,j-1);
 367     topush = bprintf("+ %s",xbt_dynar_get_as(db,j,char*));
 368     xbt_dynar_push(res,&topush);
 369   } else if (i>=0 &&
 370              (j<=0 || xbt_matrix_get_as(C,i,j-1,int) < xbt_matrix_get_as(C,i-1,j,int))) {
 371     diff_build_diff(res,C,da,db,i-1,j);
 372     topush = bprintf("- %s",xbt_dynar_get_as(da,i,char*));
 373     xbt_dynar_push(res,&topush);
 374   } else if (i<=0 && j<=0) {
 375     return;
 376   } else {
 377     THROW2(arg_error,0,"Invalid values: i=%d, j=%d",i,j);
 378   }
 379
 380 }
 381
 382 /** @brief Compute the unified diff of two strings */
 383 char *xbt_str_diff(char *a, char *b) {
 384   xbt_dynar_t da = xbt_str_split(a, "\n");
 385   xbt_dynar_t db = xbt_str_split(b, "\n");
 386
 387   xbt_matrix_t C = diff_build_LCS(da,db);
 388   xbt_dynar_t diff = xbt_dynar_new(sizeof(char*),free_string);
 389   char *res=NULL;
 390
 391   diff_build_diff(diff, C, da,db, xbt_dynar_length(da)-1, xbt_dynar_length(db)-1);
 392   /* Clean empty lines at the end */
 393   while (xbt_dynar_length(diff) > 0) {
 394      char *str;
 395      xbt_dynar_pop(diff,&str);
 396      if (str[0]=='\0' || !strcmp(str,"  ")) {
 397         free(str);
 398      } else {
 399         xbt_dynar_push(diff,&str);
 400         break;
 401      }
 402   }
 403   res = xbt_str_join(diff, "\n");
 404
 405   xbt_dynar_free(&da);
 406   xbt_dynar_free(&db);
 407   xbt_dynar_free(&diff);
 408   xbt_matrix_free(C);
 409
 410   return res;
 411 }