c_cpp/lib/klib/knhx.c

   1 #include <ctype.h>
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include <string.h>
   5 #include "knhx.h"
   6
   7 typedef struct {
   8         int error, n, max;
   9         knhx1_t *node;
  10 } knaux_t;
  11
  12 static inline char *add_node(const char *s, knaux_t *aux, int x)
  13 {
  14         char *p, *nbeg, *nend = 0;
  15         knhx1_t *r;
  16         if (aux->n == aux->max) {
  17                 aux->max = aux->max? aux->max<<1 : 8;
  18                 aux->node = (knhx1_t*)realloc(aux->node, sizeof(knhx1_t) * aux->max);
  19         }
  20         r = aux->node + (aux->n++);
  21         r->n = x; r->parent = -1;
  22         for (p = (char*)s, nbeg = p, r->d = -1.0; *p && *p != ',' && *p != ')'; ++p) {
  23                 if (*p == '[') {
  24                         if (nend == 0) nend = p;
  25                         do ++p; while (*p && *p != ']');
  26                         if (*p == 0) {
  27                                 aux->error |= KNERR_BRACKET;
  28                                 break;
  29                         }
  30                 } else if (*p == ':') {
  31                         if (nend == 0) nend = p;
  32                         r->d = strtod(p + 1, &p);
  33                         --p;
  34                 } else if (!isgraph(*p)) if (nend == 0) nend = p;
  35         }
  36         if (nend == 0) nend = p;
  37         if (nend != nbeg) {
  38                 r->name = (char*)calloc(nend - nbeg + 1, 1);
  39                 strncpy(r->name, nbeg, nend - nbeg);
  40         } else r->name = strdup("");
  41         return p;
  42 }
  43
  44 knhx1_t *kn_parse(const char *nhx, int *_n, int *_error)
  45 {
  46         char *p;
  47         int *stack, top, max;
  48         knaux_t *aux;
  49         knhx1_t *ret;
  50
  51 #define __push_back(y) do {                                                                             \
  52                 if (top == max) {                                                                               \
  53                         max = max? max<<1 : 16;                                                         \
  54                         stack = (int*)realloc(stack, sizeof(int) * max);        \
  55                 }                                                                                                               \
  56                 stack[top++] = (y);                                                                             \
  57         } while (0)                                                                                                     \
  58
  59         stack = 0; top = max = 0;
  60         p = (char*)nhx;
  61         aux = (knaux_t*)calloc(1, sizeof(knaux_t));
  62         while (*p) {
  63                 while (*p && !isgraph(*p)) ++p;
  64                 if (*p == 0) break;
  65                 if (*p == ',') ++p;
  66                 else if (*p == '(') {
  67                         __push_back(-1);
  68                         ++p;
  69                 } else if (*p == ')') {
  70                         int x = aux->n, m, i;
  71                         for (i = top - 1; i >= 0; --i)
  72                                 if (stack[i] < 0) break;
  73                         m = top - 1 - i;
  74                         p = add_node(p + 1, aux, m);
  75                         aux->node[x].child = (int*)calloc(m, sizeof(int));
  76                         for (i = top - 1, m = m - 1; m >= 0; --m, --i) {
  77                                 aux->node[x].child[m] = stack[i];
  78                                 aux->node[stack[i]].parent = x;
  79                         }
  80                         top = i;
  81                         __push_back(x);
  82                 } else {
  83                         __push_back(aux->n);
  84                         p = add_node(p, aux, 0);
  85                 }
  86         }
  87         *_n = aux->n;
  88         *_error = aux->error;
  89         ret = aux->node;
  90         free(aux); free(stack);
  91         return ret;
  92 }
  93
  94 #ifndef kroundup32
  95 #define kroundup32(x) (--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, ++(x))
  96 #endif
  97
  98 static inline int kputsn(const char *p, int l, kstring_t *s)
  99 {
 100         if (s->l + l + 1 >= s->m) {
 101                 s->m = s->l + l + 2;
 102                 kroundup32(s->m);
 103                 s->s = (char*)realloc(s->s, s->m);
 104         }
 105         memcpy(s->s + s->l, p, l);
 106         s->l += l; s->s[s->l] = 0;
 107         return l;
 108 }
 109
 110 static inline int kputc(int c, kstring_t *s)
 111 {
 112         if (s->l + 1 >= s->m) {
 113                 s->m = s->l + 2;
 114                 kroundup32(s->m);
 115                 s->s = (char*)realloc(s->s, s->m);
 116         }
 117         s->s[s->l++] = c; s->s[s->l] = 0;
 118         return c;
 119 }
 120
 121 static void format_node_recur(const knhx1_t *node, const knhx1_t *p, kstring_t *s, char *numbuf)
 122 {
 123         if (p->n) {
 124                 int i;
 125                 kputc('(', s);
 126                 for (i = 0; i < p->n; ++i) {
 127                         if (i) kputc(',', s);
 128                         format_node_recur(node, &node[p->child[i]], s, numbuf);
 129                 }
 130                 kputc(')', s);
 131                 if (p->name) kputsn(p->name, strlen(p->name), s);
 132                 if (p->d >= 0) {
 133                         sprintf(numbuf, ":%g", p->d);
 134                         kputsn(numbuf, strlen(numbuf), s);
 135                 }
 136         } else {
 137           kputsn(p->name, strlen(p->name), s);
 138           if (p->d >= 0) {
 139             sprintf(numbuf, ":%g", p->d);
 140             kputsn(numbuf, strlen(numbuf), s);
 141           }
 142         }
 143 }
 144
 145 void kn_format(const knhx1_t *node, int root, kstring_t *s) // TODO: get rid of recursion
 146 {
 147         char numbuf[128];
 148         format_node_recur(node, &node[root], s, numbuf);
 149 }
 150
 151 #ifdef KNHX_MAIN
 152 int main(int argc, char *argv[])
 153 {
 154         char *s = "((a[abc],d1)x:0.5,((b[&&NHX:S=MOUSE],h2)[&&NHX:S=HUMAN:B=99][blabla][&&NHX:K=foo],c))";
 155         knhx1_t *node;
 156         int i, j, n, error;
 157         kstring_t str;
 158         node = kn_parse(s, &n, &error);
 159         for (i = 0; i < n; ++i) {
 160                 knhx1_t *p = node + i;
 161                 printf("[%d] %s\t%d\t%d\t%g", i, p->name, p->parent, p->n, p->d);
 162                 for (j = 0; j < p->n; ++j)
 163                         printf("\t%d", p->child[j]);
 164                 putchar('\n');
 165         }
 166         str.l = str.m = 0; str.s = 0;
 167         kn_format(node, n-1, &str);
 168         puts(str.s);
 169         free(str.s);
 170         return 0;
 171 }
 172 #endif