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