[Groonga-commit] groonga/grnxx [master] Add grnxx::alpha::DoubleArray::remove().

Back to archive index

susumu.yata null+****@clear*****
Thu Jan 31 11:35:35 JST 2013


susumu.yata	2013-01-31 11:35:35 +0900 (Thu, 31 Jan 2013)

  New Revision: c6535b992d1c7412ff49c4f5ea42c866d0020e65
  https://github.com/groonga/grnxx/commit/c6535b992d1c7412ff49c4f5ea42c866d0020e65

  Log:
    Add grnxx::alpha::DoubleArray::remove().

  Modified files:
    lib/alpha/double_array.cpp
    lib/alpha/double_array.hpp

  Modified: lib/alpha/double_array.cpp (+49 -4)
===================================================================
--- lib/alpha/double_array.cpp    2013-01-30 16:14:57 +0900 (a387280)
+++ lib/alpha/double_array.cpp    2013-01-31 11:35:35 +0900 (7b644dc)
@@ -171,6 +171,51 @@ bool DoubleArrayImpl::insert(const uint8_t *ptr, uint64_t length,
   return true;
 }
 
+bool DoubleArrayImpl::remove(int64_t key_id) {
+  if ((key_id < 0) || (key_id > header_->max_key_id())) {
+    return false;
+  }
+  const DoubleArrayEntry entry = entries_[key_id];
+  if (!entry) {
+    return false;
+  }
+  const DoubleArrayKey &key = get_key(entry.key_pos());
+  return remove(static_cast<const uint8_t *>(key.ptr()), entry.key_length());
+}
+
+bool DoubleArrayImpl::remove(const uint8_t *ptr, uint64_t length) {
+  // TODO: Exclusive access control is required.
+//  GRN_DAT_THROW_IF(STATUS_ERROR, (status_flags() & CHANGING_MASK) != 0);
+//  StatusFlagManager status_flag_manager(header_, REMOVING_FLAG);
+
+//  GRN_DAT_DEBUG_THROW_IF((ptr == NULL) && (length != 0));
+
+  uint64_t node_id = root_node_id();
+  uint64_t query_pos = 0;
+  if (!search_leaf(ptr, length, node_id, query_pos)) {
+    return false;
+  }
+
+  if (length != nodes_[node_id].key_length()) {
+    return false;
+  }
+
+  const uint64_t key_pos = nodes_[node_id].key_pos();
+  const DoubleArrayKey &key = get_key(key_pos);
+  if (!key.equals_to(ptr, length, query_pos)) {
+    return false;
+  }
+
+  const uint64_t key_id = key.id();
+  nodes_[node_id].set_offset(DOUBLE_ARRAY_INVALID_OFFSET);
+  entries_[key_id].set_next(header_->next_key_id());
+
+  header_->set_next_key_id(key_id);
+  header_->set_total_key_length(header_->total_key_length() - length);
+  header_->set_num_keys(header_->num_keys() - 1);
+  return true;
+}
+
 DoubleArrayImpl::DoubleArrayImpl()
   : pool_(),
     block_info_(nullptr),
@@ -255,15 +300,13 @@ bool DoubleArrayImpl::search_leaf(const uint8_t *ptr, uint64_t length,
     return false;
   }
   node_id = node.offset() ^ DOUBLE_ARRAY_TERMINAL_LABEL;
-  return true;
+  return nodes_[node_id].is_leaf();
 }
 
 bool DoubleArrayImpl::insert_leaf(const uint8_t *ptr, uint64_t length,
                                   uint64_t &node_id, uint64_t query_pos) {
   const DoubleArrayNode node = nodes_[node_id];
-  if (node.label() == DOUBLE_ARRAY_TERMINAL_LABEL) {
-    return false;
-  } else if (node.is_leaf()) {
+  if (node.is_leaf()) {
     const DoubleArrayKey &key = get_key(node.key_pos());
     uint64_t i = query_pos;
     while ((i < length) && (i < node.key_length())) {
@@ -284,6 +327,8 @@ bool DoubleArrayImpl::insert_leaf(const uint8_t *ptr, uint64_t length,
     }
     node_id = separate(ptr, length, node_id, i);
     return true;
+  } else if (node.label() == DOUBLE_ARRAY_TERMINAL_LABEL) {
+    return true;
   } else {
     // TODO
 //    GRN_DAT_THROW_IF(SIZE_ERROR, num_keys() >= max_num_keys());

  Modified: lib/alpha/double_array.hpp (+10 -1)
===================================================================
--- lib/alpha/double_array.hpp    2013-01-30 16:14:57 +0900 (1847316)
+++ lib/alpha/double_array.hpp    2013-01-31 11:35:35 +0900 (fc64f17)
@@ -537,7 +537,7 @@ class DoubleArrayEntry {
   uint64_t qword_;
 
   // 11 (= 64 - (1 + 40 + 12)) bits are not used.
-  static constexpr uint64_t POS_MASK = uint64_t(1) << 40;
+  static constexpr uint64_t POS_MASK = (uint64_t(1) << 40) - 1;
   static constexpr uint64_t IS_VALID_FLAG = uint64_t(1) << 47;
 };
 
@@ -600,6 +600,9 @@ class DoubleArrayImpl {
   bool insert(const uint8_t *ptr, uint64_t length,
               uint64_t *key_pos = nullptr);
 
+  bool remove(int64_t key_id);
+  bool remove(const uint8_t *ptr, uint64_t length);
+
   const DoubleArrayKey &get_key(uint64_t key_pos) {
     return *reinterpret_cast<const DoubleArrayKey *>(&keys_[key_pos]);
   }
@@ -710,6 +713,12 @@ class DoubleArray {
       return impl_->insert(static_cast<const uint8_t *>(ptr), length, nullptr);
     }
   }
+  bool remove(int64_t key_id) {
+    return impl_->remove(key_id);
+  }
+  bool remove(const void *ptr, uint64_t length) {
+    return impl_->remove(static_cast<const uint8_t *>(ptr), length);
+  }
 
   uint32_t block_id() const {
     return impl_->block_id();
-------------- next part --------------
HTML����������������������������...
Download 



More information about the Groonga-commit mailing list
Back to archive index