diff options
| -rw-r--r-- | AK/IntrusiveRedBlackTree.h | 9 | ||||
| -rw-r--r-- | AK/RedBlackTree.h | 8 |
2 files changed, 17 insertions, 0 deletions
diff --git a/AK/IntrusiveRedBlackTree.h b/AK/IntrusiveRedBlackTree.h index 1a40804536..6b1442f1fc 100644 --- a/AK/IntrusiveRedBlackTree.h +++ b/AK/IntrusiveRedBlackTree.h @@ -55,6 +55,14 @@ public: return node_to_value(*node); } + Container find_smallest_not_below(K key) + { + auto* node = static_cast<TreeNode*>(BaseTree::find_smallest_not_below(this->m_root, key)); + if (!node) + return nullptr; + return node_to_value(*node); + } + void insert(K key, V& value) { auto& node = value.*member; @@ -208,6 +216,7 @@ class IntrusiveRedBlackTree<K, V, NonnullRefPtr<V>, member> : public IntrusiveRe public: [[nodiscard]] NonnullRefPtr<V> find(K key) const { return IntrusiveRedBlackTree<K, V, RefPtr<V>, member>::find(key).release_nonnull(); } [[nodiscard]] NonnullRefPtr<V> find_largest_not_above(K key) const { return IntrusiveRedBlackTree<K, V, RefPtr<V>, member>::find_largest_not_above(key).release_nonnull(); } + [[nodiscard]] NonnullRefPtr<V> find_smallest_not_below(K key) const { return IntrusiveRedBlackTree<K, V, RefPtr<V>, member>::find_smallest_not_below(key).release_nonnull(); } }; } diff --git a/AK/RedBlackTree.h b/AK/RedBlackTree.h index 11994bd4b4..8106b70d99 100644 --- a/AK/RedBlackTree.h +++ b/AK/RedBlackTree.h @@ -467,6 +467,14 @@ public: return &node->value; } + [[nodiscard]] V* find_smallest_not_below(K key) + { + auto* node = static_cast<Node*>(BaseTree::find_smallest_not_below(this->m_root, key)); + if (!node) + return nullptr; + return &node->value; + } + ErrorOr<void> try_insert(K key, V const& value) { return try_insert(key, V(value)); |