pat.c

Go to the documentation of this file.

/* -*- c-basic-offset: 2 -*- */
/* Copyright(C) 2009-2012 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-1301  USA
*/
#include "groonga_in.h"
#include <string.h>
#include <limits.h>
#include "pat.h"
#include "output.h"
#include "util.h"
#include "normalizer_in.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, deleting : 1, immediate : 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
};

/* 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;
}

inline static pat_node *
pat_node_new(grn_ctx *ctx, grn_pat *pat, grn_id *id)
{
  uint32_t n = pat->header->curr_rec + 1;
  pat_node *res;
  if (n > GRN_ID_MAX) { return NULL; }
  if ((res = pat_get(ctx, pat, n))) {
    pat->header->curr_rec = n;
    pat->header->n_entries++;
  }
  if (id) { *id = n; }
  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, int len)
{
  uint32_t res, ts;
//  if (len >= GRN_PAT_SEGMENT_SIZE) { return 0; /* error */ }
  res = pat->header->curr_key;
  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) { return 0; }
    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, unsigned int len)
{
  if (!key || !len) { return GRN_INVALID_ARGUMENT; }
  PAT_LEN_SET(n, len);
  if (len <= sizeof(uint32_t)) {
    PAT_IMD_ON(n);
    memcpy(&n->key, key, len);
  } else {
    PAT_IMD_OFF(n);
    n->key = key_put(ctx, pat, key, len);
  }
  return GRN_SUCCESS;
}

/* delinfo operation */

enum {
  DL_EMPTY = 0,
  DL_PHASE1,
  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; }
  if (!(d = di->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 r, *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];
    while ((r = *p0)) {
      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 = -1;
  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;
  }
  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_MALLOC(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;
  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;
  io = grn_io_open(ctx, path, grn_io_auto);
  if (!io) { return NULL; }
  header = grn_io_header(io);
  if (grn_io_get_type(io) != GRN_TABLE_PAT_KEY) {
    ERR(GRN_INVALID_FORMAT, "file type unmatch");
    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);
  }
  pat->obj.header.flags = header->flags;
  PAT_AT(pat, 0, node0);
  if (!node0) {
    grn_io_close(ctx, io);
    GRN_GFREE(pat);
    return NULL;
  }
  pat->cache = NULL;
  pat->cache_size = 0;
  return pat;
}

grn_rc
grn_pat_close(grn_ctx *ctx, grn_pat *pat)
{
  grn_rc rc;
  if ((rc = grn_io_close(ctx, pat->io))) {
    ERR(rc, "grn_io_close failed");
  } else {
    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;

  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 ((rc = grn_io_close(ctx, pat->io))) { goto exit; }
  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;
  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];
        }
      }
    }
  }

  *new = 0;
  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 0; }
        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 0; }
        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 0; }
            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 0; }
  } 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->header->n_entries++;
        pat->header->n_garbages--;
        PAT_AT(pat, r, rn);
        if (!rn) { return 0; }
        pat->header->garbages[0] = rn->lr[0];
      } else {
        if (!(rn = pat_node_new(ctx, pat, &r))) { return 0; }
      }
      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->header->n_entries++;
        pat->header->n_garbages--;
        PAT_AT(pat, r, rn);
        if (!rn) { return 0; }
        pat->header->garbages[size2] = rn->lr[0];
        if (!(keybuf = pat_node_get_key(ctx, pat, rn))) { return 0; }
        PAT_LEN_SET(rn, size);
        memcpy(keybuf, key, size);
      } else {
        if (!(rn = pat_node_new(ctx, pat, &r))) { return 0; }
        pat_node_set_key(ctx, pat, rn, key, size);
      }
      *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 int
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 **key;
  } else {
    return 0;
  }
}

#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)|(1LL << 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 ^ (((v^(1LL<<63))>> 63)|(1LL<<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 (!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 (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];
  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 (!(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];
  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 || !(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;
}

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;
  uint8_t direction;
  pat_node *rn, *rn0 = NULL, *rno;
  int c, c0 = -1, ch;
  uint32_t len = key_size * 16;
  grn_id r, otherside, *proot, *p, *p0 = NULL;

  di = delinfo_new(ctx, pat); /* must be called before find rn */
  di->shared = shared;
  PAT_AT(pat, 0, rn);
  c = -1;
  proot = p = &rn->lr[1];
  for (;;) {
    if (!(r = *p)) { 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) {
      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)) {
        break; /* found */
      } else {  return GRN_INVALID_ARGUMENT; }
    }
    c0 = c;
    p0 = p;
    if ((c = ch) & 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;
  }
  direction = (rn0->lr[1] == r);
  otherside = direction ? rn0->lr[0] : rn0->lr[1];
  if (rn == rn0) {
    di->stat = DL_PHASE2;
    di->d = r;
    if (otherside) {
      PAT_AT(pat, otherside, rno);
      if (rno && c0 < PAT_CHK(rno) && PAT_CHK(rno) <= c) {
        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) { rno->lr[0] = rno->lr[1] = otherside; }
    }
    *p0 = otherside;
  } else {
    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) {
      PAT_CHK_SET(rn0, 0);
      if (proot == p0 && !rn0->check) { rn0->lr[0] = rn0->lr[1] = otherside; }
    } else {
      if (otherside) {
        PAT_AT(pat, otherside, rno);
        if (rno && c0 < PAT_CHK(rno) && PAT_CHK(rno) <= c) {
          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) { rno->lr[0] = rno->lr[1] = otherside; }
      }
      *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)
{
  uint8_t keybuf[MAX_FIXED_KEY_SIZE];
  if (!pat || !key || !key_size) { return GRN_INVALID_ARGUMENT; }
  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; }
  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;
  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)
{
  if (!pat || !id) { return GRN_INVALID_ARGUMENT; }
  {
    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 GRN_INVALID_ARGUMENT; }
  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 {
      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; }
  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 = (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) {
          memcpy(valuebuf, v + sizeof(sis_node), value_size);
        } else {
          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 ((*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)
{
  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 :
          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)
{
  ERRCLR(NULL);
  if (!pat) { return GRN_INVALID_ARGUMENT; }
  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) {
    grn_rc rc;
    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 = 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)
{
  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)
{
  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 (pat->normalizer) {
    grn_obj *nstr = grn_string_open(ctx, str, str_len,
                                    pat->normalizer, GRN_STRING_WITH_CHECKS);
    if (nstr) {
      const short *cp = grn_string_get_checks(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))) {
          uint32_t len;
          _grn_pat_key(ctx, pat, tid, &len);
          sh[n].id = tid;
          sh[n].offset = (*cp > 0) ? offset : offset0;
          while (len--) {
            if (*cp > 0) { offset0 = offset; offset += *cp; }
            sp++; cp++;
          }
          sh[n].length = offset - sh[n].offset;
          n++;
        } else {
          if (*cp > 0) { offset0 = offset; offset += *cp; }
          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;
    for (;;) {
      if (id) {
        PAT_AT(c->pat, id, node);
        if (node) {
          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;
          }
        }
      } else {
        break;
      }
    }
  }
  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 ((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;
  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();
}

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

  if (c > check) {
    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_pat_inspect_check(ctx, buf, c);

    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, "]");
  }

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

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);\
    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;
            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;
}