検索インデックスのhash table化

1 files changed, 161 insertions, 0 deletions

diff --git a/tests/search_index_test.c b/tests/search_index_test.c
new file mode 100644
index 0000000..5a477ad
--- /dev/null
+++ b/tests/search_index_test.c
@@ -0,0 +1,161 @@
+#include "domain/message.h"
+#include "domain/search.h"
+
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "base/allocator.h"
+
+static int failures;
+
+#define CHECK(value)                                                                               \
+  do                                                                                               \
+    {                                                                                              \
+      if (!(value))                                                                                \
+        {                                                                                          \
+          fprintf(stderr, "CHECK failed at line %d: %s\n", __LINE__, #value);                      \
+          failures++;                                                                              \
+        }                                                                                          \
+    }                                                                                              \
+  while (0)
+
+static tiny_message_t
+make_message(const char *content, char **tags, size_t tag_count)
+{
+  tiny_message_t message;
+  tiny_message_init(&message);
+  message.content = (char *)content;
+  message.metadata.tags = tags;
+  message.metadata.tag_count = tag_count;
+  return message;
+}
+
+static bool
+candidate_contains(tiny_search_index_t *index, const char *query, size_t expected)
+{
+  size_t *candidates = NULL;
+  size_t count = 0, position;
+  bool found = false;
+  if (!tiny_search_index_candidates(index, query, &candidates, &count))
+    {
+      return false;
+    }
+  for (position = 0; position < count; ++position)
+    {
+      if (candidates[position] == expected)
+        {
+          found = true;
+          break;
+        }
+    }
+  free(candidates);
+  return found;
+}
+
+static void
+test_collision_rehash_and_unicode(void)
+{
+  tiny_search_index_t *index = tiny_search_index_create();
+  char contents[300][4];
+  size_t position;
+  char *tags[] = { "設計メモ" };
+  tiny_message_t tagged = make_message("tagged content", tags, 1);
+  tiny_message_t duplicate = make_message("aaaaaa", NULL, 0);
+  size_t *candidates = NULL;
+  size_t count = 0;
+
+  CHECK(index != NULL);
+  for (position = 0; index && position < 300; ++position)
+    {
+      tiny_message_t message;
+      contents[position][0] = (char)('a' + (position / (26 * 26)) % 26);
+      contents[position][1] = (char)('a' + (position / 26) % 26);
+      contents[position][2] = (char)('a' + position % 26);
+      contents[position][3] = '\0';
+      message = make_message(contents[position], NULL, 0);
+      CHECK(tiny_search_index_add(index, &message, position));
+    }
+  for (position = 0; index && position < 300; ++position)
+    {
+      CHECK(candidate_contains(index, contents[position], position));
+    }
+
+  CHECK(tiny_search_index_add(index, &tagged, 300));
+  CHECK(candidate_contains(index, "設計", 300));
+  CHECK(candidate_contains(index, "TAGGED", 300));
+  CHECK(tiny_search_index_add(index, &duplicate, 301));
+  CHECK(tiny_search_index_candidates(index, "aaa", &candidates, &count));
+  {
+    size_t duplicate_hits = 0;
+    for (position = 0; position < count; ++position)
+      {
+        if (candidates[position] == 301)
+          {
+            duplicate_hits++;
+          }
+      }
+    CHECK(duplicate_hits == 1);
+  }
+  free(candidates);
+  candidates = NULL;
+  CHECK(tiny_search_index_candidates(index, "a", &candidates, &count));
+  CHECK(count == 302);
+  free(candidates);
+  tiny_search_index_free(index);
+}
+
+static void
+test_transactional_allocation_failure(void)
+{
+  const tiny_message_t baseline = make_message("baseline-only", NULL, 0);
+  char *tags[] = { "transaction-tag", "日本語追加" };
+  const tiny_message_t addition
+      = make_message("zyxwvutsrqponmlkjihgfedcba-transactional-new-token", tags, 2);
+  size_t failure_index;
+  bool reached_success = false;
+
+  for (failure_index = 0; failure_index < 512; ++failure_index)
+    {
+      tiny_search_index_t *index;
+      size_t baseline_allocations = tiny_allocator_outstanding();
+      tiny_allocator_reset();
+      index = tiny_search_index_create();
+      CHECK(index != NULL);
+      CHECK(tiny_search_index_add(index, &baseline, 0));
+
+      tiny_allocator_fail_after(failure_index);
+      if (tiny_search_index_add(index, &addition, 1))
+        {
+          tiny_allocator_reset();
+          CHECK(candidate_contains(index, "transactional-new-token", 1));
+          reached_success = true;
+          tiny_search_index_free(index);
+          CHECK(tiny_allocator_outstanding() == baseline_allocations);
+          break;
+        }
+
+      tiny_allocator_reset();
+      CHECK(candidate_contains(index, "baseline-only", 0));
+      CHECK(!candidate_contains(index, "transactional-new-token", 1));
+      CHECK(tiny_search_index_add(index, &addition, 1));
+      CHECK(candidate_contains(index, "transactional-new-token", 1));
+      tiny_search_index_free(index);
+      CHECK(tiny_allocator_outstanding() == baseline_allocations);
+    }
+  CHECK(reached_success);
+}
+
+int
+main(void)
+{
+  tiny_allocator_reset();
+  CHECK(tiny_allocator_outstanding() == 0);
+  test_collision_rehash_and_unicode();
+  CHECK(tiny_allocator_outstanding() == 0);
+  test_transactional_allocation_failure();
+  tiny_allocator_reset();
+  CHECK(tiny_allocator_outstanding() == 0);
+  return failures == 0 ? 0 : 1;
+}