Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Stupid me. One day, I'll be able to compute array indices right
[simgrid.git] / 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     THROW2(arg_error,0,"Invalid values: i=%d, j=%d",i,j);
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 }