Groonga - fulltext search engine.

[Groonga-commit] groonga/grnxx [master] Add Prefix/Completion/ReverseCompletionCursor.

susumu.yata null+****@clear*****
Fri Apr 12 13:54:38 JST 2013

• Previous message: [Groonga-commit] groonga/groonga-command [master] http: ignore key only argument
• Next message: [Groonga-commit] groonga/groonga [master] Support grn_get_version() with "git clone --depth 1" repository
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

susumu.yata	2013-04-12 13:54:38 +0900 (Fri, 12 Apr 2013)

  New Revision: 1ff86a4be44b76a46aa517d4800c7ef8c5d4ed8a
  https://github.com/groonga/grnxx/commit/1ff86a4be44b76a46aa517d4800c7ef8c5d4ed8a

  Message:
    Add Prefix/Completion/ReverseCompletionCursor.

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

  Modified: lib/grnxx/alpha/map.cpp (+67 -0)
===================================================================
--- lib/grnxx/alpha/map.cpp    2013-04-11 16:16:37 +0900 (17f83d6)
+++ lib/grnxx/alpha/map.cpp    2013-04-12 13:54:38 +0900 (ca2646d)
@@ -231,6 +231,73 @@ MapCursor<GeoPoint> *Map<GeoPoint>::open_key_cursor(GeoPoint, GeoPoint,
   return nullptr;
 }
 
+template <typename T>
+MapCursor<T> *Map<T>::open_bitwise_completion_cursor(
+    T, size_t, const MapCursorOptions &) {
+  // Not supported.
+  return nullptr;
+}
+
+template <>
+MapCursor<GeoPoint> *Map<GeoPoint>::open_bitwise_completion_cursor(
+    GeoPoint query, size_t bit_size, const MapCursorOptions &options) {
+  // TODO: Not supported.
+  return nullptr;
+}
+
+template <typename T>
+MapCursor<T> *Map<T>::open_neighbor_cursor(
+    T, size_t, const MapCursorOptions &) {
+  // Not supported.
+  return nullptr;
+}
+
+template <>
+MapCursor<GeoPoint> *Map<GeoPoint>::open_neighbor_cursor(
+    GeoPoint query, size_t min_size, const MapCursorOptions &options) {
+  // TODO: Not supported.
+  return nullptr;
+}
+
+template <typename T>
+MapCursor<T> *Map<T>::open_prefix_cursor(
+    T, size_t, const MapCursorOptions &) {
+  // Not supported.
+  return nullptr;
+}
+
+template <>
+MapCursor<Slice> *Map<Slice>::open_prefix_cursor(
+    Slice query, size_t min_size, const MapCursorOptions &options) {
+  return new (std::nothrow) map::PrefixCursor(this, query, min_size, options);
+}
+
+template <typename T>
+MapCursor<T> *Map<T>::open_completion_cursor(
+    T, const MapCursorOptions &) {
+  // Not supported.
+  return nullptr;
+}
+
+template <>
+MapCursor<Slice> *Map<Slice>::open_completion_cursor(
+    Slice query, const MapCursorOptions &options) {
+  return new (std::nothrow) map::CompletionCursor(this, query, options);
+}
+
+template <typename T>
+MapCursor<T> *Map<T>::open_reverse_completion_cursor(
+    T, const MapCursorOptions &) {
+  // Not supported.
+  return nullptr;
+}
+
+template <>
+MapCursor<Slice> *Map<Slice>::open_reverse_completion_cursor(
+    Slice query, const MapCursorOptions &options) {
+  return new (std::nothrow) map::ReverseCompletionCursor(this, query, options);
+}
+
 template class Map<int8_t>;
 template class Map<int16_t>;
 template class Map<int32_t>;

  Modified: lib/grnxx/alpha/map.hpp (+29 -4)
===================================================================
--- lib/grnxx/alpha/map.hpp    2013-04-11 16:16:37 +0900 (17c3278)
+++ lib/grnxx/alpha/map.hpp    2013-04-12 13:54:38 +0900 (fc5ef62)
@@ -28,7 +28,7 @@ namespace alpha {
 enum MapType : int32_t {
   MAP_UNKNOWN      = 0,
   MAP_ARRAY        = 1,  // Test implementation.
-  MAP_DOUBLE_ARRAY = 2,  // TODO: Not supported yet.
+  MAP_DOUBLE_ARRAY = 2,  // Partly implemented.
   MAP_PATRICIA     = 3,  // TODO: Not supported yet.
   MAP_HASH_TABLE   = 4   // TODO: Not supported yet.
 };
@@ -58,6 +58,9 @@ constexpr MapCursorFlags MAP_CURSOR_EXCEPT_MIN    =
 // Return keys except max.
 constexpr MapCursorFlags MAP_CURSOR_EXCEPT_MAX    =
     MapCursorFlags::define(0x200);
+// Return keys except exact match.
+constexpr MapCursorFlags MAP_CURSOR_EXCEPT_QUERY  =
+    MapCursorFlags::define(0x400);
 
 struct MapCursorOptions {
   MapCursorFlags flags;
@@ -141,15 +144,37 @@ class Map {
   // Remove all the keys in "*this".
   virtual void truncate();
 
-  // Create a cursor that accesses all the keys.
+  // Create a cursor for accessing all the keys.
   virtual MapCursor<T> *open_basic_cursor(
       const MapCursorOptions &options = MapCursorOptions());
-  // Create a cursor that accesses keys in range [min, max].
+  // Create a cursor for accessing keys in range [min, max].
   virtual MapCursor<T> *open_id_cursor(int64_t min, int64_t max,
       const MapCursorOptions &options = MapCursorOptions());
-  // Create a cursor that accesses keys in range [min, max].
+  // Create a cursor for accessing keys in range [min, max].
   virtual MapCursor<T> *open_key_cursor(T min, T max,
       const MapCursorOptions &options = MapCursorOptions());
+
+  // Only for GeoPoint.
+  // Create a cursor for accessing keys whose most significant "bit_size" bits
+  // are same as the MSBs of "query".
+  virtual MapCursor<T> *open_bitwise_completion_cursor(
+      T query, size_t bit_size,
+      const MapCursorOptions &options = MapCursorOptions());
+  // Create a cursor for accessing keys similar to "query".
+//  virtual MapCursor<T> *open_neighbor_cursor(
+//      T query, size_t min_size,
+//      const MapCursorOptions &options = MapCursorOptions());
+
+  // Only for Slice.
+  // Create a cursor for accessing keys matching a prefix of "query".
+  virtual MapCursor<T> *open_prefix_cursor(T query, size_t min_size,
+      const MapCursorOptions &options = MapCursorOptions());
+  // Create a cursor for accessing keys starting with "query".
+  virtual MapCursor<T> *open_completion_cursor(T query,
+      const MapCursorOptions &options = MapCursorOptions());
+  // Create a cursor for accessing keys ending with "query".
+  virtual MapCursor<T> *open_reverse_completion_cursor(T query,
+      const MapCursorOptions &options = MapCursorOptions());
 };
 
 }  // namespace alpha

  Modified: lib/grnxx/alpha/map/cursor.cpp (+102 -25)
===================================================================
--- lib/grnxx/alpha/map/cursor.cpp    2013-04-11 16:16:37 +0900 (eeadd37)
+++ lib/grnxx/alpha/map/cursor.cpp    2013-04-12 13:54:38 +0900 (560676d)
@@ -152,23 +152,16 @@ template class IDCursor<GeoPoint>;
 template class IDCursor<Slice>;
 
 template <typename T>
-KeyCursor<T>::KeyCursor(Map<T> *map, T min, T max,
-                        const MapCursorOptions &options)
-  : MapCursor<T>(), map_(map), min_(min), max_(max), cur_(), end_(), step_(),
-    count_(0), options_(options), keys_() {
-  if ((options_.flags & MAP_CURSOR_ORDER_BY_ID) ||
-      (~options_.flags & MAP_CURSOR_ORDER_BY_KEY)) {
-    init_order_by_id();
-  } else {
-    init_order_by_key();
-  }
-}
+ConditionalCursor<T>::ConditionalCursor(Map<T> *map,
+                                        const MapCursorOptions &options)
+  : MapCursor<T>(), map_(map), cur_(), end_(), step_(), count_(0),
+    options_(options), keys_() {}
 
 template <typename T>
-KeyCursor<T>::~KeyCursor() {}
+ConditionalCursor<T>::~ConditionalCursor() {}
 
 template <typename T>
-bool KeyCursor<T>::next() {
+bool ConditionalCursor<T>::next() {
   if (count_ >= options_.limit) {
     return false;
   }
@@ -176,7 +169,7 @@ bool KeyCursor<T>::next() {
     while (cur_ != end_) {
       cur_ += step_;
       if (map_->get(cur_, &this->key_)) {
-        if (in_range(this->key_)) {
+        if (is_valid(this->key_)) {
           this->key_id_ = cur_;
           ++count_;
           return true;
@@ -194,12 +187,22 @@ bool KeyCursor<T>::next() {
 }
 
 template <typename T>
-bool KeyCursor<T>::remove() {
+bool ConditionalCursor<T>::remove() {
   return map_->unset(this->key_id_);
 }
 
 template <typename T>
-void KeyCursor<T>::init_order_by_id() {
+void ConditionalCursor<T>::init() {
+  if ((options_.flags & MAP_CURSOR_ORDER_BY_ID) ||
+      (~options_.flags & MAP_CURSOR_ORDER_BY_KEY)) {
+    init_order_by_id();
+  } else {
+    init_order_by_key();
+  }
+}
+
+template <typename T>
+void ConditionalCursor<T>::init_order_by_id() {
   options_.flags |= MAP_CURSOR_ORDER_BY_ID;
   options_.flags &= ~MAP_CURSOR_ORDER_BY_KEY;
 
@@ -217,7 +220,7 @@ void KeyCursor<T>::init_order_by_id() {
   while ((count < options_.offset) && (cur_ != end_)) {
     cur_ += step_;
     if (map_->get(cur_, &this->key_)) {
-      if (in_range(this->key_)) {
+      if (is_valid(this->key_)) {
         ++count;
       }
     }
@@ -225,12 +228,12 @@ void KeyCursor<T>::init_order_by_id() {
 }
 
 template <typename T>
-void KeyCursor<T>::init_order_by_key() {
+void ConditionalCursor<T>::init_order_by_key() {
   std::int64_t max_key_id = map_->max_key_id();
   for (std::int64_t i = 0; i <= max_key_id; ++i) {
     T key;
     if (map_->get(i, &key)) {
-      if (in_range(key)) {
+      if (is_valid(key)) {
         keys_.push_back(std::make_pair(key, i));
       }
     }
@@ -248,9 +251,30 @@ void KeyCursor<T>::init_order_by_key() {
   }
 }
 
+template class ConditionalCursor<int8_t>;
+template class ConditionalCursor<int16_t>;
+template class ConditionalCursor<int32_t>;
+template class ConditionalCursor<int64_t>;
+template class ConditionalCursor<uint8_t>;
+template class ConditionalCursor<uint16_t>;
+template class ConditionalCursor<uint32_t>;
+template class ConditionalCursor<uint64_t>;
+template class ConditionalCursor<double>;
+template class ConditionalCursor<Slice>;
+
 template <typename T>
-bool KeyCursor<T>::in_range(T key) const {
-  if (options_.flags & MAP_CURSOR_EXCEPT_MIN) {
+KeyCursor<T>::KeyCursor(Map<T> *map, T min, T max,
+                        const MapCursorOptions &options)
+  : ConditionalCursor<T>(map, options), min_(min), max_(max) {
+  this->init();
+}
+
+template <typename T>
+KeyCursor<T>::~KeyCursor() {}
+
+template <typename T>
+bool KeyCursor<T>::is_valid(T key) const {
+  if (this->options_.flags & MAP_CURSOR_EXCEPT_MIN) {
     if (key <= min_) {
       return false;
     }
@@ -258,7 +282,7 @@ bool KeyCursor<T>::in_range(T key) const {
     return false;
   }
 
-  if (options_.flags & MAP_CURSOR_EXCEPT_MAX) {
+  if (this->options_.flags & MAP_CURSOR_EXCEPT_MAX) {
     if (key >= max_) {
       return false;
     }
@@ -270,8 +294,8 @@ bool KeyCursor<T>::in_range(T key) const {
 }
 
 template <>
-bool KeyCursor<Slice>::in_range(Slice key) const {
-  if (options_.flags & MAP_CURSOR_EXCEPT_MIN) {
+bool KeyCursor<Slice>::is_valid(Slice key) const {
+  if (this->options_.flags & MAP_CURSOR_EXCEPT_MIN) {
     if (key <= min_) {
       return false;
     }
@@ -280,7 +304,7 @@ bool KeyCursor<Slice>::in_range(Slice key) const {
   }
 
   if (max_) {
-    if (options_.flags & MAP_CURSOR_EXCEPT_MAX) {
+    if (this->options_.flags & MAP_CURSOR_EXCEPT_MAX) {
       if (key >= max_) {
         return false;
       }
@@ -303,6 +327,59 @@ template class KeyCursor<uint64_t>;
 template class KeyCursor<double>;
 template class KeyCursor<Slice>;
 
+PrefixCursor::PrefixCursor(Map<Slice> *map, Slice query, size_t min_size,
+                           const MapCursorOptions &options)
+  : ConditionalCursor<Slice>(map, options),
+    query_(query), min_size_(min_size) {
+  if (this->options_.flags & MAP_CURSOR_EXCEPT_QUERY) {
+    query_.remove_suffix(1);
+  }
+  this->init();
+}
+
+PrefixCursor::~PrefixCursor() {}
+
+bool PrefixCursor::is_valid(Slice key) const {
+  if (key.size() < min_size_) {
+    return false;
+  }
+  return query_.starts_with(key);
+}
+
+CompletionCursor::CompletionCursor(Map<Slice> *map, Slice query,
+                                   const MapCursorOptions &options)
+  : ConditionalCursor<Slice>(map, options), query_(query) {
+  this->init();
+}
+
+CompletionCursor::~CompletionCursor() {}
+
+bool CompletionCursor::is_valid(Slice key) const {
+  if (this->options_.flags & MAP_CURSOR_EXCEPT_QUERY) {
+    if (key.size() <= query_.size()) {
+      return false;
+    }
+  }
+  return key.starts_with(query_);
+}
+
+ReverseCompletionCursor::ReverseCompletionCursor(
+    Map<Slice> *map, Slice query, const MapCursorOptions &options)
+  : ConditionalCursor<Slice>(map, options), query_(query) {
+  this->init();
+}
+
+ReverseCompletionCursor::~ReverseCompletionCursor() {}
+
+bool ReverseCompletionCursor::is_valid(Slice key) const {
+  if (this->options_.flags & MAP_CURSOR_EXCEPT_QUERY) {
+    if (key.size() <= query_.size()) {
+      return false;
+    }
+  }
+  return key.ends_with(query_);
+}
+
 }  // namespace map
 }  // namespace alpha
 }  // namespace grnxx

  Modified: lib/grnxx/alpha/map/cursor.hpp (+66 -10)
===================================================================
--- lib/grnxx/alpha/map/cursor.hpp    2013-04-11 16:16:37 +0900 (51bb4ec)
+++ lib/grnxx/alpha/map/cursor.hpp    2013-04-12 13:54:38 +0900 (8c6ceda)
@@ -29,8 +29,8 @@ namespace map {
 template <typename T>
 class IDCursor : public MapCursor<T> {
  public:
-  explicit IDCursor(Map<T> *map, int64_t min, int64_t max,
-                    const MapCursorOptions &options);
+  IDCursor(Map<T> *map, int64_t min, int64_t max,
+           const MapCursorOptions &options);
   ~IDCursor();
 
   bool next();
@@ -50,19 +50,16 @@ class IDCursor : public MapCursor<T> {
 };
 
 template <typename T>
-class KeyCursor : public MapCursor<T> {
+class ConditionalCursor : public MapCursor<T> {
  public:
-  explicit KeyCursor(Map<T> *map, T min, T max,
-                     const MapCursorOptions &options);
-  ~KeyCursor();
+  ConditionalCursor(Map<T> *map, const MapCursorOptions &options);
+  virtual ~ConditionalCursor();
 
   bool next();
   bool remove();
 
- private:
+ protected:
   Map<T> *map_;
-  T min_;
-  T max_;
   int64_t cur_;
   int64_t end_;
   int64_t step_;
@@ -70,10 +67,69 @@ class KeyCursor : public MapCursor<T> {
   MapCursorOptions options_;
   std::vector<std::pair<T, int64_t>> keys_;
 
+  void init();
   void init_order_by_id();
   void init_order_by_key();
 
-  bool in_range(T key) const;
+  virtual bool is_valid(T key) const = 0;
+};
+
+template <typename T>
+class KeyCursor : public ConditionalCursor<T> {
+ public:
+  KeyCursor(Map<T> *map, T min, T max, const MapCursorOptions &options);
+  ~KeyCursor();
+
+ private:
+  T min_;
+  T max_;
+
+  bool is_valid(T key) const;
+};
+
+// TODO
+//class BitwiseCompletionCursor : public ConditionalCursor<GeoPoint> {
+// public:
+//  BitwiseCompletionCursor(Map<GeoPoint> *map, GeoPoint query, size_t bit_size,
+//                          const MapCursorOptions &options);
+//  ~BitwiseCompletionCursor();
+//};
+
+class PrefixCursor : public ConditionalCursor<Slice> {
+ public:
+  PrefixCursor(Map<Slice> *map, Slice query, size_t min_size,
+               const MapCursorOptions &options);
+  ~PrefixCursor();
+
+ private:
+  Slice query_;
+  size_t min_size_;
+
+  bool is_valid(Slice key) const;
+};
+
+class CompletionCursor : public ConditionalCursor<Slice> {
+ public:
+  CompletionCursor(Map<Slice> *map, Slice query,
+                   const MapCursorOptions &options);
+  ~CompletionCursor();
+
+ private:
+  Slice query_;
+
+  bool is_valid(Slice key) const;
+};
+
+class ReverseCompletionCursor : public ConditionalCursor<Slice> {
+ public:
+  ReverseCompletionCursor(Map<Slice> *map, Slice query,
+                          const MapCursorOptions &options);
+  ~ReverseCompletionCursor();
+
+ private:
+  Slice query_;
+
+  bool is_valid(Slice key) const;
 };
 
 }  // namespace map
-------------- next part --------------
HTML����������������������������...
Download 

• Previous message: [Groonga-commit] groonga/groonga-command [master] http: ignore key only argument
• Next message: [Groonga-commit] groonga/groonga [master] Support grn_get_version() with "git clone --depth 1" repository
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]