Changeset 73e3791 in mainline


Ignore:
Timestamp:
2018-07-05T21:41:23Z (7 years ago)
Author:
Dzejrou <dzejrou@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
27f1bc0
Parents:
6175b78
git-author:
Dzejrou <dzejrou@…> (2018-05-13 22:57:14)
git-committer:
Dzejrou <dzejrou@…> (2018-07-05 21:41:23)
Message:

cpp: revamped rbtree so that it now stores equivalent keys in a list

Location:
uspace/lib/cpp/include/internal
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • uspace/lib/cpp/include/internal/rbtree.hpp

    r6175b78 r73e3791  
    4141        class KeyComp, class Alloc, class Size,
    4242        class Iterator, class ConstIterator,
    43         class Policy
     43        class Policy, class Node
    4444    >
    4545    class rbtree
    … …  
    5353            using key_extract    = KeyExtractor;
    5454
    55             using iterator             = Iterator;
    56             using const_iterator       = ConstIterator;
     55            using iterator       = Iterator;
     56            using const_iterator = ConstIterator;
    5757
    5858            using reverse_iterator       = std::reverse_iterator<iterator>;
    5959            using const_reverse_iterator = std::reverse_iterator<const_iterator>;
    6060
    61             using node_type = rbtree_node<value_type>;
     61            using node_type = Node;
    6262
    6363            rbtree(const key_compare& kcmp = key_compare{})
    … …  
    100100            bool empty() const noexcept
    101101            {
    102                 return size_;
     102                return size_ == 0U;
    103103            }
    104104
    … …  
    202202
    203203                node = delete_node(node);
    204                 return iterator{const_cast<node_type*>(node), node == nullptr};
     204                if (!node)
     205                    return iterator{find_largest_(), true};
     206                else
     207                    return iterator{const_cast<node_type*>(node), false};
    205208            }
    206209
    … …  
    322325                    parent = current;
    323326                    if (key_compare_(key, key_extractor_(current->value)))
    324                         current = current->left;
     327                        current = current->left();
    325328                    else if (key_compare_(key_extractor_(current->value), key))
    326                         current = current->right;
     329                        current = current->right();
    327330                    else
    328331                        return current;
    … …  
    337340                if (!node)
    338341                    return nullptr;
     342                if (auto tmp = node->get_node_for_deletion(); tmp != nullptr)
     343                {
     344                    /**
     345                     * This will kick in multi containers,
     346                     * we popped one node from a list of nodes
     347                     * with equivalent keys and we can delete it
     348                     * and return the original as it is still
     349                     * in place.
     350                     */
     351                    delete tmp;
     352
     353                    return node;
     354                }
    339355
    340356                --size_;
    341357
     358                if (node == root_)
     359                {
     360                    delete node;
     361                    root_ = nullptr;
     362
     363                    return nullptr;
     364                }
     365
    342366                auto succ = node->successor();
    343                 if (node->left && node->right)
     367                if (node->left() && node->right())
    344368                {
    345369                    node->swap(succ);
    346 
    347                     // Succ has at most one child.
    348                     delete_node(succ);
    349 
    350                     return node;
    351                 }
    352 
    353                 auto child = node->right ? node->right : node->left;
     370                    if (succ && !succ->parent())
     371                        root_ = succ;
     372
     373                    // Node now has at most one child.
     374                    // Also: If succ was nullptr, the swap
     375                    //       didn't do anything and we can
     376                    //       safely delete node.
     377                    return delete_node(node);
     378                }
     379
     380                auto child = node->right() ? node->right() : node->left();
    354381                if (!child)
    355382                {
    … …  
    362389                {
    363390                    // Replace with the child.
    364                     child->parent = node->parent;
     391                    child->parent(node->parent());
    365392                    if (node->is_left_child())
    366                         child->parent->left = child;
     393                        child->parent()->left(child);
    367394                    else if (node->is_right_child())
    368                         child->parent->right = child;
     395                        child->parent()->right(child);
    369396
    370397                    // Repair if needed.
    … …  
    380407            void insert_node(node_type* node, node_type* parent)
    381408            {
    382                 if (!node)
    383                     return;
    384 
    385                 ++size_;
    386                 if (!parent)
    387                 {
    388                     node->color = rbcolor::black;
    389                     root_ = node;
    390                 }
    391                 else
    392                 {
    393                     if (keys_comp(get_key(node->value), parent->value))
    394                         parent->add_left_child(node);
    395                     else
    396                         parent->add_right_child(node);
    397 
    398                     repair_after_insert_(node);
    399                     update_root_(node);
    400                 }
     409                Policy::insert(*this, node, parent);
    401410            }
    402411
    … …  
    413422                {
    414423                    if (key_compare_(key, key_extractor_(current->value)))
    415                         current = current->left;
     424                        current = current->left();
    416425                    else if (key_compare_(key_extractor_(current->value), key))
    417                         current = current->right;
     426                        current = current->right();
    418427                    else
    419428                        return current;
    … …  
    445454
    446455                root_ = const_cast<node_type*>(node);
    447                 while (root_->parent)
    448                     root_ = root_->parent;
     456                while (root_->parent())
     457                    root_ = root_->parent();
    449458            }
    450459

  • uspace/lib/cpp/include/internal/rbtree_iterators.hpp

    r6175b78 r73e3791  
    4545     */
    4646
    47     template<class Value, class Reference, class Pointer, class Size>
     47    template<class Value, class Reference, class Pointer, class Size, class Node>
    4848    class rbtree_iterator
    4949    {
    … …  
    5757            using iterator_category = bidirectional_iterator_tag;
    5858
    59             rbtree_iterator(rbtree_node<value_type>* current = nullptr, bool end = true)
     59            using node_type = Node;
     60
     61            rbtree_iterator(node_type* current = nullptr, bool end = true)
    6062                : current_{current}, end_{end}
    6163            { /* DUMMY BODY */ }
    … …  
    7880                if (current_)
    7981                {
    80                     auto bckp = current_;
    81                     if (current_->right)
    82                         current_ = current_->right->find_smallest();
     82                    auto next = current_->successor();
     83                    if (next)
     84                        current_ = next;
    8385                    else
    84                     {
    85                         while (!current_->is_left_child())
    86                         {
    87                             current_ = current_->parent;
    88 
    89                             if (!current_ || !current_->parent)
    90                             {
    91                                 /**
    92                                  * We've gone back to root without
    93                                  * being a left child, which means we
    94                                  * were the last node.
    95                                  */
    96                                 end_ = true;
    97                                 current_ = bckp;
    98 
    99                                 return *this;
    100                             }
    101                         }
    102 
    103                         /**
    104                          * Now we are a left child,
    105                          * so the next node we have to visit
    106                          * is our parent.
    107                          */
    108                         current_ = current_->parent;
    109                     }
     86                        end_ = true;
    11087                }
    11188
    … …  
    132109                if (current_)
    133110                {
    134                     if (current_->left)
    135                         current_ = current_->left->find_largest();
    136                     else if (current_->parent)
    137                     {
    138                         while (current_->is_left_child())
    139                             current_ = current_->parent;
    140 
    141                         /**
    142                          * We know parent exists here
    143                          * because we went up from the
    144                          * left and stopped being left
    145                          * child (if at any point we happened
    146                          * to become root then this branch
    147                          * wouldn't happen).
    148                          */
    149                         current_ = current_->parent;
    150                     }
    151                     else // We are root without a left child.
     111                    auto next = current_->predecessor();
     112                    if (next)
     113                        current_ = next;
     114                    else
    152115                        end_ = true;
    153116                }
    … …  
    164127            }
    165128
    166             const rbtree_node<value_type>* node() const
     129            const node_type* node() const
    167130            {
    168131                return current_;
    169132            }
    170133
    171             rbtree_node<value_type>* node()
     134            node_type* node()
    172135            {
    173136                return current_;
    … …  
    180143
    181144        private:
    182             rbtree_node<value_type>* current_;
     145            node_type* current_;
    183146            bool end_;
    184147
    … …  
    197160    };
    198161
    199     template<class Val, class Ref, class Ptr, class Sz>
    200     bool operator==(const rbtree_iterator<Val, Ref, Ptr, Sz>& lhs,
    201                     const rbtree_iterator<Val, Ref, Ptr, Sz>& rhs)
     162    template<class Val, class Ref, class Ptr, class Sz, class N>
     163    bool operator==(const rbtree_iterator<Val, Ref, Ptr, Sz, N>& lhs,
     164                    const rbtree_iterator<Val, Ref, Ptr, Sz, N>& rhs)
    202165    {
    203166        return (lhs.node() == rhs.node()) && (lhs.end() == rhs.end());
    204167    }
    205168
    206     template<class Val, class Ref, class Ptr, class Sz>
    207     bool operator!=(const rbtree_iterator<Val, Ref, Ptr, Sz>& lhs,
    208                     const rbtree_iterator<Val, Ref, Ptr, Sz>& rhs)
     169    template<class Val, class Ref, class Ptr, class Sz, class N>
     170    bool operator!=(const rbtree_iterator<Val, Ref, Ptr, Sz, N>& lhs,
     171                    const rbtree_iterator<Val, Ref, Ptr, Sz, N>& rhs)
    209172    {
    210173        return !(lhs == rhs);
    211174    }
    212175
    213     template<class Value, class ConstReference, class ConstPointer, class Size>
     176    template<class Value, class ConstReference, class ConstPointer, class Size, class Node>
    214177    class rbtree_const_iterator
    215178    {
    216179        using non_const_iterator_type = rbtree_iterator<
    217180            Value, get_non_const_ref_t<ConstReference>,
    218             get_non_const_ptr_t<ConstPointer>, Size
     181            get_non_const_ptr_t<ConstPointer>, Size, Node
    219182        >;
    220183
    … …  
    228191            using iterator_category = bidirectional_iterator_tag;
    229192
    230             rbtree_const_iterator(const rbtree_node<value_type>* current = nullptr, bool end = true)
     193            using node_type = Node;
     194
     195            rbtree_const_iterator(const node_type* current = nullptr, bool end = true)
    231196                : current_{current}, end_{end}
    232197            { /* DUMMY BODY */ }
    … …  
    261226                if (current_)
    262227                {
    263                     auto bckp = current_;
    264                     if (current_->right)
    265                         current_ = current_->right->find_smallest();
     228                    auto next = current_->successor();
     229                    if (next)
     230                        current_ = next;
    266231                    else
    267                     {
    268                         while (!current_->is_left_child())
    269                         {
    270                             current_ = current_->parent;
    271 
    272                             if (!current_->parent)
    273                             {
    274                                 /**
    275                                  * We've gone back to root without
    276                                  * being a left child, which means we
    277                                  * were the last node.
    278                                  */
    279                                 end_ = true;
    280                                 current_ = bckp;
    281 
    282                                 return *this;
    283                             }
    284                         }
    285 
    286                         /**
    287                          * Now we are a left child,
    288                          * so the next node we have to visit
    289                          * is our parent.
    290                          */
    291                         current_ = current_->parent;
    292                     }
     232                        end_ = true;
    293233                }
    294234
    … …  
    315255                if (current_)
    316256                {
    317                     if (current_->left)
    318                         current_ = current_->left->find_largest();
    319                     else if (current_->parent)
    320                     {
    321                         while (current_->is_left_child())
    322                             current_ = current_->parent;
    323 
    324                         /**
    325                          * We know parent exists here
    326                          * because we went up from the
    327                          * left and stopped being left
    328                          * child (if at any point we happened
    329                          * to become root then this branch
    330                          * wouldn't happen).
    331                          */
    332                         current_ = current_->parent;
    333                     }
    334                     else // We are root without a left child.
    335                         current_ = nullptr;
     257                    auto next = current_->predecessor();
     258                    if (next)
     259                        current_ = next;
     260                    else
     261                        end_ = true;
    336262                }
    337263
    … …  
    347273            }
    348274
    349             const rbtree_node<value_type>* node() const
     275            const node_type* node() const
    350276            {
    351277                return current_;
    … …  
    358284
    359285        private:
    360             const rbtree_node<value_type>* current_;
     286            const node_type* current_;
    361287            bool end_;
    362288
    … …  
    375301    };
    376302
    377     template<class Val, class CRef, class CPtr, class Sz>
    378     bool operator==(const rbtree_const_iterator<Val, CRef, CPtr, Sz>& lhs,
    379                     const rbtree_const_iterator<Val, CRef, CPtr, Sz>& rhs)
     303    template<class Val, class CRef, class CPtr, class Sz, class N>
     304    bool operator==(const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& lhs,
     305                    const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& rhs)
    380306    {
    381307        return (lhs.node() == rhs.node()) && (lhs.end() == rhs.end());
    382308    }
    383309
    384     template<class Val, class CRef, class CPtr, class Sz>
    385     bool operator!=(const rbtree_const_iterator<Val, CRef, CPtr, Sz>& lhs,
    386                     const rbtree_const_iterator<Val, CRef, CPtr, Sz>& rhs)
     310    template<class Val, class CRef, class CPtr, class Sz, class N>
     311    bool operator!=(const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& lhs,
     312                    const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& rhs)
    387313    {
    388314        return !(lhs == rhs);
    389315    }
    390316
    391     template<class Val, class Ref, class Ptr, class CRef, class CPtr, class Sz>
    392     bool operator==(const rbtree_iterator<Val, Ref, Ptr, Sz>& lhs,
    393                     const rbtree_const_iterator<Val, CRef, CPtr, Sz>& rhs)
     317    template<class Val, class Ref, class Ptr, class CRef, class CPtr, class Sz, class N>
     318    bool operator==(const rbtree_iterator<Val, Ref, Ptr, Sz, N>& lhs,
     319                    const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& rhs)
    394320    {
    395321        return (lhs.node() == rhs.node()) && (lhs.end() == rhs.end());
    396322    }
    397323
    398     template<class Val, class Ref, class Ptr, class CRef, class CPtr, class Sz>
    399     bool operator!=(const rbtree_iterator<Val, Ref, Ptr, Sz>& lhs,
    400                     const rbtree_const_iterator<Val, CRef, CPtr, Sz>& rhs)
     324    template<class Val, class Ref, class Ptr, class CRef, class CPtr, class Sz, class N>
     325    bool operator!=(const rbtree_iterator<Val, Ref, Ptr, Sz, N>& lhs,
     326                    const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& rhs)
    401327    {
    402328        return !(lhs == rhs);
    403329    }
    404330
    405     template<class Val, class CRef, class CPtr, class Ref, class Ptr, class Sz>
    406     bool operator==(const rbtree_const_iterator<Val, CRef, CPtr, Sz>& lhs,
    407                     const rbtree_iterator<Val, Ref, Ptr, Sz>& rhs)
     331    template<class Val, class CRef, class CPtr, class Ref, class Ptr, class Sz, class N>
     332    bool operator==(const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& lhs,
     333                    const rbtree_iterator<Val, Ref, Ptr, Sz, N>& rhs)
    408334    {
    409335        return (lhs.node() == rhs.node()) && (lhs.end() == rhs.end());
    410336    }
    411337
    412     template<class Val, class CRef, class CPtr, class Ref, class Ptr, class Sz>
    413     bool operator!=(const rbtree_const_iterator<Val, CRef, CPtr, Sz>& lhs,
    414                     const rbtree_iterator<Val, Ref, Ptr, Sz>& rhs)
     338    template<class Val, class CRef, class CPtr, class Ref, class Ptr, class Sz, class N>
     339    bool operator!=(const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& lhs,
     340                    const rbtree_iterator<Val, Ref, Ptr, Sz, N>& rhs)
    415341    {
    416342        return !(lhs == rhs);

  • uspace/lib/cpp/include/internal/rbtree_node.hpp

    r6175b78 r73e3791  
    3030#define LIBCPP_INTERNAL_RBTREE_NODE
    3131
     32#include <cassert>
    3233#include <utility>
    3334
    … …  
    3940    };
    4041
    41     template<class T>
    42     struct rbtree_node
     42    template<class Node>
     43    struct rbtree_utils
    4344    {
    44         T value;
    45         rbcolor color;
    46 
    47         rbtree_node* parent;
    48         rbtree_node* left;
    49         rbtree_node* right;
    50 
    51         template<class... Args>
    52         rbtree_node(Args&&... args)
    53             : value{forward<Args>(args)...}, color{rbcolor::red},
    54               parent{}, left{}, right{}
    55         { /* DUMMY BODY */ }
    56 
    57         rbtree_node* grandparent() const
    58         {
    59             if (parent)
    60                 return parent->parent;
     45        static Node* grandparent(Node* node)
     46        {
     47            if (node && node->parent())
     48                return node->parent->parent();
    6149            else
    6250                return nullptr;
    6351        }
    6452
    65         rbtree_node* brother() const
    66         {
    67             if (parent)
    68             {
    69                 if (this == parent->left)
    70                     return parent->right;
    71                 else
    72                     return parent->left;
     53        static Node* brother(Node* node)
     54        {
     55            if (node && node->parent())
     56            {
     57                if (node == node->parent->left())
     58                    return node->parent->right();
     59                else
     60                    return node->parent->left();
    7361            }
    7462            else
    … …  
    7664        }
    7765
    78         rbtree_node* uncle() const
    79         {
    80             if (grandparent())
    81             {
    82                 if (parent == grandparent()->left)
    83                     return grandparent()->right;
    84                 else
    85                     return grandparent()->left;
     66        static Node* uncle(Node* node)
     67        {
     68            auto gp = grandparent(node);
     69            if (gp)
     70            {
     71                if (node->parent() == gp->left())
     72                    return gp->right();
     73                else
     74                    return gp->left();
    8675            }
    8776            else
    … …  
    8978        }
    9079
    91         bool is_left_child() const
    92         {
    93             if (parent)
    94                 return parent->left == this;
     80        static bool is_left_child(const Node* node)
     81        {
     82            if (!node)
     83                return false;
     84
     85            if (node->parent())
     86                return node->parent()->left() == node;
    9587            else
    9688                return false;
    9789        }
    9890
    99         bool is_right_child() const
    100         {
    101             if (parent)
    102                 return parent->right == this;
     91        static bool is_right_child(const Node* node)
     92        {
     93            if (!node)
     94                return false;
     95
     96            if (node->parent())
     97                return node->parent()->right() == node;
    10398            else
    10499                return false;
    105100        }
    106101
    107         void rotate_left()
    108         {
    109             // TODO:
    110         }
    111 
    112         void rotate_right()
    113         {
    114             // TODO:
    115         }
    116 
    117         rbtree_node* find_smallest()
    118         {
    119             auto res = this;
    120             while (res->left)
    121                 res = res->left;
    122 
    123             return res;
    124         }
    125 
    126         const rbtree_node* find_smallest() const
    127         {
    128             auto res = this;
    129             while (res->left)
    130                 res = res->left;
    131 
    132             return res;
    133         }
    134 
    135         rbtree_node* find_largest()
    136         {
    137             auto res = this;
    138             while (res->right)
    139                 res = res->right;
    140 
    141             return res;
    142         }
    143 
    144         const rbtree_node* find_largest() const
    145         {
    146             auto res = this;
    147             while (res->right)
    148                 res = res->right;
    149 
    150             return res;
    151         }
    152 
    153         rbtree_node* successor() const
    154         {
    155             if (right)
    156                 return right->find_smallest();
     102        static void rotate_left(Node* node)
     103        {
     104            // TODO: implement
     105        }
     106
     107        static void rotate_right(Node* node)
     108        {
     109            // TODO: implement
     110        }
     111
     112        static Node* find_smallest(Node* node)
     113        {
     114            return const_cast<Node*>(find_smallest(const_cast<const Node*>(node)));
     115        }
     116
     117        static const Node* find_smallest(const Node* node)
     118        {
     119            if (!node)
     120                return nullptr;
     121
     122            while (node->left())
     123                node = node->left();
     124
     125            return node;
     126        }
     127
     128        static Node* find_largest(Node* node)
     129        {
     130            return const_cast<Node*>(find_largest(const_cast<const Node*>(node)));
     131        }
     132
     133        static const Node* find_largest(const Node* node)
     134        {
     135            if (!node)
     136                return nullptr;
     137
     138            while (node->right())
     139                node = node->right();
     140
     141            return node;
     142        }
     143
     144        static Node* successor(Node* node)
     145        {
     146            return const_cast<Node*>(successor(const_cast<const Node*>(node)));
     147        }
     148
     149        static const Node* successor(const Node* node)
     150        {
     151            if (!node)
     152                return nullptr;
     153
     154            if (node->right())
     155                return find_smallest(node->right());
    157156            else
    158157            {
    159                 auto current = this;
    160                 while (!current->is_left_child())
    161                     current = current->parent;
    162 
    163                 return current->parent;
    164             }
    165         }
    166 
    167         void add_left_child(rbtree_node* node)
    168         {
    169             if (left)
     158                while (node && !is_left_child(node))
     159                    node = node->parent();
     160
     161                if (node)
     162                    return node->parent();
     163                else
     164                    return node;
     165            }
     166        }
     167
     168        static Node* predecessor(Node* node)
     169        {
     170            return const_cast<Node*>(predecessor(const_cast<const Node*>(node)));
     171        }
     172
     173        static const Node* predecessor(const Node* node)
     174        {
     175            if (!node)
     176                return nullptr;
     177
     178            if (node->left())
     179                return find_largest(node->left());
     180            else
     181            {
     182                while (node && is_left_child(node))
     183                    node = node->parent();
     184
     185                if (node)
     186                    return node->parent();
     187                else
     188                    return node;
     189            }
     190        }
     191
     192        static void add_left_child(Node* node, Node* child)
     193        {
     194            if (!node || !child)
    170195                return;
    171196
    172             left = node;
    173             node->parent = this;
    174         }
    175 
    176         void add_right_child(rbtree_node* node)
    177         {
    178             if (right)
     197            node->left(child);
     198            child->parent(node);
     199        }
     200
     201        static void add_right_child(Node* node, Node* child)
     202        {
     203            if (!node || !child)
    179204                return;
    180205
    181             right = node;
    182             node->parent = this;
    183         }
    184 
    185         void swap(rbtree_node* other)
    186         {
    187             std::swap(value, other->value);
    188         }
    189 
    190         void unlink()
    191         {
    192             if (is_left_child())
    193                 parent->left = nullptr;
    194             else if (is_right_child())
    195                 parent->right = nullptr;
    196         }
    197 
    198         ~rbtree_node()
    199         {
    200             // TODO: delete recursively or iteratively?
    201         }
     206            node->right(child);
     207            child->parent(node);
     208        }
     209
     210        static void swap(Node* node1, Node* node2)
     211        {
     212            if (!node1 || !node2)
     213                return;
     214
     215            auto parent1 = node1->parent();
     216            auto left1 = node1->left();
     217            auto right1 = node1->right();
     218            auto is_right1 = is_right_child(node1);
     219
     220            auto parent2 = node2->parent();
     221            auto left2 = node2->left();
     222            auto right2 = node2->right();
     223            auto is_right2 = is_right_child(node2);
     224
     225            assimilate(node1, parent2, left2, right2, is_right2);
     226            assimilate(node2, parent1, left1, right1, is_right1);
     227        }
     228
     229        static void assimilate(
     230            Node* node, Node* p, Node* l, Node* r, bool is_r
     231        )
     232        {
     233            if (!node)
     234                return;
     235
     236            node->parent(p);
     237            if (node->parent())
     238            {
     239                if (is_r)
     240                    node->parent()->right(node);
     241                else
     242                    node->parent()->left(node);
     243            }
     244
     245            node->left(l);
     246            if (node->left())
     247                node->left()->parent(node);
     248
     249            node->right(r);
     250            if (node->right())
     251                node->right()->parent(node);
     252        }
     253    };
     254
     255    template<class T>
     256    struct rbtree_single_node
     257    {
     258        using utils = rbtree_utils<rbtree_single_node<T>>;
     259
     260        public:
     261            T value;
     262            rbcolor color;
     263
     264            template<class... Args>
     265            rbtree_single_node(Args&&... args)
     266                : value{forward<Args>(args)...}, color{rbcolor::red},
     267                  parent_{}, left_{}, right_{}
     268            { /* DUMMY BODY */ }
     269
     270            rbtree_single_node* parent() const
     271            {
     272                return parent_;
     273            }
     274
     275            void parent(rbtree_single_node* node)
     276            {
     277                parent_ = node;
     278            }
     279
     280            rbtree_single_node* left() const
     281            {
     282                return left_;
     283            }
     284
     285            void left(rbtree_single_node* node)
     286            {
     287                left_ = node;
     288            }
     289
     290            rbtree_single_node* right() const
     291            {
     292                return right_;
     293            }
     294
     295            void right(rbtree_single_node* node)
     296            {
     297                right_ = node;
     298            }
     299
     300            rbtree_single_node* grandparent()
     301            {
     302                return utils::grandparent(this);
     303            }
     304
     305            rbtree_single_node* brother()
     306            {
     307                return utils::brother(this);
     308            }
     309
     310            rbtree_single_node* uncle()
     311            {
     312                return utils::uncle(this);
     313            }
     314
     315            bool is_left_child() const
     316            {
     317                return utils::is_left_child(this);
     318            }
     319
     320            bool is_right_child() const
     321            {
     322                return utils::is_right_child(this);
     323            }
     324
     325            void rotate_left()
     326            {
     327                utils::rotate_left(this);
     328            }
     329
     330            void rotate_right()
     331            {
     332                utils::rotate_right(this);
     333            }
     334
     335            rbtree_single_node* find_smallest()
     336            {
     337                return utils::find_smallest(this);
     338            }
     339
     340            const rbtree_single_node* find_smallest() const
     341            {
     342                return utils::find_smallest(this);
     343            }
     344
     345            rbtree_single_node* find_largest()
     346            {
     347                return utils::find_largest(this);
     348            }
     349
     350            const rbtree_single_node* find_largest() const
     351            {
     352                return utils::find_largest(this);
     353            }
     354
     355            rbtree_single_node* successor()
     356            {
     357                return utils::successor(this);
     358            }
     359
     360            const rbtree_single_node* successor() const
     361            {
     362                return utils::successor(this);
     363            }
     364
     365            rbtree_single_node* predecessor()
     366            {
     367                return utils::predecessor(this);
     368            }
     369
     370            const rbtree_single_node* predecessor() const
     371            {
     372                return utils::predecessor(this);
     373            }
     374
     375            void add_left_child(rbtree_single_node* node)
     376            {
     377                utils::add_left_child(this, node);
     378            }
     379
     380            void add_right_child(rbtree_single_node* node)
     381            {
     382                utils::add_right_child(this, node);
     383            }
     384
     385            void swap(rbtree_single_node* other)
     386            {
     387                utils::swap(this, other);
     388            }
     389
     390            void unlink()
     391            {
     392                if (is_left_child())
     393                    parent_->left_ = nullptr;
     394                else if (is_right_child())
     395                    parent_->right_ = nullptr;
     396            }
     397
     398            rbtree_single_node* get_node_for_deletion()
     399            {
     400                return nullptr;
     401            }
     402
     403            ~rbtree_single_node()
     404            {
     405                parent_ = nullptr;
     406                if (left_)
     407                    delete left_;
     408                if (right_)
     409                    delete right_;
     410            }
     411
     412        private:
     413            rbtree_single_node* parent_;
     414            rbtree_single_node* left_;
     415            rbtree_single_node* right_;
     416    };
     417
     418    template<class T>
     419    struct rbtree_multi_node
     420    {
     421        using utils = rbtree_utils<rbtree_multi_node<T>>;
     422
     423        public:
     424            T value;
     425            rbcolor color;
     426
     427            template<class... Args>
     428            rbtree_multi_node(Args&&... args)
     429                : value{forward<Args>(args)...}, color{rbcolor::red},
     430                  parent_{}, left_{}, right_{}, next_{}, first_{this}
     431            { /* DUMMY BODY */ }
     432
     433            rbtree_multi_node* parent() const
     434            {
     435                return parent_;
     436            }
     437
     438            void parent(rbtree_multi_node* node)
     439            {
     440                parent_ = node;
     441
     442                auto tmp = first_;
     443                while (tmp)
     444                {
     445                    tmp->parent_ = node;
     446                    tmp = tmp->next_;
     447                }
     448            }
     449
     450            rbtree_multi_node* left() const
     451            {
     452                return left_;
     453            }
     454
     455            void left(rbtree_multi_node* node)
     456            {
     457                left_ = node;
     458
     459                auto tmp = first_;
     460                while (tmp)
     461                {
     462                    tmp->left_ = node;
     463                    tmp = tmp->next_;
     464                }
     465            }
     466
     467            rbtree_multi_node* right() const
     468            {
     469                return right_;
     470            }
     471
     472            void right(rbtree_multi_node* node)
     473            {
     474                right_ = node;
     475
     476                auto tmp = first_;
     477                while (tmp)
     478                {
     479                    tmp->right_ = node;
     480                    tmp = tmp->next_;
     481                }
     482            }
     483
     484            rbtree_multi_node* grandparent()
     485            {
     486                return utils::grandparent(this);
     487            }
     488
     489            rbtree_multi_node* brother()
     490            {
     491                return utils::brother(this);
     492            }
     493
     494            rbtree_multi_node* uncle()
     495            {
     496                return utils::uncle(this);
     497            }
     498
     499            bool is_left_child() const
     500            {
     501                return utils::is_left_child(this);
     502            }
     503
     504            bool is_right_child()
     505            {
     506                return utils::is_right_child(this);
     507            }
     508
     509            void rotate_left()
     510            {
     511                utils::rotate_left(this);
     512            }
     513
     514            void rotate_right()
     515            {
     516                utils::rotate_right(this);
     517            }
     518
     519            rbtree_multi_node* find_smallest()
     520            {
     521                return utils::find_smallest(this);
     522            }
     523
     524            const rbtree_multi_node* find_smallest() const
     525            {
     526                return utils::find_smallest(this);
     527            }
     528
     529            rbtree_multi_node* find_largest()
     530            {
     531                return utils::find_largest(this);
     532            }
     533
     534            const rbtree_multi_node* find_largest() const
     535            {
     536                return utils::find_largest(this);
     537            }
     538
     539            rbtree_multi_node* successor()
     540            {
     541                return const_cast<
     542                    rbtree_multi_node*
     543                >(const_cast<const rbtree_multi_node*>(this)->successor());
     544            }
     545
     546            const rbtree_multi_node* successor() const
     547            {
     548                if (next_)
     549                    return next_;
     550                else
     551                    return utils::successor(this);
     552            }
     553
     554            rbtree_multi_node* predecessor()
     555            {
     556                return const_cast<
     557                    rbtree_multi_node*
     558                >(const_cast<const rbtree_multi_node*>(this)->predecessor());
     559            }
     560
     561            const rbtree_multi_node* predecessor() const
     562            {
     563                return utils::predecessor(this);
     564            }
     565
     566            void add_left_child(rbtree_multi_node* node)
     567            {
     568                utils::add_left_child(this, node);
     569            }
     570
     571            void add_right_child(rbtree_multi_node* node)
     572            {
     573                utils::add_right_child(this, node);
     574            }
     575
     576            void swap(rbtree_multi_node* other)
     577            {
     578                utils::swap(this, other);
     579            }
     580
     581            rbtree_multi_node<T>* get_node_for_deletion()
     582            {
     583                if (next_)
     584                {
     585                    auto tmp = next_;
     586                    while (tmp && tmp->next_ != this)
     587                        tmp = tmp->next_;
     588
     589                    return tmp; // This will get deleted.
     590                }
     591                else
     592                    return nullptr;
     593            }
     594
     595            void unlink()
     596            {
     597                if (is_left_child())
     598                    parent->left_ = nullptr;
     599                else if (is_right_child())
     600                    parent->right_ = nullptr;
     601            }
     602
     603            void add(rbtree_multi_node* node)
     604            {
     605                if (next_)
     606                    next_->add(node);
     607                else
     608                {
     609                    next_ = node;
     610                    next_->first_ = first_;
     611                    next_->parent_ = parent_;
     612                    next_->left_ = left_;
     613                    next_->right_ = right_;
     614                }
     615            }
     616
     617            ~rbtree_multi_node()
     618            {
     619                parent_ = nullptr;
     620                if (left_)
     621                    delete left_;
     622                if (right)
     623                    delete right_;
     624
     625                // TODO: delete the list
     626            }
     627
     628        private:
     629            rbtree_multi_node* parent_;
     630            rbtree_multi_node* left_;
     631            rbtree_multi_node* right_;
     632
     633            rbtree_multi_node* next_;
     634            rbtree_multi_node* first_;
    202635    };
    203636}

  • uspace/lib/cpp/include/internal/rbtree_policies.hpp

    r6175b78 r73e3791  
    5959        static typename Tree::iterator lower_bound(const Tree& tree, const Key& key)
    6060        {
    61             using iterator = typename Tree::iterator;
     61            using iterator  = typename Tree::iterator;
     62            using node_type = typename Tree::node_type;
    6263
    6364            auto it = lower_bound_const(tree, key);
    6465
    65             return iterator{it.node(), it.end()};
     66            return iterator{const_cast<node_type*>(it.node()), it.end()};
    6667        }
    6768
    … …  
    101102        static typename Tree::iterator upper_bound(const Tree& tree, const Key& key)
    102103        {
    103             using iterator = typename Tree::iterator;
     104            using iterator  = typename Tree::iterator;
     105            using node_type = typename Tree::node_type;
    104106
    105107            auto it = upper_bound_const(tree, key);
    106108
    107             return iterator{it.node(), it.end()};
     109            return iterator{const_cast<node_type*>(it.node()), it.end()};
    108110        }
    109111
    … …  
    113115            /**
    114116             * If key isn't in the tree, we get it's
    115              * successor or tree.end(). If key is
    116              * in the tree, we get it.
    117              * In the first case, the successor is also
    118              * the upper bound, so we just return it,
    119              * otherwise (as long as it != end()) we
    120              * increment.
     117             * predecessor or tree.end(). If key is
     118             * in the tree, we get it. So unless it
     119             * is equal to end(), we can increment it
     120             * to get the upper bound.
    121121             */
    122122            auto it = lower_bound_const(tree, key);
    123123            if (it == tree.end())
    124124                return it;
    125             else if (tree.keys_equal(key, *it))
     125            else
    126126                return ++it;
    127             else
    128                 return it;
    129127        }
    130128
    … …  
    176174
    177175            auto node = new node_type{move(val)};
    178             tree.insert_node(node, parent);
    179 
    180             return make_pair(iterator{node, false}, true);
     176
     177            return insert(tree, node, parent);
    181178        }
    182179
    … …  
    194191
    195192            auto node = new node_type{val};
    196             tree.insert_node(node, parent);
    197 
    198             return make_pair(iterator{node, false}, true);
     193
     194            return insert(tree, node, parent);
    199195        }
    200196
    … …  
    212208
    213209            auto node = new node_type{forward<Value>(val)};
    214             tree.insert_node(node, parent);
     210
     211            return insert(tree, node, parent);
     212        }
     213
     214        template<class Tree>
     215        static pair<
     216            typename Tree::iterator, bool
     217        > insert(
     218            Tree& tree, typename Tree::node_type* node,
     219            typename Tree::node_type* parent
     220        )
     221        {
     222            using iterator  = typename Tree::iterator;
     223
     224            if (!node)
     225                return make_pair(tree.end(), false);
     226
     227            ++tree.size_;
     228            if (!parent)
     229            {
     230                node->color = rbcolor::black;
     231                tree.root_ = node;
     232            }
     233            else
     234            {
     235                if (tree.keys_comp(tree.get_key(node->value), parent->value))
     236                    parent->add_left_child(node);
     237                else
     238                    parent->add_right_child(node);
     239
     240                tree.repair_after_insert_(node);
     241                tree.update_root_(node);
     242            }
    215243
    216244            return make_pair(iterator{node, false}, true);
    … …  
    308336            /**
    309337             * If key isn't in the tree, we get it's
    310              * successor or tree.end(). If key is
    311              * in the tree, we get it.
    312              * In the first case, the successor is also
    313              * the upper bound, so we just return it,
    314              * otherwise (as long as it != end()) we
    315              * increment.
     338             * predecessor or tree.end(). If key is
     339             * in the tree, we get it. So unless it
     340             * is equal to end(), we keep incrementing
     341             * until we get to the next key.
    316342             */
    317343            auto it = lower_bound(tree, key);
    … …  
    320346            else if (tree.keys_equal(tree.get_key(*it), key))
    321347            {
    322                 while (tree.keys_equal(tree.get_key(*it), key))
     348                while (it != tree.end() && tree.keys_equal(tree.get_key(*it), key))
    323349                    ++it;
    324350
    … …  
    384410
    385411        template<class Tree>
    386         static typename Tree::iterator insert(Tree& tree, typename Tree::node_type* node)
    387         {
    388             using iterator  = typename Tree::iterator;
     412        static typename Tree::iterator insert(
     413            Tree& tree, typename Tree::node_type* node,
     414            typename Tree::node_type* = nullptr
     415        )
     416        {
     417            using iterator  = typename Tree::iterator;
     418
     419            if (!node)
     420                return tree.end();
    389421
    390422            auto parent = tree.find_parent_for_insertion(tree.get_key(node->value));
    391             tree.insert_node(node, parent);
     423
     424            ++tree.size_;
     425            if (!parent)
     426            {
     427                node->color = rbcolor::black;
     428                tree.root_ = node;
     429            }
     430            else
     431            {
     432                if (tree.keys_comp(tree.get_key(node->value), parent->value))
     433                    parent->add_left_child(node);
     434                else if (tree.keys_comp(tree.get_key(parent->value), node->value))
     435                    parent->add_right_child(node);
     436                else
     437                {
     438                    parent->add(node); // List of nodes with equivalent keys.
     439                    tree.update_root_(parent);
     440
     441                    return iterator{node, false};
     442                }
     443
     444                tree.repair_after_insert_(node);
     445                tree.update_root_(node);
     446            }
    392447
    393448            return iterator{node, false};
Note: See TracChangeset for help on using the changeset viewer.