Adding upstream version 1:10.5.12.upstream/1%10.5.12upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 3674 insertions, 0 deletions

diff --git a/storage/mroonga/vendor/groonga/lib/pat.c b/storage/mroonga/vendor/groonga/lib/pat.c
new file mode 100644
index 00000000..01f6108f
--- /dev/null
+++ b/storage/mroonga/vendor/groonga/lib/pat.c
@@ -0,0 +1,3674 @@
+/* -*- c-basic-offset: 2 -*- */
+/*
+  Copyright(C) 2009-2017 Brazil
+
+  This library is free software; you can redistribute it and/or
+  modify it under the terms of the GNU Lesser General Public
+  License version 2.1 as published by the Free Software Foundation.
+
+  This library is distributed in the hope that it will be useful,
+  but WITHOUT ANY WARRANTY; without even the implied warranty of
+  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+  Lesser General Public License for more details.
+
+  You should have received a copy of the GNU Lesser General Public
+  License along with this library; if not, write to the Free Software
+  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1335  USA
+*/
+#include "grn.h"
+#include <string.h>
+#include <limits.h>
+#include "grn_pat.h"
+#include "grn_output.h"
+#include "grn_util.h"
+#include "grn_normalizer.h"
+
+#define GRN_PAT_DELETED (GRN_ID_MAX + 1)
+
+#define GRN_PAT_SEGMENT_SIZE 0x400000
+#define W_OF_KEY_IN_A_SEGMENT 22
+#define W_OF_PAT_IN_A_SEGMENT 18
+#define W_OF_SIS_IN_A_SEGMENT 19
+#define KEY_MASK_IN_A_SEGMENT 0x3fffff
+#define PAT_MASK_IN_A_SEGMENT 0x3ffff
+#define SIS_MASK_IN_A_SEGMENT 0x7ffff
+#define SEG_NOT_ASSIGNED 0xffff
+#define GRN_PAT_MAX_SEGMENT 0x1000
+#define GRN_PAT_MDELINFOS (GRN_PAT_NDELINFOS - 1)
+
+#define GRN_PAT_BIN_KEY 0x70000
+
+typedef struct {
+  grn_id lr[2];
+  /*
+    lr[0]: the left node.
+    lr[1]: the right node.
+
+    The left node has 0 at the nth bit at the nth byte.
+    The right node has 1 at the nth bit at the nth byte.
+    'check' value indicate 'at the nth bit at the nth byte'.
+
+    The both available nodes has larger check value rather
+    than the current node.
+
+    The first node (PAT_AT(pat, GRN_ID_NIL, node)) has only
+    the right node and the node is the start point.
+   */
+  uint32_t key;
+  /*
+    PAT_IMD(node) == 0: key bytes offset in memory map.
+    PAT_IMD(node) == 1: the key bytes.
+   */
+  uint16_t check;
+  /*
+    nth byte: 12, nth bit: 3, terminated: 1
+
+    nth byte is different in key bytes: (check >> 4): max == 4095
+    the left most byte is the 0th byte and the right most byte is the 11th byte.
+
+    nth bit is different in nth byte: ((check >> 1) & 0b111)
+    the left most bit is the 0th bit and the right most bit is the 7th bit.
+
+    terminated: (check & 0b1)
+    terminated == 1: key is terminated.
+   */
+  uint16_t bits;
+  /* length: 13, immediate: 1, deleting: 1 */
+} pat_node;
+
+#define PAT_DELETING  (1<<1)
+#define PAT_IMMEDIATE (1<<2)
+
+#define PAT_DEL(x) ((x)->bits & PAT_DELETING)
+#define PAT_IMD(x) ((x)->bits & PAT_IMMEDIATE)
+#define PAT_LEN(x) (((x)->bits >> 3) + 1)
+#define PAT_CHK(x) ((x)->check)
+#define PAT_DEL_ON(x) ((x)->bits |= PAT_DELETING)
+#define PAT_IMD_ON(x) ((x)->bits |= PAT_IMMEDIATE)
+#define PAT_DEL_OFF(x) ((x)->bits &= ~PAT_DELETING)
+#define PAT_IMD_OFF(x) ((x)->bits &= ~PAT_IMMEDIATE)
+#define PAT_LEN_SET(x,v) ((x)->bits = ((x)->bits & ((1<<3) - 1))|(((v) - 1) << 3))
+#define PAT_CHK_SET(x,v) ((x)->check = (v))
+
+typedef struct {
+  grn_id children;
+  grn_id sibling;
+} sis_node;
+
+enum {
+  segment_key = 0,
+  segment_pat = 1,
+  segment_sis = 2
+};
+
+void grn_p_pat_node(grn_ctx *ctx, grn_pat *pat, pat_node *node);
+
+/* error utilities */
+inline static int
+grn_pat_name(grn_ctx *ctx, grn_pat *pat, char *buffer, int buffer_size)
+{
+  int name_size;
+
+  if (DB_OBJ(pat)->id == GRN_ID_NIL) {
+    grn_strcpy(buffer, buffer_size, "(anonymous)");
+    name_size = strlen(buffer);
+  } else {
+    name_size = grn_obj_name(ctx, (grn_obj *)pat, buffer, buffer_size);
+  }
+
+  return name_size;
+}
+
+/* bit operation */
+
+#define nth_bit(key,n,l) ((((key)[(n)>>4]) >> (7 - (((n)>>1) & 7))) & 1)
+
+/* segment operation */
+
+/* patricia array operation */
+
+#define PAT_AT(pat,id,n) do {\
+  int flags = 0;\
+  GRN_IO_ARRAY_AT(pat->io, segment_pat, id, &flags, n);\
+} while (0)
+
+inline static pat_node *
+pat_get(grn_ctx *ctx, grn_pat *pat, grn_id id)
+{
+  pat_node *res;
+  int flags = GRN_TABLE_ADD;
+  if (id > GRN_ID_MAX) { return NULL; }
+  GRN_IO_ARRAY_AT(pat->io, segment_pat, id, &flags, res);
+  return res;
+}
+
+/* sis operation */
+
+inline static sis_node *
+sis_at(grn_ctx *ctx, grn_pat *pat, grn_id id)
+{
+  sis_node *res;
+  int flags = 0;
+  if (id > GRN_ID_MAX) { return NULL; }
+  GRN_IO_ARRAY_AT(pat->io, segment_sis, id, &flags, res);
+  return res;
+}
+
+inline static sis_node *
+sis_get(grn_ctx *ctx, grn_pat *pat, grn_id id)
+{
+  sis_node *res;
+  int flags = GRN_TABLE_ADD;
+  if (id > GRN_ID_MAX) { return NULL; }
+  GRN_IO_ARRAY_AT(pat->io, segment_sis, id, &flags, res);
+  return res;
+}
+
+#define MAX_LEVEL 16
+
+static void
+sis_collect(grn_ctx *ctx, grn_pat *pat, grn_hash *h, grn_id id, uint32_t level)
+{
+  uint32_t *offset;
+  sis_node *sl = sis_at(ctx, pat, id);
+  if (sl) {
+    grn_id sid = sl->children;
+    while (sid && sid != id) {
+      if (grn_hash_add(ctx, h, &sid, sizeof(grn_id), (void **) &offset, NULL)) {
+        *offset = level;
+        if (level < MAX_LEVEL) { sis_collect(ctx, pat, h, sid, level + 1); }
+        if (!(sl = sis_at(ctx, pat, sid))) { break; }
+        sid = sl->sibling;
+      } else {
+        /* todo : must be handled */
+      }
+    }
+  }
+}
+
+/* key operation */
+
+#define KEY_AT(pat,pos,ptr,addp) do {\
+  int flags = addp;\
+  GRN_IO_ARRAY_AT(pat->io, segment_key, pos, &flags, ptr);\
+} while (0)
+
+inline static uint32_t
+key_put(grn_ctx *ctx, grn_pat *pat, const uint8_t *key, uint32_t len)
+{
+  uint32_t res, ts;
+//  if (len >= GRN_PAT_SEGMENT_SIZE) { return 0; /* error */ }
+  res = pat->header->curr_key;
+  if (res < GRN_PAT_MAX_TOTAL_KEY_SIZE &&
+      len > GRN_PAT_MAX_TOTAL_KEY_SIZE - res) {
+    char name[GRN_TABLE_MAX_KEY_SIZE];
+    int name_size;
+    name_size = grn_pat_name(ctx, pat, name, GRN_TABLE_MAX_KEY_SIZE);
+    ERR(GRN_NOT_ENOUGH_SPACE,
+        "[pat][key][put] total key size is over: <%.*s>: "
+        "max=%u: current=%u: new key size=%u",
+        name_size, name,
+        GRN_PAT_MAX_TOTAL_KEY_SIZE,
+        res,
+        len);
+    return 0;
+  }
+
+  ts = (res + len) >> W_OF_KEY_IN_A_SEGMENT;
+  if (res >> W_OF_KEY_IN_A_SEGMENT != ts) {
+    res = pat->header->curr_key = ts << W_OF_KEY_IN_A_SEGMENT;
+  }
+  {
+    uint8_t *dest;
+    KEY_AT(pat, res, dest, GRN_TABLE_ADD);
+    if (!dest) {
+      char name[GRN_TABLE_MAX_KEY_SIZE];
+      int name_size;
+      name_size = grn_pat_name(ctx, pat, name, GRN_TABLE_MAX_KEY_SIZE);
+      ERR(GRN_NO_MEMORY_AVAILABLE,
+          "[pat][key][put] failed to allocate memory for new key: <%.*s>: "
+          "new offset:%u key size:%u",
+          name_size, name,
+          res,
+          len);
+      return 0;
+    }
+    grn_memcpy(dest, key, len);
+  }
+  pat->header->curr_key += len;
+  return res;
+}
+
+inline static uint8_t *
+pat_node_get_key(grn_ctx *ctx, grn_pat *pat, pat_node *n)
+{
+  if (PAT_IMD(n)) {
+    return (uint8_t *) &n->key;
+  } else {
+    uint8_t *res;
+    KEY_AT(pat, n->key, res, 0);
+    return res;
+  }
+}
+
+inline static grn_rc
+pat_node_set_key(grn_ctx *ctx, grn_pat *pat, pat_node *n, const uint8_t *key, uint32_t len)
+{
+  grn_rc rc;
+  if (!key || !len) { return GRN_INVALID_ARGUMENT; }
+  PAT_LEN_SET(n, len);
+  if (len <= sizeof(uint32_t)) {
+    PAT_IMD_ON(n);
+    grn_memcpy(&n->key, key, len);
+    rc = GRN_SUCCESS;
+  } else {
+    PAT_IMD_OFF(n);
+    n->key = key_put(ctx, pat, key, len);
+    rc = ctx->rc;
+  }
+  return rc;
+}
+
+/* delinfo operation */
+
+enum {
+  /* The delinfo is currently not used. */
+  DL_EMPTY = 0,
+  /*
+   * stat->d refers to a deleting node (in a tree).
+   * The deletion requires an additional operation.
+   */
+  DL_PHASE1,
+  /*
+   * stat->d refers to a deleted node (not in a tree).
+   * The node is pending for safety.
+   */
+  DL_PHASE2
+};
+
+inline static grn_pat_delinfo *
+delinfo_search(grn_pat *pat, grn_id id)
+{
+  int i;
+  grn_pat_delinfo *di;
+  for (i = (pat->header->curr_del2) & GRN_PAT_MDELINFOS;
+       i != pat->header->curr_del;
+       i = (i + 1) & GRN_PAT_MDELINFOS) {
+    di = &pat->header->delinfos[i];
+    if (di->stat != DL_PHASE1) { continue; }
+    if (di->ld == id) { return di; }
+    if (di->d == id) { return di; }
+  }
+  return NULL;
+}
+
+inline static grn_rc
+delinfo_turn_2(grn_ctx *ctx, grn_pat *pat, grn_pat_delinfo *di)
+{
+  grn_id d, *p = NULL;
+  pat_node *ln, *dn;
+  // grn_log("delinfo_turn_2> di->d=%d di->ld=%d stat=%d", di->d, di->ld, di->stat);
+  if (di->stat != DL_PHASE1) {
+    return GRN_SUCCESS;
+  }
+  PAT_AT(pat, di->ld, ln);
+  if (!ln) {
+    return GRN_INVALID_ARGUMENT;
+  }
+  d = di->d;
+  if (!d) {
+    return GRN_INVALID_ARGUMENT;
+  }
+  PAT_AT(pat, d, dn);
+  if (!dn) {
+    return GRN_INVALID_ARGUMENT;
+  }
+  PAT_DEL_OFF(ln);
+  PAT_DEL_OFF(dn);
+  {
+    grn_id *p0;
+    pat_node *rn;
+    int c0 = -1, c;
+    uint32_t len = PAT_LEN(dn) * 16;
+    const uint8_t *key = pat_node_get_key(ctx, pat, dn);
+    if (!key) {
+      return GRN_INVALID_ARGUMENT;
+    }
+    PAT_AT(pat, 0, rn);
+    p0 = &rn->lr[1];
+    for (;;) {
+      grn_id r = *p0;
+      if (!r) {
+        break;
+      }
+      if (r == d) {
+        p = p0;
+        break;
+      }
+      PAT_AT(pat, r, rn);
+      if (!rn) {
+        return GRN_FILE_CORRUPT;
+      }
+      c = PAT_CHK(rn);
+      if (c <= c0 || len <= c) {
+        break;
+      }
+      if (c & 1) {
+        p0 = (c + 1 < len) ? &rn->lr[1] : &rn->lr[0];
+      } else {
+        p0 = &rn->lr[nth_bit((uint8_t *)key, c, len)];
+      }
+      c0 = c;
+    }
+  }
+  if (p) {
+    PAT_CHK_SET(ln, PAT_CHK(dn));
+    ln->lr[1] = dn->lr[1];
+    ln->lr[0] = dn->lr[0];
+    *p = di->ld;
+  } else {
+    /* debug */
+    int j;
+    grn_id dd;
+    grn_pat_delinfo *ddi;
+    GRN_LOG(ctx, GRN_LOG_DEBUG, "failed to find d=%d", d);
+    for (j = (pat->header->curr_del2 + 1) & GRN_PAT_MDELINFOS;
+         j != pat->header->curr_del;
+         j = (j + 1) & GRN_PAT_MDELINFOS) {
+      ddi = &pat->header->delinfos[j];
+      if (ddi->stat != DL_PHASE1) { continue; }
+      PAT_AT(pat, ddi->ld, ln);
+      if (!ln) { continue; }
+      if (!(dd = ddi->d)) { continue; }
+      if (d == ddi->ld) {
+        GRN_LOG(ctx, GRN_LOG_DEBUG, "found!!!, d(%d) become ld of (%d)", d, dd);
+      }
+    }
+    /* debug */
+  }
+  di->stat = DL_PHASE2;
+  di->d = d;
+  // grn_log("delinfo_turn_2< di->d=%d di->ld=%d", di->d, di->ld);
+  return GRN_SUCCESS;
+}
+
+inline static grn_rc
+delinfo_turn_3(grn_ctx *ctx, grn_pat *pat, grn_pat_delinfo *di)
+{
+  pat_node *dn;
+  uint32_t size;
+  if (di->stat != DL_PHASE2) { return GRN_SUCCESS; }
+  PAT_AT(pat, di->d, dn);
+  if (!dn) { return GRN_INVALID_ARGUMENT; }
+  if (di->shared) {
+    PAT_IMD_ON(dn);
+    size = 0;
+  } else {
+    if (PAT_IMD(dn)) {
+      size = 0;
+    } else {
+      size = PAT_LEN(dn);
+    }
+  }
+  di->stat = DL_EMPTY;
+  //  dn->lr[1] = GRN_PAT_DELETED;
+  dn->lr[0] = pat->header->garbages[size];
+  pat->header->garbages[size] = di->d;
+  return GRN_SUCCESS;
+}
+
+inline static grn_pat_delinfo *
+delinfo_new(grn_ctx *ctx, grn_pat *pat)
+{
+  grn_pat_delinfo *res = &pat->header->delinfos[pat->header->curr_del];
+  uint32_t n = (pat->header->curr_del + 1) & GRN_PAT_MDELINFOS;
+  int gap = ((n + GRN_PAT_NDELINFOS - pat->header->curr_del2) & GRN_PAT_MDELINFOS)
+            - (GRN_PAT_NDELINFOS / 2);
+  while (gap-- > 0) {
+    if (delinfo_turn_2(ctx, pat, &pat->header->delinfos[pat->header->curr_del2])) {
+      GRN_LOG(ctx, GRN_LOG_CRIT, "d2 failed: %d", pat->header->delinfos[pat->header->curr_del2].ld);
+    }
+    pat->header->curr_del2 = (pat->header->curr_del2 + 1) & GRN_PAT_MDELINFOS;
+  }
+  if (n == pat->header->curr_del3) {
+    if (delinfo_turn_3(ctx, pat, &pat->header->delinfos[pat->header->curr_del3])) {
+      GRN_LOG(ctx, GRN_LOG_CRIT, "d3 failed: %d", pat->header->delinfos[pat->header->curr_del3].ld);
+    }
+    pat->header->curr_del3 = (pat->header->curr_del3 + 1) & GRN_PAT_MDELINFOS;
+  }
+  pat->header->curr_del = n;
+  return res;
+}
+
+/* pat operation */
+
+inline static grn_pat *
+_grn_pat_create(grn_ctx *ctx, grn_pat *pat,
+                const char *path, uint32_t key_size,
+                uint32_t value_size, uint32_t flags) {
+  grn_io *io;
+  pat_node *node0;
+  struct grn_pat_header *header;
+  uint32_t entry_size, w_of_element;
+  grn_encoding encoding = ctx->encoding;
+  if (flags & GRN_OBJ_KEY_WITH_SIS) {
+    entry_size = sizeof(sis_node) + value_size;
+  } else {
+    entry_size = value_size;
+  }
+  for (w_of_element = 0; (1 << w_of_element) < entry_size; w_of_element++) {
+    /* nop */
+  }
+  {
+    grn_io_array_spec array_spec[3];
+    array_spec[segment_key].w_of_element = 0;
+    array_spec[segment_key].max_n_segments = 0x400;
+    array_spec[segment_pat].w_of_element = 4;
+    array_spec[segment_pat].max_n_segments = 1 << (30 - (22 - 4));
+    array_spec[segment_sis].w_of_element = w_of_element;
+    array_spec[segment_sis].max_n_segments = 1 << (30 - (22 - w_of_element));
+    io = grn_io_create_with_array(ctx, path, sizeof(struct grn_pat_header),
+                                  GRN_PAT_SEGMENT_SIZE, grn_io_auto, 3, array_spec);
+  }
+  if (!io) { return NULL; }
+  if (encoding == GRN_ENC_DEFAULT) { encoding = grn_gctx.encoding; }
+  header = grn_io_header(io);
+  grn_io_set_type(io, GRN_TABLE_PAT_KEY);
+  header->flags = flags;
+  header->encoding = encoding;
+  header->key_size = key_size;
+  header->value_size = value_size;
+  header->n_entries = 0;
+  header->curr_rec = 0;
+  header->curr_key = 0;
+  header->curr_del = 0;
+  header->curr_del2 = 0;
+  header->curr_del3 = 0;
+  header->n_garbages = 0;
+  header->tokenizer = GRN_ID_NIL;
+  if (header->flags & GRN_OBJ_KEY_NORMALIZE) {
+    header->flags &= ~GRN_OBJ_KEY_NORMALIZE;
+    pat->normalizer = grn_ctx_get(ctx, GRN_NORMALIZER_AUTO_NAME, -1);
+    header->normalizer = grn_obj_id(ctx, pat->normalizer);
+  } else {
+    pat->normalizer = NULL;
+    header->normalizer = GRN_ID_NIL;
+  }
+  header->truncated = GRN_FALSE;
+  GRN_PTR_INIT(&(pat->token_filters), GRN_OBJ_VECTOR, GRN_ID_NIL);
+  pat->io = io;
+  pat->header = header;
+  pat->key_size = key_size;
+  pat->value_size = value_size;
+  pat->tokenizer = NULL;
+  pat->encoding = encoding;
+  pat->obj.header.flags = header->flags;
+  if (!(node0 = pat_get(ctx, pat, 0))) {
+    grn_io_close(ctx, io);
+    return NULL;
+  }
+  node0->lr[1] = 0;
+  node0->lr[0] = 0;
+  node0->key = 0;
+  return pat;
+}
+
+grn_pat *
+grn_pat_create(grn_ctx *ctx, const char *path, uint32_t key_size,
+               uint32_t value_size, uint32_t flags)
+{
+  grn_pat *pat;
+  if (!(pat = GRN_CALLOC(sizeof(grn_pat)))) {
+    return NULL;
+  }
+  GRN_DB_OBJ_SET_TYPE(pat, GRN_TABLE_PAT_KEY);
+  if (!_grn_pat_create(ctx, pat, path, key_size, value_size, flags)) {
+    GRN_FREE(pat);
+    return NULL;
+  }
+  pat->cache = NULL;
+  pat->cache_size = 0;
+  pat->is_dirty = GRN_FALSE;
+  CRITICAL_SECTION_INIT(pat->lock);
+  return pat;
+}
+
+/*
+ grn_pat_cache_enable() and grn_pat_cache_disable() are not thread-safe.
+ So far, they can be used only from single threaded programs.
+ */
+
+grn_rc
+grn_pat_cache_enable(grn_ctx *ctx, grn_pat *pat, uint32_t cache_size)
+{
+  if (pat->cache || pat->cache_size) {
+    ERR(GRN_INVALID_ARGUMENT, "cache is already enabled");
+    return ctx->rc;
+  }
+  if (cache_size & (cache_size - 1)) {
+    ERR(GRN_INVALID_ARGUMENT, "cache_size(%u) must be a power of two", cache_size);
+    return ctx->rc;
+  }
+  if (!(pat->cache = GRN_CALLOC(cache_size * sizeof(grn_id)))) {
+    return ctx->rc;
+  }
+  pat->cache_size = cache_size;
+  return GRN_SUCCESS;
+}
+
+void
+grn_pat_cache_disable(grn_ctx *ctx, grn_pat *pat)
+{
+  if (pat->cache) {
+    GRN_FREE(pat->cache);
+    pat->cache_size = 0;
+    pat->cache = NULL;
+  }
+}
+
+grn_pat *
+grn_pat_open(grn_ctx *ctx, const char *path)
+{
+  grn_io *io;
+  grn_pat *pat;
+  pat_node *node0;
+  struct grn_pat_header *header;
+  uint32_t io_type;
+  io = grn_io_open(ctx, path, grn_io_auto);
+  if (!io) { return NULL; }
+  header = grn_io_header(io);
+  io_type = grn_io_get_type(io);
+  if (io_type != GRN_TABLE_PAT_KEY) {
+    ERR(GRN_INVALID_FORMAT, "[table][pat] file type must be %#04x: <%#04x>",
+        GRN_TABLE_PAT_KEY, io_type);
+    grn_io_close(ctx, io);
+    return NULL;
+  }
+  if (!(pat = GRN_MALLOC(sizeof(grn_pat)))) {
+    grn_io_close(ctx, io);
+    return NULL;
+  }
+  GRN_DB_OBJ_SET_TYPE(pat, GRN_TABLE_PAT_KEY);
+  pat->io = io;
+  pat->header = header;
+  pat->key_size = header->key_size;
+  pat->value_size = header->value_size;
+  pat->encoding = header->encoding;
+  pat->tokenizer = grn_ctx_at(ctx, header->tokenizer);
+  if (header->flags & GRN_OBJ_KEY_NORMALIZE) {
+    header->flags &= ~GRN_OBJ_KEY_NORMALIZE;
+    pat->normalizer = grn_ctx_get(ctx, GRN_NORMALIZER_AUTO_NAME, -1);
+    header->normalizer = grn_obj_id(ctx, pat->normalizer);
+  } else {
+    pat->normalizer = grn_ctx_at(ctx, header->normalizer);
+  }
+  GRN_PTR_INIT(&(pat->token_filters), GRN_OBJ_VECTOR, GRN_ID_NIL);
+  pat->obj.header.flags = header->flags;
+  PAT_AT(pat, 0, node0);
+  if (!node0) {
+    grn_io_close(ctx, io);
+    GRN_FREE(pat);
+    return NULL;
+  }
+  pat->cache = NULL;
+  pat->cache_size = 0;
+  pat->is_dirty = GRN_FALSE;
+  CRITICAL_SECTION_INIT(pat->lock);
+  return pat;
+}
+
+/*
+ * grn_pat_error_if_truncated() logs an error and returns its error code if
+ * a pat is truncated by another process.
+ * Otherwise, this function returns GRN_SUCCESS.
+ * Note that `ctx` and `pat` must be valid.
+ *
+ * FIXME: A pat should be reopened if possible.
+ */
+static grn_rc
+grn_pat_error_if_truncated(grn_ctx *ctx, grn_pat *pat)
+{
+  if (pat->header->truncated) {
+    ERR(GRN_FILE_CORRUPT,
+        "pat is truncated, please unmap or reopen the database");
+    return GRN_FILE_CORRUPT;
+  }
+  return GRN_SUCCESS;
+}
+
+grn_rc
+grn_pat_close(grn_ctx *ctx, grn_pat *pat)
+{
+  grn_rc rc;
+
+  CRITICAL_SECTION_FIN(pat->lock);
+
+  if (pat->is_dirty) {
+    uint32_t n_dirty_opens;
+    GRN_ATOMIC_ADD_EX(&(pat->header->n_dirty_opens), -1, n_dirty_opens);
+  }
+
+  if ((rc = grn_io_close(ctx, pat->io))) {
+    ERR(rc, "grn_io_close failed");
+  } else {
+    grn_pvector_fin(ctx, &pat->token_filters);
+    if (pat->cache) { grn_pat_cache_disable(ctx, pat); }
+    GRN_FREE(pat);
+  }
+
+  return rc;
+}
+
+grn_rc
+grn_pat_remove(grn_ctx *ctx, const char *path)
+{
+  if (!path) {
+    ERR(GRN_INVALID_ARGUMENT, "path is null");
+    return GRN_INVALID_ARGUMENT;
+  }
+  return grn_io_remove(ctx, path);
+}
+
+grn_rc
+grn_pat_truncate(grn_ctx *ctx, grn_pat *pat)
+{
+  grn_rc rc;
+  const char *io_path;
+  char *path;
+  uint32_t key_size, value_size, flags;
+
+  rc = grn_pat_error_if_truncated(ctx, pat);
+  if (rc != GRN_SUCCESS) {
+    return rc;
+  }
+  if ((io_path = grn_io_path(pat->io)) && *io_path != '\0') {
+    if (!(path = GRN_STRDUP(io_path))) {
+      ERR(GRN_NO_MEMORY_AVAILABLE, "cannot duplicate path: <%s>", io_path);
+      return GRN_NO_MEMORY_AVAILABLE;
+    }
+  } else {
+    path = NULL;
+  }
+  key_size = pat->key_size;
+  value_size = pat->value_size;
+  flags = pat->obj.header.flags;
+  if (path) {
+    pat->header->truncated = GRN_TRUE;
+  }
+  if ((rc = grn_io_close(ctx, pat->io))) { goto exit; }
+  grn_pvector_fin(ctx, &pat->token_filters);
+  pat->io = NULL;
+  if (path && (rc = grn_io_remove(ctx, path))) { goto exit; }
+  if (!_grn_pat_create(ctx, pat, path, key_size, value_size, flags)) {
+    rc = GRN_UNKNOWN_ERROR;
+  }
+  if (pat->cache && pat->cache_size) {
+    memset(pat->cache, 0, pat->cache_size * sizeof(grn_id));
+  }
+exit:
+  if (path) { GRN_FREE(path); }
+  return rc;
+}
+
+inline static grn_id
+_grn_pat_add(grn_ctx *ctx, grn_pat *pat, const uint8_t *key, uint32_t size, uint32_t *new, uint32_t *lkey)
+{
+  grn_id r, r0, *p0, *p1 = NULL;
+  pat_node *rn, *rn0;
+  int c, c0 = -1, c1 = -1, len;
+  uint32_t cache_id = 0;
+
+  *new = 0;
+  if (pat->cache) {
+    const uint8_t *p = key;
+    uint32_t length = size;
+    for (cache_id = 0; length--; p++) { cache_id = (cache_id * 37) + *p; }
+    cache_id &= (pat->cache_size - 1);
+    if (pat->cache[cache_id]) {
+      PAT_AT(pat, pat->cache[cache_id], rn);
+      if (rn) {
+        const uint8_t *k = pat_node_get_key(ctx, pat, rn);
+        if (k && size == PAT_LEN(rn) && !memcmp(k, key, size)) {
+          return pat->cache[cache_id];
+        }
+      }
+    }
+  }
+
+  len = (int)size * 16;
+  PAT_AT(pat, 0, rn0);
+  p0 = &rn0->lr[1];
+  if (*p0) {
+    uint32_t size2;
+    int xor, mask;
+    const uint8_t *s, *d;
+    for (;;) {
+      if (!(r0 = *p0)) {
+        if (!(s = pat_node_get_key(ctx, pat, rn0))) { return GRN_ID_NIL; }
+        size2 = PAT_LEN(rn0);
+        break;
+      }
+      PAT_AT(pat, r0, rn0);
+      if (!rn0) { return GRN_ID_NIL; }
+      if (c0 < rn0->check && rn0->check < len) {
+        c1 = c0; c0 = rn0->check;
+        p1 = p0;
+        if (c0 & 1) {
+          p0 = (c0 + 1 < len) ? &rn0->lr[1] : &rn0->lr[0];
+        } else {
+          p0 = &rn0->lr[nth_bit(key, c0, len)];
+        }
+      } else {
+        if (!(s = pat_node_get_key(ctx, pat, rn0))) { return GRN_ID_NIL; }
+        size2 = PAT_LEN(rn0);
+        if (size == size2 && !memcmp(s, key, size)) {
+          if (pat->cache) { pat->cache[cache_id] = r0; }
+          return r0;
+        }
+        break;
+      }
+    }
+    {
+      uint32_t min = size > size2 ? size2 : size;
+      for (c = 0, d = key; min && *s == *d; c += 16, s++, d++, min--);
+      if (min) {
+        for (xor = *s ^ *d, mask = 0x80; !(xor & mask); mask >>= 1, c += 2);
+      } else {
+        c--;
+      }
+    }
+    if (c == c0 && !*p0) {
+      if (c < len - 2) { c += 2; }
+    } else {
+      if (c < c0) {
+        if (c > c1) {
+          p0 = p1;
+        } else {
+          PAT_AT(pat, 0, rn0);
+          p0 = &rn0->lr[1];
+          while ((r0 = *p0)) {
+            PAT_AT(pat, r0, rn0);
+            if (!rn0) { return GRN_ID_NIL; }
+            c0 = PAT_CHK(rn0);
+            if (c < c0) { break; }
+            if (c0 & 1) {
+              p0 = (c0 + 1 < len) ? &rn0->lr[1] : &rn0->lr[0];
+            } else {
+              p0 = &rn0->lr[nth_bit(key, c0, len)];
+            }
+          }
+        }
+      }
+    }
+    if (c >= len) { return GRN_ID_NIL; }
+  } else {
+    c = len - 2;
+  }
+  {
+    uint32_t size2 = size > sizeof(uint32_t) ? size : 0;
+    if (*lkey && size2) {
+      if (pat->header->garbages[0]) {
+        r = pat->header->garbages[0];
+        PAT_AT(pat, r, rn);
+        if (!rn) { return GRN_ID_NIL; }
+        pat->header->n_entries++;
+        pat->header->n_garbages--;
+        pat->header->garbages[0] = rn->lr[0];
+      } else {
+        r = pat->header->curr_rec + 1;
+        rn = pat_get(ctx, pat, r);
+        if (!rn) { return GRN_ID_NIL; }
+        pat->header->curr_rec = r;
+        pat->header->n_entries++;
+      }
+      PAT_IMD_OFF(rn);
+      PAT_LEN_SET(rn, size);
+      rn->key = *lkey;
+    } else {
+      if (pat->header->garbages[size2]) {
+        uint8_t *keybuf;
+        r = pat->header->garbages[size2];
+        PAT_AT(pat, r, rn);
+        if (!rn) { return GRN_ID_NIL; }
+        if (!(keybuf = pat_node_get_key(ctx, pat, rn))) { return GRN_ID_NIL; }
+        pat->header->n_entries++;
+        pat->header->n_garbages--;
+        pat->header->garbages[size2] = rn->lr[0];
+        PAT_LEN_SET(rn, size);
+        grn_memcpy(keybuf, key, size);
+      } else {
+        r = pat->header->curr_rec + 1;
+        rn = pat_get(ctx, pat, r);
+        if (!rn) { return GRN_ID_NIL; }
+        if (pat_node_set_key(ctx, pat, rn, key, size)) { return GRN_ID_NIL; }
+        pat->header->curr_rec = r;
+        pat->header->n_entries++;
+      }
+      *lkey = rn->key;
+    }
+  }
+  PAT_CHK_SET(rn, c);
+  PAT_DEL_OFF(rn);
+  if ((c & 1) ? (c + 1 < len) : nth_bit(key, c, len)) {
+    rn->lr[1] = r;
+    rn->lr[0] = *p0;
+  } else {
+    rn->lr[1] = *p0;
+    rn->lr[0] = r;
+  }
+  // smp_wmb();
+  *p0 = r;
+  *new = 1;
+  if (pat->cache) { pat->cache[cache_id] = r; }
+  return r;
+}
+
+inline static grn_bool
+chop(grn_ctx *ctx, grn_pat *pat, const char **key, const char *end, uint32_t *lkey)
+{
+  size_t len = grn_charlen(ctx, *key, end);
+  if (len) {
+    *lkey += len;
+    *key += len;
+    return (end - *key) > 0;
+  } else {
+    return GRN_FALSE;
+  }
+}
+
+#define MAX_FIXED_KEY_SIZE (sizeof(int64_t))
+
+#define KEY_NEEDS_CONVERT(pat,size) \
+  (!((pat)->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) && (size) <= MAX_FIXED_KEY_SIZE)
+
+#define KEY_ENC(pat,keybuf,key,size) do {\
+  switch ((pat)->obj.header.flags & GRN_OBJ_KEY_MASK) {\
+  case GRN_OBJ_KEY_UINT :\
+    if (((pat)->obj.header.domain != GRN_DB_TOKYO_GEO_POINT) &&\
+        ((pat)->obj.header.domain != GRN_DB_WGS84_GEO_POINT)) {\
+      grn_hton((keybuf), (key), (size));\
+      break;\
+    }\
+  case GRN_OBJ_KEY_GEO_POINT :\
+    grn_gton((keybuf), (key), (size));\
+    break;\
+  case GRN_OBJ_KEY_INT :\
+    grn_hton((keybuf), (key), (size));\
+    *((uint8_t *)(keybuf)) ^= 0x80;\
+    break;\
+  case GRN_OBJ_KEY_FLOAT :\
+    if ((size) == sizeof(int64_t)) {\
+      int64_t v = *(int64_t *)(key);\
+      v ^= ((v >> 63)|(1ULL << 63));\
+      grn_hton((keybuf), &v, (size));\
+    }\
+    break;\
+  }\
+} while (0)
+
+#define KEY_DEC(pat,keybuf,key,size) do {\
+  switch ((pat)->obj.header.flags & GRN_OBJ_KEY_MASK) {\
+  case GRN_OBJ_KEY_UINT :\
+    if (((pat)->obj.header.domain != GRN_DB_TOKYO_GEO_POINT) &&\
+        ((pat)->obj.header.domain != GRN_DB_WGS84_GEO_POINT)) {\
+      grn_ntoh((keybuf), (key), (size));\
+      break;\
+    }\
+  case GRN_OBJ_KEY_GEO_POINT :\
+    grn_ntog((keybuf), (key), (size));\
+    break;\
+  case GRN_OBJ_KEY_INT :\
+    grn_ntohi((keybuf), (key), (size));\
+    break;\
+  case GRN_OBJ_KEY_FLOAT :\
+    if ((size) == sizeof(int64_t)) {\
+      int64_t v;\
+      grn_hton(&v, (key), (size));\
+      *((int64_t *)(keybuf)) = v ^ ((((int64_t)(v^(1ULL<<63)))>> 63)|(1ULL<<63)); \
+    }\
+    break;\
+  }\
+} while (0)
+
+#define KEY_ENCODE(pat,keybuf,key,size) do {\
+  if (KEY_NEEDS_CONVERT(pat,size)) {\
+    KEY_ENC((pat), (keybuf), (key), (size));\
+    (key) = (keybuf);\
+  }\
+} while (0)
+
+grn_id
+grn_pat_add(grn_ctx *ctx, grn_pat *pat, const void *key, uint32_t key_size,
+            void **value, int *added)
+{
+  uint32_t new, lkey = 0;
+  grn_id r0;
+  uint8_t keybuf[MAX_FIXED_KEY_SIZE];
+  if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
+    return GRN_ID_NIL;
+  }
+  if (!key || !key_size) { return GRN_ID_NIL; }
+  if (key_size > GRN_TABLE_MAX_KEY_SIZE) {
+    ERR(GRN_INVALID_ARGUMENT, "too long key: (%u)", key_size);
+    return GRN_ID_NIL;
+  }
+  KEY_ENCODE(pat, keybuf, key, key_size);
+  r0 = _grn_pat_add(ctx, pat, (uint8_t *)key, key_size, &new, &lkey);
+  if (r0 == GRN_ID_NIL) { return GRN_ID_NIL; }
+  if (added) { *added = new; }
+  if (r0 && (pat->obj.header.flags & GRN_OBJ_KEY_WITH_SIS) &&
+      (*((uint8_t *)key) & 0x80)) { // todo: refine!!
+    sis_node *sl, *sr;
+    grn_id l = r0, r;
+    if (new && (sl = sis_get(ctx, pat, l))) {
+      const char *sis = key, *end = sis + key_size;
+      sl->children = l;
+      sl->sibling = 0;
+      while (chop(ctx, pat, &sis, end, &lkey)) {
+        if (!(*sis & 0x80)) { break; }
+        if (!(r = _grn_pat_add(ctx, pat, (uint8_t *)sis, end - sis, &new, &lkey))) {
+          break;
+        }
+        if (!(sr = sis_get(ctx, pat, r))) { break; }
+        if (new) {
+          sl->sibling = r;
+          sr->children = l;
+          sr->sibling = 0;
+        } else {
+          sl->sibling = sr->children;
+          sr->children = l;
+          break;
+        }
+        l = r;
+        sl = sr;
+      }
+    }
+  }
+  if (r0 && value) {
+    byte *v = (byte *)sis_get(ctx, pat, r0);
+    if (pat->obj.header.flags & GRN_OBJ_KEY_WITH_SIS) {
+      *value = v + sizeof(sis_node);
+    } else {
+      *value = v;
+    }
+  }
+  return r0;
+}
+
+inline static grn_id
+_grn_pat_get(grn_ctx *ctx, grn_pat *pat, const void *key, uint32_t key_size, void **value)
+{
+  grn_id r;
+  pat_node *rn;
+  int c0 = -1, c;
+  uint32_t len = key_size * 16;
+  PAT_AT(pat, 0, rn);
+  for (r = rn->lr[1]; r;) {
+    PAT_AT(pat, r, rn);
+    if (!rn) { break; /* corrupt? */ }
+    c = PAT_CHK(rn);
+    if (len <= c) { break; }
+    if (c <= c0) {
+      const uint8_t *k = pat_node_get_key(ctx, pat, rn);
+      if (k && key_size == PAT_LEN(rn) && !memcmp(k, key, key_size)) {
+        if (value) {
+          byte *v = (byte *)sis_get(ctx, pat, r);
+          if (pat->obj.header.flags & GRN_OBJ_KEY_WITH_SIS) {
+            *value = v + sizeof(sis_node);
+          } else {
+            *value = v;
+          }
+        }
+        return r;
+      }
+      break;
+    }
+    if (c & 1) {
+      r = (c + 1 < len) ? rn->lr[1] : rn->lr[0];
+    } else {
+      r = rn->lr[nth_bit((uint8_t *)key, c, len)];
+    }
+    c0 = c;
+  }
+  return GRN_ID_NIL;
+}
+
+grn_id
+grn_pat_get(grn_ctx *ctx, grn_pat *pat, const void *key, uint32_t key_size, void **value)
+{
+  uint8_t keybuf[MAX_FIXED_KEY_SIZE];
+  if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
+    return GRN_ID_NIL;
+  }
+  KEY_ENCODE(pat, keybuf, key, key_size);
+  return _grn_pat_get(ctx, pat, key, key_size, value);
+}
+
+grn_id
+grn_pat_nextid(grn_ctx *ctx, grn_pat *pat, const void *key, uint32_t key_size)
+{
+  grn_id r = GRN_ID_NIL;
+  if (pat && key) {
+    if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
+      return GRN_ID_NIL;
+    }
+    if (!(r = pat->header->garbages[key_size > sizeof(uint32_t) ? key_size : 0])) {
+      r = pat->header->curr_rec + 1;
+    }
+  }
+  return r;
+}
+
+static void
+get_tc(grn_ctx *ctx, grn_pat *pat, grn_hash *h, pat_node *rn)
+{
+  grn_id id;
+  pat_node *node;
+  id = rn->lr[1];
+  if (id) {
+    PAT_AT(pat, id, node);
+    if (node) {
+      if (PAT_CHK(node) > PAT_CHK(rn)) {
+        get_tc(ctx, pat, h, node);
+      } else {
+        grn_hash_add(ctx, h, &id, sizeof(grn_id), NULL, NULL);
+      }
+    }
+  }
+  id = rn->lr[0];
+  if (id) {
+    PAT_AT(pat, id, node);
+    if (node) {
+      if (PAT_CHK(node) > PAT_CHK(rn)) {
+        get_tc(ctx, pat, h, node);
+      } else {
+        grn_hash_add(ctx, h, &id, sizeof(grn_id), NULL, NULL);
+      }
+    }
+  }
+}
+
+grn_rc
+grn_pat_prefix_search(grn_ctx *ctx, grn_pat *pat,
+                      const void *key, uint32_t key_size, grn_hash *h)
+{
+  int c0 = -1, c;
+  const uint8_t *k;
+  uint32_t len = key_size * 16;
+  grn_id r;
+  pat_node *rn;
+  uint8_t keybuf[MAX_FIXED_KEY_SIZE];
+  grn_rc rc = grn_pat_error_if_truncated(ctx, pat);
+  if (rc != GRN_SUCCESS) {
+    return rc;
+  }
+  KEY_ENCODE(pat, keybuf, key, key_size);
+  PAT_AT(pat, 0, rn);
+  r = rn->lr[1];
+  while (r) {
+    PAT_AT(pat, r, rn);
+    if (!rn) { return GRN_FILE_CORRUPT; }
+    c = PAT_CHK(rn);
+    if (c0 < c && c < len - 1) {
+      if (c & 1) {
+        r = (c + 1 < len) ? rn->lr[1] : rn->lr[0];
+      } else {
+        r = rn->lr[nth_bit((uint8_t *)key, c, len)];
+      }
+      c0 = c;
+      continue;
+    }
+    if (!(k = pat_node_get_key(ctx, pat, rn))) { break; }
+    if (PAT_LEN(rn) < key_size) { break; }
+    if (!memcmp(k, key, key_size)) {
+      if (c >= len - 1) {
+        get_tc(ctx, pat, h, rn);
+      } else {
+        grn_hash_add(ctx, h, &r, sizeof(grn_id), NULL, NULL);
+      }
+      return GRN_SUCCESS;
+    }
+    break;
+  }
+  return GRN_END_OF_DATA;
+}
+
+grn_hash *
+grn_pat_prefix_search2(grn_ctx *ctx, grn_pat *pat, const void *key, uint32_t key_size)
+{
+  grn_hash *h;
+  if (!pat || !key) { return NULL; }
+  if ((h = grn_hash_create(ctx, NULL, sizeof(grn_id), 0, 0))) {
+    if (grn_pat_prefix_search(ctx, pat, key, key_size, h)) {
+      grn_hash_close(ctx, h);
+      h = NULL;
+    }
+  }
+  return h;
+}
+
+grn_rc
+grn_pat_suffix_search(grn_ctx *ctx, grn_pat *pat,
+                      const void *key, uint32_t key_size, grn_hash *h)
+{
+  grn_id r;
+  if ((r = grn_pat_get(ctx, pat, key, key_size, NULL))) {
+    uint32_t *offset;
+    if (grn_hash_add(ctx, h, &r, sizeof(grn_id), (void **) &offset, NULL)) {
+      *offset = 0;
+      if (pat->obj.header.flags & GRN_OBJ_KEY_WITH_SIS) { sis_collect(ctx, pat, h, r, 1); }
+      return GRN_SUCCESS;
+    }
+  }
+  return GRN_END_OF_DATA;
+}
+
+grn_hash *
+grn_pat_suffix_search2(grn_ctx *ctx, grn_pat *pat, const void *key, uint32_t key_size)
+{
+  grn_hash *h;
+  if (!pat || !key) { return NULL; }
+  if ((h = grn_hash_create(ctx, NULL, sizeof(grn_id), sizeof(uint32_t), 0))) {
+    if (grn_pat_suffix_search(ctx, pat, key, key_size, h)) {
+      grn_hash_close(ctx, h);
+      h = NULL;
+    }
+  }
+  return h;
+}
+
+grn_id
+grn_pat_lcp_search(grn_ctx *ctx, grn_pat *pat, const void *key, uint32_t key_size)
+{
+  pat_node *rn;
+  grn_id r, r2 = GRN_ID_NIL;
+  uint32_t len = key_size * 16;
+  int c0 = -1, c;
+  if (!pat || !key) {
+    return GRN_ID_NIL;
+  }
+  if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
+    return GRN_ID_NIL;
+  }
+  if (!(pat->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE)) { return GRN_ID_NIL; }
+  PAT_AT(pat, 0, rn);
+  for (r = rn->lr[1]; r;) {
+    PAT_AT(pat, r, rn);
+    if (!rn) { break; /* corrupt? */ }
+    c = PAT_CHK(rn);
+    if (c <= c0) {
+      if (PAT_LEN(rn) <= key_size) {
+        uint8_t *p = pat_node_get_key(ctx, pat, rn);
+        if (!p) { break; }
+        if (!memcmp(p, key, PAT_LEN(rn))) { return r; }
+      }
+      break;
+    }
+    if (len <= c) { break; }
+    if (c & 1) {
+      uint8_t *p;
+      pat_node *rn0;
+      grn_id r0 = rn->lr[0];
+      PAT_AT(pat, r0, rn0);
+      if (!rn0) { break; /* corrupt? */ }
+      p = pat_node_get_key(ctx, pat, rn0);
+      if (!p) { break; }
+      if (PAT_LEN(rn0) <= key_size && !memcmp(p, key, PAT_LEN(rn0))) { r2 = r0; }
+      r = (c + 1 < len) ? rn->lr[1] : rn->lr[0];
+    } else {
+      r = rn->lr[nth_bit((uint8_t *)key, c, len)];
+    }
+    c0 = c;
+  }
+  return r2;
+}
+
+static grn_id
+common_prefix_pat_node_get(grn_ctx *ctx, grn_pat *pat, const void *key, uint32_t key_size)
+{
+  int c0 = -1, c;
+  const uint8_t *k;
+  uint32_t len = key_size * 16;
+  grn_id r;
+  pat_node *rn;
+  uint8_t keybuf[MAX_FIXED_KEY_SIZE];
+
+  KEY_ENCODE(pat, keybuf, key, key_size);
+  PAT_AT(pat, 0, rn);
+  r = rn->lr[1];
+  while (r) {
+    PAT_AT(pat, r, rn);
+    if (!rn) { return GRN_ID_NIL; }
+    c = PAT_CHK(rn);
+    if (c0 < c && c < len - 1) {
+      if (c & 1) {
+        r = (c + 1 < len) ? rn->lr[1] : rn->lr[0];
+      } else {
+        r = rn->lr[nth_bit((uint8_t *)key, c, len)];
+      }
+      c0 = c;
+      continue;
+    }
+    if (!(k = pat_node_get_key(ctx, pat, rn))) { break; }
+    if (PAT_LEN(rn) < key_size) { break; }
+    if (!memcmp(k, key, key_size)) {
+      return r;
+    }
+    break;
+  }
+  return GRN_ID_NIL;
+}
+
+typedef struct {
+  grn_id id;
+  uint16_t distance;
+} fuzzy_heap_node;
+
+typedef struct {
+  int n_entries;
+  int limit;
+  fuzzy_heap_node *nodes;
+} fuzzy_heap;
+
+static inline fuzzy_heap *
+fuzzy_heap_open(grn_ctx *ctx, int max)
+{
+  fuzzy_heap *h = GRN_MALLOC(sizeof(fuzzy_heap));
+  if (!h) { return NULL; }
+  h->nodes = GRN_MALLOC(sizeof(fuzzy_heap_node) * max);
+  if (!h->nodes) {
+    GRN_FREE(h);
+    return NULL;
+  }
+  h->n_entries = 0;
+  h->limit = max;
+  return h;
+}
+
+static inline grn_bool
+fuzzy_heap_push(grn_ctx *ctx, fuzzy_heap *h, grn_id id, uint16_t distance)
+{
+  int n, n2;
+  fuzzy_heap_node node = {id, distance};
+  fuzzy_heap_node node2;
+  if (h->n_entries >= h->limit) {
+    int max = h->limit * 2;
+    fuzzy_heap_node *nodes = GRN_REALLOC(h->nodes, sizeof(fuzzy_heap) * max);
+    if (!h) {
+      return GRN_FALSE;
+    }
+    h->limit = max;
+    h->nodes = nodes;
+  }
+  h->nodes[h->n_entries] = node;
+  n = h->n_entries++;
+  while (n) {
+    n2 = (n - 1) >> 1;
+    if (h->nodes[n2].distance <= h->nodes[n].distance) { break; }
+    node2 = h->nodes[n];
+    h->nodes[n] = h->nodes[n2];
+    h->nodes[n2] = node2;
+    n = n2;
+  }
+  return GRN_TRUE;
+}
+
+static inline void
+fuzzy_heap_close(grn_ctx *ctx, fuzzy_heap *h)
+{
+  GRN_FREE(h->nodes);
+  GRN_FREE(h);
+}
+
+#define DIST(ox,oy) (dists[((lx + 1) * (oy)) + (ox)])
+
+inline static uint16_t
+calc_edit_distance_by_offset(grn_ctx *ctx,
+                             const char *sx, const char *ex,
+                             const char *sy, const char *ey,
+                             uint16_t *dists, uint32_t lx,
+                             uint32_t offset, uint32_t max_distance,
+                             grn_bool *can_transition, int flags)
+{
+  uint32_t cx, cy, x, y;
+  const char *px, *py;
+
+  /* Skip already calculated rows */
+  for (py = sy, y = 1; py < ey && (cy = grn_charlen(ctx, py, ey)); py += cy, y++) {
+    if (py - sy >= offset) {
+      break;
+    }
+  }
+  for (; py < ey && (cy = grn_charlen(ctx, py, ey)); py += cy, y++) {
+    /* children nodes will be no longer smaller than max distance
+     * with only insertion costs.
+     * This is end of row on allocated memory. */
+    if (y > lx + max_distance) {
+      *can_transition = GRN_FALSE;
+      return max_distance + 1;
+    }
+
+    for (px = sx, x = 1; px < ex && (cx = grn_charlen(ctx, px, ex)); px += cx, x++) {
+      if (cx == cy && !memcmp(px, py, cx)) {
+        DIST(x, y) = DIST(x - 1, y - 1);
+      } else {
+        uint32_t a, b, c;
+        a = DIST(x - 1, y) + 1;
+        b = DIST(x, y - 1) + 1;
+        c = DIST(x - 1, y - 1) + 1;
+        DIST(x, y) = ((a < b) ? ((a < c) ? a : c) : ((b < c) ? b : c));
+        if (flags & GRN_TABLE_FUZZY_SEARCH_WITH_TRANSPOSITION &&
+            x > 1 && y > 1 &&
+            cx == cy &&
+            memcmp(px, py - cy, cx) == 0 &&
+            memcmp(px - cx, py, cx) == 0) {
+          uint32_t t = DIST(x - 2, y - 2) + 1;
+          DIST(x, y) = ((DIST(x, y) < t) ? DIST(x, y) : t);
+        }
+      }
+    }
+  }
+  if (lx) {
+    /* If there is no cell which is smaller than equal to max distance on end of row,
+     * children nodes will be no longer smaller than max distance */
+    *can_transition = GRN_FALSE;
+    for (x = 1; x <= lx; x++) {
+      if (DIST(x, y - 1) <= max_distance) {
+        *can_transition = GRN_TRUE;
+        break;
+      }
+    }
+  }
+  return DIST(lx, y - 1);
+}
+
+typedef struct {
+  const char *key;
+  int key_length;
+  grn_bool can_transition;
+} fuzzy_node;
+
+inline static void
+_grn_pat_fuzzy_search(grn_ctx *ctx, grn_pat *pat, grn_id id,
+                      const char *key, uint32_t key_size,
+                      uint16_t *dists, uint32_t lx,
+                      int last_check, fuzzy_node *last_node,
+                      uint32_t max_distance, int flags, fuzzy_heap *heap)
+{
+  pat_node *node = NULL;
+  int check, len;
+  const char *k;
+  uint32_t offset = 0;
+
+  PAT_AT(pat, id, node);
+  if (!node) {
+    return;
+  }
+  check = PAT_CHK(node);
+  len = PAT_LEN(node);
+  k = pat_node_get_key(ctx, pat, node);
+
+  if (check > last_check) {
+    if (len >= last_node->key_length &&
+        !memcmp(k, last_node->key, last_node->key_length)) {
+      if (last_node->can_transition == GRN_FALSE) {
+        return;
+      }
+    }
+    _grn_pat_fuzzy_search(ctx, pat, node->lr[0],
+                          key, key_size, dists, lx,
+                          check, last_node,
+                          max_distance, flags, heap);
+
+    _grn_pat_fuzzy_search(ctx, pat, node->lr[1],
+                          key, key_size, dists, lx,
+                          check, last_node,
+                          max_distance, flags, heap);
+  } else {
+    if (id) {
+      /* Set already calculated common prefix length */
+      if (len >= last_node->key_length &&
+          !memcmp(k, last_node->key, last_node->key_length)) {
+        if (last_node->can_transition == GRN_FALSE) {
+          return;
+        }
+        offset = last_node->key_length;
+      } else {
+        if (last_node->can_transition == GRN_FALSE) {
+          last_node->can_transition = GRN_TRUE;
+        }
+        if (last_node->key_length) {
+          const char *kp = k;
+          const char *ke = k + len;
+          const char *p = last_node->key;
+          const char *e = last_node->key + last_node->key_length;
+          int lp;
+          for (;p < e && kp < ke && (lp = grn_charlen(ctx, p, e));
+               p += lp, kp += lp) {
+            if (p + lp <= e && kp + lp <= ke && memcmp(p, kp, lp)) {
+              break;
+            }
+          }
+          offset = kp - k;
+        }
+      }
+      if (len - offset) {
+        uint16_t distance;
+        distance =
+          calc_edit_distance_by_offset(ctx,
+                                       key, key + key_size,
+                                       k, k + len,
+                                       dists, lx,
+                                       offset, max_distance,
+                                       &(last_node->can_transition), flags);
+        if (distance <= max_distance) {
+          fuzzy_heap_push(ctx, heap, id, distance);
+        }
+      }
+      last_node->key = k;
+      last_node->key_length = len;
+    }
+  }
+  return;
+}
+
+#define HEAP_SIZE 256
+
+grn_rc
+grn_pat_fuzzy_search(grn_ctx *ctx, grn_pat *pat,
+                     const void *key, uint32_t key_size,
+                     grn_fuzzy_search_optarg *args, grn_hash *h)
+{
+  pat_node *node;
+  grn_id id;
+  uint16_t *dists;
+  uint32_t lx, len, x, y, i;
+  const char *s = key;
+  const char *e = (const char *)key + key_size;
+  fuzzy_node last_node;
+  fuzzy_heap *heap;
+  uint32_t max_distance = 1;
+  uint32_t max_expansion = 0;
+  uint32_t prefix_match_size = 0;
+  int flags = 0;
+  grn_rc rc = grn_pat_error_if_truncated(ctx, pat);
+  if (rc != GRN_SUCCESS) {
+    return rc;
+  }
+  if (args) {
+    max_distance = args->max_distance;
+    max_expansion = args->max_expansion;
+    prefix_match_size = args->prefix_match_size;
+    flags = args->flags;
+  }
+  if (key_size > GRN_TABLE_MAX_KEY_SIZE ||
+      max_distance > GRN_TABLE_MAX_KEY_SIZE ||
+      prefix_match_size > key_size) {
+    return GRN_INVALID_ARGUMENT;
+  }
+
+  heap = fuzzy_heap_open(ctx, HEAP_SIZE);
+  if (!heap) {
+    return GRN_NO_MEMORY_AVAILABLE;
+  }
+
+  PAT_AT(pat, GRN_ID_NIL, node);
+  id = node->lr[1];
+
+  if (prefix_match_size) {
+    grn_id tid;
+    tid = common_prefix_pat_node_get(ctx, pat, key, prefix_match_size);
+    if (tid != GRN_ID_NIL) {
+      id = tid;
+    } else {
+      return GRN_END_OF_DATA;
+    }
+  }
+  for (lx = 0; s < e && (len = grn_charlen(ctx, s, e)); s += len) {
+    lx++;
+  }
+  dists = GRN_MALLOC((lx + 1) * (lx + max_distance + 1) * sizeof(uint16_t));
+  if (!dists) {
+    return GRN_NO_MEMORY_AVAILABLE;
+  }
+
+  for (x = 0; x <= lx; x++) { DIST(x, 0) = x; }
+  for (y = 0; y <= lx + max_distance ; y++) { DIST(0, y) = y; }
+
+  last_node.key = NULL;
+  last_node.key_length = 0;
+  last_node.can_transition = GRN_TRUE;
+  _grn_pat_fuzzy_search(ctx, pat, id,
+                        key, key_size, dists, lx,
+                        -1, &last_node, max_distance, flags, heap);
+  GRN_FREE(dists);
+  for (i = 0; i < heap->n_entries; i++) {
+    if (max_expansion > 0 && i >= max_expansion) {
+      break;
+    }
+    if (DB_OBJ(h)->header.flags & GRN_OBJ_WITH_SUBREC) {
+      grn_rset_recinfo *ri;
+      if (grn_hash_add(ctx, h, &(heap->nodes[i].id), sizeof(grn_id), (void **)&ri, NULL)) {
+        ri->score = max_distance - heap->nodes[i].distance + 1;
+      }
+    } else {
+      grn_hash_add(ctx, h, &(heap->nodes[i].id), sizeof(grn_id), NULL, NULL);
+    }
+  }
+  fuzzy_heap_close(ctx, heap);
+  if (grn_hash_size(ctx, h)) {
+    return GRN_SUCCESS;
+  } else {
+    return GRN_END_OF_DATA;
+  }
+}
+
+inline static grn_rc
+_grn_pat_del(grn_ctx *ctx, grn_pat *pat, const char *key, uint32_t key_size, int shared,
+             grn_table_delete_optarg *optarg)
+{
+  grn_pat_delinfo *di;
+  pat_node *rn, *rn0 = NULL, *rno = NULL;
+  int c = -1, c0 = -1, ch;
+  uint32_t len = key_size * 16;
+  grn_id r, otherside, *proot, *p, *p0 = NULL;
+
+  /* delinfo_new() must be called before searching for rn. */
+  di = delinfo_new(ctx, pat);
+  di->shared = shared;
+
+  /*
+   * Search a patricia tree for a given key.
+   * If the key exists, get its output node.
+   *
+   * rn, rn0: the output node and its previous node.
+   * rno: the other side of rn (the other destination of rn0).
+   * c, c0: checks of rn0 and its previous node.
+   * p, p0: pointers to transitions (IDs) that refer to rn and rn0.
+   */
+  PAT_AT(pat, 0, rn);
+  proot = p = &rn->lr[1];
+  for (;;) {
+    r = *p;
+    if (!r) {
+      return GRN_INVALID_ARGUMENT;
+    }
+    PAT_AT(pat, r, rn);
+    if (!rn) {
+      return GRN_FILE_CORRUPT;
+    }
+    ch = PAT_CHK(rn);
+    if (len <= ch) {
+      return GRN_INVALID_ARGUMENT;
+    }
+    if (c >= ch) {
+      /* Output node found. */
+      const uint8_t *k = pat_node_get_key(ctx, pat, rn);
+      if (!k) {
+        return GRN_INVALID_ARGUMENT;
+      }
+      if (key_size != PAT_LEN(rn) || memcmp(k, key, key_size)) {
+        return GRN_INVALID_ARGUMENT;
+      }
+      /* Given key found. */
+      break;
+    }
+    c0 = c;
+    p0 = p;
+    c = ch;
+    if (c & 1) {
+      p = (c + 1 < len) ? &rn->lr[1] : &rn->lr[0];
+    } else {
+      p = &rn->lr[nth_bit((uint8_t *)key, c, len)];
+    }
+    rn0 = rn;
+  }
+  if (optarg && optarg->func &&
+      !optarg->func(ctx, (grn_obj *)pat, r, optarg->func_arg)) {
+    return GRN_SUCCESS;
+  }
+  if (rn0->lr[0] == rn0->lr[1]) {
+    GRN_LOG(ctx, GRN_LOG_DEBUG, "*p0 (%d), rn0->lr[0] == rn0->lr[1] (%d)",
+            *p0, rn0->lr[0]);
+    return GRN_FILE_CORRUPT;
+  }
+  otherside = (rn0->lr[1] == r) ? rn0->lr[0] : rn0->lr[1];
+  if (otherside) {
+    PAT_AT(pat, otherside, rno);
+    if (!rno) {
+      return GRN_FILE_CORRUPT;
+    }
+  }
+
+  if (rn == rn0) {
+    /* The last transition (p) is a self-loop. */
+    di->stat = DL_PHASE2;
+    di->d = r;
+    if (otherside) {
+      if (c0 < PAT_CHK(rno) && PAT_CHK(rno) <= c) {
+        /* To keep rno as an output node, its check is set to zero. */
+        if (!delinfo_search(pat, otherside)) {
+          GRN_LOG(ctx, GRN_LOG_DEBUG, "no delinfo found %d", otherside);
+        }
+        PAT_CHK_SET(rno, 0);
+      }
+      if (proot == p0 && !rno->check) {
+        /*
+         * Update rno->lr because the first node, rno becomes the new first
+         * node, is not an output node even if its check is zero.
+         */
+        const uint8_t *k = pat_node_get_key(ctx, pat, rno);
+        int direction = k ? (*k >> 7) : 1;
+        rno->lr[direction] = otherside;
+        rno->lr[!direction] = 0;
+      }
+    }
+    *p0 = otherside;
+  } else if ((!rn->lr[0] && rn->lr[1] == r) ||
+             (!rn->lr[1] && rn->lr[0] == r)) {
+    /* The output node has only a disabled self-loop. */
+    di->stat = DL_PHASE2;
+    di->d = r;
+    *p = 0;
+  } else {
+    /* The last transition (p) is not a self-loop. */
+    grn_pat_delinfo *ldi = NULL, *ddi = NULL;
+    if (PAT_DEL(rn)) {
+      ldi = delinfo_search(pat, r);
+    }
+    if (PAT_DEL(rn0)) {
+      ddi = delinfo_search(pat, *p0);
+    }
+    if (ldi) {
+      PAT_DEL_OFF(rn);
+      di->stat = DL_PHASE2;
+      if (ddi) {
+        PAT_DEL_OFF(rn0);
+        ddi->stat = DL_PHASE2;
+        if (ddi == ldi) {
+          if (r != ddi->ld) {
+            GRN_LOG(ctx, GRN_LOG_ERROR, "r(%d) != ddi->ld(%d)", r, ddi->ld);
+          }
+          di->d = r;
+        } else {
+          ldi->ld = ddi->ld;
+          di->d = r;
+        }
+      } else {
+        PAT_DEL_ON(rn0);
+        ldi->ld = *p0;
+        di->d = r;
+      }
+    } else {
+      PAT_DEL_ON(rn);
+      if (ddi) {
+        if (ddi->d != *p0) {
+          GRN_LOG(ctx, GRN_LOG_ERROR, "ddi->d(%d) != *p0(%d)", ddi->d, *p0);
+        }
+        PAT_DEL_OFF(rn0);
+        ddi->stat = DL_PHASE2;
+        di->stat = DL_PHASE1;
+        di->ld = ddi->ld;
+        di->d = r;
+        /*
+        PAT_DEL_OFF(rn0);
+        ddi->d = r;
+        di->stat = DL_PHASE2;
+        di->d = *p0;
+        */
+      } else {
+        PAT_DEL_ON(rn0);
+        di->stat = DL_PHASE1;
+        di->ld = *p0;
+        di->d = r;
+        // grn_log("pat_del d=%d ld=%d stat=%d", r, *p0, DL_PHASE1);
+      }
+    }
+    if (*p0 == otherside) {
+      /* The previous node (*p0) has a self-loop (rn0 == rno). */
+      PAT_CHK_SET(rno, 0);
+      if (proot == p0) {
+        /*
+         * Update rno->lr because the first node, rno becomes the new first
+         * node, is not an output node even if its check is zero.
+         */
+        const uint8_t *k = pat_node_get_key(ctx, pat, rno);
+        int direction = k ? (*k >> 7) : 1;
+        rno->lr[direction] = otherside;
+        rno->lr[!direction] = 0;
+      }
+    } else {
+      if (otherside) {
+        if (c0 < PAT_CHK(rno) && PAT_CHK(rno) <= c) {
+          /* To keep rno as an output node, its check is set to zero. */
+          if (!delinfo_search(pat, otherside)) {
+            GRN_LOG(ctx, GRN_LOG_ERROR, "no delinfo found %d", otherside);
+          }
+          PAT_CHK_SET(rno, 0);
+        }
+        if (proot == p0 && !rno->check) {
+          /*
+           * Update rno->lr because the first node, rno becomes the new first
+           * node, is not an output node even if its check is zero.
+           */
+          const uint8_t *k = pat_node_get_key(ctx, pat, rno);
+          int direction = k ? (*k >> 7) : 1;
+          rno->lr[direction] = otherside;
+          rno->lr[!direction] = 0;
+        }
+      }
+      *p0 = otherside;
+    }
+  }
+  pat->header->n_entries--;
+  pat->header->n_garbages++;
+  return GRN_SUCCESS;
+}
+
+static grn_rc
+_grn_pat_delete(grn_ctx *ctx, grn_pat *pat, const void *key, uint32_t key_size,
+                grn_table_delete_optarg *optarg)
+{
+  if (pat->obj.header.flags & GRN_OBJ_KEY_WITH_SIS) {
+    grn_id id = grn_pat_get(ctx, pat, key, key_size, NULL);
+    if (id && grn_pat_delete_with_sis(ctx, pat, id, optarg)) {
+      return GRN_SUCCESS;
+    }
+    return GRN_INVALID_ARGUMENT;
+  }
+  return _grn_pat_del(ctx, pat, key, key_size, 0, optarg);
+}
+
+grn_rc
+grn_pat_delete(grn_ctx *ctx, grn_pat *pat, const void *key, uint32_t key_size,
+               grn_table_delete_optarg *optarg)
+{
+  grn_rc rc;
+  uint8_t keybuf[MAX_FIXED_KEY_SIZE];
+  if (!pat || !key || !key_size) { return GRN_INVALID_ARGUMENT; }
+  rc = grn_pat_error_if_truncated(ctx, pat);
+  if (rc != GRN_SUCCESS) {
+    return rc;
+  }
+  KEY_ENCODE(pat, keybuf, key, key_size);
+  return _grn_pat_delete(ctx, pat, key, key_size, optarg);
+}
+
+uint32_t
+grn_pat_size(grn_ctx *ctx, grn_pat *pat)
+{
+  if (!pat) { return GRN_INVALID_ARGUMENT; }
+  if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
+    return 0;
+  }
+  return pat->header->n_entries;
+}
+
+const char *
+_grn_pat_key(grn_ctx *ctx, grn_pat *pat, grn_id id, uint32_t *key_size)
+{
+  pat_node *node;
+  uint8_t *key;
+  if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
+    *key_size = 0;
+    return NULL;
+  }
+  PAT_AT(pat, id, node);
+  if (!node) {
+    *key_size = 0;
+    return NULL;
+  }
+  key = pat_node_get_key(ctx, pat, node);
+  if (key) {
+    *key_size = PAT_LEN(node);
+  } else {
+    *key_size = 0;
+  }
+  return (const char *)key;
+}
+
+grn_rc
+grn_pat_delete_by_id(grn_ctx *ctx, grn_pat *pat, grn_id id,
+                     grn_table_delete_optarg *optarg)
+{
+  grn_rc rc;
+  if (!pat || !id) { return GRN_INVALID_ARGUMENT; }
+  rc = grn_pat_error_if_truncated(ctx, pat);
+  if (rc != GRN_SUCCESS) {
+    return rc;
+  }
+  {
+    uint32_t key_size;
+    const char *key = _grn_pat_key(ctx, pat, id, &key_size);
+    return _grn_pat_delete(ctx, pat, key, key_size, optarg);
+  }
+}
+
+int
+grn_pat_get_key(grn_ctx *ctx, grn_pat *pat, grn_id id, void *keybuf, int bufsize)
+{
+  int len;
+  uint8_t *key;
+  pat_node *node;
+  if (!pat) { return 0; }
+  if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
+    return 0;
+  }
+  if (!id) { return 0; }
+  PAT_AT(pat, id, node);
+  if (!node) { return 0; }
+  if (!(key = pat_node_get_key(ctx, pat, node))) { return 0; }
+  len = PAT_LEN(node);
+  if (keybuf && bufsize >= len) {
+    if (KEY_NEEDS_CONVERT(pat, len)) {
+      KEY_DEC(pat, keybuf, key, len);
+    } else {
+      grn_memcpy(keybuf, key, len);
+    }
+  }
+  return len;
+}
+
+int
+grn_pat_get_key2(grn_ctx *ctx, grn_pat *pat, grn_id id, grn_obj *bulk)
+{
+  uint32_t len;
+  uint8_t *key;
+  pat_node *node;
+  if (!pat) { return GRN_INVALID_ARGUMENT; }
+  if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
+    return 0;
+  }
+  if (!id) { return 0; }
+  PAT_AT(pat, id, node);
+  if (!node) { return 0; }
+  if (!(key = pat_node_get_key(ctx, pat, node))) { return 0; }
+  len = PAT_LEN(node);
+  if (KEY_NEEDS_CONVERT(pat, len)) {
+    if (bulk->header.impl_flags & GRN_OBJ_REFER) {
+      GRN_TEXT_INIT(bulk, 0);
+    }
+    if (!grn_bulk_reserve(ctx, bulk, len)) {
+      char *curr = GRN_BULK_CURR(bulk);
+      KEY_DEC(pat, curr, key, len);
+      grn_bulk_truncate(ctx, bulk, GRN_BULK_VSIZE(bulk) + len);
+    }
+  } else {
+    if (bulk->header.impl_flags & GRN_OBJ_REFER) {
+      bulk->u.b.head = (char *)key;
+      bulk->u.b.curr = (char *)key + len;
+    } else {
+      grn_bulk_write(ctx, bulk, (char *)key, len);
+    }
+  }
+  return len;
+}
+
+int
+grn_pat_get_value(grn_ctx *ctx, grn_pat *pat, grn_id id, void *valuebuf)
+{
+  int value_size;
+  if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
+    return 0;
+  }
+  value_size = (int)pat->value_size;
+  if (value_size) {
+    byte *v = (byte *)sis_at(ctx, pat, id);
+    if (v) {
+      if (valuebuf) {
+        if (pat->obj.header.flags & GRN_OBJ_KEY_WITH_SIS) {
+          grn_memcpy(valuebuf, v + sizeof(sis_node), value_size);
+        } else {
+          grn_memcpy(valuebuf, v, value_size);
+        }
+      }
+      return value_size;
+    }
+  }
+  return 0;
+}
+
+const char *
+grn_pat_get_value_(grn_ctx *ctx, grn_pat *pat, grn_id id, uint32_t *size)
+{
+  const char *value = NULL;
+  if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
+    return NULL;
+  }
+  if ((*size = pat->value_size)) {
+    if ((value = (const char *)sis_at(ctx, pat, id))
+        && (pat->obj.header.flags & GRN_OBJ_KEY_WITH_SIS)) {
+      value += sizeof(sis_node);
+    }
+  }
+  return value;
+}
+
+grn_rc
+grn_pat_set_value(grn_ctx *ctx, grn_pat *pat, grn_id id,
+                  const void *value, int flags)
+{
+  grn_rc rc = grn_pat_error_if_truncated(ctx, pat);
+  if (rc != GRN_SUCCESS) {
+    return rc;
+  }
+  if (value) {
+    uint32_t value_size = pat->value_size;
+    if (value_size) {
+      byte *v = (byte *)sis_get(ctx, pat, id);
+      if (v) {
+        if (pat->obj.header.flags & GRN_OBJ_KEY_WITH_SIS) { v += sizeof(sis_node); }
+        switch ((flags & GRN_OBJ_SET_MASK)) {
+        case GRN_OBJ_SET :
+          grn_memcpy(v, value, value_size);
+          return GRN_SUCCESS;
+        case GRN_OBJ_INCR :
+          switch (value_size) {
+          case sizeof(int32_t) :
+            *((int32_t *)v) += *((int32_t *)value);
+            return GRN_SUCCESS;
+          case sizeof(int64_t) :
+            *((int64_t *)v) += *((int64_t *)value);
+            return GRN_SUCCESS;
+          default :
+            return GRN_INVALID_ARGUMENT;
+          }
+          break;
+        case GRN_OBJ_DECR :
+          switch (value_size) {
+          case sizeof(int32_t) :
+            *((int32_t *)v) -= *((int32_t *)value);
+            return GRN_SUCCESS;
+          case sizeof(int64_t) :
+            *((int64_t *)v) -= *((int64_t *)value);
+            return GRN_SUCCESS;
+          default :
+            return GRN_INVALID_ARGUMENT;
+          }
+          break;
+        default :
+          // todo : support other types.
+          return GRN_INVALID_ARGUMENT;
+        }
+      } else {
+        return GRN_NO_MEMORY_AVAILABLE;
+      }
+    }
+  }
+  return GRN_INVALID_ARGUMENT;
+}
+
+grn_rc
+grn_pat_info(grn_ctx *ctx, grn_pat *pat, int *key_size, unsigned int *flags,
+             grn_encoding *encoding, unsigned int *n_entries, unsigned int *file_size)
+{
+  grn_rc rc;
+  ERRCLR(NULL);
+  if (!pat) { return GRN_INVALID_ARGUMENT; }
+  rc = grn_pat_error_if_truncated(ctx, pat);
+  if (rc != GRN_SUCCESS) {
+    return rc;
+  }
+  if (key_size) { *key_size = pat->key_size; }
+  if (flags) { *flags = pat->obj.header.flags; }
+  if (encoding) { *encoding = pat->encoding; }
+  if (n_entries) { *n_entries = pat->header->n_entries; }
+  if (file_size) {
+    uint64_t tmp = 0;
+    if ((rc = grn_io_size(ctx, pat->io, &tmp))) {
+      return rc;
+    }
+    *file_size = (unsigned int) tmp; /* FIXME: inappropriate cast */
+  }
+  return GRN_SUCCESS;
+}
+
+int
+grn_pat_delete_with_sis(grn_ctx *ctx, grn_pat *pat, grn_id id,
+                        grn_table_delete_optarg *optarg)
+{
+  int level = 0, shared;
+  const char *key = NULL, *_key;
+  sis_node *sp, *ss = NULL, *si;
+  if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
+    return 0;
+  }
+  si = sis_at(ctx, pat, id);
+  while (id) {
+    pat_node *rn;
+    uint32_t key_size;
+    if ((si && si->children && si->children != id) ||
+        (optarg && optarg->func &&
+         !optarg->func(ctx, (grn_obj *)pat, id, optarg->func_arg))) {
+      break;
+    }
+    PAT_AT(pat, id, rn);
+    if (!(_key = (char *)pat_node_get_key(ctx, pat, rn))) { return 0; }
+    if (_key == key) {
+      shared = 1;
+    } else {
+      key = _key;
+      shared = 0;
+    }
+    key_size = PAT_LEN(rn);
+    if (key && key_size) { _grn_pat_del(ctx, pat, key, key_size, shared, NULL); }
+    if (si) {
+      grn_id *p, sid;
+      uint32_t lkey = 0;
+      if ((*key & 0x80) && chop(ctx, pat, &key, key + key_size, &lkey)) {
+        if ((sid = grn_pat_get(ctx, pat, key, key_size - lkey, NULL)) &&
+            (ss = sis_at(ctx, pat, sid))) {
+          for (p = &ss->children; *p && *p != sid; p = &sp->sibling) {
+            if (*p == id) {
+              *p = si->sibling;
+              break;
+            }
+            if (!(sp = sis_at(ctx, pat, *p))) { break; }
+          }
+        }
+      } else {
+        sid = GRN_ID_NIL;
+      }
+      si->sibling = 0;
+      si->children = 0;
+      id = sid;
+      si = ss;
+    } else {
+      id = GRN_ID_NIL;
+    }
+    level++;
+  }
+  if (level) {
+    uint32_t lkey = 0;
+    while (id && key) {
+      uint32_t key_size;
+      if (_grn_pat_key(ctx, pat, id, &key_size) != key) { break; }
+      {
+        pat_node *rn;
+        PAT_AT(pat, id, rn);
+        if (!rn) { break; }
+        if (lkey) {
+          rn->key = lkey;
+        } else {
+          pat_node_set_key(ctx, pat, rn, (uint8_t *)key, key_size);
+          lkey = rn->key;
+        }
+      }
+      {
+        const char *end = key + key_size;
+        if (!((*key & 0x80) && chop(ctx, pat, &key, end, &lkey))) { break; }
+        id = grn_pat_get(ctx, pat, key, end - key, NULL);
+      }
+    }
+  }
+  return level;
+}
+
+grn_id
+grn_pat_next(grn_ctx *ctx, grn_pat *pat, grn_id id)
+{
+  if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
+    return GRN_ID_NIL;
+  }
+  while (++id <= pat->header->curr_rec) {
+    uint32_t key_size;
+    const char *key = _grn_pat_key(ctx, pat, id, &key_size);
+    if (id == grn_pat_get(ctx, pat, key, key_size, NULL)) {
+      return id;
+    }
+  }
+  return GRN_ID_NIL;
+}
+
+grn_id
+grn_pat_at(grn_ctx *ctx, grn_pat *pat, grn_id id)
+{
+  uint32_t key_size;
+  const char *key = _grn_pat_key(ctx, pat, id, &key_size);
+  if (key && (id == _grn_pat_get(ctx, pat, key, key_size, NULL))) { return id; }
+  return GRN_ID_NIL;
+}
+
+grn_id
+grn_pat_curr_id(grn_ctx *ctx, grn_pat *pat)
+{
+  if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
+    return GRN_ID_NIL;
+  }
+  return pat->header->curr_rec;
+}
+
+int
+grn_pat_scan(grn_ctx *ctx, grn_pat *pat, const char *str, unsigned int str_len,
+             grn_pat_scan_hit *sh, unsigned int sh_size, const char **rest)
+{
+  int n = 0;
+  grn_id tid;
+  if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
+    return 0;
+  }
+  if (pat->normalizer) {
+    int flags =
+      GRN_STRING_REMOVE_BLANK |
+      GRN_STRING_WITH_TYPES |
+      GRN_STRING_WITH_CHECKS;
+    grn_obj *nstr = grn_string_open(ctx, str, str_len,
+                                    pat->normalizer, flags);
+    if (nstr) {
+      const short *cp = grn_string_get_checks(ctx, nstr);
+      const unsigned char *tp = grn_string_get_types(ctx, nstr);
+      unsigned int offset = 0, offset0 = 0;
+      unsigned int normalized_length_in_bytes;
+      const char *sp, *se;
+      grn_string_get_normalized(ctx, nstr, &sp, &normalized_length_in_bytes,
+                                NULL);
+      se = sp + normalized_length_in_bytes;
+      while (n < sh_size) {
+        if ((tid = grn_pat_lcp_search(ctx, pat, sp, se - sp))) {
+          const char *key;
+          uint32_t len;
+          int first_key_char_len;
+          key = _grn_pat_key(ctx, pat, tid, &len);
+          sh[n].id = tid;
+          sh[n].offset = (*cp > 0) ? offset : offset0;
+          first_key_char_len = grn_charlen(ctx, key, key + len);
+          if (sh[n].offset > 0 &&
+              GRN_CHAR_IS_BLANK(tp[-1]) &&
+              ((first_key_char_len == 1 && key[0] != ' ') ||
+               first_key_char_len > 1)){
+            /* Remove leading spaces. */
+            const char *original_str = str + sh[n].offset;
+            while (grn_charlen(ctx, original_str, str + str_len) == 1 &&
+                   original_str[0] == ' ') {
+              original_str++;
+              sh[n].offset++;
+            }
+          }
+          {
+            grn_bool blank_in_alnum = GRN_FALSE;
+            const unsigned char *start_tp = tp;
+            const unsigned char *blank_in_alnum_check_tp;
+            while (len--) {
+              if (*cp > 0) { offset0 = offset; offset += *cp; tp++; }
+              sp++; cp++;
+            }
+            sh[n].length = offset - sh[n].offset;
+            for (blank_in_alnum_check_tp = start_tp + 1;
+                 blank_in_alnum_check_tp < tp;
+                 blank_in_alnum_check_tp++) {
+#define GRN_CHAR_IS_ALNUM(char_type)                         \
+              (GRN_CHAR_TYPE(char_type) == GRN_CHAR_ALPHA || \
+               GRN_CHAR_TYPE(char_type) == GRN_CHAR_DIGIT)
+              if (GRN_CHAR_IS_BLANK(blank_in_alnum_check_tp[0]) &&
+                  GRN_CHAR_IS_ALNUM(blank_in_alnum_check_tp[-1]) &&
+                  (blank_in_alnum_check_tp + 1) < tp &&
+                  GRN_CHAR_IS_ALNUM(blank_in_alnum_check_tp[1])) {
+                blank_in_alnum = GRN_TRUE;
+              }
+#undef GRN_CHAR_IS_ALNUM
+            }
+            if (!blank_in_alnum) {
+              n++;
+            }
+          }
+        } else {
+          if (*cp > 0) { offset0 = offset; offset += *cp; tp++; }
+          do {
+            sp++; cp++;
+          } while (sp < se && !*cp);
+        }
+        if (se <= sp) { offset = str_len; break; }
+      }
+      if (rest) {
+        grn_string_get_original(ctx, nstr, rest, NULL);
+        *rest += offset;
+      }
+      grn_obj_close(ctx, nstr);
+    } else {
+      n = -1;
+      if (rest) { *rest = str; }
+    }
+  } else {
+    uint32_t len;
+    const char *sp, *se = str + str_len;
+    for (sp = str; sp < se && n < sh_size; sp += len) {
+      if ((tid = grn_pat_lcp_search(ctx, pat, sp, se - sp))) {
+        _grn_pat_key(ctx, pat, tid, &len);
+        sh[n].id = tid;
+        sh[n].offset = sp - str;
+        sh[n].length = len;
+        n++;
+      } else {
+        len = grn_charlen(ctx, sp, se);
+      }
+      if (!len) { break; }
+    }
+    if (rest) { *rest = sp; }
+  }
+  return n;
+}
+
+#define INITIAL_SIZE 512
+
+inline static void
+push(grn_pat_cursor *c, grn_id id, uint16_t check)
+{
+  grn_ctx *ctx = c->ctx;
+  grn_pat_cursor_entry *se;
+  if (c->size <= c->sp) {
+    if (c->ss) {
+      uint32_t size = c->size * 4;
+      grn_pat_cursor_entry *ss = GRN_REALLOC(c->ss, size);
+      if (!ss) { return; /* give up */ }
+      c->ss = ss;
+      c->size = size;
+    } else {
+      if (!(c->ss = GRN_MALLOC(sizeof(grn_pat_cursor_entry) * INITIAL_SIZE))) {
+        return; /* give up */
+      }
+      c->size = INITIAL_SIZE;
+    }
+  }
+  se = &c->ss[c->sp++];
+  se->id = id;
+  se->check = check;
+}
+
+inline static grn_pat_cursor_entry *
+pop(grn_pat_cursor *c)
+{
+  return c->sp ? &c->ss[--c->sp] : NULL;
+}
+
+static grn_id
+grn_pat_cursor_next_by_id(grn_ctx *ctx, grn_pat_cursor *c)
+{
+  grn_pat *pat = c->pat;
+  int dir = (c->obj.header.flags & GRN_CURSOR_DESCENDING) ? -1 : 1;
+  while (c->curr_rec != c->tail) {
+    c->curr_rec += dir;
+    if (pat->header->n_garbages) {
+      uint32_t key_size;
+      const void *key = _grn_pat_key(ctx, pat, c->curr_rec, &key_size);
+      if (_grn_pat_get(ctx, pat, key, key_size, NULL) != c->curr_rec) {
+        continue;
+      }
+    }
+    c->rest--;
+    return c->curr_rec;
+  }
+  return GRN_ID_NIL;
+}
+
+grn_id
+grn_pat_cursor_next(grn_ctx *ctx, grn_pat_cursor *c)
+{
+  pat_node *node;
+  grn_pat_cursor_entry *se;
+  if (!c->rest) { return GRN_ID_NIL; }
+  if ((c->obj.header.flags & GRN_CURSOR_BY_ID)) {
+    return grn_pat_cursor_next_by_id(ctx, c);
+  }
+  while ((se = pop(c))) {
+    grn_id id = se->id;
+    int check = se->check, ch;
+    while (id) {
+      PAT_AT(c->pat, id, node);
+      if (!node) {
+        break;
+      }
+      ch = PAT_CHK(node);
+      if (ch > check) {
+        if (c->obj.header.flags & GRN_CURSOR_DESCENDING) {
+          push(c, node->lr[0], ch);
+          id = node->lr[1];
+        } else {
+          push(c, node->lr[1], ch);
+          id = node->lr[0];
+        }
+        check = ch;
+        continue;
+      } else {
+        if (id == c->tail) {
+          c->sp = 0;
+        } else {
+          if (!c->curr_rec && c->tail) {
+            uint32_t lmin, lmax;
+            pat_node *nmin, *nmax;
+            const uint8_t *kmin, *kmax;
+            if (c->obj.header.flags & GRN_CURSOR_DESCENDING) {
+              PAT_AT(c->pat, c->tail, nmin);
+              PAT_AT(c->pat, id, nmax);
+            } else {
+              PAT_AT(c->pat, id, nmin);
+              PAT_AT(c->pat, c->tail, nmax);
+            }
+            lmin = PAT_LEN(nmin);
+            lmax = PAT_LEN(nmax);
+            kmin = pat_node_get_key(ctx, c->pat, nmin);
+            kmax = pat_node_get_key(ctx, c->pat, nmax);
+            if ((lmin < lmax) ?
+                (memcmp(kmin, kmax, lmin) > 0) :
+                (memcmp(kmin, kmax, lmax) >= 0)) {
+              c->sp = 0;
+              break;
+            }
+          }
+        }
+        c->curr_rec = id;
+        c->rest--;
+        return id;
+      }
+    }
+  }
+  return GRN_ID_NIL;
+}
+
+void
+grn_pat_cursor_close(grn_ctx *ctx, grn_pat_cursor *c)
+{
+  GRN_ASSERT(c->ctx == ctx);
+  if (c->ss) { GRN_FREE(c->ss); }
+  GRN_FREE(c);
+}
+
+inline static int
+bitcmp(const void *s1, const void *s2, int offset, int length)
+{
+  int r, rest = length + (offset & 7) - 8, bl = offset >> 3, mask = 0xff >> (offset & 7);
+  unsigned char *a = (unsigned char *)s1 + bl, *b = (unsigned char *)s2 + bl;
+  if (rest <= 0) {
+    mask &= 0xff << -rest;
+    return (*a & mask) - (*b & mask);
+  }
+  if ((r = (*a & mask) - (*b & mask))) { return r; }
+  a++; b++;
+  if ((bl = rest >> 3)) {
+    if ((r = memcmp(a, b, bl))) { return r; }
+    a += bl; b += bl;
+  }
+  mask = 0xff << (8 - (rest & 7));
+  return (*a & mask) - (*b & mask);
+}
+
+inline static grn_rc
+set_cursor_prefix(grn_ctx *ctx, grn_pat *pat, grn_pat_cursor *c,
+                  const void *key, uint32_t key_size, int flags)
+{
+  int c0 = -1, ch;
+  const uint8_t *k;
+  uint32_t len, byte_len;
+  grn_id id;
+  pat_node *node;
+  uint8_t keybuf[MAX_FIXED_KEY_SIZE];
+  if (flags & GRN_CURSOR_SIZE_BY_BIT) {
+    len = key_size * 2;
+    byte_len = key_size >> 3;
+  } else {
+    len = key_size * 16;
+    byte_len = key_size;
+  }
+  KEY_ENCODE(pat, keybuf, key, byte_len);
+  PAT_AT(pat, 0, node);
+  id = node->lr[1];
+  while (id) {
+    PAT_AT(pat, id, node);
+    if (!node) { return GRN_FILE_CORRUPT; }
+    ch = PAT_CHK(node);
+    if (c0 < ch && ch < len - 1) {
+      if (ch & 1) {
+        id = (ch + 1 < len) ? node->lr[1] : node->lr[0];
+      } else {
+        id = node->lr[nth_bit((uint8_t *)key, ch, len)];
+      }
+      c0 = ch;
+      continue;
+    }
+    if (!(k = pat_node_get_key(ctx, pat, node))) { break; }
+    if (PAT_LEN(node) < byte_len) { break; }
+    if ((flags & GRN_CURSOR_SIZE_BY_BIT)
+        ? !bitcmp(k, key, 0, key_size)
+        : !memcmp(k, key, key_size)) {
+      if (c0 < ch) {
+        if (flags & GRN_CURSOR_DESCENDING) {
+          if ((ch > len - 1) || !(flags & GRN_CURSOR_GT)) {
+            push(c, node->lr[0], ch);
+          }
+          push(c, node->lr[1], ch);
+        } else {
+          push(c, node->lr[1], ch);
+          if ((ch > len - 1) || !(flags & GRN_CURSOR_GT)) {
+            push(c, node->lr[0], ch);
+          }
+        }
+      } else {
+        if (PAT_LEN(node) * 16 > len || !(flags & GRN_CURSOR_GT)) {
+          push(c, id, ch);
+        }
+      }
+    }
+    break;
+  }
+  return GRN_SUCCESS;
+}
+
+inline static grn_rc
+set_cursor_near(grn_ctx *ctx, grn_pat *pat, grn_pat_cursor *c,
+                uint32_t min_size, const void *key, int flags)
+{
+  grn_id id;
+  pat_node *node;
+  const uint8_t *k;
+  int r, check = -1, ch;
+  uint32_t min = min_size * 16;
+  uint8_t keybuf[MAX_FIXED_KEY_SIZE];
+  KEY_ENCODE(pat, keybuf, key, pat->key_size);
+  PAT_AT(pat, 0, node);
+  for (id = node->lr[1]; id;) {
+    PAT_AT(pat, id, node);
+    if (!node) { return GRN_FILE_CORRUPT; }
+    ch = PAT_CHK(node);
+    if (ch <= check) {
+      if (check >= min) { push(c, id, check); }
+      break;
+    }
+    if ((check += 2) < ch) {
+      if (!(k = pat_node_get_key(ctx, pat, node))) { return GRN_FILE_CORRUPT; }
+      if ((r = bitcmp(key, k, check >> 1, (ch - check) >> 1))) {
+        if (ch >= min) {
+          push(c, node->lr[1], ch);
+          push(c, node->lr[0], ch);
+        }
+        break;
+      }
+    }
+    check = ch;
+    if (nth_bit((uint8_t *)key, check, pat->key_size)) {
+      if (check >= min) { push(c, node->lr[0], check); }
+      id = node->lr[1];
+    } else {
+      if (check >= min) { push(c, node->lr[1], check); }
+      id = node->lr[0];
+    }
+  }
+  return GRN_SUCCESS;
+}
+
+inline static grn_rc
+set_cursor_common_prefix(grn_ctx *ctx, grn_pat *pat, grn_pat_cursor *c,
+                         uint32_t min_size, const void *key, uint32_t key_size, int flags)
+{
+  grn_id id;
+  pat_node *node;
+  const uint8_t *k;
+  int check = -1, ch;
+  uint32_t len = key_size * 16;
+  uint8_t keybuf[MAX_FIXED_KEY_SIZE];
+  KEY_ENCODE(pat, keybuf, key, key_size);
+  PAT_AT(pat, 0, node);
+  for (id = node->lr[1]; id;) {
+    PAT_AT(pat, id, node);
+    if (!node) { return GRN_FILE_CORRUPT; }
+    ch = PAT_CHK(node);
+    if (ch <= check) {
+      if (!(k = pat_node_get_key(ctx, pat, node))) { return GRN_FILE_CORRUPT; }
+      {
+        uint32_t l = PAT_LEN(node);
+        if (min_size <= l && l <= key_size) {
+          if (!memcmp(key, k, l)) { push(c, id, check); }
+        }
+      }
+      break;
+    }
+    check = ch;
+    if (len <= check) { break; }
+    if (check & 1) {
+      grn_id id0 = node->lr[0];
+      pat_node *node0;
+      PAT_AT(pat, id0, node0);
+      if (!node0) { return GRN_FILE_CORRUPT; }
+      if (!(k = pat_node_get_key(ctx, pat, node0))) { return GRN_FILE_CORRUPT; }
+      {
+        uint32_t l = PAT_LEN(node0);
+        if (memcmp(key, k, l)) { break; }
+        if (min_size <= l) {
+          push(c, id0, check);
+        }
+      }
+      id = node->lr[1];
+    } else {
+      id = node->lr[nth_bit((uint8_t *)key, check, len)];
+    }
+  }
+  return GRN_SUCCESS;
+}
+
+inline static grn_rc
+set_cursor_ascend(grn_ctx *ctx, grn_pat *pat, grn_pat_cursor *c,
+                  const void *key, uint32_t key_size, int flags)
+{
+  grn_id id;
+  pat_node *node;
+  const uint8_t *k;
+  int r, check = -1, ch, c2;
+  uint32_t len = key_size * 16;
+  uint8_t keybuf[MAX_FIXED_KEY_SIZE];
+  KEY_ENCODE(pat, keybuf, key, key_size);
+  PAT_AT(pat, 0, node);
+  for (id = node->lr[1]; id;) {
+    PAT_AT(pat, id, node);
+    if (!node) { return GRN_FILE_CORRUPT; }
+    ch = PAT_CHK(node);
+    if (ch <= check) {
+      if (!(k = pat_node_get_key(ctx, pat, node))) { return GRN_FILE_CORRUPT; }
+      {
+        uint32_t l = PAT_LEN(node);
+        if (l == key_size) {
+          if (flags & GRN_CURSOR_GT) {
+            if (memcmp(key, k, l) < 0) { push(c, id, check); }
+          } else {
+            if (memcmp(key, k, l) <= 0) { push(c, id, check); }
+          }
+        } else if (l < key_size) {
+          if (memcmp(key, k, l) < 0) { push(c, id, check); }
+        } else {
+          if (memcmp(key, k, key_size) <= 0) { push(c, id, check); }
+        }
+      }
+      break;
+    }
+    c2 = len < ch ? len : ch;
+    if ((check += 2) < c2) {
+      if (!(k = pat_node_get_key(ctx, pat, node))) { return GRN_FILE_CORRUPT; }
+      if ((r = bitcmp(key, k, check >> 1, ((c2 + 1) >> 1) - (check >> 1)))) {
+        if (r < 0) {
+          push(c, node->lr[1], ch);
+          push(c, node->lr[0], ch);
+        }
+        break;
+      }
+    }
+    check = ch;
+    if (len <= check) {
+      push(c, node->lr[1], ch);
+      push(c, node->lr[0], ch);
+      break;
+    }
+    if (check & 1) {
+      if (check + 1 < len) {
+        id = node->lr[1];
+      } else {
+        push(c, node->lr[1], check);
+        id = node->lr[0];
+      }
+    } else {
+      if (nth_bit((uint8_t *)key, check, len)) {
+        id = node->lr[1];
+      } else {
+        push(c, node->lr[1], check);
+        id = node->lr[0];
+      }
+    }
+  }
+  return GRN_SUCCESS;
+}
+
+inline static grn_rc
+set_cursor_descend(grn_ctx *ctx, grn_pat *pat, grn_pat_cursor *c,
+                   const void *key, uint32_t key_size, int flags)
+{
+  grn_id id;
+  pat_node *node;
+  const uint8_t *k;
+  int r, check = -1, ch, c2;
+  uint32_t len = key_size * 16;
+  uint8_t keybuf[MAX_FIXED_KEY_SIZE];
+  KEY_ENCODE(pat, keybuf, key, key_size);
+  PAT_AT(pat, 0, node);
+  for (id = node->lr[1]; id;) {
+    PAT_AT(pat, id, node);
+    if (!node) { return GRN_FILE_CORRUPT; }
+    ch = PAT_CHK(node);
+    if (ch <= check) {
+      if (!(k = pat_node_get_key(ctx, pat, node))) { return GRN_FILE_CORRUPT; }
+      {
+        uint32_t l = PAT_LEN(node);
+        if (l <= key_size) {
+          if ((flags & GRN_CURSOR_LT) && l == key_size) {
+            if (memcmp(key, k, l) > 0) { push(c, id, check); }
+          } else {
+            if (memcmp(key, k, l) >= 0) { push(c, id, check); }
+          }
+        } else {
+          if (memcmp(key, k, key_size) > 0) { push(c, id, check); }
+        }
+      }
+      break;
+    }
+    c2 = len < ch ? len : ch;
+    if ((check += 2) < c2) {
+      if (!(k = pat_node_get_key(ctx, pat, node))) { return GRN_FILE_CORRUPT; }
+      if ((r = bitcmp(key, k, check >> 1, ((c2 + 1) >> 1) - (check >> 1)))) {
+        if (r >= 0) {
+          push(c, node->lr[0], ch);
+          push(c, node->lr[1], ch);
+        }
+        break;
+      }
+    }
+    check = ch;
+    if (len <= check) { break; }
+    if (check & 1) {
+      if (check + 1 < len) {
+        push(c, node->lr[0], check);
+        id = node->lr[1];
+      } else {
+        id = node->lr[0];
+      }
+    } else {
+      if (nth_bit((uint8_t *)key, check, len)) {
+        push(c, node->lr[0], check);
+        id = node->lr[1];
+      } else {
+        id = node->lr[0];
+      }
+    }
+  }
+  return GRN_SUCCESS;
+}
+
+static grn_pat_cursor *
+grn_pat_cursor_open_by_id(grn_ctx *ctx, grn_pat *pat,
+                          const void *min, uint32_t min_size,
+                          const void *max, uint32_t max_size,
+                          int offset, int limit, int flags)
+{
+  int dir;
+  grn_pat_cursor *c;
+  if (!pat || !ctx) { return NULL; }
+  if (!(c = GRN_MALLOCN(grn_pat_cursor, 1))) { return NULL; }
+  GRN_DB_OBJ_SET_TYPE(c, GRN_CURSOR_TABLE_PAT_KEY);
+  c->pat = pat;
+  c->ctx = ctx;
+  c->obj.header.flags = flags;
+  c->obj.header.domain = GRN_ID_NIL;
+  c->size = 0;
+  c->sp = 0;
+  c->ss = NULL;
+  c->tail = 0;
+  if (flags & GRN_CURSOR_DESCENDING) {
+    dir = -1;
+    if (max) {
+      if (!(c->curr_rec = grn_pat_get(ctx, pat, max, max_size, NULL))) {
+        c->tail = GRN_ID_NIL;
+        goto exit;
+      }
+      if (!(flags & GRN_CURSOR_LT)) { c->curr_rec++; }
+    } else {
+      c->curr_rec = pat->header->curr_rec + 1;
+    }
+    if (min) {
+      if (!(c->tail = grn_pat_get(ctx, pat, min, min_size, NULL))) {
+        c->curr_rec = GRN_ID_NIL;
+        goto exit;
+      }
+      if ((flags & GRN_CURSOR_GT)) { c->tail++; }
+    } else {
+      c->tail = GRN_ID_NIL + 1;
+    }
+    if (c->curr_rec < c->tail) { c->tail = c->curr_rec; }
+  } else {
+    dir = 1;
+    if (min) {
+      if (!(c->curr_rec = grn_pat_get(ctx, pat, min, min_size, NULL))) {
+        c->tail = GRN_ID_NIL;
+        goto exit;
+      }
+      if (!(flags & GRN_CURSOR_GT)) { c->curr_rec--; }
+    } else {
+      c->curr_rec = GRN_ID_NIL;
+    }
+    if (max) {
+      if (!(c->tail = grn_pat_get(ctx, pat, max, max_size, NULL))) {
+        c->curr_rec = GRN_ID_NIL;
+        goto exit;
+      }
+      if ((flags & GRN_CURSOR_LT)) { c->tail--; }
+    } else {
+      c->tail = pat->header->curr_rec;
+    }
+    if (c->tail < c->curr_rec) { c->tail = c->curr_rec; }
+  }
+  if (pat->header->n_garbages) {
+    while (offset && c->curr_rec != c->tail) {
+      uint32_t key_size;
+      const void *key;
+      c->curr_rec += dir;
+      key = _grn_pat_key(ctx, pat, c->curr_rec, &key_size);
+      if (_grn_pat_get(ctx, pat, key, key_size, NULL) == c->curr_rec) {
+        offset--;
+      }
+    }
+  } else {
+    if ((dir * (c->tail - c->curr_rec)) < offset) {
+      c->curr_rec = c->tail;
+    } else {
+      c->curr_rec += dir * offset;
+    }
+  }
+  c->rest = (limit < 0) ? GRN_ID_MAX : limit;
+exit :
+  return c;
+}
+
+static grn_rc set_cursor_rk(grn_ctx *ctx, grn_pat *pat, grn_pat_cursor *c,
+                            const void *key, uint32_t key_size, int flags);
+
+grn_pat_cursor *
+grn_pat_cursor_open(grn_ctx *ctx, grn_pat *pat,
+                    const void *min, uint32_t min_size,
+                    const void *max, uint32_t max_size,
+                    int offset, int limit, int flags)
+{
+  grn_id id;
+  pat_node *node;
+  grn_pat_cursor *c;
+  if (!pat || !ctx) { return NULL; }
+  if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
+    return NULL;
+  }
+  if ((flags & GRN_CURSOR_BY_ID)) {
+    return grn_pat_cursor_open_by_id(ctx, pat, min, min_size, max, max_size,
+                                     offset, limit, flags);
+  }
+  if (!(c = GRN_MALLOCN(grn_pat_cursor, 1))) { return NULL; }
+  GRN_DB_OBJ_SET_TYPE(c, GRN_CURSOR_TABLE_PAT_KEY);
+  c->pat = pat;
+  c->ctx = ctx;
+  c->size = 0;
+  c->sp = 0;
+  c->ss = NULL;
+  c->tail = 0;
+  c->rest = GRN_ID_MAX;
+  c->curr_rec = GRN_ID_NIL;
+  c->obj.header.domain = GRN_ID_NIL;
+  if (flags & GRN_CURSOR_PREFIX) {
+    if (max && max_size) {
+      if ((pat->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE)) {
+        set_cursor_common_prefix(ctx, pat, c, min_size, max, max_size, flags);
+      } else {
+        set_cursor_near(ctx, pat, c, min_size, max, flags);
+      }
+      goto exit;
+    } else {
+      if (min && min_size) {
+        if (flags & GRN_CURSOR_RK) {
+          set_cursor_rk(ctx, pat, c, min, min_size, flags);
+        } else {
+          set_cursor_prefix(ctx, pat, c, min, min_size, flags);
+        }
+        goto exit;
+      }
+    }
+  }
+  if (flags & GRN_CURSOR_DESCENDING) {
+    if (min && min_size) {
+      set_cursor_ascend(ctx, pat, c, min, min_size, flags);
+      c->obj.header.flags = GRN_CURSOR_ASCENDING;
+      c->tail = grn_pat_cursor_next(ctx, c);
+      c->sp = 0;
+      if (!c->tail) { goto exit; }
+    }
+    if (max && max_size) {
+      set_cursor_descend(ctx, pat, c, max, max_size, flags);
+    } else {
+      PAT_AT(pat, 0, node);
+      if (!node) {
+        grn_pat_cursor_close(ctx, c);
+        return NULL;
+      }
+      if ((id = node->lr[1])) {
+        PAT_AT(pat, id, node);
+        if (node) {
+          int ch = PAT_CHK(node);
+          push(c, node->lr[0], ch);
+          push(c, node->lr[1], ch);
+        }
+      }
+    }
+  } else {
+    if (max && max_size) {
+      set_cursor_descend(ctx, pat, c, max, max_size, flags);
+      c->obj.header.flags = GRN_CURSOR_DESCENDING;
+      c->tail = grn_pat_cursor_next(ctx, c);
+      c->sp = 0;
+      if (!c->tail) { goto exit; }
+    }
+    if (min && min_size) {
+      set_cursor_ascend(ctx, pat, c, min, min_size, flags);
+    } else {
+      PAT_AT(pat, 0, node);
+      if (!node) {
+        grn_pat_cursor_close(ctx, c);
+        return NULL;
+      }
+      if ((id = node->lr[1])) {
+        PAT_AT(pat, id, node);
+        if (node) {
+          int ch = PAT_CHK(node);
+          push(c, node->lr[1], ch);
+          push(c, node->lr[0], ch);
+        }
+      }
+    }
+  }
+exit :
+  c->obj.header.flags = flags;
+  c->curr_rec = GRN_ID_NIL;
+  while (offset--) { grn_pat_cursor_next(ctx, c); }
+  c->rest = (limit < 0) ? GRN_ID_MAX : limit;
+  return c;
+}
+
+int
+grn_pat_cursor_get_key(grn_ctx *ctx, grn_pat_cursor *c, void **key)
+{
+  *key = c->curr_key;
+  return grn_pat_get_key(ctx, c->pat, c->curr_rec, *key, GRN_TABLE_MAX_KEY_SIZE);
+}
+
+int
+grn_pat_cursor_get_value(grn_ctx *ctx, grn_pat_cursor *c, void **value)
+{
+  int value_size = (int)c->pat->value_size;
+  if (value_size) {
+    byte *v = (byte *)sis_at(ctx, c->pat, c->curr_rec);
+    if (v) {
+      if (c->pat->obj.header.flags & GRN_OBJ_KEY_WITH_SIS) {
+        *value = v + sizeof(sis_node);
+      } else {
+        *value = v;
+      }
+    } else {
+      *value = NULL;
+    }
+  }
+  return value_size;
+}
+
+int
+grn_pat_cursor_get_key_value(grn_ctx *ctx, grn_pat_cursor *c,
+                             void **key, uint32_t *key_size, void **value)
+{
+  int value_size = (int)c->pat->value_size;
+  if (key_size) {
+    *key_size = (uint32_t) grn_pat_get_key(ctx, c->pat, c->curr_rec, c->curr_key,
+                                           GRN_TABLE_MAX_KEY_SIZE);
+    if (key) { *key = c->curr_key; }
+  }
+  if (value && value_size) {
+    byte *v = (byte *)sis_at(ctx, c->pat, c->curr_rec);
+    if (v) {
+      if (c->pat->obj.header.flags & GRN_OBJ_KEY_WITH_SIS) {
+        *value = v + sizeof(sis_node);
+      } else {
+        *value = v;
+      }
+    } else {
+      *value = NULL;
+    }
+  }
+  return value_size;
+}
+
+grn_rc
+grn_pat_cursor_set_value(grn_ctx *ctx, grn_pat_cursor *c,
+                         const void *value, int flags)
+{
+  return grn_pat_set_value(ctx, c->pat, c->curr_rec, value, flags);
+}
+
+grn_rc
+grn_pat_cursor_delete(grn_ctx *ctx, grn_pat_cursor *c,
+                      grn_table_delete_optarg *optarg)
+{
+  return grn_pat_delete_by_id(ctx, c->pat, c->curr_rec, optarg);
+}
+
+void
+grn_pat_check(grn_ctx *ctx, grn_pat *pat)
+{
+  char buf[8];
+  struct grn_pat_header *h = pat->header;
+  if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
+    return;
+  }
+  GRN_OUTPUT_ARRAY_OPEN("RESULT", 1);
+  GRN_OUTPUT_MAP_OPEN("SUMMARY", 23);
+  GRN_OUTPUT_CSTR("flags");
+  grn_itoh(h->flags, buf, 8);
+  GRN_OUTPUT_STR(buf, 8);
+  GRN_OUTPUT_CSTR("key size");
+  GRN_OUTPUT_INT64(h->key_size);
+  GRN_OUTPUT_CSTR("value_size");
+  GRN_OUTPUT_INT64(h->value_size);
+  GRN_OUTPUT_CSTR("tokenizer");
+  GRN_OUTPUT_INT64(h->tokenizer);
+  GRN_OUTPUT_CSTR("normalizer");
+  GRN_OUTPUT_INT64(h->normalizer);
+  GRN_OUTPUT_CSTR("n_entries");
+  GRN_OUTPUT_INT64(h->n_entries);
+  GRN_OUTPUT_CSTR("curr_rec");
+  GRN_OUTPUT_INT64(h->curr_rec);
+  GRN_OUTPUT_CSTR("curr_key");
+  GRN_OUTPUT_INT64(h->curr_key);
+  GRN_OUTPUT_CSTR("curr_del");
+  GRN_OUTPUT_INT64(h->curr_del);
+  GRN_OUTPUT_CSTR("curr_del2");
+  GRN_OUTPUT_INT64(h->curr_del2);
+  GRN_OUTPUT_CSTR("curr_del3");
+  GRN_OUTPUT_INT64(h->curr_del3);
+  GRN_OUTPUT_CSTR("n_garbages");
+  GRN_OUTPUT_INT64(h->n_garbages);
+  GRN_OUTPUT_MAP_CLOSE();
+  GRN_OUTPUT_ARRAY_CLOSE();
+}
+
+/* utilities */
+void
+grn_p_pat_node(grn_ctx *ctx, grn_pat *pat, pat_node *node)
+{
+  uint8_t *key = NULL;
+
+  if (!node) {
+    printf("#<pat_node:(null)>\n");
+    return;
+  }
+
+  if (PAT_IMD(node)) {
+    key = (uint8_t *)&(node->key);
+  } else {
+    KEY_AT(pat, node->key, key, 0);
+  }
+
+  printf("#<pat_node:%p "
+         "left:%u "
+         "right:%u "
+         "deleting:%s "
+         "immediate:%s "
+         "length:%u "
+         "nth-byte:%u "
+         "nth-bit:%u "
+         "terminated:%s "
+         "key:<%.*s>"
+         ">\n",
+         node,
+         node->lr[0],
+         node->lr[1],
+         PAT_DEL(node) ? "true" : "false",
+         PAT_IMD(node) ? "true" : "false",
+         PAT_LEN(node),
+         PAT_CHK(node) >> 4,
+         (PAT_CHK(node) >> 1) & 0x7,
+         (PAT_CHK(node) & 0x1) ? "true" : "false",
+         PAT_LEN(node),
+         (char *)key);
+}
+
+static void
+grn_pat_inspect_check(grn_ctx *ctx, grn_obj *buf, int check)
+{
+  GRN_TEXT_PUTS(ctx, buf, "{");
+  grn_text_lltoa(ctx, buf, check >> 4);
+  GRN_TEXT_PUTS(ctx, buf, ",");
+  grn_text_lltoa(ctx, buf, (check >> 1) & 7);
+  GRN_TEXT_PUTS(ctx, buf, ",");
+  grn_text_lltoa(ctx, buf, check & 1);
+  GRN_TEXT_PUTS(ctx, buf, "}");
+}
+
+static void
+grn_pat_inspect_node(grn_ctx *ctx, grn_pat *pat, grn_id id, int check,
+                     grn_obj *key_buf, int indent, const char *prefix,
+                     grn_obj *buf)
+{
+  pat_node *node = NULL;
+  int i, c;
+
+  PAT_AT(pat, id, node);
+  c = PAT_CHK(node);
+
+  for (i = 0; i < indent; i++) {
+    GRN_TEXT_PUTC(ctx, buf, ' ');
+  }
+  GRN_TEXT_PUTS(ctx, buf, prefix);
+  grn_text_lltoa(ctx, buf, id);
+  grn_pat_inspect_check(ctx, buf, c);
+
+  if (c > check) {
+    GRN_TEXT_PUTS(ctx, buf, "\n");
+    grn_pat_inspect_node(ctx, pat, node->lr[0], c, key_buf,
+                         indent + 2, "L:", buf);
+    GRN_TEXT_PUTS(ctx, buf, "\n");
+    grn_pat_inspect_node(ctx, pat, node->lr[1], c, key_buf,
+                         indent + 2, "R:", buf);
+  } else if (id) {
+    int key_size;
+    uint8_t *key;
+
+    key_size = PAT_LEN(node);
+    GRN_BULK_REWIND(key_buf);
+    grn_bulk_space(ctx, key_buf, key_size);
+    grn_pat_get_key(ctx, pat, id, GRN_BULK_HEAD(key_buf), key_size);
+    GRN_TEXT_PUTS(ctx, buf, "(");
+    grn_inspect(ctx, buf, key_buf);
+    GRN_TEXT_PUTS(ctx, buf, ")");
+
+    GRN_TEXT_PUTS(ctx, buf, "[");
+    key = pat_node_get_key(ctx, pat, node);
+    for (i = 0; i < key_size; i++) {
+      int j;
+      uint8_t byte = key[i];
+      if (i != 0) {
+        GRN_TEXT_PUTS(ctx, buf, " ");
+      }
+      for (j = 0; j < 8; j++) {
+        grn_text_lltoa(ctx, buf, (byte >> (7 - j)) & 1);
+      }
+    }
+    GRN_TEXT_PUTS(ctx, buf, "]");
+  }
+}
+
+void
+grn_pat_inspect_nodes(grn_ctx *ctx, grn_pat *pat, grn_obj *buf)
+{
+  pat_node *node;
+  grn_obj key_buf;
+
+  GRN_TEXT_PUTS(ctx, buf, "{");
+  PAT_AT(pat, GRN_ID_NIL, node);
+  if (node->lr[1]) {
+    GRN_TEXT_PUTS(ctx, buf, "\n");
+    GRN_OBJ_INIT(&key_buf, GRN_BULK, 0, pat->obj.header.domain);
+    grn_pat_inspect_node(ctx, pat, node->lr[1], -1, &key_buf, 0, "", buf);
+    GRN_OBJ_FIN(ctx, &key_buf);
+    GRN_TEXT_PUTS(ctx, buf, "\n");
+  }
+  GRN_TEXT_PUTS(ctx, buf, "}");
+}
+
+static void
+grn_pat_cursor_inspect_entries(grn_ctx *ctx, grn_pat_cursor *c, grn_obj *buf)
+{
+  int i;
+  GRN_TEXT_PUTS(ctx, buf, "[");
+  for (i = 0; i < c->sp; i++) {
+    grn_pat_cursor_entry *e = c->ss + i;
+    if (i != 0) {
+      GRN_TEXT_PUTS(ctx, buf, ", ");
+    }
+    GRN_TEXT_PUTS(ctx, buf, "[");
+    grn_text_lltoa(ctx, buf, e->id);
+    GRN_TEXT_PUTS(ctx, buf, ",");
+    grn_pat_inspect_check(ctx, buf, e->check);
+    GRN_TEXT_PUTS(ctx, buf, "]");
+  }
+  GRN_TEXT_PUTS(ctx, buf, "]");
+}
+
+void
+grn_pat_cursor_inspect(grn_ctx *ctx, grn_pat_cursor *c, grn_obj *buf)
+{
+  GRN_TEXT_PUTS(ctx, buf, "#<cursor:pat:");
+  grn_inspect_name(ctx, buf, (grn_obj *)(c->pat));
+
+  GRN_TEXT_PUTS(ctx, buf, " ");
+  GRN_TEXT_PUTS(ctx, buf, "current:");
+  grn_text_lltoa(ctx, buf, c->curr_rec);
+
+  GRN_TEXT_PUTS(ctx, buf, " ");
+  GRN_TEXT_PUTS(ctx, buf, "tail:");
+  grn_text_lltoa(ctx, buf, c->tail);
+
+  GRN_TEXT_PUTS(ctx, buf, " ");
+  GRN_TEXT_PUTS(ctx, buf, "flags:");
+  if (c->obj.header.flags & GRN_CURSOR_PREFIX) {
+    GRN_TEXT_PUTS(ctx, buf, "prefix");
+  } else {
+    if (c->obj.header.flags & GRN_CURSOR_DESCENDING) {
+      GRN_TEXT_PUTS(ctx, buf, "descending");
+    } else {
+      GRN_TEXT_PUTS(ctx, buf, "ascending");
+    }
+    GRN_TEXT_PUTS(ctx, buf, "|");
+    if (c->obj.header.flags & GRN_CURSOR_GT) {
+      GRN_TEXT_PUTS(ctx, buf, "greater-than");
+    } else {
+      GRN_TEXT_PUTS(ctx, buf, "greater");
+    }
+    GRN_TEXT_PUTS(ctx, buf, "|");
+    if (c->obj.header.flags & GRN_CURSOR_LT) {
+      GRN_TEXT_PUTS(ctx, buf, "less-than");
+    } else {
+      GRN_TEXT_PUTS(ctx, buf, "less");
+    }
+    if (c->obj.header.flags & GRN_CURSOR_BY_ID) {
+      GRN_TEXT_PUTS(ctx, buf, "|by-id");
+    }
+    if (c->obj.header.flags & GRN_CURSOR_BY_KEY) {
+      GRN_TEXT_PUTS(ctx, buf, "|by-key");
+    }
+  }
+
+  GRN_TEXT_PUTS(ctx, buf, " ");
+  GRN_TEXT_PUTS(ctx, buf, "rest:");
+  grn_text_lltoa(ctx, buf, c->rest);
+
+  GRN_TEXT_PUTS(ctx, buf, " ");
+  GRN_TEXT_PUTS(ctx, buf, "entries:");
+  grn_pat_cursor_inspect_entries(ctx, c, buf);
+
+  GRN_TEXT_PUTS(ctx, buf, ">");
+}
+
+typedef struct {
+  uint8_t code;
+  uint8_t next;
+  uint8_t emit;
+  uint8_t attr;
+} rk_tree_node;
+
+static uint16_t rk_str_idx[] = {
+  0x0003, 0x0006, 0x0009, 0x000c, 0x0012, 0x0015, 0x0018, 0x001e, 0x0024, 0x002a,
+  0x0030, 0x0036, 0x003c, 0x0042, 0x0048, 0x004e, 0x0054, 0x005a, 0x0060, 0x0066,
+  0x006c, 0x0072, 0x0078, 0x007e, 0x0084, 0x008a, 0x0090, 0x0096, 0x009c, 0x00a2,
+  0x00a8, 0x00ae, 0x00b4, 0x00ba, 0x00c0, 0x00c3, 0x00c6, 0x00c9, 0x00cc, 0x00cf,
+  0x00d2, 0x00d5, 0x00db, 0x00e1, 0x00e7, 0x00ea, 0x00f0, 0x00f6, 0x00fc, 0x00ff,
+  0x0105, 0x0108, 0x010e, 0x0111, 0x0114, 0x0117, 0x011a, 0x011d, 0x0120, 0x0123,
+  0x0129, 0x012f, 0x0135, 0x013b, 0x013e, 0x0144, 0x014a, 0x0150, 0x0156, 0x0159,
+  0x015c, 0x015f, 0x0162, 0x0165, 0x0168, 0x016b, 0x016e, 0x0171, 0x0177, 0x017d,
+  0x0183, 0x0189, 0x018c, 0x0192, 0x0198, 0x019e, 0x01a1, 0x01a4, 0x01aa, 0x01b0,
+  0x01b6, 0x01bc, 0x01bf, 0x01c2, 0x01c8, 0x01ce, 0x01d1, 0x01d7, 0x01dd, 0x01e0,
+  0x01e6, 0x01e9, 0x01ef, 0x01f2, 0x01f5, 0x01fb, 0x0201, 0x0207, 0x020d, 0x0213,
+  0x0216, 0x0219, 0x021c, 0x021f, 0x0222, 0x0225, 0x0228, 0x022e, 0x0234, 0x023a,
+  0x023d, 0x0243, 0x0249, 0x024f, 0x0252, 0x0258, 0x025e, 0x0264, 0x0267, 0x026d,
+  0x0273, 0x0279, 0x027f, 0x0285, 0x0288, 0x028b, 0x028e, 0x0291, 0x0294, 0x0297,
+  0x029a, 0x029d, 0x02a0, 0x02a3, 0x02a9, 0x02af, 0x02b5, 0x02b8, 0x02bb, 0x02be,
+  0x02c1, 0x02c4, 0x02c7, 0x02ca, 0x02cd, 0x02d0, 0x02d3, 0x02d6, 0x02dc, 0x02e2,
+  0x02e8, 0x02eb, 0x02ee, 0x02f1, 0x02f4, 0x02f7, 0x02fa, 0x02fd, 0x0300, 0x0303,
+  0x0309, 0x030c, 0x0312, 0x0318, 0x031e, 0x0324, 0x0327, 0x032a, 0x032d
+};
+static char rk_str[] = {
+  0xe3, 0x82, 0xa1, 0xe3, 0x82, 0xa2, 0xe3, 0x82, 0xa3, 0xe3, 0x82, 0xa4, 0xe3,
+  0x82, 0xa4, 0xe3, 0x82, 0xa7, 0xe3, 0x82, 0xa5, 0xe3, 0x82, 0xa6, 0xe3, 0x82,
+  0xa6, 0xe3, 0x82, 0xa2, 0xe3, 0x82, 0xa6, 0xe3, 0x82, 0xa3, 0xe3, 0x82, 0xa6,
+  0xe3, 0x82, 0xa4, 0xe3, 0x82, 0xa6, 0xe3, 0x82, 0xa6, 0xe3, 0x82, 0xa6, 0xe3,
+  0x82, 0xa7, 0xe3, 0x82, 0xa6, 0xe3, 0x82, 0xa8, 0xe3, 0x82, 0xa6, 0xe3, 0x82,
+  0xaa, 0xe3, 0x82, 0xa6, 0xe3, 0x83, 0xa0, 0xe3, 0x82, 0xa6, 0xe3, 0x83, 0xa1,
+  0xe3, 0x82, 0xa6, 0xe3, 0x83, 0xa2, 0xe3, 0x82, 0xa6, 0xe3, 0x83, 0xa3, 0xe3,
+  0x82, 0xa6, 0xe3, 0x83, 0xa4, 0xe3, 0x82, 0xa6, 0xe3, 0x83, 0xa5, 0xe3, 0x82,
+  0xa6, 0xe3, 0x83, 0xa6, 0xe3, 0x82, 0xa6, 0xe3, 0x83, 0xa7, 0xe3, 0x82, 0xa6,
+  0xe3, 0x83, 0xa8, 0xe3, 0x82, 0xa6, 0xe3, 0x83, 0xa9, 0xe3, 0x82, 0xa6, 0xe3,
+  0x83, 0xaa, 0xe3, 0x82, 0xa6, 0xe3, 0x83, 0xab, 0xe3, 0x82, 0xa6, 0xe3, 0x83,
+  0xac, 0xe3, 0x82, 0xa6, 0xe3, 0x83, 0xad, 0xe3, 0x82, 0xa6, 0xe3, 0x83, 0xae,
+  0xe3, 0x82, 0xa6, 0xe3, 0x83, 0xaf, 0xe3, 0x82, 0xa6, 0xe3, 0x83, 0xb0, 0xe3,
+  0x82, 0xa6, 0xe3, 0x83, 0xb1, 0xe3, 0x82, 0xa6, 0xe3, 0x83, 0xb2, 0xe3, 0x82,
+  0xa6, 0xe3, 0x83, 0xb3, 0xe3, 0x82, 0xa6, 0xe3, 0x83, 0xbc, 0xe3, 0x82, 0xa7,
+  0xe3, 0x82, 0xa8, 0xe3, 0x82, 0xa9, 0xe3, 0x82, 0xaa, 0xe3, 0x82, 0xab, 0xe3,
+  0x82, 0xac, 0xe3, 0x82, 0xad, 0xe3, 0x82, 0xad, 0xe3, 0x83, 0xa3, 0xe3, 0x82,
+  0xad, 0xe3, 0x83, 0xa5, 0xe3, 0x82, 0xad, 0xe3, 0x83, 0xa7, 0xe3, 0x82, 0xae,
+  0xe3, 0x82, 0xae, 0xe3, 0x83, 0xa3, 0xe3, 0x82, 0xae, 0xe3, 0x83, 0xa5, 0xe3,
+  0x82, 0xae, 0xe3, 0x83, 0xa7, 0xe3, 0x82, 0xaf, 0xe3, 0x82, 0xaf, 0xe3, 0x82,
+  0xa1, 0xe3, 0x82, 0xb0, 0xe3, 0x82, 0xb0, 0xe3, 0x82, 0xa1, 0xe3, 0x82, 0xb1,
+  0xe3, 0x82, 0xb2, 0xe3, 0x82, 0xb3, 0xe3, 0x82, 0xb4, 0xe3, 0x82, 0xb5, 0xe3,
+  0x82, 0xb6, 0xe3, 0x82, 0xb7, 0xe3, 0x82, 0xb7, 0xe3, 0x82, 0xa7, 0xe3, 0x82,
+  0xb7, 0xe3, 0x83, 0xa3, 0xe3, 0x82, 0xb7, 0xe3, 0x83, 0xa5, 0xe3, 0x82, 0xb7,
+  0xe3, 0x83, 0xa7, 0xe3, 0x82, 0xb8, 0xe3, 0x82, 0xb8, 0xe3, 0x82, 0xa7, 0xe3,
+  0x82, 0xb8, 0xe3, 0x83, 0xa3, 0xe3, 0x82, 0xb8, 0xe3, 0x83, 0xa5, 0xe3, 0x82,
+  0xb8, 0xe3, 0x83, 0xa7, 0xe3, 0x82, 0xb9, 0xe3, 0x82, 0xba, 0xe3, 0x82, 0xbb,
+  0xe3, 0x82, 0xbc, 0xe3, 0x82, 0xbd, 0xe3, 0x82, 0xbe, 0xe3, 0x82, 0xbf, 0xe3,
+  0x83, 0x80, 0xe3, 0x83, 0x81, 0xe3, 0x83, 0x81, 0xe3, 0x82, 0xa7, 0xe3, 0x83,
+  0x81, 0xe3, 0x83, 0xa3, 0xe3, 0x83, 0x81, 0xe3, 0x83, 0xa5, 0xe3, 0x83, 0x81,
+  0xe3, 0x83, 0xa7, 0xe3, 0x83, 0x82, 0xe3, 0x83, 0x82, 0xe3, 0x83, 0xa3, 0xe3,
+  0x83, 0x82, 0xe3, 0x83, 0xa5, 0xe3, 0x83, 0x82, 0xe3, 0x83, 0xa7, 0xe3, 0x83,
+  0x83, 0xe3, 0x83, 0x84, 0xe3, 0x83, 0x84, 0xe3, 0x82, 0xa1, 0xe3, 0x83, 0x84,
+  0xe3, 0x82, 0xa3, 0xe3, 0x83, 0x84, 0xe3, 0x82, 0xa7, 0xe3, 0x83, 0x84, 0xe3,
+  0x82, 0xa9, 0xe3, 0x83, 0x85, 0xe3, 0x83, 0x86, 0xe3, 0x83, 0x86, 0xe3, 0x82,
+  0xa3, 0xe3, 0x83, 0x86, 0xe3, 0x83, 0xa5, 0xe3, 0x83, 0x87, 0xe3, 0x83, 0x87,
+  0xe3, 0x82, 0xa3, 0xe3, 0x83, 0x87, 0xe3, 0x83, 0xa5, 0xe3, 0x83, 0x88, 0xe3,
+  0x83, 0x88, 0xe3, 0x82, 0xa5, 0xe3, 0x83, 0x89, 0xe3, 0x83, 0x89, 0xe3, 0x82,
+  0xa5, 0xe3, 0x83, 0x8a, 0xe3, 0x83, 0x8b, 0xe3, 0x83, 0x8b, 0xe3, 0x82, 0xa3,
+  0xe3, 0x83, 0x8b, 0xe3, 0x82, 0xa7, 0xe3, 0x83, 0x8b, 0xe3, 0x83, 0xa3, 0xe3,
+  0x83, 0x8b, 0xe3, 0x83, 0xa5, 0xe3, 0x83, 0x8b, 0xe3, 0x83, 0xa7, 0xe3, 0x83,
+  0x8c, 0xe3, 0x83, 0x8d, 0xe3, 0x83, 0x8e, 0xe3, 0x83, 0x8f, 0xe3, 0x83, 0x90,
+  0xe3, 0x83, 0x91, 0xe3, 0x83, 0x92, 0xe3, 0x83, 0x92, 0xe3, 0x83, 0xa3, 0xe3,
+  0x83, 0x92, 0xe3, 0x83, 0xa5, 0xe3, 0x83, 0x92, 0xe3, 0x83, 0xa7, 0xe3, 0x83,
+  0x93, 0xe3, 0x83, 0x93, 0xe3, 0x83, 0xa3, 0xe3, 0x83, 0x93, 0xe3, 0x83, 0xa5,
+  0xe3, 0x83, 0x93, 0xe3, 0x83, 0xa7, 0xe3, 0x83, 0x94, 0xe3, 0x83, 0x94, 0xe3,
+  0x83, 0xa3, 0xe3, 0x83, 0x94, 0xe3, 0x83, 0xa5, 0xe3, 0x83, 0x94, 0xe3, 0x83,
+  0xa7, 0xe3, 0x83, 0x95, 0xe3, 0x83, 0x95, 0xe3, 0x82, 0xa1, 0xe3, 0x83, 0x95,
+  0xe3, 0x82, 0xa3, 0xe3, 0x83, 0x95, 0xe3, 0x82, 0xa7, 0xe3, 0x83, 0x95, 0xe3,
+  0x82, 0xa9, 0xe3, 0x83, 0x95, 0xe3, 0x83, 0xa5, 0xe3, 0x83, 0x96, 0xe3, 0x83,
+  0x97, 0xe3, 0x83, 0x98, 0xe3, 0x83, 0x99, 0xe3, 0x83, 0x9a, 0xe3, 0x83, 0x9b,
+  0xe3, 0x83, 0x9c, 0xe3, 0x83, 0x9d, 0xe3, 0x83, 0x9e, 0xe3, 0x83, 0x9f, 0xe3,
+  0x83, 0x9f, 0xe3, 0x83, 0xa3, 0xe3, 0x83, 0x9f, 0xe3, 0x83, 0xa5, 0xe3, 0x83,
+  0x9f, 0xe3, 0x83, 0xa7, 0xe3, 0x83, 0xa0, 0xe3, 0x83, 0xa1, 0xe3, 0x83, 0xa2,
+  0xe3, 0x83, 0xa3, 0xe3, 0x83, 0xa4, 0xe3, 0x83, 0xa5, 0xe3, 0x83, 0xa6, 0xe3,
+  0x83, 0xa7, 0xe3, 0x83, 0xa8, 0xe3, 0x83, 0xa9, 0xe3, 0x83, 0xaa, 0xe3, 0x83,
+  0xaa, 0xe3, 0x83, 0xa3, 0xe3, 0x83, 0xaa, 0xe3, 0x83, 0xa5, 0xe3, 0x83, 0xaa,
+  0xe3, 0x83, 0xa7, 0xe3, 0x83, 0xab, 0xe3, 0x83, 0xac, 0xe3, 0x83, 0xad, 0xe3,
+  0x83, 0xae, 0xe3, 0x83, 0xaf, 0xe3, 0x83, 0xb0, 0xe3, 0x83, 0xb1, 0xe3, 0x83,
+  0xb2, 0xe3, 0x83, 0xb3, 0xe3, 0x83, 0xb3, 0xe3, 0x83, 0xbc, 0xe3, 0x83, 0xb4,
+  0xe3, 0x83, 0xb4, 0xe3, 0x82, 0xa1, 0xe3, 0x83, 0xb4, 0xe3, 0x82, 0xa3, 0xe3,
+  0x83, 0xb4, 0xe3, 0x82, 0xa7, 0xe3, 0x83, 0xb4, 0xe3, 0x82, 0xa9, 0xe3, 0x83,
+  0xb5, 0xe3, 0x83, 0xb6, 0xe3, 0x83, 0xbc
+};
+static uint16_t rk_tree_idx[] = {
+  0x001b, 0x0022, 0x0025, 0x0028, 0x002d, 0x0030, 0x0039, 0x003b, 0x003c, 0x003f,
+  0x0046, 0x0047, 0x004f, 0x0050, 0x0053, 0x005a, 0x005d, 0x0064, 0x0067, 0x006f,
+  0x0070, 0x0073, 0x007d, 0x007f, 0x0081, 0x0082, 0x0083, 0x0088, 0x008f, 0x0092,
+  0x00af, 0x00b5, 0x00bc, 0x00bf, 0x00c6, 0x00c9, 0x00d1, 0x00d6, 0x00da, 0x00e4,
+  0x00e6, 0x00eb, 0x00ec, 0x00f0, 0x00f6, 0x00fc, 0x00fe, 0x0108, 0x010a, 0x010c,
+  0x010d, 0x010e, 0x0113, 0x0118, 0x011f, 0x0123, 0x0125, 0x0164, 0x0180, 0x0183,
+  0x0199, 0x01ad
+};
+static rk_tree_node rk_tree[] = {
+  {0x2d, 0x00, 0xb2, 0x01}, {0x61, 0x00, 0x01, 0x01}, {0x62, 0x01, 0xff, 0x01},
+  {0x63, 0x03, 0xff, 0x01}, {0x64, 0x06, 0xff, 0x01}, {0x65, 0x00, 0x24, 0x01},
+  {0x66, 0x0a, 0xff, 0x01}, {0x67, 0x0c, 0xff, 0x01}, {0x68, 0x0f, 0xff, 0x01},
+  {0x69, 0x00, 0x03, 0x01}, {0x6a, 0x11, 0xff, 0x01}, {0x6b, 0x13, 0xff, 0x01},
+  {0x6c, 0x16, 0xff, 0x01}, {0x6d, 0x1c, 0xff, 0x01}, {0x6e, 0x1e, 0xff, 0x01},
+  {0x6f, 0x00, 0x26, 0x01}, {0x70, 0x20, 0xff, 0x01}, {0x72, 0x22, 0xff, 0x01},
+  {0x73, 0x24, 0xff, 0x01}, {0x74, 0x27, 0xff, 0x01}, {0x75, 0x00, 0x06, 0x01},
+  {0x76, 0x2c, 0xff, 0x01}, {0x77, 0x2d, 0xff, 0x01}, {0x78, 0x2f, 0xff, 0x01},
+  {0x79, 0x35, 0xff, 0x01}, {0x7a, 0x36, 0xff, 0x01}, {0xe3, 0x38, 0xff, 0x01},
+  {0x61, 0x00, 0x72, 0x01}, {0x62, 0x01, 0x56, 0x01}, {0x65, 0x00, 0x89, 0x01},
+  {0x69, 0x00, 0x78, 0x01}, {0x6f, 0x00, 0x8c, 0x01}, {0x75, 0x00, 0x86, 0x01},
+  {0x79, 0x02, 0xff, 0x00}, {0x61, 0x00, 0x79, 0x01}, {0x6f, 0x00, 0x7b, 0x01},
+  {0x75, 0x00, 0x7a, 0x01}, {0x63, 0x03, 0x56, 0x01}, {0x68, 0x04, 0xff, 0x01},
+  {0x79, 0x05, 0xff, 0x01}, {0x61, 0x00, 0x4f, 0x00}, {0x65, 0x00, 0x4e, 0x00},
+  {0x69, 0x00, 0x4d, 0x01}, {0x6f, 0x00, 0x51, 0x00}, {0x75, 0x00, 0x50, 0x00},
+  {0x61, 0x00, 0x4f, 0x01}, {0x6f, 0x00, 0x51, 0x01}, {0x75, 0x00, 0x50, 0x01},
+  {0x61, 0x00, 0x4c, 0x01}, {0x64, 0x06, 0x56, 0x01}, {0x65, 0x00, 0x60, 0x01},
+  {0x68, 0x07, 0xff, 0x00}, {0x69, 0x00, 0x61, 0x00}, {0x6f, 0x00, 0x65, 0x01},
+  {0x75, 0x00, 0x5c, 0x01}, {0x77, 0x08, 0xff, 0x00}, {0x79, 0x09, 0xff, 0x01},
+  {0x69, 0x00, 0x61, 0x01}, {0x75, 0x00, 0x62, 0x01}, {0x75, 0x00, 0x66, 0x01},
+  {0x61, 0x00, 0x53, 0x01}, {0x6f, 0x00, 0x55, 0x01}, {0x75, 0x00, 0x54, 0x01},
+  {0x61, 0x00, 0x81, 0x00}, {0x65, 0x00, 0x83, 0x00}, {0x66, 0x0a, 0x56, 0x01},
+  {0x69, 0x00, 0x82, 0x00}, {0x6f, 0x00, 0x84, 0x00}, {0x75, 0x00, 0x80, 0x01},
+  {0x79, 0x0b, 0xff, 0x00}, {0x75, 0x00, 0x85, 0x01}, {0x61, 0x00, 0x28, 0x01},
+  {0x65, 0x00, 0x36, 0x01}, {0x67, 0x0c, 0x56, 0x01}, {0x69, 0x00, 0x2d, 0x01},
+  {0x6f, 0x00, 0x38, 0x01}, {0x75, 0x00, 0x33, 0x01}, {0x77, 0x0d, 0xff, 0x00},
+  {0x79, 0x0e, 0xff, 0x00}, {0x61, 0x00, 0x34, 0x01}, {0x61, 0x00, 0x2e, 0x01},
+  {0x6f, 0x00, 0x30, 0x01}, {0x75, 0x00, 0x2f, 0x01}, {0x61, 0x00, 0x71, 0x01},
+  {0x65, 0x00, 0x88, 0x01}, {0x68, 0x0f, 0x56, 0x01}, {0x69, 0x00, 0x74, 0x01},
+  {0x6f, 0x00, 0x8b, 0x01}, {0x75, 0x00, 0x80, 0x01}, {0x79, 0x10, 0xff, 0x00},
+  {0x61, 0x00, 0x75, 0x01}, {0x6f, 0x00, 0x77, 0x01}, {0x75, 0x00, 0x76, 0x01},
+  {0x61, 0x00, 0x42, 0x00}, {0x65, 0x00, 0x41, 0x00}, {0x69, 0x00, 0x40, 0x01},
+  {0x6a, 0x11, 0x56, 0x01}, {0x6f, 0x00, 0x44, 0x00}, {0x75, 0x00, 0x43, 0x00},
+  {0x79, 0x12, 0xff, 0x00}, {0x61, 0x00, 0x42, 0x01}, {0x6f, 0x00, 0x44, 0x01},
+  {0x75, 0x00, 0x43, 0x01}, {0x61, 0x00, 0x27, 0x01}, {0x65, 0x00, 0x35, 0x01},
+  {0x69, 0x00, 0x29, 0x01}, {0x6b, 0x13, 0x56, 0x01}, {0x6f, 0x00, 0x37, 0x01},
+  {0x75, 0x00, 0x31, 0x01}, {0x77, 0x14, 0xff, 0x00}, {0x79, 0x15, 0xff, 0x00},
+  {0x61, 0x00, 0x32, 0x01}, {0x61, 0x00, 0x2a, 0x01}, {0x6f, 0x00, 0x2c, 0x01},
+  {0x75, 0x00, 0x2b, 0x01}, {0x61, 0x00, 0x00, 0x01}, {0x65, 0x00, 0x23, 0x01},
+  {0x69, 0x00, 0x02, 0x01}, {0x6b, 0x17, 0xff, 0x01}, {0x6c, 0x16, 0x56, 0x01},
+  {0x6f, 0x00, 0x25, 0x01}, {0x74, 0x18, 0xff, 0x01}, {0x75, 0x00, 0x05, 0x01},
+  {0x77, 0x1a, 0xff, 0x01}, {0x79, 0x1b, 0xff, 0x01}, {0x61, 0x00, 0xb0, 0x01},
+  {0x65, 0x00, 0xb1, 0x01}, {0x73, 0x19, 0xff, 0x00}, {0x75, 0x00, 0x56, 0x01},
+  {0x75, 0x00, 0x56, 0x01}, {0x61, 0x00, 0xa4, 0x01}, {0x61, 0x00, 0x96, 0x01},
+  {0x65, 0x00, 0x23, 0x01}, {0x69, 0x00, 0x02, 0x01}, {0x6f, 0x00, 0x9a, 0x01},
+  {0x75, 0x00, 0x98, 0x01}, {0x61, 0x00, 0x8e, 0x01}, {0x65, 0x00, 0x94, 0x01},
+  {0x69, 0x00, 0x8f, 0x01}, {0x6d, 0x1c, 0x56, 0x01}, {0x6f, 0x00, 0x95, 0x01},
+  {0x75, 0x00, 0x93, 0x01}, {0x79, 0x1d, 0xff, 0x00}, {0x61, 0x00, 0x90, 0x01},
+  {0x6f, 0x00, 0x92, 0x01}, {0x75, 0x00, 0x91, 0x01}, {0x00, 0x00, 0xa9, 0x01},
+  {0x27, 0x00, 0xa9, 0x00}, {0x2d, 0x00, 0xaa, 0x00}, {0x61, 0x00, 0x67, 0x01},
+  {0x62, 0x01, 0xa9, 0x00}, {0x63, 0x03, 0xa9, 0x00}, {0x64, 0x06, 0xa9, 0x00},
+  {0x65, 0x00, 0x6f, 0x01}, {0x66, 0x0a, 0xa9, 0x00}, {0x67, 0x0c, 0xa9, 0x00},
+  {0x68, 0x0f, 0xa9, 0x00}, {0x69, 0x00, 0x68, 0x01}, {0x6a, 0x11, 0xa9, 0x00},
+  {0x6b, 0x13, 0xa9, 0x00}, {0x6c, 0x16, 0xa9, 0x00}, {0x6d, 0x1c, 0xa9, 0x00},
+  {0x6e, 0x00, 0xa9, 0x00}, {0x6f, 0x00, 0x70, 0x01}, {0x70, 0x20, 0xa9, 0x00},
+  {0x72, 0x22, 0xa9, 0x00}, {0x73, 0x24, 0xa9, 0x00}, {0x74, 0x27, 0xa9, 0x00},
+  {0x75, 0x00, 0x6e, 0x01}, {0x76, 0x2c, 0xa9, 0x00}, {0x77, 0x2d, 0xa9, 0x00},
+  {0x78, 0x2f, 0xa9, 0x00}, {0x79, 0x1f, 0xff, 0x00}, {0x7a, 0x36, 0xa9, 0x00},
+  {0xe3, 0x38, 0xa9, 0x00}, {0x00, 0x00, 0xa9, 0x01}, {0x61, 0x00, 0x6b, 0x01},
+  {0x65, 0x00, 0x6a, 0x01}, {0x69, 0x00, 0x69, 0x01}, {0x6f, 0x00, 0x6d, 0x01},
+  {0x75, 0x00, 0x6c, 0x01}, {0x61, 0x00, 0x73, 0x01}, {0x65, 0x00, 0x8a, 0x01},
+  {0x69, 0x00, 0x7c, 0x01}, {0x6f, 0x00, 0x8d, 0x01}, {0x70, 0x20, 0x56, 0x01},
+  {0x75, 0x00, 0x87, 0x01}, {0x79, 0x21, 0xff, 0x00}, {0x61, 0x00, 0x7d, 0x01},
+  {0x6f, 0x00, 0x7f, 0x01}, {0x75, 0x00, 0x7e, 0x01}, {0x61, 0x00, 0x9c, 0x01},
+  {0x65, 0x00, 0xa2, 0x01}, {0x69, 0x00, 0x9d, 0x01}, {0x6f, 0x00, 0xa3, 0x01},
+  {0x72, 0x22, 0x56, 0x01}, {0x75, 0x00, 0xa1, 0x01}, {0x79, 0x23, 0xff, 0x00},
+  {0x61, 0x00, 0x9e, 0x01}, {0x6f, 0x00, 0xa0, 0x01}, {0x75, 0x00, 0x9f, 0x01},
+  {0x61, 0x00, 0x39, 0x01}, {0x65, 0x00, 0x47, 0x01}, {0x68, 0x25, 0xff, 0x00},
+  {0x69, 0x00, 0x3b, 0x01}, {0x6f, 0x00, 0x49, 0x01}, {0x73, 0x24, 0x56, 0x01},
+  {0x75, 0x00, 0x45, 0x01}, {0x79, 0x26, 0xff, 0x00}, {0x61, 0x00, 0x3d, 0x00},
+  {0x65, 0x00, 0x3c, 0x00}, {0x69, 0x00, 0x3b, 0x01}, {0x6f, 0x00, 0x3f, 0x00},
+  {0x75, 0x00, 0x3e, 0x00}, {0x61, 0x00, 0x3d, 0x01}, {0x65, 0x00, 0x3c, 0x01},
+  {0x6f, 0x00, 0x3f, 0x01}, {0x75, 0x00, 0x3e, 0x01}, {0x61, 0x00, 0x4b, 0x01},
+  {0x65, 0x00, 0x5d, 0x01}, {0x68, 0x28, 0xff, 0x00}, {0x69, 0x00, 0x4d, 0x01},
+  {0x6f, 0x00, 0x63, 0x01}, {0x73, 0x29, 0xff, 0x00}, {0x74, 0x27, 0x56, 0x01},
+  {0x75, 0x00, 0x57, 0x01}, {0x77, 0x2a, 0xff, 0x00}, {0x79, 0x2b, 0xff, 0x00},
+  {0x69, 0x00, 0x5e, 0x01}, {0x75, 0x00, 0x5f, 0x01}, {0x61, 0x00, 0x58, 0x00},
+  {0x65, 0x00, 0x5a, 0x00}, {0x69, 0x00, 0x59, 0x00}, {0x6f, 0x00, 0x5b, 0x00},
+  {0x75, 0x00, 0x57, 0x01}, {0x75, 0x00, 0x64, 0x01}, {0x61, 0x00, 0x4f, 0x01},
+  {0x65, 0x00, 0x4e, 0x01}, {0x6f, 0x00, 0x51, 0x01}, {0x75, 0x00, 0x50, 0x01},
+  {0x61, 0x00, 0xac, 0x00}, {0x65, 0x00, 0xae, 0x00}, {0x69, 0x00, 0xad, 0x00},
+  {0x6f, 0x00, 0xaf, 0x00}, {0x75, 0x00, 0xab, 0x01}, {0x76, 0x2c, 0x56, 0x01},
+  {0x61, 0x00, 0xa5, 0x01}, {0x65, 0x00, 0x0b, 0x01}, {0x69, 0x00, 0x08, 0x01},
+  {0x6f, 0x00, 0xa8, 0x01}, {0x77, 0x2d, 0x56, 0x01}, {0x79, 0x2e, 0xff, 0x01},
+  {0x65, 0x00, 0xa7, 0x01}, {0x69, 0x00, 0xa6, 0x01}, {0x61, 0x00, 0x00, 0x01},
+  {0x65, 0x00, 0x23, 0x01}, {0x69, 0x00, 0x02, 0x01}, {0x6b, 0x30, 0xff, 0x01},
+  {0x6f, 0x00, 0x25, 0x01}, {0x74, 0x31, 0xff, 0x01}, {0x75, 0x00, 0x05, 0x01},
+  {0x77, 0x33, 0xff, 0x01}, {0x78, 0x2f, 0x56, 0x01}, {0x79, 0x34, 0xff, 0x01},
+  {0x61, 0x00, 0xb0, 0x01}, {0x65, 0x00, 0xb1, 0x01}, {0x73, 0x32, 0xff, 0x00},
+  {0x75, 0x00, 0x56, 0x01}, {0x75, 0x00, 0x56, 0x01}, {0x61, 0x00, 0xa4, 0x01},
+  {0x61, 0x00, 0x96, 0x01}, {0x65, 0x00, 0x23, 0x01}, {0x69, 0x00, 0x02, 0x01},
+  {0x6f, 0x00, 0x9a, 0x01}, {0x75, 0x00, 0x98, 0x01}, {0x61, 0x00, 0x97, 0x01},
+  {0x65, 0x00, 0x04, 0x01}, {0x6f, 0x00, 0x9b, 0x01}, {0x75, 0x00, 0x99, 0x01},
+  {0x79, 0x35, 0x56, 0x01}, {0x61, 0x00, 0x3a, 0x01}, {0x65, 0x00, 0x48, 0x01},
+  {0x69, 0x00, 0x40, 0x01}, {0x6f, 0x00, 0x4a, 0x01}, {0x75, 0x00, 0x46, 0x01},
+  {0x79, 0x37, 0xff, 0x00}, {0x7a, 0x36, 0x56, 0x01}, {0x61, 0x00, 0x42, 0x01},
+  {0x65, 0x00, 0x41, 0x01}, {0x6f, 0x00, 0x44, 0x01}, {0x75, 0x00, 0x43, 0x01},
+  {0x81, 0x39, 0xff, 0x01}, {0x82, 0x3d, 0xff, 0x01}, {0x81, 0x00, 0x00, 0x01},
+  {0x82, 0x00, 0x01, 0x01}, {0x83, 0x00, 0x02, 0x01}, {0x84, 0x00, 0x03, 0x01},
+  {0x85, 0x00, 0x05, 0x01}, {0x86, 0x3a, 0xff, 0x01}, {0x87, 0x00, 0x23, 0x01},
+  {0x88, 0x00, 0x24, 0x01}, {0x89, 0x00, 0x25, 0x01}, {0x8a, 0x00, 0x26, 0x01},
+  {0x8b, 0x00, 0x27, 0x01}, {0x8c, 0x00, 0x28, 0x01}, {0x8d, 0x00, 0x29, 0x01},
+  {0x8e, 0x00, 0x2d, 0x01}, {0x8f, 0x00, 0x31, 0x01}, {0x90, 0x00, 0x33, 0x01},
+  {0x91, 0x00, 0x35, 0x01}, {0x92, 0x00, 0x36, 0x01}, {0x93, 0x00, 0x37, 0x01},
+  {0x94, 0x00, 0x38, 0x01}, {0x95, 0x00, 0x39, 0x01}, {0x96, 0x00, 0x3a, 0x01},
+  {0x97, 0x00, 0x3b, 0x01}, {0x98, 0x00, 0x40, 0x01}, {0x99, 0x00, 0x45, 0x01},
+  {0x9a, 0x00, 0x46, 0x01}, {0x9b, 0x00, 0x47, 0x01}, {0x9c, 0x00, 0x48, 0x01},
+  {0x9d, 0x00, 0x49, 0x01}, {0x9e, 0x00, 0x4a, 0x01}, {0x9f, 0x00, 0x4b, 0x01},
+  {0xa0, 0x00, 0x4c, 0x01}, {0xa1, 0x00, 0x4d, 0x01}, {0xa2, 0x00, 0x52, 0x01},
+  {0xa3, 0x00, 0x56, 0x01}, {0xa4, 0x00, 0x57, 0x01}, {0xa5, 0x00, 0x5c, 0x01},
+  {0xa6, 0x00, 0x5d, 0x01}, {0xa7, 0x00, 0x60, 0x01}, {0xa8, 0x00, 0x63, 0x01},
+  {0xa9, 0x00, 0x65, 0x01}, {0xaa, 0x00, 0x67, 0x01}, {0xab, 0x00, 0x68, 0x01},
+  {0xac, 0x00, 0x6e, 0x01}, {0xad, 0x00, 0x6f, 0x01}, {0xae, 0x00, 0x70, 0x01},
+  {0xaf, 0x00, 0x71, 0x01}, {0xb0, 0x00, 0x72, 0x01}, {0xb1, 0x00, 0x73, 0x01},
+  {0xb2, 0x00, 0x74, 0x01}, {0xb3, 0x00, 0x78, 0x01}, {0xb4, 0x00, 0x7c, 0x01},
+  {0xb5, 0x00, 0x80, 0x01}, {0xb6, 0x00, 0x86, 0x01}, {0xb7, 0x00, 0x87, 0x01},
+  {0xb8, 0x00, 0x88, 0x01}, {0xb9, 0x00, 0x89, 0x01}, {0xba, 0x00, 0x8a, 0x01},
+  {0xbb, 0x00, 0x8b, 0x01}, {0xbc, 0x00, 0x8c, 0x01}, {0xbd, 0x00, 0x8d, 0x01},
+  {0xbe, 0x00, 0x8e, 0x01}, {0xbf, 0x00, 0x8f, 0x01}, {0x00, 0x00, 0x06, 0x00},
+  {0x2d, 0x00, 0x22, 0x00}, {0x61, 0x00, 0x07, 0x00}, {0x62, 0x01, 0x06, 0x00},
+  {0x63, 0x03, 0x06, 0x00}, {0x64, 0x06, 0x06, 0x00}, {0x65, 0x00, 0x0c, 0x00},
+  {0x66, 0x0a, 0x06, 0x00}, {0x67, 0x0c, 0x06, 0x00}, {0x68, 0x0f, 0x06, 0x00},
+  {0x69, 0x00, 0x09, 0x00}, {0x6a, 0x11, 0x06, 0x00}, {0x6b, 0x13, 0x06, 0x00},
+  {0x6c, 0x16, 0x06, 0x00}, {0x6d, 0x1c, 0x06, 0x00}, {0x6e, 0x1e, 0x06, 0x00},
+  {0x6f, 0x00, 0x0d, 0x00}, {0x70, 0x20, 0x06, 0x00}, {0x72, 0x22, 0x06, 0x00},
+  {0x73, 0x24, 0x06, 0x00}, {0x74, 0x27, 0x06, 0x00}, {0x75, 0x00, 0x0a, 0x00},
+  {0x76, 0x2c, 0x06, 0x00}, {0x77, 0x2d, 0x06, 0x00}, {0x78, 0x2f, 0x06, 0x00},
+  {0x79, 0x35, 0x06, 0x00}, {0x7a, 0x36, 0x06, 0x00}, {0xe3, 0x3b, 0xff, 0x01},
+  {0x00, 0x00, 0x06, 0x00}, {0x81, 0x39, 0x06, 0x00}, {0x82, 0x3c, 0xff, 0x01},
+  {0x00, 0x00, 0x06, 0x01}, {0x80, 0x00, 0x0e, 0x00}, {0x81, 0x00, 0x0f, 0x00},
+  {0x82, 0x00, 0x10, 0x00}, {0x83, 0x00, 0x11, 0x00}, {0x84, 0x00, 0x12, 0x00},
+  {0x85, 0x00, 0x13, 0x00}, {0x86, 0x00, 0x14, 0x00}, {0x87, 0x00, 0x15, 0x00},
+  {0x88, 0x00, 0x16, 0x00}, {0x89, 0x00, 0x17, 0x00}, {0x8a, 0x00, 0x18, 0x00},
+  {0x8b, 0x00, 0x19, 0x00}, {0x8c, 0x00, 0x1a, 0x00}, {0x8d, 0x00, 0x1b, 0x00},
+  {0x8e, 0x00, 0x1c, 0x00}, {0x8f, 0x00, 0x1d, 0x00}, {0x90, 0x00, 0x1e, 0x00},
+  {0x91, 0x00, 0x1f, 0x00}, {0x92, 0x00, 0x20, 0x00}, {0x93, 0x00, 0x21, 0x00},
+  {0x9b, 0x00, 0xab, 0x01}, {0x80, 0x00, 0x93, 0x01}, {0x81, 0x00, 0x94, 0x01},
+  {0x82, 0x00, 0x95, 0x01}, {0x83, 0x00, 0x96, 0x01}, {0x84, 0x00, 0x97, 0x01},
+  {0x85, 0x00, 0x98, 0x01}, {0x86, 0x00, 0x99, 0x01}, {0x87, 0x00, 0x9a, 0x01},
+  {0x88, 0x00, 0x9b, 0x01}, {0x89, 0x00, 0x9c, 0x01}, {0x8a, 0x00, 0x9d, 0x01},
+  {0x8b, 0x00, 0xa1, 0x01}, {0x8c, 0x00, 0xa2, 0x01}, {0x8d, 0x00, 0xa3, 0x01},
+  {0x8e, 0x00, 0xa4, 0x01}, {0x8f, 0x00, 0xa5, 0x01}, {0x90, 0x00, 0xa6, 0x01},
+  {0x91, 0x00, 0xa7, 0x01}, {0x92, 0x00, 0xa8, 0x01}, {0x93, 0x00, 0xa9, 0x01}
+};
+
+static rk_tree_node *
+rk_lookup(uint8_t state, uint8_t code)
+{
+  if (state < sizeof(rk_tree_idx)/sizeof(uint16_t)) {
+    uint16_t ns = state ? rk_tree_idx[state - 1] : 0;
+    uint16_t ne = rk_tree_idx[state];
+    while (ns < ne) {
+      uint16_t m = (ns + ne)>>1;
+      rk_tree_node *rn = &rk_tree[m];
+      if (rn->code == code) { return rn; }
+      if (rn->code < code) {
+        ns = m + 1;
+      } else {
+        ne = m;
+      }
+    }
+  }
+  return NULL;
+}
+
+static uint32_t
+rk_emit(rk_tree_node *rn, char **str)
+{
+  if (rn && rn->emit != 0xff) {
+    uint16_t pos = rn->emit ? rk_str_idx[rn->emit - 1] :  0;
+    *str = &rk_str[pos];
+    return (uint32_t)(rk_str_idx[rn->emit] - pos);
+  } else {
+    *str = NULL;
+    return 0;
+  }
+}
+
+#define RK_OUTPUT(e,l) do {\
+  if (oc < oe) {\
+    uint32_t l_ = (oc + (l) < oe) ? (l) : (oe - oc);\
+    grn_memcpy(oc, (e), l_);\
+    oc += l_;\
+    ic_ = ic;\
+  }\
+} while (0)
+
+static uint32_t
+rk_conv(const char *str, uint32_t str_len, uint8_t *buf, uint32_t buf_size, uint8_t *statep)
+{
+  uint32_t l;
+  uint8_t state = 0;
+  rk_tree_node *rn;
+  char *e;
+  uint8_t *oc = buf, *oe = oc + buf_size;
+  const uint8_t *ic = (uint8_t *)str, *ic_ = ic, *ie = ic + str_len;
+  while (ic < ie) {
+    if ((rn = rk_lookup(state, *ic))) {
+      ic++;
+      if ((l = rk_emit(rn, &e))) { RK_OUTPUT(e, l); }
+      state = rn->next;
+    } else {
+      if (!state) { ic++; }
+      if (ic_ < ic) { RK_OUTPUT(ic_, ic - ic_); }
+      state = 0;
+    }
+  }
+#ifdef FLUSH_UNRESOLVED_INPUT
+  if ((rn = rk_lookup(state, 0))) {
+    if ((l = rk_emit(rn, &e))) { RK_OUTPUT(e, l); }
+    state = rn->next;
+  } else {
+    if (ic_ < ic) { RK_OUTPUT(ic_, ic - ic_); }
+  }
+#endif /* FLUSH_UNRESOLVED_INPUT */
+  *statep = state;
+  return oc - buf;
+}
+
+static grn_id
+sub_search(grn_ctx *ctx, grn_pat *pat, grn_id id,
+           int *c0, uint8_t *key, uint32_t key_len)
+{
+  pat_node *pn;
+  uint32_t len = key_len * 16;
+  if (!key_len) { return id; }
+  PAT_AT(pat, id, pn);
+  while (pn) {
+    int ch;
+    ch = PAT_CHK(pn);
+    if (*c0 < ch && ch < len - 1) {
+      if (ch & 1) {
+        id = (ch + 1 < len) ? pn->lr[1] : pn->lr[0];
+      } else {
+        id = pn->lr[nth_bit(key, ch, len)];
+      }
+      *c0 = ch;
+      PAT_AT(pat, id, pn);
+    } else {
+      const uint8_t *k = pat_node_get_key(ctx, pat, pn);
+      return (k && key_len <= PAT_LEN(pn) && !memcmp(k, key, key_len)) ? id : GRN_ID_NIL;
+    }
+  }
+  return GRN_ID_NIL;
+}
+
+static void
+search_push(grn_ctx *ctx, grn_pat *pat, grn_pat_cursor *c,
+            uint8_t *key, uint32_t key_len, uint8_t state, grn_id id, int c0, int flags)
+{
+  if (state) {
+    int step;
+    uint16_t ns, ne;
+    if (flags & GRN_CURSOR_DESCENDING) {
+      ns = rk_tree_idx[state - 1];
+      ne = rk_tree_idx[state];
+      step = 1;
+    } else {
+      ns = rk_tree_idx[state] - 1;
+      ne = rk_tree_idx[state - 1] - 1;
+      step = -1;
+    }
+    for (; ns != ne; ns += step) {
+      rk_tree_node *rn = &rk_tree[ns];
+      if (rn->attr) {
+        char *e;
+        uint32_t l = rk_emit(rn, &e);
+        if (l) {
+          if (l + key_len <= GRN_TABLE_MAX_KEY_SIZE) {
+            int ch = c0;
+            grn_id i;
+            grn_memcpy(key + key_len, e, l);
+            if ((i = sub_search(ctx, pat, id, &ch, key, key_len + l))) {
+              search_push(ctx, pat, c, key, key_len + l, rn->next, i, ch, flags);
+            }
+          }
+        } else {
+          search_push(ctx, pat, c, key, key_len, rn->next, id, c0, flags);
+        }
+      }
+    }
+  } else {
+    pat_node *pn;
+    PAT_AT(pat, id, pn);
+    if (pn) {
+      int ch = PAT_CHK(pn);
+      uint32_t len = key_len * 16;
+      if (c0 < ch) {
+        if (flags & GRN_CURSOR_DESCENDING) {
+          if ((ch > len - 1) || !(flags & GRN_CURSOR_GT)) { push(c, pn->lr[0], ch); }
+          push(c, pn->lr[1], ch);
+        } else {
+          push(c, pn->lr[1], ch);
+          if ((ch > len - 1) || !(flags & GRN_CURSOR_GT)) { push(c, pn->lr[0], ch); }
+        }
+      } else {
+        if (PAT_LEN(pn) * 16 > len || !(flags & GRN_CURSOR_GT)) { push(c, id, ch); }
+      }
+    }
+  }
+}
+
+static grn_rc
+set_cursor_rk(grn_ctx *ctx, grn_pat *pat, grn_pat_cursor *c,
+                  const void *key, uint32_t key_len, int flags)
+{
+  grn_id id;
+  uint8_t state;
+  pat_node *pn;
+  int c0 = -1;
+  uint32_t len, byte_len;
+  uint8_t keybuf[GRN_TABLE_MAX_KEY_SIZE];
+  if (flags & GRN_CURSOR_SIZE_BY_BIT) { return GRN_OPERATION_NOT_SUPPORTED; }
+  byte_len = rk_conv(key, key_len, keybuf, GRN_TABLE_MAX_KEY_SIZE, &state);
+  len = byte_len * 16;
+  PAT_AT(pat, 0, pn);
+  id = pn->lr[1];
+  if ((id = sub_search(ctx, pat, id, &c0, keybuf, byte_len))) {
+    search_push(ctx, pat, c, keybuf, byte_len, state, id, c0, flags);
+  }
+  return ctx->rc;
+}
+
+uint32_t
+grn_pat_total_key_size(grn_ctx *ctx, grn_pat *pat)
+{
+  return pat->header->curr_key;
+}
+
+grn_bool
+grn_pat_is_key_encoded(grn_ctx *ctx, grn_pat *pat)
+{
+  grn_obj *domain;
+  uint32_t key_size;
+
+  domain = grn_ctx_at(ctx, pat->obj.header.domain);
+  if (grn_obj_is_type(ctx, domain)) {
+    key_size = grn_type_size(ctx, domain);
+  } else {
+    key_size = sizeof(grn_id);
+  }
+
+  return KEY_NEEDS_CONVERT(pat, key_size);
+}
+
+grn_rc
+grn_pat_dirty(grn_ctx *ctx, grn_pat *pat)
+{
+  grn_rc rc = GRN_SUCCESS;
+
+  CRITICAL_SECTION_ENTER(pat->lock);
+  if (!pat->is_dirty) {
+    uint32_t n_dirty_opens;
+    pat->is_dirty = GRN_TRUE;
+    GRN_ATOMIC_ADD_EX(&(pat->header->n_dirty_opens), 1, n_dirty_opens);
+    rc = grn_io_flush(ctx, pat->io);
+  }
+  CRITICAL_SECTION_LEAVE(pat->lock);
+
+  return rc;
+}
+
+grn_bool
+grn_pat_is_dirty(grn_ctx *ctx, grn_pat *pat)
+{
+  return pat->header->n_dirty_opens > 0;
+}
+
+grn_rc
+grn_pat_clean(grn_ctx *ctx, grn_pat *pat)
+{
+  grn_rc rc = GRN_SUCCESS;
+
+  CRITICAL_SECTION_ENTER(pat->lock);
+  if (pat->is_dirty) {
+    uint32_t n_dirty_opens;
+    pat->is_dirty = GRN_FALSE;
+    GRN_ATOMIC_ADD_EX(&(pat->header->n_dirty_opens), -1, n_dirty_opens);
+    rc = grn_io_flush(ctx, pat->io);
+  }
+  CRITICAL_SECTION_LEAVE(pat->lock);
+
+  return rc;
+}
+
+grn_rc
+grn_pat_clear_dirty(grn_ctx *ctx, grn_pat *pat)
+{
+  grn_rc rc = GRN_SUCCESS;
+
+  CRITICAL_SECTION_ENTER(pat->lock);
+  pat->is_dirty = GRN_FALSE;
+  pat->header->n_dirty_opens = 0;
+  rc = grn_io_flush(ctx, pat->io);
+  CRITICAL_SECTION_LEAVE(pat->lock);
+
+  return rc;
+}