1 /* -*- c-basic-offset: 2 -*- */
2 /*
3 Copyright(C) 2009-2016 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-1335 USA
17 */
18 #include "grn_hash.h"
19 #include "grn_output.h"
20 #include <string.h>
21 #include <limits.h>
22
23 #include "grn_store.h"
24 #include "grn_normalizer.h"
25
26 /* grn_tiny_array */
27
28 /* Requirements: id != GRN_ID_NIL. */
29 inline static int
grn_tiny_array_get_block_id(grn_id id)30 grn_tiny_array_get_block_id(grn_id id)
31 {
32 int most_significant_one_bit_offset;
33 GRN_BIT_SCAN_REV(id, most_significant_one_bit_offset);
34 return most_significant_one_bit_offset >> GRN_TINY_ARRAY_FACTOR;
35 }
36
37 /* Requirements: id != GRN_ID_NIL. */
38 inline static void *
grn_tiny_array_get(grn_tiny_array * array,grn_id id)39 grn_tiny_array_get(grn_tiny_array *array, grn_id id) {
40 const int block_id = grn_tiny_array_get_block_id(id);
41 uint8_t * const block = (uint8_t *)array->blocks[block_id];
42 if (block) {
43 const size_t offset = GRN_TINY_ARRAY_GET_OFFSET(block_id);
44 return block + (id - offset) * array->element_size;
45 }
46 return NULL;
47 }
48
49 /* Requirements: id != GRN_ID_NIL. */
50 inline static void *
grn_tiny_array_put(grn_tiny_array * array,grn_id id)51 grn_tiny_array_put(grn_tiny_array *array, grn_id id) {
52 const int block_id = grn_tiny_array_get_block_id(id);
53 void ** const block = &array->blocks[block_id];
54 const size_t offset = GRN_TINY_ARRAY_GET_OFFSET(block_id);
55 if (!*block) {
56 grn_ctx * const ctx = array->ctx;
57 if (array->flags & GRN_TINY_ARRAY_THREADSAFE) {
58 CRITICAL_SECTION_ENTER(array->lock);
59 }
60 if (!*block) {
61 const size_t block_size =
62 GRN_TINY_ARRAY_GET_BLOCK_SIZE(block_id) * array->element_size;
63 if (array->flags & GRN_TINY_ARRAY_USE_MALLOC) {
64 if (array->flags & GRN_TINY_ARRAY_CLEAR) {
65 *block = GRN_CALLOC(block_size);
66 } else {
67 *block = GRN_MALLOC(block_size);
68 }
69 } else {
70 *block = GRN_CTX_ALLOC(ctx, block_size);
71 }
72 }
73 if (array->flags & GRN_TINY_ARRAY_THREADSAFE) {
74 CRITICAL_SECTION_LEAVE(array->lock);
75 }
76 if (!*block) {
77 return NULL;
78 }
79 }
80 if (id > array->max) {
81 array->max = id;
82 }
83 return (uint8_t *)*block + (id - offset) * array->element_size;
84 }
85
86 inline static void *
grn_tiny_array_at_inline(grn_tiny_array * array,grn_id id)87 grn_tiny_array_at_inline(grn_tiny_array *array, grn_id id)
88 {
89 return id ? grn_tiny_array_put(array, id) : NULL;
90 }
91
92 void
grn_tiny_array_init(grn_ctx * ctx,grn_tiny_array * array,uint16_t element_size,uint16_t flags)93 grn_tiny_array_init(grn_ctx *ctx, grn_tiny_array *array,
94 uint16_t element_size, uint16_t flags)
95 {
96 array->ctx = ctx;
97 array->max = 0;
98 array->element_size = element_size;
99 array->flags = flags;
100 memset(array->blocks, 0, sizeof(array->blocks));
101 if (flags & GRN_TINY_ARRAY_THREADSAFE) {
102 CRITICAL_SECTION_INIT(array->lock);
103 }
104 }
105
106 void
grn_tiny_array_fin(grn_tiny_array * array)107 grn_tiny_array_fin(grn_tiny_array *array)
108 {
109 int block_id;
110 grn_ctx * const ctx = array->ctx;
111 for (block_id = 0; block_id < GRN_TINY_ARRAY_NUM_BLOCKS; block_id++) {
112 if (array->blocks[block_id]) {
113 if (array->flags & GRN_TINY_ARRAY_USE_MALLOC) {
114 GRN_FREE(array->blocks[block_id]);
115 } else {
116 GRN_CTX_FREE(ctx, array->blocks[block_id]);
117 }
118 array->blocks[block_id] = NULL;
119 }
120 }
121 }
122
123 void *
grn_tiny_array_at(grn_tiny_array * array,grn_id id)124 grn_tiny_array_at(grn_tiny_array *array, grn_id id)
125 {
126 return grn_tiny_array_at_inline(array, id);
127 }
128
129 grn_id
grn_tiny_array_id(grn_tiny_array * array,const void * element_address)130 grn_tiny_array_id(grn_tiny_array *array, const void *element_address)
131 {
132 const uint8_t * const ptr = (const uint8_t *)element_address;
133 uint32_t block_id, offset = 1;
134 for (block_id = 0; block_id < GRN_TINY_ARRAY_NUM_BLOCKS; block_id++) {
135 const uint32_t block_size = GRN_TINY_ARRAY_GET_BLOCK_SIZE(block_id);
136 const uint8_t * const block = (const uint8_t *)array->blocks[block_id];
137 if (block) {
138 if (block <= ptr && ptr < (block + block_size * array->element_size)) {
139 return offset + ((ptr - block) / array->element_size);
140 }
141 }
142 offset += block_size;
143 }
144 return GRN_ID_NIL;
145 }
146
147 /* grn_tiny_bitmap */
148
149 static void
grn_tiny_bitmap_init(grn_ctx * ctx,grn_tiny_bitmap * bitmap)150 grn_tiny_bitmap_init(grn_ctx *ctx, grn_tiny_bitmap *bitmap)
151 {
152 bitmap->ctx = ctx;
153 memset(bitmap->blocks, 0, sizeof(bitmap->blocks));
154 }
155
156 static void
grn_tiny_bitmap_fin(grn_tiny_bitmap * bitmap)157 grn_tiny_bitmap_fin(grn_tiny_bitmap *bitmap)
158 {
159 int block_id;
160 grn_ctx * const ctx = bitmap->ctx;
161 for (block_id = 0; block_id < GRN_TINY_ARRAY_NUM_BLOCKS; block_id++) {
162 if (bitmap->blocks[block_id]) {
163 GRN_CTX_FREE(ctx, bitmap->blocks[block_id]);
164 bitmap->blocks[block_id] = NULL;
165 }
166 }
167 }
168
169 /* Requirements: bit_id != GRN_ID_NIL. */
170 inline static uint8_t *
grn_tiny_bitmap_get_byte(grn_tiny_bitmap * bitmap,grn_id bit_id)171 grn_tiny_bitmap_get_byte(grn_tiny_bitmap *bitmap, grn_id bit_id) {
172 const uint32_t byte_id = (bit_id >> 3) + 1;
173 const int block_id = grn_tiny_array_get_block_id(byte_id);
174 uint8_t * const block = (uint8_t *)bitmap->blocks[block_id];
175 if (block) {
176 const size_t offset = GRN_TINY_ARRAY_GET_OFFSET(block_id);
177 return block + byte_id - offset;
178 }
179 return NULL;
180 }
181
182 /* Requirements: bit_id != GRN_ID_NIL. */
183 inline static uint8_t *
grn_tiny_bitmap_put_byte(grn_tiny_bitmap * bitmap,grn_id bit_id)184 grn_tiny_bitmap_put_byte(grn_tiny_bitmap *bitmap, grn_id bit_id) {
185 const uint32_t byte_id = (bit_id >> 3) + 1;
186 const int block_id = grn_tiny_array_get_block_id(byte_id);
187 void ** const block = &bitmap->blocks[block_id];
188 const size_t offset = GRN_TINY_ARRAY_GET_OFFSET(block_id);
189 if (!*block) {
190 grn_ctx * const ctx = bitmap->ctx;
191 *block = GRN_CTX_ALLOC(ctx, GRN_TINY_ARRAY_GET_BLOCK_SIZE(block_id));
192 if (!*block) {
193 return NULL;
194 }
195 }
196 return (uint8_t *)*block + byte_id - offset;
197 }
198
199 /* Requirements: bit_id != GRN_ID_NIL. */
200 /* Return value: 1/0 on success, -1 on failure. */
201 /* Note: A bitmap is extended if needed. */
202 inline static int
grn_tiny_bitmap_put(grn_tiny_bitmap * bitmap,grn_id bit_id)203 grn_tiny_bitmap_put(grn_tiny_bitmap *bitmap, grn_id bit_id)
204 {
205 uint8_t * const ptr = grn_tiny_bitmap_put_byte(bitmap, bit_id);
206 return ptr ? ((*ptr >> (bit_id & 7)) & 1) : -1;
207 }
208
209 /* Requirements: bit_id != GRN_ID_NIL. */
210 inline static uint8_t *
grn_tiny_bitmap_get_and_set(grn_tiny_bitmap * bitmap,grn_id bit_id,grn_bool bit)211 grn_tiny_bitmap_get_and_set(grn_tiny_bitmap *bitmap, grn_id bit_id,
212 grn_bool bit)
213 {
214 uint8_t * const ptr = grn_tiny_bitmap_get_byte(bitmap, bit_id);
215 if (ptr) {
216 /* This branch will be removed because the given `bit' is constant. */
217 if (bit) {
218 *ptr |= 1 << (bit_id & 7);
219 } else {
220 *ptr &= ~(1 << (bit_id & 7));
221 }
222 }
223 return ptr;
224 }
225
226 /* Requirements: bit_id != GRN_ID_NIL. */
227 /* Note: A bitmap is extended if needed. */
228 inline static uint8_t *
grn_tiny_bitmap_put_and_set(grn_tiny_bitmap * bitmap,grn_id bit_id,grn_bool bit)229 grn_tiny_bitmap_put_and_set(grn_tiny_bitmap *bitmap, grn_id bit_id,
230 grn_bool bit)
231 {
232 uint8_t * const ptr = grn_tiny_bitmap_put_byte(bitmap, bit_id);
233 if (ptr) {
234 /* This branch will be removed because the given `bit' is constant. */
235 if (bit) {
236 *ptr |= 1 << (bit_id & 7);
237 } else {
238 *ptr &= ~(1 << (bit_id & 7));
239 }
240 }
241 return ptr;
242 }
243
244 /* grn_io_array */
245
246 #define GRN_ARRAY_MAX (GRN_ID_MAX - 8)
247
248 inline static void *
grn_io_array_at_inline(grn_ctx * ctx,grn_io * io,uint32_t segment_id,uint64_t offset,int flags)249 grn_io_array_at_inline(grn_ctx *ctx, grn_io *io, uint32_t segment_id,
250 uint64_t offset, int flags)
251 {
252 void *ptr;
253 GRN_IO_ARRAY_AT(io, segment_id, offset, &flags, ptr);
254 return ptr;
255 }
256
257 /*
258 * grn_io_array_bit_at() returns 1/0 on success, -1 on failure.
259 */
260 inline static int
grn_io_array_bit_at(grn_ctx * ctx,grn_io * io,uint32_t segment_id,uint32_t offset)261 grn_io_array_bit_at(grn_ctx *ctx, grn_io *io,
262 uint32_t segment_id, uint32_t offset)
263 {
264 uint8_t * const ptr = (uint8_t *)grn_io_array_at_inline(
265 ctx, io, segment_id, (offset >> 3) + 1, 0);
266 return ptr ? ((*ptr >> (offset & 7)) & 1) : -1;
267 }
268
269 /*
270 * The following functions, grn_io_array_bit_*(), return a non-NULL pointer on
271 * success, a NULL pointer on failure.
272 */
273 inline static void *
grn_io_array_bit_on(grn_ctx * ctx,grn_io * io,uint32_t segment_id,uint32_t offset)274 grn_io_array_bit_on(grn_ctx *ctx, grn_io *io,
275 uint32_t segment_id, uint32_t offset)
276 {
277 uint8_t * const ptr = (uint8_t *)grn_io_array_at_inline(
278 ctx, io, segment_id, (offset >> 3) + 1, GRN_TABLE_ADD);
279 if (ptr) {
280 *ptr |= 1 << (offset & 7);
281 }
282 return ptr;
283 }
284
285 inline static void *
grn_io_array_bit_off(grn_ctx * ctx,grn_io * io,uint32_t segment_id,uint32_t offset)286 grn_io_array_bit_off(grn_ctx *ctx, grn_io *io,
287 uint32_t segment_id, uint32_t offset)
288 {
289 uint8_t * const ptr = (uint8_t *)grn_io_array_at_inline(
290 ctx, io, segment_id, (offset >> 3) + 1, GRN_TABLE_ADD);
291 if (ptr) {
292 *ptr &= ~(1 << (offset & 7));
293 }
294 return ptr;
295 }
296
297 /* grn_table_queue */
298
299 static void
grn_table_queue_lock_init(grn_ctx * ctx,grn_table_queue * queue)300 grn_table_queue_lock_init(grn_ctx *ctx, grn_table_queue *queue)
301 {
302 MUTEX_INIT_SHARED(queue->mutex);
303 COND_INIT_SHARED(queue->cond);
304 }
305
306 static void
grn_table_queue_init(grn_ctx * ctx,grn_table_queue * queue)307 grn_table_queue_init(grn_ctx *ctx, grn_table_queue *queue)
308 {
309 queue->head = 0;
310 queue->tail = 0;
311 queue->cap = GRN_ARRAY_MAX;
312 queue->unblock_requested = GRN_FALSE;
313 grn_table_queue_lock_init(ctx, queue);
314 }
315
316 uint32_t
grn_table_queue_size(grn_table_queue * queue)317 grn_table_queue_size(grn_table_queue *queue)
318 {
319 return (queue->head < queue->tail)
320 ? 2 * queue->cap + queue->head - queue->tail
321 : queue->head - queue->tail;
322 }
323
324 void
grn_table_queue_head_increment(grn_table_queue * queue)325 grn_table_queue_head_increment(grn_table_queue *queue)
326 {
327 if (queue->head == 2 * queue->cap) {
328 queue->head = 1;
329 } else {
330 queue->head++;
331 }
332 }
333
334 void
grn_table_queue_tail_increment(grn_table_queue * queue)335 grn_table_queue_tail_increment(grn_table_queue *queue)
336 {
337 if (queue->tail == 2 * queue->cap) {
338 queue->tail = 1;
339 } else {
340 queue->tail++;
341 }
342 }
343
344 grn_id
grn_table_queue_head(grn_table_queue * queue)345 grn_table_queue_head(grn_table_queue *queue)
346 {
347 return queue->head > queue->cap
348 ? queue->head - queue->cap
349 : queue->head;
350 }
351
352 grn_id
grn_table_queue_tail(grn_table_queue * queue)353 grn_table_queue_tail(grn_table_queue *queue)
354 {
355 return queue->tail > queue->cap
356 ? queue->tail - queue->cap
357 : queue->tail;
358 }
359
360 /* grn_array */
361
362 #define GRN_ARRAY_SEGMENT_SIZE 0x400000
363
364 /* Header of grn_io-based grn_array. */
365 struct grn_array_header {
366 uint32_t flags;
367 uint32_t curr_rec;
368 uint32_t value_size;
369 uint32_t n_entries;
370 uint32_t n_garbages;
371 grn_id garbages;
372 uint32_t lock;
373 uint32_t truncated;
374 uint32_t reserved[8];
375 grn_table_queue queue;
376 };
377
378 /*
379 * A grn_io-based grn_array consists of the following 2 segments.
380 * GRN_ARRAY_VALUE_SEGMENT: stores values.
381 * GRN_ARRAY_BITMAP_SEGMENT: stores whether entries are valid or not.
382 */
383 enum {
384 GRN_ARRAY_VALUE_SEGMENT = 0,
385 GRN_ARRAY_BITMAP_SEGMENT = 1
386 };
387
388 inline static grn_bool
grn_array_is_io_array(grn_array * array)389 grn_array_is_io_array(grn_array *array)
390 {
391 return array->io != NULL;
392 }
393
394 inline static void *
grn_array_io_entry_at(grn_ctx * ctx,grn_array * array,grn_id id,int flags)395 grn_array_io_entry_at(grn_ctx *ctx, grn_array *array, grn_id id, int flags)
396 {
397 return grn_io_array_at_inline(ctx, array->io, GRN_ARRAY_VALUE_SEGMENT, id, flags);
398 }
399
400 inline static void *
grn_array_entry_at(grn_ctx * ctx,grn_array * array,grn_id id,int flags)401 grn_array_entry_at(grn_ctx *ctx, grn_array *array, grn_id id, int flags)
402 {
403 if (grn_array_is_io_array(array)) {
404 return grn_array_io_entry_at(ctx, array, id, flags);
405 } else {
406 return grn_tiny_array_at_inline(&array->array, id);
407 }
408 }
409
410 /* grn_array_bitmap_at() returns 1/0 on success, -1 on failure. */
411 inline static int
grn_array_bitmap_at(grn_ctx * ctx,grn_array * array,grn_id id)412 grn_array_bitmap_at(grn_ctx *ctx, grn_array *array, grn_id id)
413 {
414 if (grn_array_is_io_array(array)) {
415 return grn_io_array_bit_at(ctx, array->io, GRN_ARRAY_BITMAP_SEGMENT, id);
416 } else {
417 return grn_tiny_bitmap_put(&array->bitmap, id);
418 }
419 }
420
421 static grn_rc
grn_array_init_tiny_array(grn_ctx * ctx,grn_array * array,const char * path,uint32_t value_size,uint32_t flags)422 grn_array_init_tiny_array(grn_ctx *ctx, grn_array *array, const char *path,
423 uint32_t value_size, uint32_t flags)
424 {
425 if (path) {
426 ERR(GRN_INVALID_ARGUMENT, "failed to create tiny array");
427 return ctx->rc;
428 }
429 array->obj.header.flags = flags;
430 array->ctx = ctx;
431 array->value_size = value_size;
432 array->n_keys = 0;
433 array->keys = NULL;
434 array->n_garbages = &array->n_garbages_buf;
435 array->n_entries = &array->n_entries_buf;
436 array->n_garbages_buf = 0;
437 array->n_entries_buf = 0;
438 array->io = NULL;
439 array->header = NULL;
440 array->garbages = GRN_ID_NIL;
441 grn_tiny_array_init(ctx, &array->array, value_size, GRN_TINY_ARRAY_CLEAR);
442 grn_tiny_bitmap_init(ctx, &array->bitmap);
443 return GRN_SUCCESS;
444 }
445
446 static grn_io *
grn_array_create_io_array(grn_ctx * ctx,const char * path,uint32_t value_size)447 grn_array_create_io_array(grn_ctx *ctx, const char *path, uint32_t value_size)
448 {
449 uint32_t w_of_element = 0;
450 grn_io_array_spec array_spec[2];
451
452 while ((1U << w_of_element) < value_size) {
453 w_of_element++;
454 }
455
456 array_spec[GRN_ARRAY_VALUE_SEGMENT].w_of_element = w_of_element;
457 array_spec[GRN_ARRAY_VALUE_SEGMENT].max_n_segments =
458 1U << (30 - (22 - w_of_element));
459 array_spec[GRN_ARRAY_BITMAP_SEGMENT].w_of_element = 0;
460 array_spec[GRN_ARRAY_BITMAP_SEGMENT].max_n_segments = 1U << (30 - (22 + 3));
461 return grn_io_create_with_array(ctx, path, sizeof(struct grn_array_header),
462 GRN_ARRAY_SEGMENT_SIZE, grn_io_auto,
463 2, array_spec);
464 }
465
466 static grn_rc
grn_array_init_io_array(grn_ctx * ctx,grn_array * array,const char * path,uint32_t value_size,uint32_t flags)467 grn_array_init_io_array(grn_ctx *ctx, grn_array *array, const char *path,
468 uint32_t value_size, uint32_t flags)
469 {
470 grn_io *io;
471 struct grn_array_header *header;
472
473 io = grn_array_create_io_array(ctx, path, value_size);
474 if (!io) {
475 return ctx->rc;
476 }
477 grn_io_set_type(io, GRN_TABLE_NO_KEY);
478
479 header = grn_io_header(io);
480 header->flags = flags;
481 header->curr_rec = 0;
482 header->lock = 0;
483 header->value_size = value_size;
484 header->n_entries = 0;
485 header->n_garbages = 0;
486 header->garbages = GRN_ID_NIL;
487 header->truncated = GRN_FALSE;
488 grn_table_queue_init(ctx, &header->queue);
489 array->obj.header.flags = flags;
490 array->ctx = ctx;
491 array->value_size = value_size;
492 array->n_keys = 0;
493 array->keys = NULL;
494 array->n_garbages = &header->n_garbages;
495 array->n_entries = &header->n_entries;
496 array->io = io;
497 array->header = header;
498 array->lock = &header->lock;
499 return GRN_SUCCESS;
500 }
501
502 void
grn_array_queue_lock_clear(grn_ctx * ctx,grn_array * array)503 grn_array_queue_lock_clear(grn_ctx *ctx, grn_array *array)
504 {
505 struct grn_array_header *header;
506 header = grn_io_header(array->io);
507 grn_table_queue_lock_init(ctx, &header->queue);
508 }
509
510 grn_table_queue *
grn_array_queue(grn_ctx * ctx,grn_array * array)511 grn_array_queue(grn_ctx *ctx, grn_array *array)
512 {
513 if (grn_array_is_io_array(array)) {
514 struct grn_array_header *header;
515 header = grn_io_header(array->io);
516 return &header->queue;
517 } else {
518 return NULL;
519 }
520 }
521
522 static grn_rc
grn_array_init(grn_ctx * ctx,grn_array * array,const char * path,uint32_t value_size,uint32_t flags)523 grn_array_init(grn_ctx *ctx, grn_array *array,
524 const char *path, uint32_t value_size, uint32_t flags)
525 {
526 if (flags & GRN_ARRAY_TINY) {
527 return grn_array_init_tiny_array(ctx, array, path, value_size, flags);
528 } else {
529 return grn_array_init_io_array(ctx, array, path, value_size, flags);
530 }
531 }
532
533 grn_array *
grn_array_create(grn_ctx * ctx,const char * path,uint32_t value_size,uint32_t flags)534 grn_array_create(grn_ctx *ctx, const char *path, uint32_t value_size, uint32_t flags)
535 {
536 if (ctx) {
537 grn_array * const array = (grn_array *)GRN_CALLOC(sizeof(grn_array));
538 if (array) {
539 GRN_DB_OBJ_SET_TYPE(array, GRN_TABLE_NO_KEY);
540 if (!grn_array_init(ctx, array, path, value_size, flags)) {
541 return array;
542 }
543 GRN_FREE(array);
544 }
545 }
546 return NULL;
547 }
548
549 grn_array *
grn_array_open(grn_ctx * ctx,const char * path)550 grn_array_open(grn_ctx *ctx, const char *path)
551 {
552 if (ctx) {
553 grn_io * const io = grn_io_open(ctx, path, grn_io_auto);
554 if (io) {
555 struct grn_array_header * const header = grn_io_header(io);
556 uint32_t io_type = grn_io_get_type(io);
557 if (io_type == GRN_TABLE_NO_KEY) {
558 grn_array * const array = (grn_array *)GRN_MALLOC(sizeof(grn_array));
559 if (array) {
560 if (!(header->flags & GRN_ARRAY_TINY)) {
561 GRN_DB_OBJ_SET_TYPE(array, GRN_TABLE_NO_KEY);
562 array->obj.header.flags = header->flags;
563 array->ctx = ctx;
564 array->value_size = header->value_size;
565 array->n_keys = 0;
566 array->keys = NULL;
567 array->n_garbages = &header->n_garbages;
568 array->n_entries = &header->n_entries;
569 array->io = io;
570 array->header = header;
571 array->lock = &header->lock;
572 return array;
573 } else {
574 GRN_LOG(ctx, GRN_LOG_NOTICE, "invalid array flags. (%x)", header->flags);
575 }
576 GRN_FREE(array);
577 }
578 } else {
579 ERR(GRN_INVALID_FORMAT,
580 "[table][array] file type must be %#04x: <%#04x>",
581 GRN_TABLE_NO_KEY, io_type);
582 }
583 grn_io_close(ctx, io);
584 }
585 }
586 return NULL;
587 }
588
589 /*
590 * grn_array_error_if_truncated() logs an error and returns its error code if
591 * an array is truncated by another process.
592 * Otherwise, this function returns GRN_SUCCESS.
593 * Note that `ctx` and `array` must be valid.
594 *
595 * FIXME: An array should be reopened if possible.
596 */
597 static grn_rc
grn_array_error_if_truncated(grn_ctx * ctx,grn_array * array)598 grn_array_error_if_truncated(grn_ctx *ctx, grn_array *array)
599 {
600 if (array->header && array->header->truncated) {
601 ERR(GRN_FILE_CORRUPT,
602 "array is truncated, please unmap or reopen the database");
603 return GRN_FILE_CORRUPT;
604 }
605 return GRN_SUCCESS;
606 }
607
608 grn_rc
grn_array_close(grn_ctx * ctx,grn_array * array)609 grn_array_close(grn_ctx *ctx, grn_array *array)
610 {
611 grn_rc rc = GRN_SUCCESS;
612 if (!ctx || !array) { return GRN_INVALID_ARGUMENT; }
613 if (array->keys) { GRN_FREE(array->keys); }
614 if (grn_array_is_io_array(array)) {
615 rc = grn_io_close(ctx, array->io);
616 } else {
617 GRN_ASSERT(ctx == array->ctx);
618 grn_tiny_array_fin(&array->array);
619 grn_tiny_bitmap_fin(&array->bitmap);
620 }
621 GRN_FREE(array);
622 return rc;
623 }
624
625 grn_rc
grn_array_remove(grn_ctx * ctx,const char * path)626 grn_array_remove(grn_ctx *ctx, const char *path)
627 {
628 if (!ctx || !path) { return GRN_INVALID_ARGUMENT; }
629 return grn_io_remove(ctx, path);
630 }
631
632 uint32_t
grn_array_size(grn_ctx * ctx,grn_array * array)633 grn_array_size(grn_ctx *ctx, grn_array *array)
634 {
635 if (grn_array_error_if_truncated(ctx, array) != GRN_SUCCESS) {
636 return 0;
637 }
638 return *array->n_entries;
639 }
640
641 uint32_t
grn_array_get_flags(grn_ctx * ctx,grn_array * array)642 grn_array_get_flags(grn_ctx *ctx, grn_array *array)
643 {
644 return array->header->flags;
645 }
646
647 grn_rc
grn_array_truncate(grn_ctx * ctx,grn_array * array)648 grn_array_truncate(grn_ctx *ctx, grn_array *array)
649 {
650 grn_rc rc;
651 char *path = NULL;
652 uint32_t value_size, flags;
653
654 if (!ctx || !array) { return GRN_INVALID_ARGUMENT; }
655 rc = grn_array_error_if_truncated(ctx, array);
656 if (rc != GRN_SUCCESS) {
657 return rc;
658 }
659 if (grn_array_is_io_array(array)) {
660 const char * const io_path = grn_io_path(array->io);
661 if (io_path && *io_path) {
662 path = GRN_STRDUP(io_path);
663 if (!path) {
664 ERR(GRN_NO_MEMORY_AVAILABLE, "cannot duplicate path: <%s>", io_path);
665 return GRN_NO_MEMORY_AVAILABLE;
666 }
667 }
668 }
669 value_size = array->value_size;
670 flags = array->obj.header.flags;
671
672 if (grn_array_is_io_array(array)) {
673 if (path) {
674 /* Only an I/O array with a valid path uses the `truncated` flag. */
675 array->header->truncated = GRN_TRUE;
676 }
677 rc = grn_io_close(ctx, array->io);
678 if (!rc) {
679 array->io = NULL;
680 if (path) {
681 rc = grn_io_remove(ctx, path);
682 }
683 }
684 }
685 if (!rc) {
686 rc = grn_array_init(ctx, array, path, value_size, flags);
687 }
688 if (path) { GRN_FREE(path); }
689 return rc;
690 }
691
692 inline static grn_id
grn_array_get_max_id(grn_array * array)693 grn_array_get_max_id(grn_array *array)
694 {
695 return grn_array_is_io_array(array) ? array->header->curr_rec : array->array.max;
696 }
697
698 inline static void *
grn_array_get_value_inline(grn_ctx * ctx,grn_array * array,grn_id id)699 grn_array_get_value_inline(grn_ctx *ctx, grn_array *array, grn_id id)
700 {
701 if (!ctx || !array) {
702 return NULL;
703 }
704 if (grn_array_error_if_truncated(ctx, array) != GRN_SUCCESS) {
705 return NULL;
706 }
707 if (*array->n_garbages) {
708 /*
709 * grn_array_bitmap_at() is a time-consuming function, so it is called only
710 * when there are garbages in the array.
711 */
712 if (grn_array_bitmap_at(ctx, array, id) != 1) {
713 return NULL;
714 }
715 } else if (id == 0 || id > grn_array_get_max_id(array)) {
716 return NULL;
717 }
718 return grn_array_entry_at(ctx, array, id, 0);
719 }
720
721 int
grn_array_get_value(grn_ctx * ctx,grn_array * array,grn_id id,void * valuebuf)722 grn_array_get_value(grn_ctx *ctx, grn_array *array, grn_id id, void *valuebuf)
723 {
724 void * const value = grn_array_get_value_inline(ctx, array, id);
725 if (value) {
726 if (valuebuf) {
727 grn_memcpy(valuebuf, value, array->value_size);
728 }
729 return array->value_size;
730 }
731 return 0;
732 }
733
734 void *
_grn_array_get_value(grn_ctx * ctx,grn_array * array,grn_id id)735 _grn_array_get_value(grn_ctx *ctx, grn_array *array, grn_id id)
736 {
737 return grn_array_get_value_inline(ctx, array, id);
738 }
739
740 inline static grn_rc
grn_array_set_value_inline(grn_ctx * ctx,grn_array * array,grn_id id,const void * value,int flags)741 grn_array_set_value_inline(grn_ctx *ctx, grn_array *array, grn_id id,
742 const void *value, int flags)
743 {
744 void *entry;
745 entry = grn_array_entry_at(ctx, array, id, 0);
746 if (!entry) {
747 return GRN_NO_MEMORY_AVAILABLE;
748 }
749
750 switch ((flags & GRN_OBJ_SET_MASK)) {
751 case GRN_OBJ_SET :
752 grn_memcpy(entry, value, array->value_size);
753 return GRN_SUCCESS;
754 case GRN_OBJ_INCR :
755 switch (array->value_size) {
756 case sizeof(int32_t) :
757 *((int32_t *)entry) += *((int32_t *)value);
758 return GRN_SUCCESS;
759 case sizeof(int64_t) :
760 *((int64_t *)entry) += *((int64_t *)value);
761 return GRN_SUCCESS;
762 default :
763 return GRN_INVALID_ARGUMENT;
764 }
765 break;
766 case GRN_OBJ_DECR :
767 switch (array->value_size) {
768 case sizeof(int32_t) :
769 *((int32_t *)entry) -= *((int32_t *)value);
770 return GRN_SUCCESS;
771 case sizeof(int64_t) :
772 *((int64_t *)entry) -= *((int64_t *)value);
773 return GRN_SUCCESS;
774 default :
775 return GRN_INVALID_ARGUMENT;
776 }
777 break;
778 default :
779 /* todo : support other types. */
780 return GRN_INVALID_ARGUMENT;
781 }
782 }
783
784 grn_rc
grn_array_set_value(grn_ctx * ctx,grn_array * array,grn_id id,const void * value,int flags)785 grn_array_set_value(grn_ctx *ctx, grn_array *array, grn_id id,
786 const void *value, int flags)
787 {
788 grn_rc rc;
789
790 if (!ctx || !array || !value) {
791 return GRN_INVALID_ARGUMENT;
792 }
793
794 rc = grn_array_error_if_truncated(ctx, array);
795 if (rc != GRN_SUCCESS) {
796 return rc;
797 }
798 if (*array->n_garbages) {
799 /*
800 * grn_array_bitmap_at() is a time-consuming function, so it is called only
801 * when there are garbages in the array.
802 */
803 if (grn_array_bitmap_at(ctx, array, id) != 1) {
804 return GRN_INVALID_ARGUMENT;
805 }
806 } else if (id == 0 || id > grn_array_get_max_id(array)) {
807 return GRN_INVALID_ARGUMENT;
808 }
809 return grn_array_set_value_inline(ctx, array, id, value, flags);
810 }
811
812 grn_rc
grn_array_delete_by_id(grn_ctx * ctx,grn_array * array,grn_id id,grn_table_delete_optarg * optarg)813 grn_array_delete_by_id(grn_ctx *ctx, grn_array *array, grn_id id,
814 grn_table_delete_optarg *optarg)
815 {
816 grn_rc rc;
817 if (!ctx || !array) {
818 return GRN_INVALID_ARGUMENT;
819 }
820 rc = grn_array_error_if_truncated(ctx, array);
821 if (rc != GRN_SUCCESS) {
822 return rc;
823 }
824 if (grn_array_bitmap_at(ctx, array, id) != 1) {
825 return GRN_INVALID_ARGUMENT;
826 }
827
828 {
829 rc = GRN_SUCCESS;
830 /* lock */
831 if (grn_array_is_io_array(array)) {
832 if (array->value_size >= sizeof(grn_id)) {
833 struct grn_array_header * const header = array->header;
834 void * const entry = grn_array_io_entry_at(ctx, array, id, 0);
835 if (!entry) {
836 rc = GRN_INVALID_ARGUMENT;
837 } else {
838 *((grn_id *)entry) = header->garbages;
839 header->garbages = id;
840 }
841 }
842 if (!rc) {
843 (*array->n_entries)--;
844 (*array->n_garbages)++;
845 /*
846 * The following grn_io_array_bit_off() fails iff a problem has
847 * occurred after the above grn_array_bitmap_at(). That is to say,
848 * an unexpected case.
849 */
850 grn_io_array_bit_off(ctx, array->io, GRN_ARRAY_BITMAP_SEGMENT, id);
851 }
852 } else {
853 if (array->value_size >= sizeof(grn_id)) {
854 void * const entry = grn_tiny_array_get(&array->array, id);
855 if (!entry) {
856 rc = GRN_INVALID_ARGUMENT;
857 } else {
858 *((grn_id *)entry) = array->garbages;
859 array->garbages = id;
860 }
861 }
862 if (!rc) {
863 (*array->n_entries)--;
864 (*array->n_garbages)++;
865 /*
866 * The following grn_io_array_bit_off() fails iff a problem has
867 * occurred after the above grn_array_bitmap_at(). That is to say,
868 * an unexpected case.
869 */
870 grn_tiny_bitmap_get_and_set(&array->bitmap, id, 0);
871 }
872 }
873 /* unlock */
874 return rc;
875 }
876 }
877
878 grn_id
grn_array_at(grn_ctx * ctx,grn_array * array,grn_id id)879 grn_array_at(grn_ctx *ctx, grn_array *array, grn_id id)
880 {
881 if (grn_array_error_if_truncated(ctx, array) != GRN_SUCCESS) {
882 return GRN_ID_NIL;
883 }
884 if (*array->n_garbages) {
885 /*
886 * grn_array_bitmap_at() is a time-consuming function, so it is called only
887 * when there are garbages in the array.
888 */
889 if (grn_array_bitmap_at(ctx, array, id) != 1) {
890 return GRN_ID_NIL;
891 }
892 } else if (id > grn_array_get_max_id(array)) {
893 return GRN_ID_NIL;
894 }
895 return id;
896 }
897
898 grn_rc
grn_array_copy_sort_key(grn_ctx * ctx,grn_array * array,grn_table_sort_key * keys,int n_keys)899 grn_array_copy_sort_key(grn_ctx *ctx, grn_array *array,
900 grn_table_sort_key *keys, int n_keys)
901 {
902 array->keys = (grn_table_sort_key *)GRN_MALLOCN(grn_table_sort_key, n_keys);
903 if (!array->keys) {
904 return ctx->rc;
905 }
906 grn_memcpy(array->keys, keys, sizeof(grn_table_sort_key) * n_keys);
907 array->n_keys = n_keys;
908 return GRN_SUCCESS;
909 }
910
911 void
grn_array_cursor_close(grn_ctx * ctx,grn_array_cursor * cursor)912 grn_array_cursor_close(grn_ctx *ctx, grn_array_cursor *cursor)
913 {
914 GRN_ASSERT(cursor->ctx == ctx);
915 GRN_FREE(cursor);
916 }
917
918 grn_array_cursor *
grn_array_cursor_open(grn_ctx * ctx,grn_array * array,grn_id min,grn_id max,int offset,int limit,int flags)919 grn_array_cursor_open(grn_ctx *ctx, grn_array *array, grn_id min, grn_id max,
920 int offset, int limit, int flags)
921 {
922 grn_array_cursor *cursor;
923 if (!array || !ctx) { return NULL; }
924 if (grn_array_error_if_truncated(ctx, array) != GRN_SUCCESS) {
925 return NULL;
926 }
927
928 cursor = (grn_array_cursor *)GRN_MALLOCN(grn_array_cursor, 1);
929 if (!cursor) { return NULL; }
930
931 GRN_DB_OBJ_SET_TYPE(cursor, GRN_CURSOR_TABLE_NO_KEY);
932 cursor->array = array;
933 cursor->ctx = ctx;
934 cursor->obj.header.flags = flags;
935 cursor->obj.header.domain = GRN_ID_NIL;
936
937 if (flags & GRN_CURSOR_DESCENDING) {
938 cursor->dir = -1;
939 if (max) {
940 cursor->curr_rec = max;
941 if (!(flags & GRN_CURSOR_LT)) { cursor->curr_rec++; }
942 } else {
943 cursor->curr_rec = grn_array_get_max_id(array) + 1;
944 }
945 if (min) {
946 cursor->tail = min;
947 if ((flags & GRN_CURSOR_GT)) { cursor->tail++; }
948 } else {
949 cursor->tail = GRN_ID_NIL + 1;
950 }
951 if (cursor->curr_rec < cursor->tail) { cursor->tail = cursor->curr_rec; }
952 } else {
953 cursor->dir = 1;
954 if (min) {
955 cursor->curr_rec = min;
956 if (!(flags & GRN_CURSOR_GT)) { cursor->curr_rec--; }
957 } else {
958 cursor->curr_rec = GRN_ID_NIL;
959 }
960 if (max) {
961 cursor->tail = max;
962 if ((flags & GRN_CURSOR_LT)) { cursor->tail--; }
963 } else {
964 cursor->tail = grn_array_get_max_id(array);
965 }
966 if (cursor->tail < cursor->curr_rec) { cursor->tail = cursor->curr_rec; }
967 }
968
969 if (*array->n_garbages) {
970 while (offset && cursor->curr_rec != cursor->tail) {
971 cursor->curr_rec += cursor->dir;
972 if (grn_array_bitmap_at(ctx, cursor->array, cursor->curr_rec) == 1) {
973 offset--;
974 }
975 }
976 } else {
977 cursor->curr_rec += cursor->dir * offset;
978 }
979 cursor->rest = (limit < 0) ? GRN_ARRAY_MAX : limit;
980 return cursor;
981 }
982
983 grn_id
grn_array_cursor_next(grn_ctx * ctx,grn_array_cursor * cursor)984 grn_array_cursor_next(grn_ctx *ctx, grn_array_cursor *cursor)
985 {
986 if (cursor && cursor->rest) {
987 while (cursor->curr_rec != cursor->tail) {
988 cursor->curr_rec += cursor->dir;
989 if (*cursor->array->n_garbages) {
990 if (grn_array_bitmap_at(ctx, cursor->array, cursor->curr_rec) != 1) {
991 continue;
992 }
993 }
994 cursor->rest--;
995 return cursor->curr_rec;
996 }
997 }
998 return GRN_ID_NIL;
999 }
1000
1001 grn_id
grn_array_next(grn_ctx * ctx,grn_array * array,grn_id id)1002 grn_array_next(grn_ctx *ctx, grn_array *array, grn_id id)
1003 {
1004 grn_id max_id;
1005 if (grn_array_error_if_truncated(ctx, array) != GRN_SUCCESS) {
1006 return GRN_ID_NIL;
1007 }
1008 max_id = grn_array_get_max_id(array);
1009 while (++id <= max_id) {
1010 if (!*array->n_garbages ||
1011 grn_array_bitmap_at(ctx, array, id) == 1) {
1012 return id;
1013 }
1014 }
1015 return GRN_ID_NIL;
1016 }
1017
1018 int
grn_array_cursor_get_value(grn_ctx * ctx,grn_array_cursor * cursor,void ** value)1019 grn_array_cursor_get_value(grn_ctx *ctx, grn_array_cursor *cursor, void **value)
1020 {
1021 if (cursor && value) {
1022 void * const entry = grn_array_entry_at(ctx, cursor->array, cursor->curr_rec, 0);
1023 if (entry) {
1024 *value = entry;
1025 return cursor->array->value_size;
1026 }
1027 }
1028 return 0;
1029 }
1030
1031 grn_rc
grn_array_cursor_set_value(grn_ctx * ctx,grn_array_cursor * cursor,const void * value,int flags)1032 grn_array_cursor_set_value(grn_ctx *ctx, grn_array_cursor *cursor,
1033 const void *value, int flags)
1034 {
1035 return grn_array_set_value_inline(ctx, cursor->array, cursor->curr_rec,
1036 value, flags);
1037 }
1038
1039 grn_rc
grn_array_cursor_delete(grn_ctx * ctx,grn_array_cursor * cursor,grn_table_delete_optarg * optarg)1040 grn_array_cursor_delete(grn_ctx *ctx, grn_array_cursor *cursor,
1041 grn_table_delete_optarg *optarg)
1042 {
1043 return grn_array_delete_by_id(ctx, cursor->array, cursor->curr_rec, optarg);
1044 }
1045
1046 inline static grn_id
grn_array_add_to_tiny_array(grn_ctx * ctx,grn_array * array,void ** value)1047 grn_array_add_to_tiny_array(grn_ctx *ctx, grn_array *array, void **value)
1048 {
1049 grn_id id = array->garbages;
1050 void *entry;
1051 if (id) {
1052 /* These operations fail iff the array is broken. */
1053 entry = grn_tiny_array_get(&array->array, id);
1054 if (!entry) {
1055 return GRN_ID_NIL;
1056 }
1057 array->garbages = *(grn_id *)entry;
1058 memset(entry, 0, array->value_size);
1059 (*array->n_garbages)--;
1060 if (!grn_tiny_bitmap_get_and_set(&array->bitmap, id, 1)) {
1061 /* Actually, it is difficult to recover from this error. */
1062 *(grn_id *)entry = array->garbages;
1063 array->garbages = id;
1064 (*array->n_garbages)++;
1065 return GRN_ID_NIL;
1066 }
1067 } else {
1068 id = array->array.max + 1;
1069 if (!grn_tiny_bitmap_put_and_set(&array->bitmap, id, 1)) {
1070 return GRN_ID_NIL;
1071 }
1072 entry = grn_tiny_array_put(&array->array, id);
1073 if (!entry) {
1074 grn_tiny_bitmap_get_and_set(&array->bitmap, id, 0);
1075 return GRN_ID_NIL;
1076 }
1077 array->array.max = id;
1078 }
1079 (*array->n_entries)++;
1080 if (value) { *value = entry; }
1081 return id;
1082 }
1083
1084 inline static grn_id
grn_array_add_to_io_array(grn_ctx * ctx,grn_array * array,void ** value)1085 grn_array_add_to_io_array(grn_ctx *ctx, grn_array *array, void **value)
1086 {
1087 grn_id id;
1088 void *entry;
1089 struct grn_array_header *header;
1090 if (grn_array_error_if_truncated(ctx, array) != GRN_SUCCESS) {
1091 return GRN_ID_NIL;
1092 }
1093 header = array->header;
1094 id = header->garbages;
1095 if (id) {
1096 /* These operations fail iff the array is broken. */
1097 entry = grn_array_io_entry_at(ctx, array, id, GRN_TABLE_ADD);
1098 if (!entry) {
1099 return GRN_ID_NIL;
1100 }
1101 header->garbages = *(grn_id *)entry;
1102 memset(entry, 0, header->value_size);
1103 (*array->n_garbages)--;
1104 if (!grn_io_array_bit_on(ctx, array->io, GRN_ARRAY_BITMAP_SEGMENT, id)) {
1105 /* Actually, it is difficult to recover from this error. */
1106 *(grn_id *)entry = array->garbages;
1107 array->garbages = id;
1108 (*array->n_garbages)++;
1109 return GRN_ID_NIL;
1110 }
1111 } else {
1112 if (header->curr_rec >= GRN_ARRAY_MAX) { return GRN_ID_NIL; }
1113 id = header->curr_rec + 1;
1114 if (!grn_io_array_bit_on(ctx, array->io, GRN_ARRAY_BITMAP_SEGMENT, id)) {
1115 return GRN_ID_NIL;
1116 }
1117 entry = grn_array_io_entry_at(ctx, array, id, GRN_TABLE_ADD);
1118 if (!entry) {
1119 grn_io_array_bit_off(ctx, array->io, GRN_ARRAY_BITMAP_SEGMENT, id);
1120 return GRN_ID_NIL;
1121 }
1122 header->curr_rec = id;
1123 }
1124 (*array->n_entries)++;
1125 if (value) { *value = entry; }
1126 return id;
1127 }
1128
1129 void
grn_array_clear_curr_rec(grn_ctx * ctx,grn_array * array)1130 grn_array_clear_curr_rec(grn_ctx *ctx, grn_array *array)
1131 {
1132 struct grn_array_header * const header = array->header;
1133 header->curr_rec = GRN_ID_NIL;
1134 }
1135
1136 grn_id
grn_array_add(grn_ctx * ctx,grn_array * array,void ** value)1137 grn_array_add(grn_ctx *ctx, grn_array *array, void **value)
1138 {
1139 if (ctx && array) {
1140 if (grn_array_is_io_array(array)) {
1141 return grn_array_add_to_io_array(ctx, array, value);
1142 } else {
1143 return grn_array_add_to_tiny_array(ctx, array, value);
1144 }
1145 }
1146 return GRN_ID_NIL;
1147 }
1148
1149 grn_id
grn_array_push(grn_ctx * ctx,grn_array * array,void (* func)(grn_ctx *,grn_array *,grn_id,void *),void * func_arg)1150 grn_array_push(grn_ctx *ctx, grn_array *array,
1151 void (*func)(grn_ctx *, grn_array *, grn_id, void *),
1152 void *func_arg)
1153 {
1154 grn_id id = GRN_ID_NIL;
1155 grn_table_queue *queue = grn_array_queue(ctx, array);
1156 if (queue) {
1157 MUTEX_LOCK(queue->mutex);
1158 if (grn_table_queue_head(queue) == queue->cap) {
1159 grn_array_clear_curr_rec(ctx, array);
1160 }
1161 id = grn_array_add(ctx, array, NULL);
1162 if (func) {
1163 func(ctx, array, id, func_arg);
1164 }
1165 if (grn_table_queue_size(queue) == queue->cap) {
1166 grn_table_queue_tail_increment(queue);
1167 }
1168 grn_table_queue_head_increment(queue);
1169 COND_SIGNAL(queue->cond);
1170 MUTEX_UNLOCK(queue->mutex);
1171 } else {
1172 ERR(GRN_OPERATION_NOT_SUPPORTED, "only persistent arrays support push");
1173 }
1174 return id;
1175 }
1176
1177 grn_id
grn_array_pull(grn_ctx * ctx,grn_array * array,grn_bool blockp,void (* func)(grn_ctx *,grn_array *,grn_id,void *),void * func_arg)1178 grn_array_pull(grn_ctx *ctx, grn_array *array, grn_bool blockp,
1179 void (*func)(grn_ctx *, grn_array *, grn_id, void *),
1180 void *func_arg)
1181 {
1182 grn_id id = GRN_ID_NIL;
1183 grn_table_queue *queue = grn_array_queue(ctx, array);
1184 if (queue) {
1185 MUTEX_LOCK(queue->mutex);
1186 queue->unblock_requested = GRN_FALSE;
1187 while (grn_table_queue_size(queue) == 0) {
1188 if (!blockp || queue->unblock_requested) {
1189 MUTEX_UNLOCK(queue->mutex);
1190 GRN_OUTPUT_BOOL(0);
1191 return id;
1192 }
1193 COND_WAIT(queue->cond, queue->mutex);
1194 }
1195 grn_table_queue_tail_increment(queue);
1196 id = grn_table_queue_tail(queue);
1197 if (func) {
1198 func(ctx, array, id, func_arg);
1199 }
1200 MUTEX_UNLOCK(queue->mutex);
1201 } else {
1202 ERR(GRN_OPERATION_NOT_SUPPORTED, "only persistent arrays support pull");
1203 }
1204 return id;
1205 }
1206
1207 void
grn_array_unblock(grn_ctx * ctx,grn_array * array)1208 grn_array_unblock(grn_ctx *ctx, grn_array *array)
1209 {
1210 grn_table_queue *queue = grn_array_queue(ctx, array);
1211 if (!queue) {
1212 return;
1213 }
1214
1215 queue->unblock_requested = GRN_TRUE;
1216 COND_BROADCAST(queue->cond);
1217 }
1218
1219 /* grn_hash : hash table */
1220
1221 #define GRN_HASH_MAX_SEGMENT 0x400
1222 #define GRN_HASH_HEADER_SIZE_NORMAL 0x9000
1223 #define GRN_HASH_HEADER_SIZE_LARGE\
1224 (GRN_HASH_HEADER_SIZE_NORMAL +\
1225 (sizeof(grn_id) *\
1226 (GRN_HASH_MAX_KEY_SIZE_LARGE - GRN_HASH_MAX_KEY_SIZE_NORMAL)))
1227 #define GRN_HASH_SEGMENT_SIZE 0x400000
1228 #define GRN_HASH_KEY_MAX_N_SEGMENTS_NORMAL 0x400
1229 #define GRN_HASH_KEY_MAX_N_SEGMENTS_LARGE 0x40000
1230 #define W_OF_KEY_IN_A_SEGMENT 22
1231 #define GRN_HASH_KEY_MAX_TOTAL_SIZE_NORMAL\
1232 (((uint64_t)(1) << W_OF_KEY_IN_A_SEGMENT) *\
1233 GRN_HASH_KEY_MAX_N_SEGMENTS_NORMAL - 1)
1234 #define GRN_HASH_KEY_MAX_TOTAL_SIZE_LARGE\
1235 (((uint64_t)(1) << W_OF_KEY_IN_A_SEGMENT) *\
1236 GRN_HASH_KEY_MAX_N_SEGMENTS_LARGE - 1)
1237 #define IDX_MASK_IN_A_SEGMENT 0xfffff
1238
1239 typedef struct {
1240 uint8_t key[4];
1241 uint8_t value[1];
1242 } grn_plain_hash_entry;
1243
1244 typedef struct {
1245 uint32_t hash_value;
1246 uint8_t key_and_value[1];
1247 } grn_rich_hash_entry;
1248
1249 typedef struct {
1250 uint32_t hash_value;
1251 uint16_t flag;
1252 uint16_t key_size;
1253 union {
1254 uint8_t buf[sizeof(uint32_t)];
1255 uint32_t offset;
1256 } key;
1257 uint8_t value[1];
1258 } grn_io_hash_entry_normal;
1259
1260 typedef struct {
1261 uint32_t hash_value;
1262 uint16_t flag;
1263 uint16_t key_size;
1264 union {
1265 uint8_t buf[sizeof(uint64_t)];
1266 uint64_t offset;
1267 } key;
1268 uint8_t value[1];
1269 } grn_io_hash_entry_large;
1270
1271 typedef struct {
1272 uint32_t hash_value;
1273 uint16_t flag;
1274 uint16_t key_size;
1275 union {
1276 uint8_t buf[sizeof(void *)];
1277 void *ptr;
1278 } key;
1279 uint8_t value[1];
1280 } grn_tiny_hash_entry;
1281
1282 /*
1283 * hash_value is valid even if the entry is grn_plain_hash_entry. In this case,
1284 * its hash_value equals its key.
1285 * flag, key_size and key.buf are valid if the entry has a variable length key.
1286 */
1287 typedef struct {
1288 uint32_t hash_value;
1289 uint16_t flag;
1290 uint16_t key_size;
1291 } grn_hash_entry_header;
1292
1293 typedef union {
1294 uint32_t hash_value;
1295 grn_hash_entry_header header;
1296 grn_plain_hash_entry plain_entry;
1297 grn_rich_hash_entry rich_entry;
1298 grn_io_hash_entry_normal io_entry_normal;
1299 grn_io_hash_entry_large io_entry_large;
1300 grn_tiny_hash_entry tiny_entry;
1301 } grn_hash_entry;
1302
1303 typedef struct {
1304 uint32_t key;
1305 uint8_t dummy[1];
1306 } entry;
1307
1308 typedef struct {
1309 uint32_t key;
1310 uint16_t flag;
1311 uint16_t size;
1312 uint32_t str;
1313 uint8_t dummy[1];
1314 } entry_str;
1315
1316 typedef struct {
1317 uint32_t key;
1318 uint16_t flag;
1319 uint16_t size;
1320 char *str;
1321 uint8_t dummy[1];
1322 } entry_astr;
1323
1324 enum {
1325 GRN_HASH_KEY_SEGMENT = 0,
1326 GRN_HASH_ENTRY_SEGMENT = 1,
1327 GRN_HASH_INDEX_SEGMENT = 2,
1328 GRN_HASH_BITMAP_SEGMENT = 3
1329 };
1330
1331 inline static int
grn_hash_name(grn_ctx * ctx,grn_hash * hash,char * buffer,int buffer_size)1332 grn_hash_name(grn_ctx *ctx, grn_hash *hash, char *buffer, int buffer_size)
1333 {
1334 int name_size;
1335
1336 if (DB_OBJ(hash)->id == GRN_ID_NIL) {
1337 grn_strcpy(buffer, buffer_size, "(anonymous)");
1338 name_size = strlen(buffer);
1339 } else {
1340 name_size = grn_obj_name(ctx, (grn_obj *)hash, buffer, buffer_size);
1341 }
1342
1343 return name_size;
1344 }
1345
1346 inline static grn_bool
grn_hash_is_io_hash(grn_hash * hash)1347 grn_hash_is_io_hash(grn_hash *hash)
1348 {
1349 return hash->io != NULL;
1350 }
1351
1352 inline static void *
grn_io_hash_entry_at(grn_ctx * ctx,grn_hash * hash,grn_id id,int flags)1353 grn_io_hash_entry_at(grn_ctx *ctx, grn_hash *hash, grn_id id, int flags)
1354 {
1355 return grn_io_array_at_inline(ctx, hash->io, GRN_HASH_ENTRY_SEGMENT, id, flags);
1356 }
1357
1358 /* todo : error handling */
1359 inline static void *
grn_hash_entry_at(grn_ctx * ctx,grn_hash * hash,grn_id id,int flags)1360 grn_hash_entry_at(grn_ctx *ctx, grn_hash *hash, grn_id id, int flags)
1361 {
1362 if (grn_hash_is_io_hash(hash)) {
1363 return grn_io_hash_entry_at(ctx, hash, id, flags);
1364 } else {
1365 return grn_tiny_array_at_inline(&hash->a, id);
1366 }
1367 }
1368
1369 inline static grn_bool
grn_hash_bitmap_at(grn_ctx * ctx,grn_hash * hash,grn_id id)1370 grn_hash_bitmap_at(grn_ctx *ctx, grn_hash *hash, grn_id id)
1371 {
1372 if (grn_hash_is_io_hash(hash)) {
1373 return grn_io_array_bit_at(ctx, hash->io, GRN_HASH_BITMAP_SEGMENT, id) == 1;
1374 } else {
1375 return grn_tiny_bitmap_put(&hash->bitmap, id) == 1;
1376 }
1377 }
1378
1379 inline static grn_id *
grn_io_hash_idx_at(grn_ctx * ctx,grn_hash * hash,grn_id id)1380 grn_io_hash_idx_at(grn_ctx *ctx, grn_hash *hash, grn_id id)
1381 {
1382 return grn_io_array_at_inline(ctx, hash->io, GRN_HASH_INDEX_SEGMENT,
1383 id, GRN_TABLE_ADD);
1384 }
1385
1386 inline static grn_id *
grn_hash_idx_at(grn_ctx * ctx,grn_hash * hash,grn_id id)1387 grn_hash_idx_at(grn_ctx *ctx, grn_hash *hash, grn_id id)
1388 {
1389 if (grn_hash_is_io_hash(hash)) {
1390 id = (id & *hash->max_offset) + hash->header.common->idx_offset;
1391 return grn_io_hash_idx_at(ctx, hash, id);
1392 } else {
1393 return hash->index + (id & *hash->max_offset);
1394 }
1395 }
1396
1397 inline static void *
grn_io_hash_key_at(grn_ctx * ctx,grn_hash * hash,uint64_t pos)1398 grn_io_hash_key_at(grn_ctx *ctx, grn_hash *hash, uint64_t pos)
1399 {
1400 return grn_io_array_at_inline(ctx, hash->io, GRN_HASH_KEY_SEGMENT,
1401 pos, GRN_TABLE_ADD);
1402 }
1403
1404 #define HASH_IMMEDIATE 1
1405
1406 #define MAX_INDEX_SIZE ((GRN_HASH_MAX_SEGMENT * (IDX_MASK_IN_A_SEGMENT + 1)) >> 1)
1407
1408 inline static uint16_t
grn_hash_entry_get_key_size(grn_hash * hash,grn_hash_entry * entry)1409 grn_hash_entry_get_key_size(grn_hash *hash, grn_hash_entry *entry)
1410 {
1411 if (hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) {
1412 return entry->header.key_size;
1413 } else {
1414 return hash->key_size;
1415 }
1416 }
1417
1418 inline static char *
grn_hash_entry_get_key(grn_ctx * ctx,grn_hash * hash,grn_hash_entry * entry)1419 grn_hash_entry_get_key(grn_ctx *ctx, grn_hash *hash, grn_hash_entry *entry)
1420 {
1421 if (hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) {
1422 if (grn_hash_is_io_hash(hash)) {
1423 if (grn_hash_is_large_total_key_size(ctx, hash)) {
1424 if (entry->io_entry_large.flag & HASH_IMMEDIATE) {
1425 return (char *)entry->io_entry_large.key.buf;
1426 } else {
1427 return (char *)grn_io_hash_key_at(ctx, hash,
1428 entry->io_entry_large.key.offset);
1429 }
1430 } else {
1431 if (entry->io_entry_normal.flag & HASH_IMMEDIATE) {
1432 return (char *)entry->io_entry_normal.key.buf;
1433 } else {
1434 return (char *)grn_io_hash_key_at(ctx, hash,
1435 entry->io_entry_normal.key.offset);
1436 }
1437 }
1438 } else {
1439 if (entry->tiny_entry.flag & HASH_IMMEDIATE) {
1440 return (char *)entry->tiny_entry.key.buf;
1441 } else {
1442 return entry->tiny_entry.key.ptr;
1443 }
1444 }
1445 } else {
1446 if (hash->key_size == sizeof(uint32_t)) {
1447 return (char *)entry->plain_entry.key;
1448 } else {
1449 return (char *)entry->rich_entry.key_and_value;
1450 }
1451 }
1452 }
1453
1454 inline static void *
grn_hash_entry_get_value(grn_ctx * ctx,grn_hash * hash,grn_hash_entry * entry)1455 grn_hash_entry_get_value(grn_ctx *ctx, grn_hash *hash, grn_hash_entry *entry)
1456 {
1457 if (hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) {
1458 if (grn_hash_is_io_hash(hash)) {
1459 if (grn_hash_is_large_total_key_size(ctx, hash)) {
1460 return entry->io_entry_large.value;
1461 } else {
1462 return entry->io_entry_normal.value;
1463 }
1464 } else {
1465 return entry->tiny_entry.value;
1466 }
1467 } else {
1468 if (hash->key_size == sizeof(uint32_t)) {
1469 return entry->plain_entry.value;
1470 } else {
1471 return entry->rich_entry.key_and_value + hash->key_size;
1472 }
1473 }
1474 }
1475
1476 inline static grn_rc
grn_io_hash_entry_put_key(grn_ctx * ctx,grn_hash * hash,grn_hash_entry * entry,const void * key,unsigned int key_size)1477 grn_io_hash_entry_put_key(grn_ctx *ctx, grn_hash *hash,
1478 grn_hash_entry *entry,
1479 const void *key, unsigned int key_size)
1480 {
1481 grn_bool is_large_mode;
1482 grn_bool key_exist;
1483 uint64_t key_offset;
1484 grn_io_hash_entry_normal *io_entry_normal = &(entry->io_entry_normal);
1485 grn_io_hash_entry_large *io_entry_large = &(entry->io_entry_large);
1486
1487 is_large_mode = grn_hash_is_large_total_key_size(ctx, hash);
1488
1489 if (is_large_mode) {
1490 key_exist = (io_entry_large->key_size > 0);
1491 } else {
1492 key_exist = (io_entry_normal->key_size > 0);
1493 }
1494
1495 if (key_exist > 0) {
1496 if (is_large_mode) {
1497 key_offset = io_entry_large->key.offset;
1498 } else {
1499 key_offset = io_entry_normal->key.offset;
1500 }
1501 } else {
1502 uint64_t segment_id;
1503 grn_hash_header_common *header;
1504 uint64_t curr_key;
1505 uint64_t max_total_size;
1506
1507 header = hash->header.common;
1508 if (key_size >= GRN_HASH_SEGMENT_SIZE) {
1509 char name[GRN_TABLE_MAX_KEY_SIZE];
1510 int name_size;
1511 name_size = grn_hash_name(ctx, hash, name, GRN_TABLE_MAX_KEY_SIZE);
1512 ERR(GRN_INVALID_ARGUMENT,
1513 "[hash][key][put] too long key: <%.*s>: max=%u: key size=%u",
1514 name_size, name,
1515 GRN_HASH_SEGMENT_SIZE,
1516 key_size);
1517 return ctx->rc;
1518 }
1519
1520 if (is_large_mode) {
1521 curr_key = header->curr_key_large;
1522 max_total_size = GRN_HASH_KEY_MAX_TOTAL_SIZE_LARGE;
1523 } else {
1524 curr_key = header->curr_key_normal;
1525 max_total_size = GRN_HASH_KEY_MAX_TOTAL_SIZE_NORMAL;
1526 }
1527
1528 if (key_size > (max_total_size - curr_key)) {
1529 char name[GRN_TABLE_MAX_KEY_SIZE];
1530 int name_size;
1531 name_size = grn_hash_name(ctx, hash, name, GRN_TABLE_MAX_KEY_SIZE);
1532 ERR(GRN_NOT_ENOUGH_SPACE,
1533 "[hash][key][put] total key size is over: <%.*s>: "
1534 "max=%" GRN_FMT_INT64U ": "
1535 "current=%" GRN_FMT_INT64U ": "
1536 "new key size=%u",
1537 name_size, name,
1538 max_total_size,
1539 curr_key,
1540 key_size);
1541 return ctx->rc;
1542 }
1543 key_offset = curr_key;
1544 segment_id = (key_offset + key_size) >> W_OF_KEY_IN_A_SEGMENT;
1545 if ((key_offset >> W_OF_KEY_IN_A_SEGMENT) != segment_id) {
1546 key_offset = segment_id << W_OF_KEY_IN_A_SEGMENT;
1547 if (is_large_mode) {
1548 header->curr_key_large = key_offset;
1549 } else {
1550 header->curr_key_normal = key_offset;
1551 }
1552 }
1553 if (is_large_mode) {
1554 header->curr_key_large += key_size;
1555 io_entry_large->key.offset = key_offset;
1556 } else {
1557 header->curr_key_normal += key_size;
1558 io_entry_normal->key.offset = key_offset;
1559 }
1560 }
1561
1562 {
1563 void * const key_ptr = grn_io_hash_key_at(ctx, hash, key_offset);
1564 if (!key_ptr) {
1565 char name[GRN_TABLE_MAX_KEY_SIZE];
1566 int name_size;
1567 name_size = grn_hash_name(ctx, hash, name, GRN_TABLE_MAX_KEY_SIZE);
1568 ERR(GRN_NO_MEMORY_AVAILABLE,
1569 "[hash][key][put] failed to allocate for new key: <%.*s>: "
1570 "new offset:%" GRN_FMT_INT64U " "
1571 "key size:%u",
1572 name_size, name,
1573 key_offset,
1574 key_size);
1575 return ctx->rc;
1576 }
1577 grn_memcpy(key_ptr, key, key_size);
1578 }
1579 return GRN_SUCCESS;
1580 }
1581
1582 inline static grn_rc
grn_hash_entry_put_key(grn_ctx * ctx,grn_hash * hash,grn_hash_entry * entry,uint32_t hash_value,const void * key,unsigned int key_size)1583 grn_hash_entry_put_key(grn_ctx *ctx, grn_hash *hash,
1584 grn_hash_entry *entry, uint32_t hash_value,
1585 const void *key, unsigned int key_size)
1586 {
1587 if (hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) {
1588 if (grn_hash_is_io_hash(hash)) {
1589 grn_bool is_large_mode;
1590 uint8_t *buffer;
1591 size_t buffer_size;
1592 uint16_t flag;
1593
1594 is_large_mode = grn_hash_is_large_total_key_size(ctx, hash);
1595 if (is_large_mode) {
1596 buffer = entry->io_entry_large.key.buf;
1597 buffer_size = sizeof(entry->io_entry_large.key.buf);
1598 } else {
1599 buffer = entry->io_entry_normal.key.buf;
1600 buffer_size = sizeof(entry->io_entry_normal.key.buf);
1601 }
1602
1603 if (key_size <= buffer_size) {
1604 grn_memcpy(buffer, key, key_size);
1605 flag = HASH_IMMEDIATE;
1606 } else {
1607 const grn_rc rc =
1608 grn_io_hash_entry_put_key(ctx, hash, entry, key, key_size);
1609 if (rc) {
1610 return rc;
1611 }
1612 flag = 0;
1613 }
1614
1615 if (is_large_mode) {
1616 entry->io_entry_large.flag = flag;
1617 entry->io_entry_large.hash_value = hash_value;
1618 entry->io_entry_large.key_size = key_size;
1619 } else {
1620 entry->io_entry_normal.flag = flag;
1621 entry->io_entry_normal.hash_value = hash_value;
1622 entry->io_entry_normal.key_size = key_size;
1623 }
1624 } else {
1625 if (key_size <= sizeof(entry->tiny_entry.key.buf)) {
1626 grn_memcpy(entry->tiny_entry.key.buf, key, key_size);
1627 entry->tiny_entry.flag = HASH_IMMEDIATE;
1628 } else {
1629 grn_ctx * const ctx = hash->ctx;
1630 entry->tiny_entry.key.ptr = GRN_CTX_ALLOC(ctx, key_size);
1631 if (!entry->tiny_entry.key.ptr) {
1632 return GRN_NO_MEMORY_AVAILABLE;
1633 }
1634 grn_memcpy(entry->tiny_entry.key.ptr, key, key_size);
1635 entry->tiny_entry.flag = 0;
1636 }
1637 entry->tiny_entry.hash_value = hash_value;
1638 entry->tiny_entry.key_size = key_size;
1639 }
1640 } else {
1641 if (hash->key_size == sizeof(uint32_t)) {
1642 *(uint32_t *)entry->plain_entry.key = hash_value;
1643 } else {
1644 entry->rich_entry.hash_value = hash_value;
1645 grn_memcpy(entry->rich_entry.key_and_value, key, key_size);
1646 }
1647 }
1648 return GRN_SUCCESS;
1649 }
1650
1651 /*
1652 * grn_hash_entry_compare_key() returns GRN_TRUE if the entry key equals the
1653 * specified key, or GRN_FALSE otherwise.
1654 */
1655 inline static grn_bool
grn_hash_entry_compare_key(grn_ctx * ctx,grn_hash * hash,grn_hash_entry * entry,uint32_t hash_value,const void * key,unsigned int key_size)1656 grn_hash_entry_compare_key(grn_ctx *ctx, grn_hash *hash,
1657 grn_hash_entry *entry, uint32_t hash_value,
1658 const void *key, unsigned int key_size)
1659 {
1660 if (hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) {
1661 if (entry->hash_value != hash_value ||
1662 entry->header.key_size != key_size) {
1663 return GRN_FALSE;
1664 }
1665 if (grn_hash_is_io_hash(hash)) {
1666 if (grn_hash_is_large_total_key_size(ctx, hash)) {
1667 if (entry->io_entry_large.flag & HASH_IMMEDIATE) {
1668 return !memcmp(key, entry->io_entry_large.key.buf, key_size);
1669 } else {
1670 const void * const entry_key_ptr =
1671 grn_io_hash_key_at(ctx, hash, entry->io_entry_large.key.offset);
1672 return !memcmp(key, entry_key_ptr, key_size);
1673 }
1674 } else {
1675 if (entry->io_entry_normal.flag & HASH_IMMEDIATE) {
1676 return !memcmp(key, entry->io_entry_normal.key.buf, key_size);
1677 } else {
1678 const void * const entry_key_ptr =
1679 grn_io_hash_key_at(ctx, hash, entry->io_entry_normal.key.offset);
1680 return !memcmp(key, entry_key_ptr, key_size);
1681 }
1682 }
1683 } else {
1684 if (entry->tiny_entry.flag & HASH_IMMEDIATE) {
1685 return !memcmp(key, entry->tiny_entry.key.buf, key_size);
1686 } else {
1687 return !memcmp(key, entry->tiny_entry.key.ptr, key_size);
1688 }
1689 }
1690 } else {
1691 if (entry->hash_value != hash_value) {
1692 return GRN_FALSE;
1693 }
1694 if (key_size == sizeof(uint32_t)) {
1695 return GRN_TRUE;
1696 } else {
1697 return !memcmp(key, entry->rich_entry.key_and_value, key_size);
1698 }
1699 }
1700 }
1701
1702 inline static char *
get_key(grn_ctx * ctx,grn_hash * hash,entry_str * n)1703 get_key(grn_ctx *ctx, grn_hash *hash, entry_str *n)
1704 {
1705 return grn_hash_entry_get_key(ctx, hash, (grn_hash_entry *)n);
1706 }
1707
1708 inline static void *
get_value(grn_ctx * ctx,grn_hash * hash,entry_str * n)1709 get_value(grn_ctx *ctx, grn_hash *hash, entry_str *n)
1710 {
1711 return grn_hash_entry_get_value(ctx, hash, (grn_hash_entry *)n);
1712 }
1713
1714 inline static int
match_key(grn_ctx * ctx,grn_hash * hash,entry_str * ee,uint32_t h,const char * key,unsigned int len)1715 match_key(grn_ctx *ctx, grn_hash *hash, entry_str *ee, uint32_t h,
1716 const char *key, unsigned int len)
1717 {
1718 return grn_hash_entry_compare_key(ctx, hash, (grn_hash_entry *)ee,
1719 h, key, len);
1720 }
1721
1722 #define GARBAGE (0xffffffff)
1723
1724 inline static uint32_t
grn_io_hash_calculate_entry_size(uint32_t key_size,uint32_t value_size,uint32_t flags)1725 grn_io_hash_calculate_entry_size(uint32_t key_size, uint32_t value_size,
1726 uint32_t flags)
1727 {
1728 if (flags & GRN_OBJ_KEY_VAR_SIZE) {
1729 if (flags & GRN_OBJ_KEY_LARGE) {
1730 return (uintptr_t)((grn_io_hash_entry_large *)0)->value + value_size;
1731 } else {
1732 return (uintptr_t)((grn_io_hash_entry_normal *)0)->value + value_size;
1733 }
1734 } else {
1735 if (key_size == sizeof(uint32_t)) {
1736 return (uintptr_t)((grn_plain_hash_entry *)0)->value + value_size;
1737 } else {
1738 return (uintptr_t)((grn_rich_hash_entry *)0)->key_and_value
1739 + key_size + value_size;
1740 }
1741 }
1742 }
1743
1744 static grn_io *
grn_io_hash_create_io(grn_ctx * ctx,const char * path,uint32_t header_size,uint32_t entry_size,uint32_t flags)1745 grn_io_hash_create_io(grn_ctx *ctx, const char *path,
1746 uint32_t header_size, uint32_t entry_size,
1747 uint32_t flags)
1748 {
1749 uint32_t w_of_element = 0;
1750 grn_io_array_spec array_spec[4];
1751
1752 while ((1U << w_of_element) < entry_size) {
1753 w_of_element++;
1754 }
1755
1756 array_spec[GRN_HASH_KEY_SEGMENT].w_of_element = 0;
1757 if (flags & GRN_OBJ_KEY_LARGE) {
1758 array_spec[GRN_HASH_KEY_SEGMENT].max_n_segments =
1759 GRN_HASH_KEY_MAX_N_SEGMENTS_LARGE;
1760 } else {
1761 array_spec[GRN_HASH_KEY_SEGMENT].max_n_segments =
1762 GRN_HASH_KEY_MAX_N_SEGMENTS_NORMAL;
1763 }
1764 array_spec[GRN_HASH_ENTRY_SEGMENT].w_of_element = w_of_element;
1765 array_spec[GRN_HASH_ENTRY_SEGMENT].max_n_segments =
1766 1U << (30 - (22 - w_of_element));
1767 array_spec[GRN_HASH_INDEX_SEGMENT].w_of_element = 2;
1768 array_spec[GRN_HASH_INDEX_SEGMENT].max_n_segments = 1U << (30 - (22 - 2));
1769 array_spec[GRN_HASH_BITMAP_SEGMENT].w_of_element = 0;
1770 array_spec[GRN_HASH_BITMAP_SEGMENT].max_n_segments = 1U << (30 - (22 + 3));
1771 return grn_io_create_with_array(ctx, path, header_size,
1772 GRN_HASH_SEGMENT_SIZE,
1773 grn_io_auto, 4, array_spec);
1774 }
1775
1776 static grn_rc
grn_io_hash_init(grn_ctx * ctx,grn_hash * hash,const char * path,uint32_t key_size,uint32_t value_size,uint32_t flags,grn_encoding encoding,uint32_t init_size)1777 grn_io_hash_init(grn_ctx *ctx, grn_hash *hash, const char *path,
1778 uint32_t key_size, uint32_t value_size, uint32_t flags,
1779 grn_encoding encoding, uint32_t init_size)
1780 {
1781 grn_io *io;
1782 grn_hash_header_common *header;
1783 uint32_t header_size, entry_size, max_offset;
1784
1785 if (key_size <= GRN_HASH_MAX_KEY_SIZE_NORMAL) {
1786 header_size = GRN_HASH_HEADER_SIZE_NORMAL;
1787 } else {
1788 header_size = GRN_HASH_HEADER_SIZE_LARGE;
1789 }
1790 entry_size = grn_io_hash_calculate_entry_size(key_size, value_size, flags);
1791
1792 io = grn_io_hash_create_io(ctx, path, header_size, entry_size, flags);
1793 if (!io) {
1794 return GRN_NO_MEMORY_AVAILABLE;
1795 }
1796 grn_io_set_type(io, GRN_TABLE_HASH_KEY);
1797
1798 max_offset = IDX_MASK_IN_A_SEGMENT + 1;
1799 while (max_offset < init_size * 2) {
1800 max_offset *= 2;
1801 }
1802 max_offset--;
1803
1804 if (encoding == GRN_ENC_DEFAULT) {
1805 encoding = ctx->encoding;
1806 }
1807
1808 hash->key_size = key_size;
1809
1810 header = grn_io_header(io);
1811 header->flags = flags;
1812 header->encoding = encoding;
1813 header->key_size = key_size;
1814 header->curr_rec = 0;
1815 header->curr_key_normal = 0;
1816 header->curr_key_large = 0;
1817 header->lock = 0;
1818 header->idx_offset = 0;
1819 header->value_size = value_size;
1820 header->entry_size = entry_size;
1821 header->max_offset = max_offset;
1822 header->n_entries = 0;
1823 header->n_garbages = 0;
1824 header->tokenizer = GRN_ID_NIL;
1825 if (header->flags & GRN_OBJ_KEY_NORMALIZE) {
1826 header->flags &= ~GRN_OBJ_KEY_NORMALIZE;
1827 hash->normalizer = grn_ctx_get(ctx, GRN_NORMALIZER_AUTO_NAME, -1);
1828 header->normalizer = grn_obj_id(ctx, hash->normalizer);
1829 } else {
1830 hash->normalizer = NULL;
1831 header->normalizer = GRN_ID_NIL;
1832 }
1833 header->truncated = GRN_FALSE;
1834 GRN_PTR_INIT(&(hash->token_filters), GRN_OBJ_VECTOR, GRN_ID_NIL);
1835 {
1836 grn_table_queue *queue;
1837 if (GRN_HASH_IS_LARGE_KEY(hash)) {
1838 queue = &(((grn_hash_header_large *)(header))->queue);
1839 } else {
1840 queue = &(((grn_hash_header_normal *)(header))->queue);
1841 }
1842 grn_table_queue_init(ctx, queue);
1843 }
1844
1845 hash->obj.header.flags = (header->flags & GRN_OBJ_FLAGS_MASK);
1846 hash->ctx = ctx;
1847 hash->encoding = encoding;
1848 hash->value_size = value_size;
1849 hash->entry_size = entry_size;
1850 hash->n_garbages = &header->n_garbages;
1851 hash->n_entries = &header->n_entries;
1852 hash->max_offset = &header->max_offset;
1853 hash->io = io;
1854 hash->header.common = header;
1855 hash->lock = &header->lock;
1856 hash->tokenizer = NULL;
1857 return GRN_SUCCESS;
1858 }
1859
1860 #define INITIAL_INDEX_SIZE 256U
1861
1862 static uint32_t
grn_tiny_hash_calculate_entry_size(uint32_t key_size,uint32_t value_size,uint32_t flags)1863 grn_tiny_hash_calculate_entry_size(uint32_t key_size, uint32_t value_size,
1864 uint32_t flags)
1865 {
1866 uint32_t entry_size;
1867 if (flags & GRN_OBJ_KEY_VAR_SIZE) {
1868 entry_size = (uintptr_t)((grn_tiny_hash_entry *)0)->value + value_size;
1869 } else {
1870 if (key_size == sizeof(uint32_t)) {
1871 entry_size = (uintptr_t)((grn_plain_hash_entry *)0)->value + value_size;
1872 } else {
1873 entry_size = (uintptr_t)((grn_rich_hash_entry *)0)->key_and_value
1874 + key_size + value_size;
1875 }
1876 }
1877 if (entry_size != sizeof(uint32_t)) {
1878 entry_size += sizeof(uintptr_t) - 1;
1879 entry_size &= ~(sizeof(uintptr_t) - 1);
1880 }
1881 return entry_size;
1882 }
1883
1884 static grn_rc
grn_tiny_hash_init(grn_ctx * ctx,grn_hash * hash,const char * path,uint32_t key_size,uint32_t value_size,uint32_t flags,grn_encoding encoding)1885 grn_tiny_hash_init(grn_ctx *ctx, grn_hash *hash, const char *path,
1886 uint32_t key_size, uint32_t value_size, uint32_t flags,
1887 grn_encoding encoding)
1888 {
1889 uint32_t entry_size;
1890
1891 if (path) {
1892 return GRN_INVALID_ARGUMENT;
1893 }
1894 hash->index = GRN_CTX_ALLOC(ctx, INITIAL_INDEX_SIZE * sizeof(grn_id));
1895 if (!hash->index) {
1896 return GRN_NO_MEMORY_AVAILABLE;
1897 }
1898
1899 entry_size = grn_tiny_hash_calculate_entry_size(key_size, value_size, flags);
1900 hash->obj.header.flags = flags;
1901 hash->ctx = ctx;
1902 hash->key_size = key_size;
1903 hash->encoding = encoding;
1904 hash->value_size = value_size;
1905 hash->entry_size = entry_size;
1906 hash->n_garbages = &hash->n_garbages_;
1907 hash->n_entries = &hash->n_entries_;
1908 hash->max_offset = &hash->max_offset_;
1909 hash->max_offset_ = INITIAL_INDEX_SIZE - 1;
1910 hash->io = NULL;
1911 hash->header.common = NULL;
1912 hash->n_garbages_ = 0;
1913 hash->n_entries_ = 0;
1914 hash->garbages = GRN_ID_NIL;
1915 hash->tokenizer = NULL;
1916 hash->normalizer = NULL;
1917 GRN_PTR_INIT(&(hash->token_filters), GRN_OBJ_VECTOR, GRN_ID_NIL);
1918 grn_tiny_array_init(ctx, &hash->a, entry_size, GRN_TINY_ARRAY_CLEAR);
1919 grn_tiny_bitmap_init(ctx, &hash->bitmap);
1920 return GRN_SUCCESS;
1921 }
1922
1923 static grn_rc
grn_hash_init(grn_ctx * ctx,grn_hash * hash,const char * path,uint32_t key_size,uint32_t value_size,uint32_t flags)1924 grn_hash_init(grn_ctx *ctx, grn_hash *hash, const char *path,
1925 uint32_t key_size, uint32_t value_size, uint32_t flags)
1926 {
1927 if (flags & GRN_HASH_TINY) {
1928 return grn_tiny_hash_init(ctx, hash, path, key_size, value_size,
1929 flags, ctx->encoding);
1930 } else {
1931 return grn_io_hash_init(ctx, hash, path, key_size, value_size,
1932 flags, ctx->encoding, 0);
1933 }
1934 }
1935
1936 grn_hash *
grn_hash_create(grn_ctx * ctx,const char * path,uint32_t key_size,uint32_t value_size,uint32_t flags)1937 grn_hash_create(grn_ctx *ctx, const char *path, uint32_t key_size, uint32_t value_size,
1938 uint32_t flags)
1939 {
1940 grn_hash *hash;
1941 if (!ctx) {
1942 return NULL;
1943 }
1944 if (key_size > GRN_HASH_MAX_KEY_SIZE_LARGE) {
1945 return NULL;
1946 }
1947 hash = (grn_hash *)GRN_CALLOC(sizeof(grn_hash));
1948 if (!hash) {
1949 return NULL;
1950 }
1951 GRN_DB_OBJ_SET_TYPE(hash, GRN_TABLE_HASH_KEY);
1952 if (grn_hash_init(ctx, hash, path, key_size, value_size, flags)) {
1953 GRN_FREE(hash);
1954 return NULL;
1955 }
1956 return hash;
1957 }
1958
1959 grn_hash *
grn_hash_open(grn_ctx * ctx,const char * path)1960 grn_hash_open(grn_ctx *ctx, const char *path)
1961 {
1962 if (ctx) {
1963 grn_io * const io = grn_io_open(ctx, path, grn_io_auto);
1964 if (io) {
1965 grn_hash_header_common * const header = grn_io_header(io);
1966 uint32_t io_type = grn_io_get_type(io);
1967 if (io_type == GRN_TABLE_HASH_KEY) {
1968 grn_hash * const hash = (grn_hash *)GRN_MALLOC(sizeof(grn_hash));
1969 if (hash) {
1970 if (!(header->flags & GRN_HASH_TINY)) {
1971 GRN_DB_OBJ_SET_TYPE(hash, GRN_TABLE_HASH_KEY);
1972 hash->ctx = ctx;
1973 hash->key_size = header->key_size;
1974 hash->encoding = header->encoding;
1975 hash->value_size = header->value_size;
1976 hash->entry_size = header->entry_size;
1977 hash->n_garbages = &header->n_garbages;
1978 hash->n_entries = &header->n_entries;
1979 hash->max_offset = &header->max_offset;
1980 hash->io = io;
1981 hash->header.common = header;
1982 hash->lock = &header->lock;
1983 hash->tokenizer = grn_ctx_at(ctx, header->tokenizer);
1984 if (header->flags & GRN_OBJ_KEY_NORMALIZE) {
1985 header->flags &= ~GRN_OBJ_KEY_NORMALIZE;
1986 hash->normalizer = grn_ctx_get(ctx, GRN_NORMALIZER_AUTO_NAME, -1);
1987 header->normalizer = grn_obj_id(ctx, hash->normalizer);
1988 } else {
1989 hash->normalizer = grn_ctx_at(ctx, header->normalizer);
1990 }
1991 GRN_PTR_INIT(&(hash->token_filters), GRN_OBJ_VECTOR, GRN_ID_NIL);
1992 hash->obj.header.flags = header->flags;
1993 return hash;
1994 } else {
1995 GRN_LOG(ctx, GRN_LOG_NOTICE,
1996 "invalid hash flag. (%x)", header->flags);
1997 }
1998 GRN_FREE(hash);
1999 }
2000 } else {
2001 ERR(GRN_INVALID_FORMAT,
2002 "[table][hash] file type must be %#04x: <%#04x>",
2003 GRN_TABLE_HASH_KEY, io_type);
2004 }
2005 grn_io_close(ctx, io);
2006 }
2007 }
2008 return NULL;
2009 }
2010
2011 /*
2012 * grn_hash_error_if_truncated() logs an error and returns its error code if
2013 * a hash is truncated by another process.
2014 * Otherwise, this function returns GRN_SUCCESS.
2015 * Note that `ctx` and `hash` must be valid.
2016 *
2017 * FIXME: A hash should be reopened if possible.
2018 */
2019 static grn_rc
grn_hash_error_if_truncated(grn_ctx * ctx,grn_hash * hash)2020 grn_hash_error_if_truncated(grn_ctx *ctx, grn_hash *hash)
2021 {
2022 if (hash->header.common && hash->header.common->truncated) {
2023 ERR(GRN_FILE_CORRUPT,
2024 "hash is truncated, please unmap or reopen the database");
2025 return GRN_FILE_CORRUPT;
2026 }
2027 return GRN_SUCCESS;
2028 }
2029
2030 static grn_rc
grn_tiny_hash_fin(grn_ctx * ctx,grn_hash * hash)2031 grn_tiny_hash_fin(grn_ctx *ctx, grn_hash *hash)
2032 {
2033 if (!hash->index) {
2034 return GRN_INVALID_ARGUMENT;
2035 }
2036
2037 GRN_OBJ_FIN(ctx, &(hash->token_filters));
2038
2039 if (hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) {
2040 uint32_t num_remaining_entries = *hash->n_entries;
2041 grn_id *hash_ptr;
2042 for (hash_ptr = hash->index; num_remaining_entries; hash_ptr++) {
2043 const grn_id id = *hash_ptr;
2044 if (id && id != GARBAGE) {
2045 grn_tiny_hash_entry * const entry =
2046 (grn_tiny_hash_entry *)grn_tiny_array_get(&hash->a, id);
2047 GRN_ASSERT(entry);
2048 num_remaining_entries--;
2049 if (entry && !(entry->flag & HASH_IMMEDIATE)) {
2050 GRN_CTX_FREE(ctx, entry->key.ptr);
2051 }
2052 }
2053 }
2054 }
2055 grn_tiny_array_fin(&hash->a);
2056 grn_tiny_bitmap_fin(&hash->bitmap);
2057 GRN_CTX_FREE(ctx, hash->index);
2058 return GRN_SUCCESS;
2059 }
2060
2061 grn_rc
grn_hash_close(grn_ctx * ctx,grn_hash * hash)2062 grn_hash_close(grn_ctx *ctx, grn_hash *hash)
2063 {
2064 grn_rc rc;
2065 if (!ctx || !hash) { return GRN_INVALID_ARGUMENT; }
2066 if (grn_hash_is_io_hash(hash)) {
2067 rc = grn_io_close(ctx, hash->io);
2068 GRN_OBJ_FIN(ctx, &(hash->token_filters));
2069 } else {
2070 GRN_ASSERT(ctx == hash->ctx);
2071 rc = grn_tiny_hash_fin(ctx, hash);
2072 }
2073 GRN_FREE(hash);
2074 return rc;
2075 }
2076
2077 grn_rc
grn_hash_remove(grn_ctx * ctx,const char * path)2078 grn_hash_remove(grn_ctx *ctx, const char *path)
2079 {
2080 if (!ctx || !path) { return GRN_INVALID_ARGUMENT; }
2081 return grn_io_remove(ctx, path);
2082 }
2083
2084 grn_rc
grn_hash_truncate(grn_ctx * ctx,grn_hash * hash)2085 grn_hash_truncate(grn_ctx *ctx, grn_hash *hash)
2086 {
2087 grn_rc rc;
2088 char *path = NULL;
2089 uint32_t key_size, value_size, flags;
2090
2091 if (!ctx || !hash) {
2092 return GRN_INVALID_ARGUMENT;
2093 }
2094 rc = grn_hash_error_if_truncated(ctx, hash);
2095 if (rc != GRN_SUCCESS) {
2096 return rc;
2097 }
2098
2099 if (grn_hash_is_io_hash(hash)) {
2100 const char * const io_path = grn_io_path(hash->io);
2101 if (io_path && *io_path) {
2102 path = GRN_STRDUP(io_path);
2103 if (!path) {
2104 ERR(GRN_NO_MEMORY_AVAILABLE, "cannot duplicate path: <%s>", io_path);
2105 return GRN_NO_MEMORY_AVAILABLE;
2106 }
2107 }
2108 }
2109 key_size = hash->key_size;
2110 value_size = hash->value_size;
2111 flags = hash->obj.header.flags;
2112
2113 if (grn_hash_is_io_hash(hash)) {
2114 if (path) {
2115 /* Only an I/O hash with a valid path uses the `truncated` flag. */
2116 hash->header.common->truncated = GRN_TRUE;
2117 }
2118 rc = grn_io_close(ctx, hash->io);
2119 if (!rc) {
2120 hash->io = NULL;
2121 if (path) {
2122 rc = grn_io_remove(ctx, path);
2123 }
2124 }
2125 GRN_OBJ_FIN(ctx, &(hash->token_filters));
2126 }
2127 if (!rc) {
2128 rc = grn_hash_init(ctx, hash, path, key_size, value_size, flags);
2129 }
2130 if (path) {
2131 GRN_FREE(path);
2132 }
2133 return rc;
2134 }
2135
2136 inline static uint32_t
grn_hash_calculate_hash_value(const void * ptr,uint32_t size)2137 grn_hash_calculate_hash_value(const void *ptr, uint32_t size)
2138 {
2139 uint32_t i;
2140 uint32_t hash_value = 0;
2141 for (i = 0; i < size; i++) {
2142 hash_value = (hash_value * 1021) + ((const uint8_t *)ptr)[i];
2143 }
2144 return hash_value;
2145 }
2146
2147 inline static uint32_t
grn_hash_calculate_step(uint32_t hash_value)2148 grn_hash_calculate_step(uint32_t hash_value)
2149 {
2150 return (hash_value >> 2) | 0x1010101;
2151 }
2152
2153 static grn_rc
grn_hash_reset(grn_ctx * ctx,grn_hash * hash,uint32_t expected_n_entries)2154 grn_hash_reset(grn_ctx *ctx, grn_hash *hash, uint32_t expected_n_entries)
2155 {
2156 grn_id *new_index = NULL;
2157 uint32_t new_index_size = INITIAL_INDEX_SIZE;
2158 grn_id *src_ptr = NULL, *dest_ptr = NULL;
2159 uint32_t src_offset = 0, dest_offset = 0;
2160 const uint32_t n_entries = *hash->n_entries;
2161 const uint32_t max_offset = *hash->max_offset;
2162
2163 if (!expected_n_entries) {
2164 expected_n_entries = n_entries * 2;
2165 }
2166 if (expected_n_entries > INT_MAX) {
2167 return GRN_NO_MEMORY_AVAILABLE;
2168 }
2169 while (new_index_size <= expected_n_entries) {
2170 new_index_size *= 2;
2171 }
2172
2173 if (grn_hash_is_io_hash(hash)) {
2174 uint32_t i;
2175 src_offset = hash->header.common->idx_offset;
2176 dest_offset = MAX_INDEX_SIZE - src_offset;
2177 for (i = 0; i < new_index_size; i += (IDX_MASK_IN_A_SEGMENT + 1)) {
2178 /*
2179 * The following grn_io_hash_idx_at() allocates memory for a new segment
2180 * and returns a pointer to the new segment. It's actually bad manners
2181 * but faster than calling grn_io_hash_idx_at() for each element.
2182 */
2183 dest_ptr = grn_io_hash_idx_at(ctx, hash, i + dest_offset);
2184 if (!dest_ptr) {
2185 return GRN_NO_MEMORY_AVAILABLE;
2186 }
2187 memset(dest_ptr, 0, GRN_HASH_SEGMENT_SIZE);
2188 }
2189 } else {
2190 GRN_ASSERT(ctx == hash->ctx);
2191 new_index = GRN_CTX_ALLOC(ctx, new_index_size * sizeof(grn_id));
2192 if (!new_index) {
2193 return GRN_NO_MEMORY_AVAILABLE;
2194 }
2195 src_ptr = hash->index;
2196 }
2197
2198 {
2199 uint32_t src_pos, count;
2200 const uint32_t new_max_offset = new_index_size - 1;
2201 for (count = 0, src_pos = 0; count < n_entries && src_pos <= max_offset;
2202 src_pos++, src_ptr++) {
2203 uint32_t i, step;
2204 grn_id entry_id;
2205 grn_hash_entry *entry;
2206 if (grn_hash_is_io_hash(hash) && !(src_pos & IDX_MASK_IN_A_SEGMENT)) {
2207 src_ptr = grn_io_hash_idx_at(ctx, hash, src_pos + src_offset);
2208 if (!src_ptr) {
2209 return GRN_NO_MEMORY_AVAILABLE;
2210 }
2211 }
2212 entry_id = *src_ptr;
2213 if (!entry_id || (entry_id == GARBAGE)) {
2214 continue;
2215 }
2216 entry = grn_hash_entry_at(ctx, hash, entry_id, GRN_TABLE_ADD);
2217 if (!entry) {
2218 return GRN_NO_MEMORY_AVAILABLE;
2219 }
2220 step = grn_hash_calculate_step(entry->hash_value);
2221 for (i = entry->hash_value; ; i += step) {
2222 i &= new_max_offset;
2223 if (grn_hash_is_io_hash(hash)) {
2224 dest_ptr = grn_io_hash_idx_at(ctx, hash, i + dest_offset);
2225 if (!dest_ptr) {
2226 return GRN_NO_MEMORY_AVAILABLE;
2227 }
2228 } else {
2229 dest_ptr = new_index + i;
2230 }
2231 if (!*dest_ptr) {
2232 break;
2233 }
2234 }
2235 *dest_ptr = entry_id;
2236 count++;
2237 }
2238 *hash->max_offset = new_max_offset;
2239 *hash->n_garbages = 0;
2240 }
2241
2242 if (grn_hash_is_io_hash(hash)) {
2243 hash->header.common->idx_offset = dest_offset;
2244 } else {
2245 grn_id * const old_index = hash->index;
2246 hash->index = new_index;
2247 GRN_CTX_FREE(ctx, old_index);
2248 }
2249
2250 return GRN_SUCCESS;
2251 }
2252
2253 grn_rc
grn_hash_lock(grn_ctx * ctx,grn_hash * hash,int timeout)2254 grn_hash_lock(grn_ctx *ctx, grn_hash *hash, int timeout)
2255 {
2256 static int _ncalls = 0, _ncolls = 0;
2257 uint32_t count;
2258 _ncalls++;
2259 for (count = 0;; count++) {
2260 uint32_t lock;
2261 GRN_ATOMIC_ADD_EX(hash->lock, 1, lock);
2262 if (lock) {
2263 GRN_ATOMIC_ADD_EX(hash->lock, -1, lock);
2264 if (!timeout || (timeout > 0 && timeout == count)) { break; }
2265 if (!(++_ncolls % 1000000) && (_ncolls > _ncalls)) {
2266 if (_ncolls < 0 || _ncalls < 0) {
2267 _ncolls = 0; _ncalls = 0;
2268 } else {
2269 GRN_LOG(ctx, GRN_LOG_NOTICE, "hash(%p) collisions(%d/%d)", hash, _ncolls, _ncalls);
2270 }
2271 }
2272 grn_nanosleep(GRN_LOCK_WAIT_TIME_NANOSECOND);
2273 continue;
2274 }
2275 return GRN_SUCCESS;
2276 }
2277 ERR(GRN_RESOURCE_DEADLOCK_AVOIDED, "grn_hash_lock");
2278 return ctx->rc;
2279 }
2280
2281 grn_rc
grn_hash_unlock(grn_ctx * ctx,grn_hash * hash)2282 grn_hash_unlock(grn_ctx *ctx, grn_hash *hash)
2283 {
2284 uint32_t lock;
2285 GRN_ATOMIC_ADD_EX(hash->lock, -1, lock);
2286 return GRN_SUCCESS;
2287 }
2288
2289 grn_rc
grn_hash_clear_lock(grn_ctx * ctx,grn_hash * hash)2290 grn_hash_clear_lock(grn_ctx *ctx, grn_hash *hash)
2291 {
2292 *hash->lock = 0;
2293 return GRN_SUCCESS;
2294 }
2295
2296 uint32_t
grn_hash_size(grn_ctx * ctx,grn_hash * hash)2297 grn_hash_size(grn_ctx *ctx, grn_hash *hash)
2298 {
2299 if (grn_hash_error_if_truncated(ctx, hash) != GRN_SUCCESS) {
2300 return 0;
2301 }
2302 return *hash->n_entries;
2303 }
2304
2305 inline static grn_id
grn_io_hash_add(grn_ctx * ctx,grn_hash * hash,uint32_t hash_value,const void * key,unsigned int key_size,void ** value)2306 grn_io_hash_add(grn_ctx *ctx, grn_hash *hash, uint32_t hash_value,
2307 const void *key, unsigned int key_size, void **value)
2308 {
2309 grn_id entry_id;
2310 grn_hash_entry *entry;
2311 grn_hash_header_common * const header = hash->header.common;
2312 grn_id *garbages;
2313
2314 if (GRN_HASH_IS_LARGE_KEY(hash)) {
2315 garbages = hash->header.large->garbages;
2316 } else {
2317 garbages = hash->header.normal->garbages;
2318 }
2319
2320 entry_id = garbages[key_size - 1];
2321 if (entry_id) {
2322 entry = grn_io_hash_entry_at(ctx, hash, entry_id, GRN_TABLE_ADD);
2323 if (!entry) {
2324 return GRN_ID_NIL;
2325 }
2326 garbages[key_size - 1] = *(grn_id *)entry;
2327 if (hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) {
2328 /* keep entry->io_entry's hash_value, flag, key_size and key. */
2329 if (grn_hash_is_large_total_key_size(ctx, hash)) {
2330 memset(entry->io_entry_large.value, 0, header->value_size);
2331 } else {
2332 memset(entry->io_entry_normal.value, 0, header->value_size);
2333 }
2334 } else {
2335 memset(entry, 0, header->entry_size);
2336 }
2337 } else {
2338 entry_id = header->curr_rec + 1;
2339 entry = grn_hash_entry_at(ctx, hash, entry_id, GRN_TABLE_ADD);
2340 if (!entry) {
2341 return GRN_ID_NIL;
2342 }
2343 header->curr_rec = entry_id;
2344 }
2345
2346 if (!grn_io_array_bit_on(ctx, hash->io, GRN_HASH_BITMAP_SEGMENT, entry_id)) {
2347 /* TODO: error handling. */
2348 }
2349
2350 if (grn_hash_entry_put_key(ctx, hash, entry, hash_value, key, key_size)) {
2351 grn_hash_delete_by_id(ctx, hash, entry_id, NULL);
2352 return GRN_ID_NIL;
2353 }
2354
2355 if (value) {
2356 *value = grn_hash_entry_get_value(ctx, hash, entry);
2357 }
2358 return entry_id;
2359 }
2360
2361 inline static grn_id
grn_tiny_hash_add(grn_ctx * ctx,grn_hash * hash,uint32_t hash_value,const void * key,unsigned int key_size,void ** value)2362 grn_tiny_hash_add(grn_ctx *ctx, grn_hash *hash, uint32_t hash_value,
2363 const void *key, unsigned int key_size, void **value)
2364 {
2365 grn_id entry_id;
2366 grn_hash_entry *entry;
2367 if (hash->garbages) {
2368 entry_id = hash->garbages;
2369 entry = (grn_hash_entry *)grn_tiny_array_get(&hash->a, entry_id);
2370 hash->garbages = *(grn_id *)entry;
2371 memset(entry, 0, hash->entry_size);
2372 } else {
2373 entry_id = hash->a.max + 1;
2374 entry = (grn_hash_entry *)grn_tiny_array_put(&hash->a, entry_id);
2375 if (!entry) {
2376 return GRN_ID_NIL;
2377 }
2378 }
2379
2380 if (!grn_tiny_bitmap_put_and_set(&hash->bitmap, entry_id, 1)) {
2381 /* TODO: error handling. */
2382 }
2383
2384 if (grn_hash_entry_put_key(ctx, hash, entry, hash_value, key, key_size)) {
2385 /* TODO: error handling. */
2386 }
2387
2388 if (value) {
2389 *value = grn_hash_entry_get_value(ctx, hash, entry);
2390 }
2391 return entry_id;
2392 }
2393
2394 grn_id
grn_hash_add(grn_ctx * ctx,grn_hash * hash,const void * key,unsigned int key_size,void ** value,int * added)2395 grn_hash_add(grn_ctx *ctx, grn_hash *hash, const void *key,
2396 unsigned int key_size, void **value, int *added)
2397 {
2398 uint32_t hash_value;
2399 if (grn_hash_error_if_truncated(ctx, hash) != GRN_SUCCESS) {
2400 return GRN_ID_NIL;
2401 }
2402 if (!key || !key_size) {
2403 return GRN_ID_NIL;
2404 }
2405 if (hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) {
2406 if (key_size > hash->key_size) {
2407 ERR(GRN_INVALID_ARGUMENT, "too long key");
2408 return GRN_ID_NIL;
2409 }
2410 hash_value = grn_hash_calculate_hash_value(key, key_size);
2411 } else {
2412 if (key_size != hash->key_size) {
2413 ERR(GRN_INVALID_ARGUMENT, "key size unmatch");
2414 return GRN_ID_NIL;
2415 }
2416 if (key_size == sizeof(uint32_t)) {
2417 hash_value = *((uint32_t *)key);
2418 } else {
2419 hash_value = grn_hash_calculate_hash_value(key, key_size);
2420 }
2421 }
2422
2423 {
2424 uint32_t i;
2425 const uint32_t step = grn_hash_calculate_step(hash_value);
2426 grn_id id, *index, *garbage_index = NULL;
2427 grn_hash_entry *entry;
2428
2429 /* lock */
2430 if ((*hash->n_entries + *hash->n_garbages) * 2 > *hash->max_offset) {
2431 if (*hash->max_offset > (1 << 29)) {
2432 ERR(GRN_TOO_LARGE_OFFSET, "hash table size limit");
2433 return GRN_ID_NIL;
2434 }
2435 grn_hash_reset(ctx, hash, 0);
2436 }
2437
2438 for (i = hash_value; ; i += step) {
2439 index = grn_hash_idx_at(ctx, hash, i);
2440 if (!index) {
2441 return GRN_ID_NIL;
2442 }
2443 id = *index;
2444 if (!id) {
2445 break;
2446 }
2447 if (id == GARBAGE) {
2448 if (!garbage_index) {
2449 garbage_index = index;
2450 }
2451 continue;
2452 }
2453
2454 entry = grn_hash_entry_at(ctx, hash, id, GRN_TABLE_ADD);
2455 if (!entry) {
2456 return GRN_ID_NIL;
2457 }
2458 if (grn_hash_entry_compare_key(ctx, hash, entry, hash_value,
2459 key, key_size)) {
2460 if (value) {
2461 *value = grn_hash_entry_get_value(ctx, hash, entry);
2462 }
2463 if (added) {
2464 *added = 0;
2465 }
2466 return id;
2467 }
2468 }
2469
2470 if (grn_hash_is_io_hash(hash)) {
2471 id = grn_io_hash_add(ctx, hash, hash_value, key, key_size, value);
2472 } else {
2473 id = grn_tiny_hash_add(ctx, hash, hash_value, key, key_size, value);
2474 }
2475 if (!id) {
2476 return GRN_ID_NIL;
2477 }
2478 if (garbage_index) {
2479 (*hash->n_garbages)--;
2480 index = garbage_index;
2481 }
2482 *index = id;
2483 (*hash->n_entries)++;
2484 /* unlock */
2485
2486 if (added) {
2487 *added = 1;
2488 }
2489 return id;
2490 }
2491 }
2492
2493 grn_id
grn_hash_get(grn_ctx * ctx,grn_hash * hash,const void * key,unsigned int key_size,void ** value)2494 grn_hash_get(grn_ctx *ctx, grn_hash *hash, const void *key,
2495 unsigned int key_size, void **value)
2496 {
2497 uint32_t hash_value;
2498 if (grn_hash_error_if_truncated(ctx, hash) != GRN_SUCCESS) {
2499 return GRN_ID_NIL;
2500 }
2501 if (hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) {
2502 if (key_size > hash->key_size) {
2503 return GRN_ID_NIL;
2504 }
2505 hash_value = grn_hash_calculate_hash_value(key, key_size);
2506 } else {
2507 if (key_size != hash->key_size) {
2508 return GRN_ID_NIL;
2509 }
2510 if (key_size == sizeof(uint32_t)) {
2511 hash_value = *((uint32_t *)key);
2512 } else {
2513 hash_value = grn_hash_calculate_hash_value(key, key_size);
2514 }
2515 }
2516
2517 {
2518 uint32_t i;
2519 const uint32_t step = grn_hash_calculate_step(hash_value);
2520 for (i = hash_value; ; i += step) {
2521 grn_id id;
2522 grn_id * const index = grn_hash_idx_at(ctx, hash, i);
2523 if (!index) {
2524 return GRN_ID_NIL;
2525 }
2526 id = *index;
2527 if (!id) {
2528 return GRN_ID_NIL;
2529 }
2530 if (id != GARBAGE) {
2531 grn_hash_entry * const entry = grn_hash_entry_at(ctx, hash, id, 0);
2532 if (entry) {
2533 if (grn_hash_entry_compare_key(ctx, hash, entry, hash_value,
2534 key, key_size)) {
2535 if (value) {
2536 *value = grn_hash_entry_get_value(ctx, hash, entry);
2537 }
2538 return id;
2539 }
2540 }
2541 }
2542 }
2543 }
2544 }
2545
2546 inline static grn_hash_entry *
grn_hash_get_entry(grn_ctx * ctx,grn_hash * hash,grn_id id)2547 grn_hash_get_entry(grn_ctx *ctx, grn_hash *hash, grn_id id)
2548 {
2549 if (!grn_hash_bitmap_at(ctx, hash, id)) {
2550 return NULL;
2551 }
2552 return grn_hash_entry_at(ctx, hash, id, 0);
2553 }
2554
2555 const char *
_grn_hash_key(grn_ctx * ctx,grn_hash * hash,grn_id id,uint32_t * key_size)2556 _grn_hash_key(grn_ctx *ctx, grn_hash *hash, grn_id id, uint32_t *key_size)
2557 {
2558 grn_hash_entry * const entry = grn_hash_get_entry(ctx, hash, id);
2559 if (!entry) {
2560 *key_size = 0;
2561 return NULL;
2562 }
2563 *key_size = grn_hash_entry_get_key_size(hash, entry);
2564 return grn_hash_entry_get_key(ctx, hash, entry);
2565 }
2566
2567 int
grn_hash_get_key(grn_ctx * ctx,grn_hash * hash,grn_id id,void * keybuf,int bufsize)2568 grn_hash_get_key(grn_ctx *ctx, grn_hash *hash, grn_id id, void *keybuf, int bufsize)
2569 {
2570 int key_size;
2571 grn_hash_entry *entry;
2572 if (grn_hash_error_if_truncated(ctx, hash) != GRN_SUCCESS) {
2573 return 0;
2574 }
2575 entry = grn_hash_get_entry(ctx, hash, id);
2576 if (!entry) {
2577 return 0;
2578 }
2579 key_size = grn_hash_entry_get_key_size(hash, entry);
2580 if (bufsize >= key_size) {
2581 grn_memcpy(keybuf, grn_hash_entry_get_key(ctx, hash, entry), key_size);
2582 }
2583 return key_size;
2584 }
2585
2586 int
grn_hash_get_key2(grn_ctx * ctx,grn_hash * hash,grn_id id,grn_obj * bulk)2587 grn_hash_get_key2(grn_ctx *ctx, grn_hash *hash, grn_id id, grn_obj *bulk)
2588 {
2589 int key_size;
2590 char *key;
2591 grn_hash_entry *entry;
2592 if (grn_hash_error_if_truncated(ctx, hash) != GRN_SUCCESS) {
2593 return 0;
2594 }
2595 entry = grn_hash_get_entry(ctx, hash, id);
2596 if (!entry) {
2597 return 0;
2598 }
2599 key_size = grn_hash_entry_get_key_size(hash, entry);
2600 key = grn_hash_entry_get_key(ctx, hash, entry);
2601 if (bulk->header.impl_flags & GRN_OBJ_REFER) {
2602 bulk->u.b.head = key;
2603 bulk->u.b.curr = key + key_size;
2604 } else {
2605 grn_bulk_write(ctx, bulk, key, key_size);
2606 }
2607 return key_size;
2608 }
2609
2610 int
grn_hash_get_value(grn_ctx * ctx,grn_hash * hash,grn_id id,void * valuebuf)2611 grn_hash_get_value(grn_ctx *ctx, grn_hash *hash, grn_id id, void *valuebuf)
2612 {
2613 void *value;
2614 grn_hash_entry *entry;
2615 if (grn_hash_error_if_truncated(ctx, hash) != GRN_SUCCESS) {
2616 return 0;
2617 }
2618 entry = grn_hash_get_entry(ctx, hash, id);
2619 if (!entry) {
2620 return 0;
2621 }
2622 value = grn_hash_entry_get_value(ctx, hash, entry);
2623 if (!value) {
2624 return 0;
2625 }
2626 if (valuebuf) {
2627 grn_memcpy(valuebuf, value, hash->value_size);
2628 }
2629 return hash->value_size;
2630 }
2631
2632 const char *
grn_hash_get_value_(grn_ctx * ctx,grn_hash * hash,grn_id id,uint32_t * size)2633 grn_hash_get_value_(grn_ctx *ctx, grn_hash *hash, grn_id id, uint32_t *size)
2634 {
2635 const void *value;
2636 grn_hash_entry *entry;
2637 if (grn_hash_error_if_truncated(ctx, hash) != GRN_SUCCESS) {
2638 return NULL;
2639 }
2640 entry = grn_hash_get_entry(ctx, hash, id);
2641 if (!entry) {
2642 return NULL;
2643 }
2644 value = grn_hash_entry_get_value(ctx, hash, entry);
2645 if (!value) {
2646 return NULL;
2647 }
2648 if (size) {
2649 *size = hash->value_size;
2650 }
2651 return (const char *)value;
2652 }
2653
2654 int
grn_hash_get_key_value(grn_ctx * ctx,grn_hash * hash,grn_id id,void * keybuf,int bufsize,void * valuebuf)2655 grn_hash_get_key_value(grn_ctx *ctx, grn_hash *hash, grn_id id,
2656 void *keybuf, int bufsize, void *valuebuf)
2657 {
2658 void *value;
2659 int key_size;
2660 grn_hash_entry *entry;
2661 if (grn_hash_error_if_truncated(ctx, hash) != GRN_SUCCESS) {
2662 return 0;
2663 }
2664 entry = grn_hash_get_entry(ctx, hash, id);
2665 if (!entry) {
2666 return 0;
2667 }
2668 key_size = grn_hash_entry_get_key_size(hash, entry);
2669 if (bufsize >= key_size) {
2670 grn_memcpy(keybuf, grn_hash_entry_get_key(ctx, hash, entry), key_size);
2671 }
2672 value = grn_hash_entry_get_value(ctx, hash, entry);
2673 if (!value) {
2674 return 0;
2675 }
2676 if (valuebuf) {
2677 grn_memcpy(valuebuf, value, hash->value_size);
2678 }
2679 return key_size;
2680 }
2681
2682 int
_grn_hash_get_key_value(grn_ctx * ctx,grn_hash * hash,grn_id id,void ** key,void ** value)2683 _grn_hash_get_key_value(grn_ctx *ctx, grn_hash *hash, grn_id id,
2684 void **key, void **value)
2685 {
2686 int key_size;
2687 grn_hash_entry *entry;
2688 if (grn_hash_error_if_truncated(ctx, hash) != GRN_SUCCESS) {
2689 return 0;
2690 }
2691 entry = grn_hash_get_entry(ctx, hash, id);
2692 if (!entry) {
2693 return 0;
2694 }
2695 key_size = grn_hash_entry_get_key_size(hash, entry);
2696 *key = grn_hash_entry_get_key(ctx, hash, entry);
2697 *value = grn_hash_entry_get_value(ctx, hash, entry);
2698 return *value ? key_size : 0;
2699 }
2700
2701 grn_rc
grn_hash_set_value(grn_ctx * ctx,grn_hash * hash,grn_id id,const void * value,int flags)2702 grn_hash_set_value(grn_ctx *ctx, grn_hash *hash, grn_id id,
2703 const void *value, int flags)
2704 {
2705 void *entry_value;
2706 grn_hash_entry *entry;
2707 if (grn_hash_error_if_truncated(ctx, hash) != GRN_SUCCESS) {
2708 return GRN_ID_NIL;
2709 }
2710 if (!value) {
2711 return GRN_INVALID_ARGUMENT;
2712 }
2713 entry = grn_hash_get_entry(ctx, hash, id);
2714 if (!entry) {
2715 return GRN_NO_MEMORY_AVAILABLE;
2716 }
2717 entry_value = grn_hash_entry_get_value(ctx, hash, entry);
2718 if (!entry_value) {
2719 return GRN_NO_MEMORY_AVAILABLE;
2720 }
2721
2722 switch (flags & GRN_OBJ_SET_MASK) {
2723 case GRN_OBJ_SET :
2724 grn_memcpy(entry_value, value, hash->value_size);
2725 return GRN_SUCCESS;
2726 case GRN_OBJ_INCR :
2727 switch (hash->value_size) {
2728 case sizeof(int32_t) :
2729 *((int32_t *)entry_value) += *((int32_t *)value);
2730 return GRN_SUCCESS;
2731 case sizeof(int64_t) :
2732 *((int64_t *)entry_value) += *((int64_t *)value);
2733 return GRN_SUCCESS;
2734 default :
2735 return GRN_INVALID_ARGUMENT;
2736 }
2737 break;
2738 case GRN_OBJ_DECR :
2739 switch (hash->value_size) {
2740 case sizeof(int32_t) :
2741 *((int32_t *)entry_value) -= *((int32_t *)value);
2742 return GRN_SUCCESS;
2743 case sizeof(int64_t) :
2744 *((int64_t *)entry_value) -= *((int64_t *)value);
2745 return GRN_SUCCESS;
2746 default :
2747 return GRN_INVALID_ARGUMENT;
2748 }
2749 break;
2750 default :
2751 ERR(GRN_INVALID_ARGUMENT, "flags = %d", flags);
2752 return ctx->rc;
2753 }
2754 }
2755
2756 #define DELETE_IT do {\
2757 *ep = GARBAGE;\
2758 if (grn_hash_is_io_hash(hash)) {\
2759 uint32_t size = key_size - 1;\
2760 grn_id *garbages;\
2761 if (GRN_HASH_IS_LARGE_KEY(hash)) {\
2762 garbages = hash->header.large->garbages;\
2763 } else {\
2764 garbages = hash->header.normal->garbages;\
2765 }\
2766 ee->key = garbages[size];\
2767 garbages[size] = e;\
2768 grn_io_array_bit_off(ctx, hash->io, GRN_HASH_BITMAP_SEGMENT, e);\
2769 } else {\
2770 ee->key = hash->garbages;\
2771 hash->garbages = e;\
2772 if ((hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) && !(ee->flag & HASH_IMMEDIATE)) {\
2773 grn_ctx *ctx = hash->ctx;\
2774 GRN_CTX_FREE(ctx, ((entry_astr *)ee)->str);\
2775 }\
2776 grn_tiny_bitmap_get_and_set(&hash->bitmap, e, 0);\
2777 }\
2778 (*hash->n_entries)--;\
2779 (*hash->n_garbages)++;\
2780 rc = GRN_SUCCESS;\
2781 } while (0)
2782
2783 grn_rc
grn_hash_delete_by_id(grn_ctx * ctx,grn_hash * hash,grn_id id,grn_table_delete_optarg * optarg)2784 grn_hash_delete_by_id(grn_ctx *ctx, grn_hash *hash, grn_id id,
2785 grn_table_delete_optarg *optarg)
2786 {
2787 entry_str *ee;
2788 grn_rc rc;
2789 if (!hash || !id) { return GRN_INVALID_ARGUMENT; }
2790 rc = grn_hash_error_if_truncated(ctx, hash);
2791 if (rc != GRN_SUCCESS) {
2792 return rc;
2793 }
2794 rc = GRN_INVALID_ARGUMENT;
2795 /* lock */
2796 ee = grn_hash_entry_at(ctx, hash, id, 0);
2797 if (ee) {
2798 grn_id e, *ep;
2799 uint32_t i, key_size, h = ee->key, s = grn_hash_calculate_step(h);
2800 key_size = (hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) ? ee->size : hash->key_size;
2801 for (i = h; ; i += s) {
2802 if (!(ep = grn_hash_idx_at(ctx, hash, i))) { return GRN_NO_MEMORY_AVAILABLE; }
2803 if (!(e = *ep)) { break; }
2804 if (e == id) {
2805 DELETE_IT;
2806 break;
2807 }
2808 }
2809 }
2810 /* unlock */
2811 return rc;
2812 }
2813
2814 grn_rc
grn_hash_delete(grn_ctx * ctx,grn_hash * hash,const void * key,uint32_t key_size,grn_table_delete_optarg * optarg)2815 grn_hash_delete(grn_ctx *ctx, grn_hash *hash, const void *key, uint32_t key_size,
2816 grn_table_delete_optarg *optarg)
2817 {
2818 uint32_t h, i, m, s;
2819 grn_rc rc = grn_hash_error_if_truncated(ctx, hash);
2820 if (rc != GRN_SUCCESS) {
2821 return rc;
2822 }
2823 rc = GRN_INVALID_ARGUMENT;
2824 if (hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) {
2825 if (key_size > hash->key_size) { return GRN_INVALID_ARGUMENT; }
2826 h = grn_hash_calculate_hash_value(key, key_size);
2827 } else {
2828 if (key_size != hash->key_size) { return GRN_INVALID_ARGUMENT; }
2829 if (key_size == sizeof(uint32_t)) {
2830 h = *((uint32_t *)key);
2831 } else {
2832 h = grn_hash_calculate_hash_value(key, key_size);
2833 }
2834 }
2835 s = grn_hash_calculate_step(h);
2836 {
2837 grn_id e, *ep;
2838 /* lock */
2839 m = *hash->max_offset;
2840 for (i = h; ; i += s) {
2841 if (!(ep = grn_hash_idx_at(ctx, hash, i))) { return GRN_NO_MEMORY_AVAILABLE; }
2842 if (!(e = *ep)) { break; }
2843 if (e == GARBAGE) { continue; }
2844 {
2845 entry_str * const ee = grn_hash_entry_at(ctx, hash, e, 0);
2846 if (ee && match_key(ctx, hash, ee, h, key, key_size)) {
2847 DELETE_IT;
2848 break;
2849 }
2850 }
2851 }
2852 /* unlock */
2853 return rc;
2854 }
2855 }
2856
2857 /* only valid for hash tables, GRN_OBJ_KEY_VAR_SIZE && GRN_HASH_TINY */
2858 const char *
_grn_hash_strkey_by_val(void * v,uint16_t * size)2859 _grn_hash_strkey_by_val(void *v, uint16_t *size)
2860 {
2861 entry_astr *n = (entry_astr *)((uintptr_t)v -
2862 (uintptr_t)&((entry_astr *)0)->dummy);
2863 *size = n->size;
2864 return (n->flag & HASH_IMMEDIATE) ? (char *)&n->str : n->str;
2865 }
2866
2867 void
grn_hash_cursor_close(grn_ctx * ctx,grn_hash_cursor * c)2868 grn_hash_cursor_close(grn_ctx *ctx, grn_hash_cursor *c)
2869 {
2870 GRN_ASSERT(c->ctx == ctx);
2871 GRN_FREE(c);
2872 }
2873
2874 #define HASH_CURR_MAX(hash) \
2875 ((grn_hash_is_io_hash(hash)) ? (hash)->header.common->curr_rec : (hash)->a.max)
2876
2877 grn_hash_cursor *
grn_hash_cursor_open(grn_ctx * ctx,grn_hash * hash,const void * min,uint32_t min_size,const void * max,uint32_t max_size,int offset,int limit,int flags)2878 grn_hash_cursor_open(grn_ctx *ctx, grn_hash *hash,
2879 const void *min, uint32_t min_size,
2880 const void *max, uint32_t max_size,
2881 int offset, int limit, int flags)
2882 {
2883 grn_hash_cursor *c;
2884 if (!hash || !ctx) { return NULL; }
2885 if (grn_hash_error_if_truncated(ctx, hash) != GRN_SUCCESS) {
2886 return NULL;
2887 }
2888 if (!(c = GRN_MALLOCN(grn_hash_cursor, 1))) { return NULL; }
2889 GRN_DB_OBJ_SET_TYPE(c, GRN_CURSOR_TABLE_HASH_KEY);
2890 c->hash = hash;
2891 c->ctx = ctx;
2892 c->obj.header.flags = flags;
2893 c->obj.header.domain = GRN_ID_NIL;
2894 if (flags & GRN_CURSOR_DESCENDING) {
2895 c->dir = -1;
2896 if (max) {
2897 if (!(c->curr_rec = grn_hash_get(ctx, hash, max, max_size, NULL))) {
2898 c->tail = GRN_ID_NIL;
2899 goto exit;
2900 }
2901 if (!(flags & GRN_CURSOR_LT)) { c->curr_rec++; }
2902 } else {
2903 c->curr_rec = HASH_CURR_MAX(hash) + 1;
2904 }
2905 if (min) {
2906 if (!(c->tail = grn_hash_get(ctx, hash, min, min_size, NULL))) {
2907 c->curr_rec = GRN_ID_NIL;
2908 goto exit;
2909 }
2910 if ((flags & GRN_CURSOR_GT)) { c->tail++; }
2911 } else {
2912 c->tail = GRN_ID_NIL + 1;
2913 }
2914 if (c->curr_rec < c->tail) { c->tail = c->curr_rec; }
2915 } else {
2916 c->dir = 1;
2917 if (min) {
2918 if (!(c->curr_rec = grn_hash_get(ctx, hash, min, min_size, NULL))) {
2919 c->tail = GRN_ID_NIL;
2920 goto exit;
2921 }
2922 if (!(flags & GRN_CURSOR_GT)) { c->curr_rec--; }
2923 } else {
2924 c->curr_rec = GRN_ID_NIL;
2925 }
2926 if (max) {
2927 if (!(c->tail = grn_hash_get(ctx, hash, max, max_size, NULL))) {
2928 c->curr_rec = GRN_ID_NIL;
2929 goto exit;
2930 }
2931 if ((flags & GRN_CURSOR_LT)) { c->tail--; }
2932 } else {
2933 c->tail = HASH_CURR_MAX(hash);
2934 }
2935 if (c->tail < c->curr_rec) { c->tail = c->curr_rec; }
2936 }
2937 if (*hash->n_entries != HASH_CURR_MAX(hash)) {
2938 while (offset && c->curr_rec != c->tail) {
2939 c->curr_rec += c->dir;
2940 if (grn_hash_bitmap_at(ctx, c->hash, c->curr_rec)) { offset--; }
2941 }
2942 } else {
2943 c->curr_rec += c->dir * offset;
2944 }
2945 exit :
2946 c->rest = (limit < 0) ? GRN_ARRAY_MAX : limit;
2947 return c;
2948 }
2949
2950 grn_id
grn_hash_cursor_next(grn_ctx * ctx,grn_hash_cursor * c)2951 grn_hash_cursor_next(grn_ctx *ctx, grn_hash_cursor *c)
2952 {
2953 if (c && c->rest) {
2954 while (c->curr_rec != c->tail) {
2955 c->curr_rec += c->dir;
2956 if (*c->hash->n_entries != HASH_CURR_MAX(c->hash)) {
2957 if (!grn_hash_bitmap_at(ctx, c->hash, c->curr_rec)) { continue; }
2958 }
2959 c->rest--;
2960 return c->curr_rec;
2961 }
2962 }
2963 return GRN_ID_NIL;
2964 }
2965
2966 grn_id
grn_hash_next(grn_ctx * ctx,grn_hash * hash,grn_id id)2967 grn_hash_next(grn_ctx *ctx, grn_hash *hash, grn_id id)
2968 {
2969 grn_id max = HASH_CURR_MAX(hash);
2970 while (++id <= max) {
2971 if (grn_hash_bitmap_at(ctx, hash, id)) { return id; }
2972 }
2973 return GRN_ID_NIL;
2974 }
2975
2976 grn_id
grn_hash_at(grn_ctx * ctx,grn_hash * hash,grn_id id)2977 grn_hash_at(grn_ctx *ctx, grn_hash *hash, grn_id id)
2978 {
2979 return grn_hash_bitmap_at(ctx, hash, id) ? id : GRN_ID_NIL;
2980 }
2981
2982 int
grn_hash_cursor_get_key(grn_ctx * ctx,grn_hash_cursor * c,void ** key)2983 grn_hash_cursor_get_key(grn_ctx *ctx, grn_hash_cursor *c, void **key)
2984 {
2985 int key_size;
2986 entry_str *ee;
2987 if (!c) { return 0; }
2988 ee = grn_hash_entry_at(ctx, c->hash, c->curr_rec, 0);
2989 if (!ee) { return 0; }
2990 key_size = (c->hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) ? ee->size : c->hash->key_size;
2991 *key = get_key(ctx, c->hash, ee);
2992 return key_size;
2993 }
2994
2995 int
grn_hash_cursor_get_value(grn_ctx * ctx,grn_hash_cursor * c,void ** value)2996 grn_hash_cursor_get_value(grn_ctx *ctx, grn_hash_cursor *c, void **value)
2997 {
2998 void *v;
2999 entry_str *ee;
3000 if (!c) { return 0; }
3001 ee = grn_hash_entry_at(ctx, c->hash, c->curr_rec, 0);
3002 if (ee && (v = get_value(ctx, c->hash, ee))) {
3003 *value = v;
3004 return c->hash->value_size;
3005 }
3006 return 0;
3007 }
3008
3009 int
grn_hash_cursor_get_key_value(grn_ctx * ctx,grn_hash_cursor * c,void ** key,uint32_t * key_size,void ** value)3010 grn_hash_cursor_get_key_value(grn_ctx *ctx, grn_hash_cursor *c,
3011 void **key, uint32_t *key_size, void **value)
3012 {
3013 entry_str *ee;
3014 if (!c) { return GRN_INVALID_ARGUMENT; }
3015 ee = grn_hash_entry_at(ctx, c->hash, c->curr_rec, 0);
3016 if (!ee) { return GRN_INVALID_ARGUMENT; }
3017 if (key_size) {
3018 *key_size = (c->hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) ? ee->size : c->hash->key_size;
3019 }
3020 if (key) { *key = get_key(ctx, c->hash, ee); }
3021 if (value) { *value = get_value(ctx, c->hash, ee); }
3022 return c->hash->value_size;
3023 }
3024
3025 grn_rc
grn_hash_cursor_set_value(grn_ctx * ctx,grn_hash_cursor * c,const void * value,int flags)3026 grn_hash_cursor_set_value(grn_ctx *ctx, grn_hash_cursor *c,
3027 const void *value, int flags)
3028 {
3029 if (!c) { return GRN_INVALID_ARGUMENT; }
3030 return grn_hash_set_value(ctx, c->hash, c->curr_rec, value, flags);
3031 }
3032
3033 grn_rc
grn_hash_cursor_delete(grn_ctx * ctx,grn_hash_cursor * c,grn_table_delete_optarg * optarg)3034 grn_hash_cursor_delete(grn_ctx *ctx, grn_hash_cursor *c,
3035 grn_table_delete_optarg *optarg)
3036 {
3037 if (!c) { return GRN_INVALID_ARGUMENT; }
3038 return grn_hash_delete_by_id(ctx, c->hash, c->curr_rec, optarg);
3039 }
3040
3041 /* sort */
3042
3043 #define PREPARE_VAL(e,ep,es) do {\
3044 if ((arg->flags & GRN_TABLE_SORT_BY_VALUE)) {\
3045 ep = ((const uint8_t *)(get_value(ctx, hash, (entry_str *)(e))));\
3046 es = hash->value_size;\
3047 } else {\
3048 ep = ((const uint8_t *)(get_key(ctx, hash, (entry_str *)(e))));\
3049 es = ((hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE)\
3050 ? ((entry_str *)(e))->size : hash->key_size); \
3051 }\
3052 ep += arg->offset;\
3053 es -= arg->offset;\
3054 } while (0)
3055
3056 #define COMPARE_VAL_(ap,as,bp,bs)\
3057 (arg->compar\
3058 ? arg->compar(ctx,\
3059 (grn_obj *)hash, (void *)(ap), as,\
3060 (grn_obj *)hash, (void *)(bp), bs, arg->compar_arg)\
3061 : ((arg->flags & GRN_TABLE_SORT_AS_NUMBER)\
3062 ? ((arg->flags & GRN_TABLE_SORT_AS_UNSIGNED)\
3063 ? ((arg->flags & GRN_TABLE_SORT_AS_INT64)\
3064 ? *((uint64_t *)(ap)) > *((uint64_t *)(bp))\
3065 : *((uint32_t *)(ap)) > *((uint32_t *)(bp)))\
3066 : ((arg->flags & GRN_TABLE_SORT_AS_INT64)\
3067 ? *((int64_t *)(ap)) > *((int64_t *)(bp))\
3068 : *((int32_t *)(ap)) > *((int32_t *)(bp))))\
3069 : grn_str_greater(ap, as, bp, bs)))
3070
3071 #define COMPARE_VAL(ap,as,bp,bs)\
3072 ((dir) ? COMPARE_VAL_((bp),(bs),(ap),(as)) : COMPARE_VAL_((ap),(as),(bp),(bs)))
3073
3074 inline static entry **
pack(grn_ctx * ctx,grn_hash * hash,entry ** res,grn_table_sort_optarg * arg,int dir)3075 pack(grn_ctx *ctx, grn_hash *hash, entry **res, grn_table_sort_optarg *arg, int dir)
3076 {
3077 uint32_t n;
3078 uint32_t cs, es;
3079 const uint8_t *cp, *ep;
3080 entry **head, **tail, *e, *c;
3081 grn_id id, m = HASH_CURR_MAX(hash);
3082 for (id = m >> 1;;id = (id == m) ? 1 : id + 1) {
3083 if (grn_hash_bitmap_at(ctx, hash, id)) { break; }
3084 }
3085 c = grn_hash_entry_at(ctx, hash, id, 0);
3086 if (!c) { return NULL; }
3087 PREPARE_VAL(c, cp, cs);
3088 head = res;
3089 n = *hash->n_entries - 1;
3090 tail = res + n;
3091 while (n--) {
3092 do {
3093 id = (id == m) ? 1 : id + 1;
3094 } while (!grn_hash_bitmap_at(ctx, hash, id));
3095 e = grn_hash_entry_at(ctx, hash, id, 0);
3096 if (!e) { return NULL; }
3097 PREPARE_VAL(e, ep, es);
3098 if (COMPARE_VAL(cp, cs, ep, es)) {
3099 *head++ = e;
3100 } else {
3101 *tail-- = e;
3102 }
3103 }
3104 *head = c;
3105 return *hash->n_entries > 2 ? head : NULL;
3106 }
3107
3108 inline static void
swap(entry ** a,entry ** b)3109 swap(entry **a, entry **b)
3110 {
3111 entry *c_ = *a;
3112 *a = *b;
3113 *b = c_;
3114 }
3115
3116 #define SWAP(a,ap,as,b,bp,bs) do {\
3117 const uint8_t *cp_ = ap;\
3118 uint32_t cs_ = as;\
3119 ap = bp; bp = cp_;\
3120 as = bs; bs = cs_;\
3121 swap(a,b);\
3122 } while (0)
3123
3124 inline static entry **
part(grn_ctx * ctx,entry ** b,entry ** e,grn_table_sort_optarg * arg,grn_hash * hash,int dir)3125 part(grn_ctx *ctx, entry **b, entry **e, grn_table_sort_optarg *arg, grn_hash *hash, int dir)
3126 {
3127 entry **c;
3128 const uint8_t *bp, *cp, *ep;
3129 uint32_t bs, cs, es;
3130 intptr_t d = e - b;
3131 PREPARE_VAL(*b, bp, bs);
3132 PREPARE_VAL(*e, ep, es);
3133 if (COMPARE_VAL(bp, bs, ep, es)) {
3134 SWAP(b, bp, bs, e, ep, es);
3135 }
3136 if (d < 2) { return NULL; }
3137 c = b + (d >> 1);
3138 PREPARE_VAL(*c, cp, cs);
3139 if (COMPARE_VAL(bp, bs, cp, cs)) {
3140 SWAP(b, bp, bs, c, cp, cs);
3141 } else {
3142 if (COMPARE_VAL(cp, cs, ep, es)) {
3143 SWAP(c, cp, cs, e, ep, es);
3144 }
3145 }
3146 if (d < 3) { return NULL; }
3147 b++;
3148 swap(b, c);
3149 c = b;
3150 PREPARE_VAL(*c, cp, cs);
3151 for (;;) {
3152 do {
3153 b++;
3154 PREPARE_VAL(*b, bp, bs);
3155 } while (COMPARE_VAL(cp, cs, bp, bs));
3156 do {
3157 e--;
3158 PREPARE_VAL(*e, ep, es);
3159 } while (COMPARE_VAL(ep, es, cp, cs));
3160 if (b >= e) { break; }
3161 SWAP(b, bp, bs, e, ep, es);
3162 }
3163 SWAP(c, cp, cs, e, ep, es);
3164 return e;
3165 }
3166
3167 static void
_sort(grn_ctx * ctx,entry ** head,entry ** tail,int limit,grn_table_sort_optarg * arg,grn_hash * hash,int dir)3168 _sort(grn_ctx *ctx, entry **head, entry **tail, int limit,
3169 grn_table_sort_optarg *arg, grn_hash *hash, int dir)
3170 {
3171 entry **c;
3172 if (head < tail && (c = part(ctx, head, tail, arg, hash, dir))) {
3173 intptr_t rest = limit - 1 - (c - head);
3174 _sort(ctx, head, c - 1, limit, arg, hash, dir);
3175 if (rest > 0) { _sort(ctx, c + 1, tail, (int)rest, arg, hash, dir); }
3176 }
3177 }
3178
3179 static void
sort(grn_ctx * ctx,grn_hash * hash,entry ** res,int limit,grn_table_sort_optarg * arg,int dir)3180 sort(grn_ctx *ctx,
3181 grn_hash *hash, entry **res, int limit, grn_table_sort_optarg *arg, int dir)
3182 {
3183 entry **c = pack(ctx, hash, res, arg, dir);
3184 if (c) {
3185 intptr_t rest = limit - 1 - (c - res);
3186 _sort(ctx, res, c - 1, limit, arg, hash, dir);
3187 if (rest > 0 ) {
3188 _sort(ctx, c + 1, res + *hash->n_entries - 1, (int)rest, arg, hash, dir);
3189 }
3190 }
3191 }
3192
3193 typedef struct {
3194 grn_id id;
3195 int32_t v;
3196 } val32;
3197
3198 #define PREPARE_VAL32(id,e,ep) do {\
3199 (ep)->id = id;\
3200 (ep)->v = (arg->flags & GRN_TABLE_SORT_BY_ID)\
3201 ? (int32_t) id\
3202 : (*((int32_t *)((byte *)((arg->flags & GRN_TABLE_SORT_BY_VALUE)\
3203 ? get_value(ctx, hash, (e))\
3204 : get_key(ctx, hash, (e))) + arg->offset)));\
3205 } while (0)
3206
3207 #define COMPARE_VAL32_(ap,bp) \
3208 (arg->compar\
3209 ? arg->compar(ctx,\
3210 (grn_obj *)hash, (void *)&(ap)->v, sizeof(uint32_t),\
3211 (grn_obj *)hash, (void *)&(bp)->v, sizeof(uint32_t),\
3212 arg->compar_arg)\
3213 : ((arg->flags & GRN_TABLE_SORT_AS_NUMBER)\
3214 ? ((arg->flags & GRN_TABLE_SORT_AS_UNSIGNED)\
3215 ? *((uint32_t *)&(ap)->v) > *((uint32_t *)&(bp)->v)\
3216 : *((int32_t *)&(ap)->v) > *((int32_t *)&(bp)->v))\
3217 : memcmp(&(ap)->v, &(bp)->v, sizeof(uint32_t)) > 0))
3218
3219 #define COMPARE_VAL32(ap,bp)\
3220 ((dir) ? COMPARE_VAL32_((bp),(ap)) : COMPARE_VAL32_((ap),(bp)))
3221
3222 inline static val32 *
pack_val32(grn_ctx * ctx,grn_hash * hash,val32 * res,grn_table_sort_optarg * arg,int dir)3223 pack_val32(grn_ctx *ctx, grn_hash *hash, val32 *res, grn_table_sort_optarg *arg, int dir)
3224 {
3225 uint32_t n;
3226 entry_str *e, *c;
3227 val32 *head, *tail, cr, er;
3228 grn_id id, m = HASH_CURR_MAX(hash);
3229 for (id = m >> 1;;id = (id == m) ? 1 : id + 1) {
3230 if (grn_hash_bitmap_at(ctx, hash, id)) { break; }
3231 }
3232 c = grn_hash_entry_at(ctx, hash, id, 0);
3233 if (!c) { return NULL; }
3234 PREPARE_VAL32(id, c, &cr);
3235 head = res;
3236 n = *hash->n_entries - 1;
3237 tail = res + n;
3238 while (n--) {
3239 do {
3240 id = (id == m) ? 1 : id + 1;
3241 } while (!grn_hash_bitmap_at(ctx, hash, id));
3242 e = grn_hash_entry_at(ctx, hash, id, 0);
3243 if (!e) { return NULL; }
3244 PREPARE_VAL32(id, e, &er);
3245 if (COMPARE_VAL32(&cr, &er)) {
3246 *head++ = er;
3247 } else {
3248 *tail-- = er;
3249 }
3250 }
3251 *head = cr;
3252 return *hash->n_entries > 2 ? head : NULL;
3253 }
3254
3255 #define SWAP_VAL32(ap,bp) do {\
3256 val32 cr_ = *ap;\
3257 *ap = *bp;\
3258 *bp = cr_;\
3259 } while (0)
3260
3261 inline static val32 *
part_val32(grn_ctx * ctx,val32 * b,val32 * e,grn_table_sort_optarg * arg,grn_hash * hash,int dir)3262 part_val32(grn_ctx *ctx,
3263 val32 *b, val32 *e, grn_table_sort_optarg *arg, grn_hash *hash, int dir)
3264 {
3265 val32 *c;
3266 intptr_t d = e - b;
3267 if (COMPARE_VAL32(b, e)) { SWAP_VAL32(b, e); }
3268 if (d < 2) { return NULL; }
3269 c = b + (d >> 1);
3270 if (COMPARE_VAL32(b, c)) {
3271 SWAP_VAL32(b, c);
3272 } else {
3273 if (COMPARE_VAL32(c, e)) { SWAP_VAL32(c, e); }
3274 }
3275 if (d < 3) { return NULL; }
3276 b++;
3277 SWAP_VAL32(b, c);
3278 c = b;
3279 for (;;) {
3280 do { b++; } while (COMPARE_VAL32(c, b));
3281 do { e--; } while (COMPARE_VAL32(e, c));
3282 if (b >= e) { break; }
3283 SWAP_VAL32(b, e);
3284 }
3285 SWAP_VAL32(c, e);
3286 return e;
3287 }
3288
3289 static void
_sort_val32(grn_ctx * ctx,val32 * head,val32 * tail,int limit,grn_table_sort_optarg * arg,grn_hash * hash,int dir)3290 _sort_val32(grn_ctx *ctx, val32 *head, val32 *tail, int limit,
3291 grn_table_sort_optarg *arg, grn_hash *hash, int dir)
3292 {
3293 val32 *c;
3294 if (head < tail && (c = part_val32(ctx, head, tail, arg, hash, dir))) {
3295 intptr_t rest = limit - 1 - (c - head);
3296 _sort_val32(ctx, head, c - 1, limit, arg, hash, dir);
3297 if (rest > 0) { _sort_val32(ctx, c + 1, tail, (int)rest, arg, hash, dir); }
3298 }
3299 }
3300
3301 static void
sort_val32(grn_ctx * ctx,grn_hash * hash,val32 * res,int limit,grn_table_sort_optarg * arg,int dir)3302 sort_val32(grn_ctx *ctx,
3303 grn_hash *hash, val32 *res, int limit, grn_table_sort_optarg *arg, int dir)
3304 {
3305 val32 *c = pack_val32(ctx, hash, res, arg, dir);
3306 if (c) {
3307 intptr_t rest = limit - 1 - (c - res);
3308 _sort_val32(ctx, res, c - 1, limit, arg, hash, dir);
3309 if (rest > 0 ) {
3310 _sort_val32(ctx, c + 1, res + *hash->n_entries - 1, (int)rest, arg, hash, dir);
3311 }
3312 }
3313 }
3314
3315 inline static grn_id
entry2id(grn_ctx * ctx,grn_hash * hash,entry * e)3316 entry2id(grn_ctx *ctx, grn_hash *hash, entry *e)
3317 {
3318 entry *e2;
3319 grn_id id, *ep;
3320 uint32_t i, h = e->key, s = grn_hash_calculate_step(h);
3321 for (i = h; ; i += s) {
3322 if (!(ep = grn_hash_idx_at(ctx, hash, i))) { return GRN_ID_NIL; }
3323 if (!(id = *ep)) { break; }
3324 if (id != GARBAGE) {
3325 e2 = grn_hash_entry_at(ctx, hash, id, 0);
3326 if (!e2) { return GRN_ID_NIL; }
3327 if (e2 == e) { break; }
3328 }
3329 }
3330 return id;
3331 }
3332
3333 int
grn_hash_sort(grn_ctx * ctx,grn_hash * hash,int limit,grn_array * result,grn_table_sort_optarg * optarg)3334 grn_hash_sort(grn_ctx *ctx, grn_hash *hash,
3335 int limit, grn_array *result, grn_table_sort_optarg *optarg)
3336 {
3337 entry **res;
3338 if (!result || !*hash->n_entries) { return 0; }
3339 if (grn_hash_error_if_truncated(ctx, hash) != GRN_SUCCESS) {
3340 return 0;
3341 }
3342 if (!(res = GRN_MALLOC(sizeof(entry *) * *hash->n_entries))) {
3343 GRN_LOG(ctx, GRN_LOG_ALERT, "allocation of entries failed on grn_hash_sort !");
3344 return 0;
3345 }
3346 if (limit < 0) {
3347 limit += *hash->n_entries + 1;
3348 if (limit < 0) {
3349 GRN_LOG(ctx, GRN_LOG_ALERT, "limit is too small in grn_hash_sort !");
3350 return 0;
3351 }
3352 }
3353 if (limit > *hash->n_entries) { limit = *hash->n_entries; }
3354 /* hash->limit = limit; */
3355 if (optarg) {
3356 int dir = (optarg->flags & GRN_TABLE_SORT_DESC);
3357 if ((optarg->flags & GRN_TABLE_SORT_BY_ID) ||
3358 (optarg->flags & GRN_TABLE_SORT_BY_VALUE)
3359 ? ((hash->value_size - optarg->offset) == sizeof(uint32_t))
3360 : (!(hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE)
3361 && hash->key_size == sizeof(uint32_t))) {
3362 if (sizeof(entry *) != sizeof(val32)) {
3363 GRN_FREE(res);
3364 if (!(res = GRN_MALLOC(sizeof(val32) * *hash->n_entries))) {
3365 GRN_LOG(ctx, GRN_LOG_ALERT, "allocation of entries failed on grn_hash_sort !");
3366 return 0;
3367 }
3368 }
3369 sort_val32(ctx, hash, (val32 *)res, limit, optarg, dir);
3370 {
3371 int i;
3372 grn_id *v;
3373 val32 *rp = (val32 *)res;
3374 for (i = 0; i < limit; i++, rp++) {
3375 if (!grn_array_add(ctx, result, (void **)&v)) { break; }
3376 if (!(*v = rp->id)) { break; }
3377 }
3378 GRN_FREE(res);
3379 return i;
3380 }
3381 } else {
3382 sort(ctx, hash, res, limit, optarg, dir);
3383 }
3384 } else {
3385 grn_table_sort_optarg opt = {0, NULL, NULL, NULL, 0};
3386 sort(ctx, hash, res, limit, &opt, 0);
3387 }
3388 {
3389 int i;
3390 grn_id *v;
3391 entry **rp = res;
3392 for (i = 0; i < limit; i++, rp++) {
3393 if (!grn_array_add(ctx, result, (void **)&v)) { break; }
3394 if (!(*v = entry2id(ctx, hash, *rp))) { break; }
3395 }
3396 GRN_FREE(res);
3397 return i;
3398 }
3399 }
3400
3401 void
grn_hash_check(grn_ctx * ctx,grn_hash * hash)3402 grn_hash_check(grn_ctx *ctx, grn_hash *hash)
3403 {
3404 char buf[8];
3405 grn_hash_header_common *h = hash->header.common;
3406 if (grn_hash_error_if_truncated(ctx, hash) != GRN_SUCCESS) {
3407 return;
3408 }
3409 GRN_OUTPUT_ARRAY_OPEN("RESULT", 1);
3410 GRN_OUTPUT_MAP_OPEN("SUMMARY", 26);
3411 GRN_OUTPUT_CSTR("flags");
3412 grn_itoh(h->flags, buf, 8);
3413 GRN_OUTPUT_STR(buf, 8);
3414 GRN_OUTPUT_CSTR("key_size");
3415 GRN_OUTPUT_INT64(hash->key_size);
3416 GRN_OUTPUT_CSTR("value_size");
3417 GRN_OUTPUT_INT64(hash->value_size);
3418 GRN_OUTPUT_CSTR("tokenizer");
3419 GRN_OUTPUT_INT64(h->tokenizer);
3420 GRN_OUTPUT_CSTR("normalizer");
3421 GRN_OUTPUT_INT64(h->normalizer);
3422 GRN_OUTPUT_CSTR("curr_rec");
3423 GRN_OUTPUT_INT64(h->curr_rec);
3424 GRN_OUTPUT_CSTR("curr_key_normal");
3425 GRN_OUTPUT_UINT64(h->curr_key_normal);
3426 GRN_OUTPUT_CSTR("curr_key_large");
3427 GRN_OUTPUT_UINT64(h->curr_key_large);
3428 GRN_OUTPUT_CSTR("idx_offset");
3429 GRN_OUTPUT_INT64(h->idx_offset);
3430 GRN_OUTPUT_CSTR("entry_size");
3431 GRN_OUTPUT_INT64(hash->entry_size);
3432 GRN_OUTPUT_CSTR("max_offset");
3433 GRN_OUTPUT_INT64(*hash->max_offset);
3434 GRN_OUTPUT_CSTR("n_entries");
3435 GRN_OUTPUT_INT64(*hash->n_entries);
3436 GRN_OUTPUT_CSTR("n_garbages");
3437 GRN_OUTPUT_INT64(*hash->n_garbages);
3438 GRN_OUTPUT_CSTR("lock");
3439 GRN_OUTPUT_INT64(h->lock);
3440 GRN_OUTPUT_MAP_CLOSE();
3441 GRN_OUTPUT_ARRAY_CLOSE();
3442 }
3443
3444 /* rhash : grn_hash with subrecs */
3445
3446 #ifdef USE_GRN_INDEX2
3447
3448 static uint32_t default_flags = GRN_HASH_TINY;
3449
3450 grn_rc
grn_rhash_init(grn_ctx * ctx,grn_hash * hash,grn_rec_unit record_unit,int record_size,grn_rec_unit subrec_unit,int subrec_size,unsigned int max_n_subrecs)3451 grn_rhash_init(grn_ctx *ctx, grn_hash *hash, grn_rec_unit record_unit, int record_size,
3452 grn_rec_unit subrec_unit, int subrec_size, unsigned int max_n_subrecs)
3453 {
3454 grn_rc rc;
3455 record_size = grn_rec_unit_size(record_unit, record_size);
3456 subrec_size = grn_rec_unit_size(subrec_unit, subrec_size);
3457 if (record_unit != grn_rec_userdef && subrec_unit != grn_rec_userdef) {
3458 subrec_size -= record_size;
3459 }
3460 if (!hash) { return GRN_INVALID_ARGUMENT; }
3461 if (record_size < 0) { return GRN_INVALID_ARGUMENT; }
3462 if ((default_flags & GRN_HASH_TINY)) {
3463 rc = grn_tiny_hash_init(ctx, hash, NULL, record_size,
3464 max_n_subrecs * (GRN_RSET_SCORE_SIZE + subrec_size),
3465 default_flags, GRN_ENC_NONE);
3466 } else {
3467 rc = grn_io_hash_init(ctx, hash, NULL, record_size,
3468 max_n_subrecs * (GRN_RSET_SCORE_SIZE + subrec_size),
3469 default_flags, GRN_ENC_NONE, 0);
3470 }
3471 if (rc) { return rc; }
3472 hash->record_unit = record_unit;
3473 hash->subrec_unit = subrec_unit;
3474 hash->subrec_size = subrec_size;
3475 hash->max_n_subrecs = max_n_subrecs;
3476 return rc;
3477 }
3478
3479 grn_rc
grn_rhash_fin(grn_ctx * ctx,grn_hash * hash)3480 grn_rhash_fin(grn_ctx *ctx, grn_hash *hash)
3481 {
3482 grn_rc rc;
3483 if (grn_hash_is_io_hash(hash)) {
3484 rc = grn_io_close(ctx, hash->io);
3485 } else {
3486 GRN_ASSERT(ctx == hash->ctx);
3487 rc = grn_tiny_hash_fin(ctx, hash);
3488 }
3489 return rc;
3490 }
3491
3492 inline static void
subrecs_push(byte * subrecs,int size,int n_subrecs,int score,void * body,int dir)3493 subrecs_push(byte *subrecs, int size, int n_subrecs, int score, void *body, int dir)
3494 {
3495 byte *v;
3496 int *c2;
3497 int n = n_subrecs - 1, n2;
3498 while (n) {
3499 n2 = (n - 1) >> 1;
3500 c2 = GRN_RSET_SUBRECS_NTH(subrecs,size,n2);
3501 if (GRN_RSET_SUBRECS_CMP(score, *c2, dir) > 0) { break; }
3502 GRN_RSET_SUBRECS_COPY(subrecs,size,n,c2);
3503 n = n2;
3504 }
3505 v = subrecs + n * (size + GRN_RSET_SCORE_SIZE);
3506 *((int *)v) = score;
3507 grn_memcpy(v + GRN_RSET_SCORE_SIZE, body, size);
3508 }
3509
3510 inline static void
subrecs_replace_min(byte * subrecs,int size,int n_subrecs,int score,void * body,int dir)3511 subrecs_replace_min(byte *subrecs, int size, int n_subrecs, int score, void *body, int dir)
3512 {
3513 byte *v;
3514 int n = 0, n1, n2, *c1, *c2;
3515 for (;;) {
3516 n1 = n * 2 + 1;
3517 n2 = n1 + 1;
3518 c1 = n1 < n_subrecs ? GRN_RSET_SUBRECS_NTH(subrecs,size,n1) : NULL;
3519 c2 = n2 < n_subrecs ? GRN_RSET_SUBRECS_NTH(subrecs,size,n2) : NULL;
3520 if (c1 && GRN_RSET_SUBRECS_CMP(score, *c1, dir) > 0) {
3521 if (c2 &&
3522 GRN_RSET_SUBRECS_CMP(score, *c2, dir) > 0 &&
3523 GRN_RSET_SUBRECS_CMP(*c1, *c2, dir) > 0) {
3524 GRN_RSET_SUBRECS_COPY(subrecs,size,n,c2);
3525 n = n2;
3526 } else {
3527 GRN_RSET_SUBRECS_COPY(subrecs,size,n,c1);
3528 n = n1;
3529 }
3530 } else {
3531 if (c2 && GRN_RSET_SUBRECS_CMP(score, *c2, dir) > 0) {
3532 GRN_RSET_SUBRECS_COPY(subrecs,size,n,c2);
3533 n = n2;
3534 } else {
3535 break;
3536 }
3537 }
3538 }
3539 v = subrecs + n * (size + GRN_RSET_SCORE_SIZE);
3540 grn_memcpy(v, &score, GRN_RSET_SCORE_SIZE);
3541 grn_memcpy(v + GRN_RSET_SCORE_SIZE, body, size);
3542 }
3543
3544 void
grn_rhash_add_subrec(grn_hash * s,grn_rset_recinfo * ri,int score,void * body,int dir)3545 grn_rhash_add_subrec(grn_hash *s, grn_rset_recinfo *ri, int score, void *body, int dir)
3546 {
3547 int limit = s->max_n_subrecs;
3548 ri->score += score;
3549 ri->n_subrecs += 1;
3550 if (limit) {
3551 int ssize = s->subrec_size;
3552 int n_subrecs = GRN_RSET_N_SUBRECS(ri);
3553 if (limit < n_subrecs) {
3554 if (GRN_RSET_SUBRECS_CMP(score, *ri->subrecs, dir) > 0) {
3555 subrecs_replace_min(ri->subrecs, ssize, limit, score, body, dir);
3556 }
3557 } else {
3558 subrecs_push(ri->subrecs, ssize, n_subrecs, score, body, dir);
3559 }
3560 }
3561 }
3562
3563 grn_hash *
grn_rhash_group(grn_hash * s,int limit,grn_group_optarg * optarg)3564 grn_rhash_group(grn_hash *s, int limit, grn_group_optarg *optarg)
3565 {
3566 grn_ctx *ctx = s->ctx;
3567 grn_hash *g, h;
3568 grn_rset_recinfo *ri;
3569 grn_rec_unit unit;
3570 grn_hash_cursor *c;
3571 grn_id rh;
3572 byte *key, *ekey, *gkey = NULL;
3573 int funcp, dir;
3574 unsigned int rsize;
3575 if (!s || !s->index) { return NULL; }
3576 if (optarg) {
3577 unit = grn_rec_userdef;
3578 rsize = optarg->key_size;
3579 funcp = optarg->func ? 1 : 0;
3580 dir = (optarg->mode == grn_sort_ascending) ? -1 : 1;
3581 } else {
3582 unit = grn_rec_document;
3583 rsize = grn_rec_unit_size(unit, sizeof(grn_id));
3584 funcp = 0;
3585 dir = 1;
3586 }
3587 if (funcp) {
3588 gkey = GRN_MALLOC(rsize ? rsize : 8192);
3589 if (!gkey) {
3590 GRN_LOG(ctx, GRN_LOG_ALERT, "allocation for gkey failed !");
3591 return NULL;
3592 }
3593 } else {
3594 if (s->key_size <= rsize) { return NULL; }
3595 }
3596 if (!(c = grn_hash_cursor_open(s->ctx, s, NULL, 0, NULL, -1, 0))) {
3597 GRN_LOG(ctx, GRN_LOG_ALERT, "grn_hash_cursor_open on grn_hash_group failed !");
3598 if (gkey) { GRN_FREE(gkey); }
3599 return NULL;
3600 }
3601 grn_memcpy(&h, s, sizeof(grn_hash));
3602 g = s;
3603 s = &h;
3604 if (grn_rhash_init(ctx, g, unit, rsize, s->record_unit, s->key_size, limit)) {
3605 GRN_LOG(ctx, GRN_LOG_ALERT, "grn_rhash_init in grn_hash_group failed !");
3606 grn_hash_cursor_close(s->ctx, c);
3607 if (gkey) { GRN_FREE(gkey); }
3608 return NULL;
3609 }
3610 while ((rh = grn_hash_cursor_next(ctx, c))) {
3611 grn_hash_cursor_get_key_value(ctx, c, (void **)&key, NULL, (void **)&ri);
3612 if (funcp) {
3613 if (optarg->func((grn_records *)s,
3614 (grn_recordh *)(intptr_t)rh, gkey, optarg->func_arg)) { continue; }
3615 ekey = key;
3616 } else {
3617 gkey = key;
3618 ekey = key + rsize;
3619 }
3620 {
3621 grn_rset_recinfo *gri;
3622 if (grn_hash_add(ctx, g, gkey, rsize, (void **)&gri, NULL)) {
3623 grn_rhash_add_subrec(g, gri, ri->score, ekey, dir);
3624 }
3625 }
3626 }
3627 grn_hash_cursor_close(s->ctx, c);
3628 grn_rhash_fin(s->ctx, s);
3629 if (funcp) { GRN_FREE(gkey); }
3630 return g;
3631 }
3632
3633 grn_rc
grn_rhash_subrec_info(grn_ctx * ctx,grn_hash * s,grn_id rh,int index,grn_id * rid,int * section,int * pos,int * score,void ** subrec)3634 grn_rhash_subrec_info(grn_ctx *ctx, grn_hash *s, grn_id rh, int index,
3635 grn_id *rid, int *section, int *pos, int *score, void **subrec)
3636 {
3637 grn_rset_posinfo *pi;
3638 grn_rset_recinfo *ri;
3639 int *p, unit_size = GRN_RSET_SCORE_SIZE + s->subrec_size;
3640 if (!s || !rh || index < 0) { return GRN_INVALID_ARGUMENT; }
3641 if ((unsigned int)index >= s->max_n_subrecs) { return GRN_INVALID_ARGUMENT; }
3642 {
3643 entry_str *ee;
3644 if (!grn_hash_bitmap_at(ctx, s, rh)) { return GRN_INVALID_ARGUMENT; }
3645 ee = grn_hash_entry_at(ctx, s, rh, 0);
3646 if (!ee) { return GRN_INVALID_ARGUMENT; }
3647 pi = (grn_rset_posinfo *)get_key(ctx, s, ee);
3648 ri = get_value(ctx, s, ee);
3649 if (!pi || !ri) { return GRN_INVALID_ARGUMENT; }
3650 }
3651 if (index >= ri->n_subrecs) { return GRN_INVALID_ARGUMENT; }
3652 p = (int *)(ri->subrecs + index * unit_size);
3653 if (score) { *score = p[0]; }
3654 if (subrec) { *subrec = &p[1]; }
3655 switch (s->record_unit) {
3656 case grn_rec_document :
3657 if (rid) { *rid = pi->rid; }
3658 if (section) { *section = (s->subrec_unit != grn_rec_userdef) ? p[1] : 0; }
3659 if (pos) { *pos = (s->subrec_unit == grn_rec_position) ? p[2] : 0; }
3660 break;
3661 case grn_rec_section :
3662 if (rid) { *rid = pi->rid; }
3663 if (section) { *section = pi->sid; }
3664 if (pos) { *pos = (s->subrec_unit == grn_rec_position) ? p[1] : 0; }
3665 break;
3666 default :
3667 pi = (grn_rset_posinfo *)&p[1];
3668 switch (s->subrec_unit) {
3669 case grn_rec_document :
3670 if (rid) { *rid = pi->rid; }
3671 if (section) { *section = 0; }
3672 if (pos) { *pos = 0; }
3673 break;
3674 case grn_rec_section :
3675 if (rid) { *rid = pi->rid; }
3676 if (section) { *section = pi->sid; }
3677 if (pos) { *pos = 0; }
3678 break;
3679 case grn_rec_position :
3680 if (rid) { *rid = pi->rid; }
3681 if (section) { *section = pi->sid; }
3682 if (pos) { *pos = pi->pos; }
3683 break;
3684 default :
3685 if (rid) { *rid = 0; }
3686 if (section) { *section = 0; }
3687 if (pos) { *pos = 0; }
3688 break;
3689 }
3690 break;
3691 }
3692 return GRN_SUCCESS;
3693 }
3694 #endif /* USE_GRN_INDEX2 */
3695
3696 grn_bool
grn_hash_is_large_total_key_size(grn_ctx * ctx,grn_hash * hash)3697 grn_hash_is_large_total_key_size(grn_ctx *ctx, grn_hash *hash)
3698 {
3699 return (hash->header.common->flags & GRN_OBJ_KEY_LARGE) == GRN_OBJ_KEY_LARGE;
3700 }
3701
3702 uint64_t
grn_hash_total_key_size(grn_ctx * ctx,grn_hash * hash)3703 grn_hash_total_key_size(grn_ctx *ctx, grn_hash *hash)
3704 {
3705 if (grn_hash_is_large_total_key_size(ctx, hash)) {
3706 return hash->header.common->curr_key_large;
3707 } else {
3708 return hash->header.common->curr_key_normal;
3709 }
3710 }
3711
3712 uint64_t
grn_hash_max_total_key_size(grn_ctx * ctx,grn_hash * hash)3713 grn_hash_max_total_key_size(grn_ctx *ctx, grn_hash *hash)
3714 {
3715 if (grn_hash_is_large_total_key_size(ctx, hash)) {
3716 return GRN_HASH_KEY_MAX_TOTAL_SIZE_LARGE;
3717 } else {
3718 return GRN_HASH_KEY_MAX_TOTAL_SIZE_NORMAL;
3719 }
3720 }
3721