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