1/* -*- c-basic-offset: 2 -*- */
2/*
3 Copyright(C) 2009-2017 Brazil
4
5 This library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Lesser General Public
7 License version 2.1 as published by the Free Software Foundation.
8
9 This library is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 Lesser General Public License for more details.
13
14 You should have received a copy of the GNU Lesser General Public
15 License along with this library; if not, write to the Free Software
16 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17*/
18#include "grn.h"
19#include <string.h>
20#include <limits.h>
21#include "grn_pat.h"
22#include "grn_output.h"
23#include "grn_util.h"
24#include "grn_normalizer.h"
25
26#define GRN_PAT_DELETED (GRN_ID_MAX + 1)
27
28#define GRN_PAT_SEGMENT_SIZE 0x400000
29#define W_OF_KEY_IN_A_SEGMENT 22
30#define W_OF_PAT_IN_A_SEGMENT 18
31#define W_OF_SIS_IN_A_SEGMENT 19
32#define KEY_MASK_IN_A_SEGMENT 0x3fffff
33#define PAT_MASK_IN_A_SEGMENT 0x3ffff
34#define SIS_MASK_IN_A_SEGMENT 0x7ffff
35#define SEG_NOT_ASSIGNED 0xffff
36#define GRN_PAT_MAX_SEGMENT 0x1000
37#define GRN_PAT_MDELINFOS (GRN_PAT_NDELINFOS - 1)
38
39#define GRN_PAT_BIN_KEY 0x70000
40
41typedef struct {
42 grn_id lr[2];
43 /*
44 lr[0]: the left node.
45 lr[1]: the right node.
46
47 The left node has 0 at the nth bit at the nth byte.
48 The right node has 1 at the nth bit at the nth byte.
49 'check' value indicate 'at the nth bit at the nth byte'.
50
51 The both available nodes has larger check value rather
52 than the current node.
53
54 The first node (PAT_AT(pat, GRN_ID_NIL, node)) has only
55 the right node and the node is the start point.
56 */
57 uint32_t key;
58 /*
59 PAT_IMD(node) == 0: key bytes offset in memory map.
60 PAT_IMD(node) == 1: the key bytes.
61 */
62 uint16_t check;
63 /*
64 nth byte: 12, nth bit: 3, terminated: 1
65
66 nth byte is different in key bytes: (check >> 4): max == 4095
67 the left most byte is the 0th byte and the right most byte is the 11th byte.
68
69 nth bit is different in nth byte: ((check >> 1) & 0b111)
70 the left most bit is the 0th bit and the right most bit is the 7th bit.
71
72 terminated: (check & 0b1)
73 terminated == 1: key is terminated.
74 */
75 uint16_t bits;
76 /* length: 13, immediate: 1, deleting: 1 */
77} pat_node;
78
79#define PAT_DELETING (1<<1)
80#define PAT_IMMEDIATE (1<<2)
81
82#define PAT_DEL(x) ((x)->bits & PAT_DELETING)
83#define PAT_IMD(x) ((x)->bits & PAT_IMMEDIATE)
84#define PAT_LEN(x) (((x)->bits >> 3) + 1)
85#define PAT_CHK(x) ((x)->check)
86#define PAT_DEL_ON(x) ((x)->bits |= PAT_DELETING)
87#define PAT_IMD_ON(x) ((x)->bits |= PAT_IMMEDIATE)
88#define PAT_DEL_OFF(x) ((x)->bits &= ~PAT_DELETING)
89#define PAT_IMD_OFF(x) ((x)->bits &= ~PAT_IMMEDIATE)
90#define PAT_LEN_SET(x,v) ((x)->bits = ((x)->bits & ((1<<3) - 1))|(((v) - 1) << 3))
91#define PAT_CHK_SET(x,v) ((x)->check = (v))
92
93typedef struct {
94 grn_id children;
95 grn_id sibling;
96} sis_node;
97
98enum {
99 segment_key = 0,
100 segment_pat = 1,
101 segment_sis = 2
102};
103
104void grn_p_pat_node(grn_ctx *ctx, grn_pat *pat, pat_node *node);
105
106/* error utilities */
107inline static int
108grn_pat_name(grn_ctx *ctx, grn_pat *pat, char *buffer, int buffer_size)
109{
110 int name_size;
111
112 if (DB_OBJ(pat)->id == GRN_ID_NIL) {
113 grn_strcpy(buffer, buffer_size, "(anonymous)");
114 name_size = strlen(buffer);
115 } else {
116 name_size = grn_obj_name(ctx, (grn_obj *)pat, buffer, buffer_size);
117 }
118
119 return name_size;
120}
121
122/* bit operation */
123
124#define nth_bit(key,n,l) ((((key)[(n)>>4]) >> (7 - (((n)>>1) & 7))) & 1)
125
126/* segment operation */
127
128/* patricia array operation */
129
130#define PAT_AT(pat,id,n) do {\
131 int flags = 0;\
132 GRN_IO_ARRAY_AT(pat->io, segment_pat, id, &flags, n);\
133} while (0)
134
135inline static pat_node *
136pat_get(grn_ctx *ctx, grn_pat *pat, grn_id id)
137{
138 pat_node *res;
139 int flags = GRN_TABLE_ADD;
140 if (id > GRN_ID_MAX) { return NULL; }
141 GRN_IO_ARRAY_AT(pat->io, segment_pat, id, &flags, res);
142 return res;
143}
144
145inline static pat_node *
146pat_node_new(grn_ctx *ctx, grn_pat *pat, grn_id *id)
147{
148 uint32_t n = pat->header->curr_rec + 1;
149 pat_node *res;
150 if (n > GRN_ID_MAX) { return NULL; }
151 if ((res = pat_get(ctx, pat, n))) {
152 pat->header->curr_rec = n;
153 pat->header->n_entries++;
154 }
155 if (id) { *id = n; }
156 return res;
157}
158
159/* sis operation */
160
161inline static sis_node *
162sis_at(grn_ctx *ctx, grn_pat *pat, grn_id id)
163{
164 sis_node *res;
165 int flags = 0;
166 if (id > GRN_ID_MAX) { return NULL; }
167 GRN_IO_ARRAY_AT(pat->io, segment_sis, id, &flags, res);
168 return res;
169}
170
171inline static sis_node *
172sis_get(grn_ctx *ctx, grn_pat *pat, grn_id id)
173{
174 sis_node *res;
175 int flags = GRN_TABLE_ADD;
176 if (id > GRN_ID_MAX) { return NULL; }
177 GRN_IO_ARRAY_AT(pat->io, segment_sis, id, &flags, res);
178 return res;
179}
180
181#define MAX_LEVEL 16
182
183static void
184sis_collect(grn_ctx *ctx, grn_pat *pat, grn_hash *h, grn_id id, uint32_t level)
185{
186 uint32_t *offset;
187 sis_node *sl = sis_at(ctx, pat, id);
188 if (sl) {
189 grn_id sid = sl->children;
190 while (sid && sid != id) {
191 if (grn_hash_add(ctx, h, &sid, sizeof(grn_id), (void **) &offset, NULL)) {
192 *offset = level;
193 if (level < MAX_LEVEL) { sis_collect(ctx, pat, h, sid, level + 1); }
194 if (!(sl = sis_at(ctx, pat, sid))) { break; }
195 sid = sl->sibling;
196 } else {
197 /* todo : must be handled */
198 }
199 }
200 }
201}
202
203/* key operation */
204
205#define KEY_AT(pat,pos,ptr,addp) do {\
206 int flags = addp;\
207 GRN_IO_ARRAY_AT(pat->io, segment_key, pos, &flags, ptr);\
208} while (0)
209
210inline static uint32_t
211key_put(grn_ctx *ctx, grn_pat *pat, const uint8_t *key, uint32_t len)
212{
213 uint32_t res, ts;
214// if (len >= GRN_PAT_SEGMENT_SIZE) { return 0; /* error */ }
215 res = pat->header->curr_key;
216 if (res < GRN_PAT_MAX_TOTAL_KEY_SIZE &&
217 len > GRN_PAT_MAX_TOTAL_KEY_SIZE - res) {
218 char name[GRN_TABLE_MAX_KEY_SIZE];
219 int name_size;
220 name_size = grn_pat_name(ctx, pat, name, GRN_TABLE_MAX_KEY_SIZE);
221 ERR(GRN_NOT_ENOUGH_SPACE,
222 "[pat][key][put] total key size is over: <%.*s>: "
223 "max=%u: current=%u: new key size=%u",
224 name_size, name,
225 GRN_PAT_MAX_TOTAL_KEY_SIZE,
226 res,
227 len);
228 return 0;
229 }
230
231 ts = (res + len) >> W_OF_KEY_IN_A_SEGMENT;
232 if (res >> W_OF_KEY_IN_A_SEGMENT != ts) {
233 res = pat->header->curr_key = ts << W_OF_KEY_IN_A_SEGMENT;
234 }
235 {
236 uint8_t *dest;
237 KEY_AT(pat, res, dest, GRN_TABLE_ADD);
238 if (!dest) {
239 char name[GRN_TABLE_MAX_KEY_SIZE];
240 int name_size;
241 name_size = grn_pat_name(ctx, pat, name, GRN_TABLE_MAX_KEY_SIZE);
242 ERR(GRN_NO_MEMORY_AVAILABLE,
243 "[pat][key][put] failed to allocate memory for new key: <%.*s>: "
244 "new offset:%u key size:%u",
245 name_size, name,
246 res,
247 len);
248 return 0;
249 }
250 grn_memcpy(dest, key, len);
251 }
252 pat->header->curr_key += len;
253 return res;
254}
255
256inline static uint8_t *
257pat_node_get_key(grn_ctx *ctx, grn_pat *pat, pat_node *n)
258{
259 if (PAT_IMD(n)) {
260 return (uint8_t *) &n->key;
261 } else {
262 uint8_t *res;
263 KEY_AT(pat, n->key, res, 0);
264 return res;
265 }
266}
267
268inline static grn_rc
269pat_node_set_key(grn_ctx *ctx, grn_pat *pat, pat_node *n, const uint8_t *key, uint32_t len)
270{
271 grn_rc rc;
272 if (!key || !len) { return GRN_INVALID_ARGUMENT; }
273 PAT_LEN_SET(n, len);
274 if (len <= sizeof(uint32_t)) {
275 PAT_IMD_ON(n);
276 grn_memcpy(&n->key, key, len);
277 rc = GRN_SUCCESS;
278 } else {
279 PAT_IMD_OFF(n);
280 n->key = key_put(ctx, pat, key, len);
281 rc = ctx->rc;
282 }
283 return rc;
284}
285
286/* delinfo operation */
287
288enum {
289 /* The delinfo is currently not used. */
290 DL_EMPTY = 0,
291 /*
292 * stat->d refers to a deleting node (in a tree).
293 * The deletion requires an additional operation.
294 */
295 DL_PHASE1,
296 /*
297 * stat->d refers to a deleted node (not in a tree).
298 * The node is pending for safety.
299 */
300 DL_PHASE2
301};
302
303inline static grn_pat_delinfo *
304delinfo_search(grn_pat *pat, grn_id id)
305{
306 int i;
307 grn_pat_delinfo *di;
308 for (i = (pat->header->curr_del2) & GRN_PAT_MDELINFOS;
309 i != pat->header->curr_del;
310 i = (i + 1) & GRN_PAT_MDELINFOS) {
311 di = &pat->header->delinfos[i];
312 if (di->stat != DL_PHASE1) { continue; }
313 if (di->ld == id) { return di; }
314 if (di->d == id) { return di; }
315 }
316 return NULL;
317}
318
319inline static grn_rc
320delinfo_turn_2(grn_ctx *ctx, grn_pat *pat, grn_pat_delinfo *di)
321{
322 grn_id d, *p = NULL;
323 pat_node *ln, *dn;
324 // grn_log("delinfo_turn_2> di->d=%d di->ld=%d stat=%d", di->d, di->ld, di->stat);
325 if (di->stat != DL_PHASE1) {
326 return GRN_SUCCESS;
327 }
328 PAT_AT(pat, di->ld, ln);
329 if (!ln) {
330 return GRN_INVALID_ARGUMENT;
331 }
332 d = di->d;
333 if (!d) {
334 return GRN_INVALID_ARGUMENT;
335 }
336 PAT_AT(pat, d, dn);
337 if (!dn) {
338 return GRN_INVALID_ARGUMENT;
339 }
340 PAT_DEL_OFF(ln);
341 PAT_DEL_OFF(dn);
342 {
343 grn_id *p0;
344 pat_node *rn;
345 int c0 = -1, c;
346 uint32_t len = PAT_LEN(dn) * 16;
347 const uint8_t *key = pat_node_get_key(ctx, pat, dn);
348 if (!key) {
349 return GRN_INVALID_ARGUMENT;
350 }
351 PAT_AT(pat, 0, rn);
352 p0 = &rn->lr[1];
353 for (;;) {
354 grn_id r = *p0;
355 if (!r) {
356 break;
357 }
358 if (r == d) {
359 p = p0;
360 break;
361 }
362 PAT_AT(pat, r, rn);
363 if (!rn) {
364 return GRN_FILE_CORRUPT;
365 }
366 c = PAT_CHK(rn);
367 if (c <= c0 || len <= c) {
368 break;
369 }
370 if (c & 1) {
371 p0 = (c + 1 < len) ? &rn->lr[1] : &rn->lr[0];
372 } else {
373 p0 = &rn->lr[nth_bit((uint8_t *)key, c, len)];
374 }
375 c0 = c;
376 }
377 }
378 if (p) {
379 PAT_CHK_SET(ln, PAT_CHK(dn));
380 ln->lr[1] = dn->lr[1];
381 ln->lr[0] = dn->lr[0];
382 *p = di->ld;
383 } else {
384 /* debug */
385 int j;
386 grn_id dd;
387 grn_pat_delinfo *ddi;
388 GRN_LOG(ctx, GRN_LOG_DEBUG, "failed to find d=%d", d);
389 for (j = (pat->header->curr_del2 + 1) & GRN_PAT_MDELINFOS;
390 j != pat->header->curr_del;
391 j = (j + 1) & GRN_PAT_MDELINFOS) {
392 ddi = &pat->header->delinfos[j];
393 if (ddi->stat != DL_PHASE1) { continue; }
394 PAT_AT(pat, ddi->ld, ln);
395 if (!ln) { continue; }
396 if (!(dd = ddi->d)) { continue; }
397 if (d == ddi->ld) {
398 GRN_LOG(ctx, GRN_LOG_DEBUG, "found!!!, d(%d) become ld of (%d)", d, dd);
399 }
400 }
401 /* debug */
402 }
403 di->stat = DL_PHASE2;
404 di->d = d;
405 // grn_log("delinfo_turn_2< di->d=%d di->ld=%d", di->d, di->ld);
406 return GRN_SUCCESS;
407}
408
409inline static grn_rc
410delinfo_turn_3(grn_ctx *ctx, grn_pat *pat, grn_pat_delinfo *di)
411{
412 pat_node *dn;
413 uint32_t size;
414 if (di->stat != DL_PHASE2) { return GRN_SUCCESS; }
415 PAT_AT(pat, di->d, dn);
416 if (!dn) { return GRN_INVALID_ARGUMENT; }
417 if (di->shared) {
418 PAT_IMD_ON(dn);
419 size = 0;
420 } else {
421 if (PAT_IMD(dn)) {
422 size = 0;
423 } else {
424 size = PAT_LEN(dn);
425 }
426 }
427 di->stat = DL_EMPTY;
428 // dn->lr[1] = GRN_PAT_DELETED;
429 dn->lr[0] = pat->header->garbages[size];
430 pat->header->garbages[size] = di->d;
431 return GRN_SUCCESS;
432}
433
434inline static grn_pat_delinfo *
435delinfo_new(grn_ctx *ctx, grn_pat *pat)
436{
437 grn_pat_delinfo *res = &pat->header->delinfos[pat->header->curr_del];
438 uint32_t n = (pat->header->curr_del + 1) & GRN_PAT_MDELINFOS;
439 int gap = ((n + GRN_PAT_NDELINFOS - pat->header->curr_del2) & GRN_PAT_MDELINFOS)
440 - (GRN_PAT_NDELINFOS / 2);
441 while (gap-- > 0) {
442 if (delinfo_turn_2(ctx, pat, &pat->header->delinfos[pat->header->curr_del2])) {
443 GRN_LOG(ctx, GRN_LOG_CRIT, "d2 failed: %d", pat->header->delinfos[pat->header->curr_del2].ld);
444 }
445 pat->header->curr_del2 = (pat->header->curr_del2 + 1) & GRN_PAT_MDELINFOS;
446 }
447 if (n == pat->header->curr_del3) {
448 if (delinfo_turn_3(ctx, pat, &pat->header->delinfos[pat->header->curr_del3])) {
449 GRN_LOG(ctx, GRN_LOG_CRIT, "d3 failed: %d", pat->header->delinfos[pat->header->curr_del3].ld);
450 }
451 pat->header->curr_del3 = (pat->header->curr_del3 + 1) & GRN_PAT_MDELINFOS;
452 }
453 pat->header->curr_del = n;
454 return res;
455}
456
457/* pat operation */
458
459inline static grn_pat *
460_grn_pat_create(grn_ctx *ctx, grn_pat *pat,
461 const char *path, uint32_t key_size,
462 uint32_t value_size, uint32_t flags) {
463 grn_io *io;
464 pat_node *node0;
465 struct grn_pat_header *header;
466 uint32_t entry_size, w_of_element;
467 grn_encoding encoding = ctx->encoding;
468 if (flags & GRN_OBJ_KEY_WITH_SIS) {
469 entry_size = sizeof(sis_node) + value_size;
470 } else {
471 entry_size = value_size;
472 }
473 for (w_of_element = 0; (1 << w_of_element) < entry_size; w_of_element++) {
474 /* nop */
475 }
476 {
477 grn_io_array_spec array_spec[3];
478 array_spec[segment_key].w_of_element = 0;
479 array_spec[segment_key].max_n_segments = 0x400;
480 array_spec[segment_pat].w_of_element = 4;
481 array_spec[segment_pat].max_n_segments = 1 << (30 - (22 - 4));
482 array_spec[segment_sis].w_of_element = w_of_element;
483 array_spec[segment_sis].max_n_segments = 1 << (30 - (22 - w_of_element));
484 io = grn_io_create_with_array(ctx, path, sizeof(struct grn_pat_header),
485 GRN_PAT_SEGMENT_SIZE, grn_io_auto, 3, array_spec);
486 }
487 if (!io) { return NULL; }
488 if (encoding == GRN_ENC_DEFAULT) { encoding = grn_gctx.encoding; }
489 header = grn_io_header(io);
490 grn_io_set_type(io, GRN_TABLE_PAT_KEY);
491 header->flags = flags;
492 header->encoding = encoding;
493 header->key_size = key_size;
494 header->value_size = value_size;
495 header->n_entries = 0;
496 header->curr_rec = 0;
497 header->curr_key = 0;
498 header->curr_del = 0;
499 header->curr_del2 = 0;
500 header->curr_del3 = 0;
501 header->n_garbages = 0;
502 header->tokenizer = GRN_ID_NIL;
503 if (header->flags & GRN_OBJ_KEY_NORMALIZE) {
504 header->flags &= ~GRN_OBJ_KEY_NORMALIZE;
505 pat->normalizer = grn_ctx_get(ctx, GRN_NORMALIZER_AUTO_NAME, -1);
506 header->normalizer = grn_obj_id(ctx, pat->normalizer);
507 } else {
508 pat->normalizer = NULL;
509 header->normalizer = GRN_ID_NIL;
510 }
511 header->truncated = GRN_FALSE;
512 GRN_PTR_INIT(&(pat->token_filters), GRN_OBJ_VECTOR, GRN_ID_NIL);
513 pat->io = io;
514 pat->header = header;
515 pat->key_size = key_size;
516 pat->value_size = value_size;
517 pat->tokenizer = NULL;
518 pat->encoding = encoding;
519 pat->obj.header.flags = header->flags;
520 if (!(node0 = pat_get(ctx, pat, 0))) {
521 grn_io_close(ctx, io);
522 return NULL;
523 }
524 node0->lr[1] = 0;
525 node0->lr[0] = 0;
526 node0->key = 0;
527 return pat;
528}
529
530grn_pat *
531grn_pat_create(grn_ctx *ctx, const char *path, uint32_t key_size,
532 uint32_t value_size, uint32_t flags)
533{
534 grn_pat *pat;
535 if (!(pat = GRN_CALLOC(sizeof(grn_pat)))) {
536 return NULL;
537 }
538 GRN_DB_OBJ_SET_TYPE(pat, GRN_TABLE_PAT_KEY);
539 if (!_grn_pat_create(ctx, pat, path, key_size, value_size, flags)) {
540 GRN_FREE(pat);
541 return NULL;
542 }
543 pat->cache = NULL;
544 pat->cache_size = 0;
545 pat->is_dirty = GRN_FALSE;
546 CRITICAL_SECTION_INIT(pat->lock);
547 return pat;
548}
549
550/*
551 grn_pat_cache_enable() and grn_pat_cache_disable() are not thread-safe.
552 So far, they can be used only from single threaded programs.
553 */
554
555grn_rc
556grn_pat_cache_enable(grn_ctx *ctx, grn_pat *pat, uint32_t cache_size)
557{
558 if (pat->cache || pat->cache_size) {
559 ERR(GRN_INVALID_ARGUMENT, "cache is already enabled");
560 return ctx->rc;
561 }
562 if (cache_size & (cache_size - 1)) {
563 ERR(GRN_INVALID_ARGUMENT, "cache_size(%u) must be a power of two", cache_size);
564 return ctx->rc;
565 }
566 if (!(pat->cache = GRN_CALLOC(cache_size * sizeof(grn_id)))) {
567 return ctx->rc;
568 }
569 pat->cache_size = cache_size;
570 return GRN_SUCCESS;
571}
572
573void
574grn_pat_cache_disable(grn_ctx *ctx, grn_pat *pat)
575{
576 if (pat->cache) {
577 GRN_FREE(pat->cache);
578 pat->cache_size = 0;
579 pat->cache = NULL;
580 }
581}
582
583grn_pat *
584grn_pat_open(grn_ctx *ctx, const char *path)
585{
586 grn_io *io;
587 grn_pat *pat;
588 pat_node *node0;
589 struct grn_pat_header *header;
590 uint32_t io_type;
591 io = grn_io_open(ctx, path, grn_io_auto);
592 if (!io) { return NULL; }
593 header = grn_io_header(io);
594 io_type = grn_io_get_type(io);
595 if (io_type != GRN_TABLE_PAT_KEY) {
596 ERR(GRN_INVALID_FORMAT, "[table][pat] file type must be %#04x: <%#04x>",
597 GRN_TABLE_PAT_KEY, io_type);
598 grn_io_close(ctx, io);
599 return NULL;
600 }
601 if (!(pat = GRN_MALLOC(sizeof(grn_pat)))) {
602 grn_io_close(ctx, io);
603 return NULL;
604 }
605 GRN_DB_OBJ_SET_TYPE(pat, GRN_TABLE_PAT_KEY);
606 pat->io = io;
607 pat->header = header;
608 pat->key_size = header->key_size;
609 pat->value_size = header->value_size;
610 pat->encoding = header->encoding;
611 pat->tokenizer = grn_ctx_at(ctx, header->tokenizer);
612 if (header->flags & GRN_OBJ_KEY_NORMALIZE) {
613 header->flags &= ~GRN_OBJ_KEY_NORMALIZE;
614 pat->normalizer = grn_ctx_get(ctx, GRN_NORMALIZER_AUTO_NAME, -1);
615 header->normalizer = grn_obj_id(ctx, pat->normalizer);
616 } else {
617 pat->normalizer = grn_ctx_at(ctx, header->normalizer);
618 }
619 GRN_PTR_INIT(&(pat->token_filters), GRN_OBJ_VECTOR, GRN_ID_NIL);
620 pat->obj.header.flags = header->flags;
621 PAT_AT(pat, 0, node0);
622 if (!node0) {
623 grn_io_close(ctx, io);
624 GRN_FREE(pat);
625 return NULL;
626 }
627 pat->cache = NULL;
628 pat->cache_size = 0;
629 pat->is_dirty = GRN_FALSE;
630 CRITICAL_SECTION_INIT(pat->lock);
631 return pat;
632}
633
634/*
635 * grn_pat_error_if_truncated() logs an error and returns its error code if
636 * a pat is truncated by another process.
637 * Otherwise, this function returns GRN_SUCCESS.
638 * Note that `ctx` and `pat` must be valid.
639 *
640 * FIXME: A pat should be reopened if possible.
641 */
642static grn_rc
643grn_pat_error_if_truncated(grn_ctx *ctx, grn_pat *pat)
644{
645 if (pat->header->truncated) {
646 ERR(GRN_FILE_CORRUPT,
647 "pat is truncated, please unmap or reopen the database");
648 return GRN_FILE_CORRUPT;
649 }
650 return GRN_SUCCESS;
651}
652
653grn_rc
654grn_pat_close(grn_ctx *ctx, grn_pat *pat)
655{
656 grn_rc rc;
657
658 CRITICAL_SECTION_FIN(pat->lock);
659
660 if (pat->is_dirty) {
661 uint32_t n_dirty_opens;
662 GRN_ATOMIC_ADD_EX(&(pat->header->n_dirty_opens), -1, n_dirty_opens);
663 }
664
665 if ((rc = grn_io_close(ctx, pat->io))) {
666 ERR(rc, "grn_io_close failed");
667 } else {
668 grn_pvector_fin(ctx, &pat->token_filters);
669 if (pat->cache) { grn_pat_cache_disable(ctx, pat); }
670 GRN_FREE(pat);
671 }
672
673 return rc;
674}
675
676grn_rc
677grn_pat_remove(grn_ctx *ctx, const char *path)
678{
679 if (!path) {
680 ERR(GRN_INVALID_ARGUMENT, "path is null");
681 return GRN_INVALID_ARGUMENT;
682 }
683 return grn_io_remove(ctx, path);
684}
685
686grn_rc
687grn_pat_truncate(grn_ctx *ctx, grn_pat *pat)
688{
689 grn_rc rc;
690 const char *io_path;
691 char *path;
692 uint32_t key_size, value_size, flags;
693
694 rc = grn_pat_error_if_truncated(ctx, pat);
695 if (rc != GRN_SUCCESS) {
696 return rc;
697 }
698 if ((io_path = grn_io_path(pat->io)) && *io_path != '\0') {
699 if (!(path = GRN_STRDUP(io_path))) {
700 ERR(GRN_NO_MEMORY_AVAILABLE, "cannot duplicate path: <%s>", io_path);
701 return GRN_NO_MEMORY_AVAILABLE;
702 }
703 } else {
704 path = NULL;
705 }
706 key_size = pat->key_size;
707 value_size = pat->value_size;
708 flags = pat->obj.header.flags;
709 if (path) {
710 pat->header->truncated = GRN_TRUE;
711 }
712 if ((rc = grn_io_close(ctx, pat->io))) { goto exit; }
713 grn_pvector_fin(ctx, &pat->token_filters);
714 pat->io = NULL;
715 if (path && (rc = grn_io_remove(ctx, path))) { goto exit; }
716 if (!_grn_pat_create(ctx, pat, path, key_size, value_size, flags)) {
717 rc = GRN_UNKNOWN_ERROR;
718 }
719 if (pat->cache && pat->cache_size) {
720 memset(pat->cache, 0, pat->cache_size * sizeof(grn_id));
721 }
722exit:
723 if (path) { GRN_FREE(path); }
724 return rc;
725}
726
727inline static grn_id
728_grn_pat_add(grn_ctx *ctx, grn_pat *pat, const uint8_t *key, uint32_t size, uint32_t *new, uint32_t *lkey)
729{
730 grn_id r, r0, *p0, *p1 = NULL;
731 pat_node *rn, *rn0;
732 int c, c0 = -1, c1 = -1, len;
733 uint32_t cache_id = 0;
734
735 *new = 0;
736 if (pat->cache) {
737 const uint8_t *p = key;
738 uint32_t length = size;
739 for (cache_id = 0; length--; p++) { cache_id = (cache_id * 37) + *p; }
740 cache_id &= (pat->cache_size - 1);
741 if (pat->cache[cache_id]) {
742 PAT_AT(pat, pat->cache[cache_id], rn);
743 if (rn) {
744 const uint8_t *k = pat_node_get_key(ctx, pat, rn);
745 if (k && size == PAT_LEN(rn) && !memcmp(k, key, size)) {
746 return pat->cache[cache_id];
747 }
748 }
749 }
750 }
751
752 len = (int)size * 16;
753 PAT_AT(pat, 0, rn0);
754 p0 = &rn0->lr[1];
755 if (*p0) {
756 uint32_t size2;
757 int xor, mask;
758 const uint8_t *s, *d;
759 for (;;) {
760 if (!(r0 = *p0)) {
761 if (!(s = pat_node_get_key(ctx, pat, rn0))) { return GRN_ID_NIL; }
762 size2 = PAT_LEN(rn0);
763 break;
764 }
765 PAT_AT(pat, r0, rn0);
766 if (!rn0) { return GRN_ID_NIL; }
767 if (c0 < rn0->check && rn0->check < len) {
768 c1 = c0; c0 = rn0->check;
769 p1 = p0;
770 if (c0 & 1) {
771 p0 = (c0 + 1 < len) ? &rn0->lr[1] : &rn0->lr[0];
772 } else {
773 p0 = &rn0->lr[nth_bit(key, c0, len)];
774 }
775 } else {
776 if (!(s = pat_node_get_key(ctx, pat, rn0))) { return GRN_ID_NIL; }
777 size2 = PAT_LEN(rn0);
778 if (size == size2 && !memcmp(s, key, size)) {
779 if (pat->cache) { pat->cache[cache_id] = r0; }
780 return r0;
781 }
782 break;
783 }
784 }
785 {
786 uint32_t min = size > size2 ? size2 : size;
787 for (c = 0, d = key; min && *s == *d; c += 16, s++, d++, min--);
788 if (min) {
789 for (xor = *s ^ *d, mask = 0x80; !(xor & mask); mask >>= 1, c += 2);
790 } else {
791 c--;
792 }
793 }
794 if (c == c0 && !*p0) {
795 if (c < len - 2) { c += 2; }
796 } else {
797 if (c < c0) {
798 if (c > c1) {
799 p0 = p1;
800 } else {
801 PAT_AT(pat, 0, rn0);
802 p0 = &rn0->lr[1];
803 while ((r0 = *p0)) {
804 PAT_AT(pat, r0, rn0);
805 if (!rn0) { return GRN_ID_NIL; }
806 c0 = PAT_CHK(rn0);
807 if (c < c0) { break; }
808 if (c0 & 1) {
809 p0 = (c0 + 1 < len) ? &rn0->lr[1] : &rn0->lr[0];
810 } else {
811 p0 = &rn0->lr[nth_bit(key, c0, len)];
812 }
813 }
814 }
815 }
816 }
817 if (c >= len) { return GRN_ID_NIL; }
818 } else {
819 c = len - 2;
820 }
821 {
822 uint32_t size2 = size > sizeof(uint32_t) ? size : 0;
823 if (*lkey && size2) {
824 if (pat->header->garbages[0]) {
825 r = pat->header->garbages[0];
826 PAT_AT(pat, r, rn);
827 if (!rn) { return GRN_ID_NIL; }
828 pat->header->n_entries++;
829 pat->header->n_garbages--;
830 pat->header->garbages[0] = rn->lr[0];
831 } else {
832 r = pat->header->curr_rec + 1;
833 rn = pat_get(ctx, pat, r);
834 if (!rn) { return GRN_ID_NIL; }
835 pat->header->curr_rec = r;
836 pat->header->n_entries++;
837 }
838 PAT_IMD_OFF(rn);
839 PAT_LEN_SET(rn, size);
840 rn->key = *lkey;
841 } else {
842 if (pat->header->garbages[size2]) {
843 uint8_t *keybuf;
844 r = pat->header->garbages[size2];
845 PAT_AT(pat, r, rn);
846 if (!rn) { return GRN_ID_NIL; }
847 if (!(keybuf = pat_node_get_key(ctx, pat, rn))) { return GRN_ID_NIL; }
848 pat->header->n_entries++;
849 pat->header->n_garbages--;
850 pat->header->garbages[size2] = rn->lr[0];
851 PAT_LEN_SET(rn, size);
852 grn_memcpy(keybuf, key, size);
853 } else {
854 r = pat->header->curr_rec + 1;
855 rn = pat_get(ctx, pat, r);
856 if (!rn) { return GRN_ID_NIL; }
857 if (pat_node_set_key(ctx, pat, rn, key, size)) { return GRN_ID_NIL; }
858 pat->header->curr_rec = r;
859 pat->header->n_entries++;
860 }
861 *lkey = rn->key;
862 }
863 }
864 PAT_CHK_SET(rn, c);
865 PAT_DEL_OFF(rn);
866 if ((c & 1) ? (c + 1 < len) : nth_bit(key, c, len)) {
867 rn->lr[1] = r;
868 rn->lr[0] = *p0;
869 } else {
870 rn->lr[1] = *p0;
871 rn->lr[0] = r;
872 }
873 // smp_wmb();
874 *p0 = r;
875 *new = 1;
876 if (pat->cache) { pat->cache[cache_id] = r; }
877 return r;
878}
879
880inline static grn_bool
881chop(grn_ctx *ctx, grn_pat *pat, const char **key, const char *end, uint32_t *lkey)
882{
883 size_t len = grn_charlen(ctx, *key, end);
884 if (len) {
885 *lkey += len;
886 *key += len;
887 return (end - *key) > 0;
888 } else {
889 return GRN_FALSE;
890 }
891}
892
893#define MAX_FIXED_KEY_SIZE (sizeof(int64_t))
894
895#define KEY_NEEDS_CONVERT(pat,size) \
896 (!((pat)->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) && (size) <= MAX_FIXED_KEY_SIZE)
897
898#define KEY_ENC(pat,keybuf,key,size) do {\
899 switch ((pat)->obj.header.flags & GRN_OBJ_KEY_MASK) {\
900 case GRN_OBJ_KEY_UINT :\
901 if (((pat)->obj.header.domain != GRN_DB_TOKYO_GEO_POINT) &&\
902 ((pat)->obj.header.domain != GRN_DB_WGS84_GEO_POINT)) {\
903 grn_hton((keybuf), (key), (size));\
904 break;\
905 }\
906 case GRN_OBJ_KEY_GEO_POINT :\
907 grn_gton((keybuf), (key), (size));\
908 break;\
909 case GRN_OBJ_KEY_INT :\
910 grn_hton((keybuf), (key), (size));\
911 *((uint8_t *)(keybuf)) ^= 0x80;\
912 break;\
913 case GRN_OBJ_KEY_FLOAT :\
914 if ((size) == sizeof(int64_t)) {\
915 int64_t v = *(int64_t *)(key);\
916 v ^= ((v >> 63)|(1LL << 63));\
917 grn_hton((keybuf), &v, (size));\
918 }\
919 break;\
920 }\
921} while (0)
922
923#define KEY_DEC(pat,keybuf,key,size) do {\
924 switch ((pat)->obj.header.flags & GRN_OBJ_KEY_MASK) {\
925 case GRN_OBJ_KEY_UINT :\
926 if (((pat)->obj.header.domain != GRN_DB_TOKYO_GEO_POINT) &&\
927 ((pat)->obj.header.domain != GRN_DB_WGS84_GEO_POINT)) {\
928 grn_ntoh((keybuf), (key), (size));\
929 break;\
930 }\
931 case GRN_OBJ_KEY_GEO_POINT :\
932 grn_ntog((keybuf), (key), (size));\
933 break;\
934 case GRN_OBJ_KEY_INT :\
935 grn_ntohi((keybuf), (key), (size));\
936 break;\
937 case GRN_OBJ_KEY_FLOAT :\
938 if ((size) == sizeof(int64_t)) {\
939 int64_t v;\
940 grn_hton(&v, (key), (size));\
941 *((int64_t *)(keybuf)) = v ^ (((v^(1LL<<63))>> 63)|(1LL<<63)); \
942 }\
943 break;\
944 }\
945} while (0)
946
947#define KEY_ENCODE(pat,keybuf,key,size) do {\
948 if (KEY_NEEDS_CONVERT(pat,size)) {\
949 KEY_ENC((pat), (keybuf), (key), (size));\
950 (key) = (keybuf);\
951 }\
952} while (0)
953
954grn_id
955grn_pat_add(grn_ctx *ctx, grn_pat *pat, const void *key, uint32_t key_size,
956 void **value, int *added)
957{
958 uint32_t new, lkey = 0;
959 grn_id r0;
960 uint8_t keybuf[MAX_FIXED_KEY_SIZE];
961 if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
962 return GRN_ID_NIL;
963 }
964 if (!key || !key_size) { return GRN_ID_NIL; }
965 if (key_size > GRN_TABLE_MAX_KEY_SIZE) {
966 ERR(GRN_INVALID_ARGUMENT, "too long key: (%u)", key_size);
967 return GRN_ID_NIL;
968 }
969 KEY_ENCODE(pat, keybuf, key, key_size);
970 r0 = _grn_pat_add(ctx, pat, (uint8_t *)key, key_size, &new, &lkey);
971 if (r0 == GRN_ID_NIL) { return GRN_ID_NIL; }
972 if (added) { *added = new; }
973 if (r0 && (pat->obj.header.flags & GRN_OBJ_KEY_WITH_SIS) &&
974 (*((uint8_t *)key) & 0x80)) { // todo: refine!!
975 sis_node *sl, *sr;
976 grn_id l = r0, r;
977 if (new && (sl = sis_get(ctx, pat, l))) {
978 const char *sis = key, *end = sis + key_size;
979 sl->children = l;
980 sl->sibling = 0;
981 while (chop(ctx, pat, &sis, end, &lkey)) {
982 if (!(*sis & 0x80)) { break; }
983 if (!(r = _grn_pat_add(ctx, pat, (uint8_t *)sis, end - sis, &new, &lkey))) {
984 break;
985 }
986 if (!(sr = sis_get(ctx, pat, r))) { break; }
987 if (new) {
988 sl->sibling = r;
989 sr->children = l;
990 sr->sibling = 0;
991 } else {
992 sl->sibling = sr->children;
993 sr->children = l;
994 break;
995 }
996 l = r;
997 sl = sr;
998 }
999 }
1000 }
1001 if (r0 && value) {
1002 byte *v = (byte *)sis_get(ctx, pat, r0);
1003 if (pat->obj.header.flags & GRN_OBJ_KEY_WITH_SIS) {
1004 *value = v + sizeof(sis_node);
1005 } else {
1006 *value = v;
1007 }
1008 }
1009 return r0;
1010}
1011
1012inline static grn_id
1013_grn_pat_get(grn_ctx *ctx, grn_pat *pat, const void *key, uint32_t key_size, void **value)
1014{
1015 grn_id r;
1016 pat_node *rn;
1017 int c0 = -1, c;
1018 uint32_t len = key_size * 16;
1019 PAT_AT(pat, 0, rn);
1020 for (r = rn->lr[1]; r;) {
1021 PAT_AT(pat, r, rn);
1022 if (!rn) { break; /* corrupt? */ }
1023 c = PAT_CHK(rn);
1024 if (len <= c) { break; }
1025 if (c <= c0) {
1026 const uint8_t *k = pat_node_get_key(ctx, pat, rn);
1027 if (k && key_size == PAT_LEN(rn) && !memcmp(k, key, key_size)) {
1028 if (value) {
1029 byte *v = (byte *)sis_get(ctx, pat, r);
1030 if (pat->obj.header.flags & GRN_OBJ_KEY_WITH_SIS) {
1031 *value = v + sizeof(sis_node);
1032 } else {
1033 *value = v;
1034 }
1035 }
1036 return r;
1037 }
1038 break;
1039 }
1040 if (c & 1) {
1041 r = (c + 1 < len) ? rn->lr[1] : rn->lr[0];
1042 } else {
1043 r = rn->lr[nth_bit((uint8_t *)key, c, len)];
1044 }
1045 c0 = c;
1046 }
1047 return GRN_ID_NIL;
1048}
1049
1050grn_id
1051grn_pat_get(grn_ctx *ctx, grn_pat *pat, const void *key, uint32_t key_size, void **value)
1052{
1053 uint8_t keybuf[MAX_FIXED_KEY_SIZE];
1054 if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
1055 return GRN_ID_NIL;
1056 }
1057 KEY_ENCODE(pat, keybuf, key, key_size);
1058 return _grn_pat_get(ctx, pat, key, key_size, value);
1059}
1060
1061grn_id
1062grn_pat_nextid(grn_ctx *ctx, grn_pat *pat, const void *key, uint32_t key_size)
1063{
1064 grn_id r = GRN_ID_NIL;
1065 if (pat && key) {
1066 if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
1067 return GRN_ID_NIL;
1068 }
1069 if (!(r = pat->header->garbages[key_size > sizeof(uint32_t) ? key_size : 0])) {
1070 r = pat->header->curr_rec + 1;
1071 }
1072 }
1073 return r;
1074}
1075
1076static void
1077get_tc(grn_ctx *ctx, grn_pat *pat, grn_hash *h, pat_node *rn)
1078{
1079 grn_id id;
1080 pat_node *node;
1081 id = rn->lr[1];
1082 if (id) {
1083 PAT_AT(pat, id, node);
1084 if (node) {
1085 if (PAT_CHK(node) > PAT_CHK(rn)) {
1086 get_tc(ctx, pat, h, node);
1087 } else {
1088 grn_hash_add(ctx, h, &id, sizeof(grn_id), NULL, NULL);
1089 }
1090 }
1091 }
1092 id = rn->lr[0];
1093 if (id) {
1094 PAT_AT(pat, id, node);
1095 if (node) {
1096 if (PAT_CHK(node) > PAT_CHK(rn)) {
1097 get_tc(ctx, pat, h, node);
1098 } else {
1099 grn_hash_add(ctx, h, &id, sizeof(grn_id), NULL, NULL);
1100 }
1101 }
1102 }
1103}
1104
1105grn_rc
1106grn_pat_prefix_search(grn_ctx *ctx, grn_pat *pat,
1107 const void *key, uint32_t key_size, grn_hash *h)
1108{
1109 int c0 = -1, c;
1110 const uint8_t *k;
1111 uint32_t len = key_size * 16;
1112 grn_id r;
1113 pat_node *rn;
1114 uint8_t keybuf[MAX_FIXED_KEY_SIZE];
1115 grn_rc rc = grn_pat_error_if_truncated(ctx, pat);
1116 if (rc != GRN_SUCCESS) {
1117 return rc;
1118 }
1119 KEY_ENCODE(pat, keybuf, key, key_size);
1120 PAT_AT(pat, 0, rn);
1121 r = rn->lr[1];
1122 while (r) {
1123 PAT_AT(pat, r, rn);
1124 if (!rn) { return GRN_FILE_CORRUPT; }
1125 c = PAT_CHK(rn);
1126 if (c0 < c && c < len - 1) {
1127 if (c & 1) {
1128 r = (c + 1 < len) ? rn->lr[1] : rn->lr[0];
1129 } else {
1130 r = rn->lr[nth_bit((uint8_t *)key, c, len)];
1131 }
1132 c0 = c;
1133 continue;
1134 }
1135 if (!(k = pat_node_get_key(ctx, pat, rn))) { break; }
1136 if (PAT_LEN(rn) < key_size) { break; }
1137 if (!memcmp(k, key, key_size)) {
1138 if (c >= len - 1) {
1139 get_tc(ctx, pat, h, rn);
1140 } else {
1141 grn_hash_add(ctx, h, &r, sizeof(grn_id), NULL, NULL);
1142 }
1143 return GRN_SUCCESS;
1144 }
1145 break;
1146 }
1147 return GRN_END_OF_DATA;
1148}
1149
1150grn_hash *
1151grn_pat_prefix_search2(grn_ctx *ctx, grn_pat *pat, const void *key, uint32_t key_size)
1152{
1153 grn_hash *h;
1154 if (!pat || !key) { return NULL; }
1155 if ((h = grn_hash_create(ctx, NULL, sizeof(grn_id), 0, 0))) {
1156 if (grn_pat_prefix_search(ctx, pat, key, key_size, h)) {
1157 grn_hash_close(ctx, h);
1158 h = NULL;
1159 }
1160 }
1161 return h;
1162}
1163
1164grn_rc
1165grn_pat_suffix_search(grn_ctx *ctx, grn_pat *pat,
1166 const void *key, uint32_t key_size, grn_hash *h)
1167{
1168 grn_id r;
1169 if ((r = grn_pat_get(ctx, pat, key, key_size, NULL))) {
1170 uint32_t *offset;
1171 if (grn_hash_add(ctx, h, &r, sizeof(grn_id), (void **) &offset, NULL)) {
1172 *offset = 0;
1173 if (pat->obj.header.flags & GRN_OBJ_KEY_WITH_SIS) { sis_collect(ctx, pat, h, r, 1); }
1174 return GRN_SUCCESS;
1175 }
1176 }
1177 return GRN_END_OF_DATA;
1178}
1179
1180grn_hash *
1181grn_pat_suffix_search2(grn_ctx *ctx, grn_pat *pat, const void *key, uint32_t key_size)
1182{
1183 grn_hash *h;
1184 if (!pat || !key) { return NULL; }
1185 if ((h = grn_hash_create(ctx, NULL, sizeof(grn_id), sizeof(uint32_t), 0))) {
1186 if (grn_pat_suffix_search(ctx, pat, key, key_size, h)) {
1187 grn_hash_close(ctx, h);
1188 h = NULL;
1189 }
1190 }
1191 return h;
1192}
1193
1194grn_id
1195grn_pat_lcp_search(grn_ctx *ctx, grn_pat *pat, const void *key, uint32_t key_size)
1196{
1197 pat_node *rn;
1198 grn_id r, r2 = GRN_ID_NIL;
1199 uint32_t len = key_size * 16;
1200 int c0 = -1, c;
1201 if (!pat || !key) {
1202 return GRN_ID_NIL;
1203 }
1204 if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
1205 return GRN_ID_NIL;
1206 }
1207 if (!(pat->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE)) { return GRN_ID_NIL; }
1208 PAT_AT(pat, 0, rn);
1209 for (r = rn->lr[1]; r;) {
1210 PAT_AT(pat, r, rn);
1211 if (!rn) { break; /* corrupt? */ }
1212 c = PAT_CHK(rn);
1213 if (c <= c0) {
1214 if (PAT_LEN(rn) <= key_size) {
1215 uint8_t *p = pat_node_get_key(ctx, pat, rn);
1216 if (!p) { break; }
1217 if (!memcmp(p, key, PAT_LEN(rn))) { return r; }
1218 }
1219 break;
1220 }
1221 if (len <= c) { break; }
1222 if (c & 1) {
1223 uint8_t *p;
1224 pat_node *rn0;
1225 grn_id r0 = rn->lr[0];
1226 PAT_AT(pat, r0, rn0);
1227 if (!rn0) { break; /* corrupt? */ }
1228 p = pat_node_get_key(ctx, pat, rn0);
1229 if (!p) { break; }
1230 if (PAT_LEN(rn0) <= key_size && !memcmp(p, key, PAT_LEN(rn0))) { r2 = r0; }
1231 r = (c + 1 < len) ? rn->lr[1] : rn->lr[0];
1232 } else {
1233 r = rn->lr[nth_bit((uint8_t *)key, c, len)];
1234 }
1235 c0 = c;
1236 }
1237 return r2;
1238}
1239
1240static grn_id
1241common_prefix_pat_node_get(grn_ctx *ctx, grn_pat *pat, const void *key, uint32_t key_size)
1242{
1243 int c0 = -1, c;
1244 const uint8_t *k;
1245 uint32_t len = key_size * 16;
1246 grn_id r;
1247 pat_node *rn;
1248 uint8_t keybuf[MAX_FIXED_KEY_SIZE];
1249
1250 KEY_ENCODE(pat, keybuf, key, key_size);
1251 PAT_AT(pat, 0, rn);
1252 r = rn->lr[1];
1253 while (r) {
1254 PAT_AT(pat, r, rn);
1255 if (!rn) { return GRN_ID_NIL; }
1256 c = PAT_CHK(rn);
1257 if (c0 < c && c < len - 1) {
1258 if (c & 1) {
1259 r = (c + 1 < len) ? rn->lr[1] : rn->lr[0];
1260 } else {
1261 r = rn->lr[nth_bit((uint8_t *)key, c, len)];
1262 }
1263 c0 = c;
1264 continue;
1265 }
1266 if (!(k = pat_node_get_key(ctx, pat, rn))) { break; }
1267 if (PAT_LEN(rn) < key_size) { break; }
1268 if (!memcmp(k, key, key_size)) {
1269 return r;
1270 }
1271 break;
1272 }
1273 return GRN_ID_NIL;
1274}
1275
1276typedef struct {
1277 grn_id id;
1278 uint16_t distance;
1279} fuzzy_heap_node;
1280
1281typedef struct {
1282 int n_entries;
1283 int limit;
1284 fuzzy_heap_node *nodes;
1285} fuzzy_heap;
1286
1287static inline fuzzy_heap *
1288fuzzy_heap_open(grn_ctx *ctx, int max)
1289{
1290 fuzzy_heap *h = GRN_MALLOC(sizeof(fuzzy_heap));
1291 if (!h) { return NULL; }
1292 h->nodes = GRN_MALLOC(sizeof(fuzzy_heap_node) * max);
1293 if (!h->nodes) {
1294 GRN_FREE(h);
1295 return NULL;
1296 }
1297 h->n_entries = 0;
1298 h->limit = max;
1299 return h;
1300}
1301
1302static inline grn_bool
1303fuzzy_heap_push(grn_ctx *ctx, fuzzy_heap *h, grn_id id, uint16_t distance)
1304{
1305 int n, n2;
1306 fuzzy_heap_node node = {id, distance};
1307 fuzzy_heap_node node2;
1308 if (h->n_entries >= h->limit) {
1309 int max = h->limit * 2;
1310 fuzzy_heap_node *nodes = GRN_REALLOC(h->nodes, sizeof(fuzzy_heap) * max);
1311 if (!h) {
1312 return GRN_FALSE;
1313 }
1314 h->limit = max;
1315 h->nodes = nodes;
1316 }
1317 h->nodes[h->n_entries] = node;
1318 n = h->n_entries++;
1319 while (n) {
1320 n2 = (n - 1) >> 1;
1321 if (h->nodes[n2].distance <= h->nodes[n].distance) { break; }
1322 node2 = h->nodes[n];
1323 h->nodes[n] = h->nodes[n2];
1324 h->nodes[n2] = node2;
1325 n = n2;
1326 }
1327 return GRN_TRUE;
1328}
1329
1330static inline void
1331fuzzy_heap_close(grn_ctx *ctx, fuzzy_heap *h)
1332{
1333 GRN_FREE(h->nodes);
1334 GRN_FREE(h);
1335}
1336
1337#define DIST(ox,oy) (dists[((lx + 1) * (oy)) + (ox)])
1338
1339inline static uint16_t
1340calc_edit_distance_by_offset(grn_ctx *ctx,
1341 const char *sx, const char *ex,
1342 const char *sy, const char *ey,
1343 uint16_t *dists, uint32_t lx,
1344 uint32_t offset, uint32_t max_distance,
1345 grn_bool *can_transition, int flags)
1346{
1347 uint32_t cx, cy, x, y;
1348 const char *px, *py;
1349
1350 /* Skip already calculated rows */
1351 for (py = sy, y = 1; py < ey && (cy = grn_charlen(ctx, py, ey)); py += cy, y++) {
1352 if (py - sy >= offset) {
1353 break;
1354 }
1355 }
1356 for (; py < ey && (cy = grn_charlen(ctx, py, ey)); py += cy, y++) {
1357 /* children nodes will be no longer smaller than max distance
1358 * with only insertion costs.
1359 * This is end of row on allocated memory. */
1360 if (y > lx + max_distance) {
1361 *can_transition = GRN_FALSE;
1362 return max_distance + 1;
1363 }
1364
1365 for (px = sx, x = 1; px < ex && (cx = grn_charlen(ctx, px, ex)); px += cx, x++) {
1366 if (cx == cy && !memcmp(px, py, cx)) {
1367 DIST(x, y) = DIST(x - 1, y - 1);
1368 } else {
1369 uint32_t a, b, c;
1370 a = DIST(x - 1, y) + 1;
1371 b = DIST(x, y - 1) + 1;
1372 c = DIST(x - 1, y - 1) + 1;
1373 DIST(x, y) = ((a < b) ? ((a < c) ? a : c) : ((b < c) ? b : c));
1374 if (flags & GRN_TABLE_FUZZY_SEARCH_WITH_TRANSPOSITION &&
1375 x > 1 && y > 1 &&
1376 cx == cy &&
1377 memcmp(px, py - cy, cx) == 0 &&
1378 memcmp(px - cx, py, cx) == 0) {
1379 uint32_t t = DIST(x - 2, y - 2) + 1;
1380 DIST(x, y) = ((DIST(x, y) < t) ? DIST(x, y) : t);
1381 }
1382 }
1383 }
1384 }
1385 if (lx) {
1386 /* If there is no cell which is smaller than equal to max distance on end of row,
1387 * children nodes will be no longer smaller than max distance */
1388 *can_transition = GRN_FALSE;
1389 for (x = 1; x <= lx; x++) {
1390 if (DIST(x, y - 1) <= max_distance) {
1391 *can_transition = GRN_TRUE;
1392 break;
1393 }
1394 }
1395 }
1396 return DIST(lx, y - 1);
1397}
1398
1399typedef struct {
1400 const char *key;
1401 int key_length;
1402 grn_bool can_transition;
1403} fuzzy_node;
1404
1405inline static void
1406_grn_pat_fuzzy_search(grn_ctx *ctx, grn_pat *pat, grn_id id,
1407 const char *key, uint32_t key_size,
1408 uint16_t *dists, uint32_t lx,
1409 int last_check, fuzzy_node *last_node,
1410 uint32_t max_distance, int flags, fuzzy_heap *heap)
1411{
1412 pat_node *node = NULL;
1413 int check, len;
1414 const char *k;
1415 uint32_t offset = 0;
1416
1417 PAT_AT(pat, id, node);
1418 if (!node) {
1419 return;
1420 }
1421 check = PAT_CHK(node);
1422 len = PAT_LEN(node);
1423 k = pat_node_get_key(ctx, pat, node);
1424
1425 if (check > last_check) {
1426 if (len >= last_node->key_length &&
1427 !memcmp(k, last_node->key, last_node->key_length)) {
1428 if (last_node->can_transition == GRN_FALSE) {
1429 return;
1430 }
1431 }
1432 _grn_pat_fuzzy_search(ctx, pat, node->lr[0],
1433 key, key_size, dists, lx,
1434 check, last_node,
1435 max_distance, flags, heap);
1436
1437 _grn_pat_fuzzy_search(ctx, pat, node->lr[1],
1438 key, key_size, dists, lx,
1439 check, last_node,
1440 max_distance, flags, heap);
1441 } else {
1442 if (id) {
1443 /* Set already calculated common prefix length */
1444 if (len >= last_node->key_length &&
1445 !memcmp(k, last_node->key, last_node->key_length)) {
1446 if (last_node->can_transition == GRN_FALSE) {
1447 return;
1448 }
1449 offset = last_node->key_length;
1450 } else {
1451 if (last_node->can_transition == GRN_FALSE) {
1452 last_node->can_transition = GRN_TRUE;
1453 }
1454 if (last_node->key_length) {
1455 const char *kp = k;
1456 const char *ke = k + len;
1457 const char *p = last_node->key;
1458 const char *e = last_node->key + last_node->key_length;
1459 int lp;
1460 for (;p < e && kp < ke && (lp = grn_charlen(ctx, p, e));
1461 p += lp, kp += lp) {
1462 if (p + lp <= e && kp + lp <= ke && memcmp(p, kp, lp)) {
1463 break;
1464 }
1465 }
1466 offset = kp - k;
1467 }
1468 }
1469 if (len - offset) {
1470 uint16_t distance;
1471 distance =
1472 calc_edit_distance_by_offset(ctx,
1473 key, key + key_size,
1474 k, k + len,
1475 dists, lx,
1476 offset, max_distance,
1477 &(last_node->can_transition), flags);
1478 if (distance <= max_distance) {
1479 fuzzy_heap_push(ctx, heap, id, distance);
1480 }
1481 }
1482 last_node->key = k;
1483 last_node->key_length = len;
1484 }
1485 }
1486 return;
1487}
1488
1489#define HEAP_SIZE 256
1490
1491grn_rc
1492grn_pat_fuzzy_search(grn_ctx *ctx, grn_pat *pat,
1493 const void *key, uint32_t key_size,
1494 grn_fuzzy_search_optarg *args, grn_hash *h)
1495{
1496 pat_node *node;
1497 grn_id id;
1498 uint16_t *dists;
1499 uint32_t lx, len, x, y, i;
1500 const char *s = key;
1501 const char *e = (const char *)key + key_size;
1502 fuzzy_node last_node;
1503 fuzzy_heap *heap;
1504 uint32_t max_distance = 1;
1505 uint32_t max_expansion = 0;
1506 uint32_t prefix_match_size = 0;
1507 int flags = 0;
1508 grn_rc rc = grn_pat_error_if_truncated(ctx, pat);
1509 if (rc != GRN_SUCCESS) {
1510 return rc;
1511 }
1512 if (args) {
1513 max_distance = args->max_distance;
1514 max_expansion = args->max_expansion;
1515 prefix_match_size = args->prefix_match_size;
1516 flags = args->flags;
1517 }
1518 if (key_size > GRN_TABLE_MAX_KEY_SIZE ||
1519 max_distance > GRN_TABLE_MAX_KEY_SIZE ||
1520 prefix_match_size > key_size) {
1521 return GRN_INVALID_ARGUMENT;
1522 }
1523
1524 heap = fuzzy_heap_open(ctx, HEAP_SIZE);
1525 if (!heap) {
1526 return GRN_NO_MEMORY_AVAILABLE;
1527 }
1528
1529 PAT_AT(pat, GRN_ID_NIL, node);
1530 id = node->lr[1];
1531
1532 if (prefix_match_size) {
1533 grn_id tid;
1534 tid = common_prefix_pat_node_get(ctx, pat, key, prefix_match_size);
1535 if (tid != GRN_ID_NIL) {
1536 id = tid;
1537 } else {
1538 return GRN_END_OF_DATA;
1539 }
1540 }
1541 for (lx = 0; s < e && (len = grn_charlen(ctx, s, e)); s += len) {
1542 lx++;
1543 }
1544 dists = GRN_MALLOC((lx + 1) * (lx + max_distance + 1) * sizeof(uint16_t));
1545 if (!dists) {
1546 return GRN_NO_MEMORY_AVAILABLE;
1547 }
1548
1549 for (x = 0; x <= lx; x++) { DIST(x, 0) = x; }
1550 for (y = 0; y <= lx + max_distance ; y++) { DIST(0, y) = y; }
1551
1552 last_node.key = NULL;
1553 last_node.key_length = 0;
1554 last_node.can_transition = GRN_TRUE;
1555 _grn_pat_fuzzy_search(ctx, pat, id,
1556 key, key_size, dists, lx,
1557 -1, &last_node, max_distance, flags, heap);
1558 GRN_FREE(dists);
1559 for (i = 0; i < heap->n_entries; i++) {
1560 if (max_expansion > 0 && i >= max_expansion) {
1561 break;
1562 }
1563 if (DB_OBJ(h)->header.flags & GRN_OBJ_WITH_SUBREC) {
1564 grn_rset_recinfo *ri;
1565 if (grn_hash_add(ctx, h, &(heap->nodes[i].id), sizeof(grn_id), (void **)&ri, NULL)) {
1566 ri->score = max_distance - heap->nodes[i].distance + 1;
1567 }
1568 } else {
1569 grn_hash_add(ctx, h, &(heap->nodes[i].id), sizeof(grn_id), NULL, NULL);
1570 }
1571 }
1572 fuzzy_heap_close(ctx, heap);
1573 if (grn_hash_size(ctx, h)) {
1574 return GRN_SUCCESS;
1575 } else {
1576 return GRN_END_OF_DATA;
1577 }
1578}
1579
1580inline static grn_rc
1581_grn_pat_del(grn_ctx *ctx, grn_pat *pat, const char *key, uint32_t key_size, int shared,
1582 grn_table_delete_optarg *optarg)
1583{
1584 grn_pat_delinfo *di;
1585 pat_node *rn, *rn0 = NULL, *rno = NULL;
1586 int c = -1, c0 = -1, ch;
1587 uint32_t len = key_size * 16;
1588 grn_id r, otherside, *proot, *p, *p0 = NULL;
1589
1590 /* delinfo_new() must be called before searching for rn. */
1591 di = delinfo_new(ctx, pat);
1592 di->shared = shared;
1593
1594 /*
1595 * Search a patricia tree for a given key.
1596 * If the key exists, get its output node.
1597 *
1598 * rn, rn0: the output node and its previous node.
1599 * rno: the other side of rn (the other destination of rn0).
1600 * c, c0: checks of rn0 and its previous node.
1601 * p, p0: pointers to transitions (IDs) that refer to rn and rn0.
1602 */
1603 PAT_AT(pat, 0, rn);
1604 proot = p = &rn->lr[1];
1605 for (;;) {
1606 r = *p;
1607 if (!r) {
1608 return GRN_INVALID_ARGUMENT;
1609 }
1610 PAT_AT(pat, r, rn);
1611 if (!rn) {
1612 return GRN_FILE_CORRUPT;
1613 }
1614 ch = PAT_CHK(rn);
1615 if (len <= ch) {
1616 return GRN_INVALID_ARGUMENT;
1617 }
1618 if (c >= ch) {
1619 /* Output node found. */
1620 const uint8_t *k = pat_node_get_key(ctx, pat, rn);
1621 if (!k) {
1622 return GRN_INVALID_ARGUMENT;
1623 }
1624 if (key_size != PAT_LEN(rn) || memcmp(k, key, key_size)) {
1625 return GRN_INVALID_ARGUMENT;
1626 }
1627 /* Given key found. */
1628 break;
1629 }
1630 c0 = c;
1631 p0 = p;
1632 c = ch;
1633 if (c & 1) {
1634 p = (c + 1 < len) ? &rn->lr[1] : &rn->lr[0];
1635 } else {
1636 p = &rn->lr[nth_bit((uint8_t *)key, c, len)];
1637 }
1638 rn0 = rn;
1639 }
1640 if (optarg && optarg->func &&
1641 !optarg->func(ctx, (grn_obj *)pat, r, optarg->func_arg)) {
1642 return GRN_SUCCESS;
1643 }
1644 if (rn0->lr[0] == rn0->lr[1]) {
1645 GRN_LOG(ctx, GRN_LOG_DEBUG, "*p0 (%d), rn0->lr[0] == rn0->lr[1] (%d)",
1646 *p0, rn0->lr[0]);
1647 return GRN_FILE_CORRUPT;
1648 }
1649 otherside = (rn0->lr[1] == r) ? rn0->lr[0] : rn0->lr[1];
1650 if (otherside) {
1651 PAT_AT(pat, otherside, rno);
1652 if (!rno) {
1653 return GRN_FILE_CORRUPT;
1654 }
1655 }
1656
1657 if (rn == rn0) {
1658 /* The last transition (p) is a self-loop. */
1659 di->stat = DL_PHASE2;
1660 di->d = r;
1661 if (otherside) {
1662 if (c0 < PAT_CHK(rno) && PAT_CHK(rno) <= c) {
1663 /* To keep rno as an output node, its check is set to zero. */
1664 if (!delinfo_search(pat, otherside)) {
1665 GRN_LOG(ctx, GRN_LOG_DEBUG, "no delinfo found %d", otherside);
1666 }
1667 PAT_CHK_SET(rno, 0);
1668 }
1669 if (proot == p0 && !rno->check) {
1670 /*
1671 * Update rno->lr because the first node, rno becomes the new first
1672 * node, is not an output node even if its check is zero.
1673 */
1674 const uint8_t *k = pat_node_get_key(ctx, pat, rno);
1675 int direction = k ? (*k >> 7) : 1;
1676 rno->lr[direction] = otherside;
1677 rno->lr[!direction] = 0;
1678 }
1679 }
1680 *p0 = otherside;
1681 } else if ((!rn->lr[0] && rn->lr[1] == r) ||
1682 (!rn->lr[1] && rn->lr[0] == r)) {
1683 /* The output node has only a disabled self-loop. */
1684 di->stat = DL_PHASE2;
1685 di->d = r;
1686 *p = 0;
1687 } else {
1688 /* The last transition (p) is not a self-loop. */
1689 grn_pat_delinfo *ldi = NULL, *ddi = NULL;
1690 if (PAT_DEL(rn)) {
1691 ldi = delinfo_search(pat, r);
1692 }
1693 if (PAT_DEL(rn0)) {
1694 ddi = delinfo_search(pat, *p0);
1695 }
1696 if (ldi) {
1697 PAT_DEL_OFF(rn);
1698 di->stat = DL_PHASE2;
1699 if (ddi) {
1700 PAT_DEL_OFF(rn0);
1701 ddi->stat = DL_PHASE2;
1702 if (ddi == ldi) {
1703 if (r != ddi->ld) {
1704 GRN_LOG(ctx, GRN_LOG_ERROR, "r(%d) != ddi->ld(%d)", r, ddi->ld);
1705 }
1706 di->d = r;
1707 } else {
1708 ldi->ld = ddi->ld;
1709 di->d = r;
1710 }
1711 } else {
1712 PAT_DEL_ON(rn0);
1713 ldi->ld = *p0;
1714 di->d = r;
1715 }
1716 } else {
1717 PAT_DEL_ON(rn);
1718 if (ddi) {
1719 if (ddi->d != *p0) {
1720 GRN_LOG(ctx, GRN_LOG_ERROR, "ddi->d(%d) != *p0(%d)", ddi->d, *p0);
1721 }
1722 PAT_DEL_OFF(rn0);
1723 ddi->stat = DL_PHASE2;
1724 di->stat = DL_PHASE1;
1725 di->ld = ddi->ld;
1726 di->d = r;
1727 /*
1728 PAT_DEL_OFF(rn0);
1729 ddi->d = r;
1730 di->stat = DL_PHASE2;
1731 di->d = *p0;
1732 */
1733 } else {
1734 PAT_DEL_ON(rn0);
1735 di->stat = DL_PHASE1;
1736 di->ld = *p0;
1737 di->d = r;
1738 // grn_log("pat_del d=%d ld=%d stat=%d", r, *p0, DL_PHASE1);
1739 }
1740 }
1741 if (*p0 == otherside) {
1742 /* The previous node (*p0) has a self-loop (rn0 == rno). */
1743 PAT_CHK_SET(rno, 0);
1744 if (proot == p0) {
1745 /*
1746 * Update rno->lr because the first node, rno becomes the new first
1747 * node, is not an output node even if its check is zero.
1748 */
1749 const uint8_t *k = pat_node_get_key(ctx, pat, rno);
1750 int direction = k ? (*k >> 7) : 1;
1751 rno->lr[direction] = otherside;
1752 rno->lr[!direction] = 0;
1753 }
1754 } else {
1755 if (otherside) {
1756 if (c0 < PAT_CHK(rno) && PAT_CHK(rno) <= c) {
1757 /* To keep rno as an output node, its check is set to zero. */
1758 if (!delinfo_search(pat, otherside)) {
1759 GRN_LOG(ctx, GRN_LOG_ERROR, "no delinfo found %d", otherside);
1760 }
1761 PAT_CHK_SET(rno, 0);
1762 }
1763 if (proot == p0 && !rno->check) {
1764 /*
1765 * Update rno->lr because the first node, rno becomes the new first
1766 * node, is not an output node even if its check is zero.
1767 */
1768 const uint8_t *k = pat_node_get_key(ctx, pat, rno);
1769 int direction = k ? (*k >> 7) : 1;
1770 rno->lr[direction] = otherside;
1771 rno->lr[!direction] = 0;
1772 }
1773 }
1774 *p0 = otherside;
1775 }
1776 }
1777 pat->header->n_entries--;
1778 pat->header->n_garbages++;
1779 return GRN_SUCCESS;
1780}
1781
1782static grn_rc
1783_grn_pat_delete(grn_ctx *ctx, grn_pat *pat, const void *key, uint32_t key_size,
1784 grn_table_delete_optarg *optarg)
1785{
1786 if (pat->obj.header.flags & GRN_OBJ_KEY_WITH_SIS) {
1787 grn_id id = grn_pat_get(ctx, pat, key, key_size, NULL);
1788 if (id && grn_pat_delete_with_sis(ctx, pat, id, optarg)) {
1789 return GRN_SUCCESS;
1790 }
1791 return GRN_INVALID_ARGUMENT;
1792 }
1793 return _grn_pat_del(ctx, pat, key, key_size, 0, optarg);
1794}
1795
1796grn_rc
1797grn_pat_delete(grn_ctx *ctx, grn_pat *pat, const void *key, uint32_t key_size,
1798 grn_table_delete_optarg *optarg)
1799{
1800 grn_rc rc;
1801 uint8_t keybuf[MAX_FIXED_KEY_SIZE];
1802 if (!pat || !key || !key_size) { return GRN_INVALID_ARGUMENT; }
1803 rc = grn_pat_error_if_truncated(ctx, pat);
1804 if (rc != GRN_SUCCESS) {
1805 return rc;
1806 }
1807 KEY_ENCODE(pat, keybuf, key, key_size);
1808 return _grn_pat_delete(ctx, pat, key, key_size, optarg);
1809}
1810
1811uint32_t
1812grn_pat_size(grn_ctx *ctx, grn_pat *pat)
1813{
1814 if (!pat) { return GRN_INVALID_ARGUMENT; }
1815 if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
1816 return 0;
1817 }
1818 return pat->header->n_entries;
1819}
1820
1821const char *
1822_grn_pat_key(grn_ctx *ctx, grn_pat *pat, grn_id id, uint32_t *key_size)
1823{
1824 pat_node *node;
1825 uint8_t *key;
1826 if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
1827 *key_size = 0;
1828 return NULL;
1829 }
1830 PAT_AT(pat, id, node);
1831 if (!node) {
1832 *key_size = 0;
1833 return NULL;
1834 }
1835 key = pat_node_get_key(ctx, pat, node);
1836 if (key) {
1837 *key_size = PAT_LEN(node);
1838 } else {
1839 *key_size = 0;
1840 }
1841 return (const char *)key;
1842}
1843
1844grn_rc
1845grn_pat_delete_by_id(grn_ctx *ctx, grn_pat *pat, grn_id id,
1846 grn_table_delete_optarg *optarg)
1847{
1848 grn_rc rc;
1849 if (!pat || !id) { return GRN_INVALID_ARGUMENT; }
1850 rc = grn_pat_error_if_truncated(ctx, pat);
1851 if (rc != GRN_SUCCESS) {
1852 return rc;
1853 }
1854 {
1855 uint32_t key_size;
1856 const char *key = _grn_pat_key(ctx, pat, id, &key_size);
1857 return _grn_pat_delete(ctx, pat, key, key_size, optarg);
1858 }
1859}
1860
1861int
1862grn_pat_get_key(grn_ctx *ctx, grn_pat *pat, grn_id id, void *keybuf, int bufsize)
1863{
1864 int len;
1865 uint8_t *key;
1866 pat_node *node;
1867 if (!pat) { return 0; }
1868 if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
1869 return 0;
1870 }
1871 if (!id) { return 0; }
1872 PAT_AT(pat, id, node);
1873 if (!node) { return 0; }
1874 if (!(key = pat_node_get_key(ctx, pat, node))) { return 0; }
1875 len = PAT_LEN(node);
1876 if (keybuf && bufsize >= len) {
1877 if (KEY_NEEDS_CONVERT(pat, len)) {
1878 KEY_DEC(pat, keybuf, key, len);
1879 } else {
1880 grn_memcpy(keybuf, key, len);
1881 }
1882 }
1883 return len;
1884}
1885
1886int
1887grn_pat_get_key2(grn_ctx *ctx, grn_pat *pat, grn_id id, grn_obj *bulk)
1888{
1889 uint32_t len;
1890 uint8_t *key;
1891 pat_node *node;
1892 if (!pat) { return GRN_INVALID_ARGUMENT; }
1893 if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
1894 return 0;
1895 }
1896 if (!id) { return 0; }
1897 PAT_AT(pat, id, node);
1898 if (!node) { return 0; }
1899 if (!(key = pat_node_get_key(ctx, pat, node))) { return 0; }
1900 len = PAT_LEN(node);
1901 if (KEY_NEEDS_CONVERT(pat, len)) {
1902 if (bulk->header.impl_flags & GRN_OBJ_REFER) {
1903 GRN_TEXT_INIT(bulk, 0);
1904 }
1905 if (!grn_bulk_reserve(ctx, bulk, len)) {
1906 char *curr = GRN_BULK_CURR(bulk);
1907 KEY_DEC(pat, curr, key, len);
1908 grn_bulk_truncate(ctx, bulk, GRN_BULK_VSIZE(bulk) + len);
1909 }
1910 } else {
1911 if (bulk->header.impl_flags & GRN_OBJ_REFER) {
1912 bulk->u.b.head = (char *)key;
1913 bulk->u.b.curr = (char *)key + len;
1914 } else {
1915 grn_bulk_write(ctx, bulk, (char *)key, len);
1916 }
1917 }
1918 return len;
1919}
1920
1921int
1922grn_pat_get_value(grn_ctx *ctx, grn_pat *pat, grn_id id, void *valuebuf)
1923{
1924 int value_size;
1925 if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
1926 return 0;
1927 }
1928 value_size = (int)pat->value_size;
1929 if (value_size) {
1930 byte *v = (byte *)sis_at(ctx, pat, id);
1931 if (v) {
1932 if (valuebuf) {
1933 if (pat->obj.header.flags & GRN_OBJ_KEY_WITH_SIS) {
1934 grn_memcpy(valuebuf, v + sizeof(sis_node), value_size);
1935 } else {
1936 grn_memcpy(valuebuf, v, value_size);
1937 }
1938 }
1939 return value_size;
1940 }
1941 }
1942 return 0;
1943}
1944
1945const char *
1946grn_pat_get_value_(grn_ctx *ctx, grn_pat *pat, grn_id id, uint32_t *size)
1947{
1948 const char *value = NULL;
1949 if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
1950 return NULL;
1951 }
1952 if ((*size = pat->value_size)) {
1953 if ((value = (const char *)sis_at(ctx, pat, id))
1954 && (pat->obj.header.flags & GRN_OBJ_KEY_WITH_SIS)) {
1955 value += sizeof(sis_node);
1956 }
1957 }
1958 return value;
1959}
1960
1961grn_rc
1962grn_pat_set_value(grn_ctx *ctx, grn_pat *pat, grn_id id,
1963 const void *value, int flags)
1964{
1965 grn_rc rc = grn_pat_error_if_truncated(ctx, pat);
1966 if (rc != GRN_SUCCESS) {
1967 return rc;
1968 }
1969 if (value) {
1970 uint32_t value_size = pat->value_size;
1971 if (value_size) {
1972 byte *v = (byte *)sis_get(ctx, pat, id);
1973 if (v) {
1974 if (pat->obj.header.flags & GRN_OBJ_KEY_WITH_SIS) { v += sizeof(sis_node); }
1975 switch ((flags & GRN_OBJ_SET_MASK)) {
1976 case GRN_OBJ_SET :
1977 grn_memcpy(v, value, value_size);
1978 return GRN_SUCCESS;
1979 case GRN_OBJ_INCR :
1980 switch (value_size) {
1981 case sizeof(int32_t) :
1982 *((int32_t *)v) += *((int32_t *)value);
1983 return GRN_SUCCESS;
1984 case sizeof(int64_t) :
1985 *((int64_t *)v) += *((int64_t *)value);
1986 return GRN_SUCCESS;
1987 default :
1988 return GRN_INVALID_ARGUMENT;
1989 }
1990 break;
1991 case GRN_OBJ_DECR :
1992 switch (value_size) {
1993 case sizeof(int32_t) :
1994 *((int32_t *)v) -= *((int32_t *)value);
1995 return GRN_SUCCESS;
1996 case sizeof(int64_t) :
1997 *((int64_t *)v) -= *((int64_t *)value);
1998 return GRN_SUCCESS;
1999 default :
2000 return GRN_INVALID_ARGUMENT;
2001 }
2002 break;
2003 default :
2004 // todo : support other types.
2005 return GRN_INVALID_ARGUMENT;
2006 }
2007 } else {
2008 return GRN_NO_MEMORY_AVAILABLE;
2009 }
2010 }
2011 }
2012 return GRN_INVALID_ARGUMENT;
2013}
2014
2015grn_rc
2016grn_pat_info(grn_ctx *ctx, grn_pat *pat, int *key_size, unsigned int *flags,
2017 grn_encoding *encoding, unsigned int *n_entries, unsigned int *file_size)
2018{
2019 grn_rc rc;
2020 ERRCLR(NULL);
2021 if (!pat) { return GRN_INVALID_ARGUMENT; }
2022 rc = grn_pat_error_if_truncated(ctx, pat);
2023 if (rc != GRN_SUCCESS) {
2024 return rc;
2025 }
2026 if (key_size) { *key_size = pat->key_size; }
2027 if (flags) { *flags = pat->obj.header.flags; }
2028 if (encoding) { *encoding = pat->encoding; }
2029 if (n_entries) { *n_entries = pat->header->n_entries; }
2030 if (file_size) {
2031 uint64_t tmp = 0;
2032 if ((rc = grn_io_size(ctx, pat->io, &tmp))) {
2033 return rc;
2034 }
2035 *file_size = (unsigned int) tmp; /* FIXME: inappropriate cast */
2036 }
2037 return GRN_SUCCESS;
2038}
2039
2040int
2041grn_pat_delete_with_sis(grn_ctx *ctx, grn_pat *pat, grn_id id,
2042 grn_table_delete_optarg *optarg)
2043{
2044 int level = 0, shared;
2045 const char *key = NULL, *_key;
2046 sis_node *sp, *ss = NULL, *si;
2047 if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
2048 return 0;
2049 }
2050 si = sis_at(ctx, pat, id);
2051 while (id) {
2052 pat_node *rn;
2053 uint32_t key_size;
2054 if ((si && si->children && si->children != id) ||
2055 (optarg && optarg->func &&
2056 !optarg->func(ctx, (grn_obj *)pat, id, optarg->func_arg))) {
2057 break;
2058 }
2059 PAT_AT(pat, id, rn);
2060 if (!(_key = (char *)pat_node_get_key(ctx, pat, rn))) { return 0; }
2061 if (_key == key) {
2062 shared = 1;
2063 } else {
2064 key = _key;
2065 shared = 0;
2066 }
2067 key_size = PAT_LEN(rn);
2068 if (key && key_size) { _grn_pat_del(ctx, pat, key, key_size, shared, NULL); }
2069 if (si) {
2070 grn_id *p, sid;
2071 uint32_t lkey = 0;
2072 if ((*key & 0x80) && chop(ctx, pat, &key, key + key_size, &lkey)) {
2073 if ((sid = grn_pat_get(ctx, pat, key, key_size - lkey, NULL)) &&
2074 (ss = sis_at(ctx, pat, sid))) {
2075 for (p = &ss->children; *p && *p != sid; p = &sp->sibling) {
2076 if (*p == id) {
2077 *p = si->sibling;
2078 break;
2079 }
2080 if (!(sp = sis_at(ctx, pat, *p))) { break; }
2081 }
2082 }
2083 } else {
2084 sid = GRN_ID_NIL;
2085 }
2086 si->sibling = 0;
2087 si->children = 0;
2088 id = sid;
2089 si = ss;
2090 } else {
2091 id = GRN_ID_NIL;
2092 }
2093 level++;
2094 }
2095 if (level) {
2096 uint32_t lkey = 0;
2097 while (id && key) {
2098 uint32_t key_size;
2099 if (_grn_pat_key(ctx, pat, id, &key_size) != key) { break; }
2100 {
2101 pat_node *rn;
2102 PAT_AT(pat, id, rn);
2103 if (!rn) { break; }
2104 if (lkey) {
2105 rn->key = lkey;
2106 } else {
2107 pat_node_set_key(ctx, pat, rn, (uint8_t *)key, key_size);
2108 lkey = rn->key;
2109 }
2110 }
2111 {
2112 const char *end = key + key_size;
2113 if (!((*key & 0x80) && chop(ctx, pat, &key, end, &lkey))) { break; }
2114 id = grn_pat_get(ctx, pat, key, end - key, NULL);
2115 }
2116 }
2117 }
2118 return level;
2119}
2120
2121grn_id
2122grn_pat_next(grn_ctx *ctx, grn_pat *pat, grn_id id)
2123{
2124 if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
2125 return GRN_ID_NIL;
2126 }
2127 while (++id <= pat->header->curr_rec) {
2128 uint32_t key_size;
2129 const char *key = _grn_pat_key(ctx, pat, id, &key_size);
2130 if (id == grn_pat_get(ctx, pat, key, key_size, NULL)) {
2131 return id;
2132 }
2133 }
2134 return GRN_ID_NIL;
2135}
2136
2137grn_id
2138grn_pat_at(grn_ctx *ctx, grn_pat *pat, grn_id id)
2139{
2140 uint32_t key_size;
2141 const char *key = _grn_pat_key(ctx, pat, id, &key_size);
2142 if (key && (id == _grn_pat_get(ctx, pat, key, key_size, NULL))) { return id; }
2143 return GRN_ID_NIL;
2144}
2145
2146grn_id
2147grn_pat_curr_id(grn_ctx *ctx, grn_pat *pat)
2148{
2149 if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
2150 return GRN_ID_NIL;
2151 }
2152 return pat->header->curr_rec;
2153}
2154
2155int
2156grn_pat_scan(grn_ctx *ctx, grn_pat *pat, const char *str, unsigned int str_len,
2157 grn_pat_scan_hit *sh, unsigned int sh_size, const char **rest)
2158{
2159 int n = 0;
2160 grn_id tid;
2161 if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
2162 return 0;
2163 }
2164 if (pat->normalizer) {
2165 int flags =
2166 GRN_STRING_REMOVE_BLANK |
2167 GRN_STRING_WITH_TYPES |
2168 GRN_STRING_WITH_CHECKS;
2169 grn_obj *nstr = grn_string_open(ctx, str, str_len,
2170 pat->normalizer, flags);
2171 if (nstr) {
2172 const short *cp = grn_string_get_checks(ctx, nstr);
2173 const unsigned char *tp = grn_string_get_types(ctx, nstr);
2174 unsigned int offset = 0, offset0 = 0;
2175 unsigned int normalized_length_in_bytes;
2176 const char *sp, *se;
2177 grn_string_get_normalized(ctx, nstr, &sp, &normalized_length_in_bytes,
2178 NULL);
2179 se = sp + normalized_length_in_bytes;
2180 while (n < sh_size) {
2181 if ((tid = grn_pat_lcp_search(ctx, pat, sp, se - sp))) {
2182 const char *key;
2183 uint32_t len;
2184 int first_key_char_len;
2185 key = _grn_pat_key(ctx, pat, tid, &len);
2186 sh[n].id = tid;
2187 sh[n].offset = (*cp > 0) ? offset : offset0;
2188 first_key_char_len = grn_charlen(ctx, key, key + len);
2189 if (sh[n].offset > 0 &&
2190 GRN_CHAR_IS_BLANK(tp[-1]) &&
2191 ((first_key_char_len == 1 && key[0] != ' ') ||
2192 first_key_char_len > 1)){
2193 /* Remove leading spaces. */
2194 const char *original_str = str + sh[n].offset;
2195 while (grn_charlen(ctx, original_str, str + str_len) == 1 &&
2196 original_str[0] == ' ') {
2197 original_str++;
2198 sh[n].offset++;
2199 }
2200 }
2201 {
2202 grn_bool blank_in_alnum = GRN_FALSE;
2203 const unsigned char *start_tp = tp;
2204 const unsigned char *blank_in_alnum_check_tp;
2205 while (len--) {
2206 if (*cp > 0) { offset0 = offset; offset += *cp; tp++; }
2207 sp++; cp++;
2208 }
2209 sh[n].length = offset - sh[n].offset;
2210 for (blank_in_alnum_check_tp = start_tp + 1;
2211 blank_in_alnum_check_tp < tp;
2212 blank_in_alnum_check_tp++) {
2213#define GRN_CHAR_IS_ALNUM(char_type) \
2214 (GRN_CHAR_TYPE(char_type) == GRN_CHAR_ALPHA || \
2215 GRN_CHAR_TYPE(char_type) == GRN_CHAR_DIGIT)
2216 if (GRN_CHAR_IS_BLANK(blank_in_alnum_check_tp[0]) &&
2217 GRN_CHAR_IS_ALNUM(blank_in_alnum_check_tp[-1]) &&
2218 (blank_in_alnum_check_tp + 1) < tp &&
2219 GRN_CHAR_IS_ALNUM(blank_in_alnum_check_tp[1])) {
2220 blank_in_alnum = GRN_TRUE;
2221 }
2222#undef GRN_CHAR_IS_ALNUM
2223 }
2224 if (!blank_in_alnum) {
2225 n++;
2226 }
2227 }
2228 } else {
2229 if (*cp > 0) { offset0 = offset; offset += *cp; tp++; }
2230 do {
2231 sp++; cp++;
2232 } while (sp < se && !*cp);
2233 }
2234 if (se <= sp) { offset = str_len; break; }
2235 }
2236 if (rest) {
2237 grn_string_get_original(ctx, nstr, rest, NULL);
2238 *rest += offset;
2239 }
2240 grn_obj_close(ctx, nstr);
2241 } else {
2242 n = -1;
2243 if (rest) { *rest = str; }
2244 }
2245 } else {
2246 uint32_t len;
2247 const char *sp, *se = str + str_len;
2248 for (sp = str; sp < se && n < sh_size; sp += len) {
2249 if ((tid = grn_pat_lcp_search(ctx, pat, sp, se - sp))) {
2250 _grn_pat_key(ctx, pat, tid, &len);
2251 sh[n].id = tid;
2252 sh[n].offset = sp - str;
2253 sh[n].length = len;
2254 n++;
2255 } else {
2256 len = grn_charlen(ctx, sp, se);
2257 }
2258 if (!len) { break; }
2259 }
2260 if (rest) { *rest = sp; }
2261 }
2262 return n;
2263}
2264
2265#define INITIAL_SIZE 512
2266
2267inline static void
2268push(grn_pat_cursor *c, grn_id id, uint16_t check)
2269{
2270 grn_ctx *ctx = c->ctx;
2271 grn_pat_cursor_entry *se;
2272 if (c->size <= c->sp) {
2273 if (c->ss) {
2274 uint32_t size = c->size * 4;
2275 grn_pat_cursor_entry *ss = GRN_REALLOC(c->ss, size);
2276 if (!ss) { return; /* give up */ }
2277 c->ss = ss;
2278 c->size = size;
2279 } else {
2280 if (!(c->ss = GRN_MALLOC(sizeof(grn_pat_cursor_entry) * INITIAL_SIZE))) {
2281 return; /* give up */
2282 }
2283 c->size = INITIAL_SIZE;
2284 }
2285 }
2286 se = &c->ss[c->sp++];
2287 se->id = id;
2288 se->check = check;
2289}
2290
2291inline static grn_pat_cursor_entry *
2292pop(grn_pat_cursor *c)
2293{
2294 return c->sp ? &c->ss[--c->sp] : NULL;
2295}
2296
2297static grn_id
2298grn_pat_cursor_next_by_id(grn_ctx *ctx, grn_pat_cursor *c)
2299{
2300 grn_pat *pat = c->pat;
2301 int dir = (c->obj.header.flags & GRN_CURSOR_DESCENDING) ? -1 : 1;
2302 while (c->curr_rec != c->tail) {
2303 c->curr_rec += dir;
2304 if (pat->header->n_garbages) {
2305 uint32_t key_size;
2306 const void *key = _grn_pat_key(ctx, pat, c->curr_rec, &key_size);
2307 if (_grn_pat_get(ctx, pat, key, key_size, NULL) != c->curr_rec) {
2308 continue;
2309 }
2310 }
2311 c->rest--;
2312 return c->curr_rec;
2313 }
2314 return GRN_ID_NIL;
2315}
2316
2317grn_id
2318grn_pat_cursor_next(grn_ctx *ctx, grn_pat_cursor *c)
2319{
2320 pat_node *node;
2321 grn_pat_cursor_entry *se;
2322 if (!c->rest) { return GRN_ID_NIL; }
2323 if ((c->obj.header.flags & GRN_CURSOR_BY_ID)) {
2324 return grn_pat_cursor_next_by_id(ctx, c);
2325 }
2326 while ((se = pop(c))) {
2327 grn_id id = se->id;
2328 int check = se->check, ch;
2329 while (id) {
2330 PAT_AT(c->pat, id, node);
2331 if (!node) {
2332 break;
2333 }
2334 ch = PAT_CHK(node);
2335 if (ch > check) {
2336 if (c->obj.header.flags & GRN_CURSOR_DESCENDING) {
2337 push(c, node->lr[0], ch);
2338 id = node->lr[1];
2339 } else {
2340 push(c, node->lr[1], ch);
2341 id = node->lr[0];
2342 }
2343 check = ch;
2344 continue;
2345 } else {
2346 if (id == c->tail) {
2347 c->sp = 0;
2348 } else {
2349 if (!c->curr_rec && c->tail) {
2350 uint32_t lmin, lmax;
2351 pat_node *nmin, *nmax;
2352 const uint8_t *kmin, *kmax;
2353 if (c->obj.header.flags & GRN_CURSOR_DESCENDING) {
2354 PAT_AT(c->pat, c->tail, nmin);
2355 PAT_AT(c->pat, id, nmax);
2356 } else {
2357 PAT_AT(c->pat, id, nmin);
2358 PAT_AT(c->pat, c->tail, nmax);
2359 }
2360 lmin = PAT_LEN(nmin);
2361 lmax = PAT_LEN(nmax);
2362 kmin = pat_node_get_key(ctx, c->pat, nmin);
2363 kmax = pat_node_get_key(ctx, c->pat, nmax);
2364 if ((lmin < lmax) ?
2365 (memcmp(kmin, kmax, lmin) > 0) :
2366 (memcmp(kmin, kmax, lmax) >= 0)) {
2367 c->sp = 0;
2368 break;
2369 }
2370 }
2371 }
2372 c->curr_rec = id;
2373 c->rest--;
2374 return id;
2375 }
2376 }
2377 }
2378 return GRN_ID_NIL;
2379}
2380
2381void
2382grn_pat_cursor_close(grn_ctx *ctx, grn_pat_cursor *c)
2383{
2384 GRN_ASSERT(c->ctx == ctx);
2385 if (c->ss) { GRN_FREE(c->ss); }
2386 GRN_FREE(c);
2387}
2388
2389inline static int
2390bitcmp(const void *s1, const void *s2, int offset, int length)
2391{
2392 int r, rest = length + (offset & 7) - 8, bl = offset >> 3, mask = 0xff >> (offset & 7);
2393 unsigned char *a = (unsigned char *)s1 + bl, *b = (unsigned char *)s2 + bl;
2394 if (rest <= 0) {
2395 mask &= 0xff << -rest;
2396 return (*a & mask) - (*b & mask);
2397 }
2398 if ((r = (*a & mask) - (*b & mask))) { return r; }
2399 a++; b++;
2400 if ((bl = rest >> 3)) {
2401 if ((r = memcmp(a, b, bl))) { return r; }
2402 a += bl; b += bl;
2403 }
2404 mask = 0xff << (8 - (rest & 7));
2405 return (*a & mask) - (*b & mask);
2406}
2407
2408inline static grn_rc
2409set_cursor_prefix(grn_ctx *ctx, grn_pat *pat, grn_pat_cursor *c,
2410 const void *key, uint32_t key_size, int flags)
2411{
2412 int c0 = -1, ch;
2413 const uint8_t *k;
2414 uint32_t len, byte_len;
2415 grn_id id;
2416 pat_node *node;
2417 uint8_t keybuf[MAX_FIXED_KEY_SIZE];
2418 if (flags & GRN_CURSOR_SIZE_BY_BIT) {
2419 len = key_size * 2;
2420 byte_len = key_size >> 3;
2421 } else {
2422 len = key_size * 16;
2423 byte_len = key_size;
2424 }
2425 KEY_ENCODE(pat, keybuf, key, byte_len);
2426 PAT_AT(pat, 0, node);
2427 id = node->lr[1];
2428 while (id) {
2429 PAT_AT(pat, id, node);
2430 if (!node) { return GRN_FILE_CORRUPT; }
2431 ch = PAT_CHK(node);
2432 if (c0 < ch && ch < len - 1) {
2433 if (ch & 1) {
2434 id = (ch + 1 < len) ? node->lr[1] : node->lr[0];
2435 } else {
2436 id = node->lr[nth_bit((uint8_t *)key, ch, len)];
2437 }
2438 c0 = ch;
2439 continue;
2440 }
2441 if (!(k = pat_node_get_key(ctx, pat, node))) { break; }
2442 if (PAT_LEN(node) < byte_len) { break; }
2443 if ((flags & GRN_CURSOR_SIZE_BY_BIT)
2444 ? !bitcmp(k, key, 0, key_size)
2445 : !memcmp(k, key, key_size)) {
2446 if (c0 < ch) {
2447 if (flags & GRN_CURSOR_DESCENDING) {
2448 if ((ch > len - 1) || !(flags & GRN_CURSOR_GT)) {
2449 push(c, node->lr[0], ch);
2450 }
2451 push(c, node->lr[1], ch);
2452 } else {
2453 push(c, node->lr[1], ch);
2454 if ((ch > len - 1) || !(flags & GRN_CURSOR_GT)) {
2455 push(c, node->lr[0], ch);
2456 }
2457 }
2458 } else {
2459 if (PAT_LEN(node) * 16 > len || !(flags & GRN_CURSOR_GT)) {
2460 push(c, id, ch);
2461 }
2462 }
2463 }
2464 break;
2465 }
2466 return GRN_SUCCESS;
2467}
2468
2469inline static grn_rc
2470set_cursor_near(grn_ctx *ctx, grn_pat *pat, grn_pat_cursor *c,
2471 uint32_t min_size, const void *key, int flags)
2472{
2473 grn_id id;
2474 pat_node *node;
2475 const uint8_t *k;
2476 int r, check = -1, ch;
2477 uint32_t min = min_size * 16;
2478 uint8_t keybuf[MAX_FIXED_KEY_SIZE];
2479 KEY_ENCODE(pat, keybuf, key, pat->key_size);
2480 PAT_AT(pat, 0, node);
2481 for (id = node->lr[1]; id;) {
2482 PAT_AT(pat, id, node);
2483 if (!node) { return GRN_FILE_CORRUPT; }
2484 ch = PAT_CHK(node);
2485 if (ch <= check) {
2486 if (check >= min) { push(c, id, check); }
2487 break;
2488 }
2489 if ((check += 2) < ch) {
2490 if (!(k = pat_node_get_key(ctx, pat, node))) { return GRN_FILE_CORRUPT; }
2491 if ((r = bitcmp(key, k, check >> 1, (ch - check) >> 1))) {
2492 if (ch >= min) {
2493 push(c, node->lr[1], ch);
2494 push(c, node->lr[0], ch);
2495 }
2496 break;
2497 }
2498 }
2499 check = ch;
2500 if (nth_bit((uint8_t *)key, check, pat->key_size)) {
2501 if (check >= min) { push(c, node->lr[0], check); }
2502 id = node->lr[1];
2503 } else {
2504 if (check >= min) { push(c, node->lr[1], check); }
2505 id = node->lr[0];
2506 }
2507 }
2508 return GRN_SUCCESS;
2509}
2510
2511inline static grn_rc
2512set_cursor_common_prefix(grn_ctx *ctx, grn_pat *pat, grn_pat_cursor *c,
2513 uint32_t min_size, const void *key, uint32_t key_size, int flags)
2514{
2515 grn_id id;
2516 pat_node *node;
2517 const uint8_t *k;
2518 int check = -1, ch;
2519 uint32_t len = key_size * 16;
2520 uint8_t keybuf[MAX_FIXED_KEY_SIZE];
2521 KEY_ENCODE(pat, keybuf, key, key_size);
2522 PAT_AT(pat, 0, node);
2523 for (id = node->lr[1]; id;) {
2524 PAT_AT(pat, id, node);
2525 if (!node) { return GRN_FILE_CORRUPT; }
2526 ch = PAT_CHK(node);
2527 if (ch <= check) {
2528 if (!(k = pat_node_get_key(ctx, pat, node))) { return GRN_FILE_CORRUPT; }
2529 {
2530 uint32_t l = PAT_LEN(node);
2531 if (min_size <= l && l <= key_size) {
2532 if (!memcmp(key, k, l)) { push(c, id, check); }
2533 }
2534 }
2535 break;
2536 }
2537 check = ch;
2538 if (len <= check) { break; }
2539 if (check & 1) {
2540 grn_id id0 = node->lr[0];
2541 pat_node *node0;
2542 PAT_AT(pat, id0, node0);
2543 if (!node0) { return GRN_FILE_CORRUPT; }
2544 if (!(k = pat_node_get_key(ctx, pat, node0))) { return GRN_FILE_CORRUPT; }
2545 {
2546 uint32_t l = PAT_LEN(node0);
2547 if (memcmp(key, k, l)) { break; }
2548 if (min_size <= l) {
2549 push(c, id0, check);
2550 }
2551 }
2552 id = node->lr[1];
2553 } else {
2554 id = node->lr[nth_bit((uint8_t *)key, check, len)];
2555 }
2556 }
2557 return GRN_SUCCESS;
2558}
2559
2560inline static grn_rc
2561set_cursor_ascend(grn_ctx *ctx, grn_pat *pat, grn_pat_cursor *c,
2562 const void *key, uint32_t key_size, int flags)
2563{
2564 grn_id id;
2565 pat_node *node;
2566 const uint8_t *k;
2567 int r, check = -1, ch, c2;
2568 uint32_t len = key_size * 16;
2569 uint8_t keybuf[MAX_FIXED_KEY_SIZE];
2570 KEY_ENCODE(pat, keybuf, key, key_size);
2571 PAT_AT(pat, 0, node);
2572 for (id = node->lr[1]; id;) {
2573 PAT_AT(pat, id, node);
2574 if (!node) { return GRN_FILE_CORRUPT; }
2575 ch = PAT_CHK(node);
2576 if (ch <= check) {
2577 if (!(k = pat_node_get_key(ctx, pat, node))) { return GRN_FILE_CORRUPT; }
2578 {
2579 uint32_t l = PAT_LEN(node);
2580 if (l == key_size) {
2581 if (flags & GRN_CURSOR_GT) {
2582 if (memcmp(key, k, l) < 0) { push(c, id, check); }
2583 } else {
2584 if (memcmp(key, k, l) <= 0) { push(c, id, check); }
2585 }
2586 } else if (l < key_size) {
2587 if (memcmp(key, k, l) < 0) { push(c, id, check); }
2588 } else {
2589 if (memcmp(key, k, key_size) <= 0) { push(c, id, check); }
2590 }
2591 }
2592 break;
2593 }
2594 c2 = len < ch ? len : ch;
2595 if ((check += 2) < c2) {
2596 if (!(k = pat_node_get_key(ctx, pat, node))) { return GRN_FILE_CORRUPT; }
2597 if ((r = bitcmp(key, k, check >> 1, ((c2 + 1) >> 1) - (check >> 1)))) {
2598 if (r < 0) {
2599 push(c, node->lr[1], ch);
2600 push(c, node->lr[0], ch);
2601 }
2602 break;
2603 }
2604 }
2605 check = ch;
2606 if (len <= check) {
2607 push(c, node->lr[1], ch);
2608 push(c, node->lr[0], ch);
2609 break;
2610 }
2611 if (check & 1) {
2612 if (check + 1 < len) {
2613 id = node->lr[1];
2614 } else {
2615 push(c, node->lr[1], check);
2616 id = node->lr[0];
2617 }
2618 } else {
2619 if (nth_bit((uint8_t *)key, check, len)) {
2620 id = node->lr[1];
2621 } else {
2622 push(c, node->lr[1], check);
2623 id = node->lr[0];
2624 }
2625 }
2626 }
2627 return GRN_SUCCESS;
2628}
2629
2630inline static grn_rc
2631set_cursor_descend(grn_ctx *ctx, grn_pat *pat, grn_pat_cursor *c,
2632 const void *key, uint32_t key_size, int flags)
2633{
2634 grn_id id;
2635 pat_node *node;
2636 const uint8_t *k;
2637 int r, check = -1, ch, c2;
2638 uint32_t len = key_size * 16;
2639 uint8_t keybuf[MAX_FIXED_KEY_SIZE];
2640 KEY_ENCODE(pat, keybuf, key, key_size);
2641 PAT_AT(pat, 0, node);
2642 for (id = node->lr[1]; id;) {
2643 PAT_AT(pat, id, node);
2644 if (!node) { return GRN_FILE_CORRUPT; }
2645 ch = PAT_CHK(node);
2646 if (ch <= check) {
2647 if (!(k = pat_node_get_key(ctx, pat, node))) { return GRN_FILE_CORRUPT; }
2648 {
2649 uint32_t l = PAT_LEN(node);
2650 if (l <= key_size) {
2651 if ((flags & GRN_CURSOR_LT) && l == key_size) {
2652 if (memcmp(key, k, l) > 0) { push(c, id, check); }
2653 } else {
2654 if (memcmp(key, k, l) >= 0) { push(c, id, check); }
2655 }
2656 } else {
2657 if (memcmp(key, k, key_size) > 0) { push(c, id, check); }
2658 }
2659 }
2660 break;
2661 }
2662 c2 = len < ch ? len : ch;
2663 if ((check += 2) < c2) {
2664 if (!(k = pat_node_get_key(ctx, pat, node))) { return GRN_FILE_CORRUPT; }
2665 if ((r = bitcmp(key, k, check >> 1, ((c2 + 1) >> 1) - (check >> 1)))) {
2666 if (r >= 0) {
2667 push(c, node->lr[0], ch);
2668 push(c, node->lr[1], ch);
2669 }
2670 break;
2671 }
2672 }
2673 check = ch;
2674 if (len <= check) { break; }
2675 if (check & 1) {
2676 if (check + 1 < len) {
2677 push(c, node->lr[0], check);
2678 id = node->lr[1];
2679 } else {
2680 id = node->lr[0];
2681 }
2682 } else {
2683 if (nth_bit((uint8_t *)key, check, len)) {
2684 push(c, node->lr[0], check);
2685 id = node->lr[1];
2686 } else {
2687 id = node->lr[0];
2688 }
2689 }
2690 }
2691 return GRN_SUCCESS;
2692}
2693
2694static grn_pat_cursor *
2695grn_pat_cursor_open_by_id(grn_ctx *ctx, grn_pat *pat,
2696 const void *min, uint32_t min_size,
2697 const void *max, uint32_t max_size,
2698 int offset, int limit, int flags)
2699{
2700 int dir;
2701 grn_pat_cursor *c;
2702 if (!pat || !ctx) { return NULL; }
2703 if (!(c = GRN_MALLOCN(grn_pat_cursor, 1))) { return NULL; }
2704 GRN_DB_OBJ_SET_TYPE(c, GRN_CURSOR_TABLE_PAT_KEY);
2705 c->pat = pat;
2706 c->ctx = ctx;
2707 c->obj.header.flags = flags;
2708 c->obj.header.domain = GRN_ID_NIL;
2709 c->size = 0;
2710 c->sp = 0;
2711 c->ss = NULL;
2712 c->tail = 0;
2713 if (flags & GRN_CURSOR_DESCENDING) {
2714 dir = -1;
2715 if (max) {
2716 if (!(c->curr_rec = grn_pat_get(ctx, pat, max, max_size, NULL))) {
2717 c->tail = GRN_ID_NIL;
2718 goto exit;
2719 }
2720 if (!(flags & GRN_CURSOR_LT)) { c->curr_rec++; }
2721 } else {
2722 c->curr_rec = pat->header->curr_rec + 1;
2723 }
2724 if (min) {
2725 if (!(c->tail = grn_pat_get(ctx, pat, min, min_size, NULL))) {
2726 c->curr_rec = GRN_ID_NIL;
2727 goto exit;
2728 }
2729 if ((flags & GRN_CURSOR_GT)) { c->tail++; }
2730 } else {
2731 c->tail = GRN_ID_NIL + 1;
2732 }
2733 if (c->curr_rec < c->tail) { c->tail = c->curr_rec; }
2734 } else {
2735 dir = 1;
2736 if (min) {
2737 if (!(c->curr_rec = grn_pat_get(ctx, pat, min, min_size, NULL))) {
2738 c->tail = GRN_ID_NIL;
2739 goto exit;
2740 }
2741 if (!(flags & GRN_CURSOR_GT)) { c->curr_rec--; }
2742 } else {
2743 c->curr_rec = GRN_ID_NIL;
2744 }
2745 if (max) {
2746 if (!(c->tail = grn_pat_get(ctx, pat, max, max_size, NULL))) {
2747 c->curr_rec = GRN_ID_NIL;
2748 goto exit;
2749 }
2750 if ((flags & GRN_CURSOR_LT)) { c->tail--; }
2751 } else {
2752 c->tail = pat->header->curr_rec;
2753 }
2754 if (c->tail < c->curr_rec) { c->tail = c->curr_rec; }
2755 }
2756 if (pat->header->n_garbages) {
2757 while (offset && c->curr_rec != c->tail) {
2758 uint32_t key_size;
2759 const void *key;
2760 c->curr_rec += dir;
2761 key = _grn_pat_key(ctx, pat, c->curr_rec, &key_size);
2762 if (_grn_pat_get(ctx, pat, key, key_size, NULL) == c->curr_rec) {
2763 offset--;
2764 }
2765 }
2766 } else {
2767 if ((dir * (c->tail - c->curr_rec)) < offset) {
2768 c->curr_rec = c->tail;
2769 } else {
2770 c->curr_rec += dir * offset;
2771 }
2772 }
2773 c->rest = (limit < 0) ? GRN_ID_MAX : limit;
2774exit :
2775 return c;
2776}
2777
2778static grn_rc set_cursor_rk(grn_ctx *ctx, grn_pat *pat, grn_pat_cursor *c,
2779 const void *key, uint32_t key_size, int flags);
2780
2781grn_pat_cursor *
2782grn_pat_cursor_open(grn_ctx *ctx, grn_pat *pat,
2783 const void *min, uint32_t min_size,
2784 const void *max, uint32_t max_size,
2785 int offset, int limit, int flags)
2786{
2787 grn_id id;
2788 pat_node *node;
2789 grn_pat_cursor *c;
2790 if (!pat || !ctx) { return NULL; }
2791 if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
2792 return NULL;
2793 }
2794 if ((flags & GRN_CURSOR_BY_ID)) {
2795 return grn_pat_cursor_open_by_id(ctx, pat, min, min_size, max, max_size,
2796 offset, limit, flags);
2797 }
2798 if (!(c = GRN_MALLOCN(grn_pat_cursor, 1))) { return NULL; }
2799 GRN_DB_OBJ_SET_TYPE(c, GRN_CURSOR_TABLE_PAT_KEY);
2800 c->pat = pat;
2801 c->ctx = ctx;
2802 c->size = 0;
2803 c->sp = 0;
2804 c->ss = NULL;
2805 c->tail = 0;
2806 c->rest = GRN_ID_MAX;
2807 c->curr_rec = GRN_ID_NIL;
2808 c->obj.header.domain = GRN_ID_NIL;
2809 if (flags & GRN_CURSOR_PREFIX) {
2810 if (max && max_size) {
2811 if ((pat->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE)) {
2812 set_cursor_common_prefix(ctx, pat, c, min_size, max, max_size, flags);
2813 } else {
2814 set_cursor_near(ctx, pat, c, min_size, max, flags);
2815 }
2816 goto exit;
2817 } else {
2818 if (min && min_size) {
2819 if (flags & GRN_CURSOR_RK) {
2820 set_cursor_rk(ctx, pat, c, min, min_size, flags);
2821 } else {
2822 set_cursor_prefix(ctx, pat, c, min, min_size, flags);
2823 }
2824 goto exit;
2825 }
2826 }
2827 }
2828 if (flags & GRN_CURSOR_DESCENDING) {
2829 if (min && min_size) {
2830 set_cursor_ascend(ctx, pat, c, min, min_size, flags);
2831 c->obj.header.flags = GRN_CURSOR_ASCENDING;
2832 c->tail = grn_pat_cursor_next(ctx, c);
2833 c->sp = 0;
2834 if (!c->tail) { goto exit; }
2835 }
2836 if (max && max_size) {
2837 set_cursor_descend(ctx, pat, c, max, max_size, flags);
2838 } else {
2839 PAT_AT(pat, 0, node);
2840 if (!node) {
2841 grn_pat_cursor_close(ctx, c);
2842 return NULL;
2843 }
2844 if ((id = node->lr[1])) {
2845 PAT_AT(pat, id, node);
2846 if (node) {
2847 int ch = PAT_CHK(node);
2848 push(c, node->lr[0], ch);
2849 push(c, node->lr[1], ch);
2850 }
2851 }
2852 }
2853 } else {
2854 if (max && max_size) {
2855 set_cursor_descend(ctx, pat, c, max, max_size, flags);
2856 c->obj.header.flags = GRN_CURSOR_DESCENDING;
2857 c->tail = grn_pat_cursor_next(ctx, c);
2858 c->sp = 0;
2859 if (!c->tail) { goto exit; }
2860 }
2861 if (min && min_size) {
2862 set_cursor_ascend(ctx, pat, c, min, min_size, flags);
2863 } else {
2864 PAT_AT(pat, 0, node);
2865 if (!node) {
2866 grn_pat_cursor_close(ctx, c);
2867 return NULL;
2868 }
2869 if ((id = node->lr[1])) {
2870 PAT_AT(pat, id, node);
2871 if (node) {
2872 int ch = PAT_CHK(node);
2873 push(c, node->lr[1], ch);
2874 push(c, node->lr[0], ch);
2875 }
2876 }
2877 }
2878 }
2879exit :
2880 c->obj.header.flags = flags;
2881 c->curr_rec = GRN_ID_NIL;
2882 while (offset--) { grn_pat_cursor_next(ctx, c); }
2883 c->rest = (limit < 0) ? GRN_ID_MAX : limit;
2884 return c;
2885}
2886
2887int
2888grn_pat_cursor_get_key(grn_ctx *ctx, grn_pat_cursor *c, void **key)
2889{
2890 *key = c->curr_key;
2891 return grn_pat_get_key(ctx, c->pat, c->curr_rec, *key, GRN_TABLE_MAX_KEY_SIZE);
2892}
2893
2894int
2895grn_pat_cursor_get_value(grn_ctx *ctx, grn_pat_cursor *c, void **value)
2896{
2897 int value_size = (int)c->pat->value_size;
2898 if (value_size) {
2899 byte *v = (byte *)sis_at(ctx, c->pat, c->curr_rec);
2900 if (v) {
2901 if (c->pat->obj.header.flags & GRN_OBJ_KEY_WITH_SIS) {
2902 *value = v + sizeof(sis_node);
2903 } else {
2904 *value = v;
2905 }
2906 } else {
2907 *value = NULL;
2908 }
2909 }
2910 return value_size;
2911}
2912
2913int
2914grn_pat_cursor_get_key_value(grn_ctx *ctx, grn_pat_cursor *c,
2915 void **key, uint32_t *key_size, void **value)
2916{
2917 int value_size = (int)c->pat->value_size;
2918 if (key_size) {
2919 *key_size = (uint32_t) grn_pat_get_key(ctx, c->pat, c->curr_rec, c->curr_key,
2920 GRN_TABLE_MAX_KEY_SIZE);
2921 if (key) { *key = c->curr_key; }
2922 }
2923 if (value && value_size) {
2924 byte *v = (byte *)sis_at(ctx, c->pat, c->curr_rec);
2925 if (v) {
2926 if (c->pat->obj.header.flags & GRN_OBJ_KEY_WITH_SIS) {
2927 *value = v + sizeof(sis_node);
2928 } else {
2929 *value = v;
2930 }
2931 } else {
2932 *value = NULL;
2933 }
2934 }
2935 return value_size;
2936}
2937
2938grn_rc
2939grn_pat_cursor_set_value(grn_ctx *ctx, grn_pat_cursor *c,
2940 const void *value, int flags)
2941{
2942 return grn_pat_set_value(ctx, c->pat, c->curr_rec, value, flags);
2943}
2944
2945grn_rc
2946grn_pat_cursor_delete(grn_ctx *ctx, grn_pat_cursor *c,
2947 grn_table_delete_optarg *optarg)
2948{
2949 return grn_pat_delete_by_id(ctx, c->pat, c->curr_rec, optarg);
2950}
2951
2952void
2953grn_pat_check(grn_ctx *ctx, grn_pat *pat)
2954{
2955 char buf[8];
2956 struct grn_pat_header *h = pat->header;
2957 if (grn_pat_error_if_truncated(ctx, pat) != GRN_SUCCESS) {
2958 return;
2959 }
2960 GRN_OUTPUT_ARRAY_OPEN("RESULT", 1);
2961 GRN_OUTPUT_MAP_OPEN("SUMMARY", 23);
2962 GRN_OUTPUT_CSTR("flags");
2963 grn_itoh(h->flags, buf, 8);
2964 GRN_OUTPUT_STR(buf, 8);
2965 GRN_OUTPUT_CSTR("key size");
2966 GRN_OUTPUT_INT64(h->key_size);
2967 GRN_OUTPUT_CSTR("value_size");
2968 GRN_OUTPUT_INT64(h->value_size);
2969 GRN_OUTPUT_CSTR("tokenizer");
2970 GRN_OUTPUT_INT64(h->tokenizer);
2971 GRN_OUTPUT_CSTR("normalizer");
2972 GRN_OUTPUT_INT64(h->normalizer);
2973 GRN_OUTPUT_CSTR("n_entries");
2974 GRN_OUTPUT_INT64(h->n_entries);
2975 GRN_OUTPUT_CSTR("curr_rec");
2976 GRN_OUTPUT_INT64(h->curr_rec);
2977 GRN_OUTPUT_CSTR("curr_key");
2978 GRN_OUTPUT_INT64(h->curr_key);
2979 GRN_OUTPUT_CSTR("curr_del");
2980 GRN_OUTPUT_INT64(h->curr_del);
2981 GRN_OUTPUT_CSTR("curr_del2");
2982 GRN_OUTPUT_INT64(h->curr_del2);
2983 GRN_OUTPUT_CSTR("curr_del3");
2984 GRN_OUTPUT_INT64(h->curr_del3);
2985 GRN_OUTPUT_CSTR("n_garbages");
2986 GRN_OUTPUT_INT64(h->n_garbages);
2987 GRN_OUTPUT_MAP_CLOSE();
2988 GRN_OUTPUT_ARRAY_CLOSE();
2989}
2990
2991/* utilities */
2992void
2993grn_p_pat_node(grn_ctx *ctx, grn_pat *pat, pat_node *node)
2994{
2995 uint8_t *key = NULL;
2996
2997 if (!node) {
2998 printf("#<pat_node:(null)>\n");
2999 return;
3000 }
3001
3002 if (PAT_IMD(node)) {
3003 key = (uint8_t *)&(node->key);
3004 } else {
3005 KEY_AT(pat, node->key, key, 0);
3006 }
3007
3008 printf("#<pat_node:%p "
3009 "left:%u "
3010 "right:%u "
3011 "deleting:%s "
3012 "immediate:%s "
3013 "length:%u "
3014 "nth-byte:%u "
3015 "nth-bit:%u "
3016 "terminated:%s "
3017 "key:<%.*s>"
3018 ">\n",
3019 node,
3020 node->lr[0],
3021 node->lr[1],
3022 PAT_DEL(node) ? "true" : "false",
3023 PAT_IMD(node) ? "true" : "false",
3024 PAT_LEN(node),
3025 PAT_CHK(node) >> 4,
3026 (PAT_CHK(node) >> 1) & 0x7,
3027 (PAT_CHK(node) & 0x1) ? "true" : "false",
3028 PAT_LEN(node),
3029 (char *)key);
3030}
3031
3032static void
3033grn_pat_inspect_check(grn_ctx *ctx, grn_obj *buf, int check)
3034{
3035 GRN_TEXT_PUTS(ctx, buf, "{");
3036 grn_text_lltoa(ctx, buf, check >> 4);
3037 GRN_TEXT_PUTS(ctx, buf, ",");
3038 grn_text_lltoa(ctx, buf, (check >> 1) & 7);
3039 GRN_TEXT_PUTS(ctx, buf, ",");
3040 grn_text_lltoa(ctx, buf, check & 1);
3041 GRN_TEXT_PUTS(ctx, buf, "}");
3042}
3043
3044static void
3045grn_pat_inspect_node(grn_ctx *ctx, grn_pat *pat, grn_id id, int check,
3046 grn_obj *key_buf, int indent, const char *prefix,
3047 grn_obj *buf)
3048{
3049 pat_node *node = NULL;
3050 int i, c;
3051
3052 PAT_AT(pat, id, node);
3053 c = PAT_CHK(node);
3054
3055 for (i = 0; i < indent; i++) {
3056 GRN_TEXT_PUTC(ctx, buf, ' ');
3057 }
3058 GRN_TEXT_PUTS(ctx, buf, prefix);
3059 grn_text_lltoa(ctx, buf, id);
3060 grn_pat_inspect_check(ctx, buf, c);
3061
3062 if (c > check) {
3063 GRN_TEXT_PUTS(ctx, buf, "\n");
3064 grn_pat_inspect_node(ctx, pat, node->lr[0], c, key_buf,
3065 indent + 2, "L:", buf);
3066 GRN_TEXT_PUTS(ctx, buf, "\n");
3067 grn_pat_inspect_node(ctx, pat, node->lr[1], c, key_buf,
3068 indent + 2, "R:", buf);
3069 } else if (id) {
3070 int key_size;
3071 uint8_t *key;
3072
3073 key_size = PAT_LEN(node);
3074 GRN_BULK_REWIND(key_buf);
3075 grn_bulk_space(ctx, key_buf, key_size);
3076 grn_pat_get_key(ctx, pat, id, GRN_BULK_HEAD(key_buf), key_size);
3077 GRN_TEXT_PUTS(ctx, buf, "(");
3078 grn_inspect(ctx, buf, key_buf);
3079 GRN_TEXT_PUTS(ctx, buf, ")");
3080
3081 GRN_TEXT_PUTS(ctx, buf, "[");
3082 key = pat_node_get_key(ctx, pat, node);
3083 for (i = 0; i < key_size; i++) {
3084 int j;
3085 uint8_t byte = key[i];
3086 if (i != 0) {
3087 GRN_TEXT_PUTS(ctx, buf, " ");
3088 }
3089 for (j = 0; j < 8; j++) {
3090 grn_text_lltoa(ctx, buf, (byte >> (7 - j)) & 1);
3091 }
3092 }
3093 GRN_TEXT_PUTS(ctx, buf, "]");
3094 }
3095}
3096
3097void
3098grn_pat_inspect_nodes(grn_ctx *ctx, grn_pat *pat, grn_obj *buf)
3099{
3100 pat_node *node;
3101 grn_obj key_buf;
3102
3103 GRN_TEXT_PUTS(ctx, buf, "{");
3104 PAT_AT(pat, GRN_ID_NIL, node);
3105 if (node->lr[1]) {
3106 GRN_TEXT_PUTS(ctx, buf, "\n");
3107 GRN_OBJ_INIT(&key_buf, GRN_BULK, 0, pat->obj.header.domain);
3108 grn_pat_inspect_node(ctx, pat, node->lr[1], -1, &key_buf, 0, "", buf);
3109 GRN_OBJ_FIN(ctx, &key_buf);
3110 GRN_TEXT_PUTS(ctx, buf, "\n");
3111 }
3112 GRN_TEXT_PUTS(ctx, buf, "}");
3113}
3114
3115static void
3116grn_pat_cursor_inspect_entries(grn_ctx *ctx, grn_pat_cursor *c, grn_obj *buf)
3117{
3118 int i;
3119 GRN_TEXT_PUTS(ctx, buf, "[");
3120 for (i = 0; i < c->sp; i++) {
3121 grn_pat_cursor_entry *e = c->ss + i;
3122 if (i != 0) {
3123 GRN_TEXT_PUTS(ctx, buf, ", ");
3124 }
3125 GRN_TEXT_PUTS(ctx, buf, "[");
3126 grn_text_lltoa(ctx, buf, e->id);
3127 GRN_TEXT_PUTS(ctx, buf, ",");
3128 grn_pat_inspect_check(ctx, buf, e->check);
3129 GRN_TEXT_PUTS(ctx, buf, "]");
3130 }
3131 GRN_TEXT_PUTS(ctx, buf, "]");
3132}
3133
3134void
3135grn_pat_cursor_inspect(grn_ctx *ctx, grn_pat_cursor *c, grn_obj *buf)
3136{
3137 GRN_TEXT_PUTS(ctx, buf, "#<cursor:pat:");
3138 grn_inspect_name(ctx, buf, (grn_obj *)(c->pat));
3139
3140 GRN_TEXT_PUTS(ctx, buf, " ");
3141 GRN_TEXT_PUTS(ctx, buf, "current:");
3142 grn_text_lltoa(ctx, buf, c->curr_rec);
3143
3144 GRN_TEXT_PUTS(ctx, buf, " ");
3145 GRN_TEXT_PUTS(ctx, buf, "tail:");
3146 grn_text_lltoa(ctx, buf, c->tail);
3147
3148 GRN_TEXT_PUTS(ctx, buf, " ");
3149 GRN_TEXT_PUTS(ctx, buf, "flags:");
3150 if (c->obj.header.flags & GRN_CURSOR_PREFIX) {
3151 GRN_TEXT_PUTS(ctx, buf, "prefix");
3152 } else {
3153 if (c->obj.header.flags & GRN_CURSOR_DESCENDING) {
3154 GRN_TEXT_PUTS(ctx, buf, "descending");
3155 } else {
3156 GRN_TEXT_PUTS(ctx, buf, "ascending");
3157 }
3158 GRN_TEXT_PUTS(ctx, buf, "|");
3159 if (c->obj.header.flags & GRN_CURSOR_GT) {
3160 GRN_TEXT_PUTS(ctx, buf, "greater-than");
3161 } else {
3162 GRN_TEXT_PUTS(ctx, buf, "greater");
3163 }
3164 GRN_TEXT_PUTS(ctx, buf, "|");
3165 if (c->obj.header.flags & GRN_CURSOR_LT) {
3166 GRN_TEXT_PUTS(ctx, buf, "less-than");
3167 } else {
3168 GRN_TEXT_PUTS(ctx, buf, "less");
3169 }
3170 if (c->obj.header.flags & GRN_CURSOR_BY_ID) {
3171 GRN_TEXT_PUTS(ctx, buf, "|by-id");
3172 }
3173 if (c->obj.header.flags & GRN_CURSOR_BY_KEY) {
3174 GRN_TEXT_PUTS(ctx, buf, "|by-key");
3175 }
3176 }
3177
3178 GRN_TEXT_PUTS(ctx, buf, " ");
3179 GRN_TEXT_PUTS(ctx, buf, "rest:");
3180 grn_text_lltoa(ctx, buf, c->rest);
3181
3182 GRN_TEXT_PUTS(ctx, buf, " ");
3183 GRN_TEXT_PUTS(ctx, buf, "entries:");
3184 grn_pat_cursor_inspect_entries(ctx, c, buf);
3185
3186 GRN_TEXT_PUTS(ctx, buf, ">");
3187}
3188
3189typedef struct {
3190 uint8_t code;
3191 uint8_t next;
3192 uint8_t emit;
3193 uint8_t attr;
3194} rk_tree_node;
3195
3196static uint16_t rk_str_idx[] = {
3197 0x0003, 0x0006, 0x0009, 0x000c, 0x0012, 0x0015, 0x0018, 0x001e, 0x0024, 0x002a,
3198 0x0030, 0x0036, 0x003c, 0x0042, 0x0048, 0x004e, 0x0054, 0x005a, 0x0060, 0x0066,
3199 0x006c, 0x0072, 0x0078, 0x007e, 0x0084, 0x008a, 0x0090, 0x0096, 0x009c, 0x00a2,
3200 0x00a8, 0x00ae, 0x00b4, 0x00ba, 0x00c0, 0x00c3, 0x00c6, 0x00c9, 0x00cc, 0x00cf,
3201 0x00d2, 0x00d5, 0x00db, 0x00e1, 0x00e7, 0x00ea, 0x00f0, 0x00f6, 0x00fc, 0x00ff,
3202 0x0105, 0x0108, 0x010e, 0x0111, 0x0114, 0x0117, 0x011a, 0x011d, 0x0120, 0x0123,
3203 0x0129, 0x012f, 0x0135, 0x013b, 0x013e, 0x0144, 0x014a, 0x0150, 0x0156, 0x0159,
3204 0x015c, 0x015f, 0x0162, 0x0165, 0x0168, 0x016b, 0x016e, 0x0171, 0x0177, 0x017d,
3205 0x0183, 0x0189, 0x018c, 0x0192, 0x0198, 0x019e, 0x01a1, 0x01a4, 0x01aa, 0x01b0,
3206 0x01b6, 0x01bc, 0x01bf, 0x01c2, 0x01c8, 0x01ce, 0x01d1, 0x01d7, 0x01dd, 0x01e0,
3207 0x01e6, 0x01e9, 0x01ef, 0x01f2, 0x01f5, 0x01fb, 0x0201, 0x0207, 0x020d, 0x0213,
3208 0x0216, 0x0219, 0x021c, 0x021f, 0x0222, 0x0225, 0x0228, 0x022e, 0x0234, 0x023a,
3209 0x023d, 0x0243, 0x0249, 0x024f, 0x0252, 0x0258, 0x025e, 0x0264, 0x0267, 0x026d,
3210 0x0273, 0x0279, 0x027f, 0x0285, 0x0288, 0x028b, 0x028e, 0x0291, 0x0294, 0x0297,
3211 0x029a, 0x029d, 0x02a0, 0x02a3, 0x02a9, 0x02af, 0x02b5, 0x02b8, 0x02bb, 0x02be,
3212 0x02c1, 0x02c4, 0x02c7, 0x02ca, 0x02cd, 0x02d0, 0x02d3, 0x02d6, 0x02dc, 0x02e2,
3213 0x02e8, 0x02eb, 0x02ee, 0x02f1, 0x02f4, 0x02f7, 0x02fa, 0x02fd, 0x0300, 0x0303,
3214 0x0309, 0x030c, 0x0312, 0x0318, 0x031e, 0x0324, 0x0327, 0x032a, 0x032d
3215};
3216static char rk_str[] = {
3217 0xe3, 0x82, 0xa1, 0xe3, 0x82, 0xa2, 0xe3, 0x82, 0xa3, 0xe3, 0x82, 0xa4, 0xe3,
3218 0x82, 0xa4, 0xe3, 0x82, 0xa7, 0xe3, 0x82, 0xa5, 0xe3, 0x82, 0xa6, 0xe3, 0x82,
3219 0xa6, 0xe3, 0x82, 0xa2, 0xe3, 0x82, 0xa6, 0xe3, 0x82, 0xa3, 0xe3, 0x82, 0xa6,
3220 0xe3, 0x82, 0xa4, 0xe3, 0x82, 0xa6, 0xe3, 0x82, 0xa6, 0xe3, 0x82, 0xa6, 0xe3,
3221 0x82, 0xa7, 0xe3, 0x82, 0xa6, 0xe3, 0x82, 0xa8, 0xe3, 0x82, 0xa6, 0xe3, 0x82,
3222 0xaa, 0xe3, 0x82, 0xa6, 0xe3, 0x83, 0xa0, 0xe3, 0x82, 0xa6, 0xe3, 0x83, 0xa1,
3223 0xe3, 0x82, 0xa6, 0xe3, 0x83, 0xa2, 0xe3, 0x82, 0xa6, 0xe3, 0x83, 0xa3, 0xe3,
3224 0x82, 0xa6, 0xe3, 0x83, 0xa4, 0xe3, 0x82, 0xa6, 0xe3, 0x83, 0xa5, 0xe3, 0x82,
3225 0xa6, 0xe3, 0x83, 0xa6, 0xe3, 0x82, 0xa6, 0xe3, 0x83, 0xa7, 0xe3, 0x82, 0xa6,
3226 0xe3, 0x83, 0xa8, 0xe3, 0x82, 0xa6, 0xe3, 0x83, 0xa9, 0xe3, 0x82, 0xa6, 0xe3,
3227 0x83, 0xaa, 0xe3, 0x82, 0xa6, 0xe3, 0x83, 0xab, 0xe3, 0x82, 0xa6, 0xe3, 0x83,
3228 0xac, 0xe3, 0x82, 0xa6, 0xe3, 0x83, 0xad, 0xe3, 0x82, 0xa6, 0xe3, 0x83, 0xae,
3229 0xe3, 0x82, 0xa6, 0xe3, 0x83, 0xaf, 0xe3, 0x82, 0xa6, 0xe3, 0x83, 0xb0, 0xe3,
3230 0x82, 0xa6, 0xe3, 0x83, 0xb1, 0xe3, 0x82, 0xa6, 0xe3, 0x83, 0xb2, 0xe3, 0x82,
3231 0xa6, 0xe3, 0x83, 0xb3, 0xe3, 0x82, 0xa6, 0xe3, 0x83, 0xbc, 0xe3, 0x82, 0xa7,
3232 0xe3, 0x82, 0xa8, 0xe3, 0x82, 0xa9, 0xe3, 0x82, 0xaa, 0xe3, 0x82, 0xab, 0xe3,
3233 0x82, 0xac, 0xe3, 0x82, 0xad, 0xe3, 0x82, 0xad, 0xe3, 0x83, 0xa3, 0xe3, 0x82,
3234 0xad, 0xe3, 0x83, 0xa5, 0xe3, 0x82, 0xad, 0xe3, 0x83, 0xa7, 0xe3, 0x82, 0xae,
3235 0xe3, 0x82, 0xae, 0xe3, 0x83, 0xa3, 0xe3, 0x82, 0xae, 0xe3, 0x83, 0xa5, 0xe3,
3236 0x82, 0xae, 0xe3, 0x83, 0xa7, 0xe3, 0x82, 0xaf, 0xe3, 0x82, 0xaf, 0xe3, 0x82,
3237 0xa1, 0xe3, 0x82, 0xb0, 0xe3, 0x82, 0xb0, 0xe3, 0x82, 0xa1, 0xe3, 0x82, 0xb1,
3238 0xe3, 0x82, 0xb2, 0xe3, 0x82, 0xb3, 0xe3, 0x82, 0xb4, 0xe3, 0x82, 0xb5, 0xe3,
3239 0x82, 0xb6, 0xe3, 0x82, 0xb7, 0xe3, 0x82, 0xb7, 0xe3, 0x82, 0xa7, 0xe3, 0x82,
3240 0xb7, 0xe3, 0x83, 0xa3, 0xe3, 0x82, 0xb7, 0xe3, 0x83, 0xa5, 0xe3, 0x82, 0xb7,
3241 0xe3, 0x83, 0xa7, 0xe3, 0x82, 0xb8, 0xe3, 0x82, 0xb8, 0xe3, 0x82, 0xa7, 0xe3,
3242 0x82, 0xb8, 0xe3, 0x83, 0xa3, 0xe3, 0x82, 0xb8, 0xe3, 0x83, 0xa5, 0xe3, 0x82,
3243 0xb8, 0xe3, 0x83, 0xa7, 0xe3, 0x82, 0xb9, 0xe3, 0x82, 0xba, 0xe3, 0x82, 0xbb,
3244 0xe3, 0x82, 0xbc, 0xe3, 0x82, 0xbd, 0xe3, 0x82, 0xbe, 0xe3, 0x82, 0xbf, 0xe3,
3245 0x83, 0x80, 0xe3, 0x83, 0x81, 0xe3, 0x83, 0x81, 0xe3, 0x82, 0xa7, 0xe3, 0x83,
3246 0x81, 0xe3, 0x83, 0xa3, 0xe3, 0x83, 0x81, 0xe3, 0x83, 0xa5, 0xe3, 0x83, 0x81,
3247 0xe3, 0x83, 0xa7, 0xe3, 0x83, 0x82, 0xe3, 0x83, 0x82, 0xe3, 0x83, 0xa3, 0xe3,
3248 0x83, 0x82, 0xe3, 0x83, 0xa5, 0xe3, 0x83, 0x82, 0xe3, 0x83, 0xa7, 0xe3, 0x83,
3249 0x83, 0xe3, 0x83, 0x84, 0xe3, 0x83, 0x84, 0xe3, 0x82, 0xa1, 0xe3, 0x83, 0x84,
3250 0xe3, 0x82, 0xa3, 0xe3, 0x83, 0x84, 0xe3, 0x82, 0xa7, 0xe3, 0x83, 0x84, 0xe3,
3251 0x82, 0xa9, 0xe3, 0x83, 0x85, 0xe3, 0x83, 0x86, 0xe3, 0x83, 0x86, 0xe3, 0x82,
3252 0xa3, 0xe3, 0x83, 0x86, 0xe3, 0x83, 0xa5, 0xe3, 0x83, 0x87, 0xe3, 0x83, 0x87,
3253 0xe3, 0x82, 0xa3, 0xe3, 0x83, 0x87, 0xe3, 0x83, 0xa5, 0xe3, 0x83, 0x88, 0xe3,
3254 0x83, 0x88, 0xe3, 0x82, 0xa5, 0xe3, 0x83, 0x89, 0xe3, 0x83, 0x89, 0xe3, 0x82,
3255 0xa5, 0xe3, 0x83, 0x8a, 0xe3, 0x83, 0x8b, 0xe3, 0x83, 0x8b, 0xe3, 0x82, 0xa3,
3256 0xe3, 0x83, 0x8b, 0xe3, 0x82, 0xa7, 0xe3, 0x83, 0x8b, 0xe3, 0x83, 0xa3, 0xe3,
3257 0x83, 0x8b, 0xe3, 0x83, 0xa5, 0xe3, 0x83, 0x8b, 0xe3, 0x83, 0xa7, 0xe3, 0x83,
3258 0x8c, 0xe3, 0x83, 0x8d, 0xe3, 0x83, 0x8e, 0xe3, 0x83, 0x8f, 0xe3, 0x83, 0x90,
3259 0xe3, 0x83, 0x91, 0xe3, 0x83, 0x92, 0xe3, 0x83, 0x92, 0xe3, 0x83, 0xa3, 0xe3,
3260 0x83, 0x92, 0xe3, 0x83, 0xa5, 0xe3, 0x83, 0x92, 0xe3, 0x83, 0xa7, 0xe3, 0x83,
3261 0x93, 0xe3, 0x83, 0x93, 0xe3, 0x83, 0xa3, 0xe3, 0x83, 0x93, 0xe3, 0x83, 0xa5,
3262 0xe3, 0x83, 0x93, 0xe3, 0x83, 0xa7, 0xe3, 0x83, 0x94, 0xe3, 0x83, 0x94, 0xe3,
3263 0x83, 0xa3, 0xe3, 0x83, 0x94, 0xe3, 0x83, 0xa5, 0xe3, 0x83, 0x94, 0xe3, 0x83,
3264 0xa7, 0xe3, 0x83, 0x95, 0xe3, 0x83, 0x95, 0xe3, 0x82, 0xa1, 0xe3, 0x83, 0x95,
3265 0xe3, 0x82, 0xa3, 0xe3, 0x83, 0x95, 0xe3, 0x82, 0xa7, 0xe3, 0x83, 0x95, 0xe3,
3266 0x82, 0xa9, 0xe3, 0x83, 0x95, 0xe3, 0x83, 0xa5, 0xe3, 0x83, 0x96, 0xe3, 0x83,
3267 0x97, 0xe3, 0x83, 0x98, 0xe3, 0x83, 0x99, 0xe3, 0x83, 0x9a, 0xe3, 0x83, 0x9b,
3268 0xe3, 0x83, 0x9c, 0xe3, 0x83, 0x9d, 0xe3, 0x83, 0x9e, 0xe3, 0x83, 0x9f, 0xe3,
3269 0x83, 0x9f, 0xe3, 0x83, 0xa3, 0xe3, 0x83, 0x9f, 0xe3, 0x83, 0xa5, 0xe3, 0x83,
3270 0x9f, 0xe3, 0x83, 0xa7, 0xe3, 0x83, 0xa0, 0xe3, 0x83, 0xa1, 0xe3, 0x83, 0xa2,
3271 0xe3, 0x83, 0xa3, 0xe3, 0x83, 0xa4, 0xe3, 0x83, 0xa5, 0xe3, 0x83, 0xa6, 0xe3,
3272 0x83, 0xa7, 0xe3, 0x83, 0xa8, 0xe3, 0x83, 0xa9, 0xe3, 0x83, 0xaa, 0xe3, 0x83,
3273 0xaa, 0xe3, 0x83, 0xa3, 0xe3, 0x83, 0xaa, 0xe3, 0x83, 0xa5, 0xe3, 0x83, 0xaa,
3274 0xe3, 0x83, 0xa7, 0xe3, 0x83, 0xab, 0xe3, 0x83, 0xac, 0xe3, 0x83, 0xad, 0xe3,
3275 0x83, 0xae, 0xe3, 0x83, 0xaf, 0xe3, 0x83, 0xb0, 0xe3, 0x83, 0xb1, 0xe3, 0x83,
3276 0xb2, 0xe3, 0x83, 0xb3, 0xe3, 0x83, 0xb3, 0xe3, 0x83, 0xbc, 0xe3, 0x83, 0xb4,
3277 0xe3, 0x83, 0xb4, 0xe3, 0x82, 0xa1, 0xe3, 0x83, 0xb4, 0xe3, 0x82, 0xa3, 0xe3,
3278 0x83, 0xb4, 0xe3, 0x82, 0xa7, 0xe3, 0x83, 0xb4, 0xe3, 0x82, 0xa9, 0xe3, 0x83,
3279 0xb5, 0xe3, 0x83, 0xb6, 0xe3, 0x83, 0xbc
3280};
3281static uint16_t rk_tree_idx[] = {
3282 0x001b, 0x0022, 0x0025, 0x0028, 0x002d, 0x0030, 0x0039, 0x003b, 0x003c, 0x003f,
3283 0x0046, 0x0047, 0x004f, 0x0050, 0x0053, 0x005a, 0x005d, 0x0064, 0x0067, 0x006f,
3284 0x0070, 0x0073, 0x007d, 0x007f, 0x0081, 0x0082, 0x0083, 0x0088, 0x008f, 0x0092,
3285 0x00af, 0x00b5, 0x00bc, 0x00bf, 0x00c6, 0x00c9, 0x00d1, 0x00d6, 0x00da, 0x00e4,
3286 0x00e6, 0x00eb, 0x00ec, 0x00f0, 0x00f6, 0x00fc, 0x00fe, 0x0108, 0x010a, 0x010c,
3287 0x010d, 0x010e, 0x0113, 0x0118, 0x011f, 0x0123, 0x0125, 0x0164, 0x0180, 0x0183,
3288 0x0199, 0x01ad
3289};
3290static rk_tree_node rk_tree[] = {
3291 {0x2d, 0x00, 0xb2, 0x01}, {0x61, 0x00, 0x01, 0x01}, {0x62, 0x01, 0xff, 0x01},
3292 {0x63, 0x03, 0xff, 0x01}, {0x64, 0x06, 0xff, 0x01}, {0x65, 0x00, 0x24, 0x01},
3293 {0x66, 0x0a, 0xff, 0x01}, {0x67, 0x0c, 0xff, 0x01}, {0x68, 0x0f, 0xff, 0x01},
3294 {0x69, 0x00, 0x03, 0x01}, {0x6a, 0x11, 0xff, 0x01}, {0x6b, 0x13, 0xff, 0x01},
3295 {0x6c, 0x16, 0xff, 0x01}, {0x6d, 0x1c, 0xff, 0x01}, {0x6e, 0x1e, 0xff, 0x01},
3296 {0x6f, 0x00, 0x26, 0x01}, {0x70, 0x20, 0xff, 0x01}, {0x72, 0x22, 0xff, 0x01},
3297 {0x73, 0x24, 0xff, 0x01}, {0x74, 0x27, 0xff, 0x01}, {0x75, 0x00, 0x06, 0x01},
3298 {0x76, 0x2c, 0xff, 0x01}, {0x77, 0x2d, 0xff, 0x01}, {0x78, 0x2f, 0xff, 0x01},
3299 {0x79, 0x35, 0xff, 0x01}, {0x7a, 0x36, 0xff, 0x01}, {0xe3, 0x38, 0xff, 0x01},
3300 {0x61, 0x00, 0x72, 0x01}, {0x62, 0x01, 0x56, 0x01}, {0x65, 0x00, 0x89, 0x01},
3301 {0x69, 0x00, 0x78, 0x01}, {0x6f, 0x00, 0x8c, 0x01}, {0x75, 0x00, 0x86, 0x01},
3302 {0x79, 0x02, 0xff, 0x00}, {0x61, 0x00, 0x79, 0x01}, {0x6f, 0x00, 0x7b, 0x01},
3303 {0x75, 0x00, 0x7a, 0x01}, {0x63, 0x03, 0x56, 0x01}, {0x68, 0x04, 0xff, 0x01},
3304 {0x79, 0x05, 0xff, 0x01}, {0x61, 0x00, 0x4f, 0x00}, {0x65, 0x00, 0x4e, 0x00},
3305 {0x69, 0x00, 0x4d, 0x01}, {0x6f, 0x00, 0x51, 0x00}, {0x75, 0x00, 0x50, 0x00},
3306 {0x61, 0x00, 0x4f, 0x01}, {0x6f, 0x00, 0x51, 0x01}, {0x75, 0x00, 0x50, 0x01},
3307 {0x61, 0x00, 0x4c, 0x01}, {0x64, 0x06, 0x56, 0x01}, {0x65, 0x00, 0x60, 0x01},
3308 {0x68, 0x07, 0xff, 0x00}, {0x69, 0x00, 0x61, 0x00}, {0x6f, 0x00, 0x65, 0x01},
3309 {0x75, 0x00, 0x5c, 0x01}, {0x77, 0x08, 0xff, 0x00}, {0x79, 0x09, 0xff, 0x01},
3310 {0x69, 0x00, 0x61, 0x01}, {0x75, 0x00, 0x62, 0x01}, {0x75, 0x00, 0x66, 0x01},
3311 {0x61, 0x00, 0x53, 0x01}, {0x6f, 0x00, 0x55, 0x01}, {0x75, 0x00, 0x54, 0x01},
3312 {0x61, 0x00, 0x81, 0x00}, {0x65, 0x00, 0x83, 0x00}, {0x66, 0x0a, 0x56, 0x01},
3313 {0x69, 0x00, 0x82, 0x00}, {0x6f, 0x00, 0x84, 0x00}, {0x75, 0x00, 0x80, 0x01},
3314 {0x79, 0x0b, 0xff, 0x00}, {0x75, 0x00, 0x85, 0x01}, {0x61, 0x00, 0x28, 0x01},
3315 {0x65, 0x00, 0x36, 0x01}, {0x67, 0x0c, 0x56, 0x01}, {0x69, 0x00, 0x2d, 0x01},
3316 {0x6f, 0x00, 0x38, 0x01}, {0x75, 0x00, 0x33, 0x01}, {0x77, 0x0d, 0xff, 0x00},
3317 {0x79, 0x0e, 0xff, 0x00}, {0x61, 0x00, 0x34, 0x01}, {0x61, 0x00, 0x2e, 0x01},
3318 {0x6f, 0x00, 0x30, 0x01}, {0x75, 0x00, 0x2f, 0x01}, {0x61, 0x00, 0x71, 0x01},
3319 {0x65, 0x00, 0x88, 0x01}, {0x68, 0x0f, 0x56, 0x01}, {0x69, 0x00, 0x74, 0x01},
3320 {0x6f, 0x00, 0x8b, 0x01}, {0x75, 0x00, 0x80, 0x01}, {0x79, 0x10, 0xff, 0x00},
3321 {0x61, 0x00, 0x75, 0x01}, {0x6f, 0x00, 0x77, 0x01}, {0x75, 0x00, 0x76, 0x01},
3322 {0x61, 0x00, 0x42, 0x00}, {0x65, 0x00, 0x41, 0x00}, {0x69, 0x00, 0x40, 0x01},
3323 {0x6a, 0x11, 0x56, 0x01}, {0x6f, 0x00, 0x44, 0x00}, {0x75, 0x00, 0x43, 0x00},
3324 {0x79, 0x12, 0xff, 0x00}, {0x61, 0x00, 0x42, 0x01}, {0x6f, 0x00, 0x44, 0x01},
3325 {0x75, 0x00, 0x43, 0x01}, {0x61, 0x00, 0x27, 0x01}, {0x65, 0x00, 0x35, 0x01},
3326 {0x69, 0x00, 0x29, 0x01}, {0x6b, 0x13, 0x56, 0x01}, {0x6f, 0x00, 0x37, 0x01},
3327 {0x75, 0x00, 0x31, 0x01}, {0x77, 0x14, 0xff, 0x00}, {0x79, 0x15, 0xff, 0x00},
3328 {0x61, 0x00, 0x32, 0x01}, {0x61, 0x00, 0x2a, 0x01}, {0x6f, 0x00, 0x2c, 0x01},
3329 {0x75, 0x00, 0x2b, 0x01}, {0x61, 0x00, 0x00, 0x01}, {0x65, 0x00, 0x23, 0x01},
3330 {0x69, 0x00, 0x02, 0x01}, {0x6b, 0x17, 0xff, 0x01}, {0x6c, 0x16, 0x56, 0x01},
3331 {0x6f, 0x00, 0x25, 0x01}, {0x74, 0x18, 0xff, 0x01}, {0x75, 0x00, 0x05, 0x01},
3332 {0x77, 0x1a, 0xff, 0x01}, {0x79, 0x1b, 0xff, 0x01}, {0x61, 0x00, 0xb0, 0x01},
3333 {0x65, 0x00, 0xb1, 0x01}, {0x73, 0x19, 0xff, 0x00}, {0x75, 0x00, 0x56, 0x01},
3334 {0x75, 0x00, 0x56, 0x01}, {0x61, 0x00, 0xa4, 0x01}, {0x61, 0x00, 0x96, 0x01},
3335 {0x65, 0x00, 0x23, 0x01}, {0x69, 0x00, 0x02, 0x01}, {0x6f, 0x00, 0x9a, 0x01},
3336 {0x75, 0x00, 0x98, 0x01}, {0x61, 0x00, 0x8e, 0x01}, {0x65, 0x00, 0x94, 0x01},
3337 {0x69, 0x00, 0x8f, 0x01}, {0x6d, 0x1c, 0x56, 0x01}, {0x6f, 0x00, 0x95, 0x01},
3338 {0x75, 0x00, 0x93, 0x01}, {0x79, 0x1d, 0xff, 0x00}, {0x61, 0x00, 0x90, 0x01},
3339 {0x6f, 0x00, 0x92, 0x01}, {0x75, 0x00, 0x91, 0x01}, {0x00, 0x00, 0xa9, 0x01},
3340 {0x27, 0x00, 0xa9, 0x00}, {0x2d, 0x00, 0xaa, 0x00}, {0x61, 0x00, 0x67, 0x01},
3341 {0x62, 0x01, 0xa9, 0x00}, {0x63, 0x03, 0xa9, 0x00}, {0x64, 0x06, 0xa9, 0x00},
3342 {0x65, 0x00, 0x6f, 0x01}, {0x66, 0x0a, 0xa9, 0x00}, {0x67, 0x0c, 0xa9, 0x00},
3343 {0x68, 0x0f, 0xa9, 0x00}, {0x69, 0x00, 0x68, 0x01}, {0x6a, 0x11, 0xa9, 0x00},
3344 {0x6b, 0x13, 0xa9, 0x00}, {0x6c, 0x16, 0xa9, 0x00}, {0x6d, 0x1c, 0xa9, 0x00},
3345 {0x6e, 0x00, 0xa9, 0x00}, {0x6f, 0x00, 0x70, 0x01}, {0x70, 0x20, 0xa9, 0x00},
3346 {0x72, 0x22, 0xa9, 0x00}, {0x73, 0x24, 0xa9, 0x00}, {0x74, 0x27, 0xa9, 0x00},
3347 {0x75, 0x00, 0x6e, 0x01}, {0x76, 0x2c, 0xa9, 0x00}, {0x77, 0x2d, 0xa9, 0x00},
3348 {0x78, 0x2f, 0xa9, 0x00}, {0x79, 0x1f, 0xff, 0x00}, {0x7a, 0x36, 0xa9, 0x00},
3349 {0xe3, 0x38, 0xa9, 0x00}, {0x00, 0x00, 0xa9, 0x01}, {0x61, 0x00, 0x6b, 0x01},
3350 {0x65, 0x00, 0x6a, 0x01}, {0x69, 0x00, 0x69, 0x01}, {0x6f, 0x00, 0x6d, 0x01},
3351 {0x75, 0x00, 0x6c, 0x01}, {0x61, 0x00, 0x73, 0x01}, {0x65, 0x00, 0x8a, 0x01},
3352 {0x69, 0x00, 0x7c, 0x01}, {0x6f, 0x00, 0x8d, 0x01}, {0x70, 0x20, 0x56, 0x01},
3353 {0x75, 0x00, 0x87, 0x01}, {0x79, 0x21, 0xff, 0x00}, {0x61, 0x00, 0x7d, 0x01},
3354 {0x6f, 0x00, 0x7f, 0x01}, {0x75, 0x00, 0x7e, 0x01}, {0x61, 0x00, 0x9c, 0x01},
3355 {0x65, 0x00, 0xa2, 0x01}, {0x69, 0x00, 0x9d, 0x01}, {0x6f, 0x00, 0xa3, 0x01},
3356 {0x72, 0x22, 0x56, 0x01}, {0x75, 0x00, 0xa1, 0x01}, {0x79, 0x23, 0xff, 0x00},
3357 {0x61, 0x00, 0x9e, 0x01}, {0x6f, 0x00, 0xa0, 0x01}, {0x75, 0x00, 0x9f, 0x01},
3358 {0x61, 0x00, 0x39, 0x01}, {0x65, 0x00, 0x47, 0x01}, {0x68, 0x25, 0xff, 0x00},
3359 {0x69, 0x00, 0x3b, 0x01}, {0x6f, 0x00, 0x49, 0x01}, {0x73, 0x24, 0x56, 0x01},
3360 {0x75, 0x00, 0x45, 0x01}, {0x79, 0x26, 0xff, 0x00}, {0x61, 0x00, 0x3d, 0x00},
3361 {0x65, 0x00, 0x3c, 0x00}, {0x69, 0x00, 0x3b, 0x01}, {0x6f, 0x00, 0x3f, 0x00},
3362 {0x75, 0x00, 0x3e, 0x00}, {0x61, 0x00, 0x3d, 0x01}, {0x65, 0x00, 0x3c, 0x01},
3363 {0x6f, 0x00, 0x3f, 0x01}, {0x75, 0x00, 0x3e, 0x01}, {0x61, 0x00, 0x4b, 0x01},
3364 {0x65, 0x00, 0x5d, 0x01}, {0x68, 0x28, 0xff, 0x00}, {0x69, 0x00, 0x4d, 0x01},
3365 {0x6f, 0x00, 0x63, 0x01}, {0x73, 0x29, 0xff, 0x00}, {0x74, 0x27, 0x56, 0x01},
3366 {0x75, 0x00, 0x57, 0x01}, {0x77, 0x2a, 0xff, 0x00}, {0x79, 0x2b, 0xff, 0x00},
3367 {0x69, 0x00, 0x5e, 0x01}, {0x75, 0x00, 0x5f, 0x01}, {0x61, 0x00, 0x58, 0x00},
3368 {0x65, 0x00, 0x5a, 0x00}, {0x69, 0x00, 0x59, 0x00}, {0x6f, 0x00, 0x5b, 0x00},
3369 {0x75, 0x00, 0x57, 0x01}, {0x75, 0x00, 0x64, 0x01}, {0x61, 0x00, 0x4f, 0x01},
3370 {0x65, 0x00, 0x4e, 0x01}, {0x6f, 0x00, 0x51, 0x01}, {0x75, 0x00, 0x50, 0x01},
3371 {0x61, 0x00, 0xac, 0x00}, {0x65, 0x00, 0xae, 0x00}, {0x69, 0x00, 0xad, 0x00},
3372 {0x6f, 0x00, 0xaf, 0x00}, {0x75, 0x00, 0xab, 0x01}, {0x76, 0x2c, 0x56, 0x01},
3373 {0x61, 0x00, 0xa5, 0x01}, {0x65, 0x00, 0x0b, 0x01}, {0x69, 0x00, 0x08, 0x01},
3374 {0x6f, 0x00, 0xa8, 0x01}, {0x77, 0x2d, 0x56, 0x01}, {0x79, 0x2e, 0xff, 0x01},
3375 {0x65, 0x00, 0xa7, 0x01}, {0x69, 0x00, 0xa6, 0x01}, {0x61, 0x00, 0x00, 0x01},
3376 {0x65, 0x00, 0x23, 0x01}, {0x69, 0x00, 0x02, 0x01}, {0x6b, 0x30, 0xff, 0x01},
3377 {0x6f, 0x00, 0x25, 0x01}, {0x74, 0x31, 0xff, 0x01}, {0x75, 0x00, 0x05, 0x01},
3378 {0x77, 0x33, 0xff, 0x01}, {0x78, 0x2f, 0x56, 0x01}, {0x79, 0x34, 0xff, 0x01},
3379 {0x61, 0x00, 0xb0, 0x01}, {0x65, 0x00, 0xb1, 0x01}, {0x73, 0x32, 0xff, 0x00},
3380 {0x75, 0x00, 0x56, 0x01}, {0x75, 0x00, 0x56, 0x01}, {0x61, 0x00, 0xa4, 0x01},
3381 {0x61, 0x00, 0x96, 0x01}, {0x65, 0x00, 0x23, 0x01}, {0x69, 0x00, 0x02, 0x01},
3382 {0x6f, 0x00, 0x9a, 0x01}, {0x75, 0x00, 0x98, 0x01}, {0x61, 0x00, 0x97, 0x01},
3383 {0x65, 0x00, 0x04, 0x01}, {0x6f, 0x00, 0x9b, 0x01}, {0x75, 0x00, 0x99, 0x01},
3384 {0x79, 0x35, 0x56, 0x01}, {0x61, 0x00, 0x3a, 0x01}, {0x65, 0x00, 0x48, 0x01},
3385 {0x69, 0x00, 0x40, 0x01}, {0x6f, 0x00, 0x4a, 0x01}, {0x75, 0x00, 0x46, 0x01},
3386 {0x79, 0x37, 0xff, 0x00}, {0x7a, 0x36, 0x56, 0x01}, {0x61, 0x00, 0x42, 0x01},
3387 {0x65, 0x00, 0x41, 0x01}, {0x6f, 0x00, 0x44, 0x01}, {0x75, 0x00, 0x43, 0x01},
3388 {0x81, 0x39, 0xff, 0x01}, {0x82, 0x3d, 0xff, 0x01}, {0x81, 0x00, 0x00, 0x01},
3389 {0x82, 0x00, 0x01, 0x01}, {0x83, 0x00, 0x02, 0x01}, {0x84, 0x00, 0x03, 0x01},
3390 {0x85, 0x00, 0x05, 0x01}, {0x86, 0x3a, 0xff, 0x01}, {0x87, 0x00, 0x23, 0x01},
3391 {0x88, 0x00, 0x24, 0x01}, {0x89, 0x00, 0x25, 0x01}, {0x8a, 0x00, 0x26, 0x01},
3392 {0x8b, 0x00, 0x27, 0x01}, {0x8c, 0x00, 0x28, 0x01}, {0x8d, 0x00, 0x29, 0x01},
3393 {0x8e, 0x00, 0x2d, 0x01}, {0x8f, 0x00, 0x31, 0x01}, {0x90, 0x00, 0x33, 0x01},
3394 {0x91, 0x00, 0x35, 0x01}, {0x92, 0x00, 0x36, 0x01}, {0x93, 0x00, 0x37, 0x01},
3395 {0x94, 0x00, 0x38, 0x01}, {0x95, 0x00, 0x39, 0x01}, {0x96, 0x00, 0x3a, 0x01},
3396 {0x97, 0x00, 0x3b, 0x01}, {0x98, 0x00, 0x40, 0x01}, {0x99, 0x00, 0x45, 0x01},
3397 {0x9a, 0x00, 0x46, 0x01}, {0x9b, 0x00, 0x47, 0x01}, {0x9c, 0x00, 0x48, 0x01},
3398 {0x9d, 0x00, 0x49, 0x01}, {0x9e, 0x00, 0x4a, 0x01}, {0x9f, 0x00, 0x4b, 0x01},
3399 {0xa0, 0x00, 0x4c, 0x01}, {0xa1, 0x00, 0x4d, 0x01}, {0xa2, 0x00, 0x52, 0x01},
3400 {0xa3, 0x00, 0x56, 0x01}, {0xa4, 0x00, 0x57, 0x01}, {0xa5, 0x00, 0x5c, 0x01},
3401 {0xa6, 0x00, 0x5d, 0x01}, {0xa7, 0x00, 0x60, 0x01}, {0xa8, 0x00, 0x63, 0x01},
3402 {0xa9, 0x00, 0x65, 0x01}, {0xaa, 0x00, 0x67, 0x01}, {0xab, 0x00, 0x68, 0x01},
3403 {0xac, 0x00, 0x6e, 0x01}, {0xad, 0x00, 0x6f, 0x01}, {0xae, 0x00, 0x70, 0x01},
3404 {0xaf, 0x00, 0x71, 0x01}, {0xb0, 0x00, 0x72, 0x01}, {0xb1, 0x00, 0x73, 0x01},
3405 {0xb2, 0x00, 0x74, 0x01}, {0xb3, 0x00, 0x78, 0x01}, {0xb4, 0x00, 0x7c, 0x01},
3406 {0xb5, 0x00, 0x80, 0x01}, {0xb6, 0x00, 0x86, 0x01}, {0xb7, 0x00, 0x87, 0x01},
3407 {0xb8, 0x00, 0x88, 0x01}, {0xb9, 0x00, 0x89, 0x01}, {0xba, 0x00, 0x8a, 0x01},
3408 {0xbb, 0x00, 0x8b, 0x01}, {0xbc, 0x00, 0x8c, 0x01}, {0xbd, 0x00, 0x8d, 0x01},
3409 {0xbe, 0x00, 0x8e, 0x01}, {0xbf, 0x00, 0x8f, 0x01}, {0x00, 0x00, 0x06, 0x00},
3410 {0x2d, 0x00, 0x22, 0x00}, {0x61, 0x00, 0x07, 0x00}, {0x62, 0x01, 0x06, 0x00},
3411 {0x63, 0x03, 0x06, 0x00}, {0x64, 0x06, 0x06, 0x00}, {0x65, 0x00, 0x0c, 0x00},
3412 {0x66, 0x0a, 0x06, 0x00}, {0x67, 0x0c, 0x06, 0x00}, {0x68, 0x0f, 0x06, 0x00},
3413 {0x69, 0x00, 0x09, 0x00}, {0x6a, 0x11, 0x06, 0x00}, {0x6b, 0x13, 0x06, 0x00},
3414 {0x6c, 0x16, 0x06, 0x00}, {0x6d, 0x1c, 0x06, 0x00}, {0x6e, 0x1e, 0x06, 0x00},
3415 {0x6f, 0x00, 0x0d, 0x00}, {0x70, 0x20, 0x06, 0x00}, {0x72, 0x22, 0x06, 0x00},
3416 {0x73, 0x24, 0x06, 0x00}, {0x74, 0x27, 0x06, 0x00}, {0x75, 0x00, 0x0a, 0x00},
3417 {0x76, 0x2c, 0x06, 0x00}, {0x77, 0x2d, 0x06, 0x00}, {0x78, 0x2f, 0x06, 0x00},
3418 {0x79, 0x35, 0x06, 0x00}, {0x7a, 0x36, 0x06, 0x00}, {0xe3, 0x3b, 0xff, 0x01},
3419 {0x00, 0x00, 0x06, 0x00}, {0x81, 0x39, 0x06, 0x00}, {0x82, 0x3c, 0xff, 0x01},
3420 {0x00, 0x00, 0x06, 0x01}, {0x80, 0x00, 0x0e, 0x00}, {0x81, 0x00, 0x0f, 0x00},
3421 {0x82, 0x00, 0x10, 0x00}, {0x83, 0x00, 0x11, 0x00}, {0x84, 0x00, 0x12, 0x00},
3422 {0x85, 0x00, 0x13, 0x00}, {0x86, 0x00, 0x14, 0x00}, {0x87, 0x00, 0x15, 0x00},
3423 {0x88, 0x00, 0x16, 0x00}, {0x89, 0x00, 0x17, 0x00}, {0x8a, 0x00, 0x18, 0x00},
3424 {0x8b, 0x00, 0x19, 0x00}, {0x8c, 0x00, 0x1a, 0x00}, {0x8d, 0x00, 0x1b, 0x00},
3425 {0x8e, 0x00, 0x1c, 0x00}, {0x8f, 0x00, 0x1d, 0x00}, {0x90, 0x00, 0x1e, 0x00},
3426 {0x91, 0x00, 0x1f, 0x00}, {0x92, 0x00, 0x20, 0x00}, {0x93, 0x00, 0x21, 0x00},
3427 {0x9b, 0x00, 0xab, 0x01}, {0x80, 0x00, 0x93, 0x01}, {0x81, 0x00, 0x94, 0x01},
3428 {0x82, 0x00, 0x95, 0x01}, {0x83, 0x00, 0x96, 0x01}, {0x84, 0x00, 0x97, 0x01},
3429 {0x85, 0x00, 0x98, 0x01}, {0x86, 0x00, 0x99, 0x01}, {0x87, 0x00, 0x9a, 0x01},
3430 {0x88, 0x00, 0x9b, 0x01}, {0x89, 0x00, 0x9c, 0x01}, {0x8a, 0x00, 0x9d, 0x01},
3431 {0x8b, 0x00, 0xa1, 0x01}, {0x8c, 0x00, 0xa2, 0x01}, {0x8d, 0x00, 0xa3, 0x01},
3432 {0x8e, 0x00, 0xa4, 0x01}, {0x8f, 0x00, 0xa5, 0x01}, {0x90, 0x00, 0xa6, 0x01},
3433 {0x91, 0x00, 0xa7, 0x01}, {0x92, 0x00, 0xa8, 0x01}, {0x93, 0x00, 0xa9, 0x01}
3434};
3435
3436static rk_tree_node *
3437rk_lookup(uint8_t state, uint8_t code)
3438{
3439 if (state < sizeof(rk_tree_idx)/sizeof(uint16_t)) {
3440 uint16_t ns = state ? rk_tree_idx[state - 1] : 0;
3441 uint16_t ne = rk_tree_idx[state];
3442 while (ns < ne) {
3443 uint16_t m = (ns + ne)>>1;
3444 rk_tree_node *rn = &rk_tree[m];
3445 if (rn->code == code) { return rn; }
3446 if (rn->code < code) {
3447 ns = m + 1;
3448 } else {
3449 ne = m;
3450 }
3451 }
3452 }
3453 return NULL;
3454}
3455
3456static uint32_t
3457rk_emit(rk_tree_node *rn, char **str)
3458{
3459 if (rn && rn->emit != 0xff) {
3460 uint16_t pos = rn->emit ? rk_str_idx[rn->emit - 1] : 0;
3461 *str = &rk_str[pos];
3462 return (uint32_t)(rk_str_idx[rn->emit] - pos);
3463 } else {
3464 *str = NULL;
3465 return 0;
3466 }
3467}
3468
3469#define RK_OUTPUT(e,l) do {\
3470 if (oc < oe) {\
3471 uint32_t l_ = (oc + (l) < oe) ? (l) : (oe - oc);\
3472 grn_memcpy(oc, (e), l_);\
3473 oc += l_;\
3474 ic_ = ic;\
3475 }\
3476} while (0)
3477
3478static uint32_t
3479rk_conv(const char *str, uint32_t str_len, uint8_t *buf, uint32_t buf_size, uint8_t *statep)
3480{
3481 uint32_t l;
3482 uint8_t state = 0;
3483 rk_tree_node *rn;
3484 char *e;
3485 uint8_t *oc = buf, *oe = oc + buf_size;
3486 const uint8_t *ic = (uint8_t *)str, *ic_ = ic, *ie = ic + str_len;
3487 while (ic < ie) {
3488 if ((rn = rk_lookup(state, *ic))) {
3489 ic++;
3490 if ((l = rk_emit(rn, &e))) { RK_OUTPUT(e, l); }
3491 state = rn->next;
3492 } else {
3493 if (!state) { ic++; }
3494 if (ic_ < ic) { RK_OUTPUT(ic_, ic - ic_); }
3495 state = 0;
3496 }
3497 }
3498#ifdef FLUSH_UNRESOLVED_INPUT
3499 if ((rn = rk_lookup(state, 0))) {
3500 if ((l = rk_emit(rn, &e))) { RK_OUTPUT(e, l); }
3501 state = rn->next;
3502 } else {
3503 if (ic_ < ic) { RK_OUTPUT(ic_, ic - ic_); }
3504 }
3505#endif /* FLUSH_UNRESOLVED_INPUT */
3506 *statep = state;
3507 return oc - buf;
3508}
3509
3510static grn_id
3511sub_search(grn_ctx *ctx, grn_pat *pat, grn_id id,
3512 int *c0, uint8_t *key, uint32_t key_len)
3513{
3514 pat_node *pn;
3515 uint32_t len = key_len * 16;
3516 if (!key_len) { return id; }
3517 PAT_AT(pat, id, pn);
3518 while (pn) {
3519 int ch;
3520 ch = PAT_CHK(pn);
3521 if (*c0 < ch && ch < len - 1) {
3522 if (ch & 1) {
3523 id = (ch + 1 < len) ? pn->lr[1] : pn->lr[0];
3524 } else {
3525 id = pn->lr[nth_bit(key, ch, len)];
3526 }
3527 *c0 = ch;
3528 PAT_AT(pat, id, pn);
3529 } else {
3530 const uint8_t *k = pat_node_get_key(ctx, pat, pn);
3531 return (k && key_len <= PAT_LEN(pn) && !memcmp(k, key, key_len)) ? id : GRN_ID_NIL;
3532 }
3533 }
3534 return GRN_ID_NIL;
3535}
3536
3537static void
3538search_push(grn_ctx *ctx, grn_pat *pat, grn_pat_cursor *c,
3539 uint8_t *key, uint32_t key_len, uint8_t state, grn_id id, int c0, int flags)
3540{
3541 if (state) {
3542 int step;
3543 uint16_t ns, ne;
3544 if (flags & GRN_CURSOR_DESCENDING) {
3545 ns = rk_tree_idx[state - 1];
3546 ne = rk_tree_idx[state];
3547 step = 1;
3548 } else {
3549 ns = rk_tree_idx[state] - 1;
3550 ne = rk_tree_idx[state - 1] - 1;
3551 step = -1;
3552 }
3553 for (; ns != ne; ns += step) {
3554 rk_tree_node *rn = &rk_tree[ns];
3555 if (rn->attr) {
3556 char *e;
3557 uint32_t l = rk_emit(rn, &e);
3558 if (l) {
3559 if (l + key_len <= GRN_TABLE_MAX_KEY_SIZE) {
3560 int ch = c0;
3561 grn_id i;
3562 grn_memcpy(key + key_len, e, l);
3563 if ((i = sub_search(ctx, pat, id, &ch, key, key_len + l))) {
3564 search_push(ctx, pat, c, key, key_len + l, rn->next, i, ch, flags);
3565 }
3566 }
3567 } else {
3568 search_push(ctx, pat, c, key, key_len, rn->next, id, c0, flags);
3569 }
3570 }
3571 }
3572 } else {
3573 pat_node *pn;
3574 PAT_AT(pat, id, pn);
3575 if (pn) {
3576 int ch = PAT_CHK(pn);
3577 uint32_t len = key_len * 16;
3578 if (c0 < ch) {
3579 if (flags & GRN_CURSOR_DESCENDING) {
3580 if ((ch > len - 1) || !(flags & GRN_CURSOR_GT)) { push(c, pn->lr[0], ch); }
3581 push(c, pn->lr[1], ch);
3582 } else {
3583 push(c, pn->lr[1], ch);
3584 if ((ch > len - 1) || !(flags & GRN_CURSOR_GT)) { push(c, pn->lr[0], ch); }
3585 }
3586 } else {
3587 if (PAT_LEN(pn) * 16 > len || !(flags & GRN_CURSOR_GT)) { push(c, id, ch); }
3588 }
3589 }
3590 }
3591}
3592
3593static grn_rc
3594set_cursor_rk(grn_ctx *ctx, grn_pat *pat, grn_pat_cursor *c,
3595 const void *key, uint32_t key_len, int flags)
3596{
3597 grn_id id;
3598 uint8_t state;
3599 pat_node *pn;
3600 int c0 = -1;
3601 uint32_t len, byte_len;
3602 uint8_t keybuf[GRN_TABLE_MAX_KEY_SIZE];
3603 if (flags & GRN_CURSOR_SIZE_BY_BIT) { return GRN_OPERATION_NOT_SUPPORTED; }
3604 byte_len = rk_conv(key, key_len, keybuf, GRN_TABLE_MAX_KEY_SIZE, &state);
3605 len = byte_len * 16;
3606 PAT_AT(pat, 0, pn);
3607 id = pn->lr[1];
3608 if ((id = sub_search(ctx, pat, id, &c0, keybuf, byte_len))) {
3609 search_push(ctx, pat, c, keybuf, byte_len, state, id, c0, flags);
3610 }
3611 return ctx->rc;
3612}
3613
3614uint32_t
3615grn_pat_total_key_size(grn_ctx *ctx, grn_pat *pat)
3616{
3617 return pat->header->curr_key;
3618}
3619
3620grn_bool
3621grn_pat_is_key_encoded(grn_ctx *ctx, grn_pat *pat)
3622{
3623 grn_obj *domain;
3624 uint32_t key_size;
3625
3626 domain = grn_ctx_at(ctx, pat->obj.header.domain);
3627 if (grn_obj_is_type(ctx, domain)) {
3628 key_size = grn_type_size(ctx, domain);
3629 } else {
3630 key_size = sizeof(grn_id);
3631 }
3632
3633 return KEY_NEEDS_CONVERT(pat, key_size);
3634}
3635
3636grn_rc
3637grn_pat_dirty(grn_ctx *ctx, grn_pat *pat)
3638{
3639 grn_rc rc = GRN_SUCCESS;
3640
3641 CRITICAL_SECTION_ENTER(pat->lock);
3642 if (!pat->is_dirty) {
3643 uint32_t n_dirty_opens;
3644 pat->is_dirty = GRN_TRUE;
3645 GRN_ATOMIC_ADD_EX(&(pat->header->n_dirty_opens), 1, n_dirty_opens);
3646 rc = grn_io_flush(ctx, pat->io);
3647 }
3648 CRITICAL_SECTION_LEAVE(pat->lock);
3649
3650 return rc;
3651}
3652
3653grn_bool
3654grn_pat_is_dirty(grn_ctx *ctx, grn_pat *pat)
3655{
3656 return pat->header->n_dirty_opens > 0;
3657}
3658
3659grn_rc
3660grn_pat_clean(grn_ctx *ctx, grn_pat *pat)
3661{
3662 grn_rc rc = GRN_SUCCESS;
3663
3664 CRITICAL_SECTION_ENTER(pat->lock);
3665 if (pat->is_dirty) {
3666 uint32_t n_dirty_opens;
3667 pat->is_dirty = GRN_FALSE;
3668 GRN_ATOMIC_ADD_EX(&(pat->header->n_dirty_opens), -1, n_dirty_opens);
3669 rc = grn_io_flush(ctx, pat->io);
3670 }
3671 CRITICAL_SECTION_LEAVE(pat->lock);
3672
3673 return rc;
3674}
3675
3676grn_rc
3677grn_pat_clear_dirty(grn_ctx *ctx, grn_pat *pat)
3678{
3679 grn_rc rc = GRN_SUCCESS;
3680
3681 CRITICAL_SECTION_ENTER(pat->lock);
3682 pat->is_dirty = GRN_FALSE;
3683 pat->header->n_dirty_opens = 0;
3684 rc = grn_io_flush(ctx, pat->io);
3685 CRITICAL_SECTION_LEAVE(pat->lock);
3686
3687 return rc;
3688}
3689