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->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)
  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
  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
 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
 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
 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>
 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