diff options
author | Henning Baldersheim <balder@yahoo-inc.com> | 2023-11-02 13:50:05 +0000 |
---|---|---|
committer | Henning Baldersheim <balder@yahoo-inc.com> | 2023-11-02 13:59:58 +0000 |
commit | c7dc9bbd20304071910f4e85121dd80bccc6e706 (patch) | |
tree | 20c61e1d07138237fabec7b332206415db838d25 /vespalib/src | |
parent | 38f3c0c47d005fff498a4b7686492bf2640a3f69 (diff) |
Deinline foreach also for internal nodes
Diffstat (limited to 'vespalib/src')
-rw-r--r-- | vespalib/src/vespa/vespalib/btree/btreenode.h | 43 | ||||
-rw-r--r-- | vespalib/src/vespa/vespalib/btree/btreenode.hpp | 71 |
2 files changed, 68 insertions, 46 deletions
diff --git a/vespalib/src/vespa/vespalib/btree/btreenode.h b/vespalib/src/vespa/vespalib/btree/btreenode.h index 0e214eff83b..7a4fa8030d3 100644 --- a/vespalib/src/vespa/vespalib/btree/btreenode.h +++ b/vespalib/src/vespa/vespalib/btree/btreenode.h @@ -380,54 +380,17 @@ public: void cleanFrozen(); template <typename NodeStoreType, typename FunctionType> - void foreach_key(NodeStoreType &store, FunctionType func) const { - const BTreeNode::ChildRef *it = this->_data; - const BTreeNode::ChildRef *ite = it + _validSlots; - if (this->getLevel() > 1u) { - for (; it != ite; ++it) { - store.mapInternalRef(it->load_acquire())->foreach_key(store, func); - } - } else { - for (; it != ite; ++it) { - store.mapLeafRef(it->load_acquire())->foreach_key(func); - } - } - } + void foreach_key(NodeStoreType &store, FunctionType func) const; /** * Call func with leaf entry key value as argument for all leaf entries in subtrees * for children [start_idx, end_idx). */ template <typename NodeStoreType, typename FunctionType> - void foreach_key_range(NodeStoreType &store, uint32_t start_idx, uint32_t end_idx, FunctionType func) const { - const BTreeNode::ChildRef *it = this->_data; - const BTreeNode::ChildRef *ite = it + end_idx; - it += start_idx; - if (this->getLevel() > 1u) { - for (; it != ite; ++it) { - store.mapInternalRef(it->load_acquire())->foreach_key(store, func); - } - } else { - for (; it != ite; ++it) { - store.mapLeafRef(it->load_acquire())->foreach_key(func); - } - } - } + void foreach_key_range(NodeStoreType &store, uint32_t start_idx, uint32_t end_idx, FunctionType func) const; template <typename NodeStoreType, typename FunctionType> - void foreach(NodeStoreType &store, FunctionType func) const { - const BTreeNode::ChildRef *it = this->_data; - const BTreeNode::ChildRef *ite = it + _validSlots; - if (this->getLevel() > 1u) { - for (; it != ite; ++it) { - store.mapInternalRef(it->load_acquire())->foreach(store, func); - } - } else { - for (; it != ite; ++it) { - store.mapLeafRef(it->load_acquire())->foreach(func); - } - } - } + void foreach(NodeStoreType &store, FunctionType func) const; }; template <typename KeyT, typename DataT, typename AggrT, uint32_t NumSlots = 16> diff --git a/vespalib/src/vespa/vespalib/btree/btreenode.hpp b/vespalib/src/vespa/vespalib/btree/btreenode.hpp index 52e83dd6f72..12b5c985ca6 100644 --- a/vespalib/src/vespa/vespalib/btree/btreenode.hpp +++ b/vespalib/src/vespa/vespalib/btree/btreenode.hpp @@ -16,7 +16,7 @@ private: uint32_t _median; bool _medianBumped; public: - SplitInsertHelper(uint32_t idx, uint32_t validSlots) : + SplitInsertHelper(uint32_t idx, uint32_t validSlots) noexcept : _idx(idx), _median(validSlots / 2), _medianBumped(false) @@ -26,8 +26,8 @@ public: _medianBumped = true; } } - uint32_t getMedian() const { return _median; } - bool insertInSplitNode() const { + uint32_t getMedian() const noexcept { return _median; } + bool insertInSplitNode() const noexcept { if (_median >= _idx && !_medianBumped) { return false; } @@ -361,6 +361,62 @@ BTreeInternalNode<KeyT, AggrT, NumSlots>::cleanFrozen() _validLeaves = 0; } +template <typename KeyT, typename AggrT, uint32_t NumSlots> +template <typename NodeStoreType, typename FunctionType> +void +BTreeInternalNode<KeyT, AggrT, NumSlots>::foreach_key(NodeStoreType &store, FunctionType func) const { + const BTreeNode::ChildRef *it = this->_data; + const BTreeNode::ChildRef *ite = it + _validSlots; + if (this->getLevel() > 1u) { + for (; it != ite; ++it) { + store.mapInternalRef(it->load_acquire())->foreach_key(store, func); + } + } else { + for (; it != ite; ++it) { + store.mapLeafRef(it->load_acquire())->foreach_key(func); + } + } +} + +/** + * Call func with leaf entry key value as argument for all leaf entries in subtrees + * for children [start_idx, end_idx). + */ +template <typename KeyT, typename AggrT, uint32_t NumSlots> +template <typename NodeStoreType, typename FunctionType> +void +BTreeInternalNode<KeyT, AggrT, NumSlots>::foreach_key_range(NodeStoreType &store, uint32_t start_idx, uint32_t end_idx, FunctionType func) const { + const BTreeNode::ChildRef *it = this->_data; + const BTreeNode::ChildRef *ite = it + end_idx; + it += start_idx; + if (this->getLevel() > 1u) { + for (; it != ite; ++it) { + store.mapInternalRef(it->load_acquire())->foreach_key(store, func); + } + } else { + for (; it != ite; ++it) { + store.mapLeafRef(it->load_acquire())->foreach_key(func); + } + } +} + +template <typename KeyT, typename AggrT, uint32_t NumSlots> +template <typename NodeStoreType, typename FunctionType> +void +BTreeInternalNode<KeyT, AggrT, NumSlots>::foreach(NodeStoreType &store, FunctionType func) const { + const BTreeNode::ChildRef *it = this->_data; + const BTreeNode::ChildRef *ite = it + _validSlots; + if (this->getLevel() > 1u) { + for (; it != ite; ++it) { + store.mapInternalRef(it->load_acquire())->foreach(store, func); + } + } else { + for (; it != ite; ++it) { + store.mapLeafRef(it->load_acquire())->foreach(func); + } + } +} + template <typename KeyT, typename DataT, typename AggrT, uint32_t NumSlots> BTreeLeafNode<KeyT, DataT, AggrT, NumSlots>:: @@ -379,7 +435,8 @@ BTreeLeafNode(const KeyDataType *smallArray, uint32_t arraySize) noexcept template <typename KeyT, typename DataT, typename AggrT, uint32_t NumSlots> template <typename FunctionType> -void BTreeLeafNode<KeyT, DataT, AggrT, NumSlots>::foreach_key(FunctionType func) const { +void +BTreeLeafNode<KeyT, DataT, AggrT, NumSlots>::foreach_key(FunctionType func) const { const KeyT *it = _keys; const KeyT *ite = it + _validSlots; for (; it != ite; ++it) { @@ -392,7 +449,8 @@ void BTreeLeafNode<KeyT, DataT, AggrT, NumSlots>::foreach_key(FunctionType func) */ template <typename KeyT, typename DataT, typename AggrT, uint32_t NumSlots> template <typename FunctionType> -void BTreeLeafNode<KeyT, DataT, AggrT, NumSlots>::foreach_key_range(uint32_t start_idx, uint32_t end_idx, FunctionType func) const { +void +BTreeLeafNode<KeyT, DataT, AggrT, NumSlots>::foreach_key_range(uint32_t start_idx, uint32_t end_idx, FunctionType func) const { const KeyT *it = _keys; const KeyT *ite = it + end_idx; it += start_idx; @@ -403,7 +461,8 @@ void BTreeLeafNode<KeyT, DataT, AggrT, NumSlots>::foreach_key_range(uint32_t sta template <typename KeyT, typename DataT, typename AggrT, uint32_t NumSlots> template <typename FunctionType> -void BTreeLeafNode<KeyT, DataT, AggrT, NumSlots>::foreach(FunctionType func) const { +void +BTreeLeafNode<KeyT, DataT, AggrT, NumSlots>::foreach(FunctionType func) const { const KeyT *it = _keys; const KeyT *ite = it + _validSlots; uint32_t idx = 0; |