[search-index] Improved performance of current search index building process.

7 files changed, 319 insertions, 68 deletions

diff --git a/base/base.pro b/base/base.pro
index 6071d8da79..005806318d 100644
--- a/base/base.pro
+++ b/base/base.pro
@@ -9,74 +9,76 @@ include($$ROOT_DIR/common.pri)
 
 SOURCES += \
     base.cpp \
-    logging.cpp \
-    thread.cpp \
-    string_utils.cpp \
     commands_queue.cpp \
-    shared_buffer_manager.cpp \
     condition.cpp \
-    lower_case.cpp \
-    normalize_unicode.cpp \
-    runner.cpp \
-    timer.cpp \
-    internal/message.cpp \
     exception.cpp \
-    threaded_container.cpp \
-    resource_pool.cpp \
     fence_manager.cpp \
-    strings_bundle.cpp \
-    string_format.cpp \
+    internal/message.cpp \
+    logging.cpp \
+    lower_case.cpp \
+    normalize_unicode.cpp \
     object_tracker.cpp \
+    pseudo_random.cpp \
+    resource_pool.cpp \
+    runner.cpp \
     scheduled_task.cpp \
+    shared_buffer_manager.cpp \
+    src_point.cpp \
+    string_format.cpp \
+    string_utils.cpp \
+    strings_bundle.cpp \
+    thread.cpp \
     thread_pool.cpp \
-    pseudo_random.cpp \
-    src_point.cpp
+    threaded_container.cpp \
+    timer.cpp \
 
 HEADERS += \
     SRC_FIRST.hpp \
+    array_adapters.hpp \
     assert.hpp \
-    const_helper.hpp \
-    internal/fast_mutex.hpp \
-    math.hpp \
-    pseudo_random.hpp \
-    scope_guard.hpp \
-    macros.hpp \
     base.hpp \
-    src_point.hpp \
     bits.hpp \
+    buffer_vector.hpp \
+    cache.hpp \
+    commands_queue.hpp \
+    condition.hpp \
+    const_helper.hpp \
     exception.hpp \
-    internal/message.hpp \
+    fence_manager.hpp \
+    internal/fast_mutex.hpp \
     internal/fast_mutex.hpp \
+    internal/message.hpp \
+    limited_priority_queue.hpp \
     logging.hpp \
-    swap.hpp \
-    thread.hpp \
+    macros.hpp \
+    math.hpp \
+    matrix.hpp \
+    mem_trie.hpp \
+    mru_cache.hpp \
     mutex.hpp \
-    string_utils.hpp \
+    object_tracker.hpp \
+    pseudo_random.hpp \
+    regexp.hpp \
+    resource_pool.hpp \
     rolling_hash.hpp \
-    stl_add.hpp \
-    timer.hpp \
-    cache.hpp \
-    matrix.hpp \
+    runner.hpp \
+    scheduled_task.hpp \
+    scope_guard.hpp \
     set_operations.hpp \
-    condition.hpp \
-    commands_queue.hpp \
-    stats.hpp \
     shared_buffer_manager.hpp \
-    buffer_vector.hpp \
-    array_adapters.hpp \
-    runner.hpp \
-    mru_cache.hpp \
-    threaded_container.hpp \
-    threaded_list.hpp \
-    resource_pool.hpp \
-    limited_priority_queue.hpp \
-    threaded_priority_queue.hpp \
+    src_point.hpp \
+    stats.hpp \
     std_serialization.hpp \
-    fence_manager.hpp \
-    strings_bundle.hpp \
+    stl_add.hpp \
+    stl_iterator.hpp \
     string_format.hpp \
-    object_tracker.hpp \
-    regexp.hpp \
-    scheduled_task.hpp \
+    string_utils.hpp \
+    strings_bundle.hpp \
+    swap.hpp \
+    thread.hpp \
     thread_pool.hpp \
-    stl_iterator.hpp \
+    threaded_container.hpp \
+    threaded_list.hpp \
+    threaded_priority_queue.hpp \
+    timer.hpp \
+    worker_thread.hpp \
diff --git a/base/base_tests/base_tests.pro b/base/base_tests/base_tests.pro
index 25cb544cb3..b1e8ae8a89 100644
--- a/base/base_tests/base_tests.pro
+++ b/base/base_tests/base_tests.pro
@@ -14,32 +14,31 @@ win32-g++: LIBS += -lpthread
 
 SOURCES += \
   ../../testing/testingmain.cpp \
-  const_helper.cpp \
-  math_test.cpp \
-  scope_guard_test.cpp \
+  assert_test.cpp \
   bits_test.cpp \
-  logging_test.cpp \
-  threads_test.cpp \
-  rolling_hash_test.cpp \
+  buffer_vector_test.cpp \
   cache_test.cpp \
-  stl_add_test.cpp \
-  string_utils_test.cpp \
-  matrix_test.cpp \
   commands_queue_test.cpp \
-  buffer_vector_test.cpp \
-  assert_test.cpp \
-  timer_test.cpp \
-  mru_cache_test.cpp \
-  threaded_list_test.cpp \
   condition_test.cpp \
+  const_helper.cpp \
   containers_test.cpp \
   fence_manager_test.cpp \
-  string_format_test.cpp \
+  logging_test.cpp \
+  math_test.cpp \
+  matrix_test.cpp \
+  mem_trie_test.cpp \
+  mru_cache_test.cpp \
   regexp_test.cpp \
+  rolling_hash_test.cpp \
   scheduled_task_test.cpp \
-    thread_pool_tests.cpp
+  scope_guard_test.cpp \
+  stl_add_test.cpp \
+  string_format_test.cpp \
+  string_utils_test.cpp \
+  thread_pool_tests.cpp \
+  threaded_list_test.cpp \
+  threads_test.cpp \
+  timer_test.cpp \
+  worker_thread_test.cpp \
 
 HEADERS +=
-
-
-
diff --git a/base/base_tests/mem_trie_test.cpp b/base/base_tests/mem_trie_test.cpp
new file mode 100644
index 0000000000..d4634dd950
--- /dev/null
+++ b/base/base_tests/mem_trie_test.cpp
@@ -0,0 +1,31 @@
+#include "../../testing/testing.hpp"
+
+#include "../mem_trie.hpp"
+
+#include "../../std/algorithm.hpp"
+#include "../../std/string.hpp"
+#include "../../std/utility.hpp"
+#include "../../std/vector.hpp"
+
+UNIT_TEST(MemTrie_Basic)
+{
+  vector<pair<string, int>> data = {{"roger", 3},
+                                    {"amy", 1},
+                                    {"emma", 1},
+                                    {"ann", 1},
+                                    {"rob", 1},
+                                    {"roger", 2},
+                                    {"", 0},
+                                    {"roger", 1}};
+  my::MemTrie<string, int> trie;
+  for (auto const & p : data)
+    trie.Add(p.first, p.second);
+
+  vector<pair<string, int>> ordered_data;
+  trie.ForEach([&ordered_data](string const & k, int v)
+               {
+                 ordered_data.emplace_back(k, v);
+               });
+  sort(data.begin(), data.end());
+  TEST_EQUAL(data, ordered_data, ());
+}
diff --git a/base/base_tests/worker_thread_test.cpp b/base/base_tests/worker_thread_test.cpp
new file mode 100644
index 0000000000..51f800b21c
--- /dev/null
+++ b/base/base_tests/worker_thread_test.cpp
@@ -0,0 +1,31 @@
+#include "../../testing/testing.hpp"
+
+#include "../worker_thread.hpp"
+
+#include "../../std/memory.hpp"
+#include "../../std/vector.hpp"
+
+struct Task
+{
+  Task(vector<int> & buffer, int index) : m_buffer(buffer), m_index(index) {}
+
+  void operator()() const { m_buffer.push_back(m_index); }
+
+  vector<int> & m_buffer;
+  int m_index;
+};
+
+UNIT_TEST(WorkerThread_Basic)
+{
+  my::WorkerThread<Task> thread(5 /* maxTasks */);
+
+  vector<int> buffer;
+
+  for (int i = 0; i < 10; ++i)
+    thread.Push(make_shared<Task>(buffer, i));
+  thread.RunUntilIdleAndStop();
+
+  TEST_EQUAL(static_cast<size_t>(10), buffer.size(), ());
+  for (size_t i = 0; i < buffer.size(); ++i)
+    TEST_EQUAL(static_cast<int>(i), buffer[i], ());
+}
diff --git a/base/macros.hpp b/base/macros.hpp
index 573cae3bab..858b547c58 100644
--- a/base/macros.hpp
+++ b/base/macros.hpp
@@ -66,4 +66,9 @@ namespace my
 #define UINT64_LO(x) (static_cast<uint32_t>(x & 0xFFFFFFFF))
 #define UINT64_HI(x) (static_cast<uint32_t>(x >> 32))
 
-
+#define DISALLOW_COPY_AND_MOVE(className)            \
+private:                                             \
+  className(const className &) = delete;             \
+  className(className &&) = delete;                  \
+  className & operator=(const className &) = delete; \
+  className & operator=(className &&) = delete;
diff --git a/base/mem_trie.hpp b/base/mem_trie.hpp
new file mode 100644
index 0000000000..27c3c4cc90
--- /dev/null
+++ b/base/mem_trie.hpp
@@ -0,0 +1,91 @@
+#pragma once
+
+#include "macros.hpp"
+
+#include "../std/map.hpp"
+#include "../std/vector.hpp"
+
+namespace my
+{
+/// This class is a simple in-memory trie which allows to add
+/// key-value pairs and then traverse them in a sorted order.
+template <typename StringT, typename ValueT>
+class MemTrie
+{
+public:
+  MemTrie() = default;
+
+  /// Adds a key-value pair to the trie.
+  void Add(StringT const & key, ValueT const & value)
+  {
+    Node * cur = &m_root;
+    for (auto const & c : key)
+      cur = cur->GetMove(c);
+    cur->AddValue(value);
+  }
+
+  /// Traverses all key-value pairs in the trie in a sorted order.
+  ///
+  /// \param toDo A callable object that will be called on an each
+  ///             key-value pair.
+  template <typename ToDo>
+  void ForEach(ToDo const & toDo)
+  {
+    StringT prefix;
+    ForEach(&m_root, prefix, toDo);
+  }
+
+private:
+  struct Node
+  {
+    using CharT = typename StringT::value_type;
+    using MovesMap = map<CharT, Node *>;
+
+    Node() = default;
+
+    ~Node()
+    {
+      for (auto const & move : m_moves)
+        delete move.second;
+    }
+
+    Node * GetMove(CharT const & c)
+    {
+      Node ** node = &m_moves[c];
+      if (*node)
+        return *node;
+      *node = new Node();
+      return *node;
+    }
+
+    void AddValue(const ValueT & value) { m_values.push_back(value); }
+
+    MovesMap m_moves;
+    vector<ValueT> m_values;
+
+    DISALLOW_COPY_AND_MOVE(Node);
+  };
+
+  template <typename ToDo>
+  void ForEach(Node * root, StringT & prefix, ToDo const & toDo)
+  {
+    if (!root->m_values.empty())
+    {
+      sort(root->m_values.begin(), root->m_values.end());
+      for (auto const & value : root->m_values)
+        toDo(prefix, value);
+    }
+
+    for (auto const & move : root->m_moves)
+    {
+      prefix.push_back(move.first);
+      ForEach(move.second, prefix, toDo);
+      prefix.pop_back();
+    }
+  }
+
+  Node m_root;
+
+  DISALLOW_COPY_AND_MOVE(MemTrie);
+};  // class MemTrie
+}  // namespace my
diff --git a/base/worker_thread.hpp b/base/worker_thread.hpp
new file mode 100644
index 0000000000..220d398b8a
--- /dev/null
+++ b/base/worker_thread.hpp
@@ -0,0 +1,92 @@
+#pragma once
+
+#include "macros.hpp"
+
+#include "../std/condition_variable.hpp"
+#include "../std/memory.hpp"
+#include "../std/mutex.hpp"
+#include "../std/queue.hpp"
+#include "../std/thread.hpp"
+
+namespace my
+{
+/// This class wraps a sequential worker thread, that performs tasks
+/// one-by-one. This class is not thread-safe, so, it should be
+/// instantiated, used and destroyed on the same thread.
+template <typename Task>
+class WorkerThread
+{
+public:
+  WorkerThread(int maxTasks)
+      : m_maxTasks(maxTasks), m_shouldFinish(false), m_workerThread(&WorkerThread::Worker, this)
+  {
+  }
+
+  ~WorkerThread() { CHECK(!m_workerThread.joinable(), ()); }
+
+  /// Pushes new task into worker thread's queue. If the queue is
+  /// full, current thread is blocked.
+  ///
+  /// \param task A callable object that will be called by worker thread.
+  void Push(shared_ptr<Task> task)
+  {
+    CHECK(m_workerThread.joinable(), ());
+    unique_lock<mutex> lock(m_mutex);
+    m_condNotFull.wait(lock, [this]()
+                       {
+                         return m_tasks.size() < m_maxTasks;
+                       });
+    m_tasks.push(task);
+    m_condNonEmpty.notify_one();
+  }
+
+  /// Runs worker thread until it'll become idle. After that,
+  /// terminates worker thread.
+  void RunUntilIdleAndStop()
+  {
+    {
+      lock_guard<mutex> lock(m_mutex);
+      m_shouldFinish = true;
+      m_condNonEmpty.notify_one();
+    }
+    m_workerThread.join();
+  }
+
+private:
+  void Worker()
+  {
+    shared_ptr<Task> task;
+    while (true)
+    {
+      {
+        unique_lock<mutex> lock(m_mutex);
+        m_condNonEmpty.wait(lock, [this]()
+                            {
+                              return m_shouldFinish || !m_tasks.empty();
+                            });
+        if (m_shouldFinish && m_tasks.empty())
+          break;
+        task = m_tasks.front();
+        m_tasks.pop();
+        m_condNotFull.notify_one();
+      }
+      (*task)();
+    }
+  }
+
+  /// Maximum number of tasks in the queue.
+  int const m_maxTasks;
+  queue<shared_ptr<Task>> m_tasks;
+
+  /// When true, worker thread should finish all tasks in the queue
+  /// and terminate.
+  bool m_shouldFinish;
+
+  mutex m_mutex;
+  condition_variable m_condNotFull;
+  condition_variable m_condNonEmpty;
+  thread m_workerThread;
+
+  DISALLOW_COPY_AND_MOVE(WorkerThread);
+};  // class WorkerThread
+}  // namespace my