tabix/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 // s MUST BE a null terminated string; l = strlen(s)
  30 int ksplit_core(char *s, int delimiter, int *_max, int **_offsets)
  31 {
  32         int i, n, max, last_char, last_start, *offsets, l;
  33         n = 0; max = *_max; offsets = *_offsets;
  34         l = strlen(s);
  35
  36 #define __ksplit_aux do {                                                                                               \
  37                 if (_offsets) {                                                                                                 \
  38                         s[i] = 0;                                                                                                       \
  39                         if (n == max) {                                                                                         \
  40                                 max = max? max<<1 : 2;                                                                  \
  41                                 offsets = (int*)realloc(offsets, sizeof(int) * max);    \
  42                         }                                                                                                                       \
  43                         offsets[n++] = last_start;                                                                      \
  44                 } else ++n;                                                                                                             \
  45         } while (0)
  46
  47         for (i = 0, last_char = last_start = 0; i <= l; ++i) {
  48                 if (delimiter == 0) {
  49                         if (isspace(s[i]) || s[i] == 0) {
  50                                 if (isgraph(last_char)) __ksplit_aux; // the end of a field
  51                         } else {
  52                                 if (isspace(last_char) || last_char == 0) last_start = i;
  53                         }
  54                 } else {
  55                         if (s[i] == delimiter || s[i] == 0) {
  56                                 if (last_char != 0 && last_char != delimiter) __ksplit_aux; // the end of a field
  57                         } else {
  58                                 if (last_char == delimiter || last_char == 0) last_start = i;
  59                         }
  60                 }
  61                 last_char = s[i];
  62         }
  63         *_max = max; *_offsets = offsets;
  64         return n;
  65 }
  66
  67 /**********************
  68  * Boyer-Moore search *
  69  **********************/
  70
  71 // reference: http://www-igm.univ-mlv.fr/~lecroq/string/node14.html
  72 int *ksBM_prep(const uint8_t *pat, int m)
  73 {
  74         int i, *suff, *prep, *bmGs, *bmBc;
  75         prep = calloc(m + 256, 1);
  76         bmGs = prep; bmBc = prep + m;
  77         { // preBmBc()
  78                 for (i = 0; i < 256; ++i) bmBc[i] = m;
  79                 for (i = 0; i < m - 1; ++i) bmBc[pat[i]] = m - i - 1;
  80         }
  81         suff = calloc(m, sizeof(int));
  82         { // suffixes()
  83                 int f = 0, g;
  84                 suff[m - 1] = m;
  85                 g = m - 1;
  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];
  89                         else {
  90                                 if (i < g) g = i;
  91                                 f = i;
  92                                 while (g >= 0 && pat[g] == pat[g + m - 1 - f]) --g;
  93                                 suff[i] = f - g;
  94                         }
  95                 }
  96         }
  97         { // preBmGs()
  98                 int j = 0;
  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)
 103                                         if (bmGs[j] == m)
 104                                                 bmGs[j] = m - 1 - i;
 105                 for (i = 0; i <= m - 2; ++i)
 106                         bmGs[m - 1 - suff[i]] = m - 1 - i;
 107         }
 108         free(suff);
 109         return prep;
 110 }
 111
 112 int *ksBM_search(const uint8_t *str, int n, const uint8_t *pat, int m, int *_prep, int *n_matches)
 113 {
 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;
 118         j = 0;
 119         while (j <= n - m) {
 120                 for (i = m - 1; i >= 0 && pat[i] == str[i+j]; --i);
 121                 if (i < 0) {
 122                         if (nm == mm) {
 123                                 mm = mm? mm<<1 : 1;
 124                                 matches = realloc(matches, mm * sizeof(int));
 125                         }
 126                         matches[nm++] = j;
 127                         j += bmGs[0];
 128                 } else {
 129                         int max = bmBc[str[i+j]] - m + 1 + i;
 130                         if (max < bmGs[i]) max = bmGs[i];
 131                         j += max;
 132                 }
 133         }
 134         *n_matches = nm;
 135         if (_prep == 0) free(prep);
 136         return matches;
 137 }
 138
 139 #ifdef KSTRING_MAIN
 140 #include <stdio.h>
 141 int main()
 142 {
 143         kstring_t *s;
 144         int *fields, n, i;
 145         s = (kstring_t*)calloc(1, sizeof(kstring_t));
 146         // test ksprintf()
 147         ksprintf(s, " abcdefg:    %d ", 100);
 148         printf("'%s'\n", s->s);
 149         // test ksplit()
 150         fields = ksplit(s, 0, &n);
 151         for (i = 0; i < n; ++i)
 152                 printf("field[%d] = '%s'\n", i, s->s + fields[i]);
 153         free(s);
 154
 155         {
 156                 static char *str = "abcdefgcdg";
 157                 static char *pat = "cd";
 158                 int n, *matches;
 159                 matches = ksBM_search(str, strlen(str), pat, strlen(pat), 0, &n);
 160                 printf("%d: \n", n);
 161                 for (i = 0; i < n; ++i)
 162                         printf("- %d\n", matches[i]);
 163                 free(matches);
 164         }
 165         return 0;
 166 }
 167 #endif