samtools/kstring.c.pysam.c

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