diff options
author | Henning Baldersheim <balder@yahoo-inc.com> | 2023-05-17 17:27:28 +0000 |
---|---|---|
committer | Henning Baldersheim <balder@yahoo-inc.com> | 2023-05-17 17:45:12 +0000 |
commit | 7832c68dc4cb00bea2a048d82d7f242625bb66a1 (patch) | |
tree | 5f4701786f97afb45e5ebb320ca496f84e2cac1e /vespalib | |
parent | 3a88b880f0b6323959dafeeb8e0076a7f515e311 (diff) |
Add test for btree iterator size and modernize some header file code
Diffstat (limited to 'vespalib')
-rw-r--r-- | vespalib/src/tests/btree/btree_test.cpp | 7 | ||||
-rw-r--r-- | vespalib/src/vespa/vespalib/btree/btree.h | 111 | ||||
-rw-r--r-- | vespalib/src/vespa/vespalib/btree/btreeiterator.h | 361 |
3 files changed, 113 insertions, 366 deletions
diff --git a/vespalib/src/tests/btree/btree_test.cpp b/vespalib/src/tests/btree/btree_test.cpp index afad3523fa3..6305eca41ac 100644 --- a/vespalib/src/tests/btree/btree_test.cpp +++ b/vespalib/src/tests/btree/btree_test.cpp @@ -2,7 +2,6 @@ #include <string> #include <vespa/vespalib/btree/btreeroot.h> -#include <vespa/vespalib/btree/btreebuilder.h> #include <vespa/vespalib/btree/btreenodeallocator.h> #include <vespa/vespalib/btree/btree.h> #include <vespa/vespalib/btree/btreestore.h> @@ -297,6 +296,12 @@ BTreeTest::assertMemoryUsage(const vespalib::MemoryUsage & exp, const vespalib:: return result; } +TEST_F(BTreeTest, control_iterator_size) { + EXPECT_EQ(208u, sizeof(BTreeIteratorBase<uint32_t, uint32_t, NoAggregated>)); + EXPECT_EQ(208u, sizeof(BTreeIteratorBase<uint32_t, BTreeNoLeafData, NoAggregated>)); + EXPECT_EQ(544u, sizeof(MyTree::Iterator)); +} + TEST_F(BTreeTest, require_that_node_insert_works) { GenerationHandler g; diff --git a/vespalib/src/vespa/vespalib/btree/btree.h b/vespalib/src/vespa/vespalib/btree/btree.h index c2f5aac01b7..0099da718a3 100644 --- a/vespalib/src/vespa/vespalib/btree/btree.h +++ b/vespalib/src/vespa/vespalib/btree/btree.h @@ -39,50 +39,22 @@ public: using ConstIterator = typename TreeType::ConstIterator; using FrozenView = typename TreeType::FrozenView; using AggrCalcType = typename TreeType::AggrCalcType; -private: - NodeAllocatorType _alloc; - TreeType _tree; - - BTree(const BTree &rhs); - BTree & - operator=(BTree &rhs); - -public: + BTree(const BTree &rhs) = delete; + BTree & operator=(BTree &rhs) = delete; BTree(); ~BTree(); const NodeAllocatorType &getAllocator() const { return _alloc; } NodeAllocatorType &getAllocator() { return _alloc; } - - void - disableFreeLists() { - _alloc.disableFreeLists(); - } - - void - disable_entry_hold_list() - { - _alloc.disable_entry_hold_list(); - } - - // Inherit doc from BTreeRoot - void clear() { - _tree.clear(_alloc); - } - void assign(Builder & rhs) { - _tree.assign(rhs, _alloc); - } + void disableFreeLists() { _alloc.disableFreeLists(); } + void disable_entry_hold_list() { _alloc.disable_entry_hold_list(); } + void clear() { _tree.clear(_alloc); } + void assign(Builder & rhs) { _tree.assign(rhs, _alloc); } bool insert(const KeyType & key, const DataType & data, CompareT comp = CompareT()) { return _tree.insert(key, data, _alloc, comp); } - - void - insert(Iterator &itr, - const KeyType &key, const DataType &data) - { - _tree.insert(itr, key, data); - } + void insert(Iterator &itr, const KeyType &key, const DataType &data) { _tree.insert(itr, key, data); } Iterator find(const KeyType & key, CompareT comp = CompareT()) const { return _tree.find(key, _alloc, comp); @@ -97,55 +69,23 @@ public: return _tree.remove(key, _alloc, comp); } - void - remove(Iterator &itr) - { - _tree.remove(itr); - } - - Iterator begin() const { - return _tree.begin(_alloc); - } - FrozenView getFrozenView() const { - return _tree.getFrozenView(_alloc); - } - size_t size() const { - return _tree.size(_alloc); - } - vespalib::string toString() const { - return _tree.toString(_alloc); - } - bool isValid(CompareT comp = CompareT()) const { - return _tree.isValid(_alloc, comp); - } - bool isValidFrozen(CompareT comp = CompareT()) const { - return _tree.isValidFrozen(_alloc, comp); - } - size_t bitSize() const { - return _tree.bitSize(_alloc); - } + void remove(Iterator &itr) { _tree.remove(itr); } + Iterator begin() const { return _tree.begin(_alloc); } + FrozenView getFrozenView() const { return _tree.getFrozenView(_alloc); } + size_t size() const { return _tree.size(_alloc); } + vespalib::string toString() const { return _tree.toString(_alloc); } + bool isValid(CompareT comp = CompareT()) const { return _tree.isValid(_alloc, comp); } + bool isValidFrozen(CompareT comp = CompareT()) const { return _tree.isValidFrozen(_alloc, comp); } + size_t bitSize() const { return _tree.bitSize(_alloc); } size_t bitSize(BTreeNode::Ref node) const { return _tree.bitSize(node, _alloc); } - void setRoot(BTreeNode::Ref newRoot) { - _tree.setRoot(newRoot, _alloc); - } - BTreeNode::Ref getRoot() const { - return _tree.getRoot(); - } - vespalib::MemoryUsage getMemoryUsage() const { - return _alloc.getMemoryUsage(); - } - - const AggrT & - getAggregated() const - { - return _tree.getAggregated(_alloc); - } + void setRoot(BTreeNode::Ref newRoot) { _tree.setRoot(newRoot, _alloc); } + BTreeNode::Ref getRoot() const { return _tree.getRoot(); } + vespalib::MemoryUsage getMemoryUsage() const { return _alloc.getMemoryUsage(); } + const AggrT & getAggregated() const { return _tree.getAggregated(_alloc); } - void - thaw(Iterator &itr) - { + void thaw(Iterator &itr) { assert(&itr.getAllocator() == &getAllocator()); _tree.thaw(itr); } @@ -153,18 +93,17 @@ public: void compact_worst(const datastore::CompactionStrategy& compaction_strategy); template <typename FunctionType> - void - foreach_key(FunctionType func) const - { + void foreach_key(FunctionType func) const { _alloc.getNodeStore().foreach_key(_tree.getRoot(), func); } template <typename FunctionType> - void - foreach(FunctionType func) const - { + void foreach(FunctionType func) const { _alloc.getNodeStore().foreach(_tree.getRoot(), func); } +private: + NodeAllocatorType _alloc; + TreeType _tree; }; } diff --git a/vespalib/src/vespa/vespalib/btree/btreeiterator.h b/vespalib/src/vespa/vespalib/btree/btreeiterator.h index 4b99edf592a..7a754880aa3 100644 --- a/vespalib/src/vespa/vespalib/btree/btreeiterator.h +++ b/vespalib/src/vespa/vespalib/btree/btreeiterator.h @@ -36,115 +36,46 @@ class NodeElement using KeyType = typename NodeType::KeyType; using DataType = typename NodeType::DataType; const NodeType *_node; - uint32_t _idx; - - NodeType * - getWNode() const - { - return const_cast<NodeType *>(_node); - } + uint32_t _idx; + NodeType * getWNode() const { return const_cast<NodeType *>(_node); } public: - NodeElement() - : _node(nullptr), - _idx(0u) - { - } + NodeElement() : _node(nullptr), _idx(0u) { } + NodeElement(const NodeType *node, uint32_t idx) : _node(node), _idx(idx) { } - NodeElement(const NodeType *node, uint32_t idx) - : _node(node), - _idx(idx) - { - } + void setNode(const NodeType *node) { _node = node; } + const NodeType * getNode() const { return _node; } + void setIdx(uint32_t idx) { _idx = idx; } + uint32_t getIdx() const { return _idx; } + void incIdx() { ++_idx; } + void decIdx() { --_idx; } - void - setNode(const NodeType *node) - { + void setNodeAndIdx(const NodeType *node, uint32_t idx) { _node = node; - } - - const NodeType * - getNode() const - { - return _node; - } - - void - setIdx(uint32_t idx) - { _idx = idx; } - uint32_t - getIdx() const - { - return _idx; - } - - void - incIdx() - { - ++_idx; - } - - void - decIdx() - { - --_idx; - } - - void - setNodeAndIdx(const NodeType *node, uint32_t idx) - { - _node = node; - _idx = idx; - } - - const KeyType & - getKey() const - { - return _node->getKey(_idx); - } - - const DataType & - getData() const - { - return _node->getData(_idx); - } - + const KeyType & getKey() const { return _node->getKey(_idx); } + const DataType & getData() const { return _node->getData(_idx); } // Only use during compaction when changing reference to moved value DataType &getWData() { return getWNode()->getWData(_idx); } - - bool - valid() const - { - return _node != nullptr; - } - - void - adjustLeftVictimKilled() - { + bool valid() const { return _node != nullptr; } + void adjustLeftVictimKilled() { assert(_idx > 0); --_idx; } - void - adjustSteal(uint32_t stolen) - { + void adjustSteal(uint32_t stolen) { assert(_idx + stolen < _node->validSlots()); _idx += stolen; } - void - adjustSplit(bool inRightSplit) - { + void adjustSplit(bool inRightSplit) { if (inRightSplit) ++_idx; } - bool - adjustSplit(bool inRightSplit, const NodeType *splitNode) - { + bool adjustSplit(bool inRightSplit, const NodeType *splitNode) { adjustSplit(inRightSplit); if (_idx >= _node->validSlots()) { _idx -= _node->validSlots(); @@ -154,18 +85,13 @@ public: return false; } - void - swap(NodeElement &rhs) - { + void swap(NodeElement &rhs) { std::swap(_node, rhs._node); std::swap(_idx, rhs._idx); } - bool - operator!=(const NodeElement &rhs) const - { - return _node != rhs._node || - _idx != rhs._idx; + bool operator!=(const NodeElement &rhs) const { + return (_node != rhs._node) || (_idx != rhs._idx); } }; @@ -243,8 +169,7 @@ protected: * * @param pidx Number of levels above leaf nodes to take into account. */ - size_t - position(uint32_t pidx) const; + size_t position(uint32_t pidx) const; /** * Create iterator pointing to first element in the tree referenced @@ -273,8 +198,7 @@ protected: /** * Step iterator forwards. If at end then leave it at end. */ - BTreeIteratorBase & - operator++() { + BTreeIteratorBase & operator++() { if (_leaf.getNode() == nullptr) { return *this; } @@ -290,8 +214,7 @@ protected: * Step iterator backwards. If at end then place it at last valid * position in tree (cf. rbegin()) */ - BTreeIteratorBase & - operator--(); + BTreeIteratorBase & operator--(); ~BTreeIteratorBase(); BTreeIteratorBase(const BTreeIteratorBase &other); @@ -311,9 +234,7 @@ protected: * from this iterator position to end of subtree. */ template <typename FunctionType> - void - foreach_key_range_start(uint32_t level, FunctionType func) const - { + void foreach_key_range_start(uint32_t level, FunctionType func) const { if (level > 0u) { --level; foreach_key_range_start(level, func); @@ -332,9 +253,7 @@ protected: * subtree before this iterator position). */ template <typename FunctionType> - void - foreach_key_range_end(uint32_t level, FunctionType func) const - { + void foreach_key_range_end(uint32_t level, FunctionType func) const { if (level > 0u) { --level; auto &store = _allocator->getNodeStore(); @@ -348,8 +267,7 @@ protected: } public: - bool - operator==(const BTreeIteratorBase & rhs) const { + bool operator==(const BTreeIteratorBase & rhs) const { if (_leaf.getIdx() != rhs._leaf.getIdx()) { return false; } @@ -367,83 +285,55 @@ public: return true; } - bool - operator!=(const BTreeIteratorBase & rhs) const - { - return !operator==(rhs); - } + bool operator!=(const BTreeIteratorBase & rhs) const { return !operator==(rhs); } /** * Swap iterator with the other. * * @param rhs Other iterator. */ - void - swap(BTreeIteratorBase & rhs); + void swap(BTreeIteratorBase & rhs); /** * Get key at current iterator location. */ - const KeyType & - getKey() const - { - return _leaf.getKey(); - } + const KeyType & getKey() const { return _leaf.getKey(); } /** * Get data at current iterator location. */ - const DataType & - getData() const - { - return _leaf.getData(); - } + const DataType & getData() const { return _leaf.getData(); } /** * Check if iterator is at a valid element, i.e. not at end. */ - bool - valid() const - { - return _leaf.valid(); - } + bool valid() const { return _leaf.valid(); } /** * Return the number of elements in the tree. */ - size_t - size() const; + size_t size() const; /** * Return the current position in the tree. */ - size_t - position() const - { - return position(_pathSize); - } + size_t position() const { return position(_pathSize); } /** * Return the distance between two positions in the tree. */ - ssize_t - operator-(const BTreeIteratorBase &rhs) const; + ssize_t operator-(const BTreeIteratorBase &rhs) const; /** * Return if the tree has data or not (e.g. keys and data or only keys). */ - static bool - hasData() - { - return LeafNodeType::hasData(); - } + static bool hasData() { return LeafNodeType::hasData(); } /** * Move the iterator directly to end. Used by findHelper method in BTree. */ - void - setupEnd(); + void setupEnd(); /** * Setup iterator to be empty and not be associated with any tree. @@ -453,50 +343,41 @@ public: /** * Move iterator to beyond last element in the current tree. */ - void - end() __attribute__((noinline)); + void end() __attribute__((noinline)); /** * Move iterator to beyond last element in the given tree. * * @param rootRef Reference to root of tree. */ - void - end(BTreeNode::Ref rootRef); + void end(BTreeNode::Ref rootRef); /** * Move iterator to first element in the current tree. */ - void - begin(); + void begin(); /** * Move iterator to first element in the given tree. * * @param rootRef Reference to root of tree. */ - void - begin(BTreeNode::Ref rootRef); + void begin(BTreeNode::Ref rootRef); /** * Move iterator to last element in the current tree. */ - void - rbegin(); + void rbegin(); /* * Get aggregated values for the current tree. */ - const AggrT & - getAggregated() const; + const AggrT & getAggregated() const; - bool - identical(const BTreeIteratorBase &rhs) const; + bool identical(const BTreeIteratorBase &rhs) const; template <typename FunctionType> - void - foreach_key(FunctionType func) const - { + void foreach_key(FunctionType func) const { if (_pathSize > 0) { _path[_pathSize - 1].getNode()-> foreach_key(_allocator->getNodeStore(), func); @@ -511,9 +392,7 @@ public: * range [this iterator, end_itr)). */ template <typename FunctionType> - void - foreach_key_range(const BTreeIteratorBase &end_itr, FunctionType func) const - { + void foreach_key_range(const BTreeIteratorBase &end_itr, FunctionType func) const { if (!valid()) { return; } @@ -584,9 +463,7 @@ class BTreeConstIterator : public BTreeIteratorBase<KeyT, DataT, AggrT, TraitsT::PATH_SIZE> { protected: - using ParentType = BTreeIteratorBase<KeyT, - DataT, - AggrT, + using ParentType = BTreeIteratorBase<KeyT, DataT, AggrT, TraitsT::INTERNAL_SLOTS, TraitsT::LEAF_SLOTS, TraitsT::PATH_SIZE>; @@ -645,17 +522,12 @@ public: /** * Default constructor. Iterator is not associated with a tree. */ - BTreeConstIterator() - : ParentType() - { - } + BTreeConstIterator() : ParentType() { } /** * Step iterator forwards. If at end then leave it at end. */ - BTreeConstIterator & - operator++() - { + BTreeConstIterator & operator++() { ParentType::operator++(); return *this; } @@ -664,9 +536,7 @@ public: * Step iterator backwards. If at end then place it at last valid * position in tree (cf. rbegin()) */ - BTreeConstIterator & - operator--() - { + BTreeConstIterator & operator--() { ParentType::operator--(); return *this; } @@ -679,8 +549,7 @@ public: * @param key Key to search for * @param comp Comparator for the tree ordering. */ - void - lower_bound(const KeyType & key, CompareT comp = CompareT()); + void lower_bound(const KeyType & key, CompareT comp = CompareT()); /** * Position iterator at first position with a key that is greater @@ -689,9 +558,7 @@ public: * @param key Key to search for * @param comp Comparator for the tree ordering. */ - void - lower_bound(BTreeNode::Ref rootRef, - const KeyType & key, CompareT comp = CompareT()); + void lower_bound(BTreeNode::Ref rootRef, const KeyType & key, CompareT comp = CompareT()); /** * Step iterator forwards until it is at a position with a key @@ -704,8 +571,7 @@ public: * @param key Key to search for * @param comp Comparator for the tree ordering. */ - void - seek(const KeyType &key, CompareT comp = CompareT()); + void seek(const KeyType &key, CompareT comp = CompareT()); /** * Step iterator forwards until it is at a position with a key @@ -717,8 +583,7 @@ public: * @param key Key to search for * @param comp Comparator for the tree ordering. */ - void - binarySeek(const KeyType &key, CompareT comp = CompareT()); + void binarySeek(const KeyType &key, CompareT comp = CompareT()); /** * Step iterator forwards until it is at a position with a key @@ -730,8 +595,7 @@ public: * @param key Key to search for * @param comp Comparator for the tree ordering. */ - void - linearSeek(const KeyType &key, CompareT comp = CompareT()); + void linearSeek(const KeyType &key, CompareT comp = CompareT()); /** * Step iterator forwards until it is at a position with a key @@ -744,8 +608,7 @@ public: * @param key Key to search for * @param comp Comparator for the tree ordering. */ - void - seekPast(const KeyType &key, CompareT comp = CompareT()); + void seekPast(const KeyType &key, CompareT comp = CompareT()); /** * Step iterator forwards until it is at a position with a key @@ -757,8 +620,7 @@ public: * @param key Key to search for * @param comp Comparator for the tree ordering. */ - void - binarySeekPast(const KeyType &key, CompareT comp = CompareT()); + void binarySeekPast(const KeyType &key, CompareT comp = CompareT()); /** * Step iterator forwards until it is at a position with a key @@ -770,8 +632,7 @@ public: * @param key Key to search for * @param comp Comparator for the tree ordering. */ - void - linearSeekPast(const KeyType &key, CompareT comp = CompareT()); + void linearSeekPast(const KeyType &key, CompareT comp = CompareT()); /** * Validate the iterator as a valid iterator or positioned at @@ -781,8 +642,7 @@ public: * @param rootRef Reference to root of tree to operate on * @param comp Comparator for the tree ordering. */ - void - validate(BTreeNode::Ref rootRef, CompareT comp = CompareT()); + void validate(BTreeNode::Ref rootRef, CompareT comp = CompareT()); }; @@ -795,15 +655,10 @@ template <typename KeyT, typename AggrT = NoAggregated, typename CompareT = std::less<KeyT>, typename TraitsT = BTreeDefaultTraits> -class BTreeIterator : public BTreeConstIterator<KeyT, DataT, AggrT, - CompareT, TraitsT> +class BTreeIterator : public BTreeConstIterator<KeyT, DataT, AggrT, CompareT, TraitsT> { public: - using ParentType = BTreeConstIterator<KeyT, - DataT, - AggrT, - CompareT, - TraitsT>; + using ParentType = BTreeConstIterator<KeyT, DataT, AggrT, CompareT, TraitsT>; using NodeAllocatorType = typename ParentType::NodeAllocatorType; using InternalNodeType = typename ParentType::InternalNodeType; using LeafNodeType = typename ParentType::LeafNodeType; @@ -844,40 +699,27 @@ public: { } - BTreeIterator() - : ParentType() - { - } + BTreeIterator() : ParentType() { } - BTreeIterator & - operator++() - { + BTreeIterator & operator++() { ParentType::operator++(); return *this; } - BTreeIterator & - operator--() - { + BTreeIterator & operator--() { ParentType::operator--(); return *this; } - NodeAllocatorType & - getAllocator() const - { + NodeAllocatorType & getAllocator() const { return const_cast<NodeAllocatorType &>(*_allocator); } - BTreeNode::Ref - moveFirstLeafNode(BTreeNode::Ref rootRef); + BTreeNode::Ref moveFirstLeafNode(BTreeNode::Ref rootRef); - void - moveNextLeafNode(); + void moveNextLeafNode(); - void - writeData(const DataType &data) - { + void writeData(const DataType &data) { _leaf.getWNode()->writeData(_leaf.getIdx(), data); } @@ -889,8 +731,7 @@ public: * The new key must have the same semantic meaning as the old key. * Typically used when compacting data store containing keys. */ - void - writeKey(const KeyType &key); + void writeKey(const KeyType &key); /** * Updata data at the current iterator position. The tree should @@ -900,71 +741,33 @@ public: * @param aggrCalc Calculator for updating aggregated information. */ template <class AggrCalcT> - void - updateData(const DataType &data, const AggrCalcT &aggrCalc); + void updateData(const DataType &data, const AggrCalcT &aggrCalc); /** * Thaw a path from the root node down the the current leaf node in * the current tree, allowing for updates to be performed without * disturbing the frozen version of the tree. */ - BTreeNode::Ref - thaw(BTreeNode::Ref rootRef); + BTreeNode::Ref thaw(BTreeNode::Ref rootRef); private: /* Insert into empty tree */ template <class AggrCalcT> - BTreeNode::Ref - insertFirst(const KeyType &key, const DataType &data, - const AggrCalcT &aggrCalc); - - LeafNodeType * - getLeafNode() const - { - return _leaf.getWNode(); - } - - bool - setLeafNodeIdx(uint32_t idx, const LeafNodeType *splitLeafNode); - - void - setLeafNodeIdx(uint32_t idx) - { - _leaf.setIdx(idx); - } - - uint32_t - getLeafNodeIdx() const - { - return _leaf.getIdx(); - } - - uint32_t - getPathSize() const - { - return _pathSize; - } - - PathElement & - getPath(uint32_t pidx) - { - return _path[pidx]; - } + BTreeNode::Ref insertFirst(const KeyType &key, const DataType &data, const AggrCalcT &aggrCalc); + LeafNodeType * getLeafNode() const { return _leaf.getWNode(); } + bool setLeafNodeIdx(uint32_t idx, const LeafNodeType *splitLeafNode); + void setLeafNodeIdx(uint32_t idx) { _leaf.setIdx(idx); } + uint32_t getLeafNodeIdx() const { return _leaf.getIdx(); } + uint32_t getPathSize() const { return _pathSize; } + PathElement & getPath(uint32_t pidx) { return _path[pidx]; } template <class AggrCalcT> - BTreeNode::Ref - addLevel(BTreeNode::Ref rootRef, BTreeNode::Ref splitNodeRef, - bool inRightSplit, const AggrCalcT &aggrCalc); + BTreeNode::Ref addLevel(BTreeNode::Ref rootRef, BTreeNode::Ref splitNodeRef, bool inRightSplit, const AggrCalcT &aggrCalc); - BTreeNode::Ref - removeLevel(BTreeNode::Ref rootRef, InternalNodeType *rootNode); + BTreeNode::Ref removeLevel(BTreeNode::Ref rootRef, InternalNodeType *rootNode); + void removeLast(BTreeNode::Ref rootRef); - void - removeLast(BTreeNode::Ref rootRef); - - void - adjustSteal(uint32_t level, bool leftVictimKilled, uint32_t stolen) - { + void adjustSteal(uint32_t level, bool leftVictimKilled, uint32_t stolen) { assert(_pathSize > level); if (leftVictimKilled) { _path[level].adjustLeftVictimKilled(); |