diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-05-04 18:07:14 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-05-04 18:07:14 +0000 |
commit | a175314c3e5827eb193872241446f2f8f5c9d33c (patch) | |
tree | cd3d60ca99ae00829c52a6ca79150a5b6e62528b /storage/mroonga/vendor/groonga/lib/pat.c | |
parent | Initial commit. (diff) | |
download | mariadb-10.5-upstream.tar.xz mariadb-10.5-upstream.zip |
Adding upstream version 1:10.5.12.upstream/1%10.5.12upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to '')
-rw-r--r-- | storage/mroonga/vendor/groonga/lib/pat.c | 3674 |
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; +} |