10 int ksprintf(kstring_t *s, const char *fmt, ...)
15 l = vsnprintf(s->s + s->l, s->m - s->l, fmt, ap); // This line does not work with glibc 2.0. See `man snprintf'.
17 if (l + 1 > s->m - s->l) {
20 s->s = (char*)realloc(s->s, s->m);
22 l = vsnprintf(s->s + s->l, s->m - s->l, fmt, ap);
29 // s MUST BE a null terminated string; l = strlen(s)
30 int ksplit_core(char *s, int delimiter, int *_max, int **_offsets)
32 int i, n, max, last_char, last_start, *offsets, l;
33 n = 0; max = *_max; offsets = *_offsets;
36 #define __ksplit_aux do { \
40 max = max? max<<1 : 2; \
41 offsets = (int*)realloc(offsets, sizeof(int) * max); \
43 offsets[n++] = last_start; \
47 for (i = 0, last_char = last_start = 0; i <= l; ++i) {
49 if (isspace(s[i]) || s[i] == 0) {
50 if (isgraph(last_char)) __ksplit_aux; // the end of a field
52 if (isspace(last_char) || last_char == 0) last_start = i;
55 if (s[i] == delimiter || s[i] == 0) {
56 if (last_char != 0 && last_char != delimiter) __ksplit_aux; // the end of a field
58 if (last_char == delimiter || last_char == 0) last_start = i;
63 *_max = max; *_offsets = offsets;
67 /**********************
68 * Boyer-Moore search *
69 **********************/
71 // reference: http://www-igm.univ-mlv.fr/~lecroq/string/node14.html
72 int *ksBM_prep(const uint8_t *pat, int m)
74 int i, *suff, *prep, *bmGs, *bmBc;
75 prep = calloc(m + 256, 1);
76 bmGs = prep; bmBc = prep + m;
78 for (i = 0; i < 256; ++i) bmBc[i] = m;
79 for (i = 0; i < m - 1; ++i) bmBc[pat[i]] = m - i - 1;
81 suff = calloc(m, sizeof(int));
86 for (i = m - 2; i >= 0; --i) {
87 if (i > g && suff[i + m - 1 - f] < i - g)
88 suff[i] = suff[i + m - 1 - f];
92 while (g >= 0 && pat[g] == pat[g + m - 1 - f]) --g;
99 for (i = 0; i < m; ++i) bmGs[i] = m;
100 for (i = m - 1; i >= 0; --i)
101 if (suff[i] == i + 1)
102 for (; j < m - 1 - i; ++j)
105 for (i = 0; i <= m - 2; ++i)
106 bmGs[m - 1 - suff[i]] = m - 1 - i;
112 int *ksBM_search(const uint8_t *str, int n, const uint8_t *pat, int m, int *_prep, int *n_matches)
114 int i, j, *prep, *bmGs, *bmBc;
115 int *matches = 0, mm = 0, nm = 0;
116 prep = _prep? _prep : ksBM_prep(pat, m);
117 bmGs = prep; bmBc = prep + m;
120 for (i = m - 1; i >= 0 && pat[i] == str[i+j]; --i);
124 matches = realloc(matches, mm * sizeof(int));
129 int max = bmBc[str[i+j]] - m + 1 + i;
130 if (max < bmGs[i]) max = bmGs[i];
135 if (_prep == 0) free(prep);
145 s = (kstring_t*)calloc(1, sizeof(kstring_t));
147 ksprintf(s, " abcdefg: %d ", 100);
148 printf("'%s'\n", s->s);
150 fields = ksplit(s, 0, &n);
151 for (i = 0; i < n; ++i)
152 printf("field[%d] = '%s'\n", i, s->s + fields[i]);
156 static char *str = "abcdefgcdg";
157 static char *pat = "cd";
159 matches = ksBM_search(str, strlen(str), pat, strlen(pat), 0, &n);
161 for (i = 0; i < n; ++i)
162 printf("- %d\n", matches[i]);