DNS Decoder create version

5 files changed, 4780 insertions, 0 deletions

diff --git a/deps/toml/CMakeLists.txt b/deps/toml/CMakeLists.txt
new file mode 100644
index 0000000..504c0bf
--- /dev/null
+++ b/deps/toml/CMakeLists.txt
@@ -0,0 +1,3 @@
+set(CMAKE_C_FLAGS "-std=c99")
+add_definitions(-fPIC)
+add_library(toml STATIC toml.c)
\ No newline at end of file
diff --git a/deps/toml/toml.c b/deps/toml/toml.c
new file mode 100644
index 0000000..fafe0da
--- /dev/null
+++ b/deps/toml/toml.c
@@ -0,0 +1,2379 @@
+/*
+
+  MIT License
+
+  Copyright (c) CK Tan
+  https://github.com/cktan/tomlc99
+
+  Permission is hereby granted, free of charge, to any person obtaining a copy
+  of this software and associated documentation files (the "Software"), to deal
+  in the Software without restriction, including without limitation the rights
+  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+  copies of the Software, and to permit persons to whom the Software is
+  furnished to do so, subject to the following conditions:
+
+  The above copyright notice and this permission notice shall be included in all
+  copies or substantial portions of the Software.
+
+  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+  SOFTWARE.
+
+*/
+#define _POSIX_C_SOURCE 200809L
+#include "toml.h"
+#include <assert.h>
+#include <ctype.h>
+#include <errno.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+static void *(*ppmalloc)(size_t) = malloc;
+static void (*ppfree)(void *) = free;
+
+void toml_set_memutil(void *(*xxmalloc)(size_t), void (*xxfree)(void *)) {
+  if (xxmalloc)
+    ppmalloc = xxmalloc;
+  if (xxfree)
+    ppfree = xxfree;
+}
+
+#define MALLOC(a) ppmalloc(a)
+#define FREE(a) ppfree(a)
+
+#define malloc(x) error - forbidden - use MALLOC instead
+#define free(x) error - forbidden - use FREE instead
+#define calloc(x, y) error - forbidden - use CALLOC instead
+
+static void *CALLOC(size_t nmemb, size_t sz) {
+  int nb = sz * nmemb;
+  void *p = MALLOC(nb);
+  if (p) {
+    memset(p, 0, nb);
+  }
+  return p;
+}
+
+// some old platforms define strdup macro -- drop it.
+#undef strdup
+#define strdup(x) error - forbidden - use STRDUP instead
+
+static char *STRDUP(const char *s) {
+  int len = strlen(s);
+  char *p = MALLOC(len + 1);
+  if (p) {
+    memcpy(p, s, len);
+    p[len] = 0;
+  }
+  return p;
+}
+
+// some old platforms define strndup macro -- drop it.
+#undef strndup
+#define strndup(x) error - forbiden - use STRNDUP instead
+
+static char *STRNDUP(const char *s, size_t n) {
+  size_t len = strnlen(s, n);
+  char *p = MALLOC(len + 1);
+  if (p) {
+    memcpy(p, s, len);
+    p[len] = 0;
+  }
+  return p;
+}
+
+/**
+ * Convert a char in utf8 into UCS, and store it in *ret.
+ * Return #bytes consumed or -1 on failure.
+ */
+int toml_utf8_to_ucs(const char *orig, int len, int64_t *ret) {
+  const unsigned char *buf = (const unsigned char *)orig;
+  unsigned i = *buf++;
+  int64_t v;
+
+  /* 0x00000000 - 0x0000007F:
+     0xxxxxxx
+  */
+  if (0 == (i >> 7)) {
+    if (len < 1)
+      return -1;
+    v = i;
+    return *ret = v, 1;
+  }
+  /* 0x00000080 - 0x000007FF:
+     110xxxxx 10xxxxxx
+  */
+  if (0x6 == (i >> 5)) {
+    if (len < 2)
+      return -1;
+    v = i & 0x1f;
+    for (int j = 0; j < 1; j++) {
+      i = *buf++;
+      if (0x2 != (i >> 6))
+        return -1;
+      v = (v << 6) | (i & 0x3f);
+    }
+    return *ret = v, (const char *)buf - orig;
+  }
+
+  /* 0x00000800 - 0x0000FFFF:
+     1110xxxx 10xxxxxx 10xxxxxx
+  */
+  if (0xE == (i >> 4)) {
+    if (len < 3)
+      return -1;
+    v = i & 0x0F;
+    for (int j = 0; j < 2; j++) {
+      i = *buf++;
+      if (0x2 != (i >> 6))
+        return -1;
+      v = (v << 6) | (i & 0x3f);
+    }
+    return *ret = v, (const char *)buf - orig;
+  }
+
+  /* 0x00010000 - 0x001FFFFF:
+     11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
+  */
+  if (0x1E == (i >> 3)) {
+    if (len < 4)
+      return -1;
+    v = i & 0x07;
+    for (int j = 0; j < 3; j++) {
+      i = *buf++;
+      if (0x2 != (i >> 6))
+        return -1;
+      v = (v << 6) | (i & 0x3f);
+    }
+    return *ret = v, (const char *)buf - orig;
+  }
+
+  /* 0x00200000 - 0x03FFFFFF:
+     111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
+  */
+  if (0x3E == (i >> 2)) {
+    if (len < 5)
+      return -1;
+    v = i & 0x03;
+    for (int j = 0; j < 4; j++) {
+      i = *buf++;
+      if (0x2 != (i >> 6))
+        return -1;
+      v = (v << 6) | (i & 0x3f);
+    }
+    return *ret = v, (const char *)buf - orig;
+  }
+
+  /* 0x04000000 - 0x7FFFFFFF:
+     1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
+  */
+  if (0x7e == (i >> 1)) {
+    if (len < 6)
+      return -1;
+    v = i & 0x01;
+    for (int j = 0; j < 5; j++) {
+      i = *buf++;
+      if (0x2 != (i >> 6))
+        return -1;
+      v = (v << 6) | (i & 0x3f);
+    }
+    return *ret = v, (const char *)buf - orig;
+  }
+  return -1;
+}
+
+/**
+ *	Convert a UCS char to utf8 code, and return it in buf.
+ *	Return #bytes used in buf to encode the char, or
+ *	-1 on error.
+ */
+int toml_ucs_to_utf8(int64_t code, char buf[6]) {
+  /* http://stackoverflow.com/questions/6240055/manually-converting-unicode-codepoints-into-utf-8-and-utf-16
+   */
+  /* The UCS code values 0xd800–0xdfff (UTF-16 surrogates) as well
+   * as 0xfffe and 0xffff (UCS noncharacters) should not appear in
+   * conforming UTF-8 streams.
+   */
+  if (0xd800 <= code && code <= 0xdfff)
+    return -1;
+  if (0xfffe <= code && code <= 0xffff)
+    return -1;
+
+  /* 0x00000000 - 0x0000007F:
+     0xxxxxxx
+  */
+  if (code < 0)
+    return -1;
+  if (code <= 0x7F) {
+    buf[0] = (unsigned char)code;
+    return 1;
+  }
+
+  /* 0x00000080 - 0x000007FF:
+     110xxxxx 10xxxxxx
+  */
+  if (code <= 0x000007FF) {
+    buf[0] = (unsigned char) (0xc0 | (code >> 6));
+    buf[1] = (unsigned char) (0x80 | (code & 0x3f));
+    return 2;
+  }
+
+  /* 0x00000800 - 0x0000FFFF:
+     1110xxxx 10xxxxxx 10xxxxxx
+  */
+  if (code <= 0x0000FFFF) {
+    buf[0] = (unsigned char) (0xe0 | (code >> 12));
+    buf[1] = (unsigned char) (0x80 | ((code >> 6) & 0x3f));
+    buf[2] = (unsigned char) (0x80 | (code & 0x3f));
+    return 3;
+  }
+
+  /* 0x00010000 - 0x001FFFFF:
+     11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
+  */
+  if (code <= 0x001FFFFF) {
+    buf[0] = (unsigned char) (0xf0 | (code >> 18));
+    buf[1] = (unsigned char) (0x80 | ((code >> 12) & 0x3f));
+    buf[2] = (unsigned char) (0x80 | ((code >> 6) & 0x3f));
+    buf[3] = (unsigned char) (0x80 | (code & 0x3f));
+    return 4;
+  }
+
+  /* 0x00200000 - 0x03FFFFFF:
+     111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
+  */
+  if (code <= 0x03FFFFFF) {
+    buf[0] = (unsigned char) (0xf8 | (code >> 24));
+    buf[1] = (unsigned char) (0x80 | ((code >> 18) & 0x3f));
+    buf[2] = (unsigned char) (0x80 | ((code >> 12) & 0x3f));
+    buf[3] = (unsigned char) (0x80 | ((code >> 6) & 0x3f));
+    buf[4] = (unsigned char) (0x80 | (code & 0x3f));
+    return 5;
+  }
+
+  /* 0x04000000 - 0x7FFFFFFF:
+     1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
+  */
+  if (code <= 0x7FFFFFFF) {
+    buf[0] = (unsigned char) (0xfc | (code >> 30));
+    buf[1] = (unsigned char) (0x80 | ((code >> 24) & 0x3f));
+    buf[2] = (unsigned char) (0x80 | ((code >> 18) & 0x3f));
+    buf[3] = (unsigned char) (0x80 | ((code >> 12) & 0x3f));
+    buf[4] = (unsigned char) (0x80 | ((code >> 6) & 0x3f));
+    buf[5] = (unsigned char) (0x80 | (code & 0x3f));
+    return 6;
+  }
+
+  return -1;
+}
+
+/*
+ *	TOML has 3 data structures: value, array, table.
+ *	Each of them can have identification key.
+ */
+typedef struct toml_keyval_t toml_keyval_t;
+struct toml_keyval_t {
+  const char *key; /* key to this value */
+  const char *val; /* the raw value */
+};
+
+typedef struct toml_arritem_t toml_arritem_t;
+struct toml_arritem_t {
+  int valtype; /* for value kind: 'i'nt, 'd'ouble, 'b'ool, 's'tring, 't'ime,
+                  'D'ate, 'T'imestamp */
+  char *val;
+  toml_array_t *arr;
+  toml_table_t *tab;
+};
+
+struct toml_array_t {
+  const char *key; /* key to this array */
+  int kind;        /* element kind: 'v'alue, 'a'rray, or 't'able, 'm'ixed */
+  int type;        /* for value kind: 'i'nt, 'd'ouble, 'b'ool, 's'tring, 't'ime,
+                      'D'ate, 'T'imestamp, 'm'ixed */
+
+  int nitem; /* number of elements */
+  toml_arritem_t *item;
+};
+
+struct toml_table_t {
+  const char *key; /* key to this table */
+  bool implicit;   /* table was created implicitly */
+  bool readonly;   /* no more modification allowed */
+
+  /* key-values in the table */
+  int nkval;
+  toml_keyval_t **kval;
+
+  /* arrays in the table */
+  int narr;
+  toml_array_t **arr;
+
+  /* tables in the table */
+  int ntab;
+  toml_table_t **tab;
+};
+
+static inline void xfree(const void *x) {
+  if (x)
+    FREE((void *)(intptr_t)x);
+}
+
+enum tokentype_t {
+  INVALID,
+  DOT,
+  COMMA,
+  EQUAL,
+  LBRACE,
+  RBRACE,
+  NEWLINE,
+  LBRACKET,
+  RBRACKET,
+  STRING,
+};
+typedef enum tokentype_t tokentype_t;
+
+typedef struct token_t token_t;
+struct token_t {
+  tokentype_t tok;
+  int lineno;
+  char *ptr; /* points into context->start */
+  int len;
+  int eof;
+};
+
+typedef struct context_t context_t;
+struct context_t {
+  char *start;
+  char *stop;
+  char *errbuf;
+  int errbufsz;
+
+  token_t tok;
+  toml_table_t *root;
+  toml_table_t *curtab;
+
+  struct {
+    int top;
+    char *key[10];
+    token_t tok[10];
+  } tpath;
+};
+
+#define STRINGIFY(x) #x
+#define TOSTRING(x) STRINGIFY(x)
+#define FLINE __FILE__ ":" TOSTRING(__LINE__)
+
+static int next_token(context_t *ctx, int dotisspecial);
+
+/*
+  Error reporting. Call when an error is detected. Always return -1.
+*/
+static int e_outofmemory(context_t *ctx, const char *fline) {
+  snprintf(ctx->errbuf, ctx->errbufsz, "ERROR: out of memory (%s)", fline);
+  return -1;
+}
+
+static int e_internal(context_t *ctx, const char *fline) {
+  snprintf(ctx->errbuf, ctx->errbufsz, "internal error (%s)", fline);
+  return -1;
+}
+
+static int e_syntax(context_t *ctx, int lineno, const char *msg) {
+  snprintf(ctx->errbuf, ctx->errbufsz, "line %d: %s", lineno, msg);
+  return -1;
+}
+
+static int e_badkey(context_t *ctx, int lineno) {
+  snprintf(ctx->errbuf, ctx->errbufsz, "line %d: bad key", lineno);
+  return -1;
+}
+
+static int e_keyexists(context_t *ctx, int lineno) {
+  snprintf(ctx->errbuf, ctx->errbufsz, "line %d: key exists", lineno);
+  return -1;
+}
+
+static int e_forbid(context_t *ctx, int lineno, const char *msg) {
+  snprintf(ctx->errbuf, ctx->errbufsz, "line %d: %s", lineno, msg);
+  return -1;
+}
+
+static void *expand(void *p, int sz, int newsz) {
+  void *s = MALLOC(newsz);
+  if (!s)
+    return 0;
+
+  memcpy(s, p, sz);
+  FREE(p);
+  return s;
+}
+
+static void **expand_ptrarr(void **p, int n) {
+  void **s = MALLOC((n + 1) * sizeof(void *));
+  if (!s)
+    return 0;
+
+  s[n] = 0;
+  memcpy(s, p, n * sizeof(void *));
+  FREE(p);
+  return s;
+}
+
+static toml_arritem_t *expand_arritem(toml_arritem_t *p, int n) {
+  toml_arritem_t *pp = expand(p, n * sizeof(*p), (n + 1) * sizeof(*p));
+  if (!pp)
+    return 0;
+
+  memset(&pp[n], 0, sizeof(pp[n]));
+  return pp;
+}
+
+static char *norm_lit_str(const char *src, int srclen, int multiline,
+                          char *errbuf, int errbufsz) {
+  char *dst = 0; /* will write to dst[] and return it */
+  int max = 0;   /* max size of dst[] */
+  int off = 0;   /* cur offset in dst[] */
+  const char *sp = src;
+  const char *sq = src + srclen;
+  int ch;
+
+  /* scan forward on src */
+  for (;;) {
+    if (off >= max - 10) { /* have some slack for misc stuff */
+      int newmax = max + 50;
+      char *x = expand(dst, max, newmax);
+      if (!x) {
+        xfree(dst);
+        snprintf(errbuf, errbufsz, "out of memory");
+        return 0;
+      }
+      dst = x;
+      max = newmax;
+    }
+
+    /* finished? */
+    if (sp >= sq)
+      break;
+
+    ch = *sp++;
+    /* control characters other than tab is not allowed */
+    if ((0 <= ch && ch <= 0x08) || (0x0a <= ch && ch <= 0x1f) || (ch == 0x7f)) {
+      if (!(multiline && (ch == '\r' || ch == '\n'))) {
+        xfree(dst);
+        snprintf(errbuf, errbufsz, "invalid char U+%04x", ch);
+        return 0;
+      }
+    }
+
+    // a plain copy suffice
+    dst[off++] = ch;
+  }
+
+  dst[off++] = 0;
+  return dst;
+}
+
+/*
+ * Convert src to raw unescaped utf-8 string.
+ * Returns NULL if error with errmsg in errbuf.
+ */
+static char *norm_basic_str(const char *src, int srclen, int multiline,
+                            char *errbuf, int errbufsz) {
+  char *dst = 0; /* will write to dst[] and return it */
+  int max = 0;   /* max size of dst[] */
+  int off = 0;   /* cur offset in dst[] */
+  const char *sp = src;
+  const char *sq = src + srclen;
+  int ch;
+
+  /* scan forward on src */
+  for (;;) {
+    if (off >= max - 10) { /* have some slack for misc stuff */
+      int newmax = max + 50;
+      char *x = expand(dst, max, newmax);
+      if (!x) {
+        xfree(dst);
+        snprintf(errbuf, errbufsz, "out of memory");
+        return 0;
+      }
+      dst = x;
+      max = newmax;
+    }
+
+    /* finished? */
+    if (sp >= sq)
+      break;
+
+    ch = *sp++;
+    if (ch != '\\') {
+      /* these chars must be escaped: U+0000 to U+0008, U+000A to U+001F, U+007F
+       */
+      if ((0 <= ch && ch <= 0x08) || (0x0a <= ch && ch <= 0x1f) ||
+          (ch == 0x7f)) {
+        if (!(multiline && (ch == '\r' || ch == '\n'))) {
+          xfree(dst);
+          snprintf(errbuf, errbufsz, "invalid char U+%04x", ch);
+          return 0;
+        }
+      }
+
+      // a plain copy suffice
+      dst[off++] = ch;
+      continue;
+    }
+
+    /* ch was backslash. we expect the escape char. */
+    if (sp >= sq) {
+      snprintf(errbuf, errbufsz, "last backslash is invalid");
+      xfree(dst);
+      return 0;
+    }
+
+    /* for multi-line, we want to kill line-ending-backslash ... */
+    if (multiline) {
+
+      // if there is only whitespace after the backslash ...
+      if (sp[strspn(sp, " \t\r")] == '\n') {
+        /* skip all the following whitespaces */
+        sp += strspn(sp, " \t\r\n");
+        continue;
+      }
+    }
+
+    /* get the escaped char */
+    ch = *sp++;
+    switch (ch) {
+    case 'u':
+    case 'U': {
+      int64_t ucs = 0;
+      int nhex = (ch == 'u' ? 4 : 8);
+      for (int i = 0; i < nhex; i++) {
+        if (sp >= sq) {
+          snprintf(errbuf, errbufsz, "\\%c expects %d hex chars", ch, nhex);
+          xfree(dst);
+          return 0;
+        }
+        ch = *sp++;
+        int v = ('0' <= ch && ch <= '9')
+                    ? ch - '0'
+                    : (('A' <= ch && ch <= 'F') ? ch - 'A' + 10 : -1);
+        if (-1 == v) {
+          snprintf(errbuf, errbufsz, "invalid hex chars for \\u or \\U");
+          xfree(dst);
+          return 0;
+        }
+        ucs = ucs * 16 + v;
+      }
+      int n = toml_ucs_to_utf8(ucs, &dst[off]);
+      if (-1 == n) {
+        snprintf(errbuf, errbufsz, "illegal ucs code in \\u or \\U");
+        xfree(dst);
+        return 0;
+      }
+      off += n;
+    }
+      continue;
+
+    case 'b':
+      ch = '\b';
+      break;
+    case 't':
+      ch = '\t';
+      break;
+    case 'n':
+      ch = '\n';
+      break;
+    case 'f':
+      ch = '\f';
+      break;
+    case 'r':
+      ch = '\r';
+      break;
+    case '"':
+      ch = '"';
+      break;
+    case '\\':
+      ch = '\\';
+      break;
+    default:
+      snprintf(errbuf, errbufsz, "illegal escape char \\%c", ch);
+      xfree(dst);
+      return 0;
+    }
+
+    dst[off++] = ch;
+  }
+
+  // Cap with NUL and return it.
+  dst[off++] = 0;
+  return dst;
+}
+
+/* Normalize a key. Convert all special chars to raw unescaped utf-8 chars. */
+static char *normalize_key(context_t *ctx, token_t strtok) {
+  const char *sp = strtok.ptr;
+  const char *sq = strtok.ptr + strtok.len;
+  int lineno = strtok.lineno;
+  char *ret;
+  int ch = *sp;
+  char ebuf[80];
+
+  /* handle quoted string */
+  if (ch == '\'' || ch == '\"') {
+    /* if ''' or """, take 3 chars off front and back. Else, take 1 char off. */
+    int multiline = 0;
+    if (sp[1] == ch && sp[2] == ch) {
+      sp += 3, sq -= 3;
+      multiline = 1;
+    } else
+      sp++, sq--;
+
+    if (ch == '\'') {
+      /* for single quote, take it verbatim. */
+      if (!(ret = STRNDUP(sp, sq - sp))) {
+        e_outofmemory(ctx, FLINE);
+        return 0;
+      }
+    } else {
+      /* for double quote, we need to normalize */
+      ret = norm_basic_str(sp, sq - sp, multiline, ebuf, sizeof(ebuf));
+      if (!ret) {
+        e_syntax(ctx, lineno, ebuf);
+        return 0;
+      }
+    }
+
+    /* newlines are not allowed in keys */
+    if (strchr(ret, '\n')) {
+      xfree(ret);
+      e_badkey(ctx, lineno);
+      return 0;
+    }
+    return ret;
+  }
+
+  /* for bare-key allow only this regex: [A-Za-z0-9_-]+ */
+  const char *xp;
+  for (xp = sp; xp != sq; xp++) {
+    int k = *xp;
+    if (isalnum(k))
+      continue;
+    if (k == '_' || k == '-')
+      continue;
+    e_badkey(ctx, lineno);
+    return 0;
+  }
+
+  /* dup and return it */
+  if (!(ret = STRNDUP(sp, sq - sp))) {
+    e_outofmemory(ctx, FLINE);
+    return 0;
+  }
+  return ret;
+}
+
+/*
+ * Look up key in tab. Return 0 if not found, or
+ * 'v'alue, 'a'rray or 't'able depending on the element.
+ */
+static int check_key(toml_table_t *tab, const char *key,
+                     toml_keyval_t **ret_val, toml_array_t **ret_arr,
+                     toml_table_t **ret_tab) {
+  int i;
+  void *dummy;
+
+  if (!ret_tab)
+    ret_tab = (toml_table_t **)&dummy;
+  if (!ret_arr)
+    ret_arr = (toml_array_t **)&dummy;
+  if (!ret_val)
+    ret_val = (toml_keyval_t **)&dummy;
+
+  *ret_tab = 0;
+  *ret_arr = 0;
+  *ret_val = 0;
+
+  for (i = 0; i < tab->nkval; i++) {
+    if (0 == strcmp(key, tab->kval[i]->key)) {
+      *ret_val = tab->kval[i];
+      return 'v';
+    }
+  }
+  for (i = 0; i < tab->narr; i++) {
+    if (0 == strcmp(key, tab->arr[i]->key)) {
+      *ret_arr = tab->arr[i];
+      return 'a';
+    }
+  }
+  for (i = 0; i < tab->ntab; i++) {
+    if (0 == strcmp(key, tab->tab[i]->key)) {
+      *ret_tab = tab->tab[i];
+      return 't';
+    }
+  }
+  return 0;
+}
+
+static int key_kind(toml_table_t *tab, const char *key) {
+  return check_key(tab, key, 0, 0, 0);
+}
+
+/* Create a keyval in the table.
+ */
+static toml_keyval_t *create_keyval_in_table(context_t *ctx, toml_table_t *tab,
+                                             token_t keytok) {
+  /* first, normalize the key to be used for lookup.
+   * remember to free it if we error out.
+   */
+  char *newkey = normalize_key(ctx, keytok);
+  if (!newkey)
+    return 0;
+
+  /* if key exists: error out. */
+  toml_keyval_t *dest = 0;
+  if (key_kind(tab, newkey)) {
+    xfree(newkey);
+    e_keyexists(ctx, keytok.lineno);
+    return 0;
+  }
+
+  /* make a new entry */
+  int n = tab->nkval;
+  toml_keyval_t **base;
+  if (0 == (base = (toml_keyval_t **)expand_ptrarr((void **)tab->kval, n))) {
+    xfree(newkey);
+    e_outofmemory(ctx, FLINE);
+    return 0;
+  }
+  tab->kval = base;
+
+  if (0 == (base[n] = (toml_keyval_t *)CALLOC(1, sizeof(*base[n])))) {
+    xfree(newkey);
+    e_outofmemory(ctx, FLINE);
+    return 0;
+  }
+  dest = tab->kval[tab->nkval++];
+
+  /* save the key in the new value struct */
+  dest->key = newkey;
+  return dest;
+}
+
+/* Create a table in the table.
+ */
+static toml_table_t *create_keytable_in_table(context_t *ctx, toml_table_t *tab,
+                                              token_t keytok) {
+  /* first, normalize the key to be used for lookup.
+   * remember to free it if we error out.
+   */
+  char *newkey = normalize_key(ctx, keytok);
+  if (!newkey)
+    return 0;
+
+  /* if key exists: error out */
+  toml_table_t *dest = 0;
+  if (check_key(tab, newkey, 0, 0, &dest)) {
+    xfree(newkey); /* don't need this anymore */
+
+    /* special case: if table exists, but was created implicitly ... */
+    if (dest && dest->implicit) {
+      /* we make it explicit now, and simply return it. */
+      dest->implicit = false;
+      return dest;
+    }
+    e_keyexists(ctx, keytok.lineno);
+    return 0;
+  }
+
+  /* create a new table entry */
+  int n = tab->ntab;
+  toml_table_t **base;
+  if (0 == (base = (toml_table_t **)expand_ptrarr((void **)tab->tab, n))) {
+    xfree(newkey);
+    e_outofmemory(ctx, FLINE);
+    return 0;
+  }
+  tab->tab = base;
+
+  if (0 == (base[n] = (toml_table_t *)CALLOC(1, sizeof(*base[n])))) {
+    xfree(newkey);
+    e_outofmemory(ctx, FLINE);
+    return 0;
+  }
+  dest = tab->tab[tab->ntab++];
+
+  /* save the key in the new table struct */
+  dest->key = newkey;
+  return dest;
+}
+
+/* Create an array in the table.
+ */
+static toml_array_t *create_keyarray_in_table(context_t *ctx, toml_table_t *tab,
+                                              token_t keytok, char kind) {
+  /* first, normalize the key to be used for lookup.
+   * remember to free it if we error out.
+   */
+  char *newkey = normalize_key(ctx, keytok);
+  if (!newkey)
+    return 0;
+
+  /* if key exists: error out */
+  if (key_kind(tab, newkey)) {
+    xfree(newkey); /* don't need this anymore */
+    e_keyexists(ctx, keytok.lineno);
+    return 0;
+  }
+
+  /* make a new array entry */
+  int n = tab->narr;
+  toml_array_t **base;
+  if (0 == (base = (toml_array_t **)expand_ptrarr((void **)tab->arr, n))) {
+    xfree(newkey);
+    e_outofmemory(ctx, FLINE);
+    return 0;
+  }
+  tab->arr = base;
+
+  if (0 == (base[n] = (toml_array_t *)CALLOC(1, sizeof(*base[n])))) {
+    xfree(newkey);
+    e_outofmemory(ctx, FLINE);
+    return 0;
+  }
+  toml_array_t *dest = tab->arr[tab->narr++];
+
+  /* save the key in the new array struct */
+  dest->key = newkey;
+  dest->kind = kind;
+  return dest;
+}
+
+static toml_arritem_t *create_value_in_array(context_t *ctx,
+                                             toml_array_t *parent) {
+  const int n = parent->nitem;
+  toml_arritem_t *base = expand_arritem(parent->item, n);
+  if (!base) {
+    e_outofmemory(ctx, FLINE);
+    return 0;
+  }
+  parent->item = base;
+  parent->nitem++;
+  return &parent->item[n];
+}
+
+/* Create an array in an array
+ */
+static toml_array_t *create_array_in_array(context_t *ctx,
+                                           toml_array_t *parent) {
+  const int n = parent->nitem;
+  toml_arritem_t *base = expand_arritem(parent->item, n);
+  if (!base) {
+    e_outofmemory(ctx, FLINE);
+    return 0;
+  }
+  toml_array_t *ret = (toml_array_t *)CALLOC(1, sizeof(toml_array_t));
+  if (!ret) {
+    e_outofmemory(ctx, FLINE);
+    return 0;
+  }
+  base[n].arr = ret;
+  parent->item = base;
+  parent->nitem++;
+  return ret;
+}
+
+/* Create a table in an array
+ */
+static toml_table_t *create_table_in_array(context_t *ctx,
+                                           toml_array_t *parent) {
+  int n = parent->nitem;
+  toml_arritem_t *base = expand_arritem(parent->item, n);
+  if (!base) {
+    e_outofmemory(ctx, FLINE);
+    return 0;
+  }
+  toml_table_t *ret = (toml_table_t *)CALLOC(1, sizeof(toml_table_t));
+  if (!ret) {
+    e_outofmemory(ctx, FLINE);
+    return 0;
+  }
+  base[n].tab = ret;
+  parent->item = base;
+  parent->nitem++;
+  return ret;
+}
+
+static int skip_newlines(context_t *ctx, int isdotspecial) {
+  while (ctx->tok.tok == NEWLINE) {
+    if (next_token(ctx, isdotspecial))
+      return -1;
+    if (ctx->tok.eof)
+      break;
+  }
+  return 0;
+}
+
+static int parse_keyval(context_t *ctx, toml_table_t *tab);
+
+static inline int eat_token(context_t *ctx, tokentype_t typ, int isdotspecial,
+                            const char *fline) {
+  if (ctx->tok.tok != typ)
+    return e_internal(ctx, fline);
+
+  if (next_token(ctx, isdotspecial))
+    return -1;
+
+  return 0;
+}
+
+/* We are at '{ ... }'.
+ * Parse the table.
+ */
+static int parse_inline_table(context_t *ctx, toml_table_t *tab) {
+  if (eat_token(ctx, LBRACE, 1, FLINE))
+    return -1;
+
+  for (;;) {
+    if (ctx->tok.tok == NEWLINE)
+      return e_syntax(ctx, ctx->tok.lineno,
+                      "newline not allowed in inline table");
+
+    /* until } */
+    if (ctx->tok.tok == RBRACE)
+      break;
+
+    if (ctx->tok.tok != STRING)
+      return e_syntax(ctx, ctx->tok.lineno, "expect a string");
+
+    if (parse_keyval(ctx, tab))
+      return -1;
+
+    if (ctx->tok.tok == NEWLINE)
+      return e_syntax(ctx, ctx->tok.lineno,
+                      "newline not allowed in inline table");
+
+    /* on comma, continue to scan for next keyval */
+    if (ctx->tok.tok == COMMA) {
+      if (eat_token(ctx, COMMA, 1, FLINE))
+        return -1;
+      continue;
+    }
+    break;
+  }
+
+  if (eat_token(ctx, RBRACE, 1, FLINE))
+    return -1;
+
+  tab->readonly = 1;
+
+  return 0;
+}
+
+static int valtype(const char *val) {
+  toml_timestamp_t ts;
+  if (*val == '\'' || *val == '"')
+    return 's';
+  if (0 == toml_rtob(val, 0))
+    return 'b';
+  if (0 == toml_rtoi(val, 0))
+    return 'i';
+  if (0 == toml_rtod(val, 0))
+    return 'd';
+  if (0 == toml_rtots(val, &ts)) {
+    if (ts.year && ts.hour)
+      return 'T'; /* timestamp */
+    if (ts.year)
+      return 'D'; /* date */
+    return 't';   /* time */
+  }
+  return 'u'; /* unknown */
+}
+
+/* We are at '[...]' */
+static int parse_array(context_t *ctx, toml_array_t *arr) {
+  if (eat_token(ctx, LBRACKET, 0, FLINE))
+    return -1;
+
+  for (;;) {
+    if (skip_newlines(ctx, 0))
+      return -1;
+
+    /* until ] */
+    if (ctx->tok.tok == RBRACKET)
+      break;
+
+    switch (ctx->tok.tok) {
+    case STRING: {
+      /* set array kind if this will be the first entry */
+      if (arr->kind == 0)
+        arr->kind = 'v';
+      else if (arr->kind != 'v')
+        arr->kind = 'm';
+
+      char *val = ctx->tok.ptr;
+      int vlen = ctx->tok.len;
+
+      /* make a new value in array */
+      toml_arritem_t *newval = create_value_in_array(ctx, arr);
+      if (!newval)
+        return e_outofmemory(ctx, FLINE);
+
+      if (!(newval->val = STRNDUP(val, vlen)))
+        return e_outofmemory(ctx, FLINE);
+
+      newval->valtype = valtype(newval->val);
+
+      /* set array type if this is the first entry */
+      if (arr->nitem == 1)
+        arr->type = newval->valtype;
+      else if (arr->type != newval->valtype)
+        arr->type = 'm'; /* mixed */
+
+      if (eat_token(ctx, STRING, 0, FLINE))
+        return -1;
+      break;
+    }
+
+    case LBRACKET: { /* [ [array], [array] ... ] */
+      /* set the array kind if this will be the first entry */
+      if (arr->kind == 0)
+        arr->kind = 'a';
+      else if (arr->kind != 'a')
+        arr->kind = 'm';
+
+      toml_array_t *subarr = create_array_in_array(ctx, arr);
+      if (!subarr)
+        return -1;
+      if (parse_array(ctx, subarr))
+        return -1;
+      break;
+    }
+
+    case LBRACE: { /* [ {table}, {table} ... ] */
+      /* set the array kind if this will be the first entry */
+      if (arr->kind == 0)
+        arr->kind = 't';
+      else if (arr->kind != 't')
+        arr->kind = 'm';
+
+      toml_table_t *subtab = create_table_in_array(ctx, arr);
+      if (!subtab)
+        return -1;
+      if (parse_inline_table(ctx, subtab))
+        return -1;
+      break;
+    }
+
+    default:
+      return e_syntax(ctx, ctx->tok.lineno, "syntax error");
+    }
+
+    if (skip_newlines(ctx, 0))
+      return -1;
+
+    /* on comma, continue to scan for next element */
+    if (ctx->tok.tok == COMMA) {
+      if (eat_token(ctx, COMMA, 0, FLINE))
+        return -1;
+      continue;
+    }
+    break;
+  }
+
+  if (eat_token(ctx, RBRACKET, 1, FLINE))
+    return -1;
+  return 0;
+}
+
+/* handle lines like these:
+   key = "value"
+   key = [ array ]
+   key = { table }
+*/
+static int parse_keyval(context_t *ctx, toml_table_t *tab) {
+  if (tab->readonly) {
+    return e_forbid(ctx, ctx->tok.lineno,
+                    "cannot insert new entry into existing table");
+  }
+
+  token_t key = ctx->tok;
+  if (eat_token(ctx, STRING, 1, FLINE))
+    return -1;
+
+  if (ctx->tok.tok == DOT) {
+    /* handle inline dotted key.
+       e.g.
+       physical.color = "orange"
+       physical.shape = "round"
+    */
+    toml_table_t *subtab = 0;
+    {
+      char *subtabstr = normalize_key(ctx, key);
+      if (!subtabstr)
+        return -1;
+
+      subtab = toml_table_in(tab, subtabstr);
+      xfree(subtabstr);
+    }
+    if (!subtab) {
+      subtab = create_keytable_in_table(ctx, tab, key);
+      if (!subtab)
+        return -1;
+    }
+    if (next_token(ctx, 1))
+      return -1;
+    if (parse_keyval(ctx, subtab))
+      return -1;
+    return 0;
+  }
+
+  if (ctx->tok.tok != EQUAL) {
+    return e_syntax(ctx, ctx->tok.lineno, "missing =");
+  }
+
+  if (next_token(ctx, 0))
+    return -1;
+
+  switch (ctx->tok.tok) {
+  case STRING: { /* key = "value" */
+    toml_keyval_t *keyval = create_keyval_in_table(ctx, tab, key);
+    if (!keyval)
+      return -1;
+    token_t val = ctx->tok;
+
+    assert(keyval->val == 0);
+    if (!(keyval->val = STRNDUP(val.ptr, val.len)))
+      return e_outofmemory(ctx, FLINE);
+
+    if (next_token(ctx, 1))
+      return -1;
+
+    return 0;
+  }
+
+  case LBRACKET: { /* key = [ array ] */
+    toml_array_t *arr = create_keyarray_in_table(ctx, tab, key, 0);
+    if (!arr)
+      return -1;
+    if (parse_array(ctx, arr))
+      return -1;
+    return 0;
+  }
+
+  case LBRACE: { /* key = { table } */
+    toml_table_t *nxttab = create_keytable_in_table(ctx, tab, key);
+    if (!nxttab)
+      return -1;
+    if (parse_inline_table(ctx, nxttab))
+      return -1;
+    return 0;
+  }
+
+  default:
+    return e_syntax(ctx, ctx->tok.lineno, "syntax error");
+  }
+  return 0;
+}
+
+typedef struct tabpath_t tabpath_t;
+struct tabpath_t {
+  int cnt;
+  token_t key[10];
+};
+
+/* at [x.y.z] or [[x.y.z]]
+ * Scan forward and fill tabpath until it enters ] or ]]
+ * There will be at least one entry on return.
+ */
+static int fill_tabpath(context_t *ctx) {
+  int lineno = ctx->tok.lineno;
+  int i;
+
+  /* clear tpath */
+  for (i = 0; i < ctx->tpath.top; i++) {
+    char **p = &ctx->tpath.key[i];
+    xfree(*p);
+    *p = 0;
+  }
+  ctx->tpath.top = 0;
+
+  for (;;) {
+    if (ctx->tpath.top >= 10)
+      return e_syntax(ctx, lineno,
+                      "table path is too deep; max allowed is 10.");
+
+    if (ctx->tok.tok != STRING)
+      return e_syntax(ctx, lineno, "invalid or missing key");
+
+    char *key = normalize_key(ctx, ctx->tok);
+    if (!key)
+      return -1;
+    ctx->tpath.tok[ctx->tpath.top] = ctx->tok;
+    ctx->tpath.key[ctx->tpath.top] = key;
+    ctx->tpath.top++;
+
+    if (next_token(ctx, 1))
+      return -1;
+
+    if (ctx->tok.tok == RBRACKET)
+      break;
+
+    if (ctx->tok.tok != DOT)
+      return e_syntax(ctx, lineno, "invalid key");
+
+    if (next_token(ctx, 1))
+      return -1;
+  }
+
+  if (ctx->tpath.top <= 0)
+    return e_syntax(ctx, lineno, "empty table selector");
+
+  return 0;
+}
+
+/* Walk tabpath from the root, and create new tables on the way.
+ * Sets ctx->curtab to the final table.
+ */
+static int walk_tabpath(context_t *ctx) {
+  /* start from root */
+  toml_table_t *curtab = ctx->root;
+
+  for (int i = 0; i < ctx->tpath.top; i++) {
+    const char *key = ctx->tpath.key[i];
+
+    toml_keyval_t *nextval = 0;
+    toml_array_t *nextarr = 0;
+    toml_table_t *nexttab = 0;
+    switch (check_key(curtab, key, &nextval, &nextarr, &nexttab)) {
+    case 't':
+      /* found a table. nexttab is where we will go next. */
+      break;
+
+    case 'a':
+      /* found an array. nexttab is the last table in the array. */
+      if (nextarr->kind != 't')
+        return e_internal(ctx, FLINE);
+
+      if (nextarr->nitem == 0)
+        return e_internal(ctx, FLINE);
+
+      nexttab = nextarr->item[nextarr->nitem - 1].tab;
+      break;
+
+    case 'v':
+      return e_keyexists(ctx, ctx->tpath.tok[i].lineno);
+
+    default: { /* Not found. Let's create an implicit table. */
+      int n = curtab->ntab;
+      toml_table_t **base =
+          (toml_table_t **)expand_ptrarr((void **)curtab->tab, n);
+      if (0 == base)
+        return e_outofmemory(ctx, FLINE);
+
+      curtab->tab = base;
+
+      if (0 == (base[n] = (toml_table_t *)CALLOC(1, sizeof(*base[n]))))
+        return e_outofmemory(ctx, FLINE);
+
+      if (0 == (base[n]->key = STRDUP(key)))
+        return e_outofmemory(ctx, FLINE);
+
+      nexttab = curtab->tab[curtab->ntab++];
+
+      /* tabs created by walk_tabpath are considered implicit */
+      nexttab->implicit = true;
+    } break;
+    }
+
+    /* switch to next tab */
+    curtab = nexttab;
+  }
+
+  /* save it */
+  ctx->curtab = curtab;
+
+  return 0;
+}
+
+/* handle lines like [x.y.z] or [[x.y.z]] */
+static int parse_select(context_t *ctx) {
+  assert(ctx->tok.tok == LBRACKET);
+
+  /* true if [[ */
+  int llb = (ctx->tok.ptr + 1 < ctx->stop && ctx->tok.ptr[1] == '[');
+  /* need to detect '[[' on our own because next_token() will skip whitespace,
+     and '[ [' would be taken as '[[', which is wrong. */
+
+  /* eat [ or [[ */
+  if (eat_token(ctx, LBRACKET, 1, FLINE))
+    return -1;
+  if (llb) {
+    assert(ctx->tok.tok == LBRACKET);
+    if (eat_token(ctx, LBRACKET, 1, FLINE))
+      return -1;
+  }
+
+  if (fill_tabpath(ctx))
+    return -1;
+
+  /* For [x.y.z] or [[x.y.z]], remove z from tpath.
+   */
+  token_t z = ctx->tpath.tok[ctx->tpath.top - 1];
+  xfree(ctx->tpath.key[ctx->tpath.top - 1]);
+  ctx->tpath.top--;
+
+  /* set up ctx->curtab */
+  if (walk_tabpath(ctx))
+    return -1;
+
+  if (!llb) {
+    /* [x.y.z] -> create z = {} in x.y */
+    toml_table_t *curtab = create_keytable_in_table(ctx, ctx->curtab, z);
+    if (!curtab)
+      return -1;
+    ctx->curtab = curtab;
+  } else {
+    /* [[x.y.z]] -> create z = [] in x.y */
+    toml_array_t *arr = 0;
+    {
+      char *zstr = normalize_key(ctx, z);
+      if (!zstr)
+        return -1;
+      arr = toml_array_in(ctx->curtab, zstr);
+      xfree(zstr);
+    }
+    if (!arr) {
+      arr = create_keyarray_in_table(ctx, ctx->curtab, z, 't');
+      if (!arr)
+        return -1;
+    }
+    if (arr->kind != 't')
+      return e_syntax(ctx, z.lineno, "array mismatch");
+
+    /* add to z[] */
+    toml_table_t *dest;
+    {
+      toml_table_t *t = create_table_in_array(ctx, arr);
+      if (!t)
+        return -1;
+
+      if (0 == (t->key = STRDUP("__anon__")))
+        return e_outofmemory(ctx, FLINE);
+
+      dest = t;
+    }
+
+    ctx->curtab = dest;
+  }
+
+  if (ctx->tok.tok != RBRACKET) {
+    return e_syntax(ctx, ctx->tok.lineno, "expects ]");
+  }
+  if (llb) {
+    if (!(ctx->tok.ptr + 1 < ctx->stop && ctx->tok.ptr[1] == ']')) {
+      return e_syntax(ctx, ctx->tok.lineno, "expects ]]");
+    }
+    if (eat_token(ctx, RBRACKET, 1, FLINE))
+      return -1;
+  }
+
+  if (eat_token(ctx, RBRACKET, 1, FLINE))
+    return -1;
+
+  if (ctx->tok.tok != NEWLINE)
+    return e_syntax(ctx, ctx->tok.lineno, "extra chars after ] or ]]");
+
+  return 0;
+}
+
+toml_table_t *toml_parse(char *conf, char *errbuf, int errbufsz) {
+  context_t ctx;
+
+  // clear errbuf
+  if (errbufsz <= 0)
+    errbufsz = 0;
+  if (errbufsz > 0)
+    errbuf[0] = 0;
+
+  // init context
+  memset(&ctx, 0, sizeof(ctx));
+  ctx.start = conf;
+  ctx.stop = ctx.start + strlen(conf);
+  ctx.errbuf = errbuf;
+  ctx.errbufsz = errbufsz;
+
+  // start with an artificial newline of length 0
+  ctx.tok.tok = NEWLINE;
+  ctx.tok.lineno = 1;
+  ctx.tok.ptr = conf;
+  ctx.tok.len = 0;
+
+  // make a root table
+  if (0 == (ctx.root = CALLOC(1, sizeof(*ctx.root)))) {
+    e_outofmemory(&ctx, FLINE);
+    // Do not goto fail, root table not set up yet
+    return 0;
+  }
+
+  // set root as default table
+  ctx.curtab = ctx.root;
+
+  /* Scan forward until EOF */
+  for (token_t tok = ctx.tok; !tok.eof; tok = ctx.tok) {
+    switch (tok.tok) {
+
+    case NEWLINE:
+      if (next_token(&ctx, 1))
+        goto fail;
+      break;
+
+    case STRING:
+      if (parse_keyval(&ctx, ctx.curtab))
+        goto fail;
+
+      if (ctx.tok.tok != NEWLINE) {
+        e_syntax(&ctx, ctx.tok.lineno, "extra chars after value");
+        goto fail;
+      }
+
+      if (eat_token(&ctx, NEWLINE, 1, FLINE))
+        goto fail;
+      break;
+
+    case LBRACKET: /* [ x.y.z ] or [[ x.y.z ]] */
+      if (parse_select(&ctx))
+        goto fail;
+      break;
+
+    default:
+      e_syntax(&ctx, tok.lineno, "syntax error");
+      goto fail;
+    }
+  }
+
+  /* success */
+  for (int i = 0; i < ctx.tpath.top; i++)
+    xfree(ctx.tpath.key[i]);
+  return ctx.root;
+
+fail:
+  // Something bad has happened. Free resources and return error.
+  for (int i = 0; i < ctx.tpath.top; i++)
+    xfree(ctx.tpath.key[i]);
+  toml_free(ctx.root);
+  return 0;
+}
+
+toml_table_t *toml_parse_file(FILE *fp, char *errbuf, int errbufsz) {
+  int bufsz = 0;
+  char *buf = 0;
+  int off = 0;
+
+  /* read from fp into buf */
+  while (!feof(fp)) {
+
+    if (off == bufsz) {
+      int xsz = bufsz + 1000;
+      char *x = expand(buf, bufsz, xsz);
+      if (!x) {
+        snprintf(errbuf, errbufsz, "out of memory");
+        xfree(buf);
+        return 0;
+      }
+      buf = x;
+      bufsz = xsz;
+    }
+
+    errno = 0;
+    int n = fread(buf + off, 1, bufsz - off, fp);
+    if (ferror(fp)) {
+      snprintf(errbuf, errbufsz, "%s",
+               errno ? strerror(errno) : "Error reading file");
+      xfree(buf);
+      return 0;
+    }
+    off += n;
+  }
+
+  /* tag on a NUL to cap the string */
+  if (off == bufsz) {
+    int xsz = bufsz + 1;
+    char *x = expand(buf, bufsz, xsz);
+    if (!x) {
+      snprintf(errbuf, errbufsz, "out of memory");
+      xfree(buf);
+      return 0;
+    }
+    buf = x;
+    bufsz = xsz;
+  }
+  buf[off] = 0;
+
+  /* parse it, cleanup and finish */
+  toml_table_t *ret = toml_parse(buf, errbuf, errbufsz);
+  xfree(buf);
+  return ret;
+}
+
+static void xfree_kval(toml_keyval_t *p) {
+  if (!p)
+    return;
+  xfree(p->key);
+  xfree(p->val);
+  xfree(p);
+}
+
+static void xfree_tab(toml_table_t *p);
+
+static void xfree_arr(toml_array_t *p) {
+  if (!p)
+    return;
+
+  xfree(p->key);
+  const int n = p->nitem;
+  for (int i = 0; i < n; i++) {
+    toml_arritem_t *a = &p->item[i];
+    if (a->val)
+      xfree(a->val);
+    else if (a->arr)
+      xfree_arr(a->arr);
+    else if (a->tab)
+      xfree_tab(a->tab);
+  }
+  xfree(p->item);
+  xfree(p);
+}
+
+static void xfree_tab(toml_table_t *p) {
+  int i;
+
+  if (!p)
+    return;
+
+  xfree(p->key);
+
+  for (i = 0; i < p->nkval; i++)
+    xfree_kval(p->kval[i]);
+  xfree(p->kval);
+
+  for (i = 0; i < p->narr; i++)
+    xfree_arr(p->arr[i]);
+  xfree(p->arr);
+
+  for (i = 0; i < p->ntab; i++)
+    xfree_tab(p->tab[i]);
+  xfree(p->tab);
+
+  xfree(p);
+}
+
+void toml_free(toml_table_t *tab) { xfree_tab(tab); }
+
+static void set_token(context_t *ctx, tokentype_t tok, int lineno, char *ptr,
+                      int len) {
+  token_t t;
+  t.tok = tok;
+  t.lineno = lineno;
+  t.ptr = ptr;
+  t.len = len;
+  t.eof = 0;
+  ctx->tok = t;
+}
+
+static void set_eof(context_t *ctx, int lineno) {
+  set_token(ctx, NEWLINE, lineno, ctx->stop, 0);
+  ctx->tok.eof = 1;
+}
+
+/* Scan p for n digits compositing entirely of [0-9] */
+static int scan_digits(const char *p, int n) {
+  int ret = 0;
+  for (; n > 0 && isdigit(*p); n--, p++) {
+    ret = 10 * ret + (*p - '0');
+  }
+  return n ? -1 : ret;
+}
+
+static int scan_date(const char *p, int *YY, int *MM, int *DD) {
+  int year, month, day;
+  year = scan_digits(p, 4);
+  month = (year >= 0 && p[4] == '-') ? scan_digits(p + 5, 2) : -1;
+  day = (month >= 0 && p[7] == '-') ? scan_digits(p + 8, 2) : -1;
+  if (YY)
+    *YY = year;
+  if (MM)
+    *MM = month;
+  if (DD)
+    *DD = day;
+  return (year >= 0 && month >= 0 && day >= 0) ? 0 : -1;
+}
+
+static int scan_time(const char *p, int *hh, int *mm, int *ss) {
+  int hour, minute, second;
+  hour = scan_digits(p, 2);
+  minute = (hour >= 0 && p[2] == ':') ? scan_digits(p + 3, 2) : -1;
+  second = (minute >= 0 && p[5] == ':') ? scan_digits(p + 6, 2) : -1;
+  if (hh)
+    *hh = hour;
+  if (mm)
+    *mm = minute;
+  if (ss)
+    *ss = second;
+  return (hour >= 0 && minute >= 0 && second >= 0) ? 0 : -1;
+}
+
+static int scan_string(context_t *ctx, char *p, int lineno, int dotisspecial) {
+  char *orig = p;
+  if (0 == strncmp(p, "'''", 3)) {
+    char *q = p + 3;
+
+    while (1) {
+      q = strstr(q, "'''");
+      if (0 == q) {
+        return e_syntax(ctx, lineno, "unterminated triple-s-quote");
+      }
+      while (q[3] == '\'')
+        q++;
+      break;
+    }
+
+    set_token(ctx, STRING, lineno, orig, q + 3 - orig);
+    return 0;
+  }
+
+  if (0 == strncmp(p, "\"\"\"", 3)) {
+    char *q = p + 3;
+
+    while (1) {
+      q = strstr(q, "\"\"\"");
+      if (0 == q) {
+        return e_syntax(ctx, lineno, "unterminated triple-d-quote");
+      }
+      if (q[-1] == '\\') {
+        q++;
+        continue;
+      }
+      while (q[3] == '\"')
+        q++;
+      break;
+    }
+
+    // the string is [p+3, q-1]
+
+    int hexreq = 0; /* #hex required */
+    int escape = 0;
+    for (p += 3; p < q; p++) {
+      if (escape) {
+        escape = 0;
+        if (strchr("btnfr\"\\", *p))
+          continue;
+        if (*p == 'u') {
+          hexreq = 4;
+          continue;
+        }
+        if (*p == 'U') {
+          hexreq = 8;
+          continue;
+        }
+        if (p[strspn(p, " \t\r")] == '\n')
+          continue; /* allow for line ending backslash */
+        return e_syntax(ctx, lineno, "bad escape char");
+      }
+      if (hexreq) {
+        hexreq--;
+        if (strchr("0123456789ABCDEF", *p))
+          continue;
+        return e_syntax(ctx, lineno, "expect hex char");
+      }
+      if (*p == '\\') {
+        escape = 1;
+        continue;
+      }
+    }
+    if (escape)
+      return e_syntax(ctx, lineno, "expect an escape char");
+    if (hexreq)
+      return e_syntax(ctx, lineno, "expected more hex char");
+
+    set_token(ctx, STRING, lineno, orig, q + 3 - orig);
+    return 0;
+  }
+
+  if ('\'' == *p) {
+    for (p++; *p && *p != '\n' && *p != '\''; p++)
+      ;
+    if (*p != '\'') {
+      return e_syntax(ctx, lineno, "unterminated s-quote");
+    }
+
+    set_token(ctx, STRING, lineno, orig, p + 1 - orig);
+    return 0;
+  }
+
+  if ('\"' == *p) {
+    int hexreq = 0; /* #hex required */
+    int escape = 0;
+    for (p++; *p; p++) {
+      if (escape) {
+        escape = 0;
+        if (strchr("btnfr\"\\", *p))
+          continue;
+        if (*p == 'u') {
+          hexreq = 4;
+          continue;
+        }
+        if (*p == 'U') {
+          hexreq = 8;
+          continue;
+        }
+        return e_syntax(ctx, lineno, "bad escape char");
+      }
+      if (hexreq) {
+        hexreq--;
+        if (strchr("0123456789ABCDEF", *p))
+          continue;
+        return e_syntax(ctx, lineno, "expect hex char");
+      }
+      if (*p == '\\') {
+        escape = 1;
+        continue;
+      }
+      if (*p == '\'') {
+        if (p[1] == '\'' && p[2] == '\'') {
+          return e_syntax(ctx, lineno, "triple-s-quote inside string lit");
+        }
+        continue;
+      }
+      if (*p == '\n')
+        break;
+      if (*p == '"')
+        break;
+    }
+    if (*p != '"') {
+      return e_syntax(ctx, lineno, "unterminated quote");
+    }
+
+    set_token(ctx, STRING, lineno, orig, p + 1 - orig);
+    return 0;
+  }
+
+  /* check for timestamp without quotes */
+  if (0 == scan_date(p, 0, 0, 0) || 0 == scan_time(p, 0, 0, 0)) {
+    // forward thru the timestamp
+    p += strspn(p, "0123456789.:+-T Z");
+    // squeeze out any spaces at end of string
+    for (; p[-1] == ' '; p--)
+      ;
+    // tokenize
+    set_token(ctx, STRING, lineno, orig, p - orig);
+    return 0;
+  }
+
+  /* literals */
+  for (; *p && *p != '\n'; p++) {
+    int ch = *p;
+    if (ch == '.' && dotisspecial)
+      break;
+    if ('A' <= ch && ch <= 'Z')
+      continue;
+    if ('a' <= ch && ch <= 'z')
+      continue;
+    if (strchr("0123456789+-_.", ch))
+      continue;
+    break;
+  }
+
+  set_token(ctx, STRING, lineno, orig, p - orig);
+  return 0;
+}
+
+static int next_token(context_t *ctx, int dotisspecial) {
+  int lineno = ctx->tok.lineno;
+  char *p = ctx->tok.ptr;
+  int i;
+
+  /* eat this tok */
+  for (i = 0; i < ctx->tok.len; i++) {
+    if (*p++ == '\n')
+      lineno++;
+  }
+
+  /* make next tok */
+  while (p < ctx->stop) {
+    /* skip comment. stop just before the \n. */
+    if (*p == '#') {
+      for (p++; p < ctx->stop && *p != '\n'; p++)
+        ;
+      continue;
+    }
+
+    if (dotisspecial && *p == '.') {
+      set_token(ctx, DOT, lineno, p, 1);
+      return 0;
+    }
+
+    switch (*p) {
+    case ',':
+      set_token(ctx, COMMA, lineno, p, 1);
+      return 0;
+    case '=':
+      set_token(ctx, EQUAL, lineno, p, 1);
+      return 0;
+    case '{':
+      set_token(ctx, LBRACE, lineno, p, 1);
+      return 0;
+    case '}':
+      set_token(ctx, RBRACE, lineno, p, 1);
+      return 0;
+    case '[':
+      set_token(ctx, LBRACKET, lineno, p, 1);
+      return 0;
+    case ']':
+      set_token(ctx, RBRACKET, lineno, p, 1);
+      return 0;
+    case '\n':
+      set_token(ctx, NEWLINE, lineno, p, 1);
+      return 0;
+    case '\r':
+    case ' ':
+    case '\t':
+      /* ignore white spaces */
+      p++;
+      continue;
+    }
+
+    return scan_string(ctx, p, lineno, dotisspecial);
+  }
+
+  set_eof(ctx, lineno);
+  return 0;
+}
+
+const char *toml_key_in(const toml_table_t *tab, int keyidx) {
+  if (keyidx < tab->nkval)
+    return tab->kval[keyidx]->key;
+
+  keyidx -= tab->nkval;
+  if (keyidx < tab->narr)
+    return tab->arr[keyidx]->key;
+
+  keyidx -= tab->narr;
+  if (keyidx < tab->ntab)
+    return tab->tab[keyidx]->key;
+
+  return 0;
+}
+
+int toml_key_exists(const toml_table_t *tab, const char *key) {
+  int i;
+  for (i = 0; i < tab->nkval; i++) {
+    if (0 == strcmp(key, tab->kval[i]->key))
+      return 1;
+  }
+  for (i = 0; i < tab->narr; i++) {
+    if (0 == strcmp(key, tab->arr[i]->key))
+      return 1;
+  }
+  for (i = 0; i < tab->ntab; i++) {
+    if (0 == strcmp(key, tab->tab[i]->key))
+      return 1;
+  }
+  return 0;
+}
+
+toml_raw_t toml_raw_in(const toml_table_t *tab, const char *key) {
+  int i;
+  for (i = 0; i < tab->nkval; i++) {
+    if (0 == strcmp(key, tab->kval[i]->key))
+      return tab->kval[i]->val;
+  }
+  return 0;
+}
+
+toml_array_t *toml_array_in(const toml_table_t *tab, const char *key) {
+  int i;
+  for (i = 0; i < tab->narr; i++) {
+    if (0 == strcmp(key, tab->arr[i]->key))
+      return tab->arr[i];
+  }
+  return 0;
+}
+
+toml_table_t *toml_table_in(const toml_table_t *tab, const char *key) {
+  int i;
+  for (i = 0; i < tab->ntab; i++) {
+    if (0 == strcmp(key, tab->tab[i]->key))
+      return tab->tab[i];
+  }
+  return 0;
+}
+
+toml_raw_t toml_raw_at(const toml_array_t *arr, int idx) {
+  return (0 <= idx && idx < arr->nitem) ? arr->item[idx].val : 0;
+}
+
+char toml_array_kind(const toml_array_t *arr) { return arr->kind; }
+
+char toml_array_type(const toml_array_t *arr) {
+  if (arr->kind != 'v')
+    return 0;
+
+  if (arr->nitem == 0)
+    return 0;
+
+  return arr->type;
+}
+
+int toml_array_nelem(const toml_array_t *arr) { return arr->nitem; }
+
+const char *toml_array_key(const toml_array_t *arr) {
+  return arr ? arr->key : (const char *)NULL;
+}
+
+int toml_table_nkval(const toml_table_t *tab) { return tab->nkval; }
+
+int toml_table_narr(const toml_table_t *tab) { return tab->narr; }
+
+int toml_table_ntab(const toml_table_t *tab) { return tab->ntab; }
+
+const char *toml_table_key(const toml_table_t *tab) {
+  return tab ? tab->key : (const char *)NULL;
+}
+
+toml_array_t *toml_array_at(const toml_array_t *arr, int idx) {
+  return (0 <= idx && idx < arr->nitem) ? arr->item[idx].arr : 0;
+}
+
+toml_table_t *toml_table_at(const toml_array_t *arr, int idx) {
+  return (0 <= idx && idx < arr->nitem) ? arr->item[idx].tab : 0;
+}
+
+static int parse_millisec(const char *p, const char **endp);
+
+int toml_rtots(toml_raw_t src_, toml_timestamp_t *ret) {
+  if (!src_)
+    return -1;
+
+  const char *p = src_;
+  int must_parse_time = 0;
+
+  memset(ret, 0, sizeof(*ret));
+
+  int *year = &ret->__buffer.year;
+  int *month = &ret->__buffer.month;
+  int *day = &ret->__buffer.day;
+  int *hour = &ret->__buffer.hour;
+  int *minute = &ret->__buffer.minute;
+  int *second = &ret->__buffer.second;
+  int *millisec = &ret->__buffer.millisec;
+
+  /* parse date YYYY-MM-DD */
+  if (0 == scan_date(p, year, month, day)) {
+    ret->year = year;
+    ret->month = month;
+    ret->day = day;
+
+    p += 10;
+    if (*p) {
+      // parse the T or space separator
+      if (*p != 'T' && *p != ' ')
+        return -1;
+      must_parse_time = 1;
+      p++;
+    }
+  }
+
+  /* parse time HH:MM:SS */
+  if (0 == scan_time(p, hour, minute, second)) {
+    ret->hour = hour;
+    ret->minute = minute;
+    ret->second = second;
+
+    /* optionally, parse millisec */
+    p += 8;
+    if (*p == '.') {
+      p++; /* skip '.' */
+      const char *qq;
+      *millisec = parse_millisec(p, &qq);
+      ret->millisec = millisec;
+      p = qq;
+    }
+
+    if (*p) {
+      /* parse and copy Z */
+      char *z = ret->__buffer.z;
+      ret->z = z;
+      if (*p == 'Z' || *p == 'z') {
+        *z++ = 'Z';
+        p++;
+        *z = 0;
+
+      } else if (*p == '+' || *p == '-') {
+        *z++ = *p++;
+
+        if (!(isdigit(p[0]) && isdigit(p[1])))
+          return -1;
+        *z++ = *p++;
+        *z++ = *p++;
+
+        if (*p == ':') {
+          *z++ = *p++;
+
+          if (!(isdigit(p[0]) && isdigit(p[1])))
+            return -1;
+          *z++ = *p++;
+          *z++ = *p++;
+        }
+
+        *z = 0;
+      }
+    }
+  }
+  if (*p != 0)
+    return -1;
+
+  if (must_parse_time && !ret->hour)
+    return -1;
+
+  return 0;
+}
+
+/* Raw to boolean */
+int toml_rtob(toml_raw_t src, int *ret_) {
+  if (!src)
+    return -1;
+  int dummy;
+  int *ret = ret_ ? ret_ : &dummy;
+
+  if (0 == strcmp(src, "true")) {
+    *ret = 1;
+    return 0;
+  }
+  if (0 == strcmp(src, "false")) {
+    *ret = 0;
+    return 0;
+  }
+  return -1;
+}
+
+/* Raw to integer */
+int toml_rtoi(toml_raw_t src, int64_t *ret_) {
+  if (!src)
+    return -1;
+
+  char buf[100];
+  char *p = buf;
+  char *q = p + sizeof(buf);
+  const char *s = src;
+  int base = 0;
+  int64_t dummy;
+  int64_t *ret = ret_ ? ret_ : &dummy;
+
+  /* allow +/- */
+  if (s[0] == '+' || s[0] == '-')
+    *p++ = *s++;
+
+  /* disallow +_100 */
+  if (s[0] == '_')
+    return -1;
+
+  /* if 0* ... */
+  if ('0' == s[0]) {
+    switch (s[1]) {
+    case 'x':
+      base = 16;
+      s += 2;
+      break;
+    case 'o':
+      base = 8;
+      s += 2;
+      break;
+    case 'b':
+      base = 2;
+      s += 2;
+      break;
+    case '\0':
+      return *ret = 0, 0;
+    default:
+      /* ensure no other digits after it */
+      if (s[1])
+        return -1;
+    }
+  }
+
+  /* just strip underscores and pass to strtoll */
+  while (*s && p < q) {
+    int ch = *s++;
+    if (ch == '_') {
+      // disallow '__'
+      if (s[0] == '_')
+        return -1;
+      // numbers cannot end with '_'
+      if (s[0] == '\0')
+        return -1;
+      continue; /* skip _ */
+    }
+    *p++ = ch;
+  }
+
+  // if not at end-of-string or we ran out of buffer ...
+  if (*s || p == q)
+    return -1;
+
+  /* cap with NUL */
+  *p = 0;
+
+  /* Run strtoll on buf to get the integer */
+  char *endp;
+  errno = 0;
+  *ret = strtoll(buf, &endp, base);
+  return (errno || *endp) ? -1 : 0;
+}
+
+int toml_rtod_ex(toml_raw_t src, double *ret_, char *buf, int buflen) {
+  if (!src)
+    return -1;
+
+  char *p = buf;
+  char *q = p + buflen;
+  const char *s = src;
+  double dummy;
+  double *ret = ret_ ? ret_ : &dummy;
+
+  /* allow +/- */
+  if (s[0] == '+' || s[0] == '-')
+    *p++ = *s++;
+
+  /* disallow +_1.00 */
+  if (s[0] == '_')
+    return -1;
+
+  /* decimal point, if used, must be surrounded by at least one digit on each
+   * side */
+  {
+    char *dot = strchr(s, '.');
+    if (dot) {
+      if (dot == s || !isdigit(dot[-1]) || !isdigit(dot[1]))
+        return -1;
+    }
+  }
+
+  /* zero must be followed by . or 'e', or NUL */
+  if (s[0] == '0' && s[1] && !strchr("eE.", s[1]))
+    return -1;
+
+  /* just strip underscores and pass to strtod */
+  while (*s && p < q) {
+    int ch = *s++;
+    if (ch == '_') {
+      // disallow '__'
+      if (s[0] == '_')
+        return -1;
+      // disallow last char '_'
+      if (s[0] == 0)
+        return -1;
+      continue; /* skip _ */
+    }
+    *p++ = ch;
+  }
+  if (*s || p == q)
+    return -1; /* reached end of string or buffer is full? */
+
+  /* cap with NUL */
+  *p = 0;
+
+  /* Run strtod on buf to get the value */
+  char *endp;
+  errno = 0;
+  *ret = strtod(buf, &endp);
+  return (errno || *endp) ? -1 : 0;
+}
+
+int toml_rtod(toml_raw_t src, double *ret_) {
+  char buf[100];
+  return toml_rtod_ex(src, ret_, buf, sizeof(buf));
+}
+
+int toml_rtos(toml_raw_t src, char **ret) {
+  int multiline = 0;
+  const char *sp;
+  const char *sq;
+
+  *ret = 0;
+  if (!src)
+    return -1;
+
+  int qchar = src[0];
+  int srclen = strlen(src);
+  if (!(qchar == '\'' || qchar == '"')) {
+    return -1;
+  }
+
+  // triple quotes?
+  if (qchar == src[1] && qchar == src[2]) {
+    multiline = 1;
+    sp = src + 3;
+    sq = src + srclen - 3;
+    /* last 3 chars in src must be qchar */
+    if (!(sp <= sq && sq[0] == qchar && sq[1] == qchar && sq[2] == qchar))
+      return -1;
+
+    /* skip new line immediate after qchar */
+    if (sp[0] == '\n')
+      sp++;
+    else if (sp[0] == '\r' && sp[1] == '\n')
+      sp += 2;
+
+  } else {
+    sp = src + 1;
+    sq = src + srclen - 1;
+    /* last char in src must be qchar */
+    if (!(sp <= sq && *sq == qchar))
+      return -1;
+  }
+
+  if (qchar == '\'') {
+    *ret = norm_lit_str(sp, sq - sp, multiline, 0, 0);
+  } else {
+    *ret = norm_basic_str(sp, sq - sp, multiline, 0, 0);
+  }
+
+  return *ret ? 0 : -1;
+}
+
+toml_datum_t toml_string_at(const toml_array_t *arr, int idx) {
+  toml_datum_t ret;
+  memset(&ret, 0, sizeof(ret));
+  ret.ok = (0 == toml_rtos(toml_raw_at(arr, idx), &ret.u.s));
+  return ret;
+}
+
+toml_datum_t toml_bool_at(const toml_array_t *arr, int idx) {
+  toml_datum_t ret;
+  memset(&ret, 0, sizeof(ret));
+  ret.ok = (0 == toml_rtob(toml_raw_at(arr, idx), &ret.u.b));
+  return ret;
+}
+
+toml_datum_t toml_int_at(const toml_array_t *arr, int idx) {
+  toml_datum_t ret;
+  memset(&ret, 0, sizeof(ret));
+  ret.ok = (0 == toml_rtoi(toml_raw_at(arr, idx), &ret.u.i));
+  return ret;
+}
+
+toml_datum_t toml_double_at(const toml_array_t *arr, int idx) {
+  toml_datum_t ret;
+  memset(&ret, 0, sizeof(ret));
+  ret.ok = (0 == toml_rtod(toml_raw_at(arr, idx), &ret.u.d));
+  return ret;
+}
+
+toml_datum_t toml_timestamp_at(const toml_array_t *arr, int idx) {
+  toml_timestamp_t ts;
+  toml_datum_t ret;
+  memset(&ret, 0, sizeof(ret));
+  ret.ok = (0 == toml_rtots(toml_raw_at(arr, idx), &ts));
+  if (ret.ok) {
+    ret.ok = !!(ret.u.ts = MALLOC(sizeof(*ret.u.ts)));
+    if (ret.ok) {
+      *ret.u.ts = ts;
+      if (ret.u.ts->year)
+        ret.u.ts->year = &ret.u.ts->__buffer.year;
+      if (ret.u.ts->month)
+        ret.u.ts->month = &ret.u.ts->__buffer.month;
+      if (ret.u.ts->day)
+        ret.u.ts->day = &ret.u.ts->__buffer.day;
+      if (ret.u.ts->hour)
+        ret.u.ts->hour = &ret.u.ts->__buffer.hour;
+      if (ret.u.ts->minute)
+        ret.u.ts->minute = &ret.u.ts->__buffer.minute;
+      if (ret.u.ts->second)
+        ret.u.ts->second = &ret.u.ts->__buffer.second;
+      if (ret.u.ts->millisec)
+        ret.u.ts->millisec = &ret.u.ts->__buffer.millisec;
+      if (ret.u.ts->z)
+        ret.u.ts->z = ret.u.ts->__buffer.z;
+    }
+  }
+  return ret;
+}
+
+toml_datum_t toml_string_in(const toml_table_t *arr, const char *key) {
+  toml_datum_t ret;
+  memset(&ret, 0, sizeof(ret));
+  toml_raw_t raw = toml_raw_in(arr, key);
+  if (raw) {
+    ret.ok = (0 == toml_rtos(raw, &ret.u.s));
+  }
+  return ret;
+}
+
+toml_datum_t toml_bool_in(const toml_table_t *arr, const char *key) {
+  toml_datum_t ret;
+  memset(&ret, 0, sizeof(ret));
+  ret.ok = (0 == toml_rtob(toml_raw_in(arr, key), &ret.u.b));
+  return ret;
+}
+
+toml_datum_t toml_int_in(const toml_table_t *arr, const char *key) {
+  toml_datum_t ret;
+  memset(&ret, 0, sizeof(ret));
+  ret.ok = (0 == toml_rtoi(toml_raw_in(arr, key), &ret.u.i));
+  return ret;
+}
+
+toml_datum_t toml_double_in(const toml_table_t *arr, const char *key) {
+  toml_datum_t ret;
+  memset(&ret, 0, sizeof(ret));
+  ret.ok = (0 == toml_rtod(toml_raw_in(arr, key), &ret.u.d));
+  return ret;
+}
+
+toml_datum_t toml_timestamp_in(const toml_table_t *arr, const char *key) {
+  toml_timestamp_t ts;
+  toml_datum_t ret;
+  memset(&ret, 0, sizeof(ret));
+  ret.ok = (0 == toml_rtots(toml_raw_in(arr, key), &ts));
+  if (ret.ok) {
+    ret.ok = !!(ret.u.ts = MALLOC(sizeof(*ret.u.ts)));
+    if (ret.ok) {
+      *ret.u.ts = ts;
+      if (ret.u.ts->year)
+        ret.u.ts->year = &ret.u.ts->__buffer.year;
+      if (ret.u.ts->month)
+        ret.u.ts->month = &ret.u.ts->__buffer.month;
+      if (ret.u.ts->day)
+        ret.u.ts->day = &ret.u.ts->__buffer.day;
+      if (ret.u.ts->hour)
+        ret.u.ts->hour = &ret.u.ts->__buffer.hour;
+      if (ret.u.ts->minute)
+        ret.u.ts->minute = &ret.u.ts->__buffer.minute;
+      if (ret.u.ts->second)
+        ret.u.ts->second = &ret.u.ts->__buffer.second;
+      if (ret.u.ts->millisec)
+        ret.u.ts->millisec = &ret.u.ts->__buffer.millisec;
+      if (ret.u.ts->z)
+        ret.u.ts->z = ret.u.ts->__buffer.z;
+    }
+  }
+  return ret;
+}
+
+static int parse_millisec(const char *p, const char **endp) {
+  int ret = 0;
+  int unit = 100; /* unit in millisec */
+  for (; '0' <= *p && *p <= '9'; p++, unit /= 10) {
+    ret += (*p - '0') * unit;
+  }
+  *endp = p;
+  return ret;
+}
diff --git a/deps/toml/toml.h b/deps/toml/toml.h
new file mode 100644
index 0000000..19dc3d2
--- /dev/null
+++ b/deps/toml/toml.h
@@ -0,0 +1,175 @@
+/*
+  MIT License
+
+  Copyright (c) CK Tan
+  https://github.com/cktan/tomlc99
+
+  Permission is hereby granted, free of charge, to any person obtaining a copy
+  of this software and associated documentation files (the "Software"), to deal
+  in the Software without restriction, including without limitation the rights
+  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+  copies of the Software, and to permit persons to whom the Software is
+  furnished to do so, subject to the following conditions:
+
+  The above copyright notice and this permission notice shall be included in all
+  copies or substantial portions of the Software.
+
+  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+  SOFTWARE.
+*/
+#ifndef TOML_H
+#define TOML_H
+
+#ifdef _MSC_VER
+#pragma warning(disable: 4996)
+#endif
+
+#include <stdint.h>
+#include <stdio.h>
+
+#ifdef __cplusplus
+#define TOML_EXTERN extern "C"
+#else
+#define TOML_EXTERN extern
+#endif
+
+typedef struct toml_timestamp_t toml_timestamp_t;
+typedef struct toml_table_t toml_table_t;
+typedef struct toml_array_t toml_array_t;
+typedef struct toml_datum_t toml_datum_t;
+
+/* Parse a file. Return a table on success, or 0 otherwise.
+ * Caller must toml_free(the-return-value) after use.
+ */
+TOML_EXTERN toml_table_t *toml_parse_file(FILE *fp, char *errbuf, int errbufsz);
+
+/* Parse a string containing the full config.
+ * Return a table on success, or 0 otherwise.
+ * Caller must toml_free(the-return-value) after use.
+ */
+TOML_EXTERN toml_table_t *toml_parse(char *conf, /* NUL terminated, please. */
+                                     char *errbuf, int errbufsz);
+
+/* Free the table returned by toml_parse() or toml_parse_file(). Once
+ * this function is called, any handles accessed through this tab
+ * directly or indirectly are no longer valid.
+ */
+TOML_EXTERN void toml_free(toml_table_t *tab);
+
+/* Timestamp types. The year, month, day, hour, minute, second, z
+ * fields may be NULL if they are not relevant. e.g. In a DATE
+ * type, the hour, minute, second and z fields will be NULLs.
+ */
+struct toml_timestamp_t {
+  struct { /* internal. do not use. */
+    int year, month, day;
+    int hour, minute, second, millisec;
+    char z[10];
+  } __buffer;
+  int *year, *month, *day;
+  int *hour, *minute, *second, *millisec;
+  char *z;
+};
+
+/*-----------------------------------------------------------------
+ *  Enhanced access methods
+ */
+struct toml_datum_t {
+  int ok;
+  union {
+    toml_timestamp_t *ts; /* ts must be freed after use */
+    char *s;              /* string value. s must be freed after use */
+    int b;                /* bool value */
+    int64_t i;            /* int value */
+    double d;             /* double value */
+  } u;
+};
+
+/* on arrays: */
+/* ... retrieve size of array. */
+TOML_EXTERN int toml_array_nelem(const toml_array_t *arr);
+/* ... retrieve values using index. */
+TOML_EXTERN toml_datum_t toml_string_at(const toml_array_t *arr, int idx);
+TOML_EXTERN toml_datum_t toml_bool_at(const toml_array_t *arr, int idx);
+TOML_EXTERN toml_datum_t toml_int_at(const toml_array_t *arr, int idx);
+TOML_EXTERN toml_datum_t toml_double_at(const toml_array_t *arr, int idx);
+TOML_EXTERN toml_datum_t toml_timestamp_at(const toml_array_t *arr, int idx);
+/* ... retrieve array or table using index. */
+TOML_EXTERN toml_array_t *toml_array_at(const toml_array_t *arr, int idx);
+TOML_EXTERN toml_table_t *toml_table_at(const toml_array_t *arr, int idx);
+
+/* on tables: */
+/* ... retrieve the key in table at keyidx. Return 0 if out of range. */
+TOML_EXTERN const char *toml_key_in(const toml_table_t *tab, int keyidx);
+/* ... returns 1 if key exists in tab, 0 otherwise */
+TOML_EXTERN int toml_key_exists(const toml_table_t *tab, const char *key);
+/* ... retrieve values using key. */
+TOML_EXTERN toml_datum_t toml_string_in(const toml_table_t *arr,
+                                        const char *key);
+TOML_EXTERN toml_datum_t toml_bool_in(const toml_table_t *arr, const char *key);
+TOML_EXTERN toml_datum_t toml_int_in(const toml_table_t *arr, const char *key);
+TOML_EXTERN toml_datum_t toml_double_in(const toml_table_t *arr,
+                                        const char *key);
+TOML_EXTERN toml_datum_t toml_timestamp_in(const toml_table_t *arr,
+                                           const char *key);
+/* .. retrieve array or table using key. */
+TOML_EXTERN toml_array_t *toml_array_in(const toml_table_t *tab,
+                                        const char *key);
+TOML_EXTERN toml_table_t *toml_table_in(const toml_table_t *tab,
+                                        const char *key);
+
+/*-----------------------------------------------------------------
+ * lesser used
+ */
+/* Return the array kind: 't'able, 'a'rray, 'v'alue, 'm'ixed */
+TOML_EXTERN char toml_array_kind(const toml_array_t *arr);
+
+/* For array kind 'v'alue, return the type of values
+   i:int, d:double, b:bool, s:string, t:time, D:date, T:timestamp, 'm'ixed
+   0 if unknown
+*/
+TOML_EXTERN char toml_array_type(const toml_array_t *arr);
+
+/* Return the key of an array */
+TOML_EXTERN const char *toml_array_key(const toml_array_t *arr);
+
+/* Return the number of key-values in a table */
+TOML_EXTERN int toml_table_nkval(const toml_table_t *tab);
+
+/* Return the number of arrays in a table */
+TOML_EXTERN int toml_table_narr(const toml_table_t *tab);
+
+/* Return the number of sub-tables in a table */
+TOML_EXTERN int toml_table_ntab(const toml_table_t *tab);
+
+/* Return the key of a table*/
+TOML_EXTERN const char *toml_table_key(const toml_table_t *tab);
+
+/*--------------------------------------------------------------
+ * misc
+ */
+TOML_EXTERN int toml_utf8_to_ucs(const char *orig, int len, int64_t *ret);
+TOML_EXTERN int toml_ucs_to_utf8(int64_t code, char buf[6]);
+TOML_EXTERN void toml_set_memutil(void *(*xxmalloc)(size_t),
+                                  void (*xxfree)(void *));
+
+/*--------------------------------------------------------------
+ *  deprecated
+ */
+/* A raw value, must be processed by toml_rto* before using. */
+typedef const char *toml_raw_t;
+TOML_EXTERN toml_raw_t toml_raw_in(const toml_table_t *tab, const char *key);
+TOML_EXTERN toml_raw_t toml_raw_at(const toml_array_t *arr, int idx);
+TOML_EXTERN int toml_rtos(toml_raw_t s, char **ret);
+TOML_EXTERN int toml_rtob(toml_raw_t s, int *ret);
+TOML_EXTERN int toml_rtoi(toml_raw_t s, int64_t *ret);
+TOML_EXTERN int toml_rtod(toml_raw_t s, double *ret);
+TOML_EXTERN int toml_rtod_ex(toml_raw_t s, double *ret, char *buf, int buflen);
+TOML_EXTERN int toml_rtots(toml_raw_t s, toml_timestamp_t *ret);
+
+#endif /* TOML_H */
diff --git a/deps/uthash/uthash.h b/deps/uthash/uthash.h
new file mode 100644
index 0000000..5e5866a
--- /dev/null
+++ b/deps/uthash/uthash.h
@@ -0,0 +1,1150 @@
+/*
+Copyright (c) 2003-2018, Troy D. Hanson     http://troydhanson.github.com/uthash/
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+    * Redistributions of source code must retain the above copyright
+      notice, this list of conditions and the following disclaimer.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
+IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
+OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#ifndef UTHASH_H
+#define UTHASH_H
+
+#define UTHASH_VERSION 2.1.0
+
+#include <string.h>   /* memcmp, memset, strlen */
+#include <stddef.h>   /* ptrdiff_t */
+#include <stdlib.h>   /* exit */
+
+/* These macros use decltype or the earlier __typeof GNU extension.
+   As decltype is only available in newer compilers (VS2010 or gcc 4.3+
+   when compiling c++ source) this code uses whatever method is needed
+   or, for VS2008 where neither is available, uses casting workarounds. */
+#if !defined(DECLTYPE) && !defined(NO_DECLTYPE)
+#if defined(_MSC_VER)   /* MS compiler */
+#if _MSC_VER >= 1600 && defined(__cplusplus)  /* VS2010 or newer in C++ mode */
+#define DECLTYPE(x) (decltype(x))
+#else                   /* VS2008 or older (or VS2010 in C mode) */
+#define NO_DECLTYPE
+#endif
+#elif defined(__BORLANDC__) || defined(__ICCARM__) || defined(__LCC__) || defined(__WATCOMC__)
+#define NO_DECLTYPE
+#else                   /* GNU, Sun and other compilers */
+#define DECLTYPE(x) (__typeof(x))
+#endif
+#endif
+
+#ifdef NO_DECLTYPE
+#define DECLTYPE(x)
+#define DECLTYPE_ASSIGN(dst,src)                                                 \
+do {                                                                             \
+  char **_da_dst = (char**)(&(dst));                                             \
+  *_da_dst = (char*)(src);                                                       \
+} while (0)
+#else
+#define DECLTYPE_ASSIGN(dst,src)                                                 \
+do {                                                                             \
+  (dst) = DECLTYPE(dst)(src);                                                    \
+} while (0)
+#endif
+
+/* a number of the hash function use uint32_t which isn't defined on Pre VS2010 */
+#if defined(_WIN32)
+#if defined(_MSC_VER) && _MSC_VER >= 1600
+#include <stdint.h>
+#elif defined(__WATCOMC__) || defined(__MINGW32__) || defined(__CYGWIN__)
+#include <stdint.h>
+#else
+typedef unsigned int uint32_t;
+typedef unsigned char uint8_t;
+#endif
+#elif defined(__GNUC__) && !defined(__VXWORKS__)
+#include <stdint.h>
+#else
+typedef unsigned int uint32_t;
+typedef unsigned char uint8_t;
+#endif
+
+#ifndef uthash_malloc
+#define uthash_malloc(sz) malloc(sz)      /* malloc fcn                      */
+#endif
+#ifndef uthash_free
+#define uthash_free(ptr,sz) free(ptr)     /* free fcn                        */
+#endif
+#ifndef uthash_bzero
+#define uthash_bzero(a,n) memset(a,'\0',n)
+#endif
+#ifndef uthash_strlen
+#define uthash_strlen(s) strlen(s)
+#endif
+
+#ifdef uthash_memcmp
+/* This warning will not catch programs that define uthash_memcmp AFTER including uthash.h. */
+#warning "uthash_memcmp is deprecated; please use HASH_KEYCMP instead"
+#else
+#define uthash_memcmp(a,b,n) memcmp(a,b,n)
+#endif
+
+#ifndef HASH_KEYCMP
+#define HASH_KEYCMP(a,b,n) uthash_memcmp(a,b,n)
+#endif
+
+#ifndef uthash_noexpand_fyi
+#define uthash_noexpand_fyi(tbl)          /* can be defined to log noexpand  */
+#endif
+#ifndef uthash_expand_fyi
+#define uthash_expand_fyi(tbl)            /* can be defined to log expands   */
+#endif
+
+#ifndef HASH_NONFATAL_OOM
+#define HASH_NONFATAL_OOM 0
+#endif
+
+#if HASH_NONFATAL_OOM
+/* malloc failures can be recovered from */
+
+#ifndef uthash_nonfatal_oom
+#define uthash_nonfatal_oom(obj) do {} while (0)    /* non-fatal OOM error */
+#endif
+
+#define HASH_RECORD_OOM(oomed) do { (oomed) = 1; } while (0)
+#define IF_HASH_NONFATAL_OOM(x) x
+
+#else
+/* malloc failures result in lost memory, hash tables are unusable */
+
+#ifndef uthash_fatal
+#define uthash_fatal(msg) exit(-1)        /* fatal OOM error */
+#endif
+
+#define HASH_RECORD_OOM(oomed) uthash_fatal("out of memory")
+#define IF_HASH_NONFATAL_OOM(x)
+
+#endif
+
+/* initial number of buckets */
+#define HASH_INITIAL_NUM_BUCKETS 32U     /* initial number of buckets        */
+#define HASH_INITIAL_NUM_BUCKETS_LOG2 5U /* lg2 of initial number of buckets */
+#define HASH_BKT_CAPACITY_THRESH 10U     /* expand when bucket count reaches */
+
+/* calculate the element whose hash handle address is hhp */
+#define ELMT_FROM_HH(tbl,hhp) ((void*)(((char*)(hhp)) - ((tbl)->hho)))
+/* calculate the hash handle from element address elp */
+#define HH_FROM_ELMT(tbl,elp) ((UT_hash_handle*)(void*)(((char*)(elp)) + ((tbl)->hho)))
+
+#define HASH_ROLLBACK_BKT(hh, head, itemptrhh)                                   \
+do {                                                                             \
+  struct UT_hash_handle *_hd_hh_item = (itemptrhh);                              \
+  unsigned _hd_bkt;                                                              \
+  HASH_TO_BKT(_hd_hh_item->hashv, (head)->hh.tbl->num_buckets, _hd_bkt);         \
+  (head)->hh.tbl->buckets[_hd_bkt].count++;                                      \
+  _hd_hh_item->hh_next = NULL;                                                   \
+  _hd_hh_item->hh_prev = NULL;                                                   \
+} while (0)
+
+#define HASH_VALUE(keyptr,keylen,hashv)                                          \
+do {                                                                             \
+  HASH_FCN(keyptr, keylen, hashv);                                               \
+} while (0)
+
+#define HASH_FIND_BYHASHVALUE(hh,head,keyptr,keylen,hashval,out)                 \
+do {                                                                             \
+  (out) = NULL;                                                                  \
+  if (head) {                                                                    \
+    unsigned _hf_bkt;                                                            \
+    HASH_TO_BKT(hashval, (head)->hh.tbl->num_buckets, _hf_bkt);                  \
+    if (HASH_BLOOM_TEST((head)->hh.tbl, hashval) != 0) {                         \
+      HASH_FIND_IN_BKT((head)->hh.tbl, hh, (head)->hh.tbl->buckets[ _hf_bkt ], keyptr, keylen, hashval, out); \
+    }                                                                            \
+  }                                                                              \
+} while (0)
+
+#define HASH_FIND(hh,head,keyptr,keylen,out)                                     \
+do {                                                                             \
+  (out) = NULL;                                                                  \
+  if (head) {                                                                    \
+    unsigned _hf_hashv;                                                          \
+    HASH_VALUE(keyptr, keylen, _hf_hashv);                                       \
+    HASH_FIND_BYHASHVALUE(hh, head, keyptr, keylen, _hf_hashv, out);             \
+  }                                                                              \
+} while (0)
+
+#ifdef HASH_BLOOM
+#define HASH_BLOOM_BITLEN (1UL << HASH_BLOOM)
+#define HASH_BLOOM_BYTELEN (HASH_BLOOM_BITLEN/8UL) + (((HASH_BLOOM_BITLEN%8UL)!=0UL) ? 1UL : 0UL)
+#define HASH_BLOOM_MAKE(tbl,oomed)                                               \
+do {                                                                             \
+  (tbl)->bloom_nbits = HASH_BLOOM;                                               \
+  (tbl)->bloom_bv = (uint8_t*)uthash_malloc(HASH_BLOOM_BYTELEN);                 \
+  if (!(tbl)->bloom_bv) {                                                        \
+    HASH_RECORD_OOM(oomed);                                                      \
+  } else {                                                                       \
+    uthash_bzero((tbl)->bloom_bv, HASH_BLOOM_BYTELEN);                           \
+    (tbl)->bloom_sig = HASH_BLOOM_SIGNATURE;                                     \
+  }                                                                              \
+} while (0)
+
+#define HASH_BLOOM_FREE(tbl)                                                     \
+do {                                                                             \
+  uthash_free((tbl)->bloom_bv, HASH_BLOOM_BYTELEN);                              \
+} while (0)
+
+#define HASH_BLOOM_BITSET(bv,idx) (bv[(idx)/8U] |= (1U << ((idx)%8U)))
+#define HASH_BLOOM_BITTEST(bv,idx) (bv[(idx)/8U] & (1U << ((idx)%8U)))
+
+#define HASH_BLOOM_ADD(tbl,hashv)                                                \
+  HASH_BLOOM_BITSET((tbl)->bloom_bv, ((hashv) & (uint32_t)((1UL << (tbl)->bloom_nbits) - 1U)))
+
+#define HASH_BLOOM_TEST(tbl,hashv)                                               \
+  HASH_BLOOM_BITTEST((tbl)->bloom_bv, ((hashv) & (uint32_t)((1UL << (tbl)->bloom_nbits) - 1U)))
+
+#else
+#define HASH_BLOOM_MAKE(tbl,oomed)
+#define HASH_BLOOM_FREE(tbl)
+#define HASH_BLOOM_ADD(tbl,hashv)
+#define HASH_BLOOM_TEST(tbl,hashv) (1)
+#define HASH_BLOOM_BYTELEN 0U
+#endif
+
+#define HASH_MAKE_TABLE(hh,head,oomed)                                           \
+do {                                                                             \
+  (head)->hh.tbl = (UT_hash_table*)uthash_malloc(sizeof(UT_hash_table));         \
+  if (!(head)->hh.tbl) {                                                         \
+    HASH_RECORD_OOM(oomed);                                                      \
+  } else {                                                                       \
+    uthash_bzero((head)->hh.tbl, sizeof(UT_hash_table));                         \
+    (head)->hh.tbl->tail = &((head)->hh);                                        \
+    (head)->hh.tbl->num_buckets = HASH_INITIAL_NUM_BUCKETS;                      \
+    (head)->hh.tbl->log2_num_buckets = HASH_INITIAL_NUM_BUCKETS_LOG2;            \
+    (head)->hh.tbl->hho = (char*)(&(head)->hh) - (char*)(head);                  \
+    (head)->hh.tbl->buckets = (UT_hash_bucket*)uthash_malloc(                    \
+        HASH_INITIAL_NUM_BUCKETS * sizeof(struct UT_hash_bucket));               \
+    (head)->hh.tbl->signature = HASH_SIGNATURE;                                  \
+    if (!(head)->hh.tbl->buckets) {                                              \
+      HASH_RECORD_OOM(oomed);                                                    \
+      uthash_free((head)->hh.tbl, sizeof(UT_hash_table));                        \
+    } else {                                                                     \
+      uthash_bzero((head)->hh.tbl->buckets,                                      \
+          HASH_INITIAL_NUM_BUCKETS * sizeof(struct UT_hash_bucket));             \
+      HASH_BLOOM_MAKE((head)->hh.tbl, oomed);                                    \
+      IF_HASH_NONFATAL_OOM(                                                      \
+        if (oomed) {                                                             \
+          uthash_free((head)->hh.tbl->buckets,                                   \
+              HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket));           \
+          uthash_free((head)->hh.tbl, sizeof(UT_hash_table));                    \
+        }                                                                        \
+      )                                                                          \
+    }                                                                            \
+  }                                                                              \
+} while (0)
+
+#define HASH_REPLACE_BYHASHVALUE_INORDER(hh,head,fieldname,keylen_in,hashval,add,replaced,cmpfcn) \
+do {                                                                             \
+  (replaced) = NULL;                                                             \
+  HASH_FIND_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, replaced); \
+  if (replaced) {                                                                \
+    HASH_DELETE(hh, head, replaced);                                             \
+  }                                                                              \
+  HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh, head, &((add)->fieldname), keylen_in, hashval, add, cmpfcn); \
+} while (0)
+
+#define HASH_REPLACE_BYHASHVALUE(hh,head,fieldname,keylen_in,hashval,add,replaced) \
+do {                                                                             \
+  (replaced) = NULL;                                                             \
+  HASH_FIND_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, replaced); \
+  if (replaced) {                                                                \
+    HASH_DELETE(hh, head, replaced);                                             \
+  }                                                                              \
+  HASH_ADD_KEYPTR_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, add); \
+} while (0)
+
+#define HASH_REPLACE(hh,head,fieldname,keylen_in,add,replaced)                   \
+do {                                                                             \
+  unsigned _hr_hashv;                                                            \
+  HASH_VALUE(&((add)->fieldname), keylen_in, _hr_hashv);                         \
+  HASH_REPLACE_BYHASHVALUE(hh, head, fieldname, keylen_in, _hr_hashv, add, replaced); \
+} while (0)
+
+#define HASH_REPLACE_INORDER(hh,head,fieldname,keylen_in,add,replaced,cmpfcn)    \
+do {                                                                             \
+  unsigned _hr_hashv;                                                            \
+  HASH_VALUE(&((add)->fieldname), keylen_in, _hr_hashv);                         \
+  HASH_REPLACE_BYHASHVALUE_INORDER(hh, head, fieldname, keylen_in, _hr_hashv, add, replaced, cmpfcn); \
+} while (0)
+
+#define HASH_APPEND_LIST(hh, head, add)                                          \
+do {                                                                             \
+  (add)->hh.next = NULL;                                                         \
+  (add)->hh.prev = ELMT_FROM_HH((head)->hh.tbl, (head)->hh.tbl->tail);           \
+  (head)->hh.tbl->tail->next = (add);                                            \
+  (head)->hh.tbl->tail = &((add)->hh);                                           \
+} while (0)
+
+#define HASH_AKBI_INNER_LOOP(hh,head,add,cmpfcn)                                 \
+do {                                                                             \
+  do {                                                                           \
+    if (cmpfcn(DECLTYPE(head)(_hs_iter), add) > 0) {                             \
+      break;                                                                     \
+    }                                                                            \
+  } while ((_hs_iter = HH_FROM_ELMT((head)->hh.tbl, _hs_iter)->next));           \
+} while (0)
+
+#ifdef NO_DECLTYPE
+#undef HASH_AKBI_INNER_LOOP
+#define HASH_AKBI_INNER_LOOP(hh,head,add,cmpfcn)                                 \
+do {                                                                             \
+  char *_hs_saved_head = (char*)(head);                                          \
+  do {                                                                           \
+    DECLTYPE_ASSIGN(head, _hs_iter);                                             \
+    if (cmpfcn(head, add) > 0) {                                                 \
+      DECLTYPE_ASSIGN(head, _hs_saved_head);                                     \
+      break;                                                                     \
+    }                                                                            \
+    DECLTYPE_ASSIGN(head, _hs_saved_head);                                       \
+  } while ((_hs_iter = HH_FROM_ELMT((head)->hh.tbl, _hs_iter)->next));           \
+} while (0)
+#endif
+
+#if HASH_NONFATAL_OOM
+
+#define HASH_ADD_TO_TABLE(hh,head,keyptr,keylen_in,hashval,add,oomed)            \
+do {                                                                             \
+  if (!(oomed)) {                                                                \
+    unsigned _ha_bkt;                                                            \
+    (head)->hh.tbl->num_items++;                                                 \
+    HASH_TO_BKT(hashval, (head)->hh.tbl->num_buckets, _ha_bkt);                  \
+    HASH_ADD_TO_BKT((head)->hh.tbl->buckets[_ha_bkt], hh, &(add)->hh, oomed);    \
+    if (oomed) {                                                                 \
+      HASH_ROLLBACK_BKT(hh, head, &(add)->hh);                                   \
+      HASH_DELETE_HH(hh, head, &(add)->hh);                                      \
+      (add)->hh.tbl = NULL;                                                      \
+      uthash_nonfatal_oom(add);                                                  \
+    } else {                                                                     \
+      HASH_BLOOM_ADD((head)->hh.tbl, hashval);                                   \
+      HASH_EMIT_KEY(hh, head, keyptr, keylen_in);                                \
+    }                                                                            \
+  } else {                                                                       \
+    (add)->hh.tbl = NULL;                                                        \
+    uthash_nonfatal_oom(add);                                                    \
+  }                                                                              \
+} while (0)
+
+#else
+
+#define HASH_ADD_TO_TABLE(hh,head,keyptr,keylen_in,hashval,add,oomed)            \
+do {                                                                             \
+  unsigned _ha_bkt;                                                              \
+  (head)->hh.tbl->num_items++;                                                   \
+  HASH_TO_BKT(hashval, (head)->hh.tbl->num_buckets, _ha_bkt);                    \
+  HASH_ADD_TO_BKT((head)->hh.tbl->buckets[_ha_bkt], hh, &(add)->hh, oomed);      \
+  HASH_BLOOM_ADD((head)->hh.tbl, hashval);                                       \
+  HASH_EMIT_KEY(hh, head, keyptr, keylen_in);                                    \
+} while (0)
+
+#endif
+
+
+#define HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh,head,keyptr,keylen_in,hashval,add,cmpfcn) \
+do {                                                                             \
+  IF_HASH_NONFATAL_OOM( int _ha_oomed = 0; )                                     \
+  (add)->hh.hashv = (hashval);                                                   \
+  (add)->hh.key = (char*) (keyptr);                                              \
+  (add)->hh.keylen = (unsigned) (keylen_in);                                     \
+  if (!(head)) {                                                                 \
+    (add)->hh.next = NULL;                                                       \
+    (add)->hh.prev = NULL;                                                       \
+    HASH_MAKE_TABLE(hh, add, _ha_oomed);                                         \
+    IF_HASH_NONFATAL_OOM( if (!_ha_oomed) { )                                    \
+      (head) = (add);                                                            \
+    IF_HASH_NONFATAL_OOM( } )                                                    \
+  } else {                                                                       \
+    void *_hs_iter = (head);                                                     \
+    (add)->hh.tbl = (head)->hh.tbl;                                              \
+    HASH_AKBI_INNER_LOOP(hh, head, add, cmpfcn);                                 \
+    if (_hs_iter) {                                                              \
+      (add)->hh.next = _hs_iter;                                                 \
+      if (((add)->hh.prev = HH_FROM_ELMT((head)->hh.tbl, _hs_iter)->prev)) {     \
+        HH_FROM_ELMT((head)->hh.tbl, (add)->hh.prev)->next = (add);              \
+      } else {                                                                   \
+        (head) = (add);                                                          \
+      }                                                                          \
+      HH_FROM_ELMT((head)->hh.tbl, _hs_iter)->prev = (add);                      \
+    } else {                                                                     \
+      HASH_APPEND_LIST(hh, head, add);                                           \
+    }                                                                            \
+  }                                                                              \
+  HASH_ADD_TO_TABLE(hh, head, keyptr, keylen_in, hashval, add, _ha_oomed);       \
+  HASH_FSCK(hh, head, "HASH_ADD_KEYPTR_BYHASHVALUE_INORDER");                    \
+} while (0)
+
+#define HASH_ADD_KEYPTR_INORDER(hh,head,keyptr,keylen_in,add,cmpfcn)             \
+do {                                                                             \
+  unsigned _hs_hashv;                                                            \
+  HASH_VALUE(keyptr, keylen_in, _hs_hashv);                                      \
+  HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh, head, keyptr, keylen_in, _hs_hashv, add, cmpfcn); \
+} while (0)
+
+#define HASH_ADD_BYHASHVALUE_INORDER(hh,head,fieldname,keylen_in,hashval,add,cmpfcn) \
+  HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh, head, &((add)->fieldname), keylen_in, hashval, add, cmpfcn)
+
+#define HASH_ADD_INORDER(hh,head,fieldname,keylen_in,add,cmpfcn)                 \
+  HASH_ADD_KEYPTR_INORDER(hh, head, &((add)->fieldname), keylen_in, add, cmpfcn)
+
+#define HASH_ADD_KEYPTR_BYHASHVALUE(hh,head,keyptr,keylen_in,hashval,add)        \
+do {                                                                             \
+  IF_HASH_NONFATAL_OOM( int _ha_oomed = 0; )                                     \
+  (add)->hh.hashv = (hashval);                                                   \
+  (add)->hh.key = (char*) (keyptr);                                              \
+  (add)->hh.keylen = (unsigned) (keylen_in);                                     \
+  if (!(head)) {                                                                 \
+    (add)->hh.next = NULL;                                                       \
+    (add)->hh.prev = NULL;                                                       \
+    HASH_MAKE_TABLE(hh, add, _ha_oomed);                                         \
+    IF_HASH_NONFATAL_OOM( if (!_ha_oomed) { )                                    \
+      (head) = (add);                                                            \
+    IF_HASH_NONFATAL_OOM( } )                                                    \
+  } else {                                                                       \
+    (add)->hh.tbl = (head)->hh.tbl;                                              \
+    HASH_APPEND_LIST(hh, head, add);                                             \
+  }                                                                              \
+  HASH_ADD_TO_TABLE(hh, head, keyptr, keylen_in, hashval, add, _ha_oomed);       \
+  HASH_FSCK(hh, head, "HASH_ADD_KEYPTR_BYHASHVALUE");                            \
+} while (0)
+
+#define HASH_ADD_KEYPTR(hh,head,keyptr,keylen_in,add)                            \
+do {                                                                             \
+  unsigned _ha_hashv;                                                            \
+  HASH_VALUE(keyptr, keylen_in, _ha_hashv);                                      \
+  HASH_ADD_KEYPTR_BYHASHVALUE(hh, head, keyptr, keylen_in, _ha_hashv, add);      \
+} while (0)
+
+#define HASH_ADD_BYHASHVALUE(hh,head,fieldname,keylen_in,hashval,add)            \
+  HASH_ADD_KEYPTR_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, add)
+
+#define HASH_ADD(hh,head,fieldname,keylen_in,add)                                \
+  HASH_ADD_KEYPTR(hh, head, &((add)->fieldname), keylen_in, add)
+
+#define HASH_TO_BKT(hashv,num_bkts,bkt)                                          \
+do {                                                                             \
+  bkt = ((hashv) & ((num_bkts) - 1U));                                           \
+} while (0)
+
+/* delete "delptr" from the hash table.
+ * "the usual" patch-up process for the app-order doubly-linked-list.
+ * The use of _hd_hh_del below deserves special explanation.
+ * These used to be expressed using (delptr) but that led to a bug
+ * if someone used the same symbol for the head and deletee, like
+ *  HASH_DELETE(hh,users,users);
+ * We want that to work, but by changing the head (users) below
+ * we were forfeiting our ability to further refer to the deletee (users)
+ * in the patch-up process. Solution: use scratch space to
+ * copy the deletee pointer, then the latter references are via that
+ * scratch pointer rather than through the repointed (users) symbol.
+ */
+#define HASH_DELETE(hh,head,delptr)                                              \
+    HASH_DELETE_HH(hh, head, &(delptr)->hh)
+
+#define HASH_DELETE_HH(hh,head,delptrhh)                                         \
+do {                                                                             \
+  struct UT_hash_handle *_hd_hh_del = (delptrhh);                                \
+  if ((_hd_hh_del->prev == NULL) && (_hd_hh_del->next == NULL)) {                \
+    HASH_BLOOM_FREE((head)->hh.tbl);                                             \
+    uthash_free((head)->hh.tbl->buckets,                                         \
+                (head)->hh.tbl->num_buckets * sizeof(struct UT_hash_bucket));    \
+    uthash_free((head)->hh.tbl, sizeof(UT_hash_table));                          \
+    (head) = NULL;                                                               \
+  } else {                                                                       \
+    unsigned _hd_bkt;                                                            \
+    if (_hd_hh_del == (head)->hh.tbl->tail) {                                    \
+      (head)->hh.tbl->tail = HH_FROM_ELMT((head)->hh.tbl, _hd_hh_del->prev);     \
+    }                                                                            \
+    if (_hd_hh_del->prev != NULL) {                                              \
+      HH_FROM_ELMT((head)->hh.tbl, _hd_hh_del->prev)->next = _hd_hh_del->next;   \
+    } else {                                                                     \
+      DECLTYPE_ASSIGN(head, _hd_hh_del->next);                                   \
+    }                                                                            \
+    if (_hd_hh_del->next != NULL) {                                              \
+      HH_FROM_ELMT((head)->hh.tbl, _hd_hh_del->next)->prev = _hd_hh_del->prev;   \
+    }                                                                            \
+    HASH_TO_BKT(_hd_hh_del->hashv, (head)->hh.tbl->num_buckets, _hd_bkt);        \
+    HASH_DEL_IN_BKT((head)->hh.tbl->buckets[_hd_bkt], _hd_hh_del);               \
+    (head)->hh.tbl->num_items--;                                                 \
+  }                                                                              \
+  HASH_FSCK(hh, head, "HASH_DELETE_HH");                                         \
+} while (0)
+
+/* convenience forms of HASH_FIND/HASH_ADD/HASH_DEL */
+#define HASH_FIND_STR(head,findstr,out)                                          \
+do {                                                                             \
+    unsigned _uthash_hfstr_keylen = (unsigned)uthash_strlen(findstr);            \
+    HASH_FIND(hh, head, findstr, _uthash_hfstr_keylen, out);                     \
+} while (0)
+#define HASH_ADD_STR(head,strfield,add)                                          \
+do {                                                                             \
+    unsigned _uthash_hastr_keylen = (unsigned)uthash_strlen((add)->strfield);    \
+    HASH_ADD(hh, head, strfield[0], _uthash_hastr_keylen, add);                  \
+} while (0)
+#define HASH_REPLACE_STR(head,strfield,add,replaced)                             \
+do {                                                                             \
+    unsigned _uthash_hrstr_keylen = (unsigned)uthash_strlen((add)->strfield);    \
+    HASH_REPLACE(hh, head, strfield[0], _uthash_hrstr_keylen, add, replaced);    \
+} while (0)
+#define HASH_FIND_INT(head,findint,out)                                          \
+    HASH_FIND(hh,head,findint,sizeof(int),out)
+#define HASH_ADD_INT(head,intfield,add)                                          \
+    HASH_ADD(hh,head,intfield,sizeof(int),add)
+#define HASH_REPLACE_INT(head,intfield,add,replaced)                             \
+    HASH_REPLACE(hh,head,intfield,sizeof(int),add,replaced)
+#define HASH_FIND_PTR(head,findptr,out)                                          \
+    HASH_FIND(hh,head,findptr,sizeof(void *),out)
+#define HASH_ADD_PTR(head,ptrfield,add)                                          \
+    HASH_ADD(hh,head,ptrfield,sizeof(void *),add)
+#define HASH_REPLACE_PTR(head,ptrfield,add,replaced)                             \
+    HASH_REPLACE(hh,head,ptrfield,sizeof(void *),add,replaced)
+#define HASH_DEL(head,delptr)                                                    \
+    HASH_DELETE(hh,head,delptr)
+
+/* HASH_FSCK checks hash integrity on every add/delete when HASH_DEBUG is defined.
+ * This is for uthash developer only; it compiles away if HASH_DEBUG isn't defined.
+ */
+#ifdef HASH_DEBUG
+#include <stdio.h>   /* fprintf, stderr */
+#define HASH_OOPS(...) do { fprintf(stderr, __VA_ARGS__); exit(-1); } while (0)
+#define HASH_FSCK(hh,head,where)                                                 \
+do {                                                                             \
+  struct UT_hash_handle *_thh;                                                   \
+  if (head) {                                                                    \
+    unsigned _bkt_i;                                                             \
+    unsigned _count = 0;                                                         \
+    char *_prev;                                                                 \
+    for (_bkt_i = 0; _bkt_i < (head)->hh.tbl->num_buckets; ++_bkt_i) {           \
+      unsigned _bkt_count = 0;                                                   \
+      _thh = (head)->hh.tbl->buckets[_bkt_i].hh_head;                            \
+      _prev = NULL;                                                              \
+      while (_thh) {                                                             \
+        if (_prev != (char*)(_thh->hh_prev)) {                                   \
+          HASH_OOPS("%s: invalid hh_prev %p, actual %p\n",                       \
+              (where), (void*)_thh->hh_prev, (void*)_prev);                      \
+        }                                                                        \
+        _bkt_count++;                                                            \
+        _prev = (char*)(_thh);                                                   \
+        _thh = _thh->hh_next;                                                    \
+      }                                                                          \
+      _count += _bkt_count;                                                      \
+      if ((head)->hh.tbl->buckets[_bkt_i].count !=  _bkt_count) {                \
+        HASH_OOPS("%s: invalid bucket count %u, actual %u\n",                    \
+            (where), (head)->hh.tbl->buckets[_bkt_i].count, _bkt_count);         \
+      }                                                                          \
+    }                                                                            \
+    if (_count != (head)->hh.tbl->num_items) {                                   \
+      HASH_OOPS("%s: invalid hh item count %u, actual %u\n",                     \
+          (where), (head)->hh.tbl->num_items, _count);                           \
+    }                                                                            \
+    _count = 0;                                                                  \
+    _prev = NULL;                                                                \
+    _thh =  &(head)->hh;                                                         \
+    while (_thh) {                                                               \
+      _count++;                                                                  \
+      if (_prev != (char*)_thh->prev) {                                          \
+        HASH_OOPS("%s: invalid prev %p, actual %p\n",                            \
+            (where), (void*)_thh->prev, (void*)_prev);                           \
+      }                                                                          \
+      _prev = (char*)ELMT_FROM_HH((head)->hh.tbl, _thh);                         \
+      _thh = (_thh->next ? HH_FROM_ELMT((head)->hh.tbl, _thh->next) : NULL);     \
+    }                                                                            \
+    if (_count != (head)->hh.tbl->num_items) {                                   \
+      HASH_OOPS("%s: invalid app item count %u, actual %u\n",                    \
+          (where), (head)->hh.tbl->num_items, _count);                           \
+    }                                                                            \
+  }                                                                              \
+} while (0)
+#else
+#define HASH_FSCK(hh,head,where)
+#endif
+
+/* When compiled with -DHASH_EMIT_KEYS, length-prefixed keys are emitted to
+ * the descriptor to which this macro is defined for tuning the hash function.
+ * The app can #include <unistd.h> to get the prototype for write(2). */
+#ifdef HASH_EMIT_KEYS
+#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen)                                   \
+do {                                                                             \
+  unsigned _klen = fieldlen;                                                     \
+  write(HASH_EMIT_KEYS, &_klen, sizeof(_klen));                                  \
+  write(HASH_EMIT_KEYS, keyptr, (unsigned long)fieldlen);                        \
+} while (0)
+#else
+#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen)
+#endif
+
+/* default to Jenkin's hash unless overridden e.g. DHASH_FUNCTION=HASH_SAX */
+#ifdef HASH_FUNCTION
+#define HASH_FCN HASH_FUNCTION
+#else
+#define HASH_FCN HASH_JEN
+#endif
+
+/* The Bernstein hash function, used in Perl prior to v5.6. Note (x<<5+x)=x*33. */
+#define HASH_BER(key,keylen,hashv)                                               \
+do {                                                                             \
+  unsigned _hb_keylen = (unsigned)keylen;                                        \
+  const unsigned char *_hb_key = (const unsigned char*)(key);                    \
+  (hashv) = 0;                                                                   \
+  while (_hb_keylen-- != 0U) {                                                   \
+    (hashv) = (((hashv) << 5) + (hashv)) + *_hb_key++;                           \
+  }                                                                              \
+} while (0)
+
+
+/* SAX/FNV/OAT/JEN hash functions are macro variants of those listed at
+ * http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx */
+#define HASH_SAX(key,keylen,hashv)                                               \
+do {                                                                             \
+  unsigned _sx_i;                                                                \
+  const unsigned char *_hs_key = (const unsigned char*)(key);                    \
+  hashv = 0;                                                                     \
+  for (_sx_i=0; _sx_i < keylen; _sx_i++) {                                       \
+    hashv ^= (hashv << 5) + (hashv >> 2) + _hs_key[_sx_i];                       \
+  }                                                                              \
+} while (0)
+/* FNV-1a variation */
+#define HASH_FNV(key,keylen,hashv)                                               \
+do {                                                                             \
+  unsigned _fn_i;                                                                \
+  const unsigned char *_hf_key = (const unsigned char*)(key);                    \
+  (hashv) = 2166136261U;                                                         \
+  for (_fn_i=0; _fn_i < keylen; _fn_i++) {                                       \
+    hashv = hashv ^ _hf_key[_fn_i];                                              \
+    hashv = hashv * 16777619U;                                                   \
+  }                                                                              \
+} while (0)
+
+#define HASH_OAT(key,keylen,hashv)                                               \
+do {                                                                             \
+  unsigned _ho_i;                                                                \
+  const unsigned char *_ho_key=(const unsigned char*)(key);                      \
+  hashv = 0;                                                                     \
+  for(_ho_i=0; _ho_i < keylen; _ho_i++) {                                        \
+      hashv += _ho_key[_ho_i];                                                   \
+      hashv += (hashv << 10);                                                    \
+      hashv ^= (hashv >> 6);                                                     \
+  }                                                                              \
+  hashv += (hashv << 3);                                                         \
+  hashv ^= (hashv >> 11);                                                        \
+  hashv += (hashv << 15);                                                        \
+} while (0)
+
+#define HASH_JEN_MIX(a,b,c)                                                      \
+do {                                                                             \
+  a -= b; a -= c; a ^= ( c >> 13 );                                              \
+  b -= c; b -= a; b ^= ( a << 8 );                                               \
+  c -= a; c -= b; c ^= ( b >> 13 );                                              \
+  a -= b; a -= c; a ^= ( c >> 12 );                                              \
+  b -= c; b -= a; b ^= ( a << 16 );                                              \
+  c -= a; c -= b; c ^= ( b >> 5 );                                               \
+  a -= b; a -= c; a ^= ( c >> 3 );                                               \
+  b -= c; b -= a; b ^= ( a << 10 );                                              \
+  c -= a; c -= b; c ^= ( b >> 15 );                                              \
+} while (0)
+
+#define HASH_JEN(key,keylen,hashv)                                               \
+do {                                                                             \
+  unsigned _hj_i,_hj_j,_hj_k;                                                    \
+  unsigned const char *_hj_key=(unsigned const char*)(key);                      \
+  hashv = 0xfeedbeefu;                                                           \
+  _hj_i = _hj_j = 0x9e3779b9u;                                                   \
+  _hj_k = (unsigned)(keylen);                                                    \
+  while (_hj_k >= 12U) {                                                         \
+    _hj_i +=    (_hj_key[0] + ( (unsigned)_hj_key[1] << 8 )                      \
+        + ( (unsigned)_hj_key[2] << 16 )                                         \
+        + ( (unsigned)_hj_key[3] << 24 ) );                                      \
+    _hj_j +=    (_hj_key[4] + ( (unsigned)_hj_key[5] << 8 )                      \
+        + ( (unsigned)_hj_key[6] << 16 )                                         \
+        + ( (unsigned)_hj_key[7] << 24 ) );                                      \
+    hashv += (_hj_key[8] + ( (unsigned)_hj_key[9] << 8 )                         \
+        + ( (unsigned)_hj_key[10] << 16 )                                        \
+        + ( (unsigned)_hj_key[11] << 24 ) );                                     \
+                                                                                 \
+     HASH_JEN_MIX(_hj_i, _hj_j, hashv);                                          \
+                                                                                 \
+     _hj_key += 12;                                                              \
+     _hj_k -= 12U;                                                               \
+  }                                                                              \
+  hashv += (unsigned)(keylen);                                                   \
+  switch ( _hj_k ) {                                                             \
+    case 11: hashv += ( (unsigned)_hj_key[10] << 24 ); /* FALLTHROUGH */         \
+    case 10: hashv += ( (unsigned)_hj_key[9] << 16 );  /* FALLTHROUGH */         \
+    case 9:  hashv += ( (unsigned)_hj_key[8] << 8 );   /* FALLTHROUGH */         \
+    case 8:  _hj_j += ( (unsigned)_hj_key[7] << 24 );  /* FALLTHROUGH */         \
+    case 7:  _hj_j += ( (unsigned)_hj_key[6] << 16 );  /* FALLTHROUGH */         \
+    case 6:  _hj_j += ( (unsigned)_hj_key[5] << 8 );   /* FALLTHROUGH */         \
+    case 5:  _hj_j += _hj_key[4];                      /* FALLTHROUGH */         \
+    case 4:  _hj_i += ( (unsigned)_hj_key[3] << 24 );  /* FALLTHROUGH */         \
+    case 3:  _hj_i += ( (unsigned)_hj_key[2] << 16 );  /* FALLTHROUGH */         \
+    case 2:  _hj_i += ( (unsigned)_hj_key[1] << 8 );   /* FALLTHROUGH */         \
+    case 1:  _hj_i += _hj_key[0];                                                \
+  }                                                                              \
+  HASH_JEN_MIX(_hj_i, _hj_j, hashv);                                             \
+} while (0)
+
+/* The Paul Hsieh hash function */
+#undef get16bits
+#if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__)             \
+  || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
+#define get16bits(d) (*((const uint16_t *) (d)))
+#endif
+
+#if !defined (get16bits)
+#define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)             \
+                       +(uint32_t)(((const uint8_t *)(d))[0]) )
+#endif
+#define HASH_SFH(key,keylen,hashv)                                               \
+do {                                                                             \
+  unsigned const char *_sfh_key=(unsigned const char*)(key);                     \
+  uint32_t _sfh_tmp, _sfh_len = (uint32_t)keylen;                                \
+                                                                                 \
+  unsigned _sfh_rem = _sfh_len & 3U;                                             \
+  _sfh_len >>= 2;                                                                \
+  hashv = 0xcafebabeu;                                                           \
+                                                                                 \
+  /* Main loop */                                                                \
+  for (;_sfh_len > 0U; _sfh_len--) {                                             \
+    hashv    += get16bits (_sfh_key);                                            \
+    _sfh_tmp  = ((uint32_t)(get16bits (_sfh_key+2)) << 11) ^ hashv;              \
+    hashv     = (hashv << 16) ^ _sfh_tmp;                                        \
+    _sfh_key += 2U*sizeof (uint16_t);                                            \
+    hashv    += hashv >> 11;                                                     \
+  }                                                                              \
+                                                                                 \
+  /* Handle end cases */                                                         \
+  switch (_sfh_rem) {                                                            \
+    case 3: hashv += get16bits (_sfh_key);                                       \
+            hashv ^= hashv << 16;                                                \
+            hashv ^= (uint32_t)(_sfh_key[sizeof (uint16_t)]) << 18;              \
+            hashv += hashv >> 11;                                                \
+            break;                                                               \
+    case 2: hashv += get16bits (_sfh_key);                                       \
+            hashv ^= hashv << 11;                                                \
+            hashv += hashv >> 17;                                                \
+            break;                                                               \
+    case 1: hashv += *_sfh_key;                                                  \
+            hashv ^= hashv << 10;                                                \
+            hashv += hashv >> 1;                                                 \
+  }                                                                              \
+                                                                                 \
+  /* Force "avalanching" of final 127 bits */                                    \
+  hashv ^= hashv << 3;                                                           \
+  hashv += hashv >> 5;                                                           \
+  hashv ^= hashv << 4;                                                           \
+  hashv += hashv >> 17;                                                          \
+  hashv ^= hashv << 25;                                                          \
+  hashv += hashv >> 6;                                                           \
+} while (0)
+
+/* iterate over items in a known bucket to find desired item */
+#define HASH_FIND_IN_BKT(tbl,hh,head,keyptr,keylen_in,hashval,out)               \
+do {                                                                             \
+  if ((head).hh_head != NULL) {                                                  \
+    DECLTYPE_ASSIGN(out, ELMT_FROM_HH(tbl, (head).hh_head));                     \
+  } else {                                                                       \
+    (out) = NULL;                                                                \
+  }                                                                              \
+  while ((out) != NULL) {                                                        \
+    if ((out)->hh.hashv == (hashval) && (out)->hh.keylen == (keylen_in)) {       \
+      if (HASH_KEYCMP((out)->hh.key, keyptr, keylen_in) == 0) {              \
+        break;                                                                   \
+      }                                                                          \
+    }                                                                            \
+    if ((out)->hh.hh_next != NULL) {                                             \
+      DECLTYPE_ASSIGN(out, ELMT_FROM_HH(tbl, (out)->hh.hh_next));                \
+    } else {                                                                     \
+      (out) = NULL;                                                              \
+    }                                                                            \
+  }                                                                              \
+} while (0)
+
+/* add an item to a bucket  */
+#define HASH_ADD_TO_BKT(head,hh,addhh,oomed)                                     \
+do {                                                                             \
+  UT_hash_bucket *_ha_head = &(head);                                            \
+  _ha_head->count++;                                                             \
+  (addhh)->hh_next = _ha_head->hh_head;                                          \
+  (addhh)->hh_prev = NULL;                                                       \
+  if (_ha_head->hh_head != NULL) {                                               \
+    _ha_head->hh_head->hh_prev = (addhh);                                        \
+  }                                                                              \
+  _ha_head->hh_head = (addhh);                                                   \
+  if ((_ha_head->count >= ((_ha_head->expand_mult + 1U) * HASH_BKT_CAPACITY_THRESH)) \
+      && !(addhh)->tbl->noexpand) {                                              \
+    HASH_EXPAND_BUCKETS(addhh,(addhh)->tbl, oomed);                              \
+    IF_HASH_NONFATAL_OOM(                                                        \
+      if (oomed) {                                                               \
+        HASH_DEL_IN_BKT(head,addhh);                                             \
+      }                                                                          \
+    )                                                                            \
+  }                                                                              \
+} while (0)
+
+/* remove an item from a given bucket */
+#define HASH_DEL_IN_BKT(head,delhh)                                              \
+do {                                                                             \
+  UT_hash_bucket *_hd_head = &(head);                                            \
+  _hd_head->count--;                                                             \
+  if (_hd_head->hh_head == (delhh)) {                                            \
+    _hd_head->hh_head = (delhh)->hh_next;                                        \
+  }                                                                              \
+  if ((delhh)->hh_prev) {                                                        \
+    (delhh)->hh_prev->hh_next = (delhh)->hh_next;                                \
+  }                                                                              \
+  if ((delhh)->hh_next) {                                                        \
+    (delhh)->hh_next->hh_prev = (delhh)->hh_prev;                                \
+  }                                                                              \
+} while (0)
+
+/* Bucket expansion has the effect of doubling the number of buckets
+ * and redistributing the items into the new buckets. Ideally the
+ * items will distribute more or less evenly into the new buckets
+ * (the extent to which this is true is a measure of the quality of
+ * the hash function as it applies to the key domain).
+ *
+ * With the items distributed into more buckets, the chain length
+ * (item count) in each bucket is reduced. Thus by expanding buckets
+ * the hash keeps a bound on the chain length. This bounded chain
+ * length is the essence of how a hash provides constant time lookup.
+ *
+ * The calculation of tbl->ideal_chain_maxlen below deserves some
+ * explanation. First, keep in mind that we're calculating the ideal
+ * maximum chain length based on the *new* (doubled) bucket count.
+ * In fractions this is just n/b (n=number of items,b=new num buckets).
+ * Since the ideal chain length is an integer, we want to calculate
+ * ceil(n/b). We don't depend on floating point arithmetic in this
+ * hash, so to calculate ceil(n/b) with integers we could write
+ *
+ *      ceil(n/b) = (n/b) + ((n%b)?1:0)
+ *
+ * and in fact a previous version of this hash did just that.
+ * But now we have improved things a bit by recognizing that b is
+ * always a power of two. We keep its base 2 log handy (call it lb),
+ * so now we can write this with a bit shift and logical AND:
+ *
+ *      ceil(n/b) = (n>>lb) + ( (n & (b-1)) ? 1:0)
+ *
+ */
+#define HASH_EXPAND_BUCKETS(hh,tbl,oomed)                                        \
+do {                                                                             \
+  unsigned _he_bkt;                                                              \
+  unsigned _he_bkt_i;                                                            \
+  struct UT_hash_handle *_he_thh, *_he_hh_nxt;                                   \
+  UT_hash_bucket *_he_new_buckets, *_he_newbkt;                                  \
+  _he_new_buckets = (UT_hash_bucket*)uthash_malloc(                              \
+           2UL * (tbl)->num_buckets * sizeof(struct UT_hash_bucket));            \
+  if (!_he_new_buckets) {                                                        \
+    HASH_RECORD_OOM(oomed);                                                      \
+  } else {                                                                       \
+    uthash_bzero(_he_new_buckets,                                                \
+        2UL * (tbl)->num_buckets * sizeof(struct UT_hash_bucket));               \
+    (tbl)->ideal_chain_maxlen =                                                  \
+       ((tbl)->num_items >> ((tbl)->log2_num_buckets+1U)) +                      \
+       ((((tbl)->num_items & (((tbl)->num_buckets*2U)-1U)) != 0U) ? 1U : 0U);    \
+    (tbl)->nonideal_items = 0;                                                   \
+    for (_he_bkt_i = 0; _he_bkt_i < (tbl)->num_buckets; _he_bkt_i++) {           \
+      _he_thh = (tbl)->buckets[ _he_bkt_i ].hh_head;                             \
+      while (_he_thh != NULL) {                                                  \
+        _he_hh_nxt = _he_thh->hh_next;                                           \
+        HASH_TO_BKT(_he_thh->hashv, (tbl)->num_buckets * 2U, _he_bkt);           \
+        _he_newbkt = &(_he_new_buckets[_he_bkt]);                                \
+        if (++(_he_newbkt->count) > (tbl)->ideal_chain_maxlen) {                 \
+          (tbl)->nonideal_items++;                                               \
+          if (_he_newbkt->count > _he_newbkt->expand_mult * (tbl)->ideal_chain_maxlen) { \
+            _he_newbkt->expand_mult++;                                           \
+          }                                                                      \
+        }                                                                        \
+        _he_thh->hh_prev = NULL;                                                 \
+        _he_thh->hh_next = _he_newbkt->hh_head;                                  \
+        if (_he_newbkt->hh_head != NULL) {                                       \
+          _he_newbkt->hh_head->hh_prev = _he_thh;                                \
+        }                                                                        \
+        _he_newbkt->hh_head = _he_thh;                                           \
+        _he_thh = _he_hh_nxt;                                                    \
+      }                                                                          \
+    }                                                                            \
+    uthash_free((tbl)->buckets, (tbl)->num_buckets * sizeof(struct UT_hash_bucket)); \
+    (tbl)->num_buckets *= 2U;                                                    \
+    (tbl)->log2_num_buckets++;                                                   \
+    (tbl)->buckets = _he_new_buckets;                                            \
+    (tbl)->ineff_expands = ((tbl)->nonideal_items > ((tbl)->num_items >> 1)) ?   \
+        ((tbl)->ineff_expands+1U) : 0U;                                          \
+    if ((tbl)->ineff_expands > 1U) {                                             \
+      (tbl)->noexpand = 1;                                                       \
+      uthash_noexpand_fyi(tbl);                                                  \
+    }                                                                            \
+    uthash_expand_fyi(tbl);                                                      \
+  }                                                                              \
+} while (0)
+
+
+/* This is an adaptation of Simon Tatham's O(n log(n)) mergesort */
+/* Note that HASH_SORT assumes the hash handle name to be hh.
+ * HASH_SRT was added to allow the hash handle name to be passed in. */
+#define HASH_SORT(head,cmpfcn) HASH_SRT(hh,head,cmpfcn)
+#define HASH_SRT(hh,head,cmpfcn)                                                 \
+do {                                                                             \
+  unsigned _hs_i;                                                                \
+  unsigned _hs_looping,_hs_nmerges,_hs_insize,_hs_psize,_hs_qsize;               \
+  struct UT_hash_handle *_hs_p, *_hs_q, *_hs_e, *_hs_list, *_hs_tail;            \
+  if (head != NULL) {                                                            \
+    _hs_insize = 1;                                                              \
+    _hs_looping = 1;                                                             \
+    _hs_list = &((head)->hh);                                                    \
+    while (_hs_looping != 0U) {                                                  \
+      _hs_p = _hs_list;                                                          \
+      _hs_list = NULL;                                                           \
+      _hs_tail = NULL;                                                           \
+      _hs_nmerges = 0;                                                           \
+      while (_hs_p != NULL) {                                                    \
+        _hs_nmerges++;                                                           \
+        _hs_q = _hs_p;                                                           \
+        _hs_psize = 0;                                                           \
+        for (_hs_i = 0; _hs_i < _hs_insize; ++_hs_i) {                           \
+          _hs_psize++;                                                           \
+          _hs_q = ((_hs_q->next != NULL) ?                                       \
+            HH_FROM_ELMT((head)->hh.tbl, _hs_q->next) : NULL);                   \
+          if (_hs_q == NULL) {                                                   \
+            break;                                                               \
+          }                                                                      \
+        }                                                                        \
+        _hs_qsize = _hs_insize;                                                  \
+        while ((_hs_psize != 0U) || ((_hs_qsize != 0U) && (_hs_q != NULL))) {    \
+          if (_hs_psize == 0U) {                                                 \
+            _hs_e = _hs_q;                                                       \
+            _hs_q = ((_hs_q->next != NULL) ?                                     \
+              HH_FROM_ELMT((head)->hh.tbl, _hs_q->next) : NULL);                 \
+            _hs_qsize--;                                                         \
+          } else if ((_hs_qsize == 0U) || (_hs_q == NULL)) {                     \
+            _hs_e = _hs_p;                                                       \
+            if (_hs_p != NULL) {                                                 \
+              _hs_p = ((_hs_p->next != NULL) ?                                   \
+                HH_FROM_ELMT((head)->hh.tbl, _hs_p->next) : NULL);               \
+            }                                                                    \
+            _hs_psize--;                                                         \
+          } else if ((cmpfcn(                                                    \
+                DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl, _hs_p)),             \
+                DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl, _hs_q))              \
+                )) <= 0) {                                                       \
+            _hs_e = _hs_p;                                                       \
+            if (_hs_p != NULL) {                                                 \
+              _hs_p = ((_hs_p->next != NULL) ?                                   \
+                HH_FROM_ELMT((head)->hh.tbl, _hs_p->next) : NULL);               \
+            }                                                                    \
+            _hs_psize--;                                                         \
+          } else {                                                               \
+            _hs_e = _hs_q;                                                       \
+            _hs_q = ((_hs_q->next != NULL) ?                                     \
+              HH_FROM_ELMT((head)->hh.tbl, _hs_q->next) : NULL);                 \
+            _hs_qsize--;                                                         \
+          }                                                                      \
+          if ( _hs_tail != NULL ) {                                              \
+            _hs_tail->next = ((_hs_e != NULL) ?                                  \
+              ELMT_FROM_HH((head)->hh.tbl, _hs_e) : NULL);                       \
+          } else {                                                               \
+            _hs_list = _hs_e;                                                    \
+          }                                                                      \
+          if (_hs_e != NULL) {                                                   \
+            _hs_e->prev = ((_hs_tail != NULL) ?                                  \
+              ELMT_FROM_HH((head)->hh.tbl, _hs_tail) : NULL);                    \
+          }                                                                      \
+          _hs_tail = _hs_e;                                                      \
+        }                                                                        \
+        _hs_p = _hs_q;                                                           \
+      }                                                                          \
+      if (_hs_tail != NULL) {                                                    \
+        _hs_tail->next = NULL;                                                   \
+      }                                                                          \
+      if (_hs_nmerges <= 1U) {                                                   \
+        _hs_looping = 0;                                                         \
+        (head)->hh.tbl->tail = _hs_tail;                                         \
+        DECLTYPE_ASSIGN(head, ELMT_FROM_HH((head)->hh.tbl, _hs_list));           \
+      }                                                                          \
+      _hs_insize *= 2U;                                                          \
+    }                                                                            \
+    HASH_FSCK(hh, head, "HASH_SRT");                                             \
+  }                                                                              \
+} while (0)
+
+/* This function selects items from one hash into another hash.
+ * The end result is that the selected items have dual presence
+ * in both hashes. There is no copy of the items made; rather
+ * they are added into the new hash through a secondary hash
+ * hash handle that must be present in the structure. */
+#define HASH_SELECT(hh_dst, dst, hh_src, src, cond)                              \
+do {                                                                             \
+  unsigned _src_bkt, _dst_bkt;                                                   \
+  void *_last_elt = NULL, *_elt;                                                 \
+  UT_hash_handle *_src_hh, *_dst_hh, *_last_elt_hh=NULL;                         \
+  ptrdiff_t _dst_hho = ((char*)(&(dst)->hh_dst) - (char*)(dst));                 \
+  if ((src) != NULL) {                                                           \
+    for (_src_bkt=0; _src_bkt < (src)->hh_src.tbl->num_buckets; _src_bkt++) {    \
+      for (_src_hh = (src)->hh_src.tbl->buckets[_src_bkt].hh_head;               \
+        _src_hh != NULL;                                                         \
+        _src_hh = _src_hh->hh_next) {                                            \
+        _elt = ELMT_FROM_HH((src)->hh_src.tbl, _src_hh);                         \
+        if (cond(_elt)) {                                                        \
+          IF_HASH_NONFATAL_OOM( int _hs_oomed = 0; )                             \
+          _dst_hh = (UT_hash_handle*)(void*)(((char*)_elt) + _dst_hho);          \
+          _dst_hh->key = _src_hh->key;                                           \
+          _dst_hh->keylen = _src_hh->keylen;                                     \
+          _dst_hh->hashv = _src_hh->hashv;                                       \
+          _dst_hh->prev = _last_elt;                                             \
+          _dst_hh->next = NULL;                                                  \
+          if (_last_elt_hh != NULL) {                                            \
+            _last_elt_hh->next = _elt;                                           \
+          }                                                                      \
+          if ((dst) == NULL) {                                                   \
+            DECLTYPE_ASSIGN(dst, _elt);                                          \
+            HASH_MAKE_TABLE(hh_dst, dst, _hs_oomed);                             \
+            IF_HASH_NONFATAL_OOM(                                                \
+              if (_hs_oomed) {                                                   \
+                uthash_nonfatal_oom(_elt);                                       \
+                (dst) = NULL;                                                    \
+                continue;                                                        \
+              }                                                                  \
+            )                                                                    \
+          } else {                                                               \
+            _dst_hh->tbl = (dst)->hh_dst.tbl;                                    \
+          }                                                                      \
+          HASH_TO_BKT(_dst_hh->hashv, _dst_hh->tbl->num_buckets, _dst_bkt);      \
+          HASH_ADD_TO_BKT(_dst_hh->tbl->buckets[_dst_bkt], hh_dst, _dst_hh, _hs_oomed); \
+          (dst)->hh_dst.tbl->num_items++;                                        \
+          IF_HASH_NONFATAL_OOM(                                                  \
+            if (_hs_oomed) {                                                     \
+              HASH_ROLLBACK_BKT(hh_dst, dst, _dst_hh);                           \
+              HASH_DELETE_HH(hh_dst, dst, _dst_hh);                              \
+              _dst_hh->tbl = NULL;                                               \
+              uthash_nonfatal_oom(_elt);                                         \
+              continue;                                                          \
+            }                                                                    \
+          )                                                                      \
+          HASH_BLOOM_ADD(_dst_hh->tbl, _dst_hh->hashv);                          \
+          _last_elt = _elt;                                                      \
+          _last_elt_hh = _dst_hh;                                                \
+        }                                                                        \
+      }                                                                          \
+    }                                                                            \
+  }                                                                              \
+  HASH_FSCK(hh_dst, dst, "HASH_SELECT");                                         \
+} while (0)
+
+#define HASH_CLEAR(hh,head)                                                      \
+do {                                                                             \
+  if ((head) != NULL) {                                                          \
+    HASH_BLOOM_FREE((head)->hh.tbl);                                             \
+    uthash_free((head)->hh.tbl->buckets,                                         \
+                (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket));      \
+    uthash_free((head)->hh.tbl, sizeof(UT_hash_table));                          \
+    (head) = NULL;                                                               \
+  }                                                                              \
+} while (0)
+
+#define HASH_OVERHEAD(hh,head)                                                   \
+ (((head) != NULL) ? (                                                           \
+ (size_t)(((head)->hh.tbl->num_items   * sizeof(UT_hash_handle))   +             \
+          ((head)->hh.tbl->num_buckets * sizeof(UT_hash_bucket))   +             \
+           sizeof(UT_hash_table)                                   +             \
+           (HASH_BLOOM_BYTELEN))) : 0U)
+
+#ifdef NO_DECLTYPE
+#define HASH_ITER(hh,head,el,tmp)                                                \
+for(((el)=(head)), ((*(char**)(&(tmp)))=(char*)((head!=NULL)?(head)->hh.next:NULL)); \
+  (el) != NULL; ((el)=(tmp)), ((*(char**)(&(tmp)))=(char*)((tmp!=NULL)?(tmp)->hh.next:NULL)))
+#else
+#define HASH_ITER(hh,head,el,tmp)                                                \
+for(((el)=(head)), ((tmp)=DECLTYPE(el)((head!=NULL)?(head)->hh.next:NULL));      \
+  (el) != NULL; ((el)=(tmp)), ((tmp)=DECLTYPE(el)((tmp!=NULL)?(tmp)->hh.next:NULL)))
+#endif
+
+/* obtain a count of items in the hash */
+#define HASH_COUNT(head) HASH_CNT(hh,head)
+#define HASH_CNT(hh,head) ((head != NULL)?((head)->hh.tbl->num_items):0U)
+
+typedef struct UT_hash_bucket {
+   struct UT_hash_handle *hh_head;
+   unsigned count;
+
+   /* expand_mult is normally set to 0. In this situation, the max chain length
+    * threshold is enforced at its default value, HASH_BKT_CAPACITY_THRESH. (If
+    * the bucket's chain exceeds this length, bucket expansion is triggered).
+    * However, setting expand_mult to a non-zero value delays bucket expansion
+    * (that would be triggered by additions to this particular bucket)
+    * until its chain length reaches a *multiple* of HASH_BKT_CAPACITY_THRESH.
+    * (The multiplier is simply expand_mult+1). The whole idea of this
+    * multiplier is to reduce bucket expansions, since they are expensive, in
+    * situations where we know that a particular bucket tends to be overused.
+    * It is better to let its chain length grow to a longer yet-still-bounded
+    * value, than to do an O(n) bucket expansion too often.
+    */
+   unsigned expand_mult;
+
+} UT_hash_bucket;
+
+/* random signature used only to find hash tables in external analysis */
+#define HASH_SIGNATURE 0xa0111fe1u
+#define HASH_BLOOM_SIGNATURE 0xb12220f2u
+
+typedef struct UT_hash_table {
+   UT_hash_bucket *buckets;
+   unsigned num_buckets, log2_num_buckets;
+   unsigned num_items;
+   struct UT_hash_handle *tail; /* tail hh in app order, for fast append    */
+   ptrdiff_t hho; /* hash handle offset (byte pos of hash handle in element */
+
+   /* in an ideal situation (all buckets used equally), no bucket would have
+    * more than ceil(#items/#buckets) items. that's the ideal chain length. */
+   unsigned ideal_chain_maxlen;
+
+   /* nonideal_items is the number of items in the hash whose chain position
+    * exceeds the ideal chain maxlen. these items pay the penalty for an uneven
+    * hash distribution; reaching them in a chain traversal takes >ideal steps */
+   unsigned nonideal_items;
+
+   /* ineffective expands occur when a bucket doubling was performed, but
+    * afterward, more than half the items in the hash had nonideal chain
+    * positions. If this happens on two consecutive expansions we inhibit any
+    * further expansion, as it's not helping; this happens when the hash
+    * function isn't a good fit for the key domain. When expansion is inhibited
+    * the hash will still work, albeit no longer in constant time. */
+   unsigned ineff_expands, noexpand;
+
+   uint32_t signature; /* used only to find hash tables in external analysis */
+#ifdef HASH_BLOOM
+   uint32_t bloom_sig; /* used only to test bloom exists in external analysis */
+   uint8_t *bloom_bv;
+   uint8_t bloom_nbits;
+#endif
+
+} UT_hash_table;
+
+typedef struct UT_hash_handle {
+   struct UT_hash_table *tbl;
+   void *prev;                       /* prev element in app order      */
+   void *next;                       /* next element in app order      */
+   struct UT_hash_handle *hh_prev;   /* previous hh in bucket order    */
+   struct UT_hash_handle *hh_next;   /* next hh in bucket order        */
+   void *key;                        /* ptr to enclosing struct's key  */
+   unsigned keylen;                  /* enclosing struct's key len     */
+   unsigned hashv;                   /* result of hash-fcn(key)        */
+} UT_hash_handle;
+
+#endif /* UTHASH_H */
diff --git a/deps/uthash/utlist.h b/deps/uthash/utlist.h
new file mode 100644
index 0000000..492908c
--- /dev/null
+++ b/deps/uthash/utlist.h
@@ -0,0 +1,1073 @@
+/*
+Copyright (c) 2007-2022, Troy D. Hanson  https://troydhanson.github.io/uthash/
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+    * Redistributions of source code must retain the above copyright
+      notice, this list of conditions and the following disclaimer.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
+IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
+OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#ifndef UTLIST_H
+#define UTLIST_H
+
+#define UTLIST_VERSION 2.3.0
+
+#include <assert.h>
+
+/*
+ * This file contains macros to manipulate singly and doubly-linked lists.
+ *
+ * 1. LL_ macros:  singly-linked lists.
+ * 2. DL_ macros:  doubly-linked lists.
+ * 3. CDL_ macros: circular doubly-linked lists.
+ *
+ * To use singly-linked lists, your structure must have a "next" pointer.
+ * To use doubly-linked lists, your structure must "prev" and "next" pointers.
+ * Either way, the pointer to the head of the list must be initialized to NULL.
+ *
+ * ----------------.EXAMPLE -------------------------
+ * struct item {
+ *      int id;
+ *      struct item *prev, *next;
+ * }
+ *
+ * struct item *list = NULL:
+ *
+ * int main() {
+ *      struct item *item;
+ *      ... allocate and populate item ...
+ *      DL_APPEND(list, item);
+ * }
+ * --------------------------------------------------
+ *
+ * For doubly-linked lists, the append and delete macros are O(1)
+ * For singly-linked lists, append and delete are O(n) but prepend is O(1)
+ * The sort macro is O(n log(n)) for all types of single/double/circular lists.
+ */
+
+/* These macros use decltype or the earlier __typeof GNU extension.
+   As decltype is only available in newer compilers (VS2010 or gcc 4.3+
+   when compiling c++ source) this code uses whatever method is needed
+   or, for VS2008 where neither is available, uses casting workarounds. */
+#if !defined(LDECLTYPE) && !defined(NO_DECLTYPE)
+#if defined(_MSC_VER)   /* MS compiler */
+#if _MSC_VER >= 1600 && defined(__cplusplus)  /* VS2010 or newer in C++ mode */
+#define LDECLTYPE(x) decltype(x)
+#else                   /* VS2008 or older (or VS2010 in C mode) */
+#define NO_DECLTYPE
+#endif
+#elif defined(__BORLANDC__) || defined(__ICCARM__) || defined(__LCC__) || defined(__WATCOMC__)
+#define NO_DECLTYPE
+#else                   /* GNU, Sun and other compilers */
+#define LDECLTYPE(x) __typeof(x)
+#endif
+#endif
+
+/* for VS2008 we use some workarounds to get around the lack of decltype,
+ * namely, we always reassign our tmp variable to the list head if we need
+ * to dereference its prev/next pointers, and save/restore the real head.*/
+#ifdef NO_DECLTYPE
+#define IF_NO_DECLTYPE(x) x
+#define LDECLTYPE(x) char*
+#define UTLIST_SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); }
+#define UTLIST_NEXT(elt,list,next) ((char*)((list)->next))
+#define UTLIST_NEXTASGN(elt,list,to,next) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); }
+/* #define UTLIST_PREV(elt,list,prev) ((char*)((list)->prev)) */
+#define UTLIST_PREVASGN(elt,list,to,prev) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); }
+#define UTLIST_RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; }
+#define UTLIST_CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); }
+#else
+#define IF_NO_DECLTYPE(x)
+#define UTLIST_SV(elt,list)
+#define UTLIST_NEXT(elt,list,next) ((elt)->next)
+#define UTLIST_NEXTASGN(elt,list,to,next) ((elt)->next)=(to)
+/* #define UTLIST_PREV(elt,list,prev) ((elt)->prev) */
+#define UTLIST_PREVASGN(elt,list,to,prev) ((elt)->prev)=(to)
+#define UTLIST_RS(list)
+#define UTLIST_CASTASGN(a,b) (a)=(b)
+#endif
+
+/******************************************************************************
+ * The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort    *
+ * Unwieldy variable names used here to avoid shadowing passed-in variables.  *
+ *****************************************************************************/
+#define LL_SORT(list, cmp)                                                                     \
+    LL_SORT2(list, cmp, next)
+
+#define LL_SORT2(list, cmp, next)                                                              \
+do {                                                                                           \
+  LDECLTYPE(list) _ls_p;                                                                       \
+  LDECLTYPE(list) _ls_q;                                                                       \
+  LDECLTYPE(list) _ls_e;                                                                       \
+  LDECLTYPE(list) _ls_tail;                                                                    \
+  IF_NO_DECLTYPE(LDECLTYPE(list) _tmp;)                                                        \
+  int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping;                       \
+  if (list) {                                                                                  \
+    _ls_insize = 1;                                                                            \
+    _ls_looping = 1;                                                                           \
+    while (_ls_looping) {                                                                      \
+      UTLIST_CASTASGN(_ls_p,list);                                                             \
+      (list) = NULL;                                                                           \
+      _ls_tail = NULL;                                                                         \
+      _ls_nmerges = 0;                                                                         \
+      while (_ls_p) {                                                                          \
+        _ls_nmerges++;                                                                         \
+        _ls_q = _ls_p;                                                                         \
+        _ls_psize = 0;                                                                         \
+        for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) {                                         \
+          _ls_psize++;                                                                         \
+          UTLIST_SV(_ls_q,list); _ls_q = UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list);        \
+          if (!_ls_q) break;                                                                   \
+        }                                                                                      \
+        _ls_qsize = _ls_insize;                                                                \
+        while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) {                                    \
+          if (_ls_psize == 0) {                                                                \
+            _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q =                                      \
+              UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--;                      \
+          } else if (_ls_qsize == 0 || !_ls_q) {                                               \
+            _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p =                                      \
+              UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--;                      \
+          } else if (cmp(_ls_p,_ls_q) <= 0) {                                                  \
+            _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p =                                      \
+              UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--;                      \
+          } else {                                                                             \
+            _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q =                                      \
+              UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--;                      \
+          }                                                                                    \
+          if (_ls_tail) {                                                                      \
+            UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,_ls_e,next); UTLIST_RS(list); \
+          } else {                                                                             \
+            UTLIST_CASTASGN(list,_ls_e);                                                       \
+          }                                                                                    \
+          _ls_tail = _ls_e;                                                                    \
+        }                                                                                      \
+        _ls_p = _ls_q;                                                                         \
+      }                                                                                        \
+      if (_ls_tail) {                                                                          \
+        UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,NULL,next); UTLIST_RS(list);   \
+      }                                                                                        \
+      if (_ls_nmerges <= 1) {                                                                  \
+        _ls_looping=0;                                                                         \
+      }                                                                                        \
+      _ls_insize *= 2;                                                                         \
+    }                                                                                          \
+  }                                                                                            \
+} while (0)
+
+
+#define DL_SORT(list, cmp)                                                                     \
+    DL_SORT2(list, cmp, prev, next)
+
+#define DL_SORT2(list, cmp, prev, next)                                                        \
+do {                                                                                           \
+  LDECLTYPE(list) _ls_p;                                                                       \
+  LDECLTYPE(list) _ls_q;                                                                       \
+  LDECLTYPE(list) _ls_e;                                                                       \
+  LDECLTYPE(list) _ls_tail;                                                                    \
+  IF_NO_DECLTYPE(LDECLTYPE(list) _tmp;)                                                        \
+  int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping;                       \
+  if (list) {                                                                                  \
+    _ls_insize = 1;                                                                            \
+    _ls_looping = 1;                                                                           \
+    while (_ls_looping) {                                                                      \
+      UTLIST_CASTASGN(_ls_p,list);                                                             \
+      (list) = NULL;                                                                           \
+      _ls_tail = NULL;                                                                         \
+      _ls_nmerges = 0;                                                                         \
+      while (_ls_p) {                                                                          \
+        _ls_nmerges++;                                                                         \
+        _ls_q = _ls_p;                                                                         \
+        _ls_psize = 0;                                                                         \
+        for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) {                                         \
+          _ls_psize++;                                                                         \
+          UTLIST_SV(_ls_q,list); _ls_q = UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list);        \
+          if (!_ls_q) break;                                                                   \
+        }                                                                                      \
+        _ls_qsize = _ls_insize;                                                                \
+        while ((_ls_psize > 0) || ((_ls_qsize > 0) && _ls_q)) {                                \
+          if (_ls_psize == 0) {                                                                \
+            _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q =                                      \
+              UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--;                      \
+          } else if ((_ls_qsize == 0) || (!_ls_q)) {                                           \
+            _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p =                                      \
+              UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--;                      \
+          } else if (cmp(_ls_p,_ls_q) <= 0) {                                                  \
+            _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p =                                      \
+              UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--;                      \
+          } else {                                                                             \
+            _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q =                                      \
+              UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--;                      \
+          }                                                                                    \
+          if (_ls_tail) {                                                                      \
+            UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,_ls_e,next); UTLIST_RS(list); \
+          } else {                                                                             \
+            UTLIST_CASTASGN(list,_ls_e);                                                       \
+          }                                                                                    \
+          UTLIST_SV(_ls_e,list); UTLIST_PREVASGN(_ls_e,list,_ls_tail,prev); UTLIST_RS(list);   \
+          _ls_tail = _ls_e;                                                                    \
+        }                                                                                      \
+        _ls_p = _ls_q;                                                                         \
+      }                                                                                        \
+      UTLIST_CASTASGN((list)->prev, _ls_tail);                                                 \
+      UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,NULL,next); UTLIST_RS(list);     \
+      if (_ls_nmerges <= 1) {                                                                  \
+        _ls_looping=0;                                                                         \
+      }                                                                                        \
+      _ls_insize *= 2;                                                                         \
+    }                                                                                          \
+  }                                                                                            \
+} while (0)
+
+#define CDL_SORT(list, cmp)                                                                    \
+    CDL_SORT2(list, cmp, prev, next)
+
+#define CDL_SORT2(list, cmp, prev, next)                                                       \
+do {                                                                                           \
+  LDECLTYPE(list) _ls_p;                                                                       \
+  LDECLTYPE(list) _ls_q;                                                                       \
+  LDECLTYPE(list) _ls_e;                                                                       \
+  LDECLTYPE(list) _ls_tail;                                                                    \
+  LDECLTYPE(list) _ls_oldhead;                                                                 \
+  LDECLTYPE(list) _tmp;                                                                        \
+  int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping;                       \
+  if (list) {                                                                                  \
+    _ls_insize = 1;                                                                            \
+    _ls_looping = 1;                                                                           \
+    while (_ls_looping) {                                                                      \
+      UTLIST_CASTASGN(_ls_p,list);                                                             \
+      UTLIST_CASTASGN(_ls_oldhead,list);                                                       \
+      (list) = NULL;                                                                           \
+      _ls_tail = NULL;                                                                         \
+      _ls_nmerges = 0;                                                                         \
+      while (_ls_p) {                                                                          \
+        _ls_nmerges++;                                                                         \
+        _ls_q = _ls_p;                                                                         \
+        _ls_psize = 0;                                                                         \
+        for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) {                                         \
+          _ls_psize++;                                                                         \
+          UTLIST_SV(_ls_q,list);                                                               \
+          if (UTLIST_NEXT(_ls_q,list,next) == _ls_oldhead) {                                   \
+            _ls_q = NULL;                                                                      \
+          } else {                                                                             \
+            _ls_q = UTLIST_NEXT(_ls_q,list,next);                                              \
+          }                                                                                    \
+          UTLIST_RS(list);                                                                     \
+          if (!_ls_q) break;                                                                   \
+        }                                                                                      \
+        _ls_qsize = _ls_insize;                                                                \
+        while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) {                                    \
+          if (_ls_psize == 0) {                                                                \
+            _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q =                                      \
+              UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--;                      \
+            if (_ls_q == _ls_oldhead) { _ls_q = NULL; }                                        \
+          } else if (_ls_qsize == 0 || !_ls_q) {                                               \
+            _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p =                                      \
+              UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--;                      \
+            if (_ls_p == _ls_oldhead) { _ls_p = NULL; }                                        \
+          } else if (cmp(_ls_p,_ls_q) <= 0) {                                                  \
+            _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p =                                      \
+              UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--;                      \
+            if (_ls_p == _ls_oldhead) { _ls_p = NULL; }                                        \
+          } else {                                                                             \
+            _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q =                                      \
+              UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--;                      \
+            if (_ls_q == _ls_oldhead) { _ls_q = NULL; }                                        \
+          }                                                                                    \
+          if (_ls_tail) {                                                                      \
+            UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,_ls_e,next); UTLIST_RS(list); \
+          } else {                                                                             \
+            UTLIST_CASTASGN(list,_ls_e);                                                       \
+          }                                                                                    \
+          UTLIST_SV(_ls_e,list); UTLIST_PREVASGN(_ls_e,list,_ls_tail,prev); UTLIST_RS(list);   \
+          _ls_tail = _ls_e;                                                                    \
+        }                                                                                      \
+        _ls_p = _ls_q;                                                                         \
+      }                                                                                        \
+      UTLIST_CASTASGN((list)->prev,_ls_tail);                                                  \
+      UTLIST_CASTASGN(_tmp,list);                                                              \
+      UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,_tmp,next); UTLIST_RS(list);     \
+      if (_ls_nmerges <= 1) {                                                                  \
+        _ls_looping=0;                                                                         \
+      }                                                                                        \
+      _ls_insize *= 2;                                                                         \
+    }                                                                                          \
+  }                                                                                            \
+} while (0)
+
+/******************************************************************************
+ * singly linked list macros (non-circular)                                   *
+ *****************************************************************************/
+#define LL_PREPEND(head,add)                                                                   \
+    LL_PREPEND2(head,add,next)
+
+#define LL_PREPEND2(head,add,next)                                                             \
+do {                                                                                           \
+  (add)->next = (head);                                                                        \
+  (head) = (add);                                                                              \
+} while (0)
+
+#define LL_CONCAT(head1,head2)                                                                 \
+    LL_CONCAT2(head1,head2,next)
+
+#define LL_CONCAT2(head1,head2,next)                                                           \
+do {                                                                                           \
+  LDECLTYPE(head1) _tmp;                                                                       \
+  if (head1) {                                                                                 \
+    _tmp = (head1);                                                                            \
+    while (_tmp->next) { _tmp = _tmp->next; }                                                  \
+    _tmp->next=(head2);                                                                        \
+  } else {                                                                                     \
+    (head1)=(head2);                                                                           \
+  }                                                                                            \
+} while (0)
+
+#define LL_APPEND(head,add)                                                                    \
+    LL_APPEND2(head,add,next)
+
+#define LL_APPEND2(head,add,next)                                                              \
+do {                                                                                           \
+  LDECLTYPE(head) _tmp;                                                                        \
+  (add)->next=NULL;                                                                            \
+  if (head) {                                                                                  \
+    _tmp = (head);                                                                             \
+    while (_tmp->next) { _tmp = _tmp->next; }                                                  \
+    _tmp->next=(add);                                                                          \
+  } else {                                                                                     \
+    (head)=(add);                                                                              \
+  }                                                                                            \
+} while (0)
+
+#define LL_INSERT_INORDER(head,add,cmp)                                                        \
+    LL_INSERT_INORDER2(head,add,cmp,next)
+
+#define LL_INSERT_INORDER2(head,add,cmp,next)                                                  \
+do {                                                                                           \
+  LDECLTYPE(head) _tmp;                                                                        \
+  if (head) {                                                                                  \
+    LL_LOWER_BOUND2(head, _tmp, add, cmp, next);                                               \
+    LL_APPEND_ELEM2(head, _tmp, add, next);                                                    \
+  } else {                                                                                     \
+    (head) = (add);                                                                            \
+    (head)->next = NULL;                                                                       \
+  }                                                                                            \
+} while (0)
+
+#define LL_LOWER_BOUND(head,elt,like,cmp)                                                      \
+    LL_LOWER_BOUND2(head,elt,like,cmp,next)
+
+#define LL_LOWER_BOUND2(head,elt,like,cmp,next)                                                \
+  do {                                                                                         \
+    if ((head) == NULL || (cmp(head, like)) >= 0) {                                            \
+      (elt) = NULL;                                                                            \
+    } else {                                                                                   \
+      for ((elt) = (head); (elt)->next != NULL; (elt) = (elt)->next) {                         \
+        if (cmp((elt)->next, like) >= 0) {                                                     \
+          break;                                                                               \
+        }                                                                                      \
+      }                                                                                        \
+    }                                                                                          \
+  } while (0)
+
+#define LL_DELETE(head,del)                                                                    \
+    LL_DELETE2(head,del,next)
+
+#define LL_DELETE2(head,del,next)                                                              \
+do {                                                                                           \
+  LDECLTYPE(head) _tmp;                                                                        \
+  if ((head) == (del)) {                                                                       \
+    (head)=(head)->next;                                                                       \
+  } else {                                                                                     \
+    _tmp = (head);                                                                             \
+    while (_tmp->next && (_tmp->next != (del))) {                                              \
+      _tmp = _tmp->next;                                                                       \
+    }                                                                                          \
+    if (_tmp->next) {                                                                          \
+      _tmp->next = (del)->next;                                                                \
+    }                                                                                          \
+  }                                                                                            \
+} while (0)
+
+#define LL_COUNT(head,el,counter)                                                              \
+    LL_COUNT2(head,el,counter,next)                                                            \
+
+#define LL_COUNT2(head,el,counter,next)                                                        \
+do {                                                                                           \
+  (counter) = 0;                                                                               \
+  LL_FOREACH2(head,el,next) { ++(counter); }                                                   \
+} while (0)
+
+#define LL_FOREACH(head,el)                                                                    \
+    LL_FOREACH2(head,el,next)
+
+#define LL_FOREACH2(head,el,next)                                                              \
+    for ((el) = (head); el; (el) = (el)->next)
+
+#define LL_FOREACH_SAFE(head,el,tmp)                                                           \
+    LL_FOREACH_SAFE2(head,el,tmp,next)
+
+#define LL_FOREACH_SAFE2(head,el,tmp,next)                                                     \
+  for ((el) = (head); (el) && ((tmp) = (el)->next, 1); (el) = (tmp))
+
+#define LL_SEARCH_SCALAR(head,out,field,val)                                                   \
+    LL_SEARCH_SCALAR2(head,out,field,val,next)
+
+#define LL_SEARCH_SCALAR2(head,out,field,val,next)                                             \
+do {                                                                                           \
+    LL_FOREACH2(head,out,next) {                                                               \
+      if ((out)->field == (val)) break;                                                        \
+    }                                                                                          \
+} while (0)
+
+#define LL_SEARCH(head,out,elt,cmp)                                                            \
+    LL_SEARCH2(head,out,elt,cmp,next)
+
+#define LL_SEARCH2(head,out,elt,cmp,next)                                                      \
+do {                                                                                           \
+    LL_FOREACH2(head,out,next) {                                                               \
+      if ((cmp(out,elt))==0) break;                                                            \
+    }                                                                                          \
+} while (0)
+
+#define LL_REPLACE_ELEM2(head, el, add, next)                                                  \
+do {                                                                                           \
+ LDECLTYPE(head) _tmp;                                                                         \
+ assert((head) != NULL);                                                                       \
+ assert((el) != NULL);                                                                         \
+ assert((add) != NULL);                                                                        \
+ (add)->next = (el)->next;                                                                     \
+ if ((head) == (el)) {                                                                         \
+  (head) = (add);                                                                              \
+ } else {                                                                                      \
+  _tmp = (head);                                                                               \
+  while (_tmp->next && (_tmp->next != (el))) {                                                 \
+   _tmp = _tmp->next;                                                                          \
+  }                                                                                            \
+  if (_tmp->next) {                                                                            \
+    _tmp->next = (add);                                                                        \
+  }                                                                                            \
+ }                                                                                             \
+} while (0)
+
+#define LL_REPLACE_ELEM(head, el, add)                                                         \
+    LL_REPLACE_ELEM2(head, el, add, next)
+
+#define LL_PREPEND_ELEM2(head, el, add, next)                                                  \
+do {                                                                                           \
+ if (el) {                                                                                     \
+  LDECLTYPE(head) _tmp;                                                                        \
+  assert((head) != NULL);                                                                      \
+  assert((add) != NULL);                                                                       \
+  (add)->next = (el);                                                                          \
+  if ((head) == (el)) {                                                                        \
+   (head) = (add);                                                                             \
+  } else {                                                                                     \
+   _tmp = (head);                                                                              \
+   while (_tmp->next && (_tmp->next != (el))) {                                                \
+    _tmp = _tmp->next;                                                                         \
+   }                                                                                           \
+   if (_tmp->next) {                                                                           \
+     _tmp->next = (add);                                                                       \
+   }                                                                                           \
+  }                                                                                            \
+ } else {                                                                                      \
+  LL_APPEND2(head, add, next);                                                                 \
+ }                                                                                             \
+} while (0)                                                                                    \
+
+#define LL_PREPEND_ELEM(head, el, add)                                                         \
+    LL_PREPEND_ELEM2(head, el, add, next)
+
+#define LL_APPEND_ELEM2(head, el, add, next)                                                   \
+do {                                                                                           \
+ if (el) {                                                                                     \
+  assert((head) != NULL);                                                                      \
+  assert((add) != NULL);                                                                       \
+  (add)->next = (el)->next;                                                                    \
+  (el)->next = (add);                                                                          \
+ } else {                                                                                      \
+  LL_PREPEND2(head, add, next);                                                                \
+ }                                                                                             \
+} while (0)                                                                                    \
+
+#define LL_APPEND_ELEM(head, el, add)                                                          \
+    LL_APPEND_ELEM2(head, el, add, next)
+
+#ifdef NO_DECLTYPE
+/* Here are VS2008 / NO_DECLTYPE replacements for a few functions */
+
+#undef LL_CONCAT2
+#define LL_CONCAT2(head1,head2,next)                                                           \
+do {                                                                                           \
+  char *_tmp;                                                                                  \
+  if (head1) {                                                                                 \
+    _tmp = (char*)(head1);                                                                     \
+    while ((head1)->next) { (head1) = (head1)->next; }                                         \
+    (head1)->next = (head2);                                                                   \
+    UTLIST_RS(head1);                                                                          \
+  } else {                                                                                     \
+    (head1)=(head2);                                                                           \
+  }                                                                                            \
+} while (0)
+
+#undef LL_APPEND2
+#define LL_APPEND2(head,add,next)                                                              \
+do {                                                                                           \
+  if (head) {                                                                                  \
+    (add)->next = head;     /* use add->next as a temp variable */                             \
+    while ((add)->next->next) { (add)->next = (add)->next->next; }                             \
+    (add)->next->next=(add);                                                                   \
+  } else {                                                                                     \
+    (head)=(add);                                                                              \
+  }                                                                                            \
+  (add)->next=NULL;                                                                            \
+} while (0)
+
+#undef LL_INSERT_INORDER2
+#define LL_INSERT_INORDER2(head,add,cmp,next)                                                  \
+do {                                                                                           \
+  if ((head) == NULL || (cmp(head, add)) >= 0) {                                               \
+    (add)->next = (head);                                                                      \
+    (head) = (add);                                                                            \
+  } else {                                                                                     \
+    char *_tmp = (char*)(head);                                                                \
+    while ((head)->next != NULL && (cmp((head)->next, add)) < 0) {                             \
+      (head) = (head)->next;                                                                   \
+    }                                                                                          \
+    (add)->next = (head)->next;                                                                \
+    (head)->next = (add);                                                                      \
+    UTLIST_RS(head);                                                                           \
+  }                                                                                            \
+} while (0)
+
+#undef LL_DELETE2
+#define LL_DELETE2(head,del,next)                                                              \
+do {                                                                                           \
+  if ((head) == (del)) {                                                                       \
+    (head)=(head)->next;                                                                       \
+  } else {                                                                                     \
+    char *_tmp = (char*)(head);                                                                \
+    while ((head)->next && ((head)->next != (del))) {                                          \
+      (head) = (head)->next;                                                                   \
+    }                                                                                          \
+    if ((head)->next) {                                                                        \
+      (head)->next = ((del)->next);                                                            \
+    }                                                                                          \
+    UTLIST_RS(head);                                                                           \
+  }                                                                                            \
+} while (0)
+
+#undef LL_REPLACE_ELEM2
+#define LL_REPLACE_ELEM2(head, el, add, next)                                                  \
+do {                                                                                           \
+  assert((head) != NULL);                                                                      \
+  assert((el) != NULL);                                                                        \
+  assert((add) != NULL);                                                                       \
+  if ((head) == (el)) {                                                                        \
+    (head) = (add);                                                                            \
+  } else {                                                                                     \
+    (add)->next = head;                                                                        \
+    while ((add)->next->next && ((add)->next->next != (el))) {                                 \
+      (add)->next = (add)->next->next;                                                         \
+    }                                                                                          \
+    if ((add)->next->next) {                                                                   \
+      (add)->next->next = (add);                                                               \
+    }                                                                                          \
+  }                                                                                            \
+  (add)->next = (el)->next;                                                                    \
+} while (0)
+
+#undef LL_PREPEND_ELEM2
+#define LL_PREPEND_ELEM2(head, el, add, next)                                                  \
+do {                                                                                           \
+  if (el) {                                                                                    \
+    assert((head) != NULL);                                                                    \
+    assert((add) != NULL);                                                                     \
+    if ((head) == (el)) {                                                                      \
+      (head) = (add);                                                                          \
+    } else {                                                                                   \
+      (add)->next = (head);                                                                    \
+      while ((add)->next->next && ((add)->next->next != (el))) {                               \
+        (add)->next = (add)->next->next;                                                       \
+      }                                                                                        \
+      if ((add)->next->next) {                                                                 \
+        (add)->next->next = (add);                                                             \
+      }                                                                                        \
+    }                                                                                          \
+    (add)->next = (el);                                                                        \
+  } else {                                                                                     \
+    LL_APPEND2(head, add, next);                                                               \
+  }                                                                                            \
+} while (0)                                                                                    \
+
+#endif /* NO_DECLTYPE */
+
+/******************************************************************************
+ * doubly linked list macros (non-circular)                                   *
+ *****************************************************************************/
+#define DL_PREPEND(head,add)                                                                   \
+    DL_PREPEND2(head,add,prev,next)
+
+#define DL_PREPEND2(head,add,prev,next)                                                        \
+do {                                                                                           \
+ (add)->next = (head);                                                                         \
+ if (head) {                                                                                   \
+   (add)->prev = (head)->prev;                                                                 \
+   (head)->prev = (add);                                                                       \
+ } else {                                                                                      \
+   (add)->prev = (add);                                                                        \
+ }                                                                                             \
+ (head) = (add);                                                                               \
+} while (0)
+
+#define DL_APPEND(head,add)                                                                    \
+    DL_APPEND2(head,add,prev,next)
+
+#define DL_APPEND2(head,add,prev,next)                                                         \
+do {                                                                                           \
+  if (head) {                                                                                  \
+      (add)->prev = (head)->prev;                                                              \
+      (head)->prev->next = (add);                                                              \
+      (head)->prev = (add);                                                                    \
+      (add)->next = NULL;                                                                      \
+  } else {                                                                                     \
+      (head)=(add);                                                                            \
+      (head)->prev = (head);                                                                   \
+      (head)->next = NULL;                                                                     \
+  }                                                                                            \
+} while (0)
+
+#define DL_INSERT_INORDER(head,add,cmp)                                                        \
+    DL_INSERT_INORDER2(head,add,cmp,prev,next)
+
+#define DL_INSERT_INORDER2(head,add,cmp,prev,next)                                             \
+do {                                                                                           \
+  LDECLTYPE(head) _tmp;                                                                        \
+  if (head) {                                                                                  \
+    DL_LOWER_BOUND2(head, _tmp, add, cmp, next);                                               \
+    DL_APPEND_ELEM2(head, _tmp, add, prev, next);                                              \
+  } else {                                                                                     \
+    (head) = (add);                                                                            \
+    (head)->prev = (head);                                                                     \
+    (head)->next = NULL;                                                                       \
+  }                                                                                            \
+} while (0)
+
+#define DL_LOWER_BOUND(head,elt,like,cmp)                                                      \
+    DL_LOWER_BOUND2(head,elt,like,cmp,next)
+
+#define DL_LOWER_BOUND2(head,elt,like,cmp,next)                                                \
+do {                                                                                           \
+  if ((head) == NULL || (cmp(head, like)) >= 0) {                                              \
+    (elt) = NULL;                                                                              \
+  } else {                                                                                     \
+    for ((elt) = (head); (elt)->next != NULL; (elt) = (elt)->next) {                           \
+      if ((cmp((elt)->next, like)) >= 0) {                                                     \
+        break;                                                                                 \
+      }                                                                                        \
+    }                                                                                          \
+  }                                                                                            \
+} while (0)
+
+#define DL_CONCAT(head1,head2)                                                                 \
+    DL_CONCAT2(head1,head2,prev,next)
+
+#define DL_CONCAT2(head1,head2,prev,next)                                                      \
+do {                                                                                           \
+  LDECLTYPE(head1) _tmp;                                                                       \
+  if (head2) {                                                                                 \
+    if (head1) {                                                                               \
+        UTLIST_CASTASGN(_tmp, (head2)->prev);                                                  \
+        (head2)->prev = (head1)->prev;                                                         \
+        (head1)->prev->next = (head2);                                                         \
+        UTLIST_CASTASGN((head1)->prev, _tmp);                                                  \
+    } else {                                                                                   \
+        (head1)=(head2);                                                                       \
+    }                                                                                          \
+  }                                                                                            \
+} while (0)
+
+#define DL_DELETE(head,del)                                                                    \
+    DL_DELETE2(head,del,prev,next)
+
+#define DL_DELETE2(head,del,prev,next)                                                         \
+do {                                                                                           \
+  assert((head) != NULL);                                                                      \
+  assert((del)->prev != NULL);                                                                 \
+  if ((del)->prev == (del)) {                                                                  \
+      (head)=NULL;                                                                             \
+  } else if ((del)==(head)) {                                                                  \
+      (del)->next->prev = (del)->prev;                                                         \
+      (head) = (del)->next;                                                                    \
+  } else {                                                                                     \
+      (del)->prev->next = (del)->next;                                                         \
+      if ((del)->next) {                                                                       \
+          (del)->next->prev = (del)->prev;                                                     \
+      } else {                                                                                 \
+          (head)->prev = (del)->prev;                                                          \
+      }                                                                                        \
+  }                                                                                            \
+} while (0)
+
+#define DL_COUNT(head,el,counter)                                                              \
+    DL_COUNT2(head,el,counter,next)                                                            \
+
+#define DL_COUNT2(head,el,counter,next)                                                        \
+do {                                                                                           \
+  (counter) = 0;                                                                               \
+  DL_FOREACH2(head,el,next) { ++(counter); }                                                   \
+} while (0)
+
+#define DL_FOREACH(head,el)                                                                    \
+    DL_FOREACH2(head,el,next)
+
+#define DL_FOREACH2(head,el,next)                                                              \
+    for ((el) = (head); el; (el) = (el)->next)
+
+/* this version is safe for deleting the elements during iteration */
+#define DL_FOREACH_SAFE(head,el,tmp)                                                           \
+    DL_FOREACH_SAFE2(head,el,tmp,next)
+
+#define DL_FOREACH_SAFE2(head,el,tmp,next)                                                     \
+  for ((el) = (head); (el) && ((tmp) = (el)->next, 1); (el) = (tmp))
+
+/* these are identical to their singly-linked list counterparts */
+#define DL_SEARCH_SCALAR LL_SEARCH_SCALAR
+#define DL_SEARCH LL_SEARCH
+#define DL_SEARCH_SCALAR2 LL_SEARCH_SCALAR2
+#define DL_SEARCH2 LL_SEARCH2
+
+#define DL_REPLACE_ELEM2(head, el, add, prev, next)                                            \
+do {                                                                                           \
+ assert((head) != NULL);                                                                       \
+ assert((el) != NULL);                                                                         \
+ assert((add) != NULL);                                                                        \
+ if ((head) == (el)) {                                                                         \
+  (head) = (add);                                                                              \
+  (add)->next = (el)->next;                                                                    \
+  if ((el)->next == NULL) {                                                                    \
+   (add)->prev = (add);                                                                        \
+  } else {                                                                                     \
+   (add)->prev = (el)->prev;                                                                   \
+   (add)->next->prev = (add);                                                                  \
+  }                                                                                            \
+ } else {                                                                                      \
+  (add)->next = (el)->next;                                                                    \
+  (add)->prev = (el)->prev;                                                                    \
+  (add)->prev->next = (add);                                                                   \
+  if ((el)->next == NULL) {                                                                    \
+   (head)->prev = (add);                                                                       \
+  } else {                                                                                     \
+   (add)->next->prev = (add);                                                                  \
+  }                                                                                            \
+ }                                                                                             \
+} while (0)
+
+#define DL_REPLACE_ELEM(head, el, add)                                                         \
+    DL_REPLACE_ELEM2(head, el, add, prev, next)
+
+#define DL_PREPEND_ELEM2(head, el, add, prev, next)                                            \
+do {                                                                                           \
+ if (el) {                                                                                     \
+  assert((head) != NULL);                                                                      \
+  assert((add) != NULL);                                                                       \
+  (add)->next = (el);                                                                          \
+  (add)->prev = (el)->prev;                                                                    \
+  (el)->prev = (add);                                                                          \
+  if ((head) == (el)) {                                                                        \
+   (head) = (add);                                                                             \
+  } else {                                                                                     \
+   (add)->prev->next = (add);                                                                  \
+  }                                                                                            \
+ } else {                                                                                      \
+  DL_APPEND2(head, add, prev, next);                                                           \
+ }                                                                                             \
+} while (0)                                                                                    \
+
+#define DL_PREPEND_ELEM(head, el, add)                                                         \
+    DL_PREPEND_ELEM2(head, el, add, prev, next)
+
+#define DL_APPEND_ELEM2(head, el, add, prev, next)                                             \
+do {                                                                                           \
+ if (el) {                                                                                     \
+  assert((head) != NULL);                                                                      \
+  assert((add) != NULL);                                                                       \
+  (add)->next = (el)->next;                                                                    \
+  (add)->prev = (el);                                                                          \
+  (el)->next = (add);                                                                          \
+  if ((add)->next) {                                                                           \
+   (add)->next->prev = (add);                                                                  \
+  } else {                                                                                     \
+   (head)->prev = (add);                                                                       \
+  }                                                                                            \
+ } else {                                                                                      \
+  DL_PREPEND2(head, add, prev, next);                                                          \
+ }                                                                                             \
+} while (0)                                                                                    \
+
+#define DL_APPEND_ELEM(head, el, add)                                                          \
+   DL_APPEND_ELEM2(head, el, add, prev, next)
+
+#ifdef NO_DECLTYPE
+/* Here are VS2008 / NO_DECLTYPE replacements for a few functions */
+
+#undef DL_INSERT_INORDER2
+#define DL_INSERT_INORDER2(head,add,cmp,prev,next)                                             \
+do {                                                                                           \
+  if ((head) == NULL) {                                                                        \
+    (add)->prev = (add);                                                                       \
+    (add)->next = NULL;                                                                        \
+    (head) = (add);                                                                            \
+  } else if ((cmp(head, add)) >= 0) {                                                          \
+    (add)->prev = (head)->prev;                                                                \
+    (add)->next = (head);                                                                      \
+    (head)->prev = (add);                                                                      \
+    (head) = (add);                                                                            \
+  } else {                                                                                     \
+    char *_tmp = (char*)(head);                                                                \
+    while ((head)->next && (cmp((head)->next, add)) < 0) {                                     \
+      (head) = (head)->next;                                                                   \
+    }                                                                                          \
+    (add)->prev = (head);                                                                      \
+    (add)->next = (head)->next;                                                                \
+    (head)->next = (add);                                                                      \
+    UTLIST_RS(head);                                                                           \
+    if ((add)->next) {                                                                         \
+      (add)->next->prev = (add);                                                               \
+    } else {                                                                                   \
+      (head)->prev = (add);                                                                    \
+    }                                                                                          \
+  }                                                                                            \
+} while (0)
+#endif /* NO_DECLTYPE */
+
+/******************************************************************************
+ * circular doubly linked list macros                                         *
+ *****************************************************************************/
+#define CDL_APPEND(head,add)                                                                   \
+    CDL_APPEND2(head,add,prev,next)
+
+#define CDL_APPEND2(head,add,prev,next)                                                        \
+do {                                                                                           \
+ if (head) {                                                                                   \
+   (add)->prev = (head)->prev;                                                                 \
+   (add)->next = (head);                                                                       \
+   (head)->prev = (add);                                                                       \
+   (add)->prev->next = (add);                                                                  \
+ } else {                                                                                      \
+   (add)->prev = (add);                                                                        \
+   (add)->next = (add);                                                                        \
+   (head) = (add);                                                                             \
+ }                                                                                             \
+} while (0)
+
+#define CDL_PREPEND(head,add)                                                                  \
+    CDL_PREPEND2(head,add,prev,next)
+
+#define CDL_PREPEND2(head,add,prev,next)                                                       \
+do {                                                                                           \
+ if (head) {                                                                                   \
+   (add)->prev = (head)->prev;                                                                 \
+   (add)->next = (head);                                                                       \
+   (head)->prev = (add);                                                                       \
+   (add)->prev->next = (add);                                                                  \
+ } else {                                                                                      \
+   (add)->prev = (add);                                                                        \
+   (add)->next = (add);                                                                        \
+ }                                                                                             \
+ (head) = (add);                                                                               \
+} while (0)
+
+#define CDL_INSERT_INORDER(head,add,cmp)                                                       \
+    CDL_INSERT_INORDER2(head,add,cmp,prev,next)
+
+#define CDL_INSERT_INORDER2(head,add,cmp,prev,next)                                            \
+do {                                                                                           \
+  LDECLTYPE(head) _tmp;                                                                        \
+  if (head) {                                                                                  \
+    CDL_LOWER_BOUND2(head, _tmp, add, cmp, next);                                              \
+    CDL_APPEND_ELEM2(head, _tmp, add, prev, next);                                             \
+  } else {                                                                                     \
+    (head) = (add);                                                                            \
+    (head)->next = (head);                                                                     \
+    (head)->prev = (head);                                                                     \
+  }                                                                                            \
+} while (0)
+
+#define CDL_LOWER_BOUND(head,elt,like,cmp)                                                     \
+    CDL_LOWER_BOUND2(head,elt,like,cmp,next)
+
+#define CDL_LOWER_BOUND2(head,elt,like,cmp,next)                                               \
+do {                                                                                           \
+  if ((head) == NULL || (cmp(head, like)) >= 0) {                                              \
+    (elt) = NULL;                                                                              \
+  } else {                                                                                     \
+    for ((elt) = (head); (elt)->next != (head); (elt) = (elt)->next) {                         \
+      if ((cmp((elt)->next, like)) >= 0) {                                                     \
+        break;                                                                                 \
+      }                                                                                        \
+    }                                                                                          \
+  }                                                                                            \
+} while (0)
+
+#define CDL_DELETE(head,del)                                                                   \
+    CDL_DELETE2(head,del,prev,next)
+
+#define CDL_DELETE2(head,del,prev,next)                                                        \
+do {                                                                                           \
+  if (((head)==(del)) && ((head)->next == (head))) {                                           \
+      (head) = NULL;                                                                           \
+  } else {                                                                                     \
+     (del)->next->prev = (del)->prev;                                                          \
+     (del)->prev->next = (del)->next;                                                          \
+     if ((del) == (head)) (head)=(del)->next;                                                  \
+  }                                                                                            \
+} while (0)
+
+#define CDL_COUNT(head,el,counter)                                                             \
+    CDL_COUNT2(head,el,counter,next)                                                           \
+
+#define CDL_COUNT2(head, el, counter,next)                                                     \
+do {                                                                                           \
+  (counter) = 0;                                                                               \
+  CDL_FOREACH2(head,el,next) { ++(counter); }                                                  \
+} while (0)
+
+#define CDL_FOREACH(head,el)                                                                   \
+    CDL_FOREACH2(head,el,next)
+
+#define CDL_FOREACH2(head,el,next)                                                             \
+    for ((el)=(head);el;(el)=(((el)->next==(head)) ? NULL : (el)->next))
+
+#define CDL_FOREACH_SAFE(head,el,tmp1,tmp2)                                                    \
+    CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next)
+
+#define CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next)                                         \
+  for ((el) = (head), (tmp1) = (head) ? (head)->prev : NULL;                                   \
+       (el) && ((tmp2) = (el)->next, 1);                                                       \
+       (el) = ((el) == (tmp1) ? NULL : (tmp2)))
+
+#define CDL_SEARCH_SCALAR(head,out,field,val)                                                  \
+    CDL_SEARCH_SCALAR2(head,out,field,val,next)
+
+#define CDL_SEARCH_SCALAR2(head,out,field,val,next)                                            \
+do {                                                                                           \
+    CDL_FOREACH2(head,out,next) {                                                              \
+      if ((out)->field == (val)) break;                                                        \
+    }                                                                                          \
+} while (0)
+
+#define CDL_SEARCH(head,out,elt,cmp)                                                           \
+    CDL_SEARCH2(head,out,elt,cmp,next)
+
+#define CDL_SEARCH2(head,out,elt,cmp,next)                                                     \
+do {                                                                                           \
+    CDL_FOREACH2(head,out,next) {                                                              \
+      if ((cmp(out,elt))==0) break;                                                            \
+    }                                                                                          \
+} while (0)
+
+#define CDL_REPLACE_ELEM2(head, el, add, prev, next)                                           \
+do {                                                                                           \
+ assert((head) != NULL);                                                                       \
+ assert((el) != NULL);                                                                         \
+ assert((add) != NULL);                                                                        \
+ if ((el)->next == (el)) {                                                                     \
+  (add)->next = (add);                                                                         \
+  (add)->prev = (add);                                                                         \
+  (head) = (add);                                                                              \
+ } else {                                                                                      \
+  (add)->next = (el)->next;                                                                    \
+  (add)->prev = (el)->prev;                                                                    \
+  (add)->next->prev = (add);                                                                   \
+  (add)->prev->next = (add);                                                                   \
+  if ((head) == (el)) {                                                                        \
+   (head) = (add);                                                                             \
+  }                                                                                            \
+ }                                                                                             \
+} while (0)
+
+#define CDL_REPLACE_ELEM(head, el, add)                                                        \
+    CDL_REPLACE_ELEM2(head, el, add, prev, next)
+
+#define CDL_PREPEND_ELEM2(head, el, add, prev, next)                                           \
+do {                                                                                           \
+  if (el) {                                                                                    \
+    assert((head) != NULL);                                                                    \
+    assert((add) != NULL);                                                                     \
+    (add)->next = (el);                                                                        \
+    (add)->prev = (el)->prev;                                                                  \
+    (el)->prev = (add);                                                                        \
+    (add)->prev->next = (add);                                                                 \
+    if ((head) == (el)) {                                                                      \
+      (head) = (add);                                                                          \
+    }                                                                                          \
+  } else {                                                                                     \
+    CDL_APPEND2(head, add, prev, next);                                                        \
+  }                                                                                            \
+} while (0)
+
+#define CDL_PREPEND_ELEM(head, el, add)                                                        \
+    CDL_PREPEND_ELEM2(head, el, add, prev, next)
+
+#define CDL_APPEND_ELEM2(head, el, add, prev, next)                                            \
+do {                                                                                           \
+ if (el) {                                                                                     \
+  assert((head) != NULL);                                                                      \
+  assert((add) != NULL);                                                                       \
+  (add)->next = (el)->next;                                                                    \
+  (add)->prev = (el);                                                                          \
+  (el)->next = (add);                                                                          \
+  (add)->next->prev = (add);                                                                   \
+ } else {                                                                                      \
+  CDL_PREPEND2(head, add, prev, next);                                                         \
+ }                                                                                             \
+} while (0)
+
+#define CDL_APPEND_ELEM(head, el, add)                                                         \
+    CDL_APPEND_ELEM2(head, el, add, prev, next)
+
+#ifdef NO_DECLTYPE
+/* Here are VS2008 / NO_DECLTYPE replacements for a few functions */
+
+#undef CDL_INSERT_INORDER2
+#define CDL_INSERT_INORDER2(head,add,cmp,prev,next)                                            \
+do {                                                                                           \
+  if ((head) == NULL) {                                                                        \
+    (add)->prev = (add);                                                                       \
+    (add)->next = (add);                                                                       \
+    (head) = (add);                                                                            \
+  } else if ((cmp(head, add)) >= 0) {                                                          \
+    (add)->prev = (head)->prev;                                                                \
+    (add)->next = (head);                                                                      \
+    (add)->prev->next = (add);                                                                 \
+    (head)->prev = (add);                                                                      \
+    (head) = (add);                                                                            \
+  } else {                                                                                     \
+    char *_tmp = (char*)(head);                                                                \
+    while ((char*)(head)->next != _tmp && (cmp((head)->next, add)) < 0) {                      \
+      (head) = (head)->next;                                                                   \
+    }                                                                                          \
+    (add)->prev = (head);                                                                      \
+    (add)->next = (head)->next;                                                                \
+    (add)->next->prev = (add);                                                                 \
+    (head)->next = (add);                                                                      \
+    UTLIST_RS(head);                                                                           \
+  }                                                                                            \
+} while (0)
+#endif /* NO_DECLTYPE */
+
+#endif /* UTLIST_H */