From e3db01cd487c5b666366885367c8bfff4a6a09da Mon Sep 17 00:00:00 2001 From: tanaka takashi Date: Tue, 30 Jun 2026 23:55:29 +0900 Subject: 検索インデックスのhash table化 MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- src/domain/search.c | 334 ++++++++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 288 insertions(+), 46 deletions(-) (limited to 'src') diff --git a/src/domain/search.c b/src/domain/search.c index b0ac440..0f9179d 100644 --- a/src/domain/search.c +++ b/src/domain/search.c @@ -19,11 +19,17 @@ typedef struct gram_bucket struct tiny_search_index { gram_bucket_t *buckets; - size_t count; - size_t capacity; + size_t bucket_count; + size_t bucket_capacity; + size_t *slots; + size_t slot_capacity; size_t message_count; }; +#define EMPTY_SLOT SIZE_MAX +#define INITIAL_BUCKET_CAPACITY 64U +#define INITIAL_SLOT_CAPACITY 128U + static bool decode_codepoints(const char *text, uint32_t **output, size_t *count) { @@ -100,71 +106,227 @@ gram_hash(const uint32_t *points, size_t width) hash ^= points[index]; hash *= 1099511628211ULL; } +#ifdef TINY_SEARCH_TEST_HASH_BITS + hash &= (UINT64_C(1) << TINY_SEARCH_TEST_HASH_BITS) - 1; +#endif return hash; } -static gram_bucket_t * -find_bucket(const tiny_search_index_t *index, const uint32_t *points, unsigned width) +static bool +bucket_matches(const gram_bucket_t *bucket, uint64_t hash, const uint32_t *points, unsigned width) { - const uint64_t hash = gram_hash(points, width); - size_t position; - for (position = 0; position < index->count; ++position) + return bucket->hash == hash && bucket->width == width + && memcmp(bucket->points, points, width * sizeof(uint32_t)) == 0; +} + +static size_t +slot_start(uint64_t hash, size_t capacity) +{ + hash ^= hash >> 32; + return (size_t)hash & (capacity - 1); +} + +static void +insert_slot(size_t *slots, size_t capacity, const gram_bucket_t *buckets, size_t bucket_index) +{ + size_t position = slot_start(buckets[bucket_index].hash, capacity); + while (slots[position] != EMPTY_SLOT) + { + position = (position + 1) & (capacity - 1); + } + slots[position] = bucket_index; +} + +static const gram_bucket_t * +find_bucket_const(const tiny_search_index_t *index, const uint32_t *points, unsigned width) +{ + uint64_t hash; + size_t position, bucket_index; + if (index->slot_capacity == 0) { - if (index->buckets[position].hash == hash && index->buckets[position].width == width - && memcmp(index->buckets[position].points, points, width * sizeof(uint32_t)) == 0) + return NULL; + } + hash = gram_hash(points, width); + position = slot_start(hash, index->slot_capacity); + while ((bucket_index = index->slots[position]) != EMPTY_SLOT) + { + if (bucket_index >= index->bucket_count) { - return &index->buckets[position]; + return NULL; } + if (bucket_matches(&index->buckets[bucket_index], hash, points, width)) + { + return &index->buckets[bucket_index]; + } + position = (position + 1) & (index->slot_capacity - 1); } return NULL; } +static gram_bucket_t * +find_bucket_mutable(tiny_search_index_t *index, const uint32_t *points, unsigned width) +{ + return (gram_bucket_t *)find_bucket_const(index, points, width); +} + static bool -add_gram(tiny_search_index_t *index, const uint32_t *points, unsigned width, size_t message_index) +reserve_buckets(tiny_search_index_t *index, size_t required) { - gram_bucket_t *bucket = find_bucket(index, points, width); - if (bucket == NULL) + gram_bucket_t *resized; + size_t capacity = index->bucket_capacity; + if (required <= capacity) + { + return true; + } + if (required > SIZE_MAX / sizeof(*resized)) + { + return false; + } + capacity = capacity ? capacity : INITIAL_BUCKET_CAPACITY; + while (capacity < required) { - gram_bucket_t *resized; - size_t capacity; - if (index->count == index->capacity) + if (capacity > SIZE_MAX / 2) { - capacity = index->capacity ? index->capacity * 2 : 64; - resized = realloc(index->buckets, capacity * sizeof(*resized)); - if (!resized) - { - return false; - } - index->buckets = resized; - index->capacity = capacity; + return false; } - bucket = &index->buckets[index->count++]; - memset(bucket, 0, sizeof(*bucket)); - bucket->hash = gram_hash(points, width); - bucket->width = width; - memcpy(bucket->points, points, width * sizeof(uint32_t)); + capacity *= 2; + } + resized = realloc(index->buckets, capacity * sizeof(*resized)); + if (!resized) + { + return false; + } + index->buckets = resized; + index->bucket_capacity = capacity; + return true; +} + +static bool +ensure_slots(tiny_search_index_t *index, size_t required_buckets) +{ + size_t capacity = index->slot_capacity; + size_t *slots; + size_t position; + if (capacity != 0 && required_buckets <= (capacity / 10) * 7) + { + return true; } - if (bucket->count > 0 && bucket->messages[bucket->count - 1] == message_index) + capacity = capacity ? capacity : INITIAL_SLOT_CAPACITY; + while (required_buckets > (capacity / 10) * 7) + { + if (capacity > SIZE_MAX / 2) + { + return false; + } + capacity *= 2; + } + if (capacity > SIZE_MAX / sizeof(*slots)) + { + return false; + } + slots = malloc(capacity * sizeof(*slots)); + if (!slots) + { + return false; + } + for (position = 0; position < capacity; ++position) + { + slots[position] = EMPTY_SLOT; + } + for (position = 0; position < index->bucket_count; ++position) + { + insert_slot(slots, capacity, index->buckets, position); + } + free(index->slots); + index->slots = slots; + index->slot_capacity = capacity; + return true; +} + +static bool +reserve_messages(gram_bucket_t *bucket, size_t required) +{ + size_t capacity = bucket->capacity; + size_t *resized; + if (required <= capacity) { return true; } - if (bucket->count == bucket->capacity) + if (required > SIZE_MAX / sizeof(*resized)) { - const size_t capacity = bucket->capacity ? bucket->capacity * 2 : 8; - size_t *resized = realloc(bucket->messages, capacity * sizeof(*resized)); - if (!resized) + return false; + } + capacity = capacity ? capacity : 8; + while (capacity < required) + { + if (capacity > SIZE_MAX / 2) { return false; } - bucket->messages = resized; - bucket->capacity = capacity; + capacity *= 2; } - bucket->messages[bucket->count++] = message_index; + resized = realloc(bucket->messages, capacity * sizeof(*resized)); + if (!resized) + { + return false; + } + bucket->messages = resized; + bucket->capacity = capacity; return true; } static bool -index_text(tiny_search_index_t *index, const char *text, size_t message_index) +add_gram_direct(tiny_search_index_t *index, + const uint32_t *points, + unsigned width, + size_t message_index) +{ + gram_bucket_t *bucket = find_bucket_mutable(index, points, width); + if (bucket != NULL) + { + if (bucket->count > 0 && bucket->messages[bucket->count - 1] == message_index) + { + return true; + } + if (bucket->count == SIZE_MAX || !reserve_messages(bucket, bucket->count + 1)) + { + return false; + } + bucket->messages[bucket->count++] = message_index; + return true; + } + else + { + size_t *messages = malloc(8 * sizeof(*messages)); + size_t new_index; + if (!messages) + { + return false; + } + if (index->bucket_count == SIZE_MAX || !reserve_buckets(index, index->bucket_count + 1) + || !ensure_slots(index, index->bucket_count + 1)) + { + free(messages); + return false; + } + new_index = index->bucket_count; + bucket = &index->buckets[new_index]; + memset(bucket, 0, sizeof(*bucket)); + bucket->hash = gram_hash(points, width); + bucket->width = width; + memcpy(bucket->points, points, width * sizeof(uint32_t)); + messages[0] = message_index; + bucket->messages = messages; + bucket->count = 1; + bucket->capacity = 8; + insert_slot(index->slots, index->slot_capacity, index->buckets, new_index); + index->bucket_count++; + return true; + } +} + +static bool +index_text_direct(tiny_search_index_t *index, const char *text, size_t message_index) { uint32_t *points = NULL; size_t count = 0, offset; @@ -177,7 +339,7 @@ index_text(tiny_search_index_t *index, const char *text, size_t message_index) { for (offset = 0; offset + width <= count; ++offset) { - if (!add_gram(index, points + offset, width, message_index)) + if (!add_gram_direct(index, points + offset, width, message_index)) { free(points); return false; @@ -202,19 +364,83 @@ tiny_search_index_free(tiny_search_index_t *index) { return; } - for (position = 0; position < index->count; ++position) + for (position = 0; position < index->bucket_count; ++position) { free(index->buckets[position].messages); } free(index->buckets); + free(index->slots); free(index); } +static bool +merge_delta(tiny_search_index_t *index, tiny_search_index_t *delta, size_t message_index) +{ + size_t position, new_buckets = 0, required; + for (position = 0; position < delta->bucket_count; ++position) + { + gram_bucket_t *source = &delta->buckets[position]; + if (!find_bucket_const(index, source->points, source->width)) + { + if (new_buckets == SIZE_MAX) + { + return false; + } + new_buckets++; + } + } + if (new_buckets > SIZE_MAX - index->bucket_count) + { + return false; + } + required = index->bucket_count + new_buckets; + if (!reserve_buckets(index, required) || !ensure_slots(index, required)) + { + return false; + } + for (position = 0; position < delta->bucket_count; ++position) + { + gram_bucket_t *source = &delta->buckets[position]; + gram_bucket_t *target = find_bucket_mutable(index, source->points, source->width); + if (target && !(target->count > 0 && target->messages[target->count - 1] == message_index) + && (target->count == SIZE_MAX || !reserve_messages(target, target->count + 1))) + { + return false; + } + } + for (position = 0; position < delta->bucket_count; ++position) + { + gram_bucket_t *source = &delta->buckets[position]; + gram_bucket_t *target = find_bucket_mutable(index, source->points, source->width); + if (target) + { + if (!(target->count > 0 && target->messages[target->count - 1] == message_index)) + { + target->messages[target->count++] = message_index; + } + } + else + { + size_t new_index = index->bucket_count; + index->buckets[new_index] = *source; + source->messages = NULL; + source->count = 0; + source->capacity = 0; + insert_slot(index->slots, index->slot_capacity, index->buckets, new_index); + index->bucket_count++; + } + } + index->message_count + = message_index + 1 > index->message_count ? message_index + 1 : index->message_count; + return true; +} + bool tiny_search_index_add(tiny_search_index_t *index, const tiny_message_t *message, size_t message_index) { + tiny_search_index_t *delta; size_t tag; if (index == NULL || message == NULL || message->content == NULL || (message->metadata.tag_count != 0 && message->metadata.tags == NULL) @@ -222,21 +448,30 @@ tiny_search_index_add(tiny_search_index_t *index, { return false; } - if (!index_text(index, message->content, message_index)) + delta = tiny_search_index_create(); + if (!delta) + { + return false; + } + if (!index_text_direct(delta, message->content, message_index)) { + tiny_search_index_free(delta); return false; } for (tag = 0; tag < message->metadata.tag_count; ++tag) { - if (!index_text(index, message->metadata.tags[tag], message_index)) + if (!index_text_direct(delta, message->metadata.tags[tag], message_index)) { + tiny_search_index_free(delta); return false; } } - if (message_index >= index->message_count) + if (!merge_delta(index, delta, message_index)) { - index->message_count = message_index + 1; + tiny_search_index_free(delta); + return false; } + tiny_search_index_free(delta); return true; } @@ -283,15 +518,22 @@ tiny_search_index_candidates(const tiny_search_index_t *index, } else { - gram_bucket_t *bucket; + const gram_bucket_t *bucket; width = point_count >= 3 ? 3 : 2; for (offset = 0; offset + width <= point_count; ++offset) { - if ((bucket = find_bucket(index, points + offset, (unsigned)width)) != NULL) + if ((bucket = find_bucket_const(index, points + offset, (unsigned)width)) != NULL) { size_t item; for (item = 0; item < bucket->count; ++item) { + if (bucket->messages[item] >= index->message_count) + { + free(points); + free(items); + free(seen); + return false; + } if (!seen[bucket->messages[item]]) { seen[bucket->messages[item]] = true; -- cgit v1.2.3