X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/49e717ce62a05692fc037261e131f78ba52adff2..0a8e6e02b1e79ff96a8d707fa432c5df71213882:/src/xbt/xbt_str.c diff --git a/src/xbt/xbt_str.c b/src/xbt/xbt_str.c index 5815b8b1f1..4c361b594f 100644 --- a/src/xbt/xbt_str.c +++ b/src/xbt/xbt_str.c @@ -18,12 +18,12 @@ * Strips the whitespaces from the end of s. * By default (when char_list=NULL), these characters get stripped: * - * - " " (ASCII 32 (0x20)) space. - * - "\t" (ASCII 9 (0x09)) tab. - * - "\n" (ASCII 10 (0x0A)) line feed. - * - "\r" (ASCII 13 (0x0D)) carriage return. - * - "\0" (ASCII 0 (0x00)) NULL. - * - "\x0B" (ASCII 11 (0x0B)) vertical tab. + * - " " (ASCII 32 (0x20)) space. + * - "\t" (ASCII 9 (0x09)) tab. + * - "\n" (ASCII 10 (0x0A)) line feed. + * - "\r" (ASCII 13 (0x0D)) carriage return. + * - "\0" (ASCII 0 (0x00)) NULL. + * - "\x0B" (ASCII 11 (0x0B)) vertical tab. * * @param s The string to strip. Modified in place. * @param char_list A string which contains the characters you want to strip. @@ -62,12 +62,12 @@ void xbt_str_rtrim(char *s, const char *char_list) * Strips the whitespaces from the begining of s. * By default (when char_list=NULL), these characters get stripped: * - * - " " (ASCII 32 (0x20)) space. - * - "\t" (ASCII 9 (0x09)) tab. - * - "\n" (ASCII 10 (0x0A)) line feed. - * - "\r" (ASCII 13 (0x0D)) carriage return. - * - "\0" (ASCII 0 (0x00)) NULL. - * - "\x0B" (ASCII 11 (0x0B)) vertical tab. + * - " " (ASCII 32 (0x20)) space. + * - "\t" (ASCII 9 (0x09)) tab. + * - "\n" (ASCII 10 (0x0A)) line feed. + * - "\r" (ASCII 13 (0x0D)) carriage return. + * - "\0" (ASCII 0 (0x00)) NULL. + * - "\x0B" (ASCII 11 (0x0B)) vertical tab. * * @param s The string to strip. Modified in place. * @param char_list A string which contains the characters you want to strip. @@ -103,12 +103,12 @@ void xbt_str_ltrim(char *s, const char *char_list) * Strips the whitespaces from both the beginning and the end of s. * By default (when char_list=NULL), these characters get stripped: * - * - " " (ASCII 32 (0x20)) space. - * - "\t" (ASCII 9 (0x09)) tab. - * - "\n" (ASCII 10 (0x0A)) line feed. - * - "\r" (ASCII 13 (0x0D)) carriage return. - * - "\0" (ASCII 0 (0x00)) NULL. - * - "\x0B" (ASCII 11 (0x0B)) vertical tab. + * - " " (ASCII 32 (0x20)) space. + * - "\t" (ASCII 9 (0x09)) tab. + * - "\n" (ASCII 10 (0x0A)) line feed. + * - "\r" (ASCII 13 (0x0D)) carriage return. + * - "\0" (ASCII 0 (0x00)) NULL. + * - "\x0B" (ASCII 11 (0x0B)) vertical tab. * * @param s The string to strip. * @param char_list A string which contains the characters you want to strip. @@ -223,12 +223,12 @@ char *xbt_str_varsubst(const char *str, xbt_dict_t patterns) * * By default (with sep=NULL), these characters are used as separator: * - * - " " (ASCII 32 (0x20)) space. - * - "\t" (ASCII 9 (0x09)) tab. - * - "\n" (ASCII 10 (0x0A)) line feed. - * - "\r" (ASCII 13 (0x0D)) carriage return. - * - "\0" (ASCII 0 (0x00)) NULL. - * - "\x0B" (ASCII 11 (0x0B)) vertical tab. + * - " " (ASCII 32 (0x20)) space. + * - "\t" (ASCII 9 (0x09)) tab. + * - "\n" (ASCII 10 (0x0A)) line feed. + * - "\r" (ASCII 13 (0x0D)) carriage return. + * - "\0" (ASCII 0 (0x00)) NULL. + * - "\x0B" (ASCII 11 (0x0B)) vertical tab. */ xbt_dynar_t xbt_str_split(const char *s, const char *sep) @@ -305,14 +305,14 @@ xbt_dynar_t xbt_str_split_str(const char *s, const char *sep) //if substring was not found add the entire string if (NULL == q) { v = strlen(p); - to_push = malloc(v + 1); + to_push = xbt_malloc(v + 1); memcpy(to_push, p, v); to_push[v] = '\0'; xbt_dynar_push(res, &to_push); done = 1; } else { //get the appearance - to_push = malloc(q - p + 1); + to_push = xbt_malloc(q - p + 1); memcpy(to_push, p, q - p); //add string terminator to_push[q - p] = '\0'; @@ -327,11 +327,14 @@ xbt_dynar_t xbt_str_split_str(const char *s, const char *sep) * * The string passed as argument must be writable (not const) * The elements of the dynar are just parts of the string passed as argument. + * So if you don't store that argument elsewhere, you should free it in addition + * to freeing the dynar. This can be done by simply freeing the first argument + * of the dynar: + * free(xbt_dynar_get_ptr(dynar,0)); * - * To free the structure constructed by this function, free the first element and free the dynar: - * - * free(xbt_dynar_get_ptr(dynar,0)); - * xbt_dynar_free(&dynar); + * Actually this function puts a bunch of \0 in the memory area you passed as + * argument to separate the elements, and pushes the address of each chunk + * in the resulting dynar. Yes, that's uneven. Yes, that's gory. But that's efficient. */ xbt_dynar_t xbt_str_split_quoted_in_place(char *s) { xbt_dynar_t res = xbt_dynar_new(sizeof(char *), NULL); @@ -345,7 +348,7 @@ xbt_dynar_t xbt_str_split_quoted_in_place(char *s) { beg = s; - /* do not trim leading spaces: caller responsability to clean his cruft */ + /* do not trim leading spaces: caller responsibility to clean his cruft */ end = beg; while (!done) { @@ -574,9 +577,11 @@ long getline(char **buf, size_t * n, FILE * stream) /* * Diff related functions * - * Implementation of the algorithm described in "An O(NP) Sequence - * Comparison Algorithm", by Sun Wu, Udi Manber, Gene Myers, and Webb - * Miller. + * Implementation of the algorithm described in "An O(NP) Sequence Comparison + * Algorithm", by Sun Wu, Udi Manber, Gene Myers, and Webb Miller (Information + * Processing Letters 35(6):317-323, 1990), with the linear-space + * divide-and-conquer strategy described in "An O(ND) Difference Algorithm and + * Its Variations", by Eugene W. Myers (Algorithmica 1:251-266, 1986). */ struct subsequence { @@ -655,25 +660,34 @@ static int diff_middle_subsequence(const char *vec_a[], int a0, int len_a, } /* Finds a longest common subsequence. + * Returns its length. */ -static void diff_compute_lcs(const char *vec_a[], int a0, int len_a, - const char *vec_b[], int b0, int len_b, - xbt_dynar_t common_sequence, - struct subsequence *seqs, int *fp) +static int diff_compute_lcs(const char *vec_a[], int a0, int len_a, + const char *vec_b[], int b0, int len_b, + xbt_dynar_t common_sequence, + struct subsequence *seqs, int *fp) { if (len_a > 0 && len_b > 0) { struct subsequence subseq; int ses_len = diff_middle_subsequence(vec_a, a0, len_a, vec_b, b0, len_b, &subseq, seqs, fp); - if (ses_len > 1) { - int u = subseq.x + subseq.len; - int v = subseq.y + subseq.len; - diff_compute_lcs(vec_a, a0, subseq.x - a0, vec_b, b0, subseq.y - b0, - common_sequence, seqs, fp); + int lcs_len = (len_a + len_b - ses_len) / 2; + if (lcs_len == 0) { + return 0; + } else if (ses_len > 1) { + int lcs_len1 = subseq.len; + if (lcs_len1 < lcs_len) + lcs_len1 += diff_compute_lcs(vec_a, a0, subseq.x - a0, + vec_b, b0, subseq.y - b0, + common_sequence, seqs, fp); if (subseq.len > 0) xbt_dynar_push(common_sequence, &subseq); - diff_compute_lcs(vec_a, u, a0 + len_a - u, vec_b, v, b0 + len_b - v, - common_sequence, seqs, fp); + if (lcs_len1 < lcs_len) { + int u = subseq.x + subseq.len; + int v = subseq.y + subseq.len; + diff_compute_lcs(vec_a, u, a0 + len_a - u, vec_b, v, b0 + len_b - v, + common_sequence, seqs, fp); + } } else { int len = MIN(len_a, len_b) - subseq.len; if (subseq.x == a0 && subseq.y == b0) { @@ -693,6 +707,9 @@ static void diff_compute_lcs(const char *vec_a[], int a0, int len_a, xbt_dynar_push(common_sequence, &subseq); } } + return lcs_len; + } else { + return 0; } } @@ -889,6 +906,28 @@ char *xbt_str_from_file(FILE * file) return res; } +/* @brief Retrun 1 if string 'str' starts with string 'start' + * + * \param str a string + * \param start the string to search in str + * + * \return 1 if 'str' starts with 'start' + */ +int xbt_str_start_with(const char* str, const char* start) +{ + int i; + size_t l_str = strlen(str); + size_t l_start = strlen(start); + + if(l_start > l_str) return 0; + + for(i = 0; i< l_start; i++){ + if(str[i] != start[i]) return 0; + } + + return 1; +} + #ifdef SIMGRID_TEST #include "xbt/str.h"