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(char *s, const char *sep) {
 200   char *str=xbt_strdup(s);
 201   xbt_dynar_t res = xbt_dynar_new(sizeof(char*), free_string);
 202   char *p, *q;
 203   int done;
 204   const char* sep_dflt = " \t\n\r\x0B";
 205   char is_sep[256] = {1,0};
 206
 207   /* check what are the separators */
 208   memset(is_sep,0,sizeof(is_sep));
 209   if (!sep) {
 210     while (*sep_dflt)
 211       is_sep[(unsigned char) *sep_dflt++] = 1;
 212   } else {
 213     while (*sep)
 214       is_sep[(unsigned char) *sep++] = 1;
 215   }
 216   is_sep[0] = 1; /* End of string is also separator */
 217
 218   /* Do the job */
 219   p=q=str;
 220   done=0;
 221   while (!done) {
 222     char *topush;
 223     while (!is_sep[(unsigned char)*q]) {
 224       q++;
 225     }
 226     if (*q == '\0') {
 227 #ifdef UNDEF
 228       if (p==q) {
 229         /* do not push last empty line */
 230         free(str);
 231         return res;
 232       }
 233 #endif
 234       done = 1;
 235     } else {
 236       *q='\0';
 237     }
 238     topush=xbt_strdup(p);
 239     xbt_dynar_push(res,&topush);
 240     p = ++q;
 241   }
 242   free (str);
 243   return res;
 244 }
 245
 246 /** @brief Join a set of strings as a single string */
 247
 248 char *xbt_str_join(xbt_dynar_t dyn, const char*sep) {
 249   int len=2;
 250   int cpt;
 251   char *cursor;
 252   char *res,*p;
 253   /* compute the length */
 254   xbt_dynar_foreach(dyn,cpt,cursor) {
 255     len+=strlen(cursor);
 256   }
 257   len+=strlen(sep)*(xbt_dynar_length(dyn)-1);
 258   /* Do the job */
 259   res = xbt_malloc(len);
 260   p=res;
 261   xbt_dynar_foreach(dyn,cpt,cursor) {
 262     p+=sprintf(p,"%s%s",cursor,sep);
 263   }
 264   return res;
 265 }
 266
 267 #ifndef HAVE_GETLINE
 268 long getline(char **buf, size_t *n, FILE *stream) {
 269
 270    int i, ch;
 271
 272    if (!*buf) {
 273      *buf = xbt_malloc(512);
 274      *n = 512;
 275    }
 276
 277    if (feof(stream))
 278      return (ssize_t)-1;
 279
 280    for (i=0; (ch = fgetc(stream)) != EOF; i++)  {
 281
 282       if (i >= (*n) + 1)
 283         *buf = xbt_realloc(*buf, *n += 512);
 284
 285       (*buf)[i] = ch;
 286
 287       if ((*buf)[i] == '\n')  {
 288          i++;
 289          (*buf)[i] = '\0';
 290          break;
 291       }
 292    }
 293
 294    if (i == *n)
 295      *buf = xbt_realloc(*buf, *n += 1);
 296
 297    (*buf)[i] = '\0';
 298
 299    return (ssize_t)i;
 300 }
 301
 302 #endif /* HAVE_GETLINE */
 303
 304 /*
 305  * Diff related functions
 306  */
 307 static xbt_matrix_t diff_build_LCS(xbt_dynar_t da, xbt_dynar_t db) {
 308   xbt_matrix_t C = xbt_matrix_new(xbt_dynar_length(da),xbt_dynar_length(db),
 309                                   sizeof(int),NULL);
 310   int i,j;
 311   /* Compute the LCS */
 312   /*
 313     C = array(0..m, 0..n)
 314     for i := 0..m
 315        C[i,0] = 0
 316     for j := 1..n
 317        C[0,j] = 0
 318     for i := 1..m
 319         for j := 1..n
 320             if X[i] = Y[j]
 321                 C[i,j] := C[i-1,j-1] + 1
 322             else:
 323                 C[i,j] := max(C[i,j-1], C[i-1,j])
 324     return C[m,n]
 325           */
 326   for (i=0; i<xbt_dynar_length(da); i++)
 327     *((int*) xbt_matrix_get_ptr(C,i,0) ) = 0;
 328
 329   for (j=0; j<xbt_dynar_length(db); j++)
 330     *((int*) xbt_matrix_get_ptr(C,0,j) ) = 0;
 331
 332   for (i=1; i<xbt_dynar_length(da); i++)
 333     for (j=1; j<xbt_dynar_length(db); j++) {
 334
 335       if (!strcmp(xbt_dynar_get_as(da,i,char*), xbt_dynar_get_as(db,j,char*)))
 336         *((int*) xbt_matrix_get_ptr(C,i,j) ) = xbt_matrix_get_as(C,i-1,j-1,int) + 1;
 337       else
 338         *((int*) xbt_matrix_get_ptr(C,i,j) ) = max(xbt_matrix_get_as(C,i  ,j-1,int),
 339                                                    xbt_matrix_get_as(C,i-1,j,int));
 340     }
 341   return C;
 342 }
 343
 344 static void diff_build_diff(xbt_dynar_t res,
 345                             xbt_matrix_t C,
 346                             xbt_dynar_t da, xbt_dynar_t db,
 347                             int i,int j) {
 348   char *topush;
 349   /* Construct the diff
 350   function printDiff(C[0..m,0..n], X[1..m], Y[1..n], i, j)
 351     if i > 0 and j > 0 and X[i] = Y[j]
 352         printDiff(C, X, Y, i-1, j-1)
 353         print "  " + X[i]
 354     else
 355         if j > 0 and (i = 0 or C[i,j-1] >= C[i-1,j])
 356             printDiff(C, X, Y, i, j-1)
 357             print "+ " + Y[j]
 358         else if i > 0 and (j = 0 or C[i,j-1] < C[i-1,j])
 359             printDiff(C, X, Y, i-1, j)
 360             print "- " + X[i]
 361   */
 362
 363   if (i>=0 && j >= 0 && !strcmp(xbt_dynar_get_as(da,i,char*),
 364                                 xbt_dynar_get_as(db,j,char*))) {
 365     diff_build_diff(res,C,da,db,i-1,j-1);
 366     topush = bprintf("  %s",xbt_dynar_get_as(da,i,char*));
 367     xbt_dynar_push(res, &topush);
 368   } else if (j>0 &&
 369              (i<=0 || xbt_matrix_get_as(C,i,j-1,int) >= xbt_matrix_get_as(C,i-1,j,int))) {
 370     diff_build_diff(res,C,da,db,i,j-1);
 371     topush = bprintf("+ %s",xbt_dynar_get_as(db,j,char*));
 372     xbt_dynar_push(res,&topush);
 373   } else if (i>0 &&
 374              (j<=0 || xbt_matrix_get_as(C,i,j-1,int) < xbt_matrix_get_as(C,i-1,j,int))) {
 375     diff_build_diff(res,C,da,db,i-1,j);
 376     topush = bprintf("- %s",xbt_dynar_get_as(da,i,char*));
 377     xbt_dynar_push(res,&topush);
 378   } else if (i<=0 && j<=0) {
 379     return;
 380   } else {
 381     THROW2(arg_error,0,"Invalid values: i=%d, j=%d",i,j);
 382   }
 383 }
 384
 385 /** @brief Compute the unified diff of two strings */
 386 char *xbt_str_diff(char *a, char *b) {
 387   xbt_dynar_t da = xbt_str_split(a, "\n");
 388   xbt_dynar_t db = xbt_str_split(b, "\n");
 389
 390   xbt_matrix_t C = diff_build_LCS(da,db);
 391   xbt_dynar_t diff = xbt_dynar_new(sizeof(char*),free_string);
 392   char *res=NULL;
 393
 394   diff_build_diff(diff, C, da,db, xbt_dynar_length(da)-1, xbt_dynar_length(db)-1);
 395   res = xbt_str_join(diff, "\n");
 396
 397   xbt_dynar_free(&da);
 398   xbt_dynar_free(&db);
 399   xbt_dynar_free(&diff);
 400   xbt_matrix_free(C);
 401
 402   return res;
 403 }