Ignore:
Timestamp:
2018-07-05T21:41:22Z (7 years ago)
Author:
Dzejrou <dzejrou@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
89bc6460
Parents:
009d78b
git-author:
Dzejrou <dzejrou@…> (2018-04-29 19:23:26)
git-committer:
Dzejrou <dzejrou@…> (2018-07-05 21:41:22)
Message:

cpp: fixed conversions from non-const iterators to const iterators

File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r009d78b rd6bb78b  
    3030#define LIBCPP_INTERNAL_RBTREE_ITERATORS
    3131
     32#include <internal/iterator.hpp>
    3233#include <internal/rbtree_node.hpp>
    3334#include <iterator>
    … …  
    4445     */
    4546
     47    template<class Value, class Reference, class Pointer, class Size>
     48    class rbtree_iterator
     49    {
     50        public:
     51            using value_type      = Value;
     52            using size_type       = Size;
     53            using reference       = Reference;
     54            using pointer         = Pointer;
     55            using difference_type = ptrdiff_t;
     56
     57            using iterator_category = bidirectional_iterator_tag;
     58
     59            rbtree_iterator(rbtree_node<value_type>* current = nullptr, bool end = true)
     60                : current_{current}, end_{end}
     61            { /* DUMMY BODY */ }
     62
     63            rbtree_iterator(const rbtree_iterator&) = default;
     64            rbtree_iterator& operator=(const rbtree_iterator&) = default;
     65
     66            reference operator*() const
     67            {
     68                return current_->value;
     69            }
     70
     71            pointer operator->() const
     72            {
     73                return &current_->value;
     74            }
     75
     76            rbtree_iterator& operator++()
     77            {
     78                if (current_)
     79                {
     80                    auto bckp = current_;
     81                    if (current_->right)
     82                        current_ = current_->right->find_smallest();
     83                    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                    }
     110                }
     111
     112                return *this;
     113            }
     114
     115            rbtree_iterator operator++(int)
     116            {
     117                auto tmp = *this;
     118                ++(*this);
     119
     120                return tmp;
     121            }
     122
     123            rbtree_iterator& operator--()
     124            {
     125                if (end_)
     126                {
     127                    try_undo_end_();
     128
     129                    return *this;
     130                }
     131
     132                if (current_)
     133                {
     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.
     152                        end_ = true;
     153                }
     154
     155                return *this;
     156            }
     157
     158            rbtree_iterator operator--(int)
     159            {
     160                auto tmp = *this;
     161                --(*this);
     162
     163                return tmp;
     164            }
     165
     166            const rbtree_node<value_type>* node() const
     167            {
     168                return current_;
     169            }
     170
     171            rbtree_node<value_type>* node()
     172            {
     173                return current_;
     174            }
     175
     176            bool end() const
     177            {
     178                return end_;
     179            }
     180
     181        private:
     182            rbtree_node<value_type>* current_;
     183            bool end_;
     184
     185            void try_undo_end_()
     186            {
     187                if (!current_)
     188                    return;
     189
     190                /**
     191                 * We can do this if we are past end().
     192                 * This means we are the largest.
     193                 */
     194                if (current_->find_largest() == current_)
     195                    end_ = false;
     196            }
     197    };
     198
     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)
     202    {
     203        return (lhs.node() == rhs.node()) && (lhs.end() == rhs.end());
     204    }
     205
     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)
     209    {
     210        return !(lhs == rhs);
     211    }
     212
    46213    template<class Value, class ConstReference, class ConstPointer, class Size>
    47214    class rbtree_const_iterator
    48215    {
     216        using non_const_iterator_type = rbtree_iterator<
     217            Value, get_non_const_ref_t<ConstReference>,
     218            get_non_const_ptr_t<ConstPointer>, Size
     219        >;
     220
    49221        public:
    50222            using value_type      = Value;
    … …  
    62234            rbtree_const_iterator(const rbtree_const_iterator&) = default;
    63235            rbtree_const_iterator& operator=(const rbtree_const_iterator&) = default;
     236
     237            rbtree_const_iterator(const non_const_iterator_type& other)
     238                : current_{other.node()}, end_{other.end()}
     239            { /* DUMMY BODY */ }
     240
     241            rbtree_const_iterator& operator=(const non_const_iterator_type& other)
     242            {
     243                current_ = other.node();
     244                end_ = other.end();
     245
     246                return *this;
     247            }
    64248
    65249            const_reference operator*() const
    … …  
    205389    }
    206390
    207     template<class Value, class Reference, class Pointer, class Size>
    208     class rbtree_iterator
    209     {
    210         public:
    211             using value_type      = Value;
    212             using size_type       = Size;
    213             using reference       = Reference;
    214             using pointer         = Pointer;
    215             using difference_type = ptrdiff_t;
    216 
    217             using iterator_category = bidirectional_iterator_tag;
    218 
    219             rbtree_iterator(rbtree_node<value_type>* current = nullptr, bool end = true)
    220                 : current_{current}, end_{end}
    221             { /* DUMMY BODY */ }
    222 
    223             rbtree_iterator(const rbtree_iterator&) = default;
    224             rbtree_iterator& operator=(const rbtree_iterator&) = default;
    225 
    226             reference operator*() const
    227             {
    228                 return current_->value;
    229             }
    230 
    231             pointer operator->() const
    232             {
    233                 return &current_->value;
    234             }
    235 
    236             rbtree_iterator& operator++()
    237             {
    238                 if (current_)
    239                 {
    240                     auto bckp = current_;
    241                     if (current_->right)
    242                         current_ = current_->right->find_smallest();
    243                     else
    244                     {
    245                         while (!current_->is_left_child())
    246                         {
    247                             current_ = current_->parent;
    248 
    249                             if (!current_ || !current_->parent)
    250                             {
    251                                 /**
    252                                  * We've gone back to root without
    253                                  * being a left child, which means we
    254                                  * were the last node.
    255                                  */
    256                                 end_ = true;
    257                                 current_ = bckp;
    258 
    259                                 return *this;
    260                             }
    261                         }
    262 
    263                         /**
    264                          * Now we are a left child,
    265                          * so the next node we have to visit
    266                          * is our parent.
    267                          */
    268                         current_ = current_->parent;
    269                     }
    270                 }
    271 
    272                 return *this;
    273             }
    274 
    275             rbtree_iterator operator++(int)
    276             {
    277                 auto tmp = *this;
    278                 ++(*this);
    279 
    280                 return tmp;
    281             }
    282 
    283             rbtree_iterator& operator--()
    284             {
    285                 if (end_)
    286                 {
    287                     try_undo_end_();
    288 
    289                     return *this;
    290                 }
    291 
    292                 if (current_)
    293                 {
    294                     if (current_->left)
    295                         current_ = current_->left->find_largest();
    296                     else if (current_->parent)
    297                     {
    298                         while (current_->is_left_child())
    299                             current_ = current_->parent;
    300 
    301                         /**
    302                          * We know parent exists here
    303                          * because we went up from the
    304                          * left and stopped being left
    305                          * child (if at any point we happened
    306                          * to become root then this branch
    307                          * wouldn't happen).
    308                          */
    309                         current_ = current_->parent;
    310                     }
    311                     else // We are root without a left child.
    312                         end_ = true;
    313                 }
    314 
    315                 return *this;
    316             }
    317 
    318             rbtree_iterator operator--(int)
    319             {
    320                 auto tmp = *this;
    321                 --(*this);
    322 
    323                 return tmp;
    324             }
    325 
    326             const rbtree_node<value_type>* node() const
    327             {
    328                 return current_;
    329             }
    330 
    331             rbtree_node<value_type>* node()
    332             {
    333                 return current_;
    334             }
    335 
    336             bool end() const
    337             {
    338                 return end_;
    339             }
    340 
    341         private:
    342             rbtree_node<value_type>* current_;
    343             bool end_;
    344 
    345             void try_undo_end_()
    346             {
    347                 if (!current_)
    348                     return;
    349 
    350                 /**
    351                  * We can do this if we are past end().
    352                  * This means we are the largest.
    353                  */
    354                 if (current_->find_largest() == current_)
    355                     end_ = false;
    356             }
    357     };
    358 
    359     template<class Val, class Ref, class Ptr, class Sz>
     391    template<class Val, class Ref, class Ptr, class CRef, class CPtr, class Sz>
    360392    bool operator==(const rbtree_iterator<Val, Ref, Ptr, Sz>& lhs,
     393                    const rbtree_const_iterator<Val, CRef, CPtr, Sz>& rhs)
     394    {
     395        return (lhs.node() == rhs.node()) && (lhs.end() == rhs.end());
     396    }
     397
     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)
     401    {
     402        return !(lhs == rhs);
     403    }
     404
     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,
    361407                    const rbtree_iterator<Val, Ref, Ptr, Sz>& rhs)
    362408    {
    … …  
    364410    }
    365411
    366     template<class Val, class Ref, class Ptr, class Sz>
    367     bool operator!=(const rbtree_iterator<Val, Ref, Ptr, Sz>& lhs,
     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,
    368414                    const rbtree_iterator<Val, Ref, Ptr, Sz>& rhs)
    369415    {
Note: See TracChangeset for help on using the changeset viewer.