diff options
Diffstat (limited to 'src/mongo')
-rw-r--r-- | src/mongo/db/storage/ephemeral_for_test/ephemeral_for_test_radix_store.h | 1140 | ||||
-rw-r--r-- | src/mongo/db/storage/ephemeral_for_test/ephemeral_for_test_radix_store_test.cpp | 325 |
2 files changed, 224 insertions, 1241 deletions
diff --git a/src/mongo/db/storage/ephemeral_for_test/ephemeral_for_test_radix_store.h b/src/mongo/db/storage/ephemeral_for_test/ephemeral_for_test_radix_store.h index 2a20c94ee17..9410577e442 100644 --- a/src/mongo/db/storage/ephemeral_for_test/ephemeral_for_test_radix_store.h +++ b/src/mongo/db/storage/ephemeral_for_test/ephemeral_for_test_radix_store.h @@ -65,7 +65,6 @@ struct Metrics { totalMemory.fetchAndSubtract(size); } }; -enum class NodeType : uint8_t { LEAF, NODE4, NODE16, NODE48, NODE256 }; /** * RadixStore is a Trie data structure with the ability to share nodes among copies of trees to @@ -89,10 +88,6 @@ public: using size_type = std::size_t; using difference_type = std::ptrdiff_t; using uint8_t = std::uint8_t; - using node_ptr = boost::intrusive_ptr<Node>; - using head_ptr = boost::intrusive_ptr<Head>; - - static constexpr uint8_t maxByte = 255; template <class pointer_type, class reference_type> class radix_iterator { @@ -169,9 +164,10 @@ public: } private: - radix_iterator(const head_ptr& root) : _root(root), _current(nullptr) {} + radix_iterator(const boost::intrusive_ptr<Head>& root) : _root(root), _current(nullptr) {} - radix_iterator(const head_ptr& root, Node* current) : _root(root), _current(current) {} + radix_iterator(const boost::intrusive_ptr<Head>& root, Node* current) + : _root(root), _current(current) {} /** * This function traverses the tree to find the next left-most node with data. Modifies @@ -212,20 +208,25 @@ public: // Check the children right of the node that the iterator was at already. This way, // there will be no backtracking in the traversal. - bool res = _forEachChild(node, oldKey + 1, false, [this](node_ptr child) { - // If the current node has data, return it and exit. If not, find the - // left-most node with data in this sub-tree. - if (child->_data) { - _current = child.get(); - return false; + for (auto iter = oldKey + 1 + node->_children.begin(); + iter != node->_children.end(); + ++iter) { + + // If the node has a child, then the sub-tree must have a node with data that + // has not yet been visited. + if (*iter != nullptr) { + + // If the current node has data, return it and exit. If not, continue + // following the nodes to find the next one with data. It is necessary to go + // to the left-most node in this sub-tree. + if ((*iter)->_data) { + _current = iter->get(); + return; + } + _current = iter->get(); + _traverseLeftSubtree(); + return; } - - _current = child.get(); - _traverseLeftSubtree(); - return false; - }); - if (!res) { - return; } } return; @@ -236,10 +237,12 @@ public: // '_current' is root. However, it cannot return the root, and hence at least 1 // iteration of the while loop is required. do { - _forEachChild(_current, 0, false, [this](node_ptr child) { - _current = child.get(); - return false; - }); + for (auto child : _current->_children) { + if (child != nullptr) { + _current = child.get(); + break; + } + } } while (!_current->_data); } @@ -256,7 +259,7 @@ public: } // "_root" is a pointer to the root of the tree over which this is iterating. - head_ptr _root; + boost::intrusive_ptr<Head> _root; // "_current" is the node that the iterator is currently on. _current->_data will never be // boost::none (unless it is within the process of tree traversal), and _current will be @@ -381,9 +384,10 @@ public: } private: - reverse_radix_iterator(const head_ptr& root) : _root(root), _current(nullptr) {} + reverse_radix_iterator(const boost::intrusive_ptr<Head>& root) + : _root(root), _current(nullptr) {} - reverse_radix_iterator(const head_ptr& root, Node* current) + reverse_radix_iterator(const boost::intrusive_ptr<Head>& root, Node* current) : _root(root), _current(current) {} void _findNextReverse() { @@ -412,15 +416,14 @@ public: // After moving up in the tree, continue searching for neighboring nodes to see if // they have data, moving from right to left. - bool res = _forEachChild(node, oldKey - 1, true, [this](node_ptr child) { - // If there is a sub-tree found, it must have data, therefore it's necessary - // to traverse to the right most node. - _current = child.get(); - _traverseRightSubtree(); - return false; - }); - if (!res) { - return; + for (int i = oldKey - 1; i >= 0; i--) { + if (node->_children[i] != nullptr) { + // If there is a sub-tree found, it must have data, therefore it's necessary + // to traverse to the right most node. + _current = node->_children[i].get(); + _traverseRightSubtree(); + return; + } } // If there were no sub-trees that contained data, and the 'current' node has data, @@ -436,10 +439,13 @@ public: // This function traverses the given tree to the right most leaf of the subtree where // 'current' is the root. do { - _forEachChild(_current, maxByte, true, [this](node_ptr child) { - _current = child.get(); - return false; - }); + for (auto iter = _current->_children.rbegin(); iter != _current->_children.rend(); + ++iter) { + if (*iter != nullptr) { + _current = iter->get(); + break; + } + } } while (!_current->isLeaf()); } @@ -456,7 +462,7 @@ public: } // "_root" is a pointer to the root of the tree over which this is iterating. - head_ptr _root; + boost::intrusive_ptr<Head> _root; // "_current" is a the node that the iterator is currently on. _current->_data will never be // boost::none, and _current will be become a nullptr once there are no more nodes left to @@ -536,9 +542,9 @@ public: return _metrics.totalNodes.load(); } - static float averageChildren() { + static uint16_t averageChildren() { auto totalNodes = _metrics.totalNodes.load(); - return totalNodes ? _metrics.totalChildren.load() / static_cast<float>(totalNodes) : 0; + return totalNodes ? _metrics.totalChildren.load() / totalNodes : 0; } // Modifiers @@ -587,8 +593,8 @@ public: const uint8_t* charKey = reinterpret_cast<const uint8_t*>(key.data()); size_t depth = prev->_depth + prev->_trieKey.size(); while (depth < key.size()) { - auto nodePtr = _findChild(prev, charKey[depth]); - node = nodePtr.get(); + uint8_t c = charKey[depth]; + node = prev->_children[c].get(); if (node == nullptr) { return false; } @@ -599,7 +605,7 @@ public: return false; } - isUniquelyOwned = isUniquelyOwned && nodePtr->refCount() - 1 == 1; + isUniquelyOwned = isUniquelyOwned && prev->_children[c]->refCount() == 1; context.push_back(std::make_pair(node, isUniquelyOwned)); depth = node->_depth + node->_trieKey.size(); prev = node; @@ -637,35 +643,27 @@ public: size_t sizeOfRemovedData = node->_data->second.size(); _root->_dataSize -= sizeOfRemovedData; _root->_count--; - Node* prevParent = nullptr; + for (size_t depth = 1; depth < context.size(); depth++) { Node* child = context.at(depth).first; isUniquelyOwned = context.at(depth).second; uint8_t childFirstChar = child->_trieKey.front(); if (!isUniquelyOwned) { - auto childCopy = _copyNode(child); - _setChildPtr(parent, childFirstChar, childCopy); - child = childCopy.get(); + parent->_children[childFirstChar] = make_intrusive_node<Node>(*child); + child = parent->_children[childFirstChar].get(); } - prevParent = parent; parent = child; } // Handle the deleted node, as it is a leaf. - _setChildPtr(parent, deleted->_trieKey.front(), nullptr); + parent->_children[deleted->_trieKey.front()] = nullptr; + --parent->_numChildren; // 'parent' may only have one child, in which case we need to evaluate whether or not // this node is redundant. - if (auto newParent = _compressOnlyChild(prevParent, parent)) { - parent = newParent; - } - - // Don't shrink the root node. - if (prevParent && parent->needShrink()) { - parent = _shrink(prevParent, parent).get(); - } + _compressOnlyChild(parent); return true; } @@ -731,11 +729,10 @@ public: if (idx != UINT8_MAX) context.push_back(std::make_pair(node, idx + 1)); - auto nodePtr = _findChild(node, idx); - if (!nodePtr) + if (!node->_children[idx]) break; - node = nodePtr.get(); + node = node->_children[idx].get(); size_t mismatchIdx = _comparePrefix(node->_trieKey, charKey + depth, key.size() - depth); @@ -778,17 +775,18 @@ public: std::tie(node, idx) = context.back(); context.pop_back(); - bool exhausted = _forEachChild(node, idx, false, [&node, &context](node_ptr child) { - node = child.get(); - if (!node->_data) { - // Need to search this node's children for the next largest node. - context.push_back(std::make_pair(node, 0)); - } - return false; - }); - if (!exhausted && node->_data) { + for (auto iter = idx + node->_children.begin(); iter != node->_children.end(); ++iter) { + if (!(*iter)) + continue; + // There exists a node with a key larger than the one given. - return const_iterator(_root, node); + node = iter->get(); + if (node->_data) + return const_iterator(_root, node); + + // Need to search this node's children for the next largest node. + context.push_back(std::make_pair(node, 0)); + break; } if (node->_trieKey.empty() && context.empty()) { @@ -826,9 +824,6 @@ public: } private: - /* - * The base class of all other node types. - */ class Node { friend class RadixStore; friend class RadixStoreTest; @@ -838,32 +833,32 @@ private: addNodeMemory(); } - Node(NodeType type, std::vector<uint8_t> key) { - _nodeType = type; + Node(std::vector<uint8_t> key) { _trieKey = key; addNodeMemory(); } Node(const Node& other) { - _nodeType = other._nodeType; - _numChildren = other._numChildren; - _depth = other._depth; _trieKey = other._trieKey; + _depth = other._depth; if (other._data) { - addData(other._data.value()); + addData(other._data); } + _children = other._children; + _numChildren = other._numChildren; // _refCount is initialized to 0 and not copied from other. addNodeMemory(); } - Node(Node&& other) - : _nodeType(other._nodeType), - _numChildren(other._numChildren), - _depth(other._depth), - _trieKey(std::move(other._trieKey)), - _data(std::move(other._data)) { + Node(Node&& other) { + _depth = other._depth; + _trieKey = std::move(other._trieKey); + _data = std::move(other._data); + _children = std::move(other._children); + _numChildren = other._numChildren; // _refCount is initialized to 0 and not copied from other. + // The move constructor transfers the dynamic memory so only the static memory of Node // should be added. addNodeMemory(-_trieKey.capacity() * sizeof(uint8_t)); @@ -895,354 +890,38 @@ private: } } - protected: - NodeType _nodeType; - uint16_t _numChildren = 0; - unsigned int _depth = 0; - std::vector<uint8_t> _trieKey; - boost::optional<value_type> _data; - AtomicWord<uint32_t> _refCount{0}; - - private: - bool needGrow() const { - switch (_nodeType) { - case NodeType::LEAF: - return true; - case NodeType::NODE4: - return numChildren() == 4; - case NodeType::NODE16: - return numChildren() == 16; - case NodeType::NODE48: - return numChildren() == 48; - case NodeType::NODE256: - return false; - } - MONGO_UNREACHABLE; - } - - bool needShrink() const { - switch (_nodeType) { - case NodeType::LEAF: - return false; - case NodeType::NODE4: - return numChildren() < 1; - case NodeType::NODE16: - return numChildren() < 5; - case NodeType::NODE48: - return numChildren() < 17; - case NodeType::NODE256: - return numChildren() < 49; - } - MONGO_UNREACHABLE; - } - - /* - * Only adds non-empty value and handle the increment on memory metrics. - */ - void addData(value_type value) { - _data.emplace(value.first, value.second); - _metrics.addMemory(value.first.capacity() + value.second.capacity()); - } - void addNodeMemory(difference_type offset = 0) { _metrics.totalMemory.fetchAndAdd(sizeof(Node) + _trieKey.capacity() * sizeof(uint8_t) + offset); _metrics.totalNodes.fetchAndAdd(1); + _metrics.totalChildren.fetchAndAdd(_children.size()); } void subtractNodeMemory() { + // Todo SERVER-36709: Vector capacity changes are ignored for now. This might be + // handled when nodes are made adaptive. size_t memUsage = sizeof(Node) + _trieKey.capacity() * sizeof(uint8_t); if (_data) { memUsage += _data->first.capacity() + _data->second.capacity(); } _metrics.totalMemory.fetchAndSubtract(memUsage); _metrics.totalNodes.fetchAndSubtract(1); - } - }; - - class Node4; - class Node16; - class Node48; - class Node256; - - class NodeLeaf : public Node { - friend class RadixStore; - - public: - NodeLeaf(std::vector<uint8_t> key) : Node(NodeType::LEAF, key) {} - NodeLeaf(const NodeLeaf& other) : Node(other) {} - - NodeLeaf(Node4&& other) : Node(std::move(other)) { - this->_nodeType = NodeType::LEAF; - } - }; - - /* - * Node4 is used when the number of children is in the range of [1, 4]. - */ - class Node4 : public Node { - friend class RadixStore; - - public: - Node4(std::vector<uint8_t> key) : Node(NodeType::NODE4, key) { - std::fill(_childKey.begin(), _childKey.end(), 0); - addNodeMemory(); - } - - Node4(const Node4& other) - : Node(other), _childKey(other._childKey), _children(other._children) { - addNodeMemory(); - } - - /* - * This move constructor should only be used when growing NodeLeaf to Node4. - */ - Node4(NodeLeaf&& other) : Node(std::move(other)) { - this->_nodeType = NodeType::NODE4; - std::fill(_childKey.begin(), _childKey.end(), 0); - addNodeMemory(); - } - - /* - * This move constructor should only be used when shrinking Node16 to Node4. - */ - Node4(Node16&& other) : Node(std::move(other)) { - invariant(other.needShrink()); - this->_nodeType = NodeType::NODE4; - std::fill(_childKey.begin(), _childKey.end(), 0); - for (size_t i = 0; i < other.numChildren(); ++i) { - _childKey[i] = other._childKey[i]; - _children[i] = std::move(other._children[i]); - } - addNodeMemory(); - } - - ~Node4() { - _metrics.subtractMemory(sizeof(Node4) - sizeof(Node)); - _metrics.totalChildren.fetchAndSubtract(_children.size()); - } - - private: - void addNodeMemory() { - _metrics.totalMemory.fetchAndAdd(sizeof(Node4) - sizeof(Node)); - _metrics.totalChildren.fetchAndAdd(_children.size()); - } - - // The first bytes of each child's key is stored in a sorted order. - std::array<uint8_t, 4> _childKey; - std::array<node_ptr, 4> _children; - }; - - /* - * Node16 is used when the number of children is in the range of [5, 16]. - */ - class Node16 : public Node { - friend class RadixStore; - - public: - Node16(std::vector<uint8_t> key) : Node(NodeType::NODE16, key) { - std::fill(_childKey.begin(), _childKey.end(), 0); - addNodeMemory(); - } - - Node16(const Node16& other) - : Node(other), _childKey(other._childKey), _children(other._children) { - addNodeMemory(); - } - - /* - * This move constructor should only be used when growing Node4 to Node16. - */ - Node16(Node4&& other) : Node(std::move(other)) { - invariant(other.needGrow()); - this->_nodeType = NodeType::NODE16; - auto n = other._childKey.size(); - for (size_t i = 0; i < n; ++i) { - _childKey[i] = other._childKey[i]; - _children[i] = std::move(other._children[i]); - } - std::fill(_childKey.begin() + n, _childKey.end(), 0); - addNodeMemory(); - } - - /* - * This move constructor should only be used when shrinking Node48 to Node16. - */ - Node16(Node48&& other) : Node(std::move(other)) { - invariant(other.needShrink()); - this->_nodeType = NodeType::NODE16; - std::fill(_childKey.begin(), _childKey.end(), 0); - size_t cur = 0; - for (size_t i = 0; i < other._childIndex.size(); ++i) { - auto index = other._childIndex[i]; - if (index != maxByte) { - _childKey[cur] = i; - _children[cur++] = std::move(other._children[index]); - } - } - addNodeMemory(); - } - - ~Node16() { - _metrics.subtractMemory(sizeof(Node16) - sizeof(Node)); _metrics.totalChildren.fetchAndSubtract(_children.size()); } - private: - void addNodeMemory() { - _metrics.totalMemory.fetchAndAdd(sizeof(Node16) - sizeof(Node)); - _metrics.totalChildren.fetchAndAdd(_children.size()); + void addData(boost::optional<value_type> value) { + _data.emplace(value->first, value->second); + _metrics.addMemory(value->first.capacity() + value->second.capacity()); } - // _childKey is sorted ascendingly. - std::array<uint8_t, 16> _childKey; - std::array<node_ptr, 16> _children; - }; - - /* - * Node48 is used when the number of children is in the range of [17, 48]. - */ - class Node48 : public Node { - friend class RadixStore; - - public: - Node48(std::vector<uint8_t> key) : Node(NodeType::NODE48, key) { - std::fill(_childIndex.begin(), _childIndex.end(), maxByte); - addNodeMemory(); - } - - Node48(const Node48& other) - : Node(other), _childIndex(other._childIndex), _children(other._children) { - addNodeMemory(); - } - - /* - * This move constructor should only be used when growing Node16 to Node48. - */ - Node48(Node16&& other) : Node(std::move(other)) { - invariant(other.needGrow()); - this->_nodeType = NodeType::NODE48; - std::fill(_childIndex.begin(), _childIndex.end(), maxByte); - for (uint8_t i = 0; i < other._children.size(); ++i) { - _childIndex[other._childKey[i]] = i; - _children[i] = std::move(other._children[i]); - } - addNodeMemory(); - } - - /* - * This move constructor should only be used when shrinking Node256 to Node48. - */ - Node48(Node256&& other) : Node(std::move(other)) { - invariant(other.needShrink()); - this->_nodeType = NodeType::NODE48; - std::fill(_childIndex.begin(), _childIndex.end(), maxByte); - size_t cur = 0; - for (size_t i = 0; i < other._children.size(); ++i) { - auto child = other._children[i]; - if (child) { - _childIndex[i] = cur; - _children[cur++] = child; - } - } - addNodeMemory(); - } - - ~Node48() { - _metrics.subtractMemory(sizeof(Node48) - sizeof(Node)); - _metrics.totalChildren.fetchAndSubtract(_children.size()); - } - - private: - void addNodeMemory() { - _metrics.totalMemory.fetchAndAdd(sizeof(Node48) - sizeof(Node)); - _metrics.totalChildren.fetchAndAdd(_children.size()); - } - - // A lookup table for child pointers. It has values from 0 to 48, where 0 - // represents empty, and all other index i maps to index i - 1 in _children. - std::array<uint8_t, 256> _childIndex; - std::array<node_ptr, 48> _children; - }; - - /* - * Node256 is used when the number of children is in the range of [49, 256]. - */ - class Node256 : public Node { - friend class RadixStore; - - public: - Node256() { - this->_nodeType = NodeType::NODE256; - addNodeMemory(); - } - - Node256(std::vector<uint8_t> key) : Node(NodeType::NODE256, key) { - addNodeMemory(); - } - - Node256(const NodeLeaf& other) : Node(other) { - addNodeMemory(); - } - - Node256(const Node4& other) : Node(other) { - this->_nodeType = NodeType::NODE256; - for (size_t i = 0; i < other.numChildren(); ++i) { - this->_children[other._childKey[i]] = other._children[i]; - } - addNodeMemory(); - } - - Node256(const Node16& other) : Node(other) { - this->_nodeType = NodeType::NODE256; - for (size_t i = 0; i < other.numChildren(); ++i) { - this->_children[other._childKey[i]] = other._children[i]; - } - addNodeMemory(); - } - - Node256(const Node48& other) : Node(other) { - this->_nodeType = NodeType::NODE256; - for (size_t i = 0; i < other._childIndex.size(); ++i) { - auto index = other._childIndex[i]; - if (index != maxByte) { - this->_children[i] = other._children[index]; - } - } - addNodeMemory(); - } - - Node256(const Node256& other) : Node(other), _children(other._children) { - addNodeMemory(); - } - - /* - * This move constructor should only be used when growing Node48 to Node256. - */ - Node256(Node48&& other) : Node(std::move(other)) { - invariant(other.needGrow()); - this->_nodeType = NodeType::NODE256; - for (size_t i = 0; i < other._childIndex.size(); ++i) { - auto index = other._childIndex[i]; - if (index != maxByte) { - _children[i] = std::move(other._children[index]); - } - } - addNodeMemory(); - } - - ~Node256() { - _metrics.subtractMemory(sizeof(Node256) - sizeof(Node)); - _metrics.totalChildren.fetchAndSubtract(_children.size()); - } - - private: - void addNodeMemory() { - _metrics.totalMemory.fetchAndAdd(sizeof(Node256) - sizeof(Node)); - _metrics.totalChildren.fetchAndAdd(_children.size()); - } - - std::array<node_ptr, 256> _children; + protected: + unsigned int _depth = 0; + std::vector<uint8_t> _trieKey; + boost::optional<value_type> _data; + std::array<boost::intrusive_ptr<Node>, 256> _children; + // TODO SERVER-36709: Updating to uint8_t after using adaptive nodes. + uint16_t _numChildren = 0; + AtomicWord<uint32_t> _refCount{0}; }; template <typename Node, typename... Args> @@ -1256,38 +935,34 @@ private: * be able to see when the tree is modified and to respond to these changes by ensuring they are * not iterating over stale trees. */ - class Head : public Node256 { + class Head : public Node { friend class RadixStore; public: Head() { - addNodeMemory(); + _metrics.addMemory(sizeof(Head) - sizeof(Node)); } - Head(std::vector<uint8_t> key) : Node256(key) { - addNodeMemory(); + Head(std::vector<uint8_t> key) : Node(key) { + _metrics.addMemory(sizeof(Head) - sizeof(Node)); } - Head(const Head& other) : Node256(other), _count(other._count), _dataSize(other._dataSize) { - addNodeMemory(); + Head(const Node& other) : Node(other) { + _metrics.addMemory(sizeof(Head) - sizeof(Node)); } - // Copy constructor template for the five node types. - template <typename NodeT> - Head(const NodeT& other) : Node256(other) { - addNodeMemory(); + Head(const Head& other) : Node(other), _count(other._count), _dataSize(other._dataSize) { + _metrics.addMemory(sizeof(Head) - sizeof(Node)); } ~Head() { if (_nextVersion) _nextVersion->_hasPreviousVersion = false; - _metrics.subtractMemory(sizeof(Head) - sizeof(Node256)); + _metrics.subtractMemory(sizeof(Head) - sizeof(Node)); } Head(Head&& other) - : Node256(std::move(other)), _count(other._count), _dataSize(other._dataSize) { - addNodeMemory(); - } + : Node(std::move(other)), _count(other._count), _dataSize(other._dataSize) {} bool hasPreviousVersion() const { return _hasPreviousVersion; @@ -1296,7 +971,7 @@ private: protected: // Forms a singly linked list of versions that is needed to reposition cursors after // modifications have been made. - head_ptr _nextVersion; + boost::intrusive_ptr<Head> _nextVersion; // While we have cursors that haven't been repositioned to the latest tree, this will be // true to help us understand when to copy on modifications due to the extra shared pointer @@ -1304,10 +979,6 @@ private: bool _hasPreviousVersion = false; private: - void addNodeMemory() { - _metrics.totalMemory.fetchAndAdd(sizeof(Head) - sizeof(Node256)); - } - size_type _count = 0; size_type _dataSize = 0; }; @@ -1337,160 +1008,12 @@ private: } ret.push_back('\n'); - _forEachChild(node, 0, false, [this, &ret, depth](node_ptr child) { - ret.append(_walkTree(child.get(), depth + 1)); - return true; - }); - return ret; - } - - /* - * Helper function to iterate through _children array for different node types and execute the - * given function on each child. The given function returns false when it intends to break the - * iteration. - * Returns false when the given function returns false on an element. Returns true - * when the end of the array is reached. - */ - static bool _forEachChild(Node* node, - uint16_t startKey, - bool reverse, - const std::function<bool(node_ptr)>& func) { - if (startKey > maxByte || !node->_numChildren) { - return true; - } - // Sets the step depending on the direction of iteration. - int16_t step = reverse ? -1 : 1; - switch (node->_nodeType) { - case NodeType::LEAF: - return true; - case NodeType::NODE4: { - Node4* node4 = static_cast<Node4*>(node); - // Locates the actual starting position first. - auto first = node4->_childKey.begin(); - auto numChildren = node4->numChildren(); - auto pos = std::find_if(first, first + numChildren, [&startKey](uint8_t keyByte) { - return keyByte >= startKey; - }); - if (reverse) { - if (pos == first && *pos != startKey) { - return true; - } - if (pos == first + numChildren || *pos != startKey) { - --pos; - } - } - - // No qualified elements. - if (pos == first + numChildren) { - return true; - } - - auto end = reverse ? -1 : numChildren; - for (auto cur = pos - first; cur != end; cur += step) { - // All children within the range will not be null since they are stored - // consecutively. - if (!func(node4->_children[cur])) { - // Breaks the loop if the given function decides to. - return false; - } - } - return true; - } - case NodeType::NODE16: { - Node16* node16 = static_cast<Node16*>(node); - // Locates the actual starting position first. - auto first = node16->_childKey.begin(); - auto numChildren = node16->numChildren(); - auto pos = std::find_if(first, first + numChildren, [&startKey](uint8_t keyByte) { - return keyByte >= startKey; - }); - if (reverse) { - if (pos == first && *pos != startKey) { - return true; - } - if (pos == first + numChildren || *pos != startKey) { - --pos; - } - } - - // No qualified elements. - if (pos == first + numChildren) { - return true; - } - - int16_t end = reverse ? -1 : numChildren; - for (auto cur = pos - first; cur != end; cur += step) { - // All children within the range will not be null since they are stored - // consecutively. - if (!func(node16->_children[cur])) { - return false; - } - } - return true; - } - case NodeType::NODE48: { - Node48* node48 = static_cast<Node48*>(node); - size_t end = reverse ? -1 : node48->_childIndex.size(); - for (size_t cur = startKey; cur != end; cur += step) { - auto index = node48->_childIndex[cur]; - if (index != maxByte && !func(node48->_children[index])) { - return false; - } - } - return true; - } - case NodeType::NODE256: { - Node256* node256 = static_cast<Node256*>(node); - size_t end = reverse ? -1 : node256->_children.size(); - for (size_t cur = startKey; cur != end; cur += step) { - auto child = node256->_children[cur]; - if (child && !func(child)) { - return false; - } - } - return true; - } - } - MONGO_UNREACHABLE; - } - - /* - * Gets the child mapped by the key for different node types. Node4 just does a simple linear - * search. Node16 uses binary search. Node48 does one extra lookup with the index table. Node256 - * has direct mapping. - */ - static node_ptr _findChild(const Node* node, uint8_t key) { - switch (node->_nodeType) { - case NodeType::LEAF: - return node_ptr(nullptr); - case NodeType::NODE4: { - const Node4* node4 = static_cast<const Node4*>(node); - auto start = node4->_childKey.begin(); - auto end = start + node4->numChildren(); - auto pos = std::find(start, end, key); - return pos != end ? node4->_children[pos - start] : node_ptr(nullptr); - } - case NodeType::NODE16: { - const Node16* node16 = static_cast<const Node16*>(node); - auto start = node16->_childKey.begin(); - auto end = start + node16->numChildren(); - auto pos = std::find(start, end, key); - return pos != end ? node16->_children[pos - start] : node_ptr(nullptr); - } - case NodeType::NODE48: { - const Node48* node48 = static_cast<const Node48*>(node); - auto index = node48->_childIndex[key]; - if (index != maxByte) { - return node48->_children[index]; - } - return node_ptr(nullptr); - } - case NodeType::NODE256: { - const Node256* node256 = static_cast<const Node256*>(node); - return node256->_children[key]; + for (auto child : node->_children) { + if (child != nullptr) { + ret.append(_walkTree(child.get(), depth + 1)); } } - MONGO_UNREACHABLE; + return ret; } Node* _findNode(const Key& key) const { @@ -1515,7 +1038,7 @@ private: depth = _root->_depth + _root->_trieKey.size(); uint8_t childFirstChar = charKey[depth]; - auto node = _findChild(_root.get(), childFirstChar); + auto node = _root->_children[childFirstChar]; while (node != nullptr) { @@ -1532,7 +1055,7 @@ private: depth = node->_depth + node->_trieKey.size(); childFirstChar = charKey[depth]; - node = _findChild(node.get(), childFirstChar); + node = node->_children[childFirstChar]; } return nullptr; @@ -1563,78 +1086,6 @@ private: _root->_hasPreviousVersion = true; } - /* - * Moves a smaller node's contents to a larger one. The method should only be called when the - * node is full. - */ - node_ptr _grow(Node* parent, Node* node) { - invariant(node->_nodeType != NodeType::NODE256); - auto key = node->_trieKey.front(); - switch (node->_nodeType) { - case NodeType::NODE256: - return nullptr; - case NodeType::LEAF: { - NodeLeaf* leaf = static_cast<NodeLeaf*>(node); - auto newNode = make_intrusive_node<Node4>(std::move(*leaf)); - _setChildPtr(parent, key, newNode); - return newNode; - } - case NodeType::NODE4: { - Node4* node4 = static_cast<Node4*>(node); - auto newNode = make_intrusive_node<Node16>(std::move(*node4)); - _setChildPtr(parent, key, newNode); - return newNode; - } - case NodeType::NODE16: { - Node16* node16 = static_cast<Node16*>(node); - auto newNode = make_intrusive_node<Node48>(std::move(*node16)); - _setChildPtr(parent, key, newNode); - return newNode; - } - case NodeType::NODE48: { - Node48* node48 = static_cast<Node48*>(node); - auto newNode = make_intrusive_node<Node256>(std::move(*node48)); - _setChildPtr(parent, key, newNode); - return newNode; - } - } - MONGO_UNREACHABLE; - } - - node_ptr _shrink(Node* parent, Node* node) { - invariant(node->_nodeType != NodeType::LEAF); - auto key = node->_trieKey.front(); - switch (node->_nodeType) { - case NodeType::LEAF: - return nullptr; - case NodeType::NODE4: { - Node4* node4 = static_cast<Node4*>(node); - auto newNode = make_intrusive_node<NodeLeaf>(std::move(*node4)); - _setChildPtr(parent, key, newNode); - return newNode; - } - case NodeType::NODE16: { - Node16* node16 = static_cast<Node16*>(node); - auto newNode = make_intrusive_node<Node4>(std::move(*node16)); - _setChildPtr(parent, key, newNode); - return newNode; - } - case NodeType::NODE48: { - Node48* node48 = static_cast<Node48*>(node); - auto newNode = make_intrusive_node<Node16>(std::move(*node48)); - _setChildPtr(parent, key, newNode); - return newNode; - } - case NodeType::NODE256: { - Node256* node256 = static_cast<Node256*>(node); - auto newNode = make_intrusive_node<Node48>(std::move(*node256)); - _setChildPtr(parent, key, newNode); - return newNode; - } - } - MONGO_UNREACHABLE; - } - /** * _upsertWithCopyOnSharedNodes is a helper function to help manage copy on modification for the * tree. This function follows the path for the to-be modified node using the keystring. If at @@ -1655,14 +1106,13 @@ private: _makeRootUnique(); - Node* prevParent = nullptr; Node* prev = _root.get(); - node_ptr node = _findChild(prev, childFirstChar); + boost::intrusive_ptr<Node> node = prev->_children[childFirstChar]; while (node != nullptr) { if (node->refCount() - 1 > 1) { // Copy node on a modifying operation when it isn't owned uniquely. - node = _copyNode(node.get()); - _setChildPtr(prev, childFirstChar, node); + node = make_intrusive_node<Node>(*node); + prev->_children[childFirstChar] = node; } // 'node' is uniquely owned at this point, so we are free to modify it. @@ -1676,7 +1126,8 @@ private: // Make a new node with whatever prefix is shared between node->_trieKey // and the new key. This will replace the current node in the tree. std::vector<uint8_t> newKey = _makeKey(node->_trieKey, 0, mismatchIdx); - Node* newNode = _addChild(prev, newKey, boost::none, NodeType::NODE4); + Node* newNode = _addChild(prev, newKey, boost::none); + depth += mismatchIdx; const_iterator it(_root, newNode); if (key.size() - depth != 0) { @@ -1687,14 +1138,15 @@ private: } else { // The new key is a prefix of an existing key, and has its own node, so we don't // need to add any new nodes. - newNode->addData(value.value()); + newNode->addData(value); } _root->_count++; _root->_dataSize += value->second.size(); // Change the current node's trieKey and make a child of the new node. newKey = _makeKey(node->_trieKey, mismatchIdx, node->_trieKey.size() - mismatchIdx); - _setChildPtr(newNode, newKey.front(), node); + newNode->_children[newKey.front()] = node; + ++newNode->_numChildren; // Handle key size change to the new key. _metrics.subtractMemory(sizeof(uint8_t) * @@ -1715,14 +1167,11 @@ private: // Update an internal node. if (!value) { data = boost::none; - auto keyByte = node->_trieKey.front(); - if (_compressOnlyChild(prev, node.get())) { - node = _findChild(prev, keyByte); - } + _compressOnlyChild(node.get()); } else { _root->_count++; _root->_dataSize += value->second.size(); - node->addData(value.value()); + node->addData(value); } const_iterator it(_root, node.get()); @@ -1732,17 +1181,13 @@ private: depth = node->_depth + node->_trieKey.size(); childFirstChar = charKey[depth]; - prevParent = prev; prev = node.get(); - node = _findChild(node.get(), childFirstChar); + node = node->_children[childFirstChar]; } // Add a completely new child to a node. The new key at this depth does not // share a prefix with any existing keys. std::vector<uint8_t> newKey = _makeKey(charKey + depth, key.size() - depth); - if (prev->needGrow()) { - prev = _grow(prevParent, prev).get(); - } Node* newNode = _addChild(prev, newKey, value); _root->_count++; _root->_dataSize += value->second.size(); @@ -1775,193 +1220,23 @@ private: return key; } - /* - * Wraps around the copy constructor for different node types. - */ - node_ptr _copyNode(Node* node) { - switch (node->_nodeType) { - case NodeType::LEAF: { - NodeLeaf* leaf = static_cast<NodeLeaf*>(node); - return make_intrusive_node<NodeLeaf>(*leaf); - } - case NodeType::NODE4: { - Node4* node4 = static_cast<Node4*>(node); - return make_intrusive_node<Node4>(*node4); - } - case NodeType::NODE16: { - Node16* node16 = static_cast<Node16*>(node); - return make_intrusive_node<Node16>(*node16); - } - case NodeType::NODE48: { - Node48* node48 = static_cast<Node48*>(node); - return make_intrusive_node<Node48>(*node48); - } - case NodeType::NODE256: { - Node256* node256 = static_cast<Node256*>(node); - return make_intrusive_node<Node256>(*node256); - } - } - MONGO_UNREACHABLE; - } - - head_ptr _makeHead(Node* node) { - switch (node->_nodeType) { - case NodeType::LEAF: { - NodeLeaf* leaf = static_cast<NodeLeaf*>(node); - return make_intrusive_node<Head>(*leaf); - } - case NodeType::NODE4: { - Node4* node4 = static_cast<Node4*>(node); - return make_intrusive_node<Head>(*node4); - } - case NodeType::NODE16: { - Node16* node16 = static_cast<Node16*>(node); - return make_intrusive_node<Head>(*node16); - } - case NodeType::NODE48: { - Node48* node48 = static_cast<Node48*>(node); - return make_intrusive_node<Head>(*node48); - } - case NodeType::NODE256: { - Node256* node256 = static_cast<Node256*>(node); - return make_intrusive_node<Head>(*node256); - } - } - MONGO_UNREACHABLE; - } - /** - * Add a child with trieKey 'key' and value 'value' to 'node'. The new child node created should - * only be the type NodeLeaf or Node4. + * Add a child with trieKey 'key' and value 'value' to 'node'. */ - Node* _addChild(Node* node, - std::vector<uint8_t> key, - boost::optional<value_type> value, - NodeType childType = NodeType::LEAF) { - invariant(childType == NodeType::LEAF || childType == NodeType::NODE4); - node_ptr newNode; - if (childType == NodeType::LEAF) { - newNode = make_intrusive_node<NodeLeaf>(key); - } else if (childType == NodeType::NODE4) { - newNode = make_intrusive_node<Node4>(key); - } + Node* _addChild(Node* node, std::vector<uint8_t> key, boost::optional<value_type> value) { + + boost::intrusive_ptr<Node> newNode = make_intrusive_node<Node>(key); newNode->_depth = node->_depth + node->_trieKey.size(); if (value) { - newNode->addData(value.value()); + newNode->addData(value); } - auto newNodeRaw = newNode.get(); - _setChildPtr(node, key.front(), std::move(newNode)); - return newNodeRaw; - } - - /* - * Inserts, updates, or deletes a child node at index and then maintains the key and children - * array for Node4 and Node16 in _setChildPtr(). - */ - template <class Node4Or16> - bool _setChildAtIndex(Node4Or16* node, node_ptr child, uint8_t key, size_t index) { - // Adds to the end of the array. - if (!node->_childKey[index] && !node->_children[index]) { - node->_childKey[index] = key; - node->_children[index] = child; + auto& child = node->_children[key.front()]; + if (!child) { + // Only increment the number of children if the node didn't have one at the position. ++node->_numChildren; - return true; - } - if (node->_childKey[index] == key) { - if (!child) { - // Deletes a child and shifts - auto n = node->numChildren(); - for (int j = index; j < n - 1; ++j) { - node->_childKey[j] = node->_childKey[j + 1]; - node->_children[j] = node->_children[j + 1]; - } - node->_childKey[n - 1] = 0; - node->_children[n - 1] = nullptr; - --node->_numChildren; - return true; - } - node->_children[index] = child; - return true; - } - if (node->_childKey[index] > key) { - // _children is guaranteed not to be full. - // Inserts to 'index' and shift larger keys to the right. - for (size_t j = node->numChildren(); j > index; --j) { - node->_childKey[j] = node->_childKey[j - 1]; - node->_children[j] = node->_children[j - 1]; - } - node->_childKey[index] = key; - node->_children[index] = child; - ++node->_numChildren; - return true; - } - return false; - } - - /* - * Sets the child pointer of 'key' to the 'newNode' in 'node'. - */ - void _setChildPtr(Node* node, uint8_t key, node_ptr newNode) { - switch (node->_nodeType) { - case NodeType::LEAF: - return; - case NodeType::NODE4: { - Node4* node4 = static_cast<Node4*>(node); - auto start = node4->_childKey.begin(); - // Find the position of the first larger or equal key to insert. - auto pos = std::find_if(start, - start + node4->numChildren(), - [&key](uint8_t keyByte) { return keyByte >= key; }); - _setChildAtIndex(node4, newNode, key, pos - start); - return; - } - case NodeType::NODE16: { - Node16* node16 = static_cast<Node16*>(node); - auto start = node16->_childKey.begin(); - auto pos = std::find_if(start, - start + node16->numChildren(), - [&key](uint8_t keyByte) { return keyByte >= key; }); - _setChildAtIndex(node16, newNode, key, pos - start); - return; - } - case NodeType::NODE48: { - Node48* node48 = static_cast<Node48*>(node); - auto index = node48->_childIndex[key]; - if (index != maxByte) { - // Pointer already exists. Delete or update it. - if (!newNode) { - node48->_childIndex[key] = maxByte; - --node48->_numChildren; - } - node48->_children[index] = newNode; - return; - } else { - // Finds the first empty slot to insert the newNode. - for (size_t i = 0; i < node48->_children.size(); ++i) { - auto& child = node48->_children[i]; - if (!child) { - child = newNode; - node48->_childIndex[key] = i; - ++node48->_numChildren; - return; - } - } - } - return; - } - case NodeType::NODE256: { - Node256* node256 = static_cast<Node256*>(node); - auto& child = node256->_children[key]; - if (!child) { - ++node256->_numChildren; - } else if (!newNode) { - --node256->_numChildren; - } - child = newNode; - return; - } } - MONGO_UNREACHABLE; + child = newNode; + return newNode.get(); } /** @@ -1980,7 +1255,8 @@ private: size_t depth = node->_depth + node->_trieKey.size(); while (depth < key.size()) { - node = _findChild(node, charKey[depth]).get(); + uint8_t c = charKey[depth]; + node = node->_children[c].get(); context.push_back(node); depth = node->_depth + node->_trieKey.size(); } @@ -2009,41 +1285,34 @@ private: * in a node with no value and only one child. * Returns true if compression occurred and false otherwise. */ - Node* _compressOnlyChild(Node* parent, Node* node) { - // Don't compress if this node is not of type Node4, has an actual value associated with it, + bool _compressOnlyChild(Node* node) { + // Don't compress if this node has an actual value associated with it or is the root // or doesn't have only one child. - if (node->_nodeType != NodeType::NODE4 || node->_data || node->_trieKey.empty() || - node->numChildren() != 1) { - return nullptr; + if (node->_data || node->_trieKey.empty() || node->numChildren() != 1) { + return false; } - Node4* node4 = static_cast<Node4*>(node); - node_ptr onlyChild = std::move(node4->_children[0]); - node4->_childKey[0] = 0; - node4->_numChildren = 0; - auto oldCapacity = node4->_trieKey.capacity(); + // Determine if this node has only one child. + boost::intrusive_ptr<Node> onlyChild = nullptr; - for (char item : onlyChild->_trieKey) { - node4->_trieKey.push_back(item); - } - _metrics.addMemory(sizeof(uint8_t) * (node4->_trieKey.capacity() - oldCapacity)); - if (onlyChild->_data) { - node4->addData(onlyChild->_data.value()); - } - _forEachChild(onlyChild.get(), 0, false, [this, &parent, &node](node_ptr child) { - if (node->needGrow()) { - node = _grow(parent, node).get(); + for (size_t i = 0; i < node->_children.size(); ++i) { + if (node->_children[i] != nullptr) { + onlyChild = node->_children[i]; + break; } - auto keyByte = child->_trieKey.front(); - _setChildPtr(node, keyByte, std::move(child)); - return true; - }); + } - if (node->needShrink()) { - node = _shrink(parent, node).get(); + // Append the child's key onto the parent. + for (char item : onlyChild->_trieKey) { + node->_trieKey.push_back(item); } - return node; + if (onlyChild->_data) { + node->addData(onlyChild->_data); + } + node->_children = onlyChild->_children; + node->_numChildren = onlyChild->_numChildren; + return true; } /** @@ -2056,7 +1325,7 @@ private: context[0] = replaceNode; for (size_t node = 1; node < context.size(); node++) { - replaceNode = _findChild(replaceNode, trieKeyIndex[node - 1]).get(); + replaceNode = replaceNode->_children[trieKeyIndex[node - 1]].get(); context[node] = replaceNode; } } @@ -2081,14 +1350,13 @@ private: for (size_t idx = 1; idx < context.size(); idx++) { node = context[idx]; - auto next = _findChild(prev, node->_trieKey.front()); - if (next->refCount() - 1 > 1) { - node_ptr nodeCopy = _copyNode(node); - _setChildPtr(prev, nodeCopy->_trieKey.front(), nodeCopy); + if (prev->_children[node->_trieKey.front()]->refCount() > 1) { + boost::intrusive_ptr<Node> nodeCopy = make_intrusive_node<Node>(*node); + prev->_children[nodeCopy->_trieKey.front()] = nodeCopy; context[idx] = nodeCopy.get(); prev = nodeCopy.get(); } else { - prev = next.get(); + prev = prev->_children[node->_trieKey.front()].get(); } } @@ -2099,14 +1367,14 @@ private: * Resolves conflicts within subtrees due to the complicated structure of path-compressed radix * tries. */ - void _mergeResolveConflict(Node* current, Node* baseNode, Node* otherNode) { + void _mergeResolveConflict(const Node* current, const Node* baseNode, const Node* otherNode) { // Merges all differences between this and other, using base to determine whether operations // are allowed or should throw a merge conflict. RadixStore base, other, node; - node._root = _makeHead(current); - base._root = _makeHead(baseNode); - other._root = _makeHead(otherNode); + node._root = make_intrusive_node<Head>(*current); + base._root = make_intrusive_node<Head>(*baseNode); + other._root = make_intrusive_node<Head>(*otherNode); // Merges insertions and updates from the master tree into the working tree, if possible. for (const value_type otherVal : other) { @@ -2169,11 +1437,11 @@ private: * Merges elements from the master tree into the working copy if they have no presence in the * working copy, otherwise we throw a merge conflict. */ - void _mergeTwoBranches(Node* current, Node* otherNode) { + void _mergeTwoBranches(const Node* current, const Node* otherNode) { RadixStore other, node; - node._root = _makeHead(current); - other._root = _makeHead(otherNode); + node._root = make_intrusive_node<Head>(*current); + other._root = make_intrusive_node<Head>(*otherNode); for (const value_type otherVal : other) { RadixStore::const_iterator thisIter = node.find(otherVal.first); @@ -2221,21 +1489,22 @@ private: auto key = current->_trieKey.front(); auto newTrieKeyBegin = current->_trieKey.begin(); auto newTrieKeyEnd = current->_trieKey.begin() + mismatchIdx; - auto shared_current = std::move(_findChild(parent, key)); + auto shared_current = std::move(parent->_children[key]); + --parent->_numChildren; auto newTrieKey = std::vector<uint8_t>(newTrieKeyBegin, newTrieKeyEnd); // Replace current with a new node with no data - auto newNode = _addChild(parent, newTrieKey, boost::none, NodeType::NODE4); + auto newNode = _addChild(parent, newTrieKey, boost::none); // Remove the part of the trieKey that is used by the new node. current->_trieKey.erase(current->_trieKey.begin(), current->_trieKey.begin() + mismatchIdx); - _metrics.subtractMemory(sizeof(uint8_t) * mismatchIdx); current->_depth += mismatchIdx; // Add what was the current node as a child to the new internal node key = current->_trieKey.front(); - _setChildPtr(newNode, key, std::move(shared_current)); + newNode->_children[key] = std::move(shared_current); + newNode->_numChildren = 1; // Update current pointer and context child = current; @@ -2249,9 +1518,9 @@ private: // Since _makeBranchUnique may make changes to the pointer addresses in recursive calls. current = context.back(); - Node* node = _findChild(current, key).get(); - Node* baseNode = _findChild(base, key).get(); - Node* otherNode = _findChild(other, key).get(); + Node* node = current->_children[key].get(); + Node* baseNode = base->_children[key].get(); + Node* otherNode = other->_children[key].get(); if (!node && !baseNode && !otherNode) continue; @@ -2266,14 +1535,12 @@ private: // merge in the other's branch. current = _makeBranchUnique(context); - if (current->needGrow()) { - current = _grow(context.at(context.size() - 2), current).get(); - } - // Need to rebuild our context to have updated pointers due to the // modifications that go on in _makeBranchUnique. _rebuildContext(context, trieKeyIndex); - _setChildPtr(current, key, _findChild(other, key)); + + current->_children[key] = other->_children[key]; + ++current->_numChildren; } else if (!otherNode || (baseNode && baseNode != otherNode)) { // Either the master tree and working tree remove the same branch, or the master // tree updated the branch while the working tree removed the branch, resulting @@ -2285,23 +1552,18 @@ private: node = splitCurrentBeforeWriteIfNeeded(node); // Other has a deleted branch that must also be removed from current tree. + current = _makeBranchUnique(context); - int prevIdx = context.size() - 2; - _setChildPtr(current, key, nullptr); - if (prevIdx >= 0 && current->needShrink()) { - current = _shrink(context.at(prevIdx), current).get(); - } _rebuildContext(context, trieKeyIndex); + current->_children[key] = nullptr; + --current->_numChildren; } else if (baseNode && otherNode && baseNode == node) { node = splitCurrentBeforeWriteIfNeeded(node); // If base and current point to the same node, then master changed. current = _makeBranchUnique(context); - if (current->needGrow()) { - current = _grow(context.at(context.size() - 2), current).get(); - } _rebuildContext(context, trieKeyIndex); - _setChildPtr(current, key, _findChild(other, key)); + current->_children[key] = other->_children[key]; } } else if (baseNode && otherNode && baseNode != otherNode) { // If all three are unique and leaf nodes with different data, then it is a merge @@ -2317,7 +1579,7 @@ private: // Only other changed the data. Take that node current = _makeBranchUnique(context); _rebuildContext(context, trieKeyIndex); - _setChildPtr(current, key, _findChild(other, key)); + current->_children[key] = other->_children[key]; } continue; } @@ -2343,27 +1605,15 @@ private: // Drop if leaf node without data, that is not valid. Otherwise we might // need to compress if we have only one child. if (node->isLeaf()) { - _setChildPtr(current, key, nullptr); - int prevIdx = context.size() - 2; - // Don't shrink the root node. - if (prevIdx >= 0 && current->needShrink()) { - current = _shrink(context.at(prevIdx), current).get(); - } - _rebuildContext(context, trieKeyIndex); + current->_children[key] = nullptr; + --current->_numChildren; } else { - if (auto compressedNode = _compressOnlyChild(current, node)) { - node = compressedNode; - } + _compressOnlyChild(node); } } } if (resolveConflict) { - auto curParent = context.size() > 1 ? context.at(context.size() - 2) : nullptr; - Node* nodeToResolve = node; - if (auto compressed = _compressOnlyChild(curParent, current)) { - current = compressed; - nodeToResolve = current; - } + Node* nodeToResolve = _compressOnlyChild(current) ? current : node; _mergeResolveConflict(nodeToResolve, baseNode, otherNode); _rebuildContext(context, trieKeyIndex); // If we compressed above, resolving the conflict can result in erasing current. @@ -2400,15 +1650,17 @@ private: Node* _begin(Node* root) const noexcept { Node* node = root; while (!node->_data) { - _forEachChild(node, 0, false, [&node](node_ptr child) { - node = child.get(); - return false; - }); + for (auto child : node->_children) { + if (child != nullptr) { + node = child.get(); + break; + } + } } return node; } - head_ptr _root = nullptr; + boost::intrusive_ptr<Head> _root = nullptr; static Metrics _metrics; }; diff --git a/src/mongo/db/storage/ephemeral_for_test/ephemeral_for_test_radix_store_test.cpp b/src/mongo/db/storage/ephemeral_for_test/ephemeral_for_test_radix_store_test.cpp index 46b16109d96..1dfe224f020 100644 --- a/src/mongo/db/storage/ephemeral_for_test/ephemeral_for_test_radix_store_test.cpp +++ b/src/mongo/db/storage/ephemeral_for_test/ephemeral_for_test_radix_store_test.cpp @@ -81,17 +81,18 @@ public: /** * Returns all nodes in "store" with level order traversal. */ - std::vector<node_type*> allNodes(StringStore& store) const { - std::deque<node_type*> level(1, store._root.get()); - std::vector<node_type*> result(1, store._root.get()); + std::vector<boost::intrusive_ptr<node_type>> allNodes(StringStore& store) const { + std::deque<boost::intrusive_ptr<node_type>> level(1, store._root); + std::vector<boost::intrusive_ptr<node_type>> result(1, store._root); while (!level.empty()) { - auto node = level.front(); - StringStore::_forEachChild( - node, 0, false, [&level, &result](boost::intrusive_ptr<node_type> child) { - level.push_back(child.get()); - result.push_back(child.get()); - return true; - }); + auto node = level.front().get(); + for (int i = 0; i < 256; ++i) { + auto child = node->_children[i]; + if (child.get()) { + level.push_back(child); + result.push_back(child); + } + } level.pop_front(); } return result; @@ -104,21 +105,16 @@ public: auto nodes = allNodes(store); for (const auto& node : nodes) { uint16_t numChildren = 0; - StringStore::_forEachChild( - node, 0, false, [&numChildren](boost::intrusive_ptr<node_type> child) { + auto children = node.get()->_children; + for (uint16_t i = 0; i < children.size(); ++i) { + if (children[i]) { ++numChildren; - return true; - }); - ASSERT_EQ(numChildren, node->numChildren()); + } + } + ASSERT_EQ(numChildren, node.get()->numChildren()); } } - void debug(StringStore& store) const { - std::cout << "Memory: " << store._metrics.totalMemory.load() << std::endl - << "Nodes: " << store._metrics.totalNodes.load() << std::endl - << "Children: " << store._metrics.totalChildren.load() << std::endl; - } - protected: StringStore thisStore; StringStore parallelStore; @@ -2111,139 +2107,20 @@ TEST_F(RadixStoreTest, BasicInsertFindDeleteNullCharacter) { ASSERT_EQ(iter->first, value2.first); } -TEST_F(RadixStoreTest, IteratorTest) { - uint8_t keyArr[] = {97, 0, 0}; - int v = 0; - int cur = v; - - // Node4 - for (size_t i = 0; i < 4; ++i) { - ++keyArr[1]; - std::string keyStr(reinterpret_cast<char*>(keyArr)); - value_type value = std::make_pair(keyStr, std::to_string(++v)); - - thisStore.insert(value_type(value)); - } - - cur = 0; - for (auto iter = thisStore.begin(); iter != thisStore.end(); ++iter) { - ++cur; - ASSERT_EQ(iter->second, std::to_string(cur)); - } - ASSERT_EQ(cur, v); - - // Node16 - for (size_t i = 0; i < 12; ++i) { - ++keyArr[1]; - std::string keyStr(reinterpret_cast<char*>(keyArr)); - value_type value = std::make_pair(keyStr, std::to_string(++v)); - - thisStore.insert(value_type(value)); - } - - cur = 0; - for (auto iter = thisStore.begin(); iter != thisStore.end(); ++iter) { - ++cur; - ASSERT_EQ(iter->second, std::to_string(cur)); - } - ASSERT_EQ(cur, v); - - // Node48 - for (size_t i = 0; i < 32; ++i) { - ++keyArr[1]; - std::string keyStr(reinterpret_cast<char*>(keyArr)); - value_type value = std::make_pair(keyStr, std::to_string(++v)); - - thisStore.insert(value_type(value)); - } - - cur = 0; - for (auto iter = thisStore.begin(); iter != thisStore.end(); ++iter) { - ++cur; - ASSERT_EQ(iter->second, std::to_string(cur)); - } - ASSERT_EQ(cur, v); - - // Node256 - for (size_t i = 0; i < 207; ++i) { - ++keyArr[1]; - std::string keyStr(reinterpret_cast<char*>(keyArr)); - value_type value = std::make_pair(keyStr, std::to_string(++v)); - - thisStore.insert(value_type(value)); - } - - cur = 0; - for (auto iter = thisStore.begin(); iter != thisStore.end(); ++iter) { - ++cur; - ASSERT_EQ(iter->second, std::to_string(cur)); - } - ASSERT_EQ(cur, v); -} - TEST_F(RadixStoreTest, ReverseIteratorTest) { - uint8_t keyArr[] = {97, 0, 0}; - int v = 0; - int cur = v; - - // Node4 - for (size_t i = 0; i < 4; ++i) { - ++keyArr[1]; - std::string keyStr(reinterpret_cast<char*>(keyArr)); - value_type value = std::make_pair(keyStr, std::to_string(++v)); - - thisStore.insert(value_type(value)); - } - - cur = v; - for (auto iter = thisStore.rbegin(); iter != thisStore.rend(); ++iter) { - ASSERT_EQ(iter->second, std::to_string(cur)); - --cur; - } - ASSERT_EQ(cur, 0); - - // Node16 - for (size_t i = 0; i < 12; ++i) { - ++keyArr[1]; - std::string keyStr(reinterpret_cast<char*>(keyArr)); - value_type value = std::make_pair(keyStr, std::to_string(++v)); - - thisStore.insert(value_type(value)); - } - - cur = v; - for (auto iter = thisStore.rbegin(); iter != thisStore.rend(); ++iter) { - ASSERT_EQ(iter->second, std::to_string(cur)); - --cur; - } - ASSERT_EQ(cur, 0); - - // Node48 - for (size_t i = 0; i < 32; ++i) { - ++keyArr[1]; - std::string keyStr(reinterpret_cast<char*>(keyArr)); - value_type value = std::make_pair(keyStr, std::to_string(++v)); - - thisStore.insert(value_type(value)); - } - - cur = v; - for (auto iter = thisStore.rbegin(); iter != thisStore.rend(); ++iter) { - ASSERT_EQ(iter->second, std::to_string(cur)); - --cur; - } - ASSERT_EQ(cur, 0); - - // Node256 - for (size_t i = 0; i < 207; ++i) { - ++keyArr[1]; - std::string keyStr(reinterpret_cast<char*>(keyArr)); - value_type value = std::make_pair(keyStr, std::to_string(++v)); + value_type value1 = std::make_pair("foo", "3"); + value_type value2 = std::make_pair("bar", "1"); + value_type value3 = std::make_pair("baz", "2"); + value_type value4 = std::make_pair("fools", "5"); + value_type value5 = std::make_pair("foods", "4"); - thisStore.insert(value_type(value)); - } + thisStore.insert(value_type(value4)); + thisStore.insert(value_type(value5)); + thisStore.insert(value_type(value1)); + thisStore.insert(value_type(value3)); + thisStore.insert(value_type(value2)); - cur = v; + int cur = 5; for (auto iter = thisStore.rbegin(); iter != thisStore.rend(); ++iter) { ASSERT_EQ(iter->second, std::to_string(cur)); --cur; @@ -2916,151 +2793,5 @@ TEST_F(RadixStoreTest, LowerBoundEndpoint) { ASSERT_TRUE(it == thisStore.end()); } -TEST_F(RadixStoreTest, SimpleGrowTest) { - std::pair<StringStore::const_iterator, bool> res; - uint8_t keyArr[] = {97, 0, 0}; - - for (size_t i = 0; i < 255; ++i) { - ++keyArr[1]; - std::string keyStr(reinterpret_cast<char*>(keyArr)); - value_type value = std::make_pair(keyStr, "1"); - - res = thisStore.insert(value_type(value)); - ASSERT_TRUE(res.second); - ASSERT_TRUE(*res.first == value); - } - - ASSERT_EQ(thisStore.size(), 255); -} - -TEST_F(RadixStoreTest, SimpleShrinkTest) { - uint8_t keyArr[] = {97, 0, 0}; - - for (size_t i = 0; i < 255; ++i) { - ++keyArr[1]; - std::string keyStr(reinterpret_cast<char*>(keyArr)); - value_type value = std::make_pair(keyStr, "1"); - - thisStore.insert(value_type(value)); - } - - for (size_t i = 0; i < 255; ++i) { - std::string keyStr(reinterpret_cast<char*>(keyArr)); - thisStore.erase(keyStr); - --keyArr[1]; - } - - ASSERT_EQ(thisStore.size(), 0); -} - -TEST_F(RadixStoreTest, UpdateGrowTest) { - std::pair<StringStore::const_iterator, bool> res; - uint8_t keyArr[] = {97, 0, 0}; - - for (size_t i = 0; i < 255; ++i) { - ++keyArr[1]; - std::string keyStr(reinterpret_cast<char*>(keyArr)); - value_type value = std::make_pair(keyStr, "1"); - - thisStore.insert(value_type(value)); - - value_type update = std::make_pair(keyStr, "2"); - res = thisStore.update(value_type(update)); - ASSERT_TRUE(res.second); - ASSERT_TRUE(*res.first == update); - } -} - -TEST_F(RadixStoreTest, MergeGrowOneTest) { - // !baseNode && otherNode - thisStore = baseStore; - - uint8_t keyArr[] = {97, 0, 0}; - for (size_t i = 0; i < 16; ++i) { - ++keyArr[1]; - std::string keyStr(reinterpret_cast<char*>(keyArr)); - value_type value = std::make_pair(keyStr, "1"); - thisStore.insert((value_type(value))); - } - - otherStore = baseStore; - auto keyArrOther = keyArr; - ++keyArrOther[1]; - std::string keyStr1(reinterpret_cast<char*>(keyArrOther)); - value_type value1 = std::make_pair(keyStr1, "1"); - otherStore.insert((value_type(value1))); - - thisStore.merge3(baseStore, otherStore); - - ASSERT_EQ(baseStore.size(), 0); - ASSERT_EQ(otherStore.size(), 1); - ASSERT_EQ(thisStore.size(), 17); - ASSERT_EQ(thisStore.dataSize(), 17); - - for (size_t i = 0; i < 31; ++i) { - ++keyArr[1]; - std::string keyStr(reinterpret_cast<char*>(keyArr)); - value_type value = std::make_pair(keyStr, "1"); - thisStore.insert((value_type(value))); - } - - otherStore = baseStore; - keyArrOther = keyArr; - ++keyArrOther[1]; - std::string keyStr2(reinterpret_cast<char*>(keyArrOther)); - value_type value2 = std::make_pair(keyStr2, "1"); - otherStore.insert((value_type(value2))); - - thisStore.merge3(baseStore, otherStore); - - ASSERT_EQ(baseStore.size(), 0); - ASSERT_EQ(otherStore.size(), 1); - ASSERT_EQ(thisStore.size(), 49); - ASSERT_EQ(thisStore.dataSize(), 49); -} - -TEST_F(RadixStoreTest, MergeGrowTwoTest) { - // !node && !baseNode && otherNode - value_type value1 = std::make_pair("a", "1"); - value_type value2 = std::make_pair("aa", "2"); - - baseStore.insert(value_type(value1)); - - thisStore = baseStore; - otherStore = baseStore; - - otherStore.insert(value_type(value2)); - - thisStore.merge3(baseStore, otherStore); - - ASSERT_EQ(baseStore.size(), 1); - ASSERT_EQ(otherStore.size(), 2); - ASSERT_EQ(thisStore.size(), 2); -} - -TEST_F(RadixStoreTest, MergeCompressTest) { - value_type value1 = std::make_pair("a", "1"); - value_type value2 = std::make_pair("aaa", "2"); - value_type value3 = std::make_pair("aab", "3"); - value_type value4 = std::make_pair("aac", "4"); - - baseStore.insert(value_type(value1)); - baseStore.insert(value_type(value2)); - baseStore.insert(value_type(value3)); - baseStore.insert(value_type(value4)); - - thisStore = baseStore; - otherStore = baseStore; - - thisStore.erase("aac"); - otherStore.erase("aab"); - - thisStore.merge3(baseStore, otherStore); - - ASSERT_EQ(baseStore.size(), 4); - ASSERT_EQ(otherStore.size(), 3); - ASSERT_EQ(thisStore.size(), 2); -} - } // namespace ephemeral_for_test } // namespace mongo |