Changeset 21d97e8 in mainline for uspace/lib/cpp/include/internal


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:
0fe0f32
Parents:
5608106c
git-author:
Dzejrou <dzejrou@…> (2018-05-14 17:03:57)
git-committer:
Dzejrou <dzejrou@…> (2018-07-05 21:41:23)
Message:

cpp: fixed bugs found by the map tests

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

Legend:

Unmodified
Added
Removed
  • uspace/lib/cpp/include/internal/rbtree.hpp

    r5608106c r21d97e8  
    353353                if (!node)
    354354                    return nullptr;
     355
     356                --size_;
     357
     358                auto succ = node->successor();
    355359                if (auto tmp = node->get_node_for_deletion(); tmp != nullptr)
    356360                {
     
    359363                     * we popped one node from a list of nodes
    360364                     * with equivalent keys and we can delete it
    361                      * and return the original as it is still
    362                      * in place.
     365                     * and return the successor which was the next
     366                     * in the list.
    363367                     */
    364368                    delete tmp;
    365369
    366                     return node;
    367                 }
    368 
    369                 --size_;
    370 
    371                 if (node == root_)
    372                 {
     370                    update_root_(succ); // Incase the first in list was root.
     371                    return succ;
     372                }
     373                else if (node == root_)
     374                { // Only executed if root_ is unique.
     375                    root_ = nullptr;
    373376                    delete node;
    374                     root_ = nullptr;
    375377
    376378                    return nullptr;
    377379                }
    378380
    379                 auto succ = node->successor();
    380381                if (node->left() && node->right())
    381382                {
     
    407408                    else if (node->is_right_child())
    408409                        child->parent()->right(child);
     410                    node->parent(nullptr);
     411                    node->left(nullptr);
     412                    node->right(nullptr);
    409413
    410414                    // Repair if needed.
  • uspace/lib/cpp/include/internal/rbtree_iterators.hpp

    r5608106c r21d97e8  
    7878            rbtree_iterator& operator++()
    7979            {
     80                if (end_)
     81                    return *this;
     82
    8083                if (current_)
    8184                {
     
    102105                if (end_)
    103106                {
    104                     try_undo_end_();
     107                    end_ = false;
    105108
    106109                    return *this;
     
    145148            node_type* current_;
    146149            bool end_;
    147 
    148             void try_undo_end_()
    149             {
    150                 if (!current_)
    151                     return;
    152 
    153                 /**
    154                  * We can do this if we are past end().
    155                  * This means we are the largest.
    156                  */
    157                 if (current_->find_largest() == current_)
    158                     end_ = false;
    159             }
    160150    };
    161151
     
    224214            rbtree_const_iterator& operator++()
    225215            {
     216                if (end_)
     217                    return *this;
     218
    226219                if (current_)
    227220                {
     
    248241                if (end_)
    249242                {
    250                     try_undo_end_();
     243                    end_ = false;
    251244
    252245                    return *this;
     
    286279            const node_type* current_;
    287280            bool end_;
    288 
    289             void try_undo_end_()
    290             {
    291                 if (!current_)
    292                     return;
    293 
    294                 /**
    295                  * We can do this if we are past end().
    296                  * This means we are the largest.
    297                  */
    298                 if (current_->find_largest() == current_)
    299                     end_ = false;
    300             }
    301281    };
    302282
  • uspace/lib/cpp/include/internal/rbtree_node.hpp

    r5608106c r21d97e8  
    4646        {
    4747            if (node && node->parent())
    48                 return node->parent->parent();
     48                return node->parent()->parent();
    4949            else
    5050                return nullptr;
     
    5555            if (node && node->parent())
    5656            {
    57                 if (node == node->parent->left())
    58                     return node->parent->right();
    59                 else
    60                     return node->parent->left();
     57                if (node == node->parent()->left())
     58                    return node->parent()->right();
     59                else
     60                    return node->parent()->left();
    6161            }
    6262            else
     
    573573            const rbtree_multi_node* predecessor() const
    574574            {
    575                 return utils::predecessor(this);
     575                if (this != first_)
     576                {
     577                    auto tmp = first_;
     578                    while (tmp->next_ != this)
     579                        tmp = tmp->next_;
     580
     581                    return tmp;
     582                }
     583                else
     584                {
     585                    auto tmp = utils::predecessor(this);
     586
     587                    /**
     588                     * If tmp was duplicate, we got a pointer
     589                     * to the first node in the list. So we need
     590                     * to move to the end.
     591                     */
     592                    while (tmp->next_ != nullptr)
     593                        tmp = tmp->next_;
     594
     595                    return tmp;
     596                }
    576597            }
    577598
     
    591612            }
    592613
    593             rbtree_multi_node<T>* get_node_for_deletion()
    594             {
     614            rbtree_multi_node* get_node_for_deletion()
     615            {
     616                /**
     617                 * To make sure we delete nodes in
     618                 * the order of their insertion
     619                 * (not required, but sensical), we
     620                 * update then list and return this
     621                 * for deletion.
     622                 */
    595623                if (next_)
    596624                {
    597                     auto tmp = next_;
    598                     while (tmp && tmp->next_ != this)
     625                    // Make next the new this.
     626                    next_->first_ = next_;
     627                    if (is_left_child())
     628                        parent_->left_ = next_;
     629                    else if (is_right_child())
     630                        parent_->right_ = next_;
     631
     632                    if (left_)
     633                        left_->parent_ = next_;
     634                    if (right_)
     635                        right_->parent_ = next_;
     636
     637                    /**
     638                     * Update the first_ pointer
     639                     * of the rest of the list.
     640                     */
     641                    auto tmp = next_->next_;
     642                    while (tmp)
     643                    {
     644                        tmp->first_ = next_;
    599645                        tmp = tmp->next_;
    600 
    601                     return tmp; // This will get deleted.
     646                    }
     647
     648                    /**
     649                     * Otherwise destructor could
     650                     * destroy them.
     651                     */
     652                    parent_ = nullptr;
     653                    left_ = nullptr;
     654                    right_ = nullptr;
     655                    next_ = nullptr;
     656                    first_ = nullptr;
     657
     658                    return this; // This will get deleted.
    602659                }
    603660                else
     
    608665            {
    609666                if (is_left_child())
    610                     parent->left_ = nullptr;
     667                    parent_->left_ = nullptr;
    611668                else if (is_right_child())
    612                     parent->right_ = nullptr;
     669                    parent_->right_ = nullptr;
    613670            }
    614671
  • uspace/lib/cpp/include/internal/rbtree_policies.hpp

    r5608106c r21d97e8  
    277277
    278278            size_type res{};
    279             while (tree.keys_equal(tree.get_key(*it), key))
     279            while (it != tree.end() && tree.keys_equal(tree.get_key(*it), key))
    280280            {
    281281                ++res;
     
    291291            auto it = lower_bound_const(tree, key);
    292292
    293             return typename Tree::iterator{it.node(), it.end()};
     293            return typename Tree::iterator{
     294                const_cast<typename Tree::node_type*>(it.node()), it.end()
     295            };
    294296        }
    295297
     
    328330            auto it = upper_bound_const(tree, key);
    329331
    330             return typename Tree::iterator{it.node(), it.end()};
     332            return typename Tree::iterator{
     333                const_cast<typename Tree::node_type*>(it.node()), it.end()
     334            };
    331335        }
    332336
Note: See TracChangeset for help on using the changeset viewer.