diff options
Diffstat (limited to 'storage/mroonga/vendor/groonga/lib/hash.c')
| -rw-r--r-- | storage/mroonga/vendor/groonga/lib/hash.c | 3342 |
1 files changed, 3342 insertions, 0 deletions
diff --git a/storage/mroonga/vendor/groonga/lib/hash.c b/storage/mroonga/vendor/groonga/lib/hash.c new file mode 100644 index 00000000000..79402848f55 --- /dev/null +++ b/storage/mroonga/vendor/groonga/lib/hash.c @@ -0,0 +1,3342 @@ +/* -*- c-basic-offset: 2 -*- */ +/* + Copyright(C) 2009-2012 Brazil + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License version 2.1 as published by the Free Software Foundation. + + This library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA +*/ +#include "hash.h" +#include "output.h" +#include <string.h> +#include <limits.h> + +#include "store.h" +#include "normalizer_in.h" + +/* grn_tiny_array */ + +/* Requirements: id != GRN_ID_NIL. */ +inline static int +grn_tiny_array_get_block_id(grn_id id) +{ + int most_significant_one_bit_offset; + GRN_BIT_SCAN_REV(id, most_significant_one_bit_offset); + return most_significant_one_bit_offset >> GRN_TINY_ARRAY_FACTOR; +} + +/* Requirements: id != GRN_ID_NIL. */ +inline static void * +grn_tiny_array_get(grn_tiny_array *array, grn_id id) { + const int block_id = grn_tiny_array_get_block_id(id); + uint8_t * const block = (uint8_t *)array->blocks[block_id]; + if (block) { + const size_t offset = GRN_TINY_ARRAY_GET_OFFSET(block_id); + return block + (id - offset) * array->element_size; + } + return NULL; +} + +/* Requirements: id != GRN_ID_NIL. */ +inline static void * +grn_tiny_array_put(grn_tiny_array *array, grn_id id) { + const int block_id = grn_tiny_array_get_block_id(id); + void ** const block = &array->blocks[block_id]; + const size_t offset = GRN_TINY_ARRAY_GET_OFFSET(block_id); + if (!*block) { + grn_ctx * const ctx = array->ctx; + if (array->flags & GRN_TINY_ARRAY_THREADSAFE) { + CRITICAL_SECTION_ENTER(array->lock); + } + if (!*block) { + const size_t block_size = + GRN_TINY_ARRAY_GET_BLOCK_SIZE(block_id) * array->element_size; + if (array->flags & GRN_TINY_ARRAY_USE_MALLOC) { + if (array->flags & GRN_TINY_ARRAY_CLEAR) { + *block = GRN_CALLOC(block_size); + } else { + *block = GRN_MALLOC(block_size); + } + } else { + *block = GRN_CTX_ALLOC(ctx, block_size); + } + } + if (array->flags & GRN_TINY_ARRAY_THREADSAFE) { + CRITICAL_SECTION_LEAVE(array->lock); + } + if (!*block) { + return NULL; + } + } + if (id > array->max) { + array->max = id; + } + return (uint8_t *)*block + (id - offset) * array->element_size; +} + +inline static void * +grn_tiny_array_at_inline(grn_tiny_array *array, grn_id id) +{ + return id ? grn_tiny_array_put(array, id) : NULL; +} + +inline static void * +grn_tiny_array_next(grn_tiny_array *array) +{ + return grn_tiny_array_put(array, array->max + 1); +} + +void +grn_tiny_array_init(grn_ctx *ctx, grn_tiny_array *array, + uint16_t element_size, uint16_t flags) +{ + array->ctx = ctx; + array->max = 0; + array->element_size = element_size; + array->flags = flags; + memset(array->blocks, 0, sizeof(array->blocks)); + if (flags & GRN_TINY_ARRAY_THREADSAFE) { + CRITICAL_SECTION_INIT(array->lock); + } +} + +void +grn_tiny_array_fin(grn_tiny_array *array) +{ + int block_id; + grn_ctx * const ctx = array->ctx; + for (block_id = 0; block_id < GRN_TINY_ARRAY_NUM_BLOCKS; block_id++) { + if (array->blocks[block_id]) { + if (array->flags & GRN_TINY_ARRAY_USE_MALLOC) { + GRN_FREE(array->blocks[block_id]); + } else { + GRN_CTX_FREE(ctx, array->blocks[block_id]); + } + array->blocks[block_id] = NULL; + } + } +} + +void * +grn_tiny_array_at(grn_tiny_array *array, grn_id id) +{ + return grn_tiny_array_at_inline(array, id); +} + +grn_id +grn_tiny_array_id(grn_tiny_array *array, const void *element_address) +{ + const uint8_t * const ptr = (const uint8_t *)element_address; + uint32_t block_id, offset = 1; + for (block_id = 0; block_id < GRN_TINY_ARRAY_NUM_BLOCKS; block_id++) { + const uint32_t block_size = GRN_TINY_ARRAY_GET_BLOCK_SIZE(block_id); + const uint8_t * const block = (const uint8_t *)array->blocks[block_id]; + if (block) { + if (block <= ptr && ptr < (block + block_size * array->element_size)) { + return offset + ((ptr - block) / array->element_size); + } + } + offset += block_size; + } + return GRN_ID_NIL; +} + +/* grn_tiny_bitmap */ + +static void +grn_tiny_bitmap_init(grn_ctx *ctx, grn_tiny_bitmap *bitmap) +{ + bitmap->ctx = ctx; + memset(bitmap->blocks, 0, sizeof(bitmap->blocks)); +} + +static void +grn_tiny_bitmap_fin(grn_tiny_bitmap *bitmap) +{ + int block_id; + grn_ctx * const ctx = bitmap->ctx; + for (block_id = 0; block_id < GRN_TINY_ARRAY_NUM_BLOCKS; block_id++) { + if (bitmap->blocks[block_id]) { + GRN_CTX_FREE(ctx, bitmap->blocks[block_id]); + bitmap->blocks[block_id] = NULL; + } + } +} + +/* Requirements: bit_id != GRN_ID_NIL. */ +inline static uint8_t * +grn_tiny_bitmap_get_byte(grn_tiny_bitmap *bitmap, grn_id bit_id) { + const uint32_t byte_id = (bit_id >> 3) + 1; + const int block_id = grn_tiny_array_get_block_id(byte_id); + uint8_t * const block = (uint8_t *)bitmap->blocks[block_id]; + if (block) { + const size_t offset = GRN_TINY_ARRAY_GET_OFFSET(block_id); + return block + byte_id - offset; + } + return NULL; +} + +/* Requirements: bit_id != GRN_ID_NIL. */ +inline static uint8_t * +grn_tiny_bitmap_put_byte(grn_tiny_bitmap *bitmap, grn_id bit_id) { + const uint32_t byte_id = (bit_id >> 3) + 1; + const int block_id = grn_tiny_array_get_block_id(byte_id); + void ** const block = &bitmap->blocks[block_id]; + const size_t offset = GRN_TINY_ARRAY_GET_OFFSET(block_id); + if (!*block) { + grn_ctx * const ctx = bitmap->ctx; + *block = GRN_CTX_ALLOC(ctx, GRN_TINY_ARRAY_GET_BLOCK_SIZE(block_id)); + if (!*block) { + return NULL; + } + } + return (uint8_t *)*block + byte_id - offset; +} + +/* Requirements: bit_id != GRN_ID_NIL. */ +/* Return value: 1/0 on success, -1 on failure. */ +inline static int +grn_tiny_bitmap_get(grn_tiny_bitmap *bitmap, grn_id bit_id) +{ + uint8_t * const ptr = grn_tiny_bitmap_get_byte(bitmap, bit_id); + return ptr ? ((*ptr >> (bit_id & 7)) & 1) : -1; +} + +/* Requirements: bit_id != GRN_ID_NIL. */ +/* Return value: 1/0 on success, -1 on failure. */ +/* Note: A bitmap is extended if needed. */ +inline static int +grn_tiny_bitmap_put(grn_tiny_bitmap *bitmap, grn_id bit_id) +{ + uint8_t * const ptr = grn_tiny_bitmap_put_byte(bitmap, bit_id); + return ptr ? ((*ptr >> (bit_id & 7)) & 1) : -1; +} + +/* Requirements: bit_id != GRN_ID_NIL. */ +inline static uint8_t * +grn_tiny_bitmap_get_and_set(grn_tiny_bitmap *bitmap, grn_id bit_id, + grn_bool bit) +{ + uint8_t * const ptr = grn_tiny_bitmap_get_byte(bitmap, bit_id); + if (ptr) { + /* This branch will be removed because the given `bit' is constant. */ + if (bit) { + *ptr |= 1 << (bit_id & 7); + } else { + *ptr &= ~(1 << (bit_id & 7)); + } + } + return ptr; +} + +/* Requirements: bit_id != GRN_ID_NIL. */ +/* Note: A bitmap is extended if needed. */ +inline static uint8_t * +grn_tiny_bitmap_put_and_set(grn_tiny_bitmap *bitmap, grn_id bit_id, + grn_bool bit) +{ + uint8_t * const ptr = grn_tiny_bitmap_put_byte(bitmap, bit_id); + if (ptr) { + /* This branch will be removed because the given `bit' is constant. */ + if (bit) { + *ptr |= 1 << (bit_id & 7); + } else { + *ptr &= ~(1 << (bit_id & 7)); + } + } + return ptr; +} + +/* grn_io_array */ + +#define GRN_ARRAY_MAX (GRN_ID_MAX - 8) + +inline static void * +grn_io_array_at_inline(grn_ctx *ctx, grn_io *io, uint32_t segment_id, + uint32_t offset, int flags) +{ + void *ptr; + GRN_IO_ARRAY_AT(io, segment_id, offset, &flags, ptr); + return ptr; +} + +/* + * grn_io_array_bit_at() returns 1/0 on success, -1 on failure. + */ +inline static int +grn_io_array_bit_at(grn_ctx *ctx, grn_io *io, + uint32_t segment_id, uint32_t offset) +{ + uint8_t * const ptr = (uint8_t *)grn_io_array_at_inline( + ctx, io, segment_id, (offset >> 3) + 1, 0); + return ptr ? ((*ptr >> (offset & 7)) & 1) : -1; +} + +/* + * The following functions, grn_io_array_bit_*(), return a non-NULL pointer on + * success, a NULL pointer on failure. + */ +inline static void * +grn_io_array_bit_on(grn_ctx *ctx, grn_io *io, + uint32_t segment_id, uint32_t offset) +{ + uint8_t * const ptr = (uint8_t *)grn_io_array_at_inline( + ctx, io, segment_id, (offset >> 3) + 1, GRN_TABLE_ADD); + if (ptr) { + *ptr |= 1 << (offset & 7); + } + return ptr; +} + +inline static void * +grn_io_array_bit_off(grn_ctx *ctx, grn_io *io, + uint32_t segment_id, uint32_t offset) +{ + uint8_t * const ptr = (uint8_t *)grn_io_array_at_inline( + ctx, io, segment_id, (offset >> 3) + 1, GRN_TABLE_ADD); + if (ptr) { + *ptr &= ~(1 << (offset & 7)); + } + return ptr; +} + +inline static void * +grn_io_array_bit_flip(grn_ctx *ctx, grn_io *io, + uint32_t segment_id, uint32_t offset) +{ + uint8_t * const ptr = (uint8_t *)grn_io_array_at_inline( + ctx, io, segment_id, (offset >> 3) + 1, GRN_TABLE_ADD); + if (ptr) { + *ptr ^= 1 << (offset & 7); + } + return ptr; +} + +/* grn_table_queue */ + +static void +grn_table_queue_lock_init(grn_ctx *ctx, grn_table_queue *queue) +{ + MUTEX_INIT_SHARED(queue->mutex); + COND_INIT_SHARED(queue->cond); +} + +static void +grn_table_queue_init(grn_ctx *ctx, grn_table_queue *queue) +{ + queue->head = 0; + queue->tail = 0; + queue->cap = GRN_ARRAY_MAX; + queue->unblock_requested = GRN_FALSE; + grn_table_queue_lock_init(ctx, queue); +} + +uint32_t +grn_table_queue_size(grn_table_queue *queue) +{ + return (queue->head < queue->tail) + ? 2 * queue->cap + queue->head - queue->tail + : queue->head - queue->tail; +} + +void +grn_table_queue_head_increment(grn_table_queue *queue) +{ + if (queue->head == 2 * queue->cap) { + queue->head = 1; + } else { + queue->head++; + } +} + +void +grn_table_queue_tail_increment(grn_table_queue *queue) +{ + if (queue->tail == 2 * queue->cap) { + queue->tail = 1; + } else { + queue->tail++; + } +} + +grn_id +grn_table_queue_head(grn_table_queue *queue) +{ + return queue->head > queue->cap + ? queue->head - queue->cap + : queue->head; +} + +grn_id +grn_table_queue_tail(grn_table_queue *queue) +{ + return queue->tail > queue->cap + ? queue->tail - queue->cap + : queue->tail; +} + +/* grn_array */ + +#define GRN_ARRAY_SEGMENT_SIZE 0x400000 + +/* Header of grn_io-based grn_array. */ +struct grn_array_header { + uint32_t flags; + uint32_t curr_rec; + uint32_t value_size; + uint32_t n_entries; + uint32_t n_garbages; + grn_id garbages; + uint32_t lock; + uint32_t reserved[9]; + grn_table_queue queue; +}; + +/* + * A grn_io-based grn_array consists of the following 2 segments. + * GRN_ARRAY_VALUE_SEGMENT: stores values. + * GRN_ARRAY_BITMAP_SEGMENT: stores whether entries are valid or not. + */ +enum { + GRN_ARRAY_VALUE_SEGMENT = 0, + GRN_ARRAY_BITMAP_SEGMENT = 1 +}; + +inline static grn_bool +grn_array_is_io_array(grn_array *array) +{ + return array->io != NULL; +} + +inline static void * +grn_array_io_entry_at(grn_ctx *ctx, grn_array *array, grn_id id, int flags) +{ + return grn_io_array_at_inline(ctx, array->io, GRN_ARRAY_VALUE_SEGMENT, id, flags); +} + +inline static void * +grn_array_entry_at(grn_ctx *ctx, grn_array *array, grn_id id, int flags) +{ + if (grn_array_is_io_array(array)) { + return grn_array_io_entry_at(ctx, array, id, flags); + } else { + return grn_tiny_array_at_inline(&array->array, id); + } +} + +/* grn_array_bitmap_at() returns 1/0 on success, -1 on failure. */ +inline static int +grn_array_bitmap_at(grn_ctx *ctx, grn_array *array, grn_id id) +{ + if (grn_array_is_io_array(array)) { + return grn_io_array_bit_at(ctx, array->io, GRN_ARRAY_BITMAP_SEGMENT, id); + } else { + return grn_tiny_bitmap_put(&array->bitmap, id); + } +} + +static grn_rc +grn_array_init_tiny_array(grn_ctx *ctx, grn_array *array, const char *path, + uint32_t value_size, uint32_t flags) +{ + if (path) { + ERR(GRN_INVALID_ARGUMENT, "failed to create tiny array"); + return ctx->rc; + } + array->obj.header.flags = flags; + array->ctx = ctx; + array->value_size = value_size; + array->n_keys = 0; + array->keys = NULL; + array->n_garbages = &array->n_garbages_buf; + array->n_entries = &array->n_entries_buf; + array->n_garbages_buf = 0; + array->n_entries_buf = 0; + array->io = NULL; + array->garbages = GRN_ID_NIL; + grn_tiny_array_init(ctx, &array->array, value_size, GRN_TINY_ARRAY_CLEAR); + grn_tiny_bitmap_init(ctx, &array->bitmap); + return GRN_SUCCESS; +} + +static grn_io * +grn_array_create_io_array(grn_ctx *ctx, const char *path, uint32_t value_size) +{ + uint32_t w_of_element = 0; + grn_io_array_spec array_spec[2]; + + while ((1U << w_of_element) < value_size) { + w_of_element++; + } + + array_spec[GRN_ARRAY_VALUE_SEGMENT].w_of_element = w_of_element; + array_spec[GRN_ARRAY_VALUE_SEGMENT].max_n_segments = + 1U << (30 - (22 - w_of_element)); + array_spec[GRN_ARRAY_BITMAP_SEGMENT].w_of_element = 0; + array_spec[GRN_ARRAY_BITMAP_SEGMENT].max_n_segments = 1U << (30 - (22 + 3)); + return grn_io_create_with_array(ctx, path, sizeof(struct grn_array_header), + GRN_ARRAY_SEGMENT_SIZE, grn_io_auto, + 2, array_spec); +} + +static grn_rc +grn_array_init_io_array(grn_ctx *ctx, grn_array *array, const char *path, + uint32_t value_size, uint32_t flags) +{ + grn_io *io; + struct grn_array_header *header; + + io = grn_array_create_io_array(ctx, path, value_size); + if (!io) { + return ctx->rc; + } + grn_io_set_type(io, GRN_TABLE_NO_KEY); + + header = grn_io_header(io); + header->flags = flags; + header->curr_rec = 0; + header->lock = 0; + header->value_size = value_size; + header->n_entries = 0; + header->n_garbages = 0; + header->garbages = GRN_ID_NIL; + grn_table_queue_init(ctx, &header->queue); + array->obj.header.flags = flags; + array->ctx = ctx; + array->value_size = value_size; + array->n_keys = 0; + array->keys = NULL; + array->n_garbages = &header->n_garbages; + array->n_entries = &header->n_entries; + array->io = io; + array->header = header; + array->lock = &header->lock; + return GRN_SUCCESS; +} + +void +grn_array_queue_lock_clear(grn_ctx *ctx, grn_array *array) +{ + struct grn_array_header *header; + header = grn_io_header(array->io); + grn_table_queue_lock_init(ctx, &header->queue); +} + +grn_table_queue * +grn_array_queue(grn_ctx *ctx, grn_array *array) +{ + if (grn_array_is_io_array(array)) { + struct grn_array_header *header; + header = grn_io_header(array->io); + return &header->queue; + } else { + return NULL; + } +} + +static grn_rc +grn_array_init(grn_ctx *ctx, grn_array *array, + const char *path, uint32_t value_size, uint32_t flags) +{ + if (flags & GRN_ARRAY_TINY) { + return grn_array_init_tiny_array(ctx, array, path, value_size, flags); + } else { + return grn_array_init_io_array(ctx, array, path, value_size, flags); + } +} + +grn_array * +grn_array_create(grn_ctx *ctx, const char *path, uint32_t value_size, uint32_t flags) +{ + if (ctx) { + grn_array * const array = (grn_array *)GRN_MALLOC(sizeof(grn_array)); + if (array) { + GRN_DB_OBJ_SET_TYPE(array, GRN_TABLE_NO_KEY); + if (!grn_array_init(ctx, array, path, value_size, flags)) { + return array; + } + GRN_FREE(array); + } + } + return NULL; +} + +grn_array * +grn_array_open(grn_ctx *ctx, const char *path) +{ + if (ctx) { + grn_io * const io = grn_io_open(ctx, path, grn_io_auto); + if (io) { + struct grn_array_header * const header = grn_io_header(io); + if (grn_io_get_type(io) == GRN_TABLE_NO_KEY) { + grn_array * const array = (grn_array *)GRN_MALLOC(sizeof(grn_array)); + if (array) { + if (!(header->flags & GRN_ARRAY_TINY)) { + GRN_DB_OBJ_SET_TYPE(array, GRN_TABLE_NO_KEY); + array->obj.header.flags = header->flags; + array->ctx = ctx; + array->value_size = header->value_size; + array->n_keys = 0; + array->keys = NULL; + array->n_garbages = &header->n_garbages; + array->n_entries = &header->n_entries; + array->io = io; + array->header = header; + array->lock = &header->lock; + return array; + } else { + GRN_LOG(ctx, GRN_LOG_NOTICE, "invalid array flags. (%x)", header->flags); + } + GRN_FREE(array); + } + } else { + ERR(GRN_INVALID_FORMAT, "file type unmatch"); + } + grn_io_close(ctx, io); + } + } + return NULL; +} + +grn_rc +grn_array_close(grn_ctx *ctx, grn_array *array) +{ + grn_rc rc = GRN_SUCCESS; + if (!ctx || !array) { return GRN_INVALID_ARGUMENT; } + if (array->keys) { GRN_FREE(array->keys); } + if (grn_array_is_io_array(array)) { + rc = grn_io_close(ctx, array->io); + } else { + GRN_ASSERT(ctx == array->ctx); + grn_tiny_array_fin(&array->array); + grn_tiny_bitmap_fin(&array->bitmap); + } + GRN_FREE(array); + return rc; +} + +grn_rc +grn_array_remove(grn_ctx *ctx, const char *path) +{ + if (!ctx || !path) { return GRN_INVALID_ARGUMENT; } + return grn_io_remove(ctx, path); +} + +grn_rc +grn_array_truncate(grn_ctx *ctx, grn_array *array) +{ + grn_rc rc = GRN_SUCCESS; + char *path = NULL; + uint32_t value_size, flags; + + if (!ctx || !array) { return GRN_INVALID_ARGUMENT; } + if (grn_array_is_io_array(array)) { + const char * const io_path = grn_io_path(array->io); + if (io_path && *io_path) { + path = GRN_STRDUP(io_path); + if (!path) { + ERR(GRN_NO_MEMORY_AVAILABLE, "cannot duplicate path: <%s>", io_path); + return GRN_NO_MEMORY_AVAILABLE; + } + } + } + value_size = array->value_size; + flags = array->obj.header.flags; + + if (grn_array_is_io_array(array)) { + rc = grn_io_close(ctx, array->io); + if (!rc) { + array->io = NULL; + if (path) { + rc = grn_io_remove(ctx, path); + } + } + } + if (!rc) { + rc = grn_array_init(ctx, array, path, value_size, flags); + } + if (path) { GRN_FREE(path); } + return rc; +} + +inline static grn_id +grn_array_get_max_id(grn_array *array) +{ + return grn_array_is_io_array(array) ? array->header->curr_rec : array->array.max; +} + +inline static void * +grn_array_get_value_inline(grn_ctx *ctx, grn_array *array, grn_id id) +{ + if (!ctx || !array) { + return NULL; + } + if (*array->n_garbages) { + /* + * grn_array_bitmap_at() is a time-consuming function, so it is called only + * when there are garbages in the array. + */ + if (grn_array_bitmap_at(ctx, array, id) != 1) { + return NULL; + } + } else if (id == 0 || id > grn_array_get_max_id(array)) { + return NULL; + } + return grn_array_entry_at(ctx, array, id, 0); +} + +int +grn_array_get_value(grn_ctx *ctx, grn_array *array, grn_id id, void *valuebuf) +{ + void * const value = grn_array_get_value_inline(ctx, array, id); + if (value) { + if (valuebuf) { + memcpy(valuebuf, value, array->value_size); + } + return array->value_size; + } + return 0; +} + +void * +_grn_array_get_value(grn_ctx *ctx, grn_array *array, grn_id id) +{ + return grn_array_get_value_inline(ctx, array, id); +} + +inline static grn_rc +grn_array_set_value_inline(grn_ctx *ctx, grn_array *array, grn_id id, + const void *value, int flags) +{ + void * const entry = grn_array_entry_at(ctx, array, id, 0); + if (!entry) { + return GRN_NO_MEMORY_AVAILABLE; + } + + switch ((flags & GRN_OBJ_SET_MASK)) { + case GRN_OBJ_SET : + memcpy(entry, value, array->value_size); + return GRN_SUCCESS; + case GRN_OBJ_INCR : + switch (array->value_size) { + case sizeof(int32_t) : + *((int32_t *)entry) += *((int32_t *)value); + return GRN_SUCCESS; + case sizeof(int64_t) : + *((int64_t *)entry) += *((int64_t *)value); + return GRN_SUCCESS; + default : + return GRN_INVALID_ARGUMENT; + } + break; + case GRN_OBJ_DECR : + switch (array->value_size) { + case sizeof(int32_t) : + *((int32_t *)entry) -= *((int32_t *)value); + return GRN_SUCCESS; + case sizeof(int64_t) : + *((int64_t *)entry) -= *((int64_t *)value); + return GRN_SUCCESS; + default : + return GRN_INVALID_ARGUMENT; + } + break; + default : + /* todo : support other types. */ + return GRN_INVALID_ARGUMENT; + } +} + +grn_rc +grn_array_set_value(grn_ctx *ctx, grn_array *array, grn_id id, + const void *value, int flags) +{ + if (!ctx || !array || !value) { + return GRN_INVALID_ARGUMENT; + } + if (*array->n_garbages) { + /* + * grn_array_bitmap_at() is a time-consuming function, so it is called only + * when there are garbages in the array. + */ + if (grn_array_bitmap_at(ctx, array, id) != 1) { + return GRN_INVALID_ARGUMENT; + } + } else if (id == 0 || id > grn_array_get_max_id(array)) { + return GRN_INVALID_ARGUMENT; + } + return grn_array_set_value_inline(ctx, array, id, value, flags); +} + +grn_rc +grn_array_delete_by_id(grn_ctx *ctx, grn_array *array, grn_id id, + grn_table_delete_optarg *optarg) +{ + if (!ctx || !array) { + return GRN_INVALID_ARGUMENT; + } + if (grn_array_bitmap_at(ctx, array, id) != 1) { + return GRN_INVALID_ARGUMENT; + } + + { + grn_rc rc = GRN_SUCCESS; + /* lock */ + if (grn_array_is_io_array(array)) { + if (array->value_size >= sizeof(grn_id)) { + struct grn_array_header * const header = array->header; + void * const entry = grn_array_io_entry_at(ctx, array, id, 0); + if (!entry) { + rc = GRN_INVALID_ARGUMENT; + } else { + *((grn_id *)entry) = header->garbages; + header->garbages = id; + } + } + if (!rc) { + (*array->n_entries)--; + (*array->n_garbages)++; + /* + * The following grn_io_array_bit_off() fails iff a problem has + * occurred after the above grn_array_bitmap_at(). That is to say, + * an unexpected case. + */ + grn_io_array_bit_off(ctx, array->io, GRN_ARRAY_BITMAP_SEGMENT, id); + } + } else { + if (array->value_size >= sizeof(grn_id)) { + void * const entry = grn_tiny_array_get(&array->array, id); + if (!entry) { + rc = GRN_INVALID_ARGUMENT; + } else { + *((grn_id *)entry) = array->garbages; + array->garbages = id; + } + } + if (!rc) { + (*array->n_entries)--; + (*array->n_garbages)++; + /* + * The following grn_io_array_bit_off() fails iff a problem has + * occurred after the above grn_array_bitmap_at(). That is to say, + * an unexpected case. + */ + grn_tiny_bitmap_get_and_set(&array->bitmap, id, 0); + } + } + /* unlock */ + return rc; + } +} + +grn_id +grn_array_at(grn_ctx *ctx, grn_array *array, grn_id id) +{ + if (*array->n_garbages) { + /* + * grn_array_bitmap_at() is a time-consuming function, so it is called only + * when there are garbages in the array. + */ + if (grn_array_bitmap_at(ctx, array, id) != 1) { + return GRN_ID_NIL; + } + } else if (id > grn_array_get_max_id(array)) { + return GRN_ID_NIL; + } + return id; +} + +grn_rc +grn_array_copy_sort_key(grn_ctx *ctx, grn_array *array, + grn_table_sort_key *keys, int n_keys) +{ + array->keys = (grn_table_sort_key *)GRN_MALLOCN(grn_table_sort_key, n_keys); + if (!array->keys) { + return ctx->rc; + } + memcpy(array->keys, keys, sizeof(grn_table_sort_key) * n_keys); + array->n_keys = n_keys; + return GRN_SUCCESS; +} + +void +grn_array_cursor_close(grn_ctx *ctx, grn_array_cursor *cursor) +{ + GRN_ASSERT(cursor->ctx == ctx); + GRN_FREE(cursor); +} + +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) +{ + grn_array_cursor *cursor; + if (!array || !ctx) { return NULL; } + + cursor = (grn_array_cursor *)GRN_MALLOCN(grn_array_cursor, 1); + if (!cursor) { return NULL; } + + GRN_DB_OBJ_SET_TYPE(cursor, GRN_CURSOR_TABLE_NO_KEY); + cursor->array = array; + cursor->ctx = ctx; + cursor->obj.header.flags = flags; + cursor->obj.header.domain = GRN_ID_NIL; + + if (flags & GRN_CURSOR_DESCENDING) { + cursor->dir = -1; + if (max) { + cursor->curr_rec = max; + if (!(flags & GRN_CURSOR_LT)) { cursor->curr_rec++; } + } else { + cursor->curr_rec = grn_array_get_max_id(array) + 1; + } + if (min) { + cursor->tail = min; + if ((flags & GRN_CURSOR_GT)) { cursor->tail++; } + } else { + cursor->tail = GRN_ID_NIL + 1; + } + if (cursor->curr_rec < cursor->tail) { cursor->tail = cursor->curr_rec; } + } else { + cursor->dir = 1; + if (min) { + cursor->curr_rec = min; + if (!(flags & GRN_CURSOR_GT)) { cursor->curr_rec--; } + } else { + cursor->curr_rec = GRN_ID_NIL; + } + if (max) { + cursor->tail = max; + if ((flags & GRN_CURSOR_LT)) { cursor->tail--; } + } else { + cursor->tail = grn_array_get_max_id(array); + } + if (cursor->tail < cursor->curr_rec) { cursor->tail = cursor->curr_rec; } + } + + if (*array->n_garbages) { + while (offset && cursor->curr_rec != cursor->tail) { + cursor->curr_rec += cursor->dir; + if (grn_array_bitmap_at(ctx, cursor->array, cursor->curr_rec) == 1) { + offset--; + } + } + } else { + cursor->curr_rec += cursor->dir * offset; + } + cursor->rest = (limit < 0) ? GRN_ARRAY_MAX : limit; + return cursor; +} + +grn_id +grn_array_cursor_next(grn_ctx *ctx, grn_array_cursor *cursor) +{ + if (cursor && cursor->rest) { + while (cursor->curr_rec != cursor->tail) { + cursor->curr_rec += cursor->dir; + if (*cursor->array->n_garbages) { + if (grn_array_bitmap_at(ctx, cursor->array, cursor->curr_rec) != 1) { + continue; + } + } + cursor->rest--; + return cursor->curr_rec; + } + } + return GRN_ID_NIL; +} + +grn_id +grn_array_next(grn_ctx *ctx, grn_array *array, grn_id id) +{ + const grn_id max_id = grn_array_get_max_id(array); + while (++id <= max_id) { + if (!*array->n_garbages || + grn_array_bitmap_at(ctx, array, id) == 1) { + return id; + } + } + return GRN_ID_NIL; +} + +int +grn_array_cursor_get_value(grn_ctx *ctx, grn_array_cursor *cursor, void **value) +{ + if (cursor && value) { + void * const entry = grn_array_entry_at(ctx, cursor->array, cursor->curr_rec, 0); + if (entry) { + *value = entry; + return cursor->array->value_size; + } + } + return 0; +} + +grn_rc +grn_array_cursor_set_value(grn_ctx *ctx, grn_array_cursor *cursor, + const void *value, int flags) +{ + return grn_array_set_value_inline(ctx, cursor->array, cursor->curr_rec, + value, flags); +} + +grn_rc +grn_array_cursor_delete(grn_ctx *ctx, grn_array_cursor *cursor, + grn_table_delete_optarg *optarg) +{ + return grn_array_delete_by_id(ctx, cursor->array, cursor->curr_rec, optarg); +} + +inline static grn_id +grn_array_add_to_tiny_array(grn_ctx *ctx, grn_array *array, void **value) +{ + grn_id id = array->garbages; + void *entry; + if (id) { + /* These operations fail iff the array is broken. */ + entry = grn_tiny_array_get(&array->array, id); + if (!entry) { + return GRN_ID_NIL; + } + array->garbages = *(grn_id *)entry; + memset(entry, 0, array->value_size); + (*array->n_garbages)--; + if (!grn_tiny_bitmap_get_and_set(&array->bitmap, id, 1)) { + /* Actually, it is difficult to recover from this error. */ + *(grn_id *)entry = array->garbages; + array->garbages = id; + (*array->n_garbages)++; + return GRN_ID_NIL; + } + } else { + id = array->array.max + 1; + if (!grn_tiny_bitmap_put_and_set(&array->bitmap, id, 1)) { + return GRN_ID_NIL; + } + entry = grn_tiny_array_put(&array->array, id); + if (!entry) { + grn_tiny_bitmap_get_and_set(&array->bitmap, id, 0); + return GRN_ID_NIL; + } + array->array.max = id; + } + (*array->n_entries)++; + if (value) { *value = entry; } + return id; +} + +inline static grn_id +grn_array_add_to_io_array(grn_ctx *ctx, grn_array *array, void **value) +{ + struct grn_array_header * const header = array->header; + grn_id id = header->garbages; + void *entry; + if (id) { + /* These operations fail iff the array is broken. */ + entry = grn_array_io_entry_at(ctx, array, id, GRN_TABLE_ADD); + if (!entry) { + return GRN_ID_NIL; + } + header->garbages = *(grn_id *)entry; + memset(entry, 0, header->value_size); + (*array->n_garbages)--; + if (!grn_io_array_bit_on(ctx, array->io, GRN_ARRAY_BITMAP_SEGMENT, id)) { + /* Actually, it is difficult to recover from this error. */ + *(grn_id *)entry = array->garbages; + array->garbages = id; + (*array->n_garbages)++; + return GRN_ID_NIL; + } + } else { + if (header->curr_rec >= GRN_ARRAY_MAX) { return GRN_ID_NIL; } + id = header->curr_rec + 1; + if (!grn_io_array_bit_on(ctx, array->io, GRN_ARRAY_BITMAP_SEGMENT, id)) { + return GRN_ID_NIL; + } + entry = grn_array_io_entry_at(ctx, array, id, GRN_TABLE_ADD); + if (!entry) { + grn_io_array_bit_off(ctx, array->io, GRN_ARRAY_BITMAP_SEGMENT, id); + return GRN_ID_NIL; + } + header->curr_rec = id; + } + (*array->n_entries)++; + if (value) { *value = entry; } + return id; +} + +void +grn_array_clear_curr_rec(grn_ctx *ctx, grn_array *array) +{ + struct grn_array_header * const header = array->header; + header->curr_rec = GRN_ID_NIL; +} + +grn_id +grn_array_add(grn_ctx *ctx, grn_array *array, void **value) +{ + if (ctx && array) { + if (grn_array_is_io_array(array)) { + return grn_array_add_to_io_array(ctx, array, value); + } else { + return grn_array_add_to_tiny_array(ctx, array, value); + } + } + return GRN_ID_NIL; +} + +grn_id +grn_array_push(grn_ctx *ctx, grn_array *array, + void (*func)(grn_ctx *, grn_array *, grn_id, void *), + void *func_arg) +{ + grn_id id = GRN_ID_NIL; + grn_table_queue *queue = grn_array_queue(ctx, array); + if (queue) { + MUTEX_LOCK(queue->mutex); + if (grn_table_queue_head(queue) == queue->cap) { + grn_array_clear_curr_rec(ctx, array); + } + id = grn_array_add(ctx, array, NULL); + if (func) { + func(ctx, array, id, func_arg); + } + if (grn_table_queue_size(queue) == queue->cap) { + grn_table_queue_tail_increment(queue); + } + grn_table_queue_head_increment(queue); + COND_SIGNAL(queue->cond); + MUTEX_UNLOCK(queue->mutex); + } else { + ERR(GRN_OPERATION_NOT_SUPPORTED, "only persistent arrays support push"); + } + return id; +} + +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) +{ + grn_id id = GRN_ID_NIL; + grn_table_queue *queue = grn_array_queue(ctx, array); + if (queue) { + MUTEX_LOCK(queue->mutex); + queue->unblock_requested = GRN_FALSE; + while (grn_table_queue_size(queue) == 0) { + if (!blockp || queue->unblock_requested) { + MUTEX_UNLOCK(queue->mutex); + GRN_OUTPUT_BOOL(0); + return id; + } + COND_WAIT(queue->cond, queue->mutex); + } + grn_table_queue_tail_increment(queue); + id = grn_table_queue_tail(queue); + if (func) { + func(ctx, array, id, func_arg); + } + MUTEX_UNLOCK(queue->mutex); + } else { + ERR(GRN_OPERATION_NOT_SUPPORTED, "only persistent arrays support pull"); + } + return id; +} + +void +grn_array_unblock(grn_ctx *ctx, grn_array *array) +{ + grn_table_queue *queue = grn_array_queue(ctx, array); + if (!queue) { + return; + } + + queue->unblock_requested = GRN_TRUE; + COND_BROADCAST(queue->cond); +} + +/* grn_hash : hash table */ + +#define GRN_HASH_MAX_SEGMENT 0x400 +#define GRN_HASH_HEADER_SIZE 0x9000 +#define GRN_HASH_SEGMENT_SIZE 0x400000 +#define W_OF_KEY_IN_A_SEGMENT 22 +#define IDX_MASK_IN_A_SEGMENT 0xfffff + +typedef struct { + uint8_t key[4]; + uint8_t value[1]; +} grn_plain_hash_entry; + +typedef struct { + uint32_t hash_value; + uint8_t key_and_value[1]; +} grn_rich_hash_entry; + +typedef struct { + uint32_t hash_value; + uint16_t flag; + uint16_t key_size; + union { + uint8_t buf[sizeof(uint32_t)]; + uint32_t offset; + } key; + uint8_t value[1]; +} grn_io_hash_entry; + +typedef struct { + uint32_t hash_value; + uint16_t flag; + uint16_t key_size; + union { + uint8_t buf[sizeof(void *)]; + void *ptr; + } key; + uint8_t value[1]; +} grn_tiny_hash_entry; + +/* + * hash_value is valid even if the entry is grn_plain_hash_entry. In this case, + * its hash_value equals its key. + * flag, key_size and key.buf are valid if the entry has a variable length key. + */ +typedef struct { + uint32_t hash_value; + uint16_t flag; + uint16_t key_size; +} grn_hash_entry_header; + +typedef union { + uint32_t hash_value; + grn_hash_entry_header header; + grn_plain_hash_entry plain_entry; + grn_rich_hash_entry rich_entry; + grn_io_hash_entry io_entry; + grn_tiny_hash_entry tiny_entry; +} grn_hash_entry; + +typedef struct { + uint32_t key; + uint8_t dummy[1]; +} entry; + +typedef struct { + uint32_t key; + uint16_t flag; + uint16_t size; + uint32_t str; + uint8_t dummy[1]; +} entry_str; + +typedef struct { + uint32_t key; + uint16_t flag; + uint16_t size; + char *str; + uint8_t dummy[1]; +} entry_astr; + +#define LOGICAL_MAX_SEGMENT ((GRN_HASH_MAX_SEGMENT) * 4) + +enum { + GRN_HASH_KEY_SEGMENT = 0, + GRN_HASH_ENTRY_SEGMENT = 1, + GRN_HASH_INDEX_SEGMENT = 2, + GRN_HASH_BITMAP_SEGMENT = 3 +}; + +inline static grn_bool +grn_hash_is_io_hash(grn_hash *hash) +{ + return hash->io != NULL; +} + +inline static void * +grn_io_hash_entry_at(grn_ctx *ctx, grn_hash *hash, grn_id id, int flags) +{ + return grn_io_array_at_inline(ctx, hash->io, GRN_HASH_ENTRY_SEGMENT, id, flags); +} + +/* todo : error handling */ +inline static void * +grn_hash_entry_at(grn_ctx *ctx, grn_hash *hash, grn_id id, int flags) +{ + if (grn_hash_is_io_hash(hash)) { + return grn_io_hash_entry_at(ctx, hash, id, flags); + } else { + return grn_tiny_array_at_inline(&hash->a, id); + } +} + +inline static grn_bool +grn_hash_bitmap_at(grn_ctx *ctx, grn_hash *hash, grn_id id) +{ + if (grn_hash_is_io_hash(hash)) { + return grn_io_array_bit_at(ctx, hash->io, GRN_HASH_BITMAP_SEGMENT, id) == 1; + } else { + return grn_tiny_bitmap_put(&hash->bitmap, id) == 1; + } +} + +inline static grn_id * +grn_io_hash_idx_at(grn_ctx *ctx, grn_hash *hash, grn_id id) +{ + return grn_io_array_at_inline(ctx, hash->io, GRN_HASH_INDEX_SEGMENT, + id, GRN_TABLE_ADD); +} + +inline static grn_id * +grn_hash_idx_at(grn_ctx *ctx, grn_hash *hash, grn_id id) +{ + if (grn_hash_is_io_hash(hash)) { + id = (id & *hash->max_offset) + hash->header->idx_offset; + return grn_io_hash_idx_at(ctx, hash, id); + } else { + return hash->index + (id & *hash->max_offset); + } +} + +inline static void * +grn_io_hash_key_at(grn_ctx *ctx, grn_hash *hash, uint32_t pos) +{ + return grn_io_array_at_inline(ctx, hash->io, GRN_HASH_KEY_SEGMENT, + pos, GRN_TABLE_ADD); +} + +#define HASH_IMMEDIATE 1 + +#define MAX_INDEX_SIZE ((GRN_HASH_MAX_SEGMENT * (IDX_MASK_IN_A_SEGMENT + 1)) >> 1) + +inline static uint16_t +grn_hash_entry_get_key_size(grn_hash *hash, grn_hash_entry *entry) +{ + if (hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) { + return entry->header.key_size; + } else { + return hash->key_size; + } +} + +inline static char * +grn_hash_entry_get_key(grn_ctx *ctx, grn_hash *hash, grn_hash_entry *entry) +{ + if (hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) { + if (grn_hash_is_io_hash(hash)) { + if (entry->io_entry.flag & HASH_IMMEDIATE) { + return (char *)entry->io_entry.key.buf; + } else { + return (char *)grn_io_hash_key_at(ctx, hash, entry->io_entry.key.offset); + } + } else { + if (entry->tiny_entry.flag & HASH_IMMEDIATE) { + return (char *)entry->tiny_entry.key.buf; + } else { + return entry->tiny_entry.key.ptr; + } + } + } else { + if (hash->key_size == sizeof(uint32_t)) { + return (char *)entry->plain_entry.key; + } else { + return (char *)entry->rich_entry.key_and_value; + } + } +} + +inline static void * +grn_hash_entry_get_value(grn_hash *hash, grn_hash_entry *entry) +{ + if (hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) { + if (grn_hash_is_io_hash(hash)) { + return entry->io_entry.value; + } else { + return entry->tiny_entry.value; + } + } else { + if (hash->key_size == sizeof(uint32_t)) { + return entry->plain_entry.value; + } else { + return entry->rich_entry.key_and_value + hash->key_size; + } + } +} + +inline static grn_rc +grn_io_hash_entry_put_key(grn_ctx *ctx, grn_hash *hash, + grn_io_hash_entry *entry, + const void *key, unsigned int key_size) +{ + uint32_t key_offset; + if (entry->key_size) { + key_offset = entry->key.offset; + } else { + uint32_t segment_id; + if (key_size >= GRN_HASH_SEGMENT_SIZE) { + return GRN_INVALID_ARGUMENT; + } + key_offset = hash->header->curr_key; + segment_id = (key_offset + key_size) >> W_OF_KEY_IN_A_SEGMENT; + if ((key_offset >> W_OF_KEY_IN_A_SEGMENT) != segment_id) { + key_offset = hash->header->curr_key = segment_id << W_OF_KEY_IN_A_SEGMENT; + } + hash->header->curr_key += key_size; + entry->key.offset = key_offset; + } + + { + void * const key_ptr = grn_io_hash_key_at(ctx, hash, key_offset); + if (!key_ptr) { + return GRN_NO_MEMORY_AVAILABLE; + } + memcpy(key_ptr, key, key_size); + } + return GRN_SUCCESS; +} + +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) +{ + if (hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) { + if (grn_hash_is_io_hash(hash)) { + if (key_size <= sizeof(entry->io_entry.key.buf)) { + memcpy(entry->io_entry.key.buf, key, key_size); + entry->io_entry.flag = HASH_IMMEDIATE; + } else { + const grn_rc rc = + grn_io_hash_entry_put_key(ctx, hash, (grn_io_hash_entry *)entry, + key, key_size); + if (rc) { + return rc; + } + entry->io_entry.flag = 0; + } + entry->io_entry.hash_value = hash_value; + entry->io_entry.key_size = key_size; + } else { + if (key_size <= sizeof(entry->tiny_entry.key.buf)) { + memcpy(entry->tiny_entry.key.buf, key, key_size); + entry->tiny_entry.flag = HASH_IMMEDIATE; + } else { + grn_ctx * const ctx = hash->ctx; + entry->tiny_entry.key.ptr = GRN_CTX_ALLOC(ctx, key_size); + if (!entry->tiny_entry.key.ptr) { + return GRN_NO_MEMORY_AVAILABLE; + } + memcpy(entry->tiny_entry.key.ptr, key, key_size); + entry->tiny_entry.flag = 0; + } + entry->tiny_entry.hash_value = hash_value; + entry->tiny_entry.key_size = key_size; + } + } else { + if (hash->key_size == sizeof(uint32_t)) { + *(uint32_t *)entry->plain_entry.key = hash_value; + } else { + entry->rich_entry.hash_value = hash_value; + memcpy(entry->rich_entry.key_and_value, key, key_size); + } + } + return GRN_SUCCESS; +} + +/* + * grn_hash_entry_compare_key() returns GRN_TRUE if the entry key equals the + * specified key, or GRN_FALSE otherwise. + */ +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) +{ + if (hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) { + if (entry->hash_value != hash_value || + entry->header.key_size != key_size) { + return GRN_FALSE; + } + if (grn_hash_is_io_hash(hash)) { + if (entry->io_entry.flag & HASH_IMMEDIATE) { + return !memcmp(key, entry->io_entry.key.buf, key_size); + } else { + const void * const entry_key_ptr = + grn_io_hash_key_at(ctx, hash, entry->io_entry.key.offset); + return !memcmp(key, entry_key_ptr, key_size); + } + } else { + if (entry->tiny_entry.flag & HASH_IMMEDIATE) { + return !memcmp(key, entry->tiny_entry.key.buf, key_size); + } else { + return !memcmp(key, entry->tiny_entry.key.ptr, key_size); + } + } + } else { + if (entry->hash_value != hash_value) { + return GRN_FALSE; + } + if (key_size == sizeof(uint32_t)) { + return GRN_TRUE; + } else { + return !memcmp(key, entry->rich_entry.key_and_value, key_size); + } + } +} + +inline static char * +get_key(grn_ctx *ctx, grn_hash *hash, entry_str *n) +{ + return grn_hash_entry_get_key(ctx, hash, (grn_hash_entry *)n); +} + +inline static void * +get_value(grn_hash *hash, entry_str *n) +{ + return grn_hash_entry_get_value(hash, (grn_hash_entry *)n); +} + +inline static grn_rc +put_key(grn_ctx *ctx, grn_hash *hash, entry_str *n, uint32_t h, + const char *key, unsigned int len) +{ + return grn_hash_entry_put_key(ctx, hash, (grn_hash_entry *)n, h, key, len); +} + +inline static int +match_key(grn_ctx *ctx, grn_hash *hash, entry_str *ee, uint32_t h, + const char *key, unsigned int len) +{ + return grn_hash_entry_compare_key(ctx, hash, (grn_hash_entry *)ee, + h, key, len); +} + +#define GARBAGE (0xffffffff) + +inline static uint32_t +grn_io_hash_calculate_entry_size(uint32_t key_size, uint32_t value_size, + uint32_t flags) +{ + if (flags & GRN_OBJ_KEY_VAR_SIZE) { + return (uintptr_t)((grn_io_hash_entry *)0)->value + value_size; + } else { + if (key_size == sizeof(uint32_t)) { + return (uintptr_t)((grn_plain_hash_entry *)0)->value + value_size; + } else { + return (uintptr_t)((grn_rich_hash_entry *)0)->key_and_value + + key_size + value_size; + } + } +} + +static grn_io * +grn_io_hash_create_io(grn_ctx *ctx, const char *path, uint32_t entry_size) +{ + uint32_t w_of_element = 0; + grn_io_array_spec array_spec[4]; + + while ((1U << w_of_element) < entry_size) { + w_of_element++; + } + + array_spec[GRN_HASH_KEY_SEGMENT].w_of_element = 0; + array_spec[GRN_HASH_KEY_SEGMENT].max_n_segments = 0x400; + array_spec[GRN_HASH_ENTRY_SEGMENT].w_of_element = w_of_element; + array_spec[GRN_HASH_ENTRY_SEGMENT].max_n_segments = + 1U << (30 - (22 - w_of_element)); + array_spec[GRN_HASH_INDEX_SEGMENT].w_of_element = 2; + array_spec[GRN_HASH_INDEX_SEGMENT].max_n_segments = 1U << (30 - (22 - 2)); + array_spec[GRN_HASH_BITMAP_SEGMENT].w_of_element = 0; + array_spec[GRN_HASH_BITMAP_SEGMENT].max_n_segments = 1U << (30 - (22 + 3)); + return grn_io_create_with_array(ctx, path, GRN_HASH_HEADER_SIZE, + GRN_HASH_SEGMENT_SIZE, + grn_io_auto, 4, array_spec); +} + +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) +{ + grn_io *io; + struct grn_hash_header *header; + uint32_t entry_size, max_offset; + + entry_size = grn_io_hash_calculate_entry_size(key_size, value_size, flags); + + io = grn_io_hash_create_io(ctx, path, entry_size); + if (!io) { + return GRN_NO_MEMORY_AVAILABLE; + } + grn_io_set_type(io, GRN_TABLE_HASH_KEY); + + max_offset = IDX_MASK_IN_A_SEGMENT + 1; + while (max_offset < init_size * 2) { + max_offset *= 2; + } + max_offset--; + + if (encoding == GRN_ENC_DEFAULT) { + encoding = ctx->encoding; + } + + header = grn_io_header(io); + header->flags = flags; + header->encoding = encoding; + header->key_size = key_size; + header->curr_rec = 0; + header->curr_key = 0; + header->lock = 0; + header->idx_offset = 0; + header->value_size = value_size; + header->entry_size = entry_size; + header->max_offset = max_offset; + header->n_entries = 0; + header->n_garbages = 0; + header->tokenizer = GRN_ID_NIL; + if (header->flags & GRN_OBJ_KEY_NORMALIZE) { + header->flags &= ~GRN_OBJ_KEY_NORMALIZE; + hash->normalizer = grn_ctx_get(ctx, GRN_NORMALIZER_AUTO_NAME, -1); + header->normalizer = grn_obj_id(ctx, hash->normalizer); + } else { + hash->normalizer = NULL; + header->normalizer = GRN_ID_NIL; + } + grn_table_queue_init(ctx, &header->queue); + + hash->obj.header.flags = header->flags; + hash->ctx = ctx; + hash->key_size = key_size; + hash->encoding = encoding; + hash->value_size = value_size; + hash->entry_size = entry_size; + hash->n_garbages = &header->n_garbages; + hash->n_entries = &header->n_entries; + hash->max_offset = &header->max_offset; + hash->io = io; + hash->header = header; + hash->lock = &header->lock; + hash->tokenizer = NULL; + return GRN_SUCCESS; +} + +#define INITIAL_INDEX_SIZE 256U + +static uint32_t +grn_tiny_hash_calculate_entry_size(uint32_t key_size, uint32_t value_size, + uint32_t flags) +{ + uint32_t entry_size; + if (flags & GRN_OBJ_KEY_VAR_SIZE) { + entry_size = (uintptr_t)((grn_tiny_hash_entry *)0)->value + value_size; + } else { + if (key_size == sizeof(uint32_t)) { + entry_size = (uintptr_t)((grn_plain_hash_entry *)0)->value + value_size; + } else { + entry_size = (uintptr_t)((grn_rich_hash_entry *)0)->key_and_value + + key_size + value_size; + } + } + if (entry_size != sizeof(uint32_t)) { + entry_size += sizeof(uintptr_t) - 1; + entry_size &= ~(sizeof(uintptr_t) - 1); + } + return entry_size; +} + +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) +{ + uint32_t entry_size; + + if (path) { + return GRN_INVALID_ARGUMENT; + } + hash->index = GRN_CTX_ALLOC(ctx, INITIAL_INDEX_SIZE * sizeof(grn_id)); + if (!hash->index) { + return GRN_NO_MEMORY_AVAILABLE; + } + + entry_size = grn_tiny_hash_calculate_entry_size(key_size, value_size, flags); + hash->obj.header.flags = flags; + hash->ctx = ctx; + hash->key_size = key_size; + hash->encoding = encoding; + hash->value_size = value_size; + hash->entry_size = entry_size; + hash->n_garbages = &hash->n_garbages_; + hash->n_entries = &hash->n_entries_; + hash->max_offset = &hash->max_offset_; + hash->max_offset_ = INITIAL_INDEX_SIZE - 1; + hash->io = NULL; + hash->n_garbages_ = 0; + hash->n_entries_ = 0; + hash->garbages = GRN_ID_NIL; + hash->tokenizer = NULL; + hash->normalizer = NULL; + grn_tiny_array_init(ctx, &hash->a, entry_size, GRN_TINY_ARRAY_CLEAR); + grn_tiny_bitmap_init(ctx, &hash->bitmap); + return GRN_SUCCESS; +} + +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) +{ + if (flags & GRN_HASH_TINY) { + return grn_tiny_hash_init(ctx, hash, path, key_size, value_size, + flags, ctx->encoding); + } else { + return grn_io_hash_init(ctx, hash, path, key_size, value_size, + flags, ctx->encoding, 0); + } +} + +grn_hash * +grn_hash_create(grn_ctx *ctx, const char *path, uint32_t key_size, uint32_t value_size, + uint32_t flags) +{ + grn_hash *hash; + if (!ctx) { + return NULL; + } + if (key_size > GRN_HASH_MAX_KEY_SIZE) { + return NULL; + } + hash = (grn_hash *)GRN_MALLOC(sizeof(grn_hash)); + if (!hash) { + return NULL; + } + GRN_DB_OBJ_SET_TYPE(hash, GRN_TABLE_HASH_KEY); + if (grn_hash_init(ctx, hash, path, key_size, value_size, flags)) { + GRN_FREE(hash); + return NULL; + } + return hash; +} + +grn_hash * +grn_hash_open(grn_ctx *ctx, const char *path) +{ + if (ctx) { + grn_io * const io = grn_io_open(ctx, path, grn_io_auto); + if (io) { + struct grn_hash_header * const header = grn_io_header(io); + if (grn_io_get_type(io) == GRN_TABLE_HASH_KEY) { + grn_hash * const hash = (grn_hash *)GRN_MALLOC(sizeof(grn_hash)); + if (hash) { + if (!(header->flags & GRN_HASH_TINY)) { + GRN_DB_OBJ_SET_TYPE(hash, GRN_TABLE_HASH_KEY); + hash->ctx = ctx; + hash->key_size = header->key_size; + hash->encoding = header->encoding; + hash->value_size = header->value_size; + hash->entry_size = header->entry_size; + hash->n_garbages = &header->n_garbages; + hash->n_entries = &header->n_entries; + hash->max_offset = &header->max_offset; + hash->io = io; + hash->header = header; + hash->lock = &header->lock; + hash->tokenizer = grn_ctx_at(ctx, header->tokenizer); + if (header->flags & GRN_OBJ_KEY_NORMALIZE) { + header->flags &= ~GRN_OBJ_KEY_NORMALIZE; + hash->normalizer = grn_ctx_get(ctx, GRN_NORMALIZER_AUTO_NAME, -1); + header->normalizer = grn_obj_id(ctx, hash->normalizer); + } else { + hash->normalizer = grn_ctx_at(ctx, header->normalizer); + } + hash->obj.header.flags = header->flags; + return hash; + } else { + GRN_LOG(ctx, GRN_LOG_NOTICE, + "invalid hash flag. (%x)", header->flags); + } + GRN_FREE(hash); + } + } else { + ERR(GRN_INVALID_FORMAT, "file type unmatch"); + } + grn_io_close(ctx, io); + } + } + return NULL; +} + +static grn_rc +grn_tiny_hash_fin(grn_ctx *ctx, grn_hash *hash) +{ + if (!hash->index) { + return GRN_INVALID_ARGUMENT; + } + + if (hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) { + uint32_t num_remaining_entries = *hash->n_entries; + grn_id *hash_ptr; + for (hash_ptr = hash->index; num_remaining_entries; hash_ptr++) { + const grn_id id = *hash_ptr; + if (id && id != GARBAGE) { + grn_tiny_hash_entry * const entry = + (grn_tiny_hash_entry *)grn_tiny_array_get(&hash->a, id); + GRN_ASSERT(entry); + num_remaining_entries--; + if (entry && !(entry->flag & HASH_IMMEDIATE)) { + GRN_CTX_FREE(ctx, entry->key.ptr); + } + } + } + } + grn_tiny_array_fin(&hash->a); + grn_tiny_bitmap_fin(&hash->bitmap); + GRN_CTX_FREE(ctx, hash->index); + return GRN_SUCCESS; +} + +grn_rc +grn_hash_close(grn_ctx *ctx, grn_hash *hash) +{ + grn_rc rc; + if (!ctx || !hash) { return GRN_INVALID_ARGUMENT; } + if (grn_hash_is_io_hash(hash)) { + rc = grn_io_close(ctx, hash->io); + } else { + GRN_ASSERT(ctx == hash->ctx); + rc = grn_tiny_hash_fin(ctx, hash); + } + GRN_FREE(hash); + return rc; +} + +grn_rc +grn_hash_remove(grn_ctx *ctx, const char *path) +{ + if (!ctx || !path) { return GRN_INVALID_ARGUMENT; } + return grn_io_remove(ctx, path); +} + +grn_rc +grn_hash_truncate(grn_ctx *ctx, grn_hash *hash) +{ + grn_rc rc = GRN_SUCCESS; + char *path = NULL; + uint32_t key_size, value_size, flags; + + if (!ctx || !hash) { + return GRN_INVALID_ARGUMENT; + } + + if (grn_hash_is_io_hash(hash)) { + const char * const io_path = grn_io_path(hash->io); + if (io_path && *io_path) { + path = GRN_STRDUP(io_path); + if (!path) { + ERR(GRN_NO_MEMORY_AVAILABLE, "cannot duplicate path: <%s>", io_path); + return GRN_NO_MEMORY_AVAILABLE; + } + } + } + key_size = hash->key_size; + value_size = hash->value_size; + flags = hash->obj.header.flags; + + if (grn_hash_is_io_hash(hash)) { + rc = grn_io_close(ctx, hash->io); + if (!rc) { + hash->io = NULL; + if (path) { + rc = grn_io_remove(ctx, path); + } + } + } + if (!rc) { + rc = grn_hash_init(ctx, hash, path, key_size, value_size, flags); + } + if (path) { + GRN_FREE(path); + } + return rc; +} + +inline static uint32_t +grn_hash_calculate_hash_value(const void *ptr, uint32_t size) +{ + uint32_t i; + uint32_t hash_value = 0; + for (i = 0; i < size; i++) { + hash_value = (hash_value * 1021) + ((const uint8_t *)ptr)[i]; + } + return hash_value; +} + +inline static uint32_t +grn_hash_calculate_step(uint32_t hash_value) +{ + return (hash_value >> 2) | 0x1010101; +} + +static grn_rc +grn_hash_reset(grn_ctx *ctx, grn_hash *hash, uint32_t expected_n_entries) +{ + grn_id *new_index = NULL; + uint32_t new_index_size = INITIAL_INDEX_SIZE; + grn_id *src_ptr = NULL, *dest_ptr = NULL; + uint32_t src_offset = 0, dest_offset = 0; + const uint32_t n_entries = *hash->n_entries; + const uint32_t max_offset = *hash->max_offset; + + if (!expected_n_entries) { + expected_n_entries = n_entries * 2; + } + if (expected_n_entries > INT_MAX) { + return GRN_NO_MEMORY_AVAILABLE; + } + while (new_index_size <= expected_n_entries) { + new_index_size *= 2; + } + + if (grn_hash_is_io_hash(hash)) { + uint32_t i; + src_offset = hash->header->idx_offset; + dest_offset = MAX_INDEX_SIZE - src_offset; + for (i = 0; i < new_index_size; i += (IDX_MASK_IN_A_SEGMENT + 1)) { + /* + * The following grn_io_hash_idx_at() allocates memory for a new segment + * and returns a pointer to the new segment. It's actually bad manners + * but faster than calling grn_io_hash_idx_at() for each element. + */ + dest_ptr = grn_io_hash_idx_at(ctx, hash, i + dest_offset); + if (!dest_ptr) { + return GRN_NO_MEMORY_AVAILABLE; + } + memset(dest_ptr, 0, GRN_HASH_SEGMENT_SIZE); + } + } else { + GRN_ASSERT(ctx == hash->ctx); + new_index = GRN_CTX_ALLOC(ctx, new_index_size * sizeof(grn_id)); + if (!new_index) { + return GRN_NO_MEMORY_AVAILABLE; + } + src_ptr = hash->index; + } + + { + uint32_t src_pos, count; + const uint32_t new_max_offset = new_index_size - 1; + for (count = 0, src_pos = 0; count < n_entries && src_pos <= max_offset; + src_pos++, src_ptr++) { + uint32_t i, step; + grn_id entry_id; + grn_hash_entry *entry; + if (grn_hash_is_io_hash(hash) && !(src_pos & IDX_MASK_IN_A_SEGMENT)) { + src_ptr = grn_io_hash_idx_at(ctx, hash, src_pos + src_offset); + if (!src_ptr) { + return GRN_NO_MEMORY_AVAILABLE; + } + } + entry_id = *src_ptr; + if (!entry_id || (entry_id == GARBAGE)) { + continue; + } + entry = grn_hash_entry_at(ctx, hash, entry_id, GRN_TABLE_ADD); + if (!entry) { + return GRN_NO_MEMORY_AVAILABLE; + } + step = grn_hash_calculate_step(entry->hash_value); + for (i = entry->hash_value; ; i += step) { + i &= new_max_offset; + if (grn_hash_is_io_hash(hash)) { + dest_ptr = grn_io_hash_idx_at(ctx, hash, i + dest_offset); + if (!dest_ptr) { + return GRN_NO_MEMORY_AVAILABLE; + } + } else { + dest_ptr = new_index + i; + } + if (!*dest_ptr) { + break; + } + } + *dest_ptr = entry_id; + count++; + } + *hash->max_offset = new_max_offset; + *hash->n_garbages = 0; + } + + if (grn_hash_is_io_hash(hash)) { + hash->header->idx_offset = dest_offset; + } else { + grn_id * const old_index = hash->index; + hash->index = new_index; + GRN_CTX_FREE(ctx, old_index); + } + + return GRN_SUCCESS; +} + +grn_rc +grn_hash_lock(grn_ctx *ctx, grn_hash *hash, int timeout) +{ + static int _ncalls = 0, _ncolls = 0; + uint32_t count; + _ncalls++; + for (count = 0;; count++) { + uint32_t lock; + GRN_ATOMIC_ADD_EX(hash->lock, 1, lock); + if (lock) { + GRN_ATOMIC_ADD_EX(hash->lock, -1, lock); + if (!timeout || (timeout > 0 && timeout == count)) { break; } + if (!(++_ncolls % 1000000) && (_ncolls > _ncalls)) { + if (_ncolls < 0 || _ncalls < 0) { + _ncolls = 0; _ncalls = 0; + } else { + GRN_LOG(ctx, GRN_LOG_NOTICE, "hash(%p) collisions(%d/%d)", hash, _ncolls, _ncalls); + } + } + grn_nanosleep(GRN_LOCK_WAIT_TIME_NANOSECOND); + continue; + } + return GRN_SUCCESS; + } + ERR(GRN_RESOURCE_DEADLOCK_AVOIDED, "grn_hash_lock"); + return ctx->rc; +} + +grn_rc +grn_hash_unlock(grn_ctx *ctx, grn_hash *hash) +{ + uint32_t lock; + GRN_ATOMIC_ADD_EX(hash->lock, -1, lock); + return GRN_SUCCESS; +} + +grn_rc +grn_hash_clear_lock(grn_ctx *ctx, grn_hash *hash) +{ + *hash->lock = 0; + return GRN_SUCCESS; +} + +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) +{ + grn_id entry_id; + grn_hash_entry *entry; + struct grn_hash_header * const header = hash->header; + + entry_id = header->garbages[key_size - 1]; + if (entry_id) { + entry = grn_io_hash_entry_at(ctx, hash, entry_id, GRN_TABLE_ADD); + if (!entry) { + return GRN_ID_NIL; + } + header->garbages[key_size - 1] = *(grn_id *)entry; + if (hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) { + /* keep entry->io_entry's hash_value, flag, key_size and key. */ + memset(entry->io_entry.value, 0, header->value_size); + } else { + memset(entry, 0, header->entry_size); + } + } else { + entry_id = header->curr_rec + 1; + entry = grn_hash_entry_at(ctx, hash, entry_id, GRN_TABLE_ADD); + if (!entry) { + return GRN_ID_NIL; + } + header->curr_rec = entry_id; + } + + if (!grn_io_array_bit_on(ctx, hash->io, GRN_HASH_BITMAP_SEGMENT, entry_id)) { + /* TODO: error handling. */ + } + + if (grn_hash_entry_put_key(ctx, hash, entry, hash_value, key, key_size)) { + /* TODO: error handling. */ + } + + if (value) { + *value = grn_hash_entry_get_value(hash, entry); + } + return entry_id; +} + +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) +{ + grn_id entry_id; + grn_hash_entry *entry; + if (hash->garbages) { + entry_id = hash->garbages; + entry = (grn_hash_entry *)grn_tiny_array_get(&hash->a, entry_id); + hash->garbages = *(grn_id *)entry; + memset(entry, 0, hash->entry_size); + } else { + entry_id = hash->a.max + 1; + entry = (grn_hash_entry *)grn_tiny_array_put(&hash->a, entry_id); + if (!entry) { + return GRN_ID_NIL; + } + } + + if (!grn_tiny_bitmap_put_and_set(&hash->bitmap, entry_id, 1)) { + /* TODO: error handling. */ + } + + if (grn_hash_entry_put_key(ctx, hash, entry, hash_value, key, key_size)) { + /* TODO: error handling. */ + } + + if (value) { + *value = grn_hash_entry_get_value(hash, entry); + } + return entry_id; +} + +grn_id +grn_hash_add(grn_ctx *ctx, grn_hash *hash, const void *key, + unsigned int key_size, void **value, int *added) +{ + uint32_t hash_value; + if (!key || !key_size) { + return GRN_ID_NIL; + } + if (hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) { + if (key_size > hash->key_size) { + ERR(GRN_INVALID_ARGUMENT, "too long key"); + return GRN_ID_NIL; + } + hash_value = grn_hash_calculate_hash_value(key, key_size); + } else { + if (key_size != hash->key_size) { + ERR(GRN_INVALID_ARGUMENT, "key size unmatch"); + return GRN_ID_NIL; + } + if (key_size == sizeof(uint32_t)) { + hash_value = *((uint32_t *)key); + } else { + hash_value = grn_hash_calculate_hash_value(key, key_size); + } + } + + { + uint32_t i; + const uint32_t step = grn_hash_calculate_step(hash_value); + grn_id id, *index, *garbage_index = NULL; + grn_hash_entry *entry; + + /* lock */ + if ((*hash->n_entries + *hash->n_garbages) * 2 > *hash->max_offset) { + grn_hash_reset(ctx, hash, 0); + } + + for (i = hash_value; ; i += step) { + index = grn_hash_idx_at(ctx, hash, i); + if (!index) { + return GRN_ID_NIL; + } + id = *index; + if (!id) { + break; + } + if (id == GARBAGE) { + if (!garbage_index) { + garbage_index = index; + } + continue; + } + + entry = grn_hash_entry_at(ctx, hash, id, GRN_TABLE_ADD); + if (!entry) { + return GRN_ID_NIL; + } + if (grn_hash_entry_compare_key(ctx, hash, entry, hash_value, + key, key_size)) { + if (value) { + *value = grn_hash_entry_get_value(hash, entry); + } + if (added) { + *added = 0; + } + return id; + } + } + + if (grn_hash_is_io_hash(hash)) { + id = grn_io_hash_add(ctx, hash, hash_value, key, key_size, value); + } else { + id = grn_tiny_hash_add(ctx, hash, hash_value, key, key_size, value); + } + if (!id) { + return GRN_ID_NIL; + } + if (garbage_index) { + (*hash->n_garbages)--; + index = garbage_index; + } + *index = id; + (*hash->n_entries)++; + /* unlock */ + + if (added) { + *added = 1; + } + return id; + } +} + +grn_id +grn_hash_get(grn_ctx *ctx, grn_hash *hash, const void *key, + unsigned int key_size, void **value) +{ + uint32_t hash_value; + if (hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) { + if (key_size > hash->key_size) { + return GRN_ID_NIL; + } + hash_value = grn_hash_calculate_hash_value(key, key_size); + } else { + if (key_size != hash->key_size) { + return GRN_ID_NIL; + } + if (key_size == sizeof(uint32_t)) { + hash_value = *((uint32_t *)key); + } else { + hash_value = grn_hash_calculate_hash_value(key, key_size); + } + } + + { + uint32_t i; + const uint32_t step = grn_hash_calculate_step(hash_value); + for (i = hash_value; ; i += step) { + grn_id id; + grn_id * const index = grn_hash_idx_at(ctx, hash, i); + if (!index) { + return GRN_ID_NIL; + } + id = *index; + if (!id) { + return GRN_ID_NIL; + } + if (id != GARBAGE) { + grn_hash_entry * const entry = grn_hash_entry_at(ctx, hash, id, 0); + if (entry) { + if (grn_hash_entry_compare_key(ctx, hash, entry, hash_value, + key, key_size)) { + if (value) { + *value = grn_hash_entry_get_value(hash, entry); + } + return id; + } + } + } + } + } +} + +inline static grn_hash_entry * +grn_hash_get_entry(grn_ctx *ctx, grn_hash *hash, grn_id id) +{ + if (!grn_hash_bitmap_at(ctx, hash, id)) { + return NULL; + } + return grn_hash_entry_at(ctx, hash, id, 0); +} + +const char * +_grn_hash_key(grn_ctx *ctx, grn_hash *hash, grn_id id, uint32_t *key_size) +{ + grn_hash_entry * const entry = grn_hash_get_entry(ctx, hash, id); + if (!entry) { + *key_size = 0; + return NULL; + } + *key_size = grn_hash_entry_get_key_size(hash, entry); + return grn_hash_entry_get_key(ctx, hash, entry); +} + +int +grn_hash_get_key(grn_ctx *ctx, grn_hash *hash, grn_id id, void *keybuf, int bufsize) +{ + int key_size; + grn_hash_entry * const entry = grn_hash_get_entry(ctx, hash, id); + if (!entry) { + return 0; + } + key_size = grn_hash_entry_get_key_size(hash, entry); + if (bufsize >= key_size) { + memcpy(keybuf, grn_hash_entry_get_key(ctx, hash, entry), key_size); + } + return key_size; +} + +int +grn_hash_get_key2(grn_ctx *ctx, grn_hash *hash, grn_id id, grn_obj *bulk) +{ + int key_size; + char *key; + grn_hash_entry * const entry = grn_hash_get_entry(ctx, hash, id); + if (!entry) { + return 0; + } + key_size = grn_hash_entry_get_key_size(hash, entry); + key = grn_hash_entry_get_key(ctx, hash, entry); + if (bulk->header.impl_flags & GRN_OBJ_REFER) { + bulk->u.b.head = key; + bulk->u.b.curr = key + key_size; + } else { + grn_bulk_write(ctx, bulk, key, key_size); + } + return key_size; +} + +int +grn_hash_get_value(grn_ctx *ctx, grn_hash *hash, grn_id id, void *valuebuf) +{ + void *value; + grn_hash_entry * const entry = grn_hash_get_entry(ctx, hash, id); + if (!entry) { + return 0; + } + value = grn_hash_entry_get_value(hash, entry); + if (!value) { + return 0; + } + if (valuebuf) { + memcpy(valuebuf, value, hash->value_size); + } + return hash->value_size; +} + +const char * +grn_hash_get_value_(grn_ctx *ctx, grn_hash *hash, grn_id id, uint32_t *size) +{ + const void *value; + grn_hash_entry * const entry = grn_hash_get_entry(ctx, hash, id); + if (!entry) { + return NULL; + } + value = grn_hash_entry_get_value(hash, entry); + if (!value) { + return NULL; + } + *size = hash->value_size; + return (const char *)value; +} + +int +grn_hash_get_key_value(grn_ctx *ctx, grn_hash *hash, grn_id id, + void *keybuf, int bufsize, void *valuebuf) +{ + void *value; + int key_size; + grn_hash_entry * const entry = grn_hash_get_entry(ctx, hash, id); + if (!entry) { + return 0; + } + key_size = grn_hash_entry_get_key_size(hash, entry); + if (bufsize >= key_size) { + memcpy(keybuf, grn_hash_entry_get_key(ctx, hash, entry), key_size); + } + value = grn_hash_entry_get_value(hash, entry); + if (!value) { + return 0; + } + if (valuebuf) { + memcpy(valuebuf, value, hash->value_size); + } + return key_size; +} + +int +_grn_hash_get_key_value(grn_ctx *ctx, grn_hash *hash, grn_id id, + void **key, void **value) +{ + int key_size; + grn_hash_entry * const entry = grn_hash_get_entry(ctx, hash, id); + if (!entry) { + return 0; + } + key_size = grn_hash_entry_get_key_size(hash, entry); + *key = grn_hash_entry_get_key(ctx, hash, entry); + *value = grn_hash_entry_get_value(hash, entry); + return *value ? key_size : 0; +} + +grn_rc +grn_hash_set_value(grn_ctx *ctx, grn_hash *hash, grn_id id, + const void *value, int flags) +{ + void *entry_value; + grn_hash_entry *entry; + if (!value) { + return GRN_INVALID_ARGUMENT; + } + entry = grn_hash_get_entry(ctx, hash, id); + if (!entry) { + return GRN_NO_MEMORY_AVAILABLE; + } + entry_value = grn_hash_entry_get_value(hash, entry); + if (!entry_value) { + return GRN_NO_MEMORY_AVAILABLE; + } + + switch (flags & GRN_OBJ_SET_MASK) { + case GRN_OBJ_SET : + memcpy(entry_value, value, hash->value_size); + return GRN_SUCCESS; + case GRN_OBJ_INCR : + switch (hash->value_size) { + case sizeof(int32_t) : + *((int32_t *)entry_value) += *((int32_t *)value); + return GRN_SUCCESS; + case sizeof(int64_t) : + *((int64_t *)entry_value) += *((int64_t *)value); + return GRN_SUCCESS; + default : + return GRN_INVALID_ARGUMENT; + } + break; + case GRN_OBJ_DECR : + switch (hash->value_size) { + case sizeof(int32_t) : + *((int32_t *)entry_value) -= *((int32_t *)value); + return GRN_SUCCESS; + case sizeof(int64_t) : + *((int64_t *)entry_value) -= *((int64_t *)value); + return GRN_SUCCESS; + default : + return GRN_INVALID_ARGUMENT; + } + break; + default : + ERR(GRN_INVALID_ARGUMENT, "flags = %d", flags); + return ctx->rc; + } +} + +#define DELETE_IT do {\ + *ep = GARBAGE;\ + if (grn_hash_is_io_hash(hash)) {\ + uint32_t size = key_size - 1;\ + struct grn_hash_header *hh = hash->header;\ + ee->key = hh->garbages[size];\ + hh->garbages[size] = e;\ + grn_io_array_bit_off(ctx, hash->io, GRN_HASH_BITMAP_SEGMENT, e);\ + } else {\ + ee->key = hash->garbages;\ + hash->garbages = e;\ + if ((hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) && !(ee->flag & HASH_IMMEDIATE)) {\ + grn_ctx *ctx = hash->ctx;\ + GRN_CTX_FREE(ctx, ((entry_astr *)ee)->str);\ + }\ + grn_tiny_bitmap_get_and_set(&hash->bitmap, e, 0);\ + }\ + (*hash->n_entries)--;\ + (*hash->n_garbages)++;\ + rc = GRN_SUCCESS;\ +} while (0) + +grn_rc +grn_hash_delete_by_id(grn_ctx *ctx, grn_hash *hash, grn_id id, + grn_table_delete_optarg *optarg) +{ + entry_str *ee; + grn_rc rc = GRN_INVALID_ARGUMENT; + if (!hash || !id) { return rc; } + /* lock */ + ee = grn_hash_entry_at(ctx, hash, id, 0); + if (ee) { + grn_id e, *ep; + uint32_t i, key_size, h = ee->key, s = grn_hash_calculate_step(h); + key_size = (hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) ? ee->size : hash->key_size; + for (i = h; ; i += s) { + if (!(ep = grn_hash_idx_at(ctx, hash, i))) { return GRN_NO_MEMORY_AVAILABLE; } + if (!(e = *ep)) { break; } + if (e == id) { + DELETE_IT; + break; + } + } + } + /* unlock */ + return rc; +} + +grn_rc +grn_hash_delete(grn_ctx *ctx, grn_hash *hash, const void *key, uint32_t key_size, + grn_table_delete_optarg *optarg) +{ + uint32_t h, i, m, s; + grn_rc rc = GRN_INVALID_ARGUMENT; + if (hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) { + if (key_size > hash->key_size) { return GRN_INVALID_ARGUMENT; } + h = grn_hash_calculate_hash_value(key, key_size); + } else { + if (key_size != hash->key_size) { return GRN_INVALID_ARGUMENT; } + if (key_size == sizeof(uint32_t)) { + h = *((uint32_t *)key); + } else { + h = grn_hash_calculate_hash_value(key, key_size); + } + } + s = grn_hash_calculate_step(h); + { + grn_id e, *ep; + /* lock */ + m = *hash->max_offset; + for (i = h; ; i += s) { + if (!(ep = grn_hash_idx_at(ctx, hash, i))) { return GRN_NO_MEMORY_AVAILABLE; } + if (!(e = *ep)) { break; } + if (e == GARBAGE) { continue; } + { + entry_str * const ee = grn_hash_entry_at(ctx, hash, e, 0); + if (ee && match_key(ctx, hash, ee, h, key, key_size)) { + DELETE_IT; + break; + } + } + } + /* unlock */ + return rc; + } +} + +/* only valid for hash tables, GRN_OBJ_KEY_VAR_SIZE && GRN_HASH_TINY */ +const char * +_grn_hash_strkey_by_val(void *v, uint16_t *size) +{ + entry_astr *n = (entry_astr *)((uintptr_t)v - + (uintptr_t)&((entry_astr *)0)->dummy); + *size = n->size; + return (n->flag & HASH_IMMEDIATE) ? (char *)&n->str : n->str; +} + +void +grn_hash_cursor_close(grn_ctx *ctx, grn_hash_cursor *c) +{ + GRN_ASSERT(c->ctx == ctx); + GRN_FREE(c); +} + +#define HASH_CURR_MAX(hash) \ + ((grn_hash_is_io_hash(hash)) ? (hash)->header->curr_rec : (hash)->a.max) + +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) +{ + grn_hash_cursor *c; + if (!hash || !ctx) { return NULL; } + if (!(c = GRN_MALLOCN(grn_hash_cursor, 1))) { return NULL; } + GRN_DB_OBJ_SET_TYPE(c, GRN_CURSOR_TABLE_HASH_KEY); + c->hash = hash; + c->ctx = ctx; + c->obj.header.flags = flags; + c->obj.header.domain = GRN_ID_NIL; + if (flags & GRN_CURSOR_DESCENDING) { + c->dir = -1; + if (max) { + if (!(c->curr_rec = grn_hash_get(ctx, hash, max, max_size, NULL))) { + c->tail = GRN_ID_NIL; + goto exit; + } + if (!(flags & GRN_CURSOR_LT)) { c->curr_rec++; } + } else { + c->curr_rec = HASH_CURR_MAX(hash) + 1; + } + if (min) { + if (!(c->tail = grn_hash_get(ctx, hash, min, min_size, NULL))) { + c->curr_rec = GRN_ID_NIL; + goto exit; + } + if ((flags & GRN_CURSOR_GT)) { c->tail++; } + } else { + c->tail = GRN_ID_NIL + 1; + } + if (c->curr_rec < c->tail) { c->tail = c->curr_rec; } + } else { + c->dir = 1; + if (min) { + if (!(c->curr_rec = grn_hash_get(ctx, hash, min, min_size, NULL))) { + c->tail = GRN_ID_NIL; + goto exit; + } + if (!(flags & GRN_CURSOR_GT)) { c->curr_rec--; } + } else { + c->curr_rec = GRN_ID_NIL; + } + if (max) { + if (!(c->tail = grn_hash_get(ctx, hash, max, max_size, NULL))) { + c->curr_rec = GRN_ID_NIL; + goto exit; + } + if ((flags & GRN_CURSOR_LT)) { c->tail--; } + } else { + c->tail = HASH_CURR_MAX(hash); + } + if (c->tail < c->curr_rec) { c->tail = c->curr_rec; } + } + if (*hash->n_entries != HASH_CURR_MAX(hash)) { + while (offset && c->curr_rec != c->tail) { + c->curr_rec += c->dir; + if (grn_hash_bitmap_at(ctx, c->hash, c->curr_rec)) { offset--; } + } + } else { + c->curr_rec += c->dir * offset; + } +exit : + c->rest = (limit < 0) ? GRN_ARRAY_MAX : limit; + return c; +} + +grn_id +grn_hash_cursor_next(grn_ctx *ctx, grn_hash_cursor *c) +{ + if (c && c->rest) { + while (c->curr_rec != c->tail) { + c->curr_rec += c->dir; + if (*c->hash->n_entries != HASH_CURR_MAX(c->hash)) { + if (!grn_hash_bitmap_at(ctx, c->hash, c->curr_rec)) { continue; } + } + c->rest--; + return c->curr_rec; + } + } + return GRN_ID_NIL; +} + +grn_id +grn_hash_next(grn_ctx *ctx, grn_hash *hash, grn_id id) +{ + grn_id max = HASH_CURR_MAX(hash); + while (++id <= max) { + if (grn_hash_bitmap_at(ctx, hash, id)) { return id; } + } + return GRN_ID_NIL; +} + +grn_id +grn_hash_at(grn_ctx *ctx, grn_hash *hash, grn_id id) +{ + return grn_hash_bitmap_at(ctx, hash, id) ? id : GRN_ID_NIL; +} + +int +grn_hash_cursor_get_key(grn_ctx *ctx, grn_hash_cursor *c, void **key) +{ + int key_size; + entry_str *ee; + if (!c) { return 0; } + ee = grn_hash_entry_at(ctx, c->hash, c->curr_rec, 0); + if (!ee) { return 0; } + key_size = (c->hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) ? ee->size : c->hash->key_size; + *key = get_key(ctx, c->hash, ee); + return key_size; +} + +int +grn_hash_cursor_get_value(grn_ctx *ctx, grn_hash_cursor *c, void **value) +{ + void *v; + entry_str *ee; + if (!c) { return 0; } + ee = grn_hash_entry_at(ctx, c->hash, c->curr_rec, 0); + if (ee && (v = get_value(c->hash, ee))) { + *value = v; + return c->hash->value_size; + } + return 0; +} + +int +grn_hash_cursor_get_key_value(grn_ctx *ctx, grn_hash_cursor *c, + void **key, uint32_t *key_size, void **value) +{ + entry_str *ee; + if (!c) { return GRN_INVALID_ARGUMENT; } + ee = grn_hash_entry_at(ctx, c->hash, c->curr_rec, 0); + if (!ee) { return GRN_INVALID_ARGUMENT; } + if (key_size) { + *key_size = (c->hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) ? ee->size : c->hash->key_size; + } + if (key) { *key = get_key(ctx, c->hash, ee); } + if (value) { *value = get_value(c->hash, ee); } + return c->hash->value_size; +} + +grn_rc +grn_hash_cursor_set_value(grn_ctx *ctx, grn_hash_cursor *c, + const void *value, int flags) +{ + if (!c) { return GRN_INVALID_ARGUMENT; } + return grn_hash_set_value(ctx, c->hash, c->curr_rec, value, flags); +} + +grn_rc +grn_hash_cursor_delete(grn_ctx *ctx, grn_hash_cursor *c, + grn_table_delete_optarg *optarg) +{ + if (!c) { return GRN_INVALID_ARGUMENT; } + return grn_hash_delete_by_id(ctx, c->hash, c->curr_rec, optarg); +} + +/* sort */ + +#define PREPARE_VAL(e,ep,es) do {\ + if ((arg->flags & GRN_TABLE_SORT_BY_VALUE)) {\ + ep = ((const uint8_t *)(get_value(hash, (entry_str *)(e))));\ + es = hash->value_size;\ + } else {\ + ep = ((const uint8_t *)(get_key(ctx, hash, (entry_str *)(e))));\ + es = ((hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE)\ + ? ((entry_str *)(e))->size : hash->key_size); \ + }\ + ep += arg->offset;\ + es -= arg->offset;\ +} while (0) + +#define COMPARE_VAL_(ap,as,bp,bs)\ + (arg->compar\ + ? arg->compar(ctx,\ + (grn_obj *)hash, (void *)(ap), as,\ + (grn_obj *)hash, (void *)(bp), bs, arg->compar_arg)\ + : ((arg->flags & GRN_TABLE_SORT_AS_NUMBER)\ + ? ((arg->flags & GRN_TABLE_SORT_AS_UNSIGNED)\ + ? ((arg->flags & GRN_TABLE_SORT_AS_INT64)\ + ? *((uint64_t *)(ap)) > *((uint64_t *)(bp))\ + : *((uint32_t *)(ap)) > *((uint32_t *)(bp)))\ + : ((arg->flags & GRN_TABLE_SORT_AS_INT64)\ + ? *((int64_t *)(ap)) > *((int64_t *)(bp))\ + : *((int32_t *)(ap)) > *((int32_t *)(bp))))\ + : grn_str_greater(ap, as, bp, bs))) + +#define COMPARE_VAL(ap,as,bp,bs)\ + ((dir) ? COMPARE_VAL_((bp),(bs),(ap),(as)) : COMPARE_VAL_((ap),(as),(bp),(bs))) + +inline static entry ** +pack(grn_ctx *ctx, grn_hash *hash, entry **res, grn_table_sort_optarg *arg, int dir) +{ + uint32_t n; + uint32_t cs, es; + const uint8_t *cp, *ep; + entry **head, **tail, *e, *c; + grn_id id, m = HASH_CURR_MAX(hash); + for (id = m >> 1;;id = (id == m) ? 1 : id + 1) { + if (grn_hash_bitmap_at(ctx, hash, id)) { break; } + } + c = grn_hash_entry_at(ctx, hash, id, 0); + if (!c) { return NULL; } + PREPARE_VAL(c, cp, cs); + head = res; + n = *hash->n_entries - 1; + tail = res + n; + while (n--) { + do { + id = (id == m) ? 1 : id + 1; + } while (!grn_hash_bitmap_at(ctx, hash, id)); + e = grn_hash_entry_at(ctx, hash, id, 0); + if (!e) { return NULL; } + PREPARE_VAL(e, ep, es); + if (COMPARE_VAL(cp, cs, ep, es)) { + *head++ = e; + } else { + *tail-- = e; + } + } + *head = c; + return *hash->n_entries > 2 ? head : NULL; +} + +inline static void +swap(entry **a, entry **b) +{ + entry *c_ = *a; + *a = *b; + *b = c_; +} + +#define SWAP(a,ap,as,b,bp,bs) do {\ + const uint8_t *cp_ = ap;\ + uint32_t cs_ = as;\ + ap = bp; bp = cp_;\ + as = bs; bs = cs_;\ + swap(a,b);\ +} while (0) + +inline static entry ** +part(grn_ctx *ctx, entry **b, entry **e, grn_table_sort_optarg *arg, grn_hash *hash, int dir) +{ + entry **c; + const uint8_t *bp, *cp, *ep; + uint32_t bs, cs, es; + intptr_t d = e - b; + PREPARE_VAL(*b, bp, bs); + PREPARE_VAL(*e, ep, es); + if (COMPARE_VAL(bp, bs, ep, es)) { + SWAP(b, bp, bs, e, ep, es); + } + if (d < 2) { return NULL; } + c = b + (d >> 1); + PREPARE_VAL(*c, cp, cs); + if (COMPARE_VAL(bp, bs, cp, cs)) { + SWAP(b, bp, bs, c, cp, cs); + } else { + if (COMPARE_VAL(cp, cs, ep, es)) { + SWAP(c, cp, cs, e, ep, es); + } + } + if (d < 3) { return NULL; } + b++; + swap(b, c); + c = b; + PREPARE_VAL(*c, cp, cs); + for (;;) { + do { + b++; + PREPARE_VAL(*b, bp, bs); + } while (COMPARE_VAL(cp, cs, bp, bs)); + do { + e--; + PREPARE_VAL(*e, ep, es); + } while (COMPARE_VAL(ep, es, cp, cs)); + if (b >= e) { break; } + SWAP(b, bp, bs, e, ep, es); + } + SWAP(c, cp, cs, e, ep, es); + return e; +} + +static void +_sort(grn_ctx *ctx, entry **head, entry **tail, int limit, + grn_table_sort_optarg *arg, grn_hash *hash, int dir) +{ + entry **c; + if (head < tail && (c = part(ctx, head, tail, arg, hash, dir))) { + intptr_t rest = limit - 1 - (c - head); + _sort(ctx, head, c - 1, limit, arg, hash, dir); + if (rest > 0) { _sort(ctx, c + 1, tail, (int)rest, arg, hash, dir); } + } +} + +static void +sort(grn_ctx *ctx, + grn_hash *hash, entry **res, int limit, grn_table_sort_optarg *arg, int dir) +{ + entry **c = pack(ctx, hash, res, arg, dir); + if (c) { + intptr_t rest = limit - 1 - (c - res); + _sort(ctx, res, c - 1, limit, arg, hash, dir); + if (rest > 0 ) { + _sort(ctx, c + 1, res + *hash->n_entries - 1, (int)rest, arg, hash, dir); + } + } +} + +typedef struct { + grn_id id; + int32_t v; +} val32; + +#define PREPARE_VAL32(id,e,ep) do {\ + (ep)->id = id;\ + (ep)->v = (arg->flags & GRN_TABLE_SORT_BY_ID)\ + ? (int32_t) id\ + : (*((int32_t *)((byte *)((arg->flags & GRN_TABLE_SORT_BY_VALUE)\ + ? get_value(hash, (e))\ + : get_key(ctx, hash, (e))) + arg->offset)));\ +} while (0) + +#define COMPARE_VAL32_(ap,bp) \ + (arg->compar\ + ? arg->compar(ctx,\ + (grn_obj *)hash, (void *)&(ap)->v, sizeof(uint32_t),\ + (grn_obj *)hash, (void *)&(bp)->v, sizeof(uint32_t),\ + arg->compar_arg)\ + : ((arg->flags & GRN_TABLE_SORT_AS_NUMBER)\ + ? ((arg->flags & GRN_TABLE_SORT_AS_UNSIGNED)\ + ? *((uint32_t *)&(ap)->v) > *((uint32_t *)&(bp)->v)\ + : *((int32_t *)&(ap)->v) > *((int32_t *)&(bp)->v))\ + : memcmp(&(ap)->v, &(bp)->v, sizeof(uint32_t)) > 0)) + +#define COMPARE_VAL32(ap,bp)\ + ((dir) ? COMPARE_VAL32_((bp),(ap)) : COMPARE_VAL32_((ap),(bp))) + +inline static val32 * +pack_val32(grn_ctx *ctx, grn_hash *hash, val32 *res, grn_table_sort_optarg *arg, int dir) +{ + uint32_t n; + entry_str *e, *c; + val32 *head, *tail, cr, er; + grn_id id, m = HASH_CURR_MAX(hash); + for (id = m >> 1;;id = (id == m) ? 1 : id + 1) { + if (grn_hash_bitmap_at(ctx, hash, id)) { break; } + } + c = grn_hash_entry_at(ctx, hash, id, 0); + if (!c) { return NULL; } + PREPARE_VAL32(id, c, &cr); + head = res; + n = *hash->n_entries - 1; + tail = res + n; + while (n--) { + do { + id = (id == m) ? 1 : id + 1; + } while (!grn_hash_bitmap_at(ctx, hash, id)); + e = grn_hash_entry_at(ctx, hash, id, 0); + if (!e) { return NULL; } + PREPARE_VAL32(id, e, &er); + if (COMPARE_VAL32(&cr, &er)) { + *head++ = er; + } else { + *tail-- = er; + } + } + *head = cr; + return *hash->n_entries > 2 ? head : NULL; +} + +#define SWAP_VAL32(ap,bp) do {\ + val32 cr_ = *ap;\ + *ap = *bp;\ + *bp = cr_;\ +} while (0) + +inline static val32 * +part_val32(grn_ctx *ctx, + val32 *b, val32 *e, grn_table_sort_optarg *arg, grn_hash *hash, int dir) +{ + val32 *c; + intptr_t d = e - b; + if (COMPARE_VAL32(b, e)) { SWAP_VAL32(b, e); } + if (d < 2) { return NULL; } + c = b + (d >> 1); + if (COMPARE_VAL32(b, c)) { + SWAP_VAL32(b, c); + } else { + if (COMPARE_VAL32(c, e)) { SWAP_VAL32(c, e); } + } + if (d < 3) { return NULL; } + b++; + SWAP_VAL32(b, c); + c = b; + for (;;) { + do { b++; } while (COMPARE_VAL32(c, b)); + do { e--; } while (COMPARE_VAL32(e, c)); + if (b >= e) { break; } + SWAP_VAL32(b, e); + } + SWAP_VAL32(c, e); + return e; +} + +static void +_sort_val32(grn_ctx *ctx, val32 *head, val32 *tail, int limit, + grn_table_sort_optarg *arg, grn_hash *hash, int dir) +{ + val32 *c; + if (head < tail && (c = part_val32(ctx, head, tail, arg, hash, dir))) { + intptr_t rest = limit - 1 - (c - head); + _sort_val32(ctx, head, c - 1, limit, arg, hash, dir); + if (rest > 0) { _sort_val32(ctx, c + 1, tail, (int)rest, arg, hash, dir); } + } +} + +static void +sort_val32(grn_ctx *ctx, + grn_hash *hash, val32 *res, int limit, grn_table_sort_optarg *arg, int dir) +{ + val32 *c = pack_val32(ctx, hash, res, arg, dir); + if (c) { + intptr_t rest = limit - 1 - (c - res); + _sort_val32(ctx, res, c - 1, limit, arg, hash, dir); + if (rest > 0 ) { + _sort_val32(ctx, c + 1, res + *hash->n_entries - 1, (int)rest, arg, hash, dir); + } + } +} + +inline static grn_id +entry2id(grn_ctx *ctx, grn_hash *hash, entry *e) +{ + entry *e2; + grn_id id, *ep; + uint32_t i, h = e->key, s = grn_hash_calculate_step(h); + for (i = h; ; i += s) { + if (!(ep = grn_hash_idx_at(ctx, hash, i))) { return GRN_ID_NIL; } + if (!(id = *ep)) { break; } + if (id != GARBAGE) { + e2 = grn_hash_entry_at(ctx, hash, id, 0); + if (!e2) { return GRN_ID_NIL; } + if (e2 == e) { break; } + } + } + return id; +} + +int +grn_hash_sort(grn_ctx *ctx, grn_hash *hash, + int limit, grn_array *result, grn_table_sort_optarg *optarg) +{ + entry **res; + if (!result || !*hash->n_entries) { return 0; } + if (!(res = GRN_MALLOC(sizeof(entry *) * *hash->n_entries))) { + GRN_LOG(ctx, GRN_LOG_ALERT, "allocation of entries failed on grn_hash_sort !"); + return 0; + } + if (limit < 0) { + limit += *hash->n_entries + 1; + if (limit < 0) { + GRN_LOG(ctx, GRN_LOG_ALERT, "limit is too small in grn_hash_sort !"); + return 0; + } + } + if (limit > *hash->n_entries) { limit = *hash->n_entries; } + /* hash->limit = limit; */ + if (optarg) { + int dir = (optarg->flags & GRN_TABLE_SORT_DESC); + if ((optarg->flags & GRN_TABLE_SORT_BY_ID) || + (optarg->flags & GRN_TABLE_SORT_BY_VALUE) + ? ((hash->value_size - optarg->offset) == sizeof(uint32_t)) + : (!(hash->obj.header.flags & GRN_OBJ_KEY_VAR_SIZE) + && hash->key_size == sizeof(uint32_t))) { + if (sizeof(entry *) != sizeof(val32)) { + GRN_FREE(res); + if (!(res = GRN_MALLOC(sizeof(val32) * *hash->n_entries))) { + GRN_LOG(ctx, GRN_LOG_ALERT, "allocation of entries failed on grn_hash_sort !"); + return 0; + } + } + sort_val32(ctx, hash, (val32 *)res, limit, optarg, dir); + { + int i; + grn_id *v; + val32 *rp = (val32 *)res; + for (i = 0; i < limit; i++, rp++) { + if (!grn_array_add(ctx, result, (void **)&v)) { break; } + if (!(*v = rp->id)) { break; } + } + GRN_FREE(res); + return i; + } + } else { + sort(ctx, hash, res, limit, optarg, dir); + } + } else { + grn_table_sort_optarg opt = {0, NULL, NULL, NULL, 0}; + sort(ctx, hash, res, limit, &opt, 0); + } + { + int i; + grn_id *v; + entry **rp = res; + for (i = 0; i < limit; i++, rp++) { + if (!grn_array_add(ctx, result, (void **)&v)) { break; } + if (!(*v = entry2id(ctx, hash, *rp))) { break; } + } + GRN_FREE(res); + return i; + } +} + +void +grn_hash_check(grn_ctx *ctx, grn_hash *hash) +{ + char buf[8]; + struct grn_hash_header *h = hash->header; + GRN_OUTPUT_ARRAY_OPEN("RESULT", 1); + GRN_OUTPUT_MAP_OPEN("SUMMARY", 25); + GRN_OUTPUT_CSTR("flags"); + grn_itoh(h->flags, buf, 8); + GRN_OUTPUT_STR(buf, 8); + GRN_OUTPUT_CSTR("key_size"); + GRN_OUTPUT_INT64(hash->key_size); + GRN_OUTPUT_CSTR("value_size"); + GRN_OUTPUT_INT64(hash->value_size); + GRN_OUTPUT_CSTR("tokenizer"); + GRN_OUTPUT_INT64(h->tokenizer); + GRN_OUTPUT_CSTR("normalizer"); + GRN_OUTPUT_INT64(h->normalizer); + GRN_OUTPUT_CSTR("curr_rec"); + GRN_OUTPUT_INT64(h->curr_rec); + GRN_OUTPUT_CSTR("curr_key"); + GRN_OUTPUT_INT64(h->curr_key); + GRN_OUTPUT_CSTR("idx_offset"); + GRN_OUTPUT_INT64(h->idx_offset); + GRN_OUTPUT_CSTR("entry_size"); + GRN_OUTPUT_INT64(hash->entry_size); + GRN_OUTPUT_CSTR("max_offset"); + GRN_OUTPUT_INT64(*hash->max_offset); + GRN_OUTPUT_CSTR("n_entries"); + GRN_OUTPUT_INT64(*hash->n_entries); + GRN_OUTPUT_CSTR("n_garbages"); + GRN_OUTPUT_INT64(*hash->n_garbages); + GRN_OUTPUT_CSTR("lock"); + GRN_OUTPUT_INT64(h->lock); + GRN_OUTPUT_MAP_CLOSE(); + GRN_OUTPUT_ARRAY_CLOSE(); +} + +/* rhash : grn_hash with subrecs */ + +#ifdef USE_GRN_INDEX2 + +static uint32_t default_flags = GRN_HASH_TINY; + +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) +{ + grn_rc rc; + record_size = grn_rec_unit_size(record_unit, record_size); + subrec_size = grn_rec_unit_size(subrec_unit, subrec_size); + if (record_unit != grn_rec_userdef && subrec_unit != grn_rec_userdef) { + subrec_size -= record_size; + } + if (!hash) { return GRN_INVALID_ARGUMENT; } + if (record_size < 0) { return GRN_INVALID_ARGUMENT; } + if ((default_flags & GRN_HASH_TINY)) { + rc = grn_tiny_hash_init(ctx, hash, NULL, record_size, + max_n_subrecs * (GRN_RSET_SCORE_SIZE + subrec_size), + default_flags, GRN_ENC_NONE); + } else { + rc = grn_io_hash_init(ctx, hash, NULL, record_size, + max_n_subrecs * (GRN_RSET_SCORE_SIZE + subrec_size), + default_flags, GRN_ENC_NONE, 0); + } + if (rc) { return rc; } + hash->record_unit = record_unit; + hash->subrec_unit = subrec_unit; + hash->subrec_size = subrec_size; + hash->max_n_subrecs = max_n_subrecs; + return rc; +} + +grn_rc +grn_rhash_fin(grn_ctx *ctx, grn_hash *hash) +{ + grn_rc rc; + if (grn_hash_is_io_hash(hash)) { + rc = grn_io_close(ctx, hash->io); + } else { + GRN_ASSERT(ctx == hash->ctx); + rc = grn_tiny_hash_fin(ctx, hash); + } + return rc; +} + +inline static void +subrecs_push(byte *subrecs, int size, int n_subrecs, int score, void *body, int dir) +{ + byte *v; + int *c2; + int n = n_subrecs - 1, n2; + while (n) { + n2 = (n - 1) >> 1; + c2 = GRN_RSET_SUBRECS_NTH(subrecs,size,n2); + if (GRN_RSET_SUBRECS_CMP(score, *c2, dir) > 0) { break; } + GRN_RSET_SUBRECS_COPY(subrecs,size,n,c2); + n = n2; + } + v = subrecs + n * (size + GRN_RSET_SCORE_SIZE); + *((int *)v) = score; + memcpy(v + GRN_RSET_SCORE_SIZE, body, size); +} + +inline static void +subrecs_replace_min(byte *subrecs, int size, int n_subrecs, int score, void *body, int dir) +{ + byte *v; + int n = 0, n1, n2, *c1, *c2; + for (;;) { + n1 = n * 2 + 1; + n2 = n1 + 1; + c1 = n1 < n_subrecs ? GRN_RSET_SUBRECS_NTH(subrecs,size,n1) : NULL; + c2 = n2 < n_subrecs ? GRN_RSET_SUBRECS_NTH(subrecs,size,n2) : NULL; + if (c1 && GRN_RSET_SUBRECS_CMP(score, *c1, dir) > 0) { + if (c2 && + GRN_RSET_SUBRECS_CMP(score, *c2, dir) > 0 && + GRN_RSET_SUBRECS_CMP(*c1, *c2, dir) > 0) { + GRN_RSET_SUBRECS_COPY(subrecs,size,n,c2); + n = n2; + } else { + GRN_RSET_SUBRECS_COPY(subrecs,size,n,c1); + n = n1; + } + } else { + if (c2 && GRN_RSET_SUBRECS_CMP(score, *c2, dir) > 0) { + GRN_RSET_SUBRECS_COPY(subrecs,size,n,c2); + n = n2; + } else { + break; + } + } + } + v = subrecs + n * (size + GRN_RSET_SCORE_SIZE); + memcpy(v, &score, GRN_RSET_SCORE_SIZE); + memcpy(v + GRN_RSET_SCORE_SIZE, body, size); +} + +void +grn_rhash_add_subrec(grn_hash *s, grn_rset_recinfo *ri, int score, void *body, int dir) +{ + int limit = s->max_n_subrecs; + ri->score += score; + ri->n_subrecs += 1; + if (limit) { + int ssize = s->subrec_size; + int n_subrecs = GRN_RSET_N_SUBRECS(ri); + if (limit < n_subrecs) { + if (GRN_RSET_SUBRECS_CMP(score, *ri->subrecs, dir) > 0) { + subrecs_replace_min(ri->subrecs, ssize, limit, score, body, dir); + } + } else { + subrecs_push(ri->subrecs, ssize, n_subrecs, score, body, dir); + } + } +} + +grn_hash * +grn_rhash_group(grn_hash *s, int limit, grn_group_optarg *optarg) +{ + grn_ctx *ctx = s->ctx; + grn_hash *g, h; + grn_rset_recinfo *ri; + grn_rec_unit unit; + grn_hash_cursor *c; + grn_id rh; + byte *key, *ekey, *gkey = NULL; + int funcp, dir; + unsigned int rsize; + if (!s || !s->index) { return NULL; } + if (optarg) { + unit = grn_rec_userdef; + rsize = optarg->key_size; + funcp = optarg->func ? 1 : 0; + dir = (optarg->mode == grn_sort_ascending) ? -1 : 1; + } else { + unit = grn_rec_document; + rsize = grn_rec_unit_size(unit, sizeof(grn_id)); + funcp = 0; + dir = 1; + } + if (funcp) { + gkey = GRN_MALLOC(rsize ? rsize : 8192); + if (!gkey) { + GRN_LOG(ctx, GRN_LOG_ALERT, "allocation for gkey failed !"); + return NULL; + } + } else { + if (s->key_size <= rsize) { return NULL; } + } + if (!(c = grn_hash_cursor_open(s->ctx, s, NULL, 0, NULL, -1, 0))) { + GRN_LOG(ctx, GRN_LOG_ALERT, "grn_hash_cursor_open on grn_hash_group failed !"); + if (gkey) { GRN_FREE(gkey); } + return NULL; + } + memcpy(&h, s, sizeof(grn_hash)); + g = s; + s = &h; + if (grn_rhash_init(ctx, g, unit, rsize, s->record_unit, s->key_size, limit)) { + GRN_LOG(ctx, GRN_LOG_ALERT, "grn_rhash_init in grn_hash_group failed !"); + grn_hash_cursor_close(s->ctx, c); + if (gkey) { GRN_FREE(gkey); } + return NULL; + } + while ((rh = grn_hash_cursor_next(ctx, c))) { + grn_hash_cursor_get_key_value(ctx, c, (void **)&key, NULL, (void **)&ri); + if (funcp) { + if (optarg->func((grn_records *)s, + (grn_recordh *)(intptr_t)rh, gkey, optarg->func_arg)) { continue; } + ekey = key; + } else { + gkey = key; + ekey = key + rsize; + } + { + grn_rset_recinfo *gri; + if (grn_hash_add(ctx, g, gkey, rsize, (void **)&gri, NULL)) { + grn_rhash_add_subrec(g, gri, ri->score, ekey, dir); + } + } + } + grn_hash_cursor_close(s->ctx, c); + grn_rhash_fin(s->ctx, s); + if (funcp) { GRN_FREE(gkey); } + return g; +} + +grn_rc +grn_rhash_subrec_info(grn_hash *s, grn_id rh, int index, + grn_id *rid, int *section, int *pos, int *score, void **subrec) +{ + grn_rset_posinfo *pi; + grn_rset_recinfo *ri; + int *p, unit_size = GRN_RSET_SCORE_SIZE + s->subrec_size; + if (!s || !rh || index < 0) { return GRN_INVALID_ARGUMENT; } + if ((unsigned int)index >= s->max_n_subrecs) { return GRN_INVALID_ARGUMENT; } + { + entry_str *ee; + if (!grn_hash_bitmap_at(ctx, s, rh)) { return GRN_INVALID_ARGUMENT; } + ee = grn_hash_entry_at(ctx, s, rh, 0); + if (!ee) { return GRN_INVALID_ARGUMENT; } + pi = (grn_rset_posinfo *)get_key(ctx, s, ee); + ri = get_value(s, ee); + if (!pi || !ri) { return GRN_INVALID_ARGUMENT; } + } + if (index >= ri->n_subrecs) { return GRN_INVALID_ARGUMENT; } + p = (int *)(ri->subrecs + index * unit_size); + if (score) { *score = p[0]; } + if (subrec) { *subrec = &p[1]; } + switch (s->record_unit) { + case grn_rec_document : + if (rid) { *rid = pi->rid; } + if (section) { *section = (s->subrec_unit != grn_rec_userdef) ? p[1] : 0; } + if (pos) { *pos = (s->subrec_unit == grn_rec_position) ? p[2] : 0; } + break; + case grn_rec_section : + if (rid) { *rid = pi->rid; } + if (section) { *section = pi->sid; } + if (pos) { *pos = (s->subrec_unit == grn_rec_position) ? p[1] : 0; } + break; + default : + pi = (grn_rset_posinfo *)&p[1]; + switch (s->subrec_unit) { + case grn_rec_document : + if (rid) { *rid = pi->rid; } + if (section) { *section = 0; } + if (pos) { *pos = 0; } + break; + case grn_rec_section : + if (rid) { *rid = pi->rid; } + if (section) { *section = pi->sid; } + if (pos) { *pos = 0; } + break; + case grn_rec_position : + if (rid) { *rid = pi->rid; } + if (section) { *section = pi->sid; } + if (pos) { *pos = pi->pos; } + break; + default : + if (rid) { *rid = 0; } + if (section) { *section = 0; } + if (pos) { *pos = 0; } + break; + } + break; + } + return GRN_SUCCESS; +} +#endif /* USE_GRN_INDEX2 */ |