Groonga - fulltext search engine.

[Groonga-commit] groonga/grnxx at 75f672f [master] Implement grnxx::map::Array.

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

• Previous message: [Groonga-commit] groonga/grnxx at aa73156 [master] Use MAP_MIN_KEY_ID instead of 0 and fix a bug of get_next().
• Next message: [Groonga-commit] groonga/grnxx at 1c0ffa0 [master] Add a test for grnxx::Array.
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

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

  New Revision: 75f672f72d425f44b57e8fd6b197daf582eda74e
  https://github.com/groonga/grnxx/commit/75f672f72d425f44b57e8fd6b197daf582eda74e

  Message:
    Implement grnxx::map::Array.

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

  Modified: lib/grnxx/map/array_map.cpp (+340 -5)
===================================================================
--- lib/grnxx/map/array_map.cpp    2013-05-16 18:44:02 +0900 (c8c6ea3)
+++ lib/grnxx/map/array_map.cpp    2013-05-16 18:53:18 +0900 (cef8bb4)
@@ -17,22 +17,357 @@
 */
 #include "grnxx/map/array_map.hpp"
 
-#include <cmath>
-#include <string>
+#include <memory>
+#include <new>
 
 #include "grnxx/geo_point.hpp"
+#include "grnxx/logger.hpp"
+#include "grnxx/map/helper.hpp"
 #include "grnxx/storage.hpp"
 
 namespace grnxx {
 namespace map {
 
+struct ArrayMapHeader {
+  MapType map_type;
+  uint32_t bitmap_storage_node_id;
+  uint32_t keys_storage_node_id;
+  int64_t max_key_id;
+  int64_t next_key_id;
+  uint64_t num_keys;
+
+  ArrayMapHeader();
+};
+
 ArrayMapHeader::ArrayMapHeader()
     : map_type(MAP_ARRAY),
-      bits_storage_node_id(STORAGE_INVALID_NODE_ID),
+      bitmap_storage_node_id(STORAGE_INVALID_NODE_ID),
       keys_storage_node_id(STORAGE_INVALID_NODE_ID),
-      max_key_id(-1),
-      next_key_id(0),
+      max_key_id(MAP_MIN_KEY_ID - 1),
+      next_key_id(MAP_MIN_KEY_ID),
       num_keys(0) {}
 
+template <typename T>
+ArrayMap<T>::ArrayMap()
+    : storage_(nullptr),
+      storage_node_id_(STORAGE_INVALID_NODE_ID),
+      header_(nullptr),
+      bitmap_(),
+      keys_() {}
+
+template <typename T>
+ArrayMap<T>::~ArrayMap() {}
+
+template <typename T>
+ArrayMap<T> *ArrayMap<T>::create(Storage *storage, uint32_t storage_node_id,
+                                 const MapOptions &options) {
+  std::unique_ptr<ArrayMap> map(new (std::nothrow) ArrayMap);
+  if (!map) {
+    GRNXX_ERROR() << "new grnxx::map::ArrayMap failed";
+    return nullptr;
+  }
+  if (!map->create_map(storage, storage_node_id, options)) {
+    return nullptr;
+  }
+  return map.release();
+}
+
+template <typename T>
+ArrayMap<T> *ArrayMap<T>::open(Storage *storage, uint32_t storage_node_id) {
+  std::unique_ptr<ArrayMap> map(new (std::nothrow) ArrayMap);
+  if (!map) {
+    GRNXX_ERROR() << "new grnxx::map::ArrayMap failed";
+    return nullptr;
+  }
+  if (!map->open_map(storage, storage_node_id)) {
+    return nullptr;
+  }
+  return map.release();
+}
+
+template <typename T>
+bool ArrayMap<T>::unlink(Storage *storage, uint32_t storage_node_id) {
+  std::unique_ptr<ArrayMap> map(ArrayMap::open(storage, storage_node_id));
+  if (!map) {
+    return false;
+  }
+  return storage->unlink_node(storage_node_id);
+}
+
+template <typename T>
+uint32_t ArrayMap<T>::storage_node_id() const {
+  return storage_node_id_;
+}
+
+template <typename T>
+MapType ArrayMap<T>::type() const {
+  return MAP_ARRAY;
+}
+
+template <typename T>
+int64_t ArrayMap<T>::max_key_id() const {
+  return header_->max_key_id;
+}
+
+template <typename T>
+int64_t ArrayMap<T>::next_key_id() const {
+  return header_->next_key_id;
+}
+
+template <typename T>
+uint64_t ArrayMap<T>::num_keys() const {
+  return header_->num_keys;
+}
+
+template <typename T>
+bool ArrayMap<T>::get(int64_t key_id, Key *key) {
+  if ((key_id < MAP_MIN_KEY_ID) || (key_id > header_->max_key_id)) {
+    return false;
+  }
+  bool bit;
+  if (!bitmap_.get(key_id, &bit)) {
+    return false;
+  }
+  if (!bit) {
+    return false;
+  }
+  if (!key) {
+    return true;
+  }
+  return keys_.get(key_id, key);
+}
+
+template <typename T>
+bool ArrayMap<T>::get_next(int64_t key_id, int64_t *next_key_id,
+                           Key *next_key) {
+  if ((key_id < MAP_MIN_KEY_ID) || (key_id > MAP_MAX_KEY_ID)) {
+    key_id = MAP_MIN_KEY_ID - 1;
+  }
+  for (++key_id; 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 ArrayMap<T>::unset(int64_t key_id) {
+  if (!get(key_id)) {
+    GRNXX_ERROR() << "not found: key_id = " << key_id;
+    return false;
+  }
+  if (!bitmap_.set(key_id, false)) {
+    return false;
+  }
+  header_->next_key_id = key_id;
+  --header_->num_keys;
+  return true;
+}
+
+template <typename T>
+bool ArrayMap<T>::reset(int64_t key_id, KeyArg dest_key) {
+  if (!get(key_id)) {
+    GRNXX_ERROR() << "not found: key_id = " << key_id;
+    return false;
+  }
+  if (find(dest_key)) {
+    GRNXX_ERROR() << "found: dest_key = " << dest_key;
+    return false;
+  }
+  if (!keys_.set(key_id, Helper<T>::normalize(dest_key))) {
+    return false;
+  }
+  return true;
+}
+
+template <typename T>
+bool ArrayMap<T>::find(KeyArg key, int64_t *key_id) {
+  const Key normalized_key = map::Helper<T>::normalize(key);
+  for (int64_t i = MAP_MIN_KEY_ID; i <= header_->max_key_id; ++i) {
+    bool bit;
+    if (!bitmap_.get(i, &bit)) {
+      return false;
+    }
+    if (bit) {
+      Key stored_key;
+      if (!keys_.get(i, &stored_key)) {
+        return false;
+      }
+      if (Helper<T>::equal_to(normalized_key, stored_key)) {
+        if (key_id) {
+          *key_id = i;
+        }
+        return true;
+      }
+    }
+  }
+  return false;
+}
+
+template <typename T>
+bool ArrayMap<T>::add(KeyArg key, int64_t *key_id) {
+  const Key normalized_key = Helper<T>::normalize(key);
+  int64_t next_key_id = header_->next_key_id;
+  int64_t next_next_key_id = MAP_INVALID_KEY_ID;
+  for (int64_t i = MAP_MIN_KEY_ID; i <= header_->max_key_id; ++i) {
+    bool bit;
+    if (!bitmap_.get(i, &bit)) {
+      return false;
+    }
+    if (bit) {
+      Key stored_key;
+      if (!keys_.get(i, &stored_key)) {
+        return false;
+      }
+      if (Helper<T>::equal_to(normalized_key, stored_key)) {
+        if (key_id) {
+          *key_id = i;
+        }
+        return false;
+      }
+    } else if ((i != next_key_id) &&
+               (next_next_key_id == MAP_INVALID_KEY_ID)) {
+      next_next_key_id = i;
+    }
+  }
+  if (!keys_.set(next_key_id, normalized_key) ||
+      !bitmap_.set(next_key_id, true)) {
+    return false;
+  }
+  if (next_key_id == (header_->max_key_id + 1)) {
+    ++header_->max_key_id;
+  }
+  if (next_next_key_id == MAP_INVALID_KEY_ID) {
+    header_->next_key_id = header_->max_key_id + 1;
+  } else {
+    header_->next_key_id = next_next_key_id;
+  }
+  ++header_->num_keys;
+  if (key_id) {
+    *key_id = next_key_id;
+  }
+  return true;
+}
+
+template <typename T>
+bool ArrayMap<T>::remove(KeyArg key) {
+  int64_t key_id;
+  if (!find(key, &key_id)) {
+    return false;
+  }
+  if (!bitmap_.set(key_id, false)) {
+    return false;
+  }
+  header_->next_key_id = key_id;
+  --header_->num_keys;
+  return true;
+}
+
+template <typename T>
+bool ArrayMap<T>::replace(KeyArg src_key, KeyArg dest_key, int64_t *key_id) {
+  const Key normalized_src_key = Helper<T>::normalize(src_key);
+  const Key normalized_dest_key = Helper<T>::normalize(dest_key);
+  int64_t src_key_id = MAP_INVALID_KEY_ID;
+  for (int64_t i = MAP_MIN_KEY_ID; i <= header_->max_key_id; ++i) {
+    bool bit;
+    if (!bitmap_.get(i, &bit)) {
+      return false;
+    }
+    if (bit) {
+      Key stored_key;
+      if (!keys_.get(i, &stored_key)) {
+        return false;
+      }
+      if (Helper<T>::equal_to(normalized_src_key, stored_key)) {
+        src_key_id = i;
+      }
+      if (Helper<T>::equal_to(normalized_dest_key, stored_key)) {
+        GRNXX_ERROR() << "found: dest_key = " << dest_key;
+        return false;
+      }
+    }
+  }
+  if (src_key_id == MAP_INVALID_KEY_ID) {
+    GRNXX_ERROR() << "not found: src_key = " << src_key;
+    return false;
+  }
+  if (!keys_.set(src_key_id, normalized_dest_key)) {
+    return false;
+  }
+  if (key_id) {
+    *key_id = src_key_id;
+  }
+  return true;
+}
+
+template <typename T>
+bool ArrayMap<T>::truncate() {
+  header_->max_key_id = MAP_MIN_KEY_ID - 1;
+  header_->next_key_id = MAP_MIN_KEY_ID;
+  header_->num_keys = 0;
+  return true;
+}
+
+template <typename T>
+bool ArrayMap<T>::create_map(Storage *storage, uint32_t storage_node_id,
+                             const MapOptions &) {
+  storage_ = storage;
+  StorageNode storage_node =
+      storage->create_node(storage_node_id, sizeof(ArrayMapHeader));
+  if (!storage_node) {
+    return false;
+  }
+  storage_node_id_ = storage_node.id();
+  header_ = static_cast<ArrayMapHeader *>(storage_node.body());
+  *header_ = ArrayMapHeader();
+  if (!bitmap_.create(storage, storage_node_id_, false)) {
+    storage->unlink_node(storage_node_id_);
+    return false;
+  }
+  header_->bitmap_storage_node_id = bitmap_.storage_node_id();
+  if (!keys_.create(storage, storage_node_id_)) {
+    storage->unlink_node(storage_node_id_);
+    return false;
+  }
+  header_->keys_storage_node_id = keys_.storage_node_id();
+  return true;
+}
+
+template <typename T>
+bool ArrayMap<T>::open_map(Storage *storage, uint32_t storage_node_id) {
+  storage_ = storage;
+  StorageNode storage_node = storage->open_node(storage_node_id);
+  if (!storage_node) {
+    return false;
+  }
+  if (storage_node.size() < sizeof(ArrayMapHeader)) {
+    GRNXX_ERROR() << "invalid format: size = " << storage_node.size()
+                  << ", header_size = " << sizeof(ArrayMapHeader);
+    return false;
+  }
+  storage_node_id_ = storage_node_id;
+  header_ = static_cast<ArrayMapHeader *>(storage_node.body());
+  if (!bitmap_.open(storage, header_->bitmap_storage_node_id) ||
+      !keys_.open(storage, header_->keys_storage_node_id)) {
+    return false;
+  }
+  return true;
+}
+
+template class ArrayMap<int8_t>;
+template class ArrayMap<uint8_t>;
+template class ArrayMap<int16_t>;
+template class ArrayMap<uint16_t>;
+template class ArrayMap<int32_t>;
+template class ArrayMap<uint32_t>;
+template class ArrayMap<int64_t>;
+template class ArrayMap<uint64_t>;
+template class ArrayMap<double>;
+template class ArrayMap<GeoPoint>;
+
 }  // namespace map
 }  // namespace grnxx

  Modified: lib/grnxx/map/array_map.hpp (+11 -27)
===================================================================
--- lib/grnxx/map/array_map.hpp    2013-05-16 18:44:02 +0900 (23fb874)
+++ lib/grnxx/map/array_map.hpp    2013-05-16 18:53:18 +0900 (17d0330)
@@ -22,20 +22,12 @@
 #include "grnxx/array.hpp"
 
 namespace grnxx {
-namespace map {
 
 class Storage;
 
-struct ArrayMapHeader {
-  MapType map_type;
-  uint32_t bits_storage_node_id;
-  uint32_t keys_storage_node_id;
-  int64_t max_key_id;
-  int64_t next_key_id;
-  uint64_t num_keys;
+namespace map {
 
-  ArrayMapHeader();
-};
+struct ArrayMapHeader;
 
 template <typename T>
 class ArrayMap : public Map<T> {
@@ -61,16 +53,15 @@ class ArrayMap : public Map<T> {
   uint64_t num_keys() const;
 
   bool get(int64_t key_id, Key *key = nullptr);
-//  bool get_next(int64_t key_id, int64_t *next_key_id = nullptr,
-//                        Key *next_key = nullptr);
-//  bool unset(int64_t key_id);
-//  bool reset(int64_t key_id, KeyArg dest_key);
+  bool get_next(int64_t key_id, int64_t *next_key_id = nullptr,
+                Key *next_key = nullptr);
+  bool unset(int64_t key_id);
+  bool reset(int64_t key_id, KeyArg dest_key);
 
   bool find(KeyArg key, int64_t *key_id = nullptr);
   bool add(KeyArg key, int64_t *key_id = nullptr);
   bool remove(KeyArg key);
-  bool replace(KeyArg src_key, KeyArg dest_key,
-                      int64_t *key_id = nullptr);
+  bool replace(KeyArg src_key, KeyArg dest_key, int64_t *key_id = nullptr);
 
   bool truncate();
 
@@ -78,19 +69,12 @@ class ArrayMap : public Map<T> {
   Storage *storage_;
   uint32_t storage_node_id_;
   ArrayMapHeader *header_;
-  Array<uint32_t> bits_;
+  Array<bool> bitmap_;
   Array<T> keys_;
 
-  bool get_bit(int64_t key_id) {
-    return bits_[key_id / 32] & (1U << (key_id % 32));
-  }
-  void set_bit(int64_t key_id, bool bit) {
-    if (bit) {
-      bits_[key_id / 32] |= 1U << (key_id % 32);
-    } else {
-      bits_[key_id / 32] &= ~(1U << (key_id % 32));
-    }
-  }
+  bool create_map(Storage *storage, uint32_t storage_node_id,
+                  const MapOptions &options);
+  bool open_map(Storage *storage, uint32_t storage_node_id);
 };
 
 }  // namespace map
-------------- next part --------------
HTML����������������������������...
Télécharger 

• Previous message: [Groonga-commit] groonga/grnxx at aa73156 [master] Use MAP_MIN_KEY_ID instead of 0 and fix a bug of get_next().
• Next message: [Groonga-commit] groonga/grnxx at 1c0ffa0 [master] Add a test for grnxx::Array.
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]