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