Index: uspace/lib/cpp/include/internal/rbtree.hpp =================================================================== --- uspace/lib/cpp/include/internal/rbtree.hpp (revision 4d6551509f8101bd33bdc0982410337c774372fc) +++ uspace/lib/cpp/include/internal/rbtree.hpp (revision 4d6551509f8101bd33bdc0982410337c774372fc) @@ -0,0 +1,310 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_INTERNAL_RBTREE +#define LIBCPP_INTERNAL_RBTREE + +#include +#include +#include +#include + +namespace std::aux +{ + template< + class Value, class Key, class KeyExtractor, + class KeyComp, class Alloc, class Size, + class Iterator, class ConstIterator, + class Policy + > + class rbtree + { + public: + using value_type = Value; + using key_type = Key; + using size_type = Size; + using allocator_type = Alloc; + using key_compare = KeyComp; + using key_extract = KeyExtractor; + + using iterator = Iterator; + using const_iterator = ConstIterator; + + using node_type = rbtree_node; + + rbtree(const key_compare& kcmp = key_compare{}) + : root_{nullptr}, size_{}, key_compare_{}, + key_extractor_{} + { /* DUMMY BODY */ } + + rbtree(const rbtree& other); + + rbtree(rbtree&& other); + + rbtree& operator=(const rbtree& other); + + rbtree& operator=(rbtree&& other); + + bool empty() const noexcept + { + return size_; + } + + size_type size() const noexcept + { + return size_; + } + + size_type max_size(allocator_type& alloc) + { + return allocator_traits::max_size(alloc); + } + + iterator begin() + { + return iterator{find_smallest_(), false}; + } + + const_iterator begin() const + { + return cbegin(); + } + + iterator end() + { + return iterator{find_largest_(), true}; + } + + const_iterator end() const + { + return cend(); + } + + const_iterator cbegin() const + { + return const_iterator{find_smallest_(), false}; + } + + const_iterator cend() const + { + return const_iterator{find_largest_(), true}; + } + + template + pair emplace(Args&&... args) + { + auto ret = Policy::emplace(*this, forward(args)...); + + return ret; + } + + pair insert(const value_type& val) + { + auto ret = Policy::insert(*this, val); + if (!ret.second) + return ret; + + repair_after_insert_(ret.first.node()); + update_root_(ret.first.node()); + + return ret; + } + + pair insert(value_type&& val) + { + auto ret = Policy::insert(*this, forward(val)); + if (!ret.second) + return ret; + + repair_after_insert_(ret.first.node()); + update_root_(ret.first.node()); + + return ret; + } + + size_type erase(const key_type& key) + { + auto ret = Policy::erase(*this, key); + if (ret == 0) + return ret; + // TODO: problem - we don't have a node ptr + // solution: return a pair + + return ret; + } + + iterator erase(const_iterator it) + { + // TODO: implement + } + + void clear() noexcept + { + if (root_) + { + delete root_; + root_ = nullptr; + size_ = size_type{}; + } + } + + void swap(rbtree& other) + noexcept(allocator_traits::is_always_equal::value && + noexcept(swap(declval(), declval()))) + { + std::swap(root_, other.root_); + std::swap(size_, other.size_); + std::swap(key_compare_, other.key_compare_); + std::swap(key_extractor_, other.key_extractor_); + } + + key_compare key_comp() const + { + return key_compare_; + } + + iterator find(const key_type& key) + { + // TODO: implement + } + + const_iterator find(const key_type&& key) const + { + // TODO: implement + } + + size_type count(const key_type& key) const + { + return Policy::count(*this, key); + } + + iterator upper_bound(const key_type& key) + { + return Policy::upper_bound(*this, key); + } + + const_iterator upper_bound(const key_type& key) const + { + return Policy::upper_bound_const(*this, key); + } + + iterator lower_bound(const key_type& key) + { + return Policy::lower_bound(*this, key); + } + + const_iterator lower_bound(const key_type& key) const + { + return Policy::lower_bound_const(*this, key); + } + + pair equal_range(const key_type& key) + { + return Policy::equal_range(*this, key); + } + + pair equal_range(const key_type& key) const + { + return Policy::equal_range_const(*this, key); + } + + bool is_eq_to(const rbtree& other) const + { + // TODO: implement + return false; + } + + const key_type& get_key(const value_type& val) const + { + return key_extractor_(val); + } + + bool keys_comp(const key_type& key, const value_type& val) const + { + return key_compare_(key, key_extractor_(val)); + } + + node_type* find_parent_for_insertion(const value_type& val) const + { + auto current = root_; + auto parent = current; + + while (current) + { + parent = current; + if (key_compare_(key_extractor_(val), key_extractor_(current->value))) + current = current->left; + else + current = current->right; + } + + return parent; + } + + private: + node_type* root_; + size_type size_; + key_compare key_compare_; + key_extract key_extractor_; + + node_type* find_smallest_() const + { + if (root_) + return root_->find_smallest(); + else + return nullptr; + } + + node_type* find_largest_() const + { + if (root_) + return root_->find_largest(); + else + return nullptr; + } + + void update_root_(node_type* node) + { + if (!node) + return; + + root_ = node; + while (root_->parent) + root_ = root_->parent; + } + + void repair_after_insert_(node_type* node) + { + // TODO: implement + } + + friend Policy; + }; +} + +#endif Index: uspace/lib/cpp/include/internal/rbtree_iterators.hpp =================================================================== --- uspace/lib/cpp/include/internal/rbtree_iterators.hpp (revision 4d6551509f8101bd33bdc0982410337c774372fc) +++ uspace/lib/cpp/include/internal/rbtree_iterators.hpp (revision 4d6551509f8101bd33bdc0982410337c774372fc) @@ -0,0 +1,374 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_INTERNAL_RBTREE_ITERATORS +#define LIBCPP_INTERNAL_RBTREE_ITERATORS + +#include +#include + +namespace std::aux +{ + /** + * Note: In order for these iterators to be reversible, + * the end state of an iterator is represented by a flag + * which can be set from true to false in operator-- + * (i.e. decrementing end iterator) or set from false to + * true in operator++ (i.e. incrementing last before end + * iterator). + */ + + template + class rbtree_const_iterator + { + public: + using value_type = Value; + using size_type = Size; + using const_reference = ConstReference; + using const_pointer = ConstPointer; + using difference_type = ptrdiff_t; + + using iterator_category = bidirectional_iterator_tag; + + rbtree_const_iterator(const rbtree_node* current = nullptr, bool end = true) + : current_{current}, end_{end} + { /* DUMMY BODY */ } + + rbtree_const_iterator(const rbtree_const_iterator&) = default; + rbtree_const_iterator& operator=(const rbtree_const_iterator&) = default; + + const_reference operator*() const + { + return current_->value; + } + + const_pointer operator->() const + { + return ¤t_->value; + } + + rbtree_const_iterator& operator++() + { + if (current_) + { + auto bckp = current_; + if (current_->right) + current_ = current_->right->find_smallest(); + else + { + while (!current_->is_left_child()) + { + current_ = current_->parent; + + if (!current_->parent) + { + /** + * We've gone back to root without + * being a left child, which means we + * were the last node. + */ + end_ = true; + current_ = bckp; + + return *this; + } + } + + /** + * Now we are a left child, + * so the next node we have to visit + * is our parent. + */ + current_ = current_->parent; + } + } + + return *this; + } + + rbtree_const_iterator operator++(int) + { + auto tmp = *this; + ++(*this); + + return tmp; + } + + rbtree_const_iterator& operator--() + { + if (end_) + { + try_undo_end_(); + + return *this; + } + + if (current_) + { + if (current_->left) + current_ = current_->left->find_largest(); + else if (current_->parent) + { + while (current_->is_left_child()) + current_ = current_->parent; + + /** + * We know parent exists here + * because we went up from the + * left and stopped being left + * child (if at any point we happened + * to become root then this branch + * wouldn't happen). + */ + current_ = current_->parent; + } + else // We are root without a left child. + current_ = nullptr; + } + + return *this; + } + + rbtree_const_iterator operator--(int) + { + auto tmp = *this; + --(*this); + + return tmp; + } + + const rbtree_node* node() const + { + return current_; + } + + bool end() const + { + return end_; + } + + private: + const rbtree_node* current_; + bool end_; + + void try_undo_end_() + { + if (!current_) + return; + + /** + * We can do this if we are past end(). + * This means we are the largest. + */ + if (current_->find_largest() == current_) + end_ = false; + } + }; + + template + bool operator==(const rbtree_const_iterator& lhs, + const rbtree_const_iterator& rhs) + { + return (lhs.node() == rhs.node()) && (lhs.end() == rhs.end()); + } + + template + bool operator!=(const rbtree_const_iterator& lhs, + const rbtree_const_iterator& rhs) + { + return !(lhs == rhs); + } + + template + class rbtree_iterator + { + public: + using value_type = Value; + using size_type = Size; + using reference = Reference; + using pointer = Pointer; + using difference_type = ptrdiff_t; + + using iterator_category = bidirectional_iterator_tag; + + rbtree_iterator(rbtree_node* current = nullptr, bool end = true) + : current_{current}, end_{end} + { /* DUMMY BODY */ } + + rbtree_iterator(const rbtree_iterator&) = default; + rbtree_iterator& operator=(const rbtree_iterator&) = default; + + reference operator*() const + { + return current_->value; + } + + pointer operator->() const + { + return ¤t_->value; + } + + rbtree_iterator& operator++() + { + if (current_) + { + auto bckp = current_; + if (current_->right) + current_ = current_->right->find_smallest(); + else + { + while (!current_->is_left_child()) + { + current_ = current_->parent; + + if (!current_ || !current_->parent) + { + /** + * We've gone back to root without + * being a left child, which means we + * were the last node. + */ + end_ = true; + current_ = bckp; + + return *this; + } + } + + /** + * Now we are a left child, + * so the next node we have to visit + * is our parent. + */ + current_ = current_->parent; + } + } + + return *this; + } + + rbtree_iterator operator++(int) + { + auto tmp = *this; + ++(*this); + + return tmp; + } + + rbtree_iterator& operator--() + { + if (end_) + { + try_undo_end_(); + + return *this; + } + + if (current_) + { + if (current_->left) + current_ = current_->left->find_largest(); + else if (current_->parent) + { + while (current_->is_left_child()) + current_ = current_->parent; + + /** + * We know parent exists here + * because we went up from the + * left and stopped being left + * child (if at any point we happened + * to become root then this branch + * wouldn't happen). + */ + current_ = current_->parent; + } + else // We are root without a left child. + end_ = true; + } + + return *this; + } + + rbtree_iterator operator--(int) + { + auto tmp = *this; + --(*this); + + return tmp; + } + + const rbtree_node* node() const + { + return current_; + } + + rbtree_node* node() + { + return current_; + } + + bool end() const + { + return end_; + } + + private: + rbtree_node* current_; + bool end_; + + void try_undo_end_() + { + if (!current_) + return; + + /** + * We can do this if we are past end(). + * This means we are the largest. + */ + if (current_->find_largest() == current_) + end_ = false; + } + }; + + template + bool operator==(const rbtree_iterator& lhs, + const rbtree_iterator& rhs) + { + return (lhs.node() == rhs.node()) && (lhs.end() == rhs.end()); + } + + template + bool operator!=(const rbtree_iterator& lhs, + const rbtree_iterator& rhs) + { + return !(lhs == rhs); + } +} + +#endif Index: uspace/lib/cpp/include/internal/rbtree_node.hpp =================================================================== --- uspace/lib/cpp/include/internal/rbtree_node.hpp (revision 4d6551509f8101bd33bdc0982410337c774372fc) +++ uspace/lib/cpp/include/internal/rbtree_node.hpp (revision 4d6551509f8101bd33bdc0982410337c774372fc) @@ -0,0 +1,150 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_INTERNAL_RBTREE_NODE +#define LIBCPP_INTERNAL_RBTREE_NODE + +namespace std::aux +{ + enum class rbcolor + { + red, black + }; + + template + struct rbtree_node + { + T value; + rbcolor color; + + rbtree_node* parent; + rbtree_node* left; + rbtree_node* right; + + template + rbtree_node(Args&&... args) + : value{forward(args)...}, color{rbcolor::red}, + parent{}, left{}, right{} + { /* DUMMY BODY */ } + + rbtree_node* grandparent() const + { + if (parent) + return parent->parent; + else + return nullptr; + } + + rbtree_node* brother() const + { + if (parent) + { + if (this == parent->left) + return parent->right; + else + return parent->left; + } + else + return nullptr; + } + + rbtree_node* uncle() const + { + if (grandparent()) + { + if (parent == grandparent()->left) + return grandparent()->right; + else + return grandparent()->left; + } + else + return nullptr; + } + + bool is_left_child() const + { + if (parent) + return parent->left == this; + else + return false; + } + + void rotate_left() + { + // TODO: + } + + void rotate_right() + { + // TODO: + } + + rbtree_node* find_smallest() + { + auto res = this; + while (res->left) + res = res->left; + + return res; + } + + rbtree_node* find_largest() + { + auto res = this; + while (res->right) + res = res->right; + + return res; + } + + void add_left_child(rbtree_node* node) + { + if (left) + return; + + left = node; + node->parent = this; + } + + void add_right_child(rbtree_node* node) + { + if (right) + return; + + right = node; + node->parent = this; + } + + ~rbtree_node() + { + // TODO: delete recursively or iteratively? + } + }; +} + +#endif Index: uspace/lib/cpp/include/internal/rbtree_policies.hpp =================================================================== --- uspace/lib/cpp/include/internal/rbtree_policies.hpp (revision 4d6551509f8101bd33bdc0982410337c774372fc) +++ uspace/lib/cpp/include/internal/rbtree_policies.hpp (revision 4d6551509f8101bd33bdc0982410337c774372fc) @@ -0,0 +1,105 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_INTERNAL_RBTREE_POLICIES +#define LIBCPP_INTERNAL_RBTREE_POLICIES + +#include +#include + +namespace std::aux +{ + struct rbtree_single_policy + { + // TODO: + + template + static pair< + typename Tree::iterator, bool + > insert(Tree& tree, const Value& val) + { + using iterator = typename Tree::iterator; + using node_type = typename Tree::node_type; + + auto parent = tree.find_parent_for_insertion(val); + if (!parent) + { + tree.root_ = new node_type{val}; + + return make_pair(iterator{tree.root_}, true); + } + + if (tree.get_key(parent->value) == tree.get_key(val)) + return make_pair(iterator{parent}, false); + + auto node = new node_type{val}; + if (tree.keys_comp(tree.get_key(val), parent->value)) + parent->add_left_child(node); + else + parent->add_right_child(node); + + return make_pair(iterator{node}, true); + } + + template + static pair< + typename Tree::iterator, bool + > insert(Tree& tree, Value&& val) + { + using iterator = typename Tree::iterator; + using node_type = typename Tree::node_type; + + auto parent = tree.find_parent_for_insertion(val); + if (!parent) + { + tree.root_ = new node_type{forward(val)}; + + return make_pair(iterator{tree.root_}, true); + } + + if (tree.get_key(parent->value) == tree.get_key(val)) + return make_pair(iterator{parent}, false); + + auto node = new node_type{forward(val)}; + if (tree.keys_comp(tree.get_key(val), parent->value)) + parent->add_left_child(node); + else + parent->add_right_child(node); + + return make_pair(iterator{node}, true); + } + }; + + struct rbtree_multi_policy + { + // TODO: + }; +} + +#endif +