Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Allow to split const strings, and avoid a strdup in the process
[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  * 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 /** @brief Compute the unified diff of two strings */
382 char *xbt_str_diff(char *a, char *b) {
383   xbt_dynar_t da = xbt_str_split(a, "\n");
384   xbt_dynar_t db = xbt_str_split(b, "\n");
385
386   xbt_matrix_t C = diff_build_LCS(da,db);
387   xbt_dynar_t diff = xbt_dynar_new(sizeof(char*),free_string);
388   char *res=NULL;
389   
390   diff_build_diff(diff, C, da,db, xbt_dynar_length(da)-1, xbt_dynar_length(db)-1);
391   res = xbt_str_join(diff, "\n");
392
393   xbt_dynar_free(&da);
394   xbt_dynar_free(&db);
395   xbt_dynar_free(&diff);
396   xbt_matrix_free(C);
397   
398   return res;
399 }