Groonga - fulltext search engine.

[Groonga-commit] groonga/grnxx at 8278355 [master] Implement grnxx::map::Patricia<Bytes>.

susumu.yata null+****@clear*****
Tue Jun 18 17:00:55 JST 2013

• Previous message: [Groonga-commit] [Fixed] groonga/groonga#1904 (master - 514a883)
• Next message: [Groonga-commit] groonga/groonga at 7d05b38 [master] Receive a context.
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

susumu.yata	2013-06-18 17:00:55 +0900 (Tue, 18 Jun 2013)

  New Revision: 8278355bf2ccb757c06ecb457a21f32f16990216
  https://github.com/groonga/grnxx/commit/8278355bf2ccb757c06ecb457a21f32f16990216

  Message:
    Implement grnxx::map::Patricia<Bytes>.

  Added files:
    lib/grnxx/map/patricia/node.hpp
  Modified files:
    lib/grnxx/map/patricia.cpp
    lib/grnxx/map/patricia.hpp
    lib/grnxx/map/patricia/Makefile.am
    lib/grnxx/map/patricia/dummy.cpp
    lib/grnxx/map/patricia/header.cpp
    lib/grnxx/map/patricia/header.hpp

  Modified: lib/grnxx/map/patricia.cpp (+510 -5)
===================================================================
--- lib/grnxx/map/patricia.cpp    2013-06-17 17:42:28 +0900 (0267615)
+++ lib/grnxx/map/patricia.cpp    2013-06-18 17:00:55 +0900 (056e690)
@@ -28,12 +28,26 @@
 
 namespace grnxx {
 namespace map {
+namespace {
+
+constexpr uint64_t ROOT_NODE_ID = 0;
+
+using patricia::NODE_INVALID_OFFSET;
+
+using patricia::NODE_DEAD;
+using patricia::NODE_LEAF;
+using patricia::NODE_BRANCH;
+using patricia::NODE_TERMINAL;
+
+}  // namespace
 
 template <typename T>
 Patricia<T>::Patricia()
     : storage_(nullptr),
       storage_node_id_(STORAGE_INVALID_NODE_ID),
-      header_(nullptr) {}
+      header_(nullptr),
+      nodes_(),
+      keys_() {}
 
 template <typename T>
 Patricia<T>::~Patricia() {}
@@ -74,17 +88,17 @@ uint32_t Patricia<T>::storage_node_id() const {
 
 template <typename T>
 MapType Patricia<T>::type() const {
-  return MAP_DOUBLE_ARRAY;
+  return MAP_PATRICIA;
 }
 
 template <typename T>
 int64_t Patricia<T>::max_key_id() const {
-  return header_->max_key_id;
+  return keys_->max_key_id();
 }
 
 template <typename T>
 uint64_t Patricia<T>::num_keys() const {
-  return header_->num_keys;
+  return keys_->num_keys();
 }
 
 template <typename T>
@@ -131,7 +145,498 @@ template class Patricia<int64_t>;
 template class Patricia<uint64_t>;
 template class Patricia<double>;
 template class Patricia<GeoPoint>;
-template class Patricia<Bytes>;
+
+Patricia<Bytes>::Patricia()
+    : storage_(nullptr),
+      storage_node_id_(STORAGE_INVALID_NODE_ID),
+      header_(nullptr),
+      nodes_(),
+      keys_() {}
+
+Patricia<Bytes>::~Patricia() {}
+
+Patricia<Bytes> *Patricia<Bytes>::create(Storage *storage,
+                                         uint32_t storage_node_id,
+                                         const MapOptions &options) {
+  std::unique_ptr<Patricia> map(new (std::nothrow) Patricia);
+  if (!map) {
+    GRNXX_ERROR() << "new grnxx::map::Patricia failed";
+    return nullptr;
+  }
+  if (!map->create_map(storage, storage_node_id, options)) {
+    return nullptr;
+  }
+  return map.release();
+}
+
+Patricia<Bytes> *Patricia<Bytes>::open(Storage *storage,
+                                       uint32_t storage_node_id) {
+  std::unique_ptr<Patricia> map(new (std::nothrow) Patricia);
+  if (!map) {
+    GRNXX_ERROR() << "new grnxx::map::Patricia failed";
+    return nullptr;
+  }
+  if (!map->open_map(storage, storage_node_id)) {
+    return nullptr;
+  }
+  return map.release();
+}
+
+uint32_t Patricia<Bytes>::storage_node_id() const {
+  return storage_node_id_;
+}
+
+MapType Patricia<Bytes>::type() const {
+  return MAP_PATRICIA;
+}
+
+int64_t Patricia<Bytes>::max_key_id() const {
+  return keys_->max_key_id();
+}
+
+uint64_t Patricia<Bytes>::num_keys() const {
+  return keys_->num_keys();
+}
+
+bool Patricia<Bytes>::get(int64_t key_id, Key *key) {
+  if ((key_id < MAP_MIN_KEY_ID) || (key_id > keys_->max_key_id())) {
+    // Out of range.
+    return false;
+  }
+  bool bit;
+  if (!keys_->get_bit(key_id, &bit)) {
+    // Error.
+    return false;
+  }
+  if (!bit) {
+    // Not found.
+    return false;
+  }
+  if (!keys_->get_key(key_id, key)) {
+    // Error.
+    return false;
+  }
+  return true;
+}
+
+bool Patricia<Bytes>::unset(int64_t key_id) {
+  Key key;
+  if (!get(key_id, &key)) {
+    // Not found or error.
+    return false;
+  }
+  const uint64_t bit_size = key.size() * 8;
+  uint64_t node_id = ROOT_NODE_ID;
+  Node *prev_node = nullptr;
+  for ( ; ; ) {
+    Node * const node = nodes_->get_pointer(node_id);
+    if (!node) {
+      // Error.
+      return false;
+    }
+    switch (node->status()) {
+      case NODE_DEAD: {
+        // Not found.
+        return false;
+      }
+      case NODE_LEAF: {
+        if (node->key_id() != key_id) {
+          // Not found.
+          return false;
+        }
+        keys_->unset(key_id);
+        if (prev_node) {
+          Node * const sibling_node = node + (node_id ^ 1) - node_id;
+          *prev_node = *sibling_node;
+        } else {
+          *node = Node::dead_node();
+        }
+        return true;
+      }
+      case NODE_BRANCH: {
+        if (node->bit_pos() >= bit_size) {
+          // Not found.
+          return false;
+        }
+        node_id = node->offset() +
+                  ((key[node->bit_pos() / 8] >> (node->bit_pos() % 8)) & 1);
+        break;
+      }
+      case NODE_TERMINAL: {
+        if (node->bit_size() > bit_size) {
+          // Not found.
+          return false;
+        }
+        node_id = node->offset() + (node->bit_size() < bit_size);
+        break;
+      }
+    }
+    prev_node = node;
+  }
+}
+
+//bool Patricia<Bytes>::reset(int64_t key_id, KeyArg dest_key) {
+//  // TODO
+//  return false;
+//}
+
+bool Patricia<Bytes>::find(KeyArg key, int64_t *key_id) {
+  const uint64_t bit_size = key.size() * 8;
+  uint64_t node_id = ROOT_NODE_ID;
+  for ( ; ; ) {
+    Node node;
+    if (!nodes_->get(node_id, &node)) {
+      // Error.
+      return false;
+    }
+    switch (node.status()) {
+      case NODE_DEAD: {
+        // Not found.
+        return false;
+      }
+      case NODE_LEAF: {
+        Key stored_key;
+        if (!keys_->get_key(node.key_id(), &stored_key)) {
+          // Error.
+          return false;
+        }
+        if (key != stored_key) {
+          // Not found.
+          return false;
+        }
+        if (key_id) {
+          *key_id = node.key_id();
+        }
+        return true;
+      }
+      case NODE_BRANCH: {
+        if (node.bit_pos() >= bit_size) {
+          // Not found.
+          return false;
+        }
+        node_id = node.offset() +
+                  ((key[node.bit_pos() / 8] >> (node.bit_pos() % 8)) & 1);
+        break;
+      }
+      case NODE_TERMINAL: {
+        if (node.bit_size() > bit_size) {
+          // Not found.
+          return false;
+        }
+        node_id = node.offset() + (node.bit_size() < bit_size);
+        break;
+      }
+    }
+  }
+}
+
+bool Patricia<Bytes>::add(KeyArg key, int64_t *key_id) {
+  const uint64_t bit_size = key.size() * 8;
+  uint64_t node_id = ROOT_NODE_ID;
+  Node * node;
+  for (node = nodes_->get_pointer(node_id);
+       node && (node->status() != NODE_LEAF);
+       node = nodes_->get_pointer(node_id)) {
+    switch (node->status()) {
+      case NODE_DEAD: {
+        // The patricia is empty.
+        int64_t next_key_id;
+        if (!keys_->add(key, &next_key_id)) {
+          // Error.
+          return false;
+        }
+        *node = Node::leaf_node(next_key_id);
+        if (key_id) {
+          *key_id = next_key_id;
+        }
+        return true;
+      }
+      case NODE_BRANCH: {
+        node_id = node->offset();
+        if (node->bit_pos() < bit_size) {
+          node_id += (key[node->bit_pos() / 8] >> (node->bit_pos() % 8)) & 1;
+        }
+        break;
+      }
+      case NODE_TERMINAL: {
+        node_id = node->offset() + (node->bit_size() < bit_size);
+        break;
+      }
+    }
+  }
+  if (!node) {
+    // Error.
+    return false;
+  }
+  // "node" points to a leaf node.
+  Key stored_key;
+  if (!keys_->get_key(node->key_id(), &stored_key)) {
+    // Error.
+    return false;
+  }
+  const uint64_t min_size =
+      (key.size() < stored_key.size()) ? key.size() : stored_key.size();
+  uint64_t count;
+  for (count = 0; count < min_size; ++count) {
+    if (key[count] != stored_key[count]) {
+      break;
+    }
+  }
+  if (count < min_size) {
+    const uint8_t diff = key[count] ^ stored_key[count];
+    count *= 8;
+    count += bit_scan_forward(diff);
+  } else {
+    if (key.size() == stored_key.size()) {
+      // Found.
+      if (key_id) {
+        *key_id = node->key_id();
+      }
+      return false;
+    }
+    count *= 8;
+  }
+  Node * const next_nodes = nodes_->get_pointer(header_->next_node_id);
+  node_id = ROOT_NODE_ID;
+  for (node = nodes_->get_pointer(node_id);
+       node && (node->status() != NODE_LEAF);
+       node = nodes_->get_pointer(node_id)) {
+    switch (node->status()) {
+      case NODE_BRANCH: {
+        if (count <= node->bit_pos()) {
+          int64_t next_key_id;
+          if (!keys_->add(key, &next_key_id)) {
+            // Error.
+            return false;
+          }
+          if (count == bit_size) {
+            // Create a terminal node.
+            next_nodes[0] = Node::leaf_node(next_key_id);
+            next_nodes[1] = *node;
+            *node = Node::terminal_node(count, header_->next_node_id);
+          } else {
+            // Create a branch node.
+            if (key[count / 8] & (1U << (count % 8))) {
+              next_nodes[0] = *node;
+              next_nodes[1] = Node::leaf_node(next_key_id);
+            } else {
+              next_nodes[0] = Node::leaf_node(next_key_id);
+              next_nodes[1] = *node;
+            }
+            *node = Node::branch_node(count, header_->next_node_id);
+          }
+          header_->next_node_id += 2;
+          if (key_id) {
+            *key_id = next_key_id;
+          }
+          return true;
+        }
+        node_id = node->offset();
+        if (node->bit_pos() < count) {
+          node_id += (key[node->bit_pos() / 8] >> (node->bit_pos() % 8)) & 1;
+        }
+        break;
+      }
+      case NODE_TERMINAL: {
+        if (count < node->bit_size()) {
+          int64_t next_key_id;
+          if (!keys_->add(key, &next_key_id)) {
+            // Error.
+            return false;
+          }
+          if (count == bit_size) {
+            // Create a terminal node.
+            next_nodes[0] = Node::leaf_node(next_key_id);
+            next_nodes[1] = *node;
+            *node = Node::terminal_node(count, header_->next_node_id);
+          } else {
+            // Create a branch node.
+            if (key[count / 8] & (1U << (count % 8))) {
+              next_nodes[0] = *node;
+              next_nodes[1] = Node::leaf_node(next_key_id);
+            } else {
+              next_nodes[0] = Node::leaf_node(next_key_id);
+              next_nodes[1] = *node;
+            }
+            *node = Node::branch_node(count, header_->next_node_id);
+          }
+          header_->next_node_id += 2;
+          if (key_id) {
+            *key_id = next_key_id;
+          }
+          return true;
+        }
+        node_id = node->offset() + (node->bit_size() < bit_size);
+        break;
+      }
+    }
+  }
+  if (!node) {
+    // Error.
+    return false;
+  }
+  int64_t next_key_id;
+  if (!keys_->add(key, &next_key_id)) {
+    // Error.
+    return false;
+  }
+  if (count == bit_size) {
+    // Create a terminal node.
+    next_nodes[0] = Node::leaf_node(next_key_id);
+    next_nodes[1] = *node;
+    *node = Node::terminal_node(count, header_->next_node_id);
+  } else if (count == (stored_key.size() * 8)) {
+    // Create a terminal node.
+    next_nodes[0] = *node;
+    next_nodes[1] = Node::leaf_node(next_key_id);
+    *node = Node::terminal_node(count, header_->next_node_id);
+  } else {
+    // Create a branch node.
+    if (key[count / 8] & (1U << (count % 8))) {
+      next_nodes[0] = *node;
+      next_nodes[1] = Node::leaf_node(next_key_id);
+    } else {
+      next_nodes[0] = Node::leaf_node(next_key_id);
+      next_nodes[1] = *node;
+    }
+    *node = Node::branch_node(count, header_->next_node_id);
+  }
+  header_->next_node_id += 2;
+  if (key_id) {
+    *key_id = next_key_id;
+  }
+  return true;
+}
+
+bool Patricia<Bytes>::remove(KeyArg key) {
+  const uint64_t bit_size = key.size() * 8;
+  uint64_t node_id = ROOT_NODE_ID;
+  Node * prev_node = nullptr;
+  for ( ; ; ) {
+    Node * const node = nodes_->get_pointer(node_id);
+    if (!node) {
+      // Error.
+      return false;
+    }
+    switch (node->status()) {
+      case NODE_DEAD: {
+        // Not found.
+        return false;
+      }
+      case NODE_LEAF: {
+        Key stored_key;
+        if (!keys_->get_key(node->key_id(), &stored_key)) {
+          // Error.
+          return false;
+        }
+        if (stored_key != key) {
+          // Not found.
+          return false;
+        }
+        keys_->unset(node->key_id());
+        if (prev_node) {
+          Node * const sibling_node = node + (node_id ^ 1) - node_id;
+          *prev_node = *sibling_node;
+        } else {
+          *node = Node::dead_node();
+        }
+        return true;
+      }
+      case NODE_BRANCH: {
+        if (node->bit_pos() >= bit_size) {
+          // Not found.
+          return false;
+        }
+        node_id = node->offset() +
+                  ((key[node->bit_pos() / 8] >> (node->bit_pos() % 8)) & 1);
+        break;
+      }
+      case NODE_TERMINAL: {
+        if (node->bit_size() > bit_size) {
+          // Not found.
+          return false;
+        }
+        node_id = node->offset() + (node->bit_size() < bit_size);
+        break;
+      }
+    }
+    prev_node = node;
+  }
+}
+
+//bool Patricia<Bytes>::replace(KeyArg src_key, KeyArg dest_key,
+//                              int64_t *key_id) {
+//  // TODO
+//  return false;
+//}
+
+//bool Patricia<Bytes>::find_longest_prefix_match(KeyArg query, int64_t *key_id,
+//                                                Key *key) {
+//  // TODO
+//  return false;
+//}
+
+bool Patricia<Bytes>::truncate() {
+  Node * const root_node = nodes_->get_pointer(ROOT_NODE_ID);
+  if (!root_node) {
+    return false;
+  }
+  if (!keys_->truncate()) {
+    return false;
+  }
+  *root_node = Node::dead_node();
+  return true;
+}
+
+bool Patricia<Bytes>::create_map(Storage *storage, uint32_t storage_node_id,
+                                 const MapOptions &) {
+  storage_ = storage;
+  StorageNode storage_node =
+      storage->create_node(storage_node_id, sizeof(Header));
+  if (!storage_node) {
+    return false;
+  }
+  storage_node_id_ = storage_node.id();
+  header_ = static_cast<Header *>(storage_node.body());
+  *header_ = Header();
+  nodes_.reset(NodeArray::create(storage, storage_node_id_));
+  keys_.reset(KeyStore<Bytes>::create(storage, storage_node_id_));
+  if (!nodes_ || !keys_) {
+    storage->unlink_node(storage_node_id_);
+    return false;
+  }
+  header_->nodes_storage_node_id = nodes_->storage_node_id();
+  header_->keys_storage_node_id = keys_->storage_node_id();
+  Node * const root_node = nodes_->get_pointer(ROOT_NODE_ID);
+  if (!root_node) {
+    storage->unlink_node(storage_node_id_);
+    return false;
+  }
+  *root_node = Node::dead_node();
+  return true;
+}
+
+bool Patricia<Bytes>::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(Header)) {
+    GRNXX_ERROR() << "invalid format: size = " << storage_node.size()
+                  << ", header_size = " << sizeof(Header);
+    return false;
+  }
+  storage_node_id_ = storage_node_id;
+  header_ = static_cast<Header *>(storage_node.body());
+  // TODO: Check the format.
+  nodes_.reset(NodeArray::open(storage, header_->nodes_storage_node_id));
+  keys_.reset(KeyStore<Bytes>::open(storage, header_->keys_storage_node_id));
+  if (!nodes_ || !keys_) {
+    return false;
+  }
+  return true;
+}
 
 }  // namespace map
 }  // namespace grnxx

  Modified: lib/grnxx/map/patricia.hpp (+58 -0)
===================================================================
--- lib/grnxx/map/patricia.hpp    2013-06-17 17:42:28 +0900 (207da4a)
+++ lib/grnxx/map/patricia.hpp    2013-06-18 17:00:55 +0900 (bedac35)
@@ -22,7 +22,11 @@
 
 #include <memory>
 
+#include "grnxx/array.hpp"
+#include "grnxx/bytes.hpp"
 #include "grnxx/map.hpp"
+#include "grnxx/map/key_store.hpp"
+#include "grnxx/map/patricia/node.hpp"
 #include "grnxx/types.hpp"
 
 namespace grnxx {
@@ -38,6 +42,9 @@ struct Header;
 
 template <typename T>
 class Patricia : public Map<T> {
+  using Node = patricia::Node;
+  using NodeArray = Array<Node, 65536, 8192, 8192>;
+
  public:
   using Header = patricia::Header;
   using Key = typename Map<T>::Key;
@@ -73,6 +80,57 @@ class Patricia : public Map<T> {
   Storage *storage_;
   uint32_t storage_node_id_;
   Header *header_;
+  std::unique_ptr<NodeArray> nodes_;
+  std::unique_ptr<KeyStore<T>> keys_;
+
+  bool create_map(Storage *storage, uint32_t storage_node_id,
+                  const MapOptions &options);
+  bool open_map(Storage *storage, uint32_t storage_node_id);
+};
+
+template <>
+class Patricia<Bytes> : public Map<Bytes> {
+  using Node = patricia::Node;
+  using NodeArray = Array<Node>;
+
+ public:
+  using Header = patricia::Header;
+  using Key = typename Map<Bytes>::Key;
+  using KeyArg = typename Map<Bytes>::KeyArg;
+  using Cursor = typename Map<Bytes>::Cursor;
+
+  Patricia();
+  ~Patricia();
+
+  static Patricia *create(Storage *storage, uint32_t storage_node_id,
+                          const MapOptions &options = MapOptions());
+  static Patricia *open(Storage *storage, uint32_t storage_node_id);
+
+  uint32_t storage_node_id() const;
+  MapType type() const;
+
+  int64_t max_key_id() const;
+  uint64_t num_keys() const;
+
+  bool get(int64_t key_id, Key *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 find_longest_prefix_match(KeyArg query, int64_t *key_id, Key *key);
+
+  bool truncate();
+
+ private:
+  Storage *storage_;
+  uint32_t storage_node_id_;
+  Header *header_;
+  std::unique_ptr<NodeArray> nodes_;
+  std::unique_ptr<KeyStore<Bytes>> keys_;
 
   bool create_map(Storage *storage, uint32_t storage_node_id,
                   const MapOptions &options);

  Modified: lib/grnxx/map/patricia/Makefile.am (+2 -1)
===================================================================
--- lib/grnxx/map/patricia/Makefile.am    2013-06-17 17:42:28 +0900 (232d00b)
+++ lib/grnxx/map/patricia/Makefile.am    2013-06-18 17:00:55 +0900 (17e7ebf)
@@ -9,4 +9,5 @@ libgrnxx_map_patricia_la_SOURCES =	\
 libgrnxx_map_patricia_includedir = ${includedir}/grnxx/map/patricia
 libgrnxx_map_patricia_include_HEADERS =	\
 	dummy.hpp			\
-	header.hpp
+	header.hpp			\
+	node.hpp

  Modified: lib/grnxx/map/patricia/dummy.cpp (+1 -0)
===================================================================
--- lib/grnxx/map/patricia/dummy.cpp    2013-06-17 17:42:28 +0900 (c54fb55)
+++ lib/grnxx/map/patricia/dummy.cpp    2013-06-18 17:00:55 +0900 (28aeb81)
@@ -18,6 +18,7 @@
 #include "grnxx/map/patricia/dummy.hpp"
 
 #include "grnxx/map/patricia/header.hpp"
+#include "grnxx/map/patricia/node.hpp"
 
 namespace grnxx {
 namespace map {

  Modified: lib/grnxx/map/patricia/header.cpp (+4 -3)
===================================================================
--- lib/grnxx/map/patricia/header.cpp    2013-06-17 17:42:28 +0900 (5991821)
+++ lib/grnxx/map/patricia/header.cpp    2013-06-18 17:00:55 +0900 (abe4727)
@@ -24,9 +24,10 @@ namespace map {
 namespace patricia {
 
 Header::Header()
-    : map_type(MAP_ARRAY),
-      max_key_id(MAP_MIN_KEY_ID - 1),
-      num_keys(0) {}
+    : map_type(MAP_PATRICIA),
+      next_node_id(2),
+      nodes_storage_node_id(STORAGE_INVALID_NODE_ID),
+      keys_storage_node_id(STORAGE_INVALID_NODE_ID) {}
 
 }  // namespace patricia
 }  // namespace map

  Modified: lib/grnxx/map/patricia/header.hpp (+3 -2)
===================================================================
--- lib/grnxx/map/patricia/header.hpp    2013-06-17 17:42:28 +0900 (ae0e474)
+++ lib/grnxx/map/patricia/header.hpp    2013-06-18 17:00:55 +0900 (05fa44c)
@@ -29,8 +29,9 @@ namespace patricia {
 
 struct Header {
   MapType map_type;
-  int64_t max_key_id;
-  uint64_t num_keys;
+  uint64_t next_node_id;
+  uint32_t nodes_storage_node_id;
+  uint32_t keys_storage_node_id;
 
   Header();
 };

  Added: lib/grnxx/map/patricia/node.hpp (+140 -0) 100644
===================================================================
--- /dev/null
+++ lib/grnxx/map/patricia/node.hpp    2013-06-18 17:00:55 +0900 (5c14d98)
@@ -0,0 +1,140 @@
+/*
+  Copyright (C) 2012-2013  Brazil, Inc.
+
+  This library is free software; you can redistribute it and/or
+  modify it under the terms of the GNU Lesser General Public
+  License as published by the Free Software Foundation; either
+  version 2.1 of the License, or (at your option) any later version.
+
+  This library is distributed in the hope that it will be useful,
+  but WITHOUT ANY WARRANTY; without even the implied warranty of
+  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+  Lesser General Public License for more details.
+
+  You should have received a copy of the GNU Lesser General Public
+  License along with this library; if not, write to the Free Software
+  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
+*/
+#ifndef GRNXX_MAP_PATRICIA_NODE_HPP
+#define GRNXX_MAP_PATRICIA_NODE_HPP
+
+#include "grnxx/features.hpp"
+
+#include "grnxx/bytes.hpp"
+#include "grnxx/types.hpp"
+
+namespace grnxx {
+namespace map {
+namespace patricia {
+
+constexpr uint64_t NODE_INVALID_OFFSET = 0;
+
+enum NodeStatus : uint64_t {
+  NODE_DEAD     = 0,
+  NODE_LEAF     = 1,
+  NODE_BRANCH   = 2,
+  NODE_TERMINAL = 3
+};
+
+//constexpr uint64_t NODE_DEAD = 0;
+//constexpr uint64_t NODE_LEAF = 1;
+//constexpr uint64_t NODE_BRANCH = 2;
+//constexpr uint64_t NODE_TERMINAL = 3;
+
+// The internal structure is as follows:
+// - Common
+//   62-63 ( 2): status (DEAD, LEAF, BRANCH, TERMINAL)
+// - Leaf: LEAF
+//    0-39 (40): key_id
+//   40-61 (22): reserved
+// - Branch or Terminal: BRANCH || TERMINAL
+//   16-57 (42): offset
+//   58-61 ( 4): reserved
+// - Branch: BRANCH
+//    0-15 (16): bit_pos
+// - Terminal: TERMINAL
+//    0-15 (16): bit_size
+// where 0 is the LSB and 63 is the MSB.
+
+class Node {
+  static constexpr uint64_t STATUS_MASK    = (1ULL << 2) - 1;
+  static constexpr uint8_t  STATUS_SHIFT   = 62;
+
+  static constexpr uint64_t KEY_ID_MASK    = (1ULL << 40) - 1;
+  static constexpr uint8_t  KEY_ID_SHIFT   = 0;
+
+  static constexpr uint64_t OFFSET_MASK    = (1ULL << 42) - 1;
+  static constexpr uint8_t  OFFSET_SHIFT   = 16;
+
+  static constexpr uint64_t BIT_POS_MASK   = (1ULL << 16) - 1;
+  static constexpr uint8_t  BIT_POS_SHIFT  = 0;
+
+  static constexpr uint64_t BIT_SIZE_MASK  = (1ULL << 16) - 1;
+  static constexpr uint8_t  BIT_SIZE_SHIFT = 0;
+
+ public:
+
+  Node() = default;
+
+  // Create a node that has neither descendants nor an associated key.
+  static Node dead_node() {
+    return Node((NODE_DEAD << STATUS_SHIFT));
+  }
+  // Create a node that has an associated key that is identified by "key_id".
+  static Node leaf_node(int64_t key_id) {
+    return Node((NODE_LEAF << STATUS_SHIFT) |
+                ((key_id & KEY_ID_MASK) << KEY_ID_SHIFT));
+  }
+  // Create a node that works as a 0/1 branch.
+  // If key["bit_pos"] == 0, the next node ID is "offset".
+  // Otherwise, the next node ID is "offset" + 1.
+  static Node branch_node(uint64_t bit_pos, uint64_t offset) {
+    return Node((NODE_BRANCH << STATUS_SHIFT) |
+                ((bit_pos & BIT_POS_MASK) << BIT_POS_SHIFT) |
+                ((offset & OFFSET_MASK) << OFFSET_SHIFT));
+  }
+  // Create a node that works as a short/long branch.
+  // If key_size <= "bit_size", the next node ID is "offset".
+  // Otherwise, the next node ID is "offset" + 1.
+  static Node terminal_node(uint64_t bit_size, uint64_t offset) {
+    return Node((NODE_TERMINAL << STATUS_SHIFT) |
+                ((bit_size & BIT_SIZE_MASK) << BIT_SIZE_SHIFT) |
+                ((offset & OFFSET_MASK) << OFFSET_SHIFT));
+  }
+
+  // Return the node status.
+  uint64_t status() const {
+    return (value_ >> STATUS_SHIFT) & STATUS_MASK;
+  }
+
+  // Return the associated key ID.
+  int64_t key_id() const {
+    return (value_ >> KEY_ID_SHIFT) & KEY_ID_MASK;
+  }
+
+  // Return the offset to the next nodes.
+  uint64_t offset() const {
+    return (value_ >> OFFSET_SHIFT) & OFFSET_MASK;
+  }
+
+  // Return the position of the branch.
+  uint64_t bit_pos() const {
+    return (value_ >> BIT_POS_SHIFT) & BIT_POS_MASK;
+  }
+
+  // Return the branch condition.
+  uint64_t bit_size() const {
+    return (value_ >> BIT_SIZE_SHIFT) & BIT_SIZE_MASK;
+  }
+
+ private:
+  uint64_t value_;
+
+  explicit Node(uint64_t value) : value_(value) {}
+};
+
+}  // namespace patricia
+}  // namespace map
+}  // namespace grnxx
+
+#endif  // GRNXX_MAP_PATRICIA_NODE_HPP
-------------- next part --------------
HTML����������������������������...
下载 

• Previous message: [Groonga-commit] [Fixed] groonga/groonga#1904 (master - 514a883)
• Next message: [Groonga-commit] groonga/groonga at 7d05b38 [master] Receive a context.
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]