| /** |
| * Copyright 2011-2015 Quickstep Technologies LLC. |
| * Copyright 2015-2016 Pivotal Software, Inc. |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| **/ |
| |
| #include "storage/CSBTreeIndexSubBlock.hpp" |
| |
| #include <algorithm> |
| #include <cstddef> |
| #include <cstdint> |
| #include <cstring> |
| #include <memory> |
| #include <utility> |
| #include <vector> |
| |
| #include "catalog/CatalogAttribute.hpp" |
| #include "catalog/CatalogRelationSchema.hpp" |
| #include "catalog/CatalogTypedefs.hpp" |
| #include "compression/CompressionDictionary.hpp" |
| #include "expressions/predicate/ComparisonPredicate.hpp" |
| #include "expressions/predicate/PredicateCost.hpp" |
| #include "expressions/scalar/Scalar.hpp" |
| #include "expressions/scalar/ScalarAttribute.hpp" |
| #include "storage/CompressedTupleStorageSubBlock.hpp" |
| #include "storage/StorageBlockLayout.pb.h" |
| #include "storage/StorageConstants.hpp" |
| #include "storage/StorageErrors.hpp" |
| #include "storage/SubBlockTypeRegistry.hpp" |
| #include "storage/TupleIdSequence.hpp" |
| #include "storage/TupleStorageSubBlock.hpp" |
| #include "types/Type.hpp" |
| #include "types/TypedValue.hpp" |
| #include "types/operations/comparisons/Comparison.hpp" |
| #include "types/operations/comparisons/ComparisonFactory.hpp" |
| #include "types/operations/comparisons/ComparisonID.hpp" |
| #include "types/operations/comparisons/ComparisonUtil.hpp" |
| #include "utility/BitVector.hpp" |
| #include "utility/Macros.hpp" |
| #include "utility/PtrVector.hpp" |
| #include "utility/ScopedBuffer.hpp" |
| |
| using std::memcpy; |
| using std::memmove; |
| using std::pair; |
| using std::size_t; |
| using std::sort; |
| using std::uint8_t; |
| using std::uint16_t; |
| using std::uint32_t; |
| using std::vector; |
| |
| namespace quickstep { |
| |
| QUICKSTEP_REGISTER_INDEX(CSBTreeIndexSubBlock, CSB_TREE); |
| |
| namespace csbtree_internal { |
| |
| template <typename CodeType> |
| class CompressedCodeLessComparator : public UncheckedComparator { |
| public: |
| ~CompressedCodeLessComparator() { |
| } |
| |
| bool compareTypedValues(const TypedValue &left, const TypedValue &right) const { |
| FATAL_ERROR("Can not use CompressedCodeLessComparator to compare TypedValue."); |
| } |
| |
| inline bool compareDataPtrs(const void *left, const void *right) const { |
| return compareDataPtrsInl(left, right); |
| } |
| |
| inline bool compareDataPtrsInl(const void *left, const void *right) const { |
| return *static_cast<const CodeType*>(left) < *static_cast<const CodeType*>(right); |
| } |
| |
| bool compareTypedValueWithDataPtr(const TypedValue &left, const void *right) const { |
| FATAL_ERROR("Can not use CompressedCodeLessComparator to compare TypedValue."); |
| } |
| |
| bool compareDataPtrWithTypedValue(const void *left, const TypedValue &right) const { |
| FATAL_ERROR("Can not use CompressedCodeLessComparator to compare TypedValue."); |
| } |
| }; |
| |
| |
| class EntryReference { |
| public: |
| EntryReference(TypedValue &&key, |
| const tuple_id tuple) |
| : key_(key), tuple_(tuple) { |
| } |
| |
| inline const void* getDataPtr() const { |
| return key_.getDataPtr(); |
| } |
| |
| inline tuple_id getTupleID() const { |
| return tuple_; |
| } |
| |
| private: |
| TypedValue key_; |
| tuple_id tuple_; |
| }; |
| |
| class CompressedEntryReference { |
| public: |
| CompressedEntryReference(const uint32_t key_code, const tuple_id tuple) |
| : key_code_(key_code), tuple_(tuple) { |
| } |
| |
| inline const void* getDataPtr() const { |
| return &key_code_; |
| } |
| |
| inline uint32_t getKeyCode() const { |
| return key_code_; |
| } |
| |
| inline tuple_id getTupleID() const { |
| return tuple_; |
| } |
| |
| private: |
| uint32_t key_code_; |
| tuple_id tuple_; |
| }; |
| |
| class CompositeEntryReference { |
| public: |
| CompositeEntryReference(void *composite_key_copy, const tuple_id tuple) |
| : composite_key_(composite_key_copy), |
| tuple_(tuple) { |
| } |
| |
| inline const void* getDataPtr() const { |
| return composite_key_.get(); |
| } |
| |
| inline tuple_id getTupleID() const { |
| return tuple_; |
| } |
| |
| private: |
| ScopedBuffer composite_key_; |
| tuple_id tuple_; |
| }; |
| |
| |
| class CompressedEntryReferenceComparator { |
| public: |
| inline bool operator() (const CompressedEntryReference &left, |
| const CompressedEntryReference &right) const { |
| return left.getKeyCode() < right.getKeyCode(); |
| } |
| }; |
| |
| class CompositeEntryReferenceComparator { |
| public: |
| explicit CompositeEntryReferenceComparator(const CompositeKeyLessComparator &comparator) |
| : internal_comparator_(comparator) { |
| } |
| |
| inline bool operator() (const CompositeEntryReference &left, |
| const CompositeEntryReference &right) const { |
| return internal_comparator_.compareDataPtrsInl(left.getDataPtr(), right.getDataPtr()); |
| } |
| |
| private: |
| const CompositeKeyLessComparator &internal_comparator_; |
| }; |
| |
| |
| CompositeKeyLessComparator::CompositeKeyLessComparator( |
| const CSBTreeIndexSubBlock &owner, |
| const CatalogRelationSchema &relation) |
| : owner_(owner) { |
| attribute_comparators_.reserve(owner_.indexed_attribute_ids_.size()); |
| for (vector<attribute_id>::const_iterator it = owner_.indexed_attribute_ids_.begin(); |
| it != owner_.indexed_attribute_ids_.end(); |
| ++it) { |
| const Type &attribute_type = relation.getAttributeById(*it)->getType(); |
| DEBUG_ASSERT(!attribute_type.isVariableLength()); |
| attribute_comparators_.push_back( |
| ComparisonFactory::GetComparison(ComparisonID::kLess).makeUncheckedComparatorForTypes( |
| attribute_type, |
| attribute_type)); |
| } |
| } |
| |
| bool CompositeKeyLessComparator::compareDataPtrsInl(const void *left, const void *right) const { |
| DEBUG_ASSERT(attribute_comparators_.size() == owner_.indexed_attribute_offsets_.size()); |
| vector<size_t>::const_iterator offset_it = owner_.indexed_attribute_offsets_.begin(); |
| for (PtrVector<UncheckedComparator>::const_iterator comparator_it = attribute_comparators_.begin(); |
| comparator_it != attribute_comparators_.end(); |
| ++comparator_it, ++offset_it) { |
| if (comparator_it->compareDataPtrs(static_cast<const char*>(left) + *offset_it, |
| static_cast<const char*>(right) + *offset_it)) { |
| return true; |
| } else if (comparator_it->compareDataPtrs(static_cast<const char*>(right) + *offset_it, |
| static_cast<const char*>(left) + *offset_it)) { |
| return false; |
| } |
| // Attributes are equal, so loop procedes to compare next attribute in |
| // composite key. |
| } |
| |
| return false; // Keys are exactly equal. |
| } |
| |
| } // namespace csbtree_internal |
| |
| const int CSBTreeIndexSubBlock::kNodeGroupNone = -1; |
| const int CSBTreeIndexSubBlock::kNodeGroupNextLeaf = -2; |
| const int CSBTreeIndexSubBlock::kNodeGroupFull = -3; |
| |
| CSBTreeIndexSubBlock::CSBTreeIndexSubBlock(const TupleStorageSubBlock &tuple_store, |
| const IndexSubBlockDescription &description, |
| const bool new_block, |
| void *sub_block_memory, |
| const std::size_t sub_block_memory_size) |
| : IndexSubBlock(tuple_store, |
| description, |
| new_block, |
| sub_block_memory, |
| sub_block_memory_size), |
| initialized_(false), |
| key_may_be_compressed_(false), |
| key_is_compressed_(false), |
| key_is_nullable_(false), |
| key_type_(nullptr), |
| next_free_node_group_(kNodeGroupNone), |
| num_free_node_groups_(0) { |
| if (!DescriptionIsValid(relation_, description_)) { |
| FATAL_ERROR("Attempted to construct a CSBTreeIndexSubBlock from an invalid description."); |
| } |
| |
| const int num_indexed_attributes = description_.indexed_attribute_ids_size(); |
| if (num_indexed_attributes > 1) { |
| key_is_composite_ = true; |
| } else { |
| key_is_composite_ = false; |
| const attribute_id key_id = description_.indexed_attribute_ids(0); |
| key_type_ = &(relation_.getAttributeById(key_id)->getType()); |
| } |
| |
| indexed_attribute_ids_.reserve(num_indexed_attributes); |
| indexed_attribute_offsets_.reserve(num_indexed_attributes); |
| |
| for (int indexed_attribute_num = 0; |
| indexed_attribute_num < num_indexed_attributes; |
| ++indexed_attribute_num) { |
| const attribute_id indexed_attribute_id = description_.indexed_attribute_ids(indexed_attribute_num); |
| indexed_attribute_ids_.push_back(indexed_attribute_id); |
| |
| // TODO(chasseur): Support a composite key with compressed parts. |
| if ((!key_is_composite_) && tuple_store_.isCompressed()) { |
| const CompressedTupleStorageSubBlock &compressed_tuple_store |
| = static_cast<const CompressedTupleStorageSubBlock&>(tuple_store_); |
| if (compressed_tuple_store.compressedBlockIsBuilt()) { |
| if (compressed_tuple_store.compressedAttributeIsDictionaryCompressed(indexed_attribute_id) |
| || compressed_tuple_store.compressedAttributeIsTruncationCompressed(indexed_attribute_id)) { |
| key_may_be_compressed_ = true; |
| } |
| } else { |
| if (compressed_tuple_store.compressedUnbuiltBlockAttributeMayBeCompressed(indexed_attribute_id)) { |
| key_may_be_compressed_ = true; |
| } |
| } |
| } |
| } |
| |
| bool initialize_now = true; |
| if (key_may_be_compressed_) { |
| if (!static_cast<const CompressedTupleStorageSubBlock&>(tuple_store_).compressedBlockIsBuilt()) { |
| initialize_now = false; |
| } |
| } |
| |
| if (initialize_now) { |
| if (new_block) { |
| initialize(new_block); |
| } else { |
| if (!initialize(new_block)) { |
| throw MalformedBlock(); |
| } |
| } |
| } |
| } |
| |
| bool CSBTreeIndexSubBlock::DescriptionIsValid(const CatalogRelationSchema &relation, |
| const IndexSubBlockDescription &description) { |
| // Make sure description is initialized and specifies CSBTree. |
| if (!description.IsInitialized()) { |
| return false; |
| } |
| if (description.sub_block_type() != IndexSubBlockDescription::CSB_TREE) { |
| return false; |
| } |
| |
| // Make sure at least one key attribute is specified. |
| if (description.indexed_attribute_ids_size() == 0) { |
| return false; |
| } |
| |
| // TODO(chasseur): Consider checking key-length here. |
| // Check that all key attributes exist and are fixed-length. |
| for (int indexed_attribute_num = 0; |
| indexed_attribute_num < description.indexed_attribute_ids_size(); |
| ++indexed_attribute_num) { |
| const attribute_id indexed_attribute_id = description.indexed_attribute_ids(indexed_attribute_num); |
| if (!relation.hasAttributeWithId(indexed_attribute_id)) { |
| return false; |
| } |
| const Type &attr_type = relation.getAttributeById(indexed_attribute_id)->getType(); |
| if (attr_type.isVariableLength()) { |
| return false; |
| } |
| } |
| |
| return true; |
| } |
| |
| // TODO(chasseur): Make this more accurate by actually considering the internal |
| // structure of a CSBTreeIndexSubBlock. Also consider how to get better |
| // estimates when compression might be used. |
| std::size_t CSBTreeIndexSubBlock::EstimateBytesPerTuple( |
| const CatalogRelationSchema &relation, |
| const IndexSubBlockDescription &description) { |
| DEBUG_ASSERT(DescriptionIsValid(relation, description)); |
| |
| size_t key_length = 0; |
| for (int indexed_attribute_num = 0; |
| indexed_attribute_num < description.indexed_attribute_ids_size(); |
| ++indexed_attribute_num) { |
| key_length += |
| relation.getAttributeById(description.indexed_attribute_ids(indexed_attribute_num)) |
| ->getType().maximumByteLength(); |
| } |
| |
| return (5 * key_length) >> 1; |
| } |
| |
| bool CSBTreeIndexSubBlock::addEntry(const tuple_id tuple) { |
| DEBUG_ASSERT(initialized_); |
| DEBUG_ASSERT(tuple_store_.hasTupleWithID(tuple)); |
| |
| InsertReturnValue retval; |
| |
| if (key_is_composite_) { |
| ScopedBuffer composite_key_buffer(makeKeyCopy(tuple)); |
| if (key_is_nullable_) { |
| if (composite_key_buffer.empty()) { |
| // Don't insert a NULL key. |
| return true; |
| } |
| } else { |
| DEBUG_ASSERT(!composite_key_buffer.empty()); |
| } |
| |
| retval = rootInsertHelper(tuple, |
| composite_key_buffer.get(), |
| *composite_key_comparator_); |
| } else if (key_is_compressed_) { |
| // Don't insert a NULL key. |
| if (key_is_nullable_) { |
| TypedValue typed_key(tuple_store_.getAttributeValueTyped(tuple, |
| indexed_attribute_ids_.front())); |
| if (typed_key.isNull()) { |
| return true; |
| } |
| } |
| |
| const CompressedTupleStorageSubBlock &compressed_tuple_store |
| = static_cast<const CompressedTupleStorageSubBlock&>(tuple_store_); |
| uint32_t code = compressed_tuple_store.compressedGetCode(tuple, |
| indexed_attribute_ids_.front()); |
| switch (compressed_tuple_store.compressedGetCompressedAttributeSize(indexed_attribute_ids_.front())) { |
| case 1: |
| retval = compressedKeyAddEntryHelper<uint8_t>(tuple, code); |
| break; |
| case 2: |
| retval = compressedKeyAddEntryHelper<uint16_t>(tuple, code); |
| break; |
| case 4: |
| retval = compressedKeyAddEntryHelper<uint32_t>(tuple, code); |
| break; |
| default: |
| FATAL_ERROR("Unexpected compressed key byte-length (not 1, 2, or 4) encountered " |
| "in CSBTreeIndexSubBlock::addEntry()"); |
| } |
| } else { |
| TypedValue typed_key(tuple_store_.getAttributeValueTyped(tuple, indexed_attribute_ids_.front())); |
| if (key_is_nullable_) { |
| if (typed_key.isNull()) { |
| // Don't insert a NULL key. |
| return true; |
| } |
| } else { |
| DEBUG_ASSERT(!typed_key.isNull()); |
| } |
| |
| InvokeOnLessComparatorForTypeIgnoreNullability( |
| *key_type_, |
| [&](const auto &comp) { // NOLINT(build/c++11) |
| retval = this->rootInsertHelper(tuple, typed_key.getDataPtr(), comp); |
| }); |
| } |
| |
| if (retval.new_node_group_id == kNodeGroupFull) { |
| // Needed to split a node group, but not enough space. |
| return false; |
| } |
| |
| DEBUG_ASSERT(retval.new_node_group_id == kNodeGroupNone); |
| if (retval.split_node_least_key != NULL) { |
| // The root was split, must create a new root. |
| // Allocate the new root. |
| int new_root_group_id = allocateNodeGroup(); |
| DEBUG_ASSERT(new_root_group_id >= 0); |
| void *new_root = getNode(new_root_group_id, 0); |
| |
| // Set up the new root's header. |
| static_cast<NodeHeader*>(new_root)->num_keys = 1; |
| static_cast<NodeHeader*>(new_root)->is_leaf = false; |
| static_cast<NodeHeader*>(new_root)->node_group_reference = getRootNodeGroupNumber(); |
| |
| // Insert the split key into the new root. |
| memcpy(static_cast<char*>(new_root) + sizeof(NodeHeader), |
| retval.split_node_least_key, |
| key_length_bytes_); |
| |
| // Update the root node group number. |
| setRootNodeGroupNumber(new_root_group_id); |
| } |
| |
| return true; |
| } |
| |
| bool CSBTreeIndexSubBlock::bulkAddEntries(const TupleIdSequence &tuples) { |
| DEBUG_ASSERT(initialized_); |
| // TODO(chasseur): Can possibly be more efficient in some cases if we sort |
| // and insert groups where possible. |
| for (TupleIdSequence::const_iterator it = tuples.begin(); |
| it != tuples.end(); |
| ++it) { |
| if (!addEntry(*it)) { |
| // Ran out of space. Roll back. |
| for (TupleIdSequence::const_iterator fixer_it = tuples.begin(); |
| fixer_it != it; |
| ++fixer_it) { |
| removeEntry(*fixer_it); |
| } |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| void CSBTreeIndexSubBlock::removeEntry(const tuple_id tuple) { |
| DEBUG_ASSERT(initialized_); |
| if (key_is_composite_) { |
| ScopedBuffer composite_key_buffer(makeKeyCopy(tuple)); |
| if (key_is_nullable_) { |
| if (composite_key_buffer.empty()) { |
| // Don't remove a NULL key (it would not have been inserted in the |
| // first place). |
| return; |
| } |
| } else { |
| DEBUG_ASSERT(!composite_key_buffer.empty()); |
| } |
| |
| removeEntryFromLeaf(tuple, |
| composite_key_buffer.get(), |
| *composite_key_comparator_, |
| findLeaf(getRootNode(), |
| composite_key_buffer.get(), |
| *composite_key_comparator_, |
| *composite_key_comparator_)); |
| } else if (key_is_compressed_) { |
| // Don't remove a NULL key (it would not have been inserted in the first |
| // place). |
| if (key_is_nullable_) { |
| TypedValue typed_key(tuple_store_.getAttributeValueTyped(tuple, |
| indexed_attribute_ids_.front())); |
| if (typed_key.isNull()) { |
| return; |
| } |
| } |
| |
| const CompressedTupleStorageSubBlock &compressed_tuple_store |
| = static_cast<const CompressedTupleStorageSubBlock&>(tuple_store_); |
| uint32_t code = compressed_tuple_store.compressedGetCode(tuple, |
| indexed_attribute_ids_.front()); |
| switch (compressed_tuple_store.compressedGetCompressedAttributeSize(indexed_attribute_ids_.front())) { |
| case 1: |
| compressedKeyRemoveEntryHelper<uint8_t>(tuple, code); |
| break; |
| case 2: |
| compressedKeyRemoveEntryHelper<uint16_t>(tuple, code); |
| break; |
| case 4: |
| compressedKeyRemoveEntryHelper<uint32_t>(tuple, code); |
| break; |
| default: |
| FATAL_ERROR("Unexpected compressed key byte-length (not 1, 2, or 4) encountered " |
| "in CSBTreeIndexSubBlock::removeEntry()"); |
| } |
| } else { |
| TypedValue typed_key(tuple_store_.getAttributeValueTyped(tuple, indexed_attribute_ids_.front())); |
| if (key_is_nullable_) { |
| if (typed_key.isNull()) { |
| // Don't remove a NULL key (it would not have been inserted in the |
| // first place). |
| return; |
| } |
| } else { |
| DEBUG_ASSERT(!typed_key.isNull()); |
| } |
| |
| InvokeOnLessComparatorForTypeIgnoreNullability( |
| *key_type_, |
| [&](const auto &comp) { // NOLINT(build/c++11) |
| this->removeEntryFromLeaf(tuple, |
| typed_key.getDataPtr(), |
| comp, |
| this->findLeaf(this->getRootNode(), |
| typed_key.getDataPtr(), |
| comp, |
| comp)); |
| }); |
| } |
| } |
| |
| void CSBTreeIndexSubBlock::bulkRemoveEntries(const TupleIdSequence &tuples) { |
| DEBUG_ASSERT(initialized_); |
| // TODO(chasseur): Can possibly be more efficient in some cases if we sort |
| // and scan through leaves. |
| for (TupleIdSequence::const_iterator it = tuples.begin(); |
| it != tuples.end(); |
| ++it) { |
| removeEntry(*it); |
| } |
| } |
| |
| predicate_cost_t CSBTreeIndexSubBlock::estimatePredicateEvaluationCost( |
| const ComparisonPredicate &predicate) const { |
| if ((!key_is_composite_) && predicate.isAttributeLiteralComparisonPredicate()) { |
| std::pair<bool, attribute_id> comparison_attr = predicate.getAttributeFromAttributeLiteralComparison(); |
| if (comparison_attr.second == indexed_attribute_ids_.front()) { |
| return predicate_cost::kTreeSearch; |
| } |
| } |
| return predicate_cost::kInfinite; |
| } |
| |
| TupleIdSequence* CSBTreeIndexSubBlock::getMatchesForPredicate(const ComparisonPredicate &predicate, |
| const TupleIdSequence *filter) const { |
| DEBUG_ASSERT(initialized_); |
| if (key_is_composite_) { |
| // TODO(chasseur): Evaluate predicates on composite keys. |
| FATAL_ERROR("CSBTreeIndexSubBlock::getMatchesForPredicate() is unimplemented for composite keys."); |
| } |
| |
| if (!predicate.isAttributeLiteralComparisonPredicate()) { |
| FATAL_ERROR("CSBTreeIndexSubBlock::getMatchesForPredicate() can not " |
| "evaluate predicates other than simple comparisons."); |
| } |
| |
| const CatalogAttribute *comparison_attribute = NULL; |
| bool left_literal = false; |
| if (predicate.getLeftOperand().hasStaticValue()) { |
| DEBUG_ASSERT(predicate.getRightOperand().getDataSource() == Scalar::kAttribute); |
| comparison_attribute |
| = &(static_cast<const ScalarAttribute&>(predicate.getRightOperand()).getAttribute()); |
| left_literal = true; |
| } else { |
| DEBUG_ASSERT(predicate.getLeftOperand().getDataSource() == Scalar::kAttribute); |
| comparison_attribute |
| = &(static_cast<const ScalarAttribute&>(predicate.getLeftOperand()).getAttribute()); |
| left_literal = false; |
| } |
| |
| if (comparison_attribute->getID() != indexed_attribute_ids_.front()) { |
| FATAL_ERROR("CSBTreeIndexSubBlock::getMatchesForPredicate() can not " |
| "evaluate predicates on non-indexed attributes."); |
| } |
| |
| TypedValue comparison_literal; |
| const Type* comparison_literal_type; |
| if (left_literal) { |
| comparison_literal = predicate.getLeftOperand().getStaticValue().makeReferenceToThis(); |
| comparison_literal_type = &(predicate.getLeftOperand().getType()); |
| } else { |
| comparison_literal = predicate.getRightOperand().getStaticValue().makeReferenceToThis(); |
| comparison_literal_type = &(predicate.getRightOperand().getType()); |
| } |
| |
| if (comparison_literal.isNull()) { |
| return new TupleIdSequence(tuple_store_.getMaxTupleID() + 1); |
| } |
| |
| // If the literal is on the left, flip the comparison around. |
| ComparisonID comp = predicate.getComparison().getComparisonID(); |
| if (left_literal) { |
| flipComparisonID(comp); |
| } |
| |
| TupleIdSequence *idx_result; |
| if (key_is_compressed_) { |
| idx_result = evaluateComparisonPredicateOnCompressedKey( |
| comp, |
| comparison_literal, |
| *comparison_literal_type); |
| } else { |
| idx_result = evaluateComparisonPredicateOnUncompressedKey( |
| comp, |
| comparison_literal, |
| *comparison_literal_type); |
| } |
| if (filter != nullptr) { |
| idx_result->intersectWith(*filter); |
| } |
| return idx_result; |
| } |
| |
| bool CSBTreeIndexSubBlock::rebuild() { |
| if (!initialized_) { |
| if (!initialize(false)) { |
| return false; |
| } |
| } |
| |
| clearIndex(); |
| if (tuple_store_.isEmpty()) { |
| return true; |
| } |
| if (!rebuildSpaceCheck()) { |
| return false; |
| } |
| |
| vector<int> node_groups_this_level; |
| // Rebuild leaves. |
| uint16_t nodes_in_last_group = rebuildLeaves(&node_groups_this_level); |
| // Keep building intermediate levels from the bottom up until there is a |
| // single root node. |
| while (!((node_groups_this_level.size() == 1) && (nodes_in_last_group == 1))) { |
| vector<int> node_groups_next_level; |
| nodes_in_last_group = rebuildInternalLevel(node_groups_this_level, |
| nodes_in_last_group, |
| &node_groups_next_level); |
| node_groups_this_level.swap(node_groups_next_level); |
| } |
| |
| // Set the root number. |
| setRootNodeGroupNumber(node_groups_this_level.front()); |
| return true; |
| } |
| |
| bool CSBTreeIndexSubBlock::initialize(const bool new_block) { |
| if (key_may_be_compressed_) { |
| const CompressedTupleStorageSubBlock &compressed_tuple_store |
| = static_cast<const CompressedTupleStorageSubBlock&>(tuple_store_); |
| if (!compressed_tuple_store.compressedBlockIsBuilt()) { |
| FATAL_ERROR("CSBTreeIndexSubBlock::initialize() called with a key which " |
| "may be compressed before the associated TupleStorageSubBlock " |
| "was built."); |
| } |
| |
| if (compressed_tuple_store.compressedAttributeIsDictionaryCompressed(indexed_attribute_ids_.front()) |
| || compressed_tuple_store.compressedAttributeIsTruncationCompressed(indexed_attribute_ids_.front())) { |
| key_is_compressed_ = true; |
| } |
| } |
| |
| // Compute the number of bytes needed to store a key, and fill in the vector |
| // of indexed attribute offsets. |
| key_length_bytes_ = 0; |
| for (vector<attribute_id>::const_iterator indexed_attr_it = indexed_attribute_ids_.begin(); |
| indexed_attr_it != indexed_attribute_ids_.end(); |
| ++indexed_attr_it) { |
| indexed_attribute_offsets_.push_back(key_length_bytes_); |
| |
| const Type &attr_type = relation_.getAttributeById(*indexed_attr_it)->getType(); |
| if (attr_type.isNullable()) { |
| key_is_nullable_ = true; |
| } |
| if (key_is_compressed_) { |
| key_length_bytes_ += static_cast<const CompressedTupleStorageSubBlock&>(tuple_store_) |
| .compressedGetCompressedAttributeSize(*indexed_attr_it); |
| } else { |
| key_length_bytes_ += attr_type.maximumByteLength(); |
| } |
| } |
| DEBUG_ASSERT(key_length_bytes_ > 0); |
| key_tuple_id_pair_length_bytes_ = key_length_bytes_ + sizeof(tuple_id); |
| |
| // Compute the number of keys that can be stored in internal and leaf nodes. |
| // Internal nodes are just a header and a list of keys. |
| max_keys_internal_ = (kCSBTreeNodeSizeBytes - sizeof(NodeHeader)) / key_length_bytes_; |
| // Leaf nodes are a header, plus a list of (key, tuple_id) pairs. |
| max_keys_leaf_ = (kCSBTreeNodeSizeBytes - sizeof(NodeHeader)) / key_tuple_id_pair_length_bytes_; |
| if ((max_keys_internal_ < 2) || (max_keys_leaf_ < 2)) { |
| if (new_block) { |
| throw CSBTreeKeyTooLarge(); |
| } else { |
| return false; |
| } |
| } |
| // The number of child nodes allocated to each half of a split internal node. |
| small_half_num_children_ = (max_keys_internal_ + 1) >> 1; |
| large_half_num_children_ = small_half_num_children_ + ((max_keys_internal_ + 1) & 0x1); |
| |
| small_half_num_keys_leaf_ = max_keys_leaf_ >> 1; |
| large_half_num_keys_leaf_ = (max_keys_leaf_ >> 1) + (max_keys_leaf_ & 0x1); |
| |
| // Create the less-than comparator for a composite key. |
| if (key_is_composite_) { |
| composite_key_comparator_.reset(new csbtree_internal::CompositeKeyLessComparator(*this, relation_)); |
| } |
| |
| node_group_size_bytes_ = kCSBTreeNodeSizeBytes * (max_keys_internal_ + 1); |
| |
| // Perform this computation on the order of bits. |
| size_t num_node_groups = ((sub_block_memory_size_ - sizeof(int)) << 3) |
| / ((node_group_size_bytes_ << 3) + 1); |
| |
| // Compute the number of bytes needed for this SubBlock's header. The header |
| // consists of the root node's node group number and a bitmap of free/used |
| // node groups. |
| size_t header_size_bytes = sizeof(int) + BitVector<false>::BytesNeeded(num_node_groups); |
| |
| // Node groups start after the header, and should be aligned to |
| // kCSBTreeNodeSizeBytes (i.e. cache lines). In some circumstances, the |
| // alignment requirement forces us to use one less node group than would |
| // otherwise be possible. |
| node_groups_start_ = static_cast<char*>(sub_block_memory_) + header_size_bytes; |
| if (reinterpret_cast<size_t>(node_groups_start_) & (kCSBTreeNodeSizeBytes - 1)) { |
| node_groups_start_ = static_cast<char*>(node_groups_start_) |
| + kCSBTreeNodeSizeBytes |
| - (reinterpret_cast<size_t>(node_groups_start_) & (kCSBTreeNodeSizeBytes - 1)); |
| } |
| |
| // Adjust num_node_groups as necessary for aligned nodes. |
| num_node_groups = (static_cast<char*>(sub_block_memory_) + sub_block_memory_size_ |
| - static_cast<char*>(node_groups_start_)) / node_group_size_bytes_; |
| if (num_node_groups == 0) { |
| throw BlockMemoryTooSmall("CSBTreeIndex", sub_block_memory_size_); |
| } |
| |
| // Set up the free/used node group bitmap and the free list. |
| node_group_used_bitmap_.reset(new BitVector<false>(static_cast<char*>(sub_block_memory_) + sizeof(int), |
| num_node_groups)); |
| initialized_ = true; |
| |
| if (new_block) { |
| clearIndex(); |
| } else { |
| num_free_node_groups_ = num_node_groups - node_group_used_bitmap_->onesCount(); |
| if (num_free_node_groups_ > 0) { |
| next_free_node_group_ = node_group_used_bitmap_->firstZero(); |
| DEBUG_ASSERT(static_cast<size_t>(next_free_node_group_) < node_group_used_bitmap_->size()); |
| } |
| } |
| |
| return true; |
| } |
| |
| void CSBTreeIndexSubBlock::clearIndex() { |
| // Reset the free node group bitmap. |
| DEBUG_ASSERT(node_group_used_bitmap_->size() > 0); |
| node_group_used_bitmap_->clear(); |
| next_free_node_group_ = 0; |
| num_free_node_groups_ = node_group_used_bitmap_->size(); |
| |
| // Allocate the root node. |
| setRootNodeGroupNumber(allocateNodeGroup()); |
| DEBUG_ASSERT(getRootNodeGroupNumber() >= 0); |
| |
| // Initialize the root node as an empty leaf node. |
| NodeHeader *root_header = static_cast<NodeHeader*>(getRootNode()); |
| root_header->num_keys = 0; |
| root_header->is_leaf = true; |
| root_header->node_group_reference = kNodeGroupNone; |
| } |
| |
| void* CSBTreeIndexSubBlock::makeKeyCopy(const tuple_id tuple) const { |
| DEBUG_ASSERT(tuple_store_.hasTupleWithID(tuple)); |
| DEBUG_ASSERT(indexed_attribute_ids_.size() == indexed_attribute_offsets_.size()); |
| |
| ScopedBuffer key_copy(key_length_bytes_); |
| |
| vector<attribute_id>::const_iterator attr_it = indexed_attribute_ids_.begin(); |
| for (vector<size_t>::const_iterator offset_it = indexed_attribute_offsets_.begin(); |
| offset_it != indexed_attribute_offsets_.end(); |
| ++attr_it, ++offset_it) { |
| TypedValue attr_value(tuple_store_.getAttributeValueTyped(tuple, *attr_it)); |
| if (attr_value.isNull()) { |
| return NULL; |
| } |
| attr_value.copyInto(static_cast<char*>(key_copy.get()) + *offset_it); |
| } |
| |
| return key_copy.release(); |
| } |
| |
| const void* CSBTreeIndexSubBlock::getLeastKey(const void *node) const { |
| if (static_cast<const NodeHeader*>(node)->is_leaf) { |
| if (static_cast<const NodeHeader*>(node)->num_keys) { |
| return static_cast<const char*>(node) + sizeof(NodeHeader); |
| } else { |
| return NULL; |
| } |
| } else { |
| DEBUG_ASSERT(static_cast<const NodeHeader*>(node)->num_keys); |
| const void *least_key = getLeastKey(getNode(static_cast<const NodeHeader*>(node)->node_group_reference, 0)); |
| if (least_key == NULL) { |
| // If the leftmost child leaf was empty, can just use the first key here. |
| return static_cast<const char*>(node) + sizeof(NodeHeader); |
| } |
| return least_key; |
| } |
| } |
| |
| template <typename LiteralLessKeyComparatorT, |
| typename KeyLessLiteralComparatorT> |
| void* CSBTreeIndexSubBlock::findLeaf( |
| const void *node, |
| const void *literal, |
| const LiteralLessKeyComparatorT &literal_less_key_comparator, |
| const KeyLessLiteralComparatorT &key_less_literal_comparator) const { |
| const NodeHeader *node_header = static_cast<const NodeHeader*>(node); |
| if (node_header->is_leaf) { |
| return const_cast<void*>(node); |
| } |
| for (uint16_t key_num = 0; |
| key_num < node_header->num_keys; |
| ++key_num) { |
| if (literal_less_key_comparator.compareDataPtrsInl(literal, |
| static_cast<const char*>(node) |
| + sizeof(NodeHeader) |
| + key_num * key_length_bytes_)) { |
| return findLeaf(getNode(node_header->node_group_reference, key_num), |
| literal, |
| literal_less_key_comparator, |
| key_less_literal_comparator); |
| } else if (!key_less_literal_comparator.compareDataPtrsInl(static_cast<const char*>(node) |
| + sizeof(NodeHeader) |
| + key_num * key_length_bytes_, |
| literal)) { |
| // Handle the special case where duplicate keys are spread across |
| // multiple nodes. |
| |
| // TODO(chasseur): If duplicate keys are not allowed, this branch is |
| // not necessary, and searches can be done more efficiently. |
| return findLeaf(getNode(node_header->node_group_reference, key_num), |
| literal, |
| literal_less_key_comparator, |
| key_less_literal_comparator); |
| } |
| } |
| return findLeaf(getNode(node_header->node_group_reference, node_header->num_keys), |
| literal, |
| literal_less_key_comparator, |
| key_less_literal_comparator); |
| } |
| |
| void* CSBTreeIndexSubBlock::getLeftmostLeaf() const { |
| void* node = getRootNode(); |
| while (!static_cast<const NodeHeader*>(node)->is_leaf) { |
| node = getNode(static_cast<const NodeHeader*>(node)->node_group_reference, 0); |
| } |
| return node; |
| } |
| |
| template <typename CodeType> |
| CSBTreeIndexSubBlock::InsertReturnValue CSBTreeIndexSubBlock::compressedKeyAddEntryHelper( |
| const tuple_id tuple, |
| const std::uint32_t compressed_code) { |
| CodeType actual_code = compressed_code; |
| return rootInsertHelper(tuple, |
| &actual_code, |
| csbtree_internal::CompressedCodeLessComparator<CodeType>()); |
| } |
| |
| template <typename ComparatorT> |
| CSBTreeIndexSubBlock::InsertReturnValue CSBTreeIndexSubBlock::internalInsertHelper( |
| const int node_group_allocation_requirement, |
| const tuple_id tuple, |
| const void *key, |
| const ComparatorT &key_comparator, |
| const NodeHeader *parent_node_header, |
| void *node) { |
| DEBUG_ASSERT((node_group_allocation_requirement == 0) || (parent_node_header != NULL)); |
| |
| NodeHeader *node_header = static_cast<NodeHeader*>(node); |
| DEBUG_ASSERT(!node_header->is_leaf); |
| |
| // Find the child to insert into. |
| uint16_t key_num; |
| for (key_num = 0; |
| key_num < node_header->num_keys; |
| ++key_num) { |
| if (key_comparator.compareDataPtrsInl(key, |
| static_cast<char*>(node) |
| + sizeof(NodeHeader) |
| + key_num * key_length_bytes_)) { |
| break; |
| } |
| } |
| |
| // Insert into the appropriate child. |
| void *child_node = getNode(node_header->node_group_reference, key_num); |
| int child_node_group_allocation_requirement = 0; |
| if (node_header->num_keys == max_keys_internal_) { |
| // If the child node is split, this node must also be split. |
| if (getRootNode() == node) { |
| // If this node is the root, make sure there is additional space for a |
| // new root. |
| DEBUG_ASSERT(node_group_allocation_requirement == 0); |
| child_node_group_allocation_requirement = 2; |
| } else { |
| child_node_group_allocation_requirement = node_group_allocation_requirement + 1; |
| } |
| } else { |
| // This node can accomodate an additional key without splitting. |
| child_node_group_allocation_requirement = 0; |
| } |
| InsertReturnValue child_return_value; |
| if (static_cast<NodeHeader*>(child_node)->is_leaf) { |
| child_return_value = leafInsertHelper(child_node_group_allocation_requirement, |
| tuple, |
| key, |
| key_comparator, |
| node_header, |
| child_node); |
| } else { |
| child_return_value = internalInsertHelper(child_node_group_allocation_requirement, |
| tuple, |
| key, |
| key_comparator, |
| node_header, |
| child_node); |
| } |
| |
| if (child_return_value.new_node_group_id == kNodeGroupFull) { |
| // Insertion failed (out of space). |
| return child_return_value; |
| } |
| |
| InsertReturnValue retval; |
| bool child_split_across_groups = !child_return_value.left_split_group_smaller |
| && (key_num == small_half_num_children_); |
| if (child_return_value.new_node_group_id != kNodeGroupNone) { |
| // A new node group was allocated, and this node must be split. |
| DEBUG_ASSERT(child_return_value.split_node_least_key != NULL); |
| DEBUG_ASSERT(node_header->num_keys == max_keys_internal_); |
| |
| const void *group_end = NULL; |
| if (node_group_allocation_requirement) { |
| // Parent node is full, must allocate new node group(s). |
| // Should already by checked by the child: |
| DEBUG_ASSERT(num_free_node_groups_ >= node_group_allocation_requirement); |
| |
| // Split the node group. |
| group_end = splitNodeGroupHelper(parent_node_header, &node, &retval); |
| } else { |
| group_end = getNode(parent_node_header->node_group_reference, parent_node_header->num_keys + 1); |
| } |
| |
| if (group_end == NULL) { |
| retval.split_node_least_key = splitNodeAcrossGroups(node, |
| retval.new_node_group_id, |
| child_return_value.new_node_group_id, |
| child_return_value.left_split_group_smaller, |
| child_split_across_groups); |
| } else { |
| retval.split_node_least_key = splitNodeInGroup(node, |
| group_end, |
| child_return_value.new_node_group_id, |
| child_return_value.left_split_group_smaller, |
| child_split_across_groups); |
| } |
| |
| if (child_split_across_groups) { |
| // We're done here. |
| return retval; |
| } |
| |
| if (!child_return_value.left_split_group_smaller) { |
| DEBUG_ASSERT(key_num >= large_half_num_children_); |
| key_num -= large_half_num_children_; |
| |
| if (group_end == NULL) { |
| node = getNode(retval.new_node_group_id, 0); |
| } else { |
| node = static_cast<char*>(node) + kCSBTreeNodeSizeBytes; |
| } |
| } |
| } |
| |
| if (child_return_value.split_node_least_key != NULL) { |
| // If the child was split, insert the new key. |
| node_header = static_cast<NodeHeader*>(node); |
| void *key_location = static_cast<char*>(node) |
| + sizeof(*node_header) |
| + key_num * key_length_bytes_; |
| // Move subsequent entries right if necessary. |
| if (key_num < node_header->num_keys) { |
| memmove(static_cast<char*>(key_location) + key_length_bytes_, |
| key_location, |
| (node_header->num_keys - key_num) * key_length_bytes_); |
| } |
| // Insert the new entry. |
| memcpy(key_location, child_return_value.split_node_least_key, key_length_bytes_); |
| // Increment the key count. |
| ++(node_header->num_keys); |
| } |
| |
| return retval; |
| } |
| |
| template <typename ComparatorT> |
| CSBTreeIndexSubBlock::InsertReturnValue CSBTreeIndexSubBlock::leafInsertHelper( |
| const int node_group_allocation_requirement, |
| const tuple_id tuple, |
| const void *key, |
| const ComparatorT &key_comparator, |
| const NodeHeader *parent_node_header, |
| void *node) { |
| InsertReturnValue retval; |
| |
| NodeHeader *node_header = static_cast<NodeHeader*>(node); |
| DEBUG_ASSERT(node_header->is_leaf); |
| |
| if (node_header->num_keys == max_keys_leaf_) { |
| // '*node' is full and must be split. |
| const void *group_end = NULL; |
| if (node_group_allocation_requirement) { |
| // Parent node is full, must allocate new node group(s). |
| if (num_free_node_groups_ < node_group_allocation_requirement) { |
| // Not enough node groups to allocate, so insert must fail (although |
| // more efficient packing may be possible if index is rebuilt). |
| retval.new_node_group_id = kNodeGroupFull; |
| return retval; |
| } |
| |
| // Split the node group. |
| group_end = splitNodeGroupHelper(parent_node_header, &node, &retval); |
| DEBUG_ASSERT(static_cast<const NodeHeader*>(node)->is_leaf); |
| } else { |
| // If we are splitting the root node, make sure the caller can allocate a |
| // new root. |
| if (getRootNode() == node) { |
| if (num_free_node_groups_ == 0) { |
| retval.new_node_group_id = kNodeGroupFull; |
| return retval; |
| } |
| } |
| |
| group_end = getNode(parent_node_header->node_group_reference, parent_node_header->num_keys + 1); |
| } |
| |
| // This node group (now) has space for a new node. If node splits are |
| // asymmetric (i.e. max_keys_leaf_ is odd), do the split such that the new |
| // entry will go into the smaller split node, leaving the nodes balanced. |
| if (key_comparator.compareDataPtrsInl(key, |
| static_cast<const char*>(node) |
| + sizeof(NodeHeader) |
| + (small_half_num_keys_leaf_) * key_tuple_id_pair_length_bytes_)) { |
| // Insert in the first half. |
| if (group_end == NULL) { |
| retval.split_node_least_key = splitNodeAcrossGroups(node, |
| retval.new_node_group_id, |
| kNodeGroupNone, |
| true, |
| false); |
| } else { |
| retval.split_node_least_key = splitNodeInGroup(node, group_end, kNodeGroupNone, true, false); |
| } |
| } else { |
| // Insert in the second half. |
| // Note: The new key may be inserted at the first position in the split |
| // node. The pointer 'retval.split_node_least_key' will remain correct |
| // if this is the case, as splitNodeInGroup() returns a pointer to the |
| // first leaf key's location. |
| if (group_end == NULL) { |
| retval.split_node_least_key = splitNodeAcrossGroups(node, |
| retval.new_node_group_id, |
| kNodeGroupNone, |
| false, |
| false); |
| node = getNode(retval.new_node_group_id, 0); |
| } else { |
| retval.split_node_least_key = splitNodeInGroup(node, group_end, kNodeGroupNone, false, false); |
| node = static_cast<char*>(node) + kCSBTreeNodeSizeBytes; |
| } |
| } |
| } |
| |
| // Either splitting was not necessary, or it already occured. Insert the key. |
| insertEntryInLeaf(tuple, key, key_comparator, node); |
| return retval; |
| } |
| |
| template <typename ComparatorT> |
| CSBTreeIndexSubBlock::InsertReturnValue CSBTreeIndexSubBlock::rootInsertHelper( |
| const tuple_id tuple, |
| const void *key, |
| const ComparatorT &key_comparator) { |
| void *root_node = getRootNode(); |
| NodeHeader super_root; |
| super_root.num_keys = 0; |
| super_root.is_leaf = false; |
| super_root.node_group_reference = getRootNodeGroupNumber(); |
| |
| if (static_cast<NodeHeader*>(root_node)->is_leaf) { |
| return leafInsertHelper(0, |
| tuple, |
| key, |
| key_comparator, |
| &super_root, |
| root_node); |
| } else { |
| return internalInsertHelper(0, |
| tuple, |
| key, |
| key_comparator, |
| &super_root, |
| root_node); |
| } |
| } |
| |
| const void* CSBTreeIndexSubBlock::splitNodeGroupHelper( |
| const NodeHeader *parent_node_header, |
| void **node, |
| InsertReturnValue *caller_return_value) { |
| const void *center_node = getNode(parent_node_header->node_group_reference, small_half_num_children_); |
| if (*node < center_node) { |
| caller_return_value->left_split_group_smaller = true; |
| caller_return_value->new_node_group_id = splitNodeGroup(parent_node_header, true, false); |
| return getNode(parent_node_header->node_group_reference, small_half_num_children_); |
| } else { |
| caller_return_value->left_split_group_smaller = false; |
| if (*node == center_node) { |
| caller_return_value->new_node_group_id = splitNodeGroup(parent_node_header, false, true); |
| return NULL; |
| } else { |
| caller_return_value->new_node_group_id = splitNodeGroup(parent_node_header, false, false); |
| // TODO(chasseur): Verify that this logic is correct. |
| if (static_cast<const NodeHeader*>(*node)->node_group_reference >= 0) { |
| *node = static_cast<char*>(getNode(caller_return_value->new_node_group_id, 0)) |
| + (static_cast<const char*>(*node) - static_cast<const char*>(center_node)) |
| - kCSBTreeNodeSizeBytes; |
| } else { |
| *node = static_cast<char*>(getNode(caller_return_value->new_node_group_id, 0)) |
| + (static_cast<const char*>(*node) - static_cast<const char*>(center_node)); |
| } |
| return getNode(caller_return_value->new_node_group_id, small_half_num_children_); |
| } |
| } |
| } |
| |
| int CSBTreeIndexSubBlock::splitNodeGroup(const NodeHeader *parent_node_header, |
| const bool left_smaller, |
| const bool will_split_node_across_groups) { |
| DEBUG_ASSERT(!parent_node_header->is_leaf); |
| DEBUG_ASSERT(parent_node_header->num_keys == max_keys_internal_); |
| DEBUG_ASSERT(num_free_node_groups_ > 0); |
| if (will_split_node_across_groups) { |
| DEBUG_ASSERT(!left_smaller); |
| } |
| |
| // Allocate a new node group. |
| int new_node_group_id = allocateNodeGroup(); |
| DEBUG_ASSERT(new_node_group_id >= 0); |
| void *copy_destination; |
| if (will_split_node_across_groups) { |
| copy_destination = getNode(new_node_group_id, 1); |
| } else { |
| copy_destination = getNode(new_node_group_id, 0); |
| } |
| |
| NodeHeader *rightmost_remaining_node_header; |
| // Move half of the nodes in the current group to the new group. |
| if (left_smaller) { |
| memcpy(copy_destination, |
| getNode(parent_node_header->node_group_reference, small_half_num_children_), |
| large_half_num_children_ * kCSBTreeNodeSizeBytes); |
| rightmost_remaining_node_header |
| = static_cast<NodeHeader*>(getNode(parent_node_header->node_group_reference, |
| small_half_num_children_ - 1)); |
| } else { |
| memcpy(copy_destination, |
| getNode(parent_node_header->node_group_reference, large_half_num_children_), |
| small_half_num_children_ * kCSBTreeNodeSizeBytes); |
| rightmost_remaining_node_header |
| = static_cast<NodeHeader*>(getNode(parent_node_header->node_group_reference, |
| large_half_num_children_ - 1)); |
| } |
| |
| // If the split nodes are leaves, adjust the node_group_reference of the |
| // rightmost remaining node. |
| if (rightmost_remaining_node_header->is_leaf) { |
| rightmost_remaining_node_header->node_group_reference = new_node_group_id; |
| } |
| |
| return new_node_group_id; |
| } |
| |
| const void* CSBTreeIndexSubBlock::splitNodeInGroup(void *node, |
| const void *group_end, |
| const int right_child_node_group, |
| const bool left_smaller, |
| const bool child_was_split_across_groups) { |
| NodeHeader *node_header = static_cast<NodeHeader*>(node); |
| if (child_was_split_across_groups) { |
| DEBUG_ASSERT(!node_header->is_leaf); |
| DEBUG_ASSERT(!left_smaller); |
| } |
| if (node_header->is_leaf) { |
| DEBUG_ASSERT(right_child_node_group == kNodeGroupNone); |
| DEBUG_ASSERT(node_header->num_keys == max_keys_leaf_); |
| } else { |
| DEBUG_ASSERT(right_child_node_group >= 0); |
| DEBUG_ASSERT(node_header->num_keys == max_keys_internal_); |
| } |
| |
| void *next_node = static_cast<char*>(node) + kCSBTreeNodeSizeBytes; |
| if (group_end != next_node) { |
| // Shift subsequent nodes right. |
| memmove(static_cast<char*>(next_node) + kCSBTreeNodeSizeBytes, |
| next_node, |
| static_cast<const char*>(group_end) - static_cast<char*>(next_node)); |
| } |
| |
| // Do the split. |
| NodeHeader *next_node_header = static_cast<NodeHeader*>(next_node); |
| if (node_header->is_leaf) { |
| // Set up the next node's header. |
| if (left_smaller) { |
| next_node_header->num_keys = large_half_num_keys_leaf_; |
| } else { |
| next_node_header->num_keys = small_half_num_keys_leaf_; |
| } |
| next_node_header->is_leaf = true; |
| next_node_header->node_group_reference = node_header->node_group_reference; |
| |
| // Modify the current node's header. |
| if (left_smaller) { |
| node_header->num_keys = small_half_num_keys_leaf_; |
| } else { |
| node_header->num_keys = large_half_num_keys_leaf_; |
| } |
| node_header->node_group_reference = kNodeGroupNextLeaf; |
| |
| // Copy half the keys over. |
| memcpy(static_cast<char*>(next_node) + sizeof(NodeHeader), |
| static_cast<const char*>(node) |
| + sizeof(NodeHeader) |
| + (node_header->num_keys * key_tuple_id_pair_length_bytes_), |
| next_node_header->num_keys * key_tuple_id_pair_length_bytes_); |
| return static_cast<const char*>(next_node) + sizeof(NodeHeader); |
| } else { |
| // Set up the next node's header. |
| if (left_smaller) { |
| next_node_header->num_keys = large_half_num_children_ - 1; |
| } else { |
| if (child_was_split_across_groups) { |
| next_node_header->num_keys = small_half_num_children_; |
| } else { |
| next_node_header->num_keys = small_half_num_children_ - 1; |
| } |
| } |
| next_node_header->is_leaf = false; |
| next_node_header->node_group_reference = right_child_node_group; |
| |
| // Modify the current node's header. |
| if (left_smaller) { |
| node_header->num_keys = small_half_num_children_ - 1; |
| } else { |
| node_header->num_keys = large_half_num_children_ - 1; |
| } |
| |
| if (child_was_split_across_groups) { |
| // Copy half the entries over. |
| memcpy(static_cast<char*>(next_node) + sizeof(NodeHeader), |
| static_cast<const char*>(node) |
| + sizeof(NodeHeader) |
| + ((node_header->num_keys) * key_length_bytes_), |
| next_node_header->num_keys * key_length_bytes_); |
| } else { |
| // Copy half the keys over (shift by one for the leftmost child). |
| memcpy(static_cast<char*>(next_node) + sizeof(NodeHeader), |
| static_cast<const char*>(node) |
| + sizeof(NodeHeader) |
| + ((node_header->num_keys + 1) * key_length_bytes_), |
| next_node_header->num_keys * key_length_bytes_); |
| } |
| // Push the middle key up. |
| return getLeastKey(next_node); |
| } |
| } |
| |
| const void* CSBTreeIndexSubBlock::splitNodeAcrossGroups(void *node, |
| const int destination_group_number, |
| const int right_child_node_group, |
| const bool left_smaller, |
| const bool child_was_split_across_groups) { |
| DEBUG_ASSERT(destination_group_number >= 0); |
| DEBUG_ASSERT(static_cast<size_t>(destination_group_number) < node_group_used_bitmap_->size()); |
| DEBUG_ASSERT(node_group_used_bitmap_->getBit(destination_group_number)); |
| |
| NodeHeader *node_header = static_cast<NodeHeader*>(node); |
| if (child_was_split_across_groups) { |
| DEBUG_ASSERT(!node_header->is_leaf); |
| DEBUG_ASSERT(!left_smaller); |
| } |
| if (node_header->is_leaf) { |
| DEBUG_ASSERT(right_child_node_group == kNodeGroupNone); |
| DEBUG_ASSERT(node_header->num_keys == max_keys_leaf_); |
| DEBUG_ASSERT(node_header->node_group_reference == destination_group_number); |
| } else { |
| DEBUG_ASSERT(right_child_node_group >= 0); |
| DEBUG_ASSERT(node_header->num_keys == max_keys_internal_); |
| } |
| |
| // Do the split. |
| void *destination_node = getNode(destination_group_number, 0); |
| NodeHeader *destination_node_header = static_cast<NodeHeader*>(destination_node); |
| if (node_header->is_leaf) { |
| // Set up the destination node's header. |
| if (left_smaller) { |
| destination_node_header->num_keys = large_half_num_keys_leaf_; |
| } else { |
| destination_node_header->num_keys = small_half_num_keys_leaf_; |
| } |
| destination_node_header->is_leaf = true; |
| destination_node_header->node_group_reference = kNodeGroupNextLeaf; |
| |
| // Modify the current node's header. |
| if (left_smaller) { |
| node_header->num_keys = small_half_num_keys_leaf_; |
| } else { |
| node_header->num_keys = large_half_num_keys_leaf_; |
| } |
| |
| // Copy half the entries over. |
| memcpy(static_cast<char*>(destination_node) + sizeof(NodeHeader), |
| static_cast<const char*>(node) |
| + sizeof(NodeHeader) |
| + (node_header->num_keys * key_tuple_id_pair_length_bytes_), |
| destination_node_header->num_keys * key_tuple_id_pair_length_bytes_); |
| return static_cast<const char*>(destination_node) + sizeof(NodeHeader); |
| } else { |
| // Set up the destination node's header. |
| if (left_smaller) { |
| destination_node_header->num_keys = large_half_num_children_ - 1; |
| } else { |
| if (child_was_split_across_groups) { |
| destination_node_header->num_keys = small_half_num_children_; |
| } else { |
| destination_node_header->num_keys = small_half_num_children_ - 1; |
| } |
| } |
| destination_node_header->is_leaf = false; |
| destination_node_header->node_group_reference = right_child_node_group; |
| |
| // Modify the current node's header. |
| if (left_smaller) { |
| node_header->num_keys = small_half_num_children_ - 1; |
| } else { |
| node_header->num_keys = large_half_num_children_ - 1; |
| } |
| |
| if (child_was_split_across_groups) { |
| // Copy half the keys over. |
| memcpy(static_cast<char*>(destination_node) + sizeof(NodeHeader), |
| static_cast<const char*>(node) |
| + sizeof(NodeHeader) |
| + (node_header->num_keys * key_length_bytes_), |
| destination_node_header->num_keys * key_length_bytes_); |
| } else { |
| // Copy half the keys over (shift by one for the leftmost child). |
| memcpy(static_cast<char*>(destination_node) + sizeof(NodeHeader), |
| static_cast<const char*>(node) |
| + sizeof(NodeHeader) |
| + ((node_header->num_keys + 1) * key_length_bytes_), |
| destination_node_header->num_keys * key_length_bytes_); |
| } |
| // Push the middle key up. |
| return getLeastKey(destination_node); |
| } |
| } |
| |
| template <typename ComparatorT> |
| void CSBTreeIndexSubBlock::insertEntryInLeaf(const tuple_id tuple, |
| const void *key, |
| const ComparatorT &key_comparator, |
| void *node) { |
| DEBUG_ASSERT(static_cast<NodeHeader*>(node)->is_leaf); |
| |
| const uint16_t num_keys = static_cast<NodeHeader*>(node)->num_keys; |
| DEBUG_ASSERT(num_keys < max_keys_leaf_); |
| |
| char *current_key = static_cast<char*>(node) + sizeof(NodeHeader); |
| for (uint16_t key_num = 0; |
| key_num < num_keys; |
| ++key_num, current_key += key_tuple_id_pair_length_bytes_) { |
| if (key_comparator.compareDataPtrsInl(key, current_key)) { |
| // Shift subsequent entries right. |
| memmove(current_key + key_tuple_id_pair_length_bytes_, |
| current_key, |
| (num_keys - key_num) * key_tuple_id_pair_length_bytes_); |
| break; |
| } |
| } |
| // Insert the new entry. |
| memcpy(current_key, key, key_length_bytes_); |
| *reinterpret_cast<tuple_id*>(current_key + key_length_bytes_) = tuple; |
| // Increment the key count. |
| ++(static_cast<NodeHeader*>(node)->num_keys); |
| } |
| |
| template <typename CodeType> |
| void CSBTreeIndexSubBlock::compressedKeyRemoveEntryHelper(const tuple_id tuple, |
| const std::uint32_t compressed_code) { |
| CodeType actual_code = compressed_code; |
| csbtree_internal::CompressedCodeLessComparator<CodeType> comp; |
| |
| removeEntryFromLeaf(tuple, |
| &actual_code, |
| comp, |
| findLeaf(getRootNode(), |
| &actual_code, |
| comp, |
| comp)); |
| } |
| |
| template <typename ComparatorT> |
| void CSBTreeIndexSubBlock::removeEntryFromLeaf(const tuple_id tuple, |
| const void *key, |
| const ComparatorT &key_comparator, |
| void *node) { |
| DEBUG_ASSERT(static_cast<NodeHeader*>(node)->is_leaf); |
| |
| void *right_sibling; |
| const uint16_t num_keys = static_cast<NodeHeader*>(node)->num_keys; |
| // If node is totally empty, immediately chase the next sibling. |
| if (num_keys == 0) { |
| right_sibling = getRightSiblingOfLeafNode(node); |
| if (right_sibling != NULL) { |
| removeEntryFromLeaf(tuple, key, key_comparator, right_sibling); |
| return; |
| } else { |
| FATAL_ERROR("CSBTree: attempted to remove nonexistent entry."); |
| } |
| } |
| |
| for (uint16_t key_num = 0; |
| key_num < num_keys; |
| ++key_num) { |
| char* existing_key_ptr = static_cast<char*>(node) |
| + sizeof(NodeHeader) |
| + key_num * key_tuple_id_pair_length_bytes_; |
| if (key_comparator.compareDataPtrsInl(existing_key_ptr, key)) { |
| // Haven't yet reached the target key. |
| continue; |
| } else if (key_comparator.compareDataPtrsInl(key, existing_key_ptr)) { |
| // Past the target key, but the target has not been found. |
| FATAL_ERROR("CSBTree: attempted to remove nonexistent entry."); |
| } else { |
| // Key matches, so check tuple_id. |
| if (tuple == *reinterpret_cast<const tuple_id*>(existing_key_ptr + key_length_bytes_)) { |
| // Match found, remove the entry. |
| if (key_num != num_keys - 1) { |
| // Move subsequent entries forward. |
| memmove(existing_key_ptr, |
| existing_key_ptr + key_tuple_id_pair_length_bytes_, |
| (num_keys - key_num - 1) * key_tuple_id_pair_length_bytes_); |
| } |
| // Decrement the key count. |
| --(static_cast<NodeHeader*>(node)->num_keys); |
| return; |
| } else { |
| // Not the correct tuple_id, but there may be others with the same key. |
| continue; |
| } |
| } |
| } |
| |
| // Proceed to next sibling. |
| right_sibling = getRightSiblingOfLeafNode(node); |
| if (right_sibling != NULL) { |
| removeEntryFromLeaf(tuple, key, key_comparator, right_sibling); |
| return; |
| } else { |
| FATAL_ERROR("CSBTree: attempted to remove nonexistent entry."); |
| } |
| } |
| |
| namespace csbtree_internal { |
| |
| // NOTE(chasseur): Ordinarily we would just use a lambda instead of writing out |
| // this functor. However, there is a bug in Clang (current as of 3.7.0) that |
| // prevents instantiations of templated functions from being compiled if they |
| // only occur in a lambda capture. This causes a situation where this file |
| // compiles successfully, but linking fails with unresolved symbols. Using a |
| // more verbose manually-written functor works around the problem. |
| class PredicateEvaluationForwarder { |
| public: |
| PredicateEvaluationForwarder(const CSBTreeIndexSubBlock &csb_tree, |
| const ComparisonID comp, |
| const TypedValue &right_literal) |
| : csb_tree_(csb_tree), |
| comp_(comp), |
| right_literal_(right_literal) { |
| } |
| |
| template <typename ComparatorT> |
| TupleIdSequence* operator()(const ComparatorT &comparator) const { |
| return csb_tree_.evaluatePredicate(comp_, |
| right_literal_.getDataPtr(), |
| comparator, |
| comparator); |
| } |
| |
| template <typename LiteralLessKeyComparatorT, |
| typename KeyLessLiteralComparatorT> |
| TupleIdSequence* operator()( |
| const LiteralLessKeyComparatorT &literal_less_key_comparator, |
| const KeyLessLiteralComparatorT &key_less_literal_comparator) const { |
| return csb_tree_.evaluatePredicate(comp_, |
| right_literal_.getDataPtr(), |
| literal_less_key_comparator, |
| key_less_literal_comparator); |
| } |
| |
| private: |
| const CSBTreeIndexSubBlock &csb_tree_; |
| const ComparisonID comp_; |
| const TypedValue &right_literal_; |
| }; |
| |
| } // namespace csbtree_internal |
| |
| TupleIdSequence* CSBTreeIndexSubBlock::evaluateComparisonPredicateOnUncompressedKey( |
| const ComparisonID comp, |
| const TypedValue &right_literal, |
| const Type &right_literal_type) const { |
| DEBUG_ASSERT(!key_is_compressed_); |
| DEBUG_ASSERT(!key_is_composite_); |
| |
| csbtree_internal::PredicateEvaluationForwarder forwarder(*this, comp, right_literal); |
| |
| if (right_literal_type.isSubsumedBy(*key_type_)) { |
| return InvokeOnLessComparatorForTypeIgnoreNullability( |
| *key_type_, |
| forwarder); |
| } else { |
| return InvokeOnBothLessComparatorsForDifferentTypesIgnoreNullability( |
| right_literal_type, |
| *key_type_, |
| forwarder); |
| } |
| } |
| |
| TupleIdSequence* CSBTreeIndexSubBlock::evaluateComparisonPredicateOnCompressedKey( |
| ComparisonID comp, |
| const TypedValue &right_literal, |
| const Type &right_literal_type) const { |
| DEBUG_ASSERT(key_is_compressed_); |
| DEBUG_ASSERT(!key_is_composite_); |
| |
| // Stack variables to hold compressed codes as needed. |
| uint8_t byte_code; |
| uint16_t short_code; |
| uint32_t word_code; |
| |
| const CompressedTupleStorageSubBlock &compressed_tuple_store |
| = static_cast<const CompressedTupleStorageSubBlock&>(tuple_store_); |
| if (compressed_tuple_store.compressedAttributeIsDictionaryCompressed(indexed_attribute_ids_.front())) { |
| const CompressionDictionary &dict |
| = compressed_tuple_store.compressedGetDictionary(indexed_attribute_ids_.front()); |
| switch (comp) { |
| case ComparisonID::kEqual: |
| byte_code = short_code = word_code = dict.getCodeForTypedValue(right_literal, |
| right_literal_type); |
| if (word_code == dict.numberOfCodes()) { |
| return new TupleIdSequence(tuple_store_.getMaxTupleID() + 1); |
| } |
| break; |
| case ComparisonID::kNotEqual: |
| byte_code = short_code = word_code = dict.getCodeForTypedValue(right_literal, |
| right_literal_type); |
| if (word_code == dict.numberOfCodes()) { |
| return tuple_store_.getExistenceMap(); |
| } |
| break; |
| default: { |
| pair<uint32_t, uint32_t> limits = dict.getLimitCodesForComparisonTyped(comp, |
| right_literal, |
| right_literal_type); |
| if (limits.first == 0) { |
| if (limits.second == dict.numberOfCodes()) { |
| return tuple_store_.getExistenceMap(); |
| } else { |
| byte_code = short_code = word_code = limits.second; |
| comp = ComparisonID::kLess; |
| } |
| } else if (limits.second == dict.numberOfCodes()) { |
| byte_code = short_code = word_code = limits.first; |
| comp = ComparisonID::kGreaterOrEqual; |
| } else { |
| FATAL_ERROR("CompressionDictionary::getLimitCodesForComparisonTyped() returned " |
| "limits which did not extend to either the minimum or maximum code " |
| "when called by CSBTreeIndexSubBlock::evaluateComparisonPredicateOnCompressedKey()."); |
| } |
| break; |
| } |
| } |
| } else { |
| if (compressed_tuple_store.compressedComparisonIsAlwaysTrueForTruncatedAttribute( |
| comp, |
| indexed_attribute_ids_.front(), |
| right_literal, |
| right_literal_type)) { |
| return tuple_store_.getExistenceMap(); |
| } else if (compressed_tuple_store.compressedComparisonIsAlwaysFalseForTruncatedAttribute( |
| comp, |
| indexed_attribute_ids_.front(), |
| right_literal, |
| right_literal_type)) { |
| return new TupleIdSequence(tuple_store_.getMaxTupleID() + 1); |
| } else { |
| switch (comp) { |
| case ComparisonID::kEqual: |
| case ComparisonID::kNotEqual: |
| byte_code = short_code = word_code = right_literal.getLiteral<std::int64_t>(); |
| break; |
| // Adjustments for kLessOrEqual and kGreater make predicate evaluation |
| // a bit more efficient (particularly in the presence of repeated |
| // keys). Adding 1 will not overflow the code type, as a literal of |
| // exactly the maximum possible value for the code type would have |
| // already caused |
| // compressedComparisonIsAlwaysTrueForTruncatedAttribute() to return |
| // true for kLessOrEqual, or |
| // compressedComparisonIsAlwaysFalseForTruncatedAttribute() to return |
| // false for kGreater. |
| case ComparisonID::kLessOrEqual: |
| comp = ComparisonID::kLess; |
| byte_code = short_code = word_code |
| = 1 + CompressedTupleStorageSubBlock::GetEffectiveLiteralValueForComparisonWithTruncatedAttribute( |
| comp, |
| right_literal, |
| right_literal_type); |
| break; |
| case ComparisonID::kGreater: |
| comp = ComparisonID::kGreaterOrEqual; |
| byte_code = short_code = word_code |
| = 1 + CompressedTupleStorageSubBlock::GetEffectiveLiteralValueForComparisonWithTruncatedAttribute( |
| comp, |
| right_literal, |
| right_literal_type); |
| break; |
| default: |
| byte_code = short_code = word_code |
| = CompressedTupleStorageSubBlock::GetEffectiveLiteralValueForComparisonWithTruncatedAttribute( |
| comp, |
| right_literal, |
| right_literal_type); |
| break; |
| } |
| } |
| } |
| |
| switch (compressed_tuple_store.compressedGetCompressedAttributeSize(indexed_attribute_ids_.front())) { |
| case 1: { |
| csbtree_internal::CompressedCodeLessComparator<uint8_t> comparator; |
| return evaluatePredicate(comp, &byte_code, comparator, comparator); |
| break; |
| } |
| case 2: { |
| csbtree_internal::CompressedCodeLessComparator<uint16_t> comparator; |
| return evaluatePredicate(comp, &short_code, comparator, comparator); |
| break; |
| } |
| case 4: { |
| csbtree_internal::CompressedCodeLessComparator<uint32_t> comparator; |
| return evaluatePredicate(comp, &word_code, comparator, comparator); |
| break; |
| } |
| default: |
| FATAL_ERROR("Unexpected compressed key byte-length (not 1, 2, or 4) encountered " |
| "in CSBTreeIndexSubBlock::getMatchesForPredicate()"); |
| } |
| } |
| |
| template <typename LiteralLessKeyComparatorT, |
| typename KeyLessLiteralComparatorT> |
| TupleIdSequence* CSBTreeIndexSubBlock::evaluatePredicate( |
| ComparisonID comp, |
| const void *literal, |
| const LiteralLessKeyComparatorT &literal_less_key_comparator, |
| const KeyLessLiteralComparatorT &key_less_literal_comparator) const { |
| switch (comp) { |
| case ComparisonID::kEqual: |
| return evaluateEqualPredicate(literal, |
| literal_less_key_comparator, |
| key_less_literal_comparator); |
| case ComparisonID::kNotEqual: |
| return evaluateNotEqualPredicate(literal, |
| literal_less_key_comparator, |
| key_less_literal_comparator); |
| case ComparisonID::kLess: |
| return evaluateLessPredicate<LiteralLessKeyComparatorT, |
| KeyLessLiteralComparatorT, |
| false>(literal, |
| literal_less_key_comparator, |
| key_less_literal_comparator); |
| case ComparisonID::kLessOrEqual: |
| return evaluateLessPredicate<LiteralLessKeyComparatorT, |
| KeyLessLiteralComparatorT, |
| true>(literal, |
| literal_less_key_comparator, |
| key_less_literal_comparator); |
| case ComparisonID::kGreater: |
| return evaluateGreaterPredicate<LiteralLessKeyComparatorT, |
| KeyLessLiteralComparatorT, |
| false>(literal, |
| literal_less_key_comparator, |
| key_less_literal_comparator); |
| case ComparisonID::kGreaterOrEqual: |
| return evaluateGreaterPredicate<LiteralLessKeyComparatorT, |
| KeyLessLiteralComparatorT, |
| true>(literal, |
| literal_less_key_comparator, |
| key_less_literal_comparator); |
| default: |
| FATAL_ERROR("Unrecognized ComparisonID in CSBTreeIndexSubBlock::evaluatePredicate()"); |
| } |
| } |
| |
| template <typename LiteralLessKeyComparatorT, |
| typename KeyLessLiteralComparatorT> |
| TupleIdSequence* CSBTreeIndexSubBlock::evaluateEqualPredicate( |
| const void *literal, |
| const LiteralLessKeyComparatorT &literal_less_key_comparator, |
| const KeyLessLiteralComparatorT &key_less_literal_comparator) const { |
| std::unique_ptr<TupleIdSequence> matches(new TupleIdSequence(tuple_store_.getMaxTupleID() + 1)); |
| |
| bool match_found = false; |
| const void *search_node = findLeaf(getRootNode(), |
| literal, |
| literal_less_key_comparator, |
| key_less_literal_comparator); |
| while (search_node != NULL) { |
| DEBUG_ASSERT(static_cast<const NodeHeader*>(search_node)->is_leaf); |
| const uint16_t num_keys = static_cast<const NodeHeader*>(search_node)->num_keys; |
| const char *key_ptr = static_cast<const char*>(search_node) + sizeof(NodeHeader); |
| for (uint16_t entry_num = 0; entry_num < num_keys; ++entry_num) { |
| if (!match_found) { |
| if (!key_less_literal_comparator.compareDataPtrsInl(key_ptr, literal)) { |
| match_found = true; |
| } |
| } |
| |
| if (match_found) { |
| if (literal_less_key_comparator.compareDataPtrsInl(literal, key_ptr)) { |
| // End of matches. |
| return matches.release(); |
| } |
| matches->set(*reinterpret_cast<const tuple_id*>(key_ptr + key_length_bytes_), true); |
| } |
| key_ptr += key_tuple_id_pair_length_bytes_; |
| } |
| search_node = getRightSiblingOfLeafNode(search_node); |
| } |
| |
| return matches.release(); |
| } |
| |
| template <typename LiteralLessKeyComparatorT, |
| typename KeyLessLiteralComparatorT> |
| TupleIdSequence* CSBTreeIndexSubBlock::evaluateNotEqualPredicate( |
| const void *literal, |
| const LiteralLessKeyComparatorT &literal_less_key_comparator, |
| const KeyLessLiteralComparatorT &key_less_literal_comparator) const { |
| std::unique_ptr<TupleIdSequence> matches(new TupleIdSequence(tuple_store_.getMaxTupleID() + 1)); |
| |
| const void *boundary_node = findLeaf(getRootNode(), |
| literal, |
| literal_less_key_comparator, |
| key_less_literal_comparator); |
| const void *search_node = getLeftmostLeaf(); |
| |
| // Fill in all tuples from leaves definitively less than the key. |
| while (search_node != boundary_node) { |
| DEBUG_ASSERT(search_node != NULL); |
| DEBUG_ASSERT(static_cast<const NodeHeader*>(search_node)->is_leaf); |
| const uint16_t num_keys = static_cast<const NodeHeader*>(search_node)->num_keys; |
| const char *tuple_id_ptr = static_cast<const char*>(search_node) |
| + sizeof(NodeHeader) |
| + key_length_bytes_; |
| for (uint16_t entry_num = 0; entry_num < num_keys; ++entry_num) { |
| matches->set(*reinterpret_cast<const tuple_id*>(tuple_id_ptr), true); |
| tuple_id_ptr += key_tuple_id_pair_length_bytes_; |
| } |
| search_node = getRightSiblingOfLeafNode(search_node); |
| } |
| |
| // Actually do comparisons in leaves that may contain the literal key. |
| bool equal_found = false; |
| bool past_equal = false; |
| while (search_node != NULL) { |
| DEBUG_ASSERT(static_cast<const NodeHeader*>(search_node)->is_leaf); |
| const uint16_t num_keys = static_cast<const NodeHeader*>(search_node)->num_keys; |
| const char *key_ptr = static_cast<const char*>(search_node) + sizeof(NodeHeader); |
| for (uint16_t entry_num = 0; entry_num < num_keys; ++entry_num) { |
| if (!equal_found) { |
| if (key_less_literal_comparator.compareDataPtrsInl(key_ptr, literal)) { |
| // key < literal |
| matches->set(*reinterpret_cast<const tuple_id*>(key_ptr + key_length_bytes_), true); |
| } else { |
| equal_found = true; |
| } |
| } |
| |
| if (equal_found) { |
| if (literal_less_key_comparator.compareDataPtrsInl(literal, key_ptr)) { |
| // literal < key |
| // Fill in the rest of the keys from this leaf. |
| for (uint16_t subsequent_num = entry_num; |
| subsequent_num < num_keys; |
| ++subsequent_num) { |
| matches->set(*reinterpret_cast<const tuple_id*>(key_ptr + key_length_bytes_), true); |
| key_ptr += key_tuple_id_pair_length_bytes_; |
| } |
| past_equal = true; |
| break; |
| } |
| } |
| key_ptr += key_tuple_id_pair_length_bytes_; |
| } |
| search_node = getRightSiblingOfLeafNode(search_node); |
| if (past_equal) { |
| break; |
| } |
| } |
| |
| // Fill in all tuples from leaves definitively greater than the key. |
| while (search_node != NULL) { |
| DEBUG_ASSERT(static_cast<const NodeHeader*>(search_node)->is_leaf); |
| uint16_t num_keys = static_cast<const NodeHeader*>(search_node)->num_keys; |
| const char *tuple_id_ptr = static_cast<const char*>(search_node) |
| + sizeof(NodeHeader) |
| + key_length_bytes_; |
| for (uint16_t entry_num = 0; entry_num < num_keys; ++entry_num) { |
| matches->set(*reinterpret_cast<const tuple_id*>(tuple_id_ptr), true); |
| tuple_id_ptr += key_tuple_id_pair_length_bytes_; |
| } |
| search_node = getRightSiblingOfLeafNode(search_node); |
| } |
| |
| return matches.release(); |
| } |
| |
| template <typename LiteralLessKeyComparatorT, |
| typename KeyLessLiteralComparatorT, |
| bool include_equal> |
| TupleIdSequence* CSBTreeIndexSubBlock::evaluateLessPredicate( |
| const void *literal, |
| const LiteralLessKeyComparatorT &literal_less_key_comparator, |
| const KeyLessLiteralComparatorT &key_less_literal_comparator) const { |
| std::unique_ptr<TupleIdSequence> matches(new TupleIdSequence(tuple_store_.getMaxTupleID() + 1)); |
| |
| const void *boundary_node = findLeaf(getRootNode(), |
| literal, |
| literal_less_key_comparator, |
| key_less_literal_comparator); |
| const void *search_node = getLeftmostLeaf(); |
| |
| // Fill in all tuples from leaves definitively less than the key. |
| while (search_node != boundary_node) { |
| DEBUG_ASSERT(search_node != NULL); |
| DEBUG_ASSERT(static_cast<const NodeHeader*>(search_node)->is_leaf); |
| uint16_t num_keys = static_cast<const NodeHeader*>(search_node)->num_keys; |
| const char *tuple_id_ptr = static_cast<const char*>(search_node) |
| + sizeof(NodeHeader) |
| + key_length_bytes_; |
| for (uint16_t entry_num = 0; entry_num < num_keys; ++entry_num) { |
| matches->set(*reinterpret_cast<const tuple_id*>(tuple_id_ptr), true); |
| tuple_id_ptr += key_tuple_id_pair_length_bytes_; |
| } |
| search_node = getRightSiblingOfLeafNode(search_node); |
| } |
| |
| // Actually do comparisons in leaves that may contain the literal key. |
| if (include_equal) { |
| bool equal_found = false; |
| while (search_node != NULL) { |
| DEBUG_ASSERT(static_cast<const NodeHeader*>(search_node)->is_leaf); |
| uint16_t num_keys = static_cast<const NodeHeader*>(search_node)->num_keys; |
| const char *key_ptr = static_cast<const char*>(search_node) + sizeof(NodeHeader); |
| for (uint16_t entry_num = 0; entry_num < num_keys; ++entry_num) { |
| if (!equal_found) { |
| if (key_less_literal_comparator.compareDataPtrsInl(key_ptr, literal)) { |
| // key < literal |
| matches->set(*reinterpret_cast<const tuple_id*>(key_ptr + key_length_bytes_), true); |
| } else { |
| equal_found = true; |
| } |
| } |
| |
| if (equal_found) { |
| if (literal_less_key_comparator.compareDataPtrsInl(literal, key_ptr)) { |
| // literal < key |
| return matches.release(); |
| } else { |
| matches->set(*reinterpret_cast<const tuple_id*>(key_ptr + key_length_bytes_), true); |
| } |
| } |
| |
| key_ptr += key_tuple_id_pair_length_bytes_; |
| } |
| search_node = getRightSiblingOfLeafNode(search_node); |
| } |
| } else { |
| while (search_node != NULL) { |
| DEBUG_ASSERT(static_cast<const NodeHeader*>(search_node)->is_leaf); |
| uint16_t num_keys = static_cast<const NodeHeader*>(search_node)->num_keys; |
| const char *key_ptr = static_cast<const char*>(search_node) + sizeof(NodeHeader); |
| for (uint16_t entry_num = 0; entry_num < num_keys; ++entry_num) { |
| if (key_less_literal_comparator.compareDataPtrsInl(key_ptr, literal)) { |
| // key < literal |
| matches->set(*reinterpret_cast<const tuple_id*>(key_ptr + key_length_bytes_), true); |
| } else { |
| return matches.release(); |
| } |
| key_ptr += key_tuple_id_pair_length_bytes_; |
| } |
| search_node = getRightSiblingOfLeafNode(search_node); |
| } |
| } |
| |
| return matches.release(); |
| } |
| |
| template <typename LiteralLessKeyComparatorT, |
| typename KeyLessLiteralComparatorT, |
| bool include_equal> |
| TupleIdSequence* CSBTreeIndexSubBlock::evaluateGreaterPredicate( |
| const void *literal, |
| const LiteralLessKeyComparatorT &literal_less_key_comparator, |
| const KeyLessLiteralComparatorT &key_less_literal_comparator) const { |
| std::unique_ptr<TupleIdSequence> matches(new TupleIdSequence(tuple_store_.getMaxTupleID() + 1)); |
| |
| const void *search_node = findLeaf(getRootNode(), |
| literal, |
| literal_less_key_comparator, |
| key_less_literal_comparator); |
| |
| // Do comparisons in leaves that may contain the literal key. |
| bool match_found = false; |
| while (search_node != NULL) { |
| DEBUG_ASSERT(static_cast<const NodeHeader*>(search_node)->is_leaf); |
| uint16_t num_keys = static_cast<const NodeHeader*>(search_node)->num_keys; |
| const char *key_ptr = static_cast<const char*>(search_node) + sizeof(NodeHeader); |
| for (uint16_t entry_num = 0; entry_num < num_keys; ++entry_num) { |
| if (include_equal) { |
| if (!key_less_literal_comparator.compareDataPtrsInl(key_ptr, literal)) { |
| match_found = true; |
| } |
| } else { |
| if (literal_less_key_comparator.compareDataPtrsInl(literal, key_ptr)) { |
| match_found = true; |
| } |
| } |
| |
| if (match_found) { |
| // Fill in the matching entries from this leaf. |
| for (uint16_t match_num = entry_num; match_num < num_keys; ++match_num) { |
| matches->set(*reinterpret_cast<const tuple_id*>(key_ptr + key_length_bytes_), true); |
| key_ptr += key_tuple_id_pair_length_bytes_; |
| } |
| break; |
| } |
| |
| key_ptr += key_tuple_id_pair_length_bytes_; |
| } |
| |
| search_node = getRightSiblingOfLeafNode(search_node); |
| if (match_found) { |
| break; |
| } |
| } |
| |
| // Fill in all tuples from leaves definitively greater than the key. |
| while (search_node != NULL) { |
| DEBUG_ASSERT(static_cast<const NodeHeader*>(search_node)->is_leaf); |
| uint16_t num_keys = static_cast<const NodeHeader*>(search_node)->num_keys; |
| const char *tuple_id_ptr = static_cast<const char*>(search_node) |
| + sizeof(NodeHeader) |
| + key_length_bytes_; |
| for (uint16_t entry_num = 0; entry_num < num_keys; ++entry_num) { |
| matches->set(*reinterpret_cast<const tuple_id*>(tuple_id_ptr), true); |
| tuple_id_ptr += key_tuple_id_pair_length_bytes_; |
| } |
| search_node = getRightSiblingOfLeafNode(search_node); |
| } |
| |
| return matches.release(); |
| } |
| |
| bool CSBTreeIndexSubBlock::rebuildSpaceCheck() const { |
| DEBUG_ASSERT(node_group_used_bitmap_->size() > 0); |
| if (tuple_store_.isEmpty()) { |
| return true; |
| } |
| |
| // Check that this sub block will be able to fit entries for all tuples. |
| const tuple_id num_tuples = tuple_store_.numTuples(); |
| // If all tuples can fit in a single leaf, then the root will be sufficient. |
| if (num_tuples > max_keys_leaf_) { |
| int num_node_groups_needed = 1; // 1 for the root. |
| const int keys_in_leaf_node_group = max_keys_leaf_ * (max_keys_internal_ + 1); |
| int num_node_groups_this_level = (num_tuples / keys_in_leaf_node_group) |
| + (num_tuples % keys_in_leaf_node_group ? 1 : 0); |
| num_node_groups_needed += num_node_groups_this_level; |
| while (num_node_groups_this_level > 1) { |
| num_node_groups_this_level = (num_node_groups_this_level / (max_keys_internal_ + 1)) |
| + (num_node_groups_this_level % (max_keys_internal_ + 1) ? 1 : 0); |
| num_node_groups_needed += num_node_groups_this_level; |
| } |
| if (static_cast<size_t>(num_node_groups_needed) > node_group_used_bitmap_->size()) { |
| return false; |
| } |
| } |
| |
| return true; |
| } |
| |
| uint16_t CSBTreeIndexSubBlock::rebuildLeaves(std::vector<int> *used_node_groups) { |
| DEBUG_ASSERT(static_cast<size_t>(num_free_node_groups_) == node_group_used_bitmap_->size() - 1); |
| DEBUG_ASSERT(rebuildSpaceCheck()); |
| |
| if (key_is_compressed_) { |
| vector<csbtree_internal::CompressedEntryReference> entries; |
| generateEntryReferencesFromCompressedCodes(&entries); |
| return buildLeavesFromEntryReferences(&entries, used_node_groups); |
| } else if (key_is_composite_) { |
| vector<csbtree_internal::CompositeEntryReference> entries; |
| generateEntryReferencesFromCompositeKeys(&entries); |
| return buildLeavesFromEntryReferences(&entries, used_node_groups); |
| } else { |
| vector<csbtree_internal::EntryReference> entries; |
| generateEntryReferencesFromTypedValues(&entries); |
| return buildLeavesFromEntryReferences(&entries, used_node_groups); |
| } |
| } |
| |
| template <class EntryReferenceT> |
| std::uint16_t CSBTreeIndexSubBlock::buildLeavesFromEntryReferences( |
| std::vector<EntryReferenceT> *entry_references, |
| std::vector<int> *used_node_groups) { |
| // Build tree from packed leaves. |
| int current_node_group_number = getRootNodeGroupNumber(); |
| used_node_groups->push_back(current_node_group_number); |
| |
| uint16_t current_node_number = 0; |
| uint16_t current_key_number = 0; |
| char *node_ptr = static_cast<char*>(getNode(current_node_group_number, current_node_number)); |
| // Set up the first node's header. |
| // If this node is not totally full (i.e. it is the rightmost leaf), |
| // num_keys will be reset to the correct value after the loop below. |
| reinterpret_cast<NodeHeader*>(node_ptr)->num_keys = max_keys_leaf_; |
| reinterpret_cast<NodeHeader*>(node_ptr)->is_leaf = true; |
| reinterpret_cast<NodeHeader*>(node_ptr)->node_group_reference = kNodeGroupNone; |
| |
| // Build all the leaves. |
| for (typename vector<EntryReferenceT>::const_iterator entry_it = entry_references->begin(); |
| entry_it != entry_references->end(); |
| ++entry_it) { |
| if (current_key_number == max_keys_leaf_) { |
| // At the end of this node, most move to the next. |
| if (current_node_number == max_keys_internal_) { |
| // At the end of this node group, must allocate a new one. |
| int next_node_group_number = allocateNodeGroup(); |
| DEBUG_ASSERT(next_node_group_number >= 0); |
| used_node_groups->push_back(next_node_group_number); |
| reinterpret_cast<NodeHeader*>(node_ptr)->node_group_reference = next_node_group_number; |
| current_node_group_number = next_node_group_number; |
| current_node_number = 0; |
| node_ptr = static_cast<char*>(getNode(current_node_group_number, current_node_number)); |
| } else { |
| // Use the next node in the current group. |
| reinterpret_cast<NodeHeader*>(node_ptr)->node_group_reference = kNodeGroupNextLeaf; |
| ++current_node_number; |
| node_ptr += kCSBTreeNodeSizeBytes; |
| } |
| // Set up new leaf node's header. |
| // If this node is not totally full (i.e. it is the rightmost leaf), |
| // num_keys will be reset to the correct value when this loop exits. |
| reinterpret_cast<NodeHeader*>(node_ptr)->num_keys = max_keys_leaf_; |
| reinterpret_cast<NodeHeader*>(node_ptr)->is_leaf = true; |
| reinterpret_cast<NodeHeader*>(node_ptr)->node_group_reference = kNodeGroupNone; |
| // Reset key number. |
| current_key_number = 0; |
| } |
| // Insert the key. |
| memcpy(node_ptr + sizeof(NodeHeader) + current_key_number * key_tuple_id_pair_length_bytes_, |
| entry_it->getDataPtr(), |
| key_length_bytes_); |
| // Set the tuple_id. |
| *reinterpret_cast<tuple_id*>(node_ptr |
| + sizeof(NodeHeader) |
| + current_key_number * key_tuple_id_pair_length_bytes_ |
| + key_length_bytes_) |
| = entry_it->getTupleID(); |
| ++current_key_number; |
| } |
| // Reset num_keys for the last leaf. |
| reinterpret_cast<NodeHeader*>(node_ptr)->num_keys = current_key_number; |
| return current_node_number + 1; |
| } |
| |
| void CSBTreeIndexSubBlock::generateEntryReferencesFromCompressedCodes( |
| std::vector<csbtree_internal::CompressedEntryReference> *entry_references) const { |
| DEBUG_ASSERT(key_is_compressed_); |
| // TODO(chasseur): Handle NULL. |
| DEBUG_ASSERT(!key_is_nullable_); |
| DEBUG_ASSERT(entry_references->empty()); |
| |
| DEBUG_ASSERT(tuple_store_.isCompressed()); |
| const CompressedTupleStorageSubBlock &compressed_tuple_store |
| = static_cast<const CompressedTupleStorageSubBlock&>(tuple_store_); |
| DEBUG_ASSERT(compressed_tuple_store.compressedBlockIsBuilt()); |
| DEBUG_ASSERT(compressed_tuple_store.compressedAttributeIsDictionaryCompressed(indexed_attribute_ids_.front()) |
| || compressed_tuple_store.compressedAttributeIsTruncationCompressed(indexed_attribute_ids_.front())); |
| |
| if (tuple_store_.isPacked()) { |
| for (tuple_id tid = 0; tid <= tuple_store_.getMaxTupleID(); ++tid) { |
| entry_references->emplace_back( |
| compressed_tuple_store.compressedGetCode(tid, indexed_attribute_ids_.front()), |
| tid); |
| } |
| } else { |
| for (tuple_id tid = 0; tid <= tuple_store_.getMaxTupleID(); ++tid) { |
| if (tuple_store_.hasTupleWithID(tid)) { |
| entry_references->emplace_back( |
| compressed_tuple_store.compressedGetCode(tid, indexed_attribute_ids_.front()), |
| tid); |
| } |
| } |
| } |
| |
| sort(entry_references->begin(), |
| entry_references->end(), |
| csbtree_internal::CompressedEntryReferenceComparator()); |
| |
| DEBUG_ASSERT(static_cast<vector<csbtree_internal::CompressedEntryReference>::size_type>( |
| tuple_store_.numTuples()) == entry_references->size()); |
| } |
| |
| void CSBTreeIndexSubBlock::generateEntryReferencesFromTypedValues( |
| vector<csbtree_internal::EntryReference> *entry_references) const { |
| DEBUG_ASSERT(!key_is_composite_); |
| DEBUG_ASSERT(entry_references->empty()); |
| |
| tuple_id null_count = 0; |
| if (tuple_store_.isPacked()) { |
| for (tuple_id tid = 0; tid <= tuple_store_.getMaxTupleID(); ++tid) { |
| TypedValue literal_key(tuple_store_.getAttributeValueTyped(tid, indexed_attribute_ids_.front())); |
| // Don't insert a NULL key. |
| if (!literal_key.isNull()) { |
| entry_references->emplace_back(std::move(literal_key), tid); |
| } else { |
| ++null_count; |
| } |
| } |
| } else { |
| for (tuple_id tid = 0; tid <= tuple_store_.getMaxTupleID(); ++tid) { |
| if (tuple_store_.hasTupleWithID(tid)) { |
| TypedValue literal_key(tuple_store_.getAttributeValueTyped(tid, indexed_attribute_ids_.front())); |
| // Don't insert a NULL key. |
| if (!literal_key.isNull()) { |
| entry_references->emplace_back(std::move(literal_key), tid); |
| } else { |
| ++null_count; |
| } |
| } |
| } |
| } |
| |
| SortWrappedValues<csbtree_internal::EntryReference, |
| vector<csbtree_internal::EntryReference>::iterator>(*key_type_, |
| entry_references->begin(), |
| entry_references->end()); |
| |
| DEBUG_ASSERT(static_cast<vector<csbtree_internal::EntryReference>::size_type>(tuple_store_.numTuples()) |
| == entry_references->size() + null_count); |
| } |
| |
| void CSBTreeIndexSubBlock::generateEntryReferencesFromCompositeKeys( |
| vector<csbtree_internal::CompositeEntryReference> *entry_references) const { |
| DEBUG_ASSERT(key_is_composite_); |
| DEBUG_ASSERT(entry_references->empty()); |
| |
| tuple_id null_count = 0; |
| if (tuple_store_.isPacked()) { |
| for (tuple_id tid = 0; tid <= tuple_store_.getMaxTupleID(); ++tid) { |
| void *key_copy = makeKeyCopy(tid); |
| // Don't insert a NULL key. |
| if (key_copy != NULL) { |
| entry_references->emplace_back(key_copy, tid); |
| } else { |
| ++null_count; |
| } |
| } |
| } else { |
| for (tuple_id tid = 0; tid <= tuple_store_.getMaxTupleID(); ++tid) { |
| if (tuple_store_.hasTupleWithID(tid)) { |
| void *key_copy = makeKeyCopy(tid); |
| // Don't insert a NULL key. |
| if (key_copy != NULL) { |
| entry_references->emplace_back(key_copy, tid); |
| } else { |
| ++null_count; |
| } |
| } |
| } |
| } |
| |
| sort(entry_references->begin(), |
| entry_references->end(), |
| csbtree_internal::CompositeEntryReferenceComparator(*composite_key_comparator_)); |
| |
| DEBUG_ASSERT(static_cast<vector<csbtree_internal::EntryReference>::size_type>(tuple_store_.numTuples()) |
| == entry_references->size() + null_count); |
| } |
| |
| uint16_t CSBTreeIndexSubBlock::rebuildInternalLevel(const std::vector<int> &child_node_groups, |
| uint16_t last_child_num_nodes, |
| std::vector<int> *used_node_groups) { |
| DEBUG_ASSERT(last_child_num_nodes > 0); |
| DEBUG_ASSERT(!child_node_groups.empty()); |
| |
| std::vector<int>::const_iterator last_it = child_node_groups.end() - 1; |
| // Adjusted to proper value below. |
| std::vector<int>::const_iterator next_to_last_it = child_node_groups.end(); |
| uint16_t next_to_last_child_num_nodes = max_keys_internal_ + 1; |
| |
| if (child_node_groups.size() > 1) { |
| next_to_last_it -= 2; |
| if (last_child_num_nodes < large_half_num_children_) { |
| // Rebalance last node groups as needed. |
| DEBUG_ASSERT(child_node_groups.size() > 1); |
| next_to_last_child_num_nodes = rebalanceNodeGroups(*next_to_last_it, |
| child_node_groups.back(), |
| last_child_num_nodes); |
| last_child_num_nodes = large_half_num_children_; |
| } |
| } |
| |
| int current_node_group_number = allocateNodeGroup(); |
| DEBUG_ASSERT(current_node_group_number >= 0); |
| used_node_groups->push_back(current_node_group_number); |
| |
| uint16_t current_node_number = 0; |
| for (std::vector<int>::const_iterator it = child_node_groups.begin(); |
| it != child_node_groups.end(); |
| ++it) { |
| if (current_node_number == max_keys_internal_ + 1) { |
| // Advance to next node group. |
| current_node_group_number = allocateNodeGroup(); |
| DEBUG_ASSERT(current_node_group_number >= 0); |
| used_node_groups->push_back(current_node_group_number); |
| current_node_number = 0; |
| } |
| |
| if (it == next_to_last_it) { |
| makeInternalNode(*it, |
| next_to_last_child_num_nodes, |
| getNode(current_node_group_number, current_node_number)); |
| } else if (it == last_it) { |
| makeInternalNode(*it, |
| last_child_num_nodes, |
| getNode(current_node_group_number, current_node_number)); |
| } else { |
| makeInternalNode(*it, |
| max_keys_internal_ + 1, |
| getNode(current_node_group_number, current_node_number)); |
| } |
| ++current_node_number; |
| } |
| |
| return current_node_number; |
| } |
| |
| uint16_t CSBTreeIndexSubBlock::rebalanceNodeGroups(const int full_node_group_number, |
| const int underfull_node_group_number, |
| const uint16_t underfull_num_nodes) { |
| DEBUG_ASSERT(underfull_num_nodes < large_half_num_children_); |
| |
| const uint16_t shift_nodes = large_half_num_children_ - underfull_num_nodes; |
| const uint16_t full_group_remaining_nodes = max_keys_internal_ + 1 - shift_nodes; |
| // Shift existing nodes in underfull node group right. |
| memmove(getNode(underfull_node_group_number, shift_nodes), |
| getNode(underfull_node_group_number, 0), |
| underfull_num_nodes * kCSBTreeNodeSizeBytes); |
| // Copy nodes from full node group over. |
| memcpy(getNode(underfull_node_group_number, 0), |
| getNode(full_node_group_number, full_group_remaining_nodes), |
| shift_nodes * kCSBTreeNodeSizeBytes); |
| |
| // If the rebalanced nodes are leaves, correct the sibling references. |
| NodeHeader *full_group_last_header |
| = static_cast<NodeHeader*>(getNode(full_node_group_number, full_group_remaining_nodes - 1)); |
| if (full_group_last_header->is_leaf) { |
| full_group_last_header->node_group_reference = underfull_node_group_number; |
| static_cast<NodeHeader*>(getNode(underfull_node_group_number, shift_nodes - 1))->node_group_reference |
| = kNodeGroupNextLeaf; |
| } |
| |
| return full_group_remaining_nodes; |
| } |
| |
| void CSBTreeIndexSubBlock::makeInternalNode(const int child_node_group_number, |
| const uint16_t num_children, |
| void *node) { |
| DEBUG_ASSERT(num_children > 1); |
| // Setup header. |
| static_cast<NodeHeader*>(node)->num_keys = num_children - 1; |
| static_cast<NodeHeader*>(node)->is_leaf = false; |
| static_cast<NodeHeader*>(node)->node_group_reference = child_node_group_number; |
| |
| // Fill in keys. |
| char *key_ptr = static_cast<char*>(node) + sizeof(NodeHeader); |
| for (uint16_t child_num = 1; child_num < num_children; ++child_num) { |
| DEBUG_ASSERT(static_cast<const NodeHeader*>(getNode(child_node_group_number, child_num))->num_keys > 0); |
| // TODO(chasseur): We could simply remember the least keys of all nodes |
| // generated in the previous pass, but that is a time/space tradeoff |
| // which may not be worth it. |
| memcpy(key_ptr, |
| getLeastKey(getNode(child_node_group_number, child_num)), |
| key_length_bytes_); |
| key_ptr += key_length_bytes_; |
| } |
| } |
| |
| int CSBTreeIndexSubBlock::allocateNodeGroup() { |
| if (num_free_node_groups_ == 0) { |
| // No more node groups are available. |
| return kNodeGroupNone; |
| } else { |
| DEBUG_ASSERT(!node_group_used_bitmap_->getBit(next_free_node_group_)); |
| // Return the next free node group. |
| int retval = next_free_node_group_; |
| // Mark this node group as used and decrement the count of free node |
| // groups. |
| node_group_used_bitmap_->setBit(retval, true); |
| --num_free_node_groups_; |
| // If there are still free node groups remaining, locate the next one. |
| if (num_free_node_groups_) { |
| next_free_node_group_ = node_group_used_bitmap_->firstZero(retval + 1); |
| DEBUG_ASSERT(static_cast<size_t>(next_free_node_group_) < node_group_used_bitmap_->size()); |
| return retval; |
| } else { |
| next_free_node_group_ = kNodeGroupNone; |
| } |
| return retval; |
| } |
| } |
| |
| void CSBTreeIndexSubBlock::deallocateNodeGroup(const int node_group_number) { |
| DEBUG_ASSERT(node_group_number >= 0); |
| DEBUG_ASSERT(static_cast<size_t>(node_group_number) < node_group_used_bitmap_->size()); |
| DEBUG_ASSERT(node_group_used_bitmap_->getBit(node_group_number)); |
| |
| node_group_used_bitmap_->setBit(node_group_number, false); |
| ++num_free_node_groups_; |
| if (node_group_number < next_free_node_group_) { |
| next_free_node_group_ = node_group_number; |
| } |
| } |
| |
| } // namespace quickstep |