Groonga - fulltext search engine.

[Groonga-commit] groonga/grnxx at 44102f3 [master] Add naive implementations.

susumu.yata null+****@clear*****
Thu May 16 12:18:02 JST 2013

• Previous message: [Groonga-commit] [Errored] mroonga/mroonga#615 (master - 90e9555)
• Next message: [Groonga-commit] groonga/groonga at bcc70df [master] test: group index section tests
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

susumu.yata	2013-05-16 12:18:02 +0900 (Thu, 16 May 2013)

  New Revision: 44102f3ba0cd0d0bb8ef98ddd52c50916cd96cf5
  https://github.com/groonga/grnxx/commit/44102f3ba0cd0d0bb8ef98ddd52c50916cd96cf5

  Message:
    Add naive implementations.

  Modified files:
    lib/grnxx/map.cpp
    lib/grnxx/map.hpp
    lib/grnxx/map/scanner.cpp
    lib/grnxx/map/scanner.hpp

  Modified: lib/grnxx/map.cpp (+78 -28)
===================================================================
--- lib/grnxx/map.cpp    2013-05-15 18:29:02 +0900 (bce0e8f)
+++ lib/grnxx/map.cpp    2013-05-16 12:18:02 +0900 (47875c2)
@@ -20,6 +20,7 @@
 #include "grnxx/bytes.hpp"
 #include "grnxx/geo_point.hpp"
 #include "grnxx/logger.hpp"
+#include "grnxx/map/scanner.hpp"
 
 namespace grnxx {
 
@@ -78,39 +79,66 @@ bool Map<T>::unlink(Storage *storage, uint32_t storage_node_id) {
 }
 
 template <typename T>
-bool Map<T>::get(uint64_t, Key *) {
+bool Map<T>::get(int64_t, Key *) {
   GRNXX_ERROR() << "invalid operation";
   return false;
 }
 
 template <typename T>
-bool Map<T>::get_next(uint64_t, uint64_t *, Key *) {
-  // TODO: Give a naive implementation.
-  GRNXX_ERROR() << "invalid operation";
+bool Map<T>::get_next(int64_t key_id, int64_t *next_key_id, Key *next_key) {
+  // Naive implementation.
+  for (key_id = (key_id > MAP_MAX_KEY_ID) ? 0 : (key_id + 1);
+       key_id <= max_key_id(); ++key_id) {
+    if (get(key_id, next_key)) {
+      if (next_key_id) {
+        *next_key_id = key_id;
+        return true;
+      }
+    }
+  }
   return false;
 }
 
 template <typename T>
-bool Map<T>::unset(uint64_t key_id) {
-  GRNXX_ERROR() << "invalid operation";
-  return false;
+bool Map<T>::unset(int64_t key_id) {
+  // Naive implementation.
+  Key key;
+  if (!get(key_id, &key)) {
+    return false;
+  }
+  return remove(key);
 }
 
 template <typename T>
-bool Map<T>::reset(uint64_t key_id, KeyArg dest_key) {
-  GRNXX_ERROR() << "invalid operation";
-  return false;
+bool Map<T>::reset(int64_t key_id, KeyArg dest_key) {
+  // Naive implementation.
+  Key src_key;
+  if (!get(key_id, &src_key)) {
+    return false;
+  }
+  return replace(src_key, dest_key);
 }
 
 template <typename T>
-bool Map<T>::find(KeyArg, uint64_t *) {
-  // TODO: Give a naive implementation.
-  GRNXX_ERROR() << "invalid operation";
+bool Map<T>::find(KeyArg key, int64_t *key_id) {
+  // Naive implementation.
+  int64_t next_key_id = -1;
+  Key next_key;
+  while (get_next(next_key_id, &next_key_id, &next_key)) {
+    // TODO: "key" must be normalized if T is double.
+    // TODO: Also note that NaN != NaN.
+    if (key == next_key) {
+      if (key_id) {
+        *key_id = next_key_id;
+      }
+      return true;
+    }
+  }
   return false;
 }
 
 template <typename T>
-bool Map<T>::insert(KeyArg, uint64_t *) {
+bool Map<T>::add(KeyArg, int64_t *) {
   GRNXX_ERROR() << "invalid operation";
   return false;
 }
@@ -122,18 +150,45 @@ bool Map<T>::remove(KeyArg) {
 }
 
 template <typename T>
-bool Map<T>::update(KeyArg, KeyArg, uint64_t *) {
+bool Map<T>::replace(KeyArg, KeyArg, int64_t *) {
   GRNXX_ERROR() << "invalid operation";
   return false;
 }
 
 template <typename T>
-bool Map<T>::find_longest_prefix_match(KeyArg, uint64_t *, Key *) {
-  // TODO: Give a naive implementation.
+bool Map<T>::find_longest_prefix_match(KeyArg, int64_t *, Key *) {
   GRNXX_ERROR() << "invalid operation";
   return false;
 }
 
+template <>
+bool Map<Bytes>::find_longest_prefix_match(KeyArg query, int64_t *key_id,
+                                           Key *key) {
+  // Naive implementation.
+  int64_t next_key_id = -1;
+  int64_t longest_prefix_key_id = -1;
+  Key next_key;
+  Key longest_prefix_key = nullptr;
+  while (get_next(next_key_id, &next_key_id, &next_key)) {
+    if (query.starts_with(next_key)) {
+      if (next_key.size() >= longest_prefix_key.size()) {
+        longest_prefix_key_id = next_key_id;
+        longest_prefix_key = next_key;
+      }
+    }
+  }
+  if (longest_prefix_key_id >= 0) {
+    if (key_id) {
+      *key_id = longest_prefix_key_id;
+    }
+    if (key) {
+      *key = longest_prefix_key;
+    }
+    return true;
+  }
+  return false;
+}
+
 template <typename T>
 bool Map<T>::truncate() {
   GRNXX_ERROR() << "invalid operation";
@@ -157,11 +212,16 @@ MapCursor<T> *Map<T>::create_cursor(const map::CursorQuery<Key> &,
 
 template <typename T>
 MapScanner<T> *Map<T>::create_scanner(KeyArg, const Charset *) {
-  // TODO: Give a naive implementation.
   GRNXX_ERROR() << "invalid operation";
   return nullptr;
 }
 
+template <>
+MapScanner<Bytes> *Map<Bytes>::create_scanner(KeyArg query,
+                                              const Charset *charset) {
+  return map::Scanner<Bytes>::create(this, query, charset);
+}
+
 template class MapCursor<int8_t>;
 template class MapCursor<uint8_t>;
 template class MapCursor<int16_t>;
@@ -174,16 +234,6 @@ template class MapCursor<double>;
 template class MapCursor<GeoPoint>;
 template class MapCursor<Bytes>;
 
-template class MapScanner<int8_t>;
-template class MapScanner<uint8_t>;
-template class MapScanner<int16_t>;
-template class MapScanner<uint16_t>;
-template class MapScanner<int32_t>;
-template class MapScanner<uint32_t>;
-template class MapScanner<int64_t>;
-template class MapScanner<uint64_t>;
-template class MapScanner<double>;
-template class MapScanner<GeoPoint>;
 template class MapScanner<Bytes>;
 
 template class Map<int8_t>;

  Modified: lib/grnxx/map.hpp (+26 -27)
===================================================================
--- lib/grnxx/map.hpp    2013-05-15 18:29:02 +0900 (6af5e47)
+++ lib/grnxx/map.hpp    2013-05-16 12:18:02 +0900 (e8b1562)
@@ -36,9 +36,9 @@ class Charset;
 
 template <typename T> class Map;
 
-constexpr uint64_t MAP_MIN_KEY_ID     = 0;
-constexpr uint64_t MAP_MAX_KEY_ID     = (1ULL << 40) - 1;
-constexpr uint64_t MAP_INVALID_KEY_ID = MAP_MAX_KEY_ID + 1;
+constexpr int64_t MAP_MIN_KEY_ID     = 0;
+constexpr int64_t MAP_MAX_KEY_ID     = (1LL << 40) - 2;
+constexpr int64_t MAP_INVALID_KEY_ID = MAP_MAX_KEY_ID + 1;
 
 enum MapType : uint32_t {
   MAP_UNKNOWN      = 0,
@@ -94,16 +94,16 @@ class MapCursor {
   virtual bool remove();
 
   // Return the ID of the current key.
-  uint64_t key_id() const {
+  int64_t key_id() const {
     return key_id_;
   }
-  // Return a reference to the current key.
+  // Return the current key.
   const Key &key() const {
     return key_;
   }
 
  protected:
-  uint64_t key_id_;
+  int64_t key_id_;
   Key key_;
 };
 
@@ -116,8 +116,7 @@ class MapScanner {
   MapScanner();
   virtual ~MapScanner();
 
-  // Scan the rest of the query and return true iff a key is found (success).
-  // On success, the found key is accessible via accessors.
+  // Find the next key from the rest of the query and return true on success.
   virtual bool next() = 0;
 
   // Return the start position of the found key.
@@ -129,10 +128,10 @@ class MapScanner {
     return size_;
   }
   // Return the ID of the found key.
-  uint64_t key_id() const {
+  int64_t key_id() const {
     return key_id_;
   }
-  // Return a reference to the found key.
+  // Return the found key.
   const Key &key() const {
     return key_;
   }
@@ -140,7 +139,7 @@ class MapScanner {
  protected:
   uint64_t offset_;
   uint64_t size_;
-  uint64_t key_id_;
+  int64_t key_id_;
   Key key_;
 };
 
@@ -172,51 +171,51 @@ class Map {
   virtual MapType type() const = 0;
 
   // Return the minimum key ID.
-  constexpr uint64_t min_key_id() {
+  constexpr int64_t min_key_id() {
     return MAP_MIN_KEY_ID;
   }
   // Return the maximum key ID ever used.
-  // If the map is empty, the return value can be MAP_INVALID_KEY_ID.
-  virtual uint64_t max_key_id() const = 0;
-  // Return the ID of the expected next inserted ID.
-  virtual uint64_t next_key_id() const = 0;
+  // The return value can be a negative value iff the map is empty.
+  virtual int64_t max_key_id() const = 0;
+  // Return the ID of the expected next added ID.
+  virtual int64_t next_key_id() const = 0;
   // Return the number of keys.
   virtual uint64_t num_keys() const = 0;
 
   // Get a key associated with "key_id" and return true on success.
   // Assign the found key to "*key" iff "key" != nullptr.
-  virtual bool get(uint64_t key_id, Key *key = nullptr);
+  virtual bool get(int64_t key_id, Key *key = nullptr);
   // Find the next key and return true on success. The next key means the key
   // associated with the smallest valid ID that is greater than "key_id".
-  // If "key_id" < 0, this finds the first key.
+  // If "key_id" > MAP_MAX_KEY_ID, this finds the first key.
   // Assign the ID to "*next_key_id" iff "next_key_id" != nullptr.
   // Assign the key to "*next_key" iff "next_key" != nullptr.
-  virtual bool get_next(uint64_t key_id, uint64_t *next_key_id = nullptr,
+  virtual bool get_next(int64_t key_id, int64_t *next_key_id = nullptr,
                         Key *next_key = nullptr);
   // Remove a key associated with "key_id" and return true on success.
-  virtual bool unset(uint64_t key_id);
+  virtual bool unset(int64_t key_id);
   // Replace a key associated with "key_id" with "dest_key" and return true
   // on success.
-  virtual bool reset(uint64_t key_id, KeyArg dest_key);
+  virtual bool reset(int64_t key_id, KeyArg dest_key);
 
   // Find "key" and return true on success.
   // Assign the ID to "*key_id" iff "key_id" != nullptr.
-  virtual bool find(KeyArg key, uint64_t *key_id = nullptr);
-  // Insert "key" and return true on success.
+  virtual bool find(KeyArg key, int64_t *key_id = nullptr);
+  // Add "key" and return true on success.
   // Assign the ID to "*key_id" iff "key_id" != nullptr.
-  virtual bool insert(KeyArg key, uint64_t *key_id = nullptr);
+  virtual bool add(KeyArg key, int64_t *key_id = nullptr);
   // Remove "key" and return true on success.
   virtual bool remove(KeyArg key);
   // Replace "src_key" with "dest_key" and return true on success.
   // Assign the ID to "*key_id" iff "key_id" != nullptr.
-  virtual bool update(KeyArg src_key, KeyArg dest_key,
-                      uint64_t *key_id = nullptr);
+  virtual bool replace(KeyArg src_key, KeyArg dest_key,
+                      int64_t *key_id = nullptr);
 
   // Perform longest prefix matching and return true on success.
   // Assign the ID to "*key_id" iff "key_id" != nullptr.
   // Assign the key to "*key" iff "key" != nullptr.
   virtual bool find_longest_prefix_match(KeyArg query,
-                                         uint64_t *key_id = nullptr,
+                                         int64_t *key_id = nullptr,
                                          Key *key = nullptr);
 
   // Remove all the keys in "*this" and return true on success.

  Modified: lib/grnxx/map/scanner.cpp (+53 -0)
===================================================================
--- lib/grnxx/map/scanner.cpp    2013-05-15 18:29:02 +0900 (8264259)
+++ lib/grnxx/map/scanner.cpp    2013-05-16 12:18:02 +0900 (2a6db90)
@@ -17,8 +17,61 @@
 */
 #include "grnxx/map/scanner.hpp"
 
+#include <memory>
+#include <new>
+
+#include "grnxx/bytes.hpp"
+#include "grnxx/charset.hpp"
+#include "grnxx/logger.hpp"
+
+// TODO: To be removed in future.
+#include "grnxx/slice.hpp"
+
 namespace grnxx {
 namespace map {
 
+template <typename T>
+Scanner<T>::Scanner() : map_(), query_(), charset_() {}
+
+template <typename T>
+Scanner<T>::~Scanner() {}
+
+template <typename T>
+Scanner<T> *Scanner<T>::create(Map<T> *map, KeyArg query,
+                               const Charset *charset) {
+  std::unique_ptr<Scanner> scanner(new (std::nothrow) Scanner);
+  if (!scanner) {
+    GRNXX_ERROR() << "new grnxx::map::Scanner failed";
+    return nullptr;
+  }
+  scanner->map_ = map;
+  scanner->query_ = query;
+  scanner->charset_ = charset;
+  return scanner.release();
+}
+
+template <typename T>
+bool Scanner<T>::next() {
+  this->offset_ += this->size_;
+  while (this->offset_ < query_.size()) {
+    const T rest = query_.except_prefix(this->offset_);
+    if (map_->find_longest_prefix_match(rest, &this->key_id_, &this->key_)) {
+      this->size_ = this->key_.size();
+      return true;
+    }
+    // Move to the next character.
+    if (charset_) {
+      // TODO: Charset should support Bytes.
+      this->offset_ += charset_->get_char_size(Slice(rest.ptr(), rest.size()));
+    } else {
+      ++this->offset_;
+    }
+  }
+  this->size_ = 0;
+  return false;
+}
+
+template class Scanner<Bytes>;
+
 }  // namespace map
 }  // namespace grnxx

  Modified: lib/grnxx/map/scanner.hpp (+24 -0)
===================================================================
--- lib/grnxx/map/scanner.hpp    2013-05-15 18:29:02 +0900 (c91cbc9)
+++ lib/grnxx/map/scanner.hpp    2013-05-16 12:18:02 +0900 (a62b08b)
@@ -20,9 +20,33 @@
 
 #include "grnxx/features.hpp"
 
+#include "grnxx/map.hpp"
+
 namespace grnxx {
+
+class Charset;
+
 namespace map {
 
+template <typename T>
+class Scanner : public MapScanner<T> {
+ public:
+  using Key = typename MapScanner<T>::Key;
+  using KeyArg = typename MapScanner<T>::KeyArg;
+
+  Scanner();
+  ~Scanner();
+
+  static Scanner *create(Map<T> *map, KeyArg query, const Charset *charset);
+
+  bool next();
+
+ protected:
+  Map<T> *map_;
+  Key query_;
+  const Charset *charset_;
+};
+
 }  // namespace map
 }  // namespace grnxx
 
-------------- next part --------------
HTML����������������������������...
Download 

• Previous message: [Groonga-commit] [Errored] mroonga/mroonga#615 (master - 90e9555)
• Next message: [Groonga-commit] groonga/groonga at bcc70df [master] test: group index section tests
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]