Changeset 21d97e8 in mainline


Ignore:
Timestamp:
2018-07-05T21:41:23Z (6 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
Files:
5 edited

Legend:

Unmodified
Added
Removed

  • uspace/lib/cpp/include/impl/map.hpp

    r5608106c r21d97e8  
    6363            using difference_type = ptrdiff_t;
    6464
     65            using node_type = aux::rbtree_single_node<value_type>;
     66
    6567            using iterator             = aux::rbtree_iterator<
    66                 value_type, reference, pointer, size_type
     68                value_type, reference, pointer, size_type, node_type
    6769            >;
    6870            using const_iterator       = aux::rbtree_const_iterator<
    69                 value_type, const_reference, const_pointer, size_type
     71                value_type, const_reference, const_pointer, size_type, node_type
    7072            >;
    7173
    … …  
    338340            template<class T>
    339341            pair<iterator, bool> insert(
    340                 enable_if_t<is_constructible_v<value_type, T&&>, T&&> val)
     342                T&& val,
     343                enable_if_t<is_constructible_v<value_type, T&&>>* = nullptr
     344            )
    341345            {
    342346                return emplace(forward<T>(val));
    … …  
    356360            iterator insert(
    357361                const_iterator hint,
    358                 enable_if_t<is_constructible_v<value_type, T&&>, T&&> val
     362                T&& val,
     363                enable_if_t<is_constructible_v<value_type, T&&>>* = nullptr
    359364            )
    360365            {
    … …  
    422427                if (parent && tree_.keys_equal(tree_.get_key(parent->value), key))
    423428                {
    424                     parent->value = value_type{key, forward<T>(val)};
     429                    parent->value.second = forward<T>(val);
    425430
    426431                    return make_pair(iterator{parent, false}, false);
    … …  
    441446                if (parent && tree_.keys_equal(tree_.get_key(parent->value), key))
    442447                {
    443                     parent->value = value_type{move(key), forward<T>(val)};
     448                    parent->value.second = forward<T>(val);
    444449
    445450                    return make_pair(iterator{parent, false}, false);
    … …  
    521526            template<class K>
    522527            iterator find(
    523                 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
     528                const K& key,
     529                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
    524530            )
    525531            {
    … …  
    529535            template<class K>
    530536            const_iterator find(
    531                 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
     537                const K& key,
     538                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
    532539            ) const
    533540            {
    … …  
    542549            template<class K>
    543550            size_type count(
    544                 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
     551                const K& key,
     552                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
    545553            ) const
    546554            {
    … …  
    560568            template<class K>
    561569            iterator lower_bound(
    562                 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
     570                const K& key,
     571                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
    563572            )
    564573            {
    … …  
    568577            template<class K>
    569578            const_iterator lower_bound(
    570                 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
     579                const K& key,
     580                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
    571581            ) const
    572582            {
    … …  
    586596            template<class K>
    587597            iterator upper_bound(
    588                 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
     598                const K& key,
     599                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
    589600            )
    590601            {
    … …  
    594605            template<class K>
    595606            const_iterator upper_bound(
    596                 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
     607                const K& key,
     608                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
    597609            ) const
    598610            {
    … …  
    612624            template<class K>
    613625            pair<iterator, iterator> equal_range(
    614                 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
     626                const K& key,
     627                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
    615628            )
    616629            {
    … …  
    620633            template<class K>
    621634            pair<const_iterator, const_iterator> equal_range(
    622                 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
     635                const K& key,
     636                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
    623637            ) const
    624638            {
    … …  
    631645                key_compare, allocator_type, size_type,
    632646                iterator, const_iterator,
    633                 aux::rbtree_single_policy
     647                aux::rbtree_single_policy, node_type
    634648            >;
    635 
    636             using node_type = typename tree_type::node_type;
    637649
    638650            tree_type tree_;
    … …  
    714726            using difference_type = ptrdiff_t;
    715727
     728            using node_type = aux::rbtree_multi_node<value_type>;
     729
    716730            class value_compare
    717731            {
    … …  
    737751
    738752            using iterator             = aux::rbtree_iterator<
    739                 value_type, reference, pointer, size_type
     753                value_type, reference, pointer, size_type, node_type
    740754            >;
    741755            using const_iterator       = aux::rbtree_const_iterator<
    742                 value_type, const_reference, const_pointer, size_type
     756                value_type, const_reference, const_pointer, size_type, node_type
    743757            >;
    744758
    … …  
    937951            template<class T>
    938952            iterator insert(
    939                 enable_if_t<is_constructible_v<value_type, T&&>, T&&> val
     953                T&& val,
     954                enable_if_t<is_constructible_v<value_type, T&&>>* = nullptr
    940955            )
    941956            {
    … …  
    956971            iterator insert(
    957972                const_iterator hint,
    958                 enable_if_t<is_constructible_v<value_type, T&&>, T&&> val
     973                T&& val,
     974                enable_if_t<is_constructible_v<value_type, T&&>>* = nullptr
    959975            )
    960976            {
    … …  
    10291045            template<class K>
    10301046            iterator find(
    1031                 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
     1047                const K& key,
     1048                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
    10321049            )
    10331050            {
    … …  
    10371054            template<class K>
    10381055            const_iterator find(
    1039                 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
     1056                const K& key,
     1057                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
    10401058            ) const
    10411059            {
    … …  
    10501068            template<class K>
    10511069            size_type count(
    1052                 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
     1070                const K& key,
     1071                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
    10531072            ) const
    10541073            {
    … …  
    10681087            template<class K>
    10691088            iterator lower_bound(
    1070                 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
     1089                const K& key,
     1090                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
    10711091            )
    10721092            {
    … …  
    10761096            template<class K>
    10771097            const_iterator lower_bound(
    1078                 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
     1098                const K& key,
     1099                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
    10791100            ) const
    10801101            {
    … …  
    10941115            template<class K>
    10951116            iterator upper_bound(
    1096                 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
     1117                const K& key,
     1118                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
    10971119            )
    10981120            {
    … …  
    11021124            template<class K>
    11031125            const_iterator upper_bound(
    1104                 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
     1126                const K& key,
     1127                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
    11051128            ) const
    11061129            {
    … …  
    11201143            template<class K>
    11211144            pair<iterator, iterator> equal_range(
    1122                 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
     1145                const K& key,
     1146                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
    11231147            )
    11241148            {
    … …  
    11281152            template<class K>
    11291153            pair<const_iterator, const_iterator> equal_range(
    1130                 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
     1154                const K& key,
     1155                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
    11311156            ) const
    11321157            {
    … …  
    11391164                key_compare, allocator_type, size_type,
    11401165                iterator, const_iterator,
    1141                 aux::rbtree_multi_policy
     1166                aux::rbtree_multi_policy, node_type
    11421167            >;
    11431168

  • 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.