Groonga - fulltext search engine.

[Groonga-commit] groonga/grnxx [master] Update grnxx::alpha::map::IDCursor to support MAP_CURSOR_ORDER_BY_KEY.

susumu.yata null+****@clear*****
Tue Apr 9 17:55:37 JST 2013

• Previous message: [Groonga-commit] groonga/fluent-plugin-droonga [master] test: add a test for searching existing table
• Next message: [Groonga-commit] groonga/fluent-plugin-droonga [master] Extract search methods to QuerySearcher
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

susumu.yata	2013-04-09 17:55:37 +0900 (Tue, 09 Apr 2013)

  New Revision: 2eb188b1e1288263a55e81277ed0347186e1e8e5
  https://github.com/groonga/grnxx/commit/2eb188b1e1288263a55e81277ed0347186e1e8e5

  Message:
    Update grnxx::alpha::map::IDCursor to support MAP_CURSOR_ORDER_BY_KEY.

  Modified files:
    lib/grnxx/alpha/map/cursor.cpp
    lib/grnxx/alpha/map/cursor.hpp
    test/test_alpha_map.cpp

  Modified: lib/grnxx/alpha/map/cursor.cpp (+87 -32)
===================================================================
--- lib/grnxx/alpha/map/cursor.cpp    2013-04-09 17:18:16 +0900 (976fd6c)
+++ lib/grnxx/alpha/map/cursor.cpp    2013-04-09 17:55:37 +0900 (be2b598)
@@ -17,6 +17,8 @@
 */
 #include "grnxx/alpha/map/cursor.hpp"
 
+#include <algorithm>
+
 namespace grnxx {
 namespace alpha {
 namespace map {
@@ -24,40 +26,30 @@ namespace map {
 template <typename T>
 IDCursor<T>::IDCursor(Map<T> *map, int64_t min, int64_t max,
                       const MapCursorOptions &options)
-  : MapCursor<T>(), map_(map), end_(), step_(), left_(options.limit) {
-  // TODO?
-//  if (options.flags & MAP_CURSOR_ORDER_BY_ID) {
-//  } else if (options.flags & MAP_CURSOR_ORDER_BY_KEY) {
-//  }
-
+  : MapCursor<T>(), map_(map), cur_(), end_(), step_(), count_(0),
+    options_(options), keys_() {
   if (min < 0) {
     min = 0;
-  } else if (options.flags & MAP_CURSOR_EXCEPT_MIN) {
+  } else if (options_.flags & MAP_CURSOR_EXCEPT_MIN) {
     ++min;
   }
 
   if ((max < 0) || (max > map_->max_key_id())) {
     max = map_->max_key_id();
-  } else if (options.flags & MAP_CURSOR_EXCEPT_MAX) {
+  } else if (options_.flags & MAP_CURSOR_EXCEPT_MAX) {
     --max;
   }
 
-  if (~options.flags & MAP_CURSOR_REVERSE_ORDER) {
-    this->key_id_ = min - 1;
-    end_ = max;
-    step_ = 1;
-  } else {
-    this->key_id_ = max + 1;
-    end_ = min;
-    step_ = -1;
+  if (min > max) {
+    cur_ = end_ = 0;
+    return;
   }
 
-  uint64_t count = 0;
-  while ((count < options.offset) && (this->key_id_ != end_)) {
-    this->key_id_ += step_;
-    if (map_->get(this->key_id_)) {
-      ++count;
-    }
+  if ((options_.flags & MAP_CURSOR_ORDER_BY_ID) ||
+      (~options_.flags & MAP_CURSOR_ORDER_BY_KEY)) {
+    init_order_by_id(min, max);
+  } else {
+    init_order_by_key(min, max);
   }
 }
 
@@ -66,15 +58,24 @@ IDCursor<T>::~IDCursor() {}
 
 template <typename T>
 bool IDCursor<T>::next() {
-  if (left_ == 0) {
+  if (count_ >= options_.limit) {
     return false;
   }
-  while (this->key_id_ != end_) {
-    this->key_id_ += step_;
-    if (map_->get(this->key_id_, &this->key_)) {
-      --left_;
-      return true;
+  if (options_.flags & MAP_CURSOR_ORDER_BY_ID) {
+    while (cur_ != end_) {
+      cur_ += step_;
+      if (map_->get(cur_, &this->key_)) {
+        this->key_id_ = cur_;
+        ++count_;
+        return true;
+      }
     }
+  } else if (cur_ != end_) {
+    cur_ += step_;
+    this->key_ = keys_[cur_].first;
+    this->key_id_ = keys_[cur_].second;
+    ++count_;
+    return true;
   }
   return false;
 }
@@ -84,6 +85,60 @@ bool IDCursor<T>::remove() {
   return map_->unset(this->key_id_);
 }
 
+template <typename T>
+void IDCursor<T>::init_order_by_id(int64_t min, int64_t max) {
+  options_.flags |= MAP_CURSOR_ORDER_BY_ID;
+  options_.flags &= ~MAP_CURSOR_ORDER_BY_KEY;
+
+  if (~options_.flags & MAP_CURSOR_REVERSE_ORDER) {
+    cur_ = min - 1;
+    end_ = max;
+    step_ = 1;
+  } else {
+    cur_ = max + 1;
+    end_ = min;
+    step_ = -1;
+  }
+
+  uint64_t count = 0;
+  while ((count < options_.offset) && (cur_ != end_)) {
+    cur_ += step_;
+    if (map_->get(cur_)) {
+      ++count;
+    }
+  }
+}
+
+template <typename T>
+void IDCursor<T>::init_order_by_key(int64_t min, int64_t max) {
+  cur_ = min - 1;
+  end_ = max;
+  while (cur_ != end_) {
+    ++cur_;
+    T key;
+    if (map_->get(cur_, &key)) {
+      keys_.push_back(std::make_pair(key, cur_));
+    }
+  }
+  std::sort(keys_.begin(), keys_.end());
+
+  if (~options_.flags & MAP_CURSOR_REVERSE_ORDER) {
+    cur_ = -1;
+    end_ = keys_.size() - 1;
+    step_ = 1;
+  } else {
+    cur_ = keys_.size();
+    end_ = 0;
+    step_ = -1;
+  }
+}
+
+template <>
+void IDCursor<GeoPoint>::init_order_by_key(int64_t, int64_t) {
+  // Not supported.
+  return;
+}
+
 template class IDCursor<int8_t>;
 template class IDCursor<int16_t>;
 template class IDCursor<int32_t>;
@@ -101,10 +156,10 @@ KeyCursor<T>::KeyCursor(Map<T> *map, T min, T max,
                         const MapCursorOptions &options)
   : MapCursor<T>(), map_(map), min_(min), max_(max), end_(), step_(),
     left_(options.limit), flags_(options.flags) {
-  // TODO?
-//  if (options.flags & MAP_CURSOR_ORDER_BY_ID) {
-//  } else if (options.flags & MAP_CURSOR_ORDER_BY_KEY) {
-//  }
+  if ((~options.flags & MAP_CURSOR_ORDER_BY_ID) &&
+      (options.flags & MAP_CURSOR_ORDER_BY_KEY)) {
+    // TODO: Order by key.
+  }
 
   uint64_t count = 0;
   if (~flags_ & MAP_CURSOR_REVERSE_ORDER) {

  Modified: lib/grnxx/alpha/map/cursor.hpp (+9 -1)
===================================================================
--- lib/grnxx/alpha/map/cursor.hpp    2013-04-09 17:18:16 +0900 (4d41e2c)
+++ lib/grnxx/alpha/map/cursor.hpp    2013-04-09 17:55:37 +0900 (53e662c)
@@ -20,6 +20,8 @@
 
 #include "grnxx/alpha/map.hpp"
 
+#include <vector>
+
 namespace grnxx {
 namespace alpha {
 namespace map {
@@ -36,9 +38,15 @@ class IDCursor : public MapCursor<T> {
 
  private:
   Map<T> *map_;
+  int64_t cur_;
   int64_t end_;
   int64_t step_;
-  uint64_t left_;
+  uint64_t count_;
+  MapCursorOptions options_;
+  std::vector<std::pair<T, int64_t>> keys_;
+
+  void init_order_by_id(int64_t min, int64_t max);
+  void init_order_by_key(int64_t min, int64_t max);
 };
 
 template <typename T>

  Modified: test/test_alpha_map.cpp (+98 -14)
===================================================================
--- test/test_alpha_map.cpp    2013-04-09 17:18:16 +0900 (c1e76ca)
+++ test/test_alpha_map.cpp    2013-04-09 17:55:37 +0900 (e50ad3b)
@@ -64,6 +64,15 @@ struct Hash<grnxx::Slice> {
 };
 
 template <typename T>
+using Map = grnxx::alpha::Map<T>;
+
+template <typename T>
+using MapCursor = grnxx::alpha::MapCursor<T>;
+
+template <typename T>
+using HashMap = std::unordered_map<T, std::int64_t, Hash<T>>;
+
+template <typename T>
 void generate_key(T *key) {
   static std::mt19937_64 rng;
 
@@ -94,8 +103,8 @@ void generate_key(grnxx::Slice *key) {
 }
 
 template <typename T>
-void compare_maps(const std::unique_ptr<grnxx::alpha::Map<T>> &map,
-                  const std::unordered_map<T, std::int64_t, Hash<T>> &hash_map) {
+void compare_maps(const std::unique_ptr<Map<T>> &map,
+                  const HashMap<T> &hash_map) {
   for (auto it = hash_map.begin(); it != hash_map.end(); ++it) {
     const T key = it->first;
     const std::int64_t key_id = it->second;
@@ -111,9 +120,41 @@ void compare_maps(const std::unique_ptr<grnxx::alpha::Map<T>> &map,
 }
 
 template <typename T>
-void test_basic_cursor(const std::unique_ptr<grnxx::alpha::Map<T>> &map,
+void test_basic_cursor(const std::unique_ptr<Map<T>> &map,
                        std::size_t MAP_SIZE) {
-  std::unique_ptr<grnxx::alpha::MapCursor<T>> cursor(
+  std::unique_ptr<MapCursor<T>> cursor(
+      map->open_basic_cursor());
+  for (std::size_t i = 0; i < MAP_SIZE; ++i) {
+    assert(cursor->next());
+  }
+  assert(!cursor->next());
+
+  grnxx::alpha::MapCursorOptions options;
+  options.flags |= grnxx::alpha::MAP_CURSOR_EXCEPT_MIN |
+                   grnxx::alpha::MAP_CURSOR_EXCEPT_MAX;
+  cursor.reset(map->open_basic_cursor(options));
+  for (std::size_t i = 0; i < MAP_SIZE; ++i) {
+    assert(cursor->next());
+  }
+  assert(!cursor->next());
+
+  options.flags = grnxx::alpha::MAP_CURSOR_ORDER_BY_KEY;
+  cursor.reset(map->open_basic_cursor(options));
+  assert(cursor->next());
+  T prev_key = cursor->key();
+  for (std::size_t i = 1; i < MAP_SIZE; ++i) {
+    assert(cursor->next());
+    assert(prev_key < cursor->key());
+    prev_key = cursor->key();
+  }
+  assert(!cursor->next());
+}
+
+template <>
+void test_basic_cursor(
+    const std::unique_ptr<Map<grnxx::alpha::GeoPoint>> &map,
+    std::size_t MAP_SIZE) {
+  std::unique_ptr<MapCursor<grnxx::alpha::GeoPoint>> cursor(
       map->open_basic_cursor());
   for (std::size_t i = 0; i < MAP_SIZE; ++i) {
     assert(cursor->next());
@@ -131,14 +172,14 @@ void test_basic_cursor(const std::unique_ptr<grnxx::alpha::Map<T>> &map,
 }
 
 template <typename T>
-void test_id_cursor(const std::unique_ptr<grnxx::alpha::Map<T>> &map,
+void test_id_cursor(const std::unique_ptr<Map<T>> &map,
                     std::size_t MAP_SIZE) {
   const std::int64_t MIN_ID = MAP_SIZE / 4;
   const std::int64_t MAX_ID = (MAP_SIZE * 3) / 4;
 
   grnxx::alpha::MapCursorOptions options;
   options.flags |= grnxx::alpha::MAP_CURSOR_ORDER_BY_ID;
-  std::unique_ptr<grnxx::alpha::MapCursor<T>> cursor(
+  std::unique_ptr<MapCursor<T>> cursor(
       map->open_id_cursor(MIN_ID, MAX_ID, options));
   for (std::int64_t i = MIN_ID; i <= MAX_ID; ++i) {
     assert(cursor->next());
@@ -160,10 +201,53 @@ void test_id_cursor(const std::unique_ptr<grnxx::alpha::Map<T>> &map,
     assert(cursor->key() == key);
   }
   assert(!cursor->next());
+
+  options.flags = grnxx::alpha::MAP_CURSOR_ORDER_BY_KEY;
+  cursor.reset(map->open_id_cursor(MIN_ID, MAX_ID, options));
+  assert(cursor->next());
+  T prev_key = cursor->key();
+  for (std::int64_t i = MIN_ID + 1; i <= MAX_ID; ++i) {
+    assert(cursor->next());
+    assert(prev_key < cursor->key());
+    prev_key = cursor->key();
+  }
+  assert(!cursor->next());
+}
+
+template <>
+void test_id_cursor(const std::unique_ptr<Map<grnxx::alpha::GeoPoint>> &map,
+                    std::size_t MAP_SIZE) {
+  const std::int64_t MIN_ID = MAP_SIZE / 4;
+  const std::int64_t MAX_ID = (MAP_SIZE * 3) / 4;
+
+  grnxx::alpha::MapCursorOptions options;
+  options.flags |= grnxx::alpha::MAP_CURSOR_ORDER_BY_ID;
+  std::unique_ptr<MapCursor<grnxx::alpha::GeoPoint>> cursor(
+      map->open_id_cursor(MIN_ID, MAX_ID, options));
+  for (std::int64_t i = MIN_ID; i <= MAX_ID; ++i) {
+    assert(cursor->next());
+    assert(cursor->key_id() == i);
+    grnxx::alpha::GeoPoint key;
+    assert(map->get(i, &key));
+    assert(cursor->key() == key);
+  }
+  assert(!cursor->next());
+
+  options.flags |= grnxx::alpha::MAP_CURSOR_EXCEPT_MIN |
+                   grnxx::alpha::MAP_CURSOR_EXCEPT_MAX;
+  cursor.reset(map->open_id_cursor(MIN_ID, MAX_ID, options));
+  for (std::int64_t i = MIN_ID + 1; i <= (MAX_ID - 1); ++i) {
+    assert(cursor->next());
+    assert(cursor->key_id() == i);
+    grnxx::alpha::GeoPoint key;
+    assert(map->get(i, &key));
+    assert(cursor->key() == key);
+  }
+  assert(!cursor->next());
 }
 
 template <typename T>
-void test_key_cursor(const std::unique_ptr<grnxx::alpha::Map<T>> &map) {
+void test_key_cursor(const std::unique_ptr<Map<T>> &map) {
   T min_key, max_key;
   generate_key(&min_key);
   generate_key(&max_key);
@@ -171,7 +255,7 @@ void test_key_cursor(const std::unique_ptr<grnxx::alpha::Map<T>> &map) {
     std::swap(min_key, max_key);
   }
 
-  std::unique_ptr<grnxx::alpha::MapCursor<T>> cursor(
+  std::unique_ptr<MapCursor<T>> cursor(
       map->open_key_cursor(min_key, max_key));
   while (cursor->next()) {
     assert(cursor->key() >= min_key);
@@ -191,7 +275,7 @@ void test_key_cursor(const std::unique_ptr<grnxx::alpha::Map<T>> &map) {
 }
 
 void test_key_cursor(
-    const std::unique_ptr<grnxx::alpha::Map<grnxx::alpha::GeoPoint>> &) {
+    const std::unique_ptr<Map<grnxx::alpha::GeoPoint>> &) {
   // Not supported.
 }
 
@@ -202,11 +286,11 @@ void test_map() {
   grnxx::io::Pool pool;
   pool.open(grnxx::io::POOL_ANONYMOUS);
 
-  std::unique_ptr<grnxx::alpha::Map<T>> map(
-      grnxx::alpha::Map<T>::create(grnxx::alpha::MAP_ARRAY, pool));
+  std::unique_ptr<Map<T>> map(
+      Map<T>::create(grnxx::alpha::MAP_ARRAY, pool));
 
   constexpr std::size_t MAP_SIZE = (sizeof(T) == 1) ? 128 : 1024;
-  std::unordered_map<T, std::int64_t, Hash<T>> hash_map;
+  HashMap<T> hash_map;
   while (hash_map.size() < MAP_SIZE) {
     T key;
     generate_key(&key);
@@ -236,7 +320,7 @@ void test_map() {
 
   std::uint32_t block_id = map->block_id();
   map.reset();
-  map.reset(grnxx::alpha::Map<T>::open(pool, block_id));
+  map.reset(Map<T>::open(pool, block_id));
 
   compare_maps(map, hash_map);
 
@@ -302,7 +386,7 @@ void test_nan() {
   grnxx::io::Pool pool;
   pool.open(grnxx::io::POOL_ANONYMOUS);
 
-  std::unique_ptr<grnxx::alpha::Map<double>> map;
+  std::unique_ptr<Map<double>> map;
   map.reset(map->create(grnxx::alpha::MAP_ARRAY, pool));
 
   const double nan = std::numeric_limits<double>::quiet_NaN();
-------------- next part --------------
HTML����������������������������...
Download 

• Previous message: [Groonga-commit] groonga/fluent-plugin-droonga [master] test: add a test for searching existing table
• Next message: [Groonga-commit] groonga/fluent-plugin-droonga [master] Extract search methods to QuerySearcher
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]