1 #include <stdarg.h>
2 #include <stdio.h>
3 #include <ctype.h>
4 #include <string.h>
5 #include <stdint.h>
6 #include "kstring.h"
7
ksprintf(kstring_t * s,const char * fmt,...)8 int ksprintf(kstring_t *s, const char *fmt, ...)
9 {
10 va_list ap;
11 int l;
12 va_start(ap, fmt);
13 l = vsnprintf(s->s + s->l, s->m - s->l, fmt, ap); // This line does not work with glibc 2.0. See `man snprintf'.
14 va_end(ap);
15 if (l + 1 > s->m - s->l) {
16 s->m = s->l + l + 2;
17 kroundup32(s->m);
18 s->s = (char*)realloc(s->s, s->m);
19 va_start(ap, fmt);
20 l = vsnprintf(s->s + s->l, s->m - s->l, fmt, ap);
21 }
22 va_end(ap);
23 s->l += l;
24 return l;
25 }
26
kstrtok(const char * str,const char * sep,ks_tokaux_t * aux)27 char *kstrtok(const char *str, const char *sep, ks_tokaux_t *aux)
28 {
29 const char *p, *start;
30 if (sep) { // set up the table
31 if (str == 0 && (aux->tab[0]&1)) return 0; // no need to set up if we have finished
32 aux->tab[0] = aux->tab[1] = aux->tab[2] = aux->tab[3] = 0;
33 for (p = sep; *p; ++p)
34 aux->tab[*p/64] |= 1ull<<(*p%64);
35 }
36 if (str) aux->p = str - 1, aux->tab[0] &= ~1ull;
37 else if (aux->tab[0]&1) return 0;
38 for (p = start = aux->p + 1; *p; ++p)
39 if (aux->tab[*p/64]>>(*p%64)&1) break;
40 aux->p = p; // end of token
41 if (*p == 0) aux->tab[0] |= 1; // no more tokens
42 return (char*)start;
43 }
44
45 // s MUST BE a null terminated string; l = strlen(s)
ksplit_core(char * s,int delimiter,int * _max,int ** _offsets)46 int ksplit_core(char *s, int delimiter, int *_max, int **_offsets)
47 {
48 int i, n, max, last_char, last_start, *offsets, l;
49 n = 0; max = *_max; offsets = *_offsets;
50 l = strlen(s);
51
52 #define __ksplit_aux do { \
53 if (_offsets) { \
54 s[i] = 0; \
55 if (n == max) { \
56 max = max? max<<1 : 2; \
57 offsets = (int*)realloc(offsets, sizeof(int) * max); \
58 } \
59 offsets[n++] = last_start; \
60 } else ++n; \
61 } while (0)
62
63 for (i = 0, last_char = last_start = 0; i <= l; ++i) {
64 if (delimiter == 0) {
65 if (isspace(s[i]) || s[i] == 0) {
66 if (isgraph(last_char)) __ksplit_aux; // the end of a field
67 } else {
68 if (isspace(last_char) || last_char == 0) last_start = i;
69 }
70 } else {
71 if (s[i] == delimiter || s[i] == 0) {
72 if (last_char != 0 && last_char != delimiter) __ksplit_aux; // the end of a field
73 } else {
74 if (last_char == delimiter || last_char == 0) last_start = i;
75 }
76 }
77 last_char = s[i];
78 }
79 *_max = max; *_offsets = offsets;
80 return n;
81 }
82
83 /**********************
84 * Boyer-Moore search *
85 **********************/
86
87 typedef unsigned char ubyte_t;
88
89 // reference: http://www-igm.univ-mlv.fr/~lecroq/string/node14.html
ksBM_prep(const ubyte_t * pat,int m)90 static int *ksBM_prep(const ubyte_t *pat, int m)
91 {
92 int i, *suff, *prep, *bmGs, *bmBc;
93 prep = calloc(m + 256, sizeof(int));
94 bmGs = prep; bmBc = prep + m;
95 { // preBmBc()
96 for (i = 0; i < 256; ++i) bmBc[i] = m;
97 for (i = 0; i < m - 1; ++i) bmBc[pat[i]] = m - i - 1;
98 }
99 suff = calloc(m, sizeof(int));
100 { // suffixes()
101 int f = 0, g;
102 suff[m - 1] = m;
103 g = m - 1;
104 for (i = m - 2; i >= 0; --i) {
105 if (i > g && suff[i + m - 1 - f] < i - g)
106 suff[i] = suff[i + m - 1 - f];
107 else {
108 if (i < g) g = i;
109 f = i;
110 while (g >= 0 && pat[g] == pat[g + m - 1 - f]) --g;
111 suff[i] = f - g;
112 }
113 }
114 }
115 { // preBmGs()
116 int j = 0;
117 for (i = 0; i < m; ++i) bmGs[i] = m;
118 for (i = m - 1; i >= 0; --i)
119 if (suff[i] == i + 1)
120 for (; j < m - 1 - i; ++j)
121 if (bmGs[j] == m)
122 bmGs[j] = m - 1 - i;
123 for (i = 0; i <= m - 2; ++i)
124 bmGs[m - 1 - suff[i]] = m - 1 - i;
125 }
126 free(suff);
127 return prep;
128 }
129
kmemmem(const void * _str,int n,const void * _pat,int m,int ** _prep)130 void *kmemmem(const void *_str, int n, const void *_pat, int m, int **_prep)
131 {
132 int i, j, *prep = 0, *bmGs, *bmBc;
133 const ubyte_t *str, *pat;
134 str = (const ubyte_t*)_str; pat = (const ubyte_t*)_pat;
135 prep = (_prep == 0 || *_prep == 0)? ksBM_prep(pat, m) : *_prep;
136 if (_prep && *_prep == 0) *_prep = prep;
137 bmGs = prep; bmBc = prep + m;
138 j = 0;
139 while (j <= n - m) {
140 for (i = m - 1; i >= 0 && pat[i] == str[i+j]; --i);
141 if (i >= 0) {
142 int max = bmBc[str[i+j]] - m + 1 + i;
143 if (max < bmGs[i]) max = bmGs[i];
144 j += max;
145 } else return (void*)(str + j);
146 }
147 if (_prep == 0) free(prep);
148 return 0;
149 }
150
kstrstr(const char * str,const char * pat,int ** _prep)151 char *kstrstr(const char *str, const char *pat, int **_prep)
152 {
153 return (char*)kmemmem(str, strlen(str), pat, strlen(pat), _prep);
154 }
155
kstrnstr(const char * str,const char * pat,int n,int ** _prep)156 char *kstrnstr(const char *str, const char *pat, int n, int **_prep)
157 {
158 return (char*)kmemmem(str, n, pat, strlen(pat), _prep);
159 }
160
161 /***********************
162 * The main() function *
163 ***********************/
164
165 #ifdef KSTRING_MAIN
166 #include <stdio.h>
main()167 int main()
168 {
169 kstring_t *s;
170 int *fields, n, i;
171 ks_tokaux_t aux;
172 char *p;
173 s = (kstring_t*)calloc(1, sizeof(kstring_t));
174 // test ksprintf()
175 ksprintf(s, " abcdefg: %d ", 100);
176 printf("'%s'\n", s->s);
177 // test ksplit()
178 fields = ksplit(s, 0, &n);
179 for (i = 0; i < n; ++i)
180 printf("field[%d] = '%s'\n", i, s->s + fields[i]);
181 // test kstrtok()
182 s->l = 0;
183 for (p = kstrtok("ab:cde:fg/hij::k", ":/", &aux); p; p = kstrtok(0, 0, &aux)) {
184 kputsn(p, aux.p - p, s);
185 kputc('\n', s);
186 }
187 printf("%s", s->s);
188 // free
189 free(s->s); free(s); free(fields);
190
191 {
192 static char *str = "abcdefgcdgcagtcakcdcd";
193 static char *pat = "cd";
194 char *ret, *s = str;
195 int *prep = 0;
196 while ((ret = kstrstr(s, pat, &prep)) != 0) {
197 printf("match: %s\n", ret);
198 s = ret + prep[0];
199 }
200 free(prep);
201 }
202 return 0;
203 }
204 #endif
205