Changeset 647b756 in mainline


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:
369f5df
Parents:
cacb5d0
git-author:
Dzejrou <dzejrou@…> (2018-04-30 19:49:59)
git-committer:
Dzejrou <dzejrou@…> (2018-07-05 21:41:22)
Message:

cpp: removed redundant code, eliminated some more code duplication, added more insert logic to the policy, added multi policy

File:
1 edited

Legend:

Unmodified
Added
Removed

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

    rcacb5d0 r647b756  
    5454                tree.delete_node(it.node());
    5555            return size_type{1};
    56 
    57             // This is the multi version -.-
    58             /* size_type res{}; */
    59             /* while (tree.keys_equal(tree.get_key(*it), key)) */
    60             /* { */
    61             /*     auto node = it.node(); */
    62             /*     ++it; */
    63 
    64             /*     tree->delete_node(node); */
    65             /*     ++res; */
    66             /* } */
    67 
    68             /* return res; */
    69         }
    70 
    71         template<class Tree, class Key>
    72         static typename Tree::iterator lower_bound(Tree& tree, const Key& key)
     56        }
     57
     58        template<class Tree, class Key>
     59        static typename Tree::iterator lower_bound(const Tree& tree, const Key& key)
    7360        {
    7461            using iterator = typename Tree::iterator;
    7562
     63            auto it = lower_bound_const(tree, key);
     64
     65            return iterator{it.node(), it.end()};
     66        }
     67
     68        template<class Tree, class Key>
     69        static typename Tree::const_iterator lower_bound_const(const Tree& tree, const Key& key)
     70        {
     71            using const_iterator = typename Tree::const_iterator;
     72
    7673            auto node = tree.find_parent_for_insertion(key);
    77             iterator it{node, false};
     74            const_iterator it{node, false};
    7875            auto beg = tree.begin();
    7976            auto end = tree.end();
    … …  
    10299
    103100        template<class Tree, class Key>
    104         static typename Tree::const_iterator lower_bound_const(const Tree& tree, const Key& key)
    105         {
    106             using const_iterator = typename Tree::const_iterator;
    107 
    108             auto node = tree.find_parent_for_insertion(key);
    109             const_iterator it{node, false};
    110             auto beg = tree.begin();
    111             auto end = tree.end();
    112 
    113             if (tree.key_compare_(tree.get_key(*it), key))
    114             {
    115                 // Predecessor.
    116                 if (it != end)
    117                     return ++it;
    118                 else
    119                     return it;
    120             }
    121             else if (tree.key_compare_(key, tree.get_key(*it)))
    122             {
    123                 // Successor.
    124                 if (it != beg)
    125                     return --it;
    126                 else
    127                     return it;
    128             }
    129             else // Perfect match.
    130                 return it;
    131 
    132             return it;
    133         }
    134 
    135         template<class Tree, class Key>
    136         static typename Tree::iterator upper_bound(Tree& tree, const Key& key)
    137         {
    138             /**
    139              * If key isn't in the tree, we get it's
    140              * successor or tree.end(). If key is
    141              * in the tree, we get it.
    142              * In the first case, the successor is also
    143              * the upper bound, so we just return it,
    144              * otherwise (as long as it != end()) we
    145              * increment.
    146              */
    147             auto it = lower_bound(tree, key);
    148             if (it == tree.end())
    149                 return it;
    150             else if (tree.keys_equal(key, *it))
    151                 return ++it;
    152             else
    153                 return it;
     101        static typename Tree::iterator upper_bound(const Tree& tree, const Key& key)
     102        {
     103            using iterator = typename Tree::iterator;
     104
     105            auto it = upper_bound_const(tree, key);
     106
     107            return iterator{it.node(), it.end()};
    154108        }
    155109
    … …  
    220174            {
    221175                tree.root_ = new node_type{move(val)};
    222 
    223                 return make_pair(iterator{tree.root_}, true);
     176                ++tree.size_;
     177
     178                return make_pair(iterator{tree.root_, false}, true);
    224179            }
    225180
    226181            if (tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
    227                 return make_pair(iterator{parent}, false);
     182                return make_pair(iterator{parent, false}, false);
    228183
    229184            auto node = new node_type{move(val)};
    … …  
    233188                parent->add_right_child(node);
    234189
    235             return make_pair(iterator{node}, true);
     190            ++tree.size_;
     191            tree.repair_after_insert_(node);
     192            tree.update_root_(node);
     193
     194            return make_pair(iterator{node, false}, true);
    236195        }
    237196
    … …  
    248207            {
    249208                tree.root_ = new node_type{val};
     209                ++tree.size_;
    250210
    251211                return make_pair(iterator{tree.root_}, true);
    … …  
    253213
    254214            if (tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
    255                 return make_pair(iterator{parent}, false);
     215                return make_pair(iterator{parent, false}, false);
    256216
    257217            auto node = new node_type{val};
    … …  
    261221                parent->add_right_child(node);
    262222
    263             return make_pair(iterator{node}, true);
     223            ++tree.size_;
     224            tree.repair_after_insert_(node);
     225            tree.update_root_(node);
     226
     227            return make_pair(iterator{node, false}, true);
    264228        }
    265229
    … …  
    276240            {
    277241                tree.root_ = new node_type{forward<Value>(val)};
    278 
    279                 return make_pair(iterator{tree.root_}, true);
     242                ++tree.size_;
     243
     244                return make_pair(iterator{tree.root_, false}, true);
    280245            }
    281246
    282247            if (tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
    283                 return make_pair(iterator{parent}, false);
     248                return make_pair(iterator{parent, false}, false);
    284249
    285250            auto node = new node_type{forward<Value>(val)};
    … …  
    289254                parent->add_right_child(node);
    290255
    291             return make_pair(iterator{node}, true);
     256            ++tree.size_;
     257            tree.repair_after_insert_(node);
     258            tree.update_root_(node);
     259
     260            return make_pair(iterator{node, false}, true);
    292261        }
    293262    };
    … …  
    295264    struct rbtree_multi_policy
    296265    {
    297         // TODO:
     266        template<class Tree, class Key>
     267        static typename Tree::size_type count(const Tree& tree, const Key& key)
     268        {
     269            using size_type = typename Tree::size_type;
     270
     271            auto it = tree.find(key);
     272            if (it == tree.end())
     273                return size_type{};
     274
     275            size_type res{};
     276            while (tree.keys_equal(tree.get_key(*it), key))
     277            {
     278                ++res;
     279                ++it;
     280            }
     281
     282            return res;
     283        }
     284
     285        template<class Tree, class Key>
     286        static typename Tree::size_type erase(Tree& tree, const Key& key)
     287        {
     288            using size_type = typename Tree::size_type;
     289
     290            auto it = tree.find(key);
     291            if (it == tree.end())
     292                return size_type{};
     293
     294            size_type res{};
     295            while (tree.keys_equal(tree.get_key(*it), key))
     296            {
     297                ++res;
     298                it = tree.erase(it);
     299            }
     300
     301            return res;
     302        }
     303
     304        template<class Tree, class Key>
     305        static typename Tree::iterator lower_bound(const Tree& tree, const Key& key)
     306        {
     307            auto it = lower_bound_const(tree, key);
     308
     309            return typename Tree::iterator{it.node(), it.end()};
     310        }
     311
     312        template<class Tree, class Key>
     313        static typename Tree::const_iterator lower_bound_const(const Tree& tree, const Key& key)
     314        {
     315            using const_iterator = typename Tree::const_iterator;
     316
     317            auto node = tree.find_parent_for_insertion(key);
     318            const_iterator it{node, false};
     319            auto beg = tree.begin();
     320            auto end = tree.end();
     321
     322            if (tree.keys_comp(key, *it))
     323                --it; // Incase we are on a successor.
     324            while (tree.keys_equal(tree.get_key(*it), key) && it != beg)
     325                --it; // Skip keys that are equal.
     326            if (it != beg)
     327                ++it; // If we moved all the way to the start, key is the smallest.
     328
     329            if (tree.key_compare_(tree.get_key(*it), key))
     330            {
     331                // Predecessor.
     332                if (it != end)
     333                    return ++it;
     334                else
     335                    return it;
     336            }
     337
     338            return it;
     339        }
     340
     341        template<class Tree, class Key>
     342        static typename Tree::iterator upper_bound(const Tree& tree, const Key& key)
     343        {
     344            auto it = upper_bound_const(tree, key);
     345
     346            return typename Tree::iterator{it.node(), it.end()};
     347        }
     348
     349        template<class Tree, class Key>
     350        static typename Tree::const_iterator upper_bound_const(const Tree& tree, const Key& key)
     351        {
     352            /**
     353             * If key isn't in the tree, we get it's
     354             * successor or tree.end(). If key is
     355             * in the tree, we get it.
     356             * In the first case, the successor is also
     357             * the upper bound, so we just return it,
     358             * otherwise (as long as it != end()) we
     359             * increment.
     360             */
     361            auto it = lower_bound(tree, key);
     362            if (it == tree.end())
     363                return it;
     364            else if (tree.keys_equal(tree.get_key(*it), key))
     365            {
     366                while (tree.keys_equal(tree.get_key(*it), key))
     367                    ++it;
     368
     369                return it;
     370            }
     371
     372            return it;
     373        }
     374
     375        template<class Tree, class Key>
     376        static pair<
     377            typename Tree::iterator,
     378            typename Tree::iterator
     379        > equal_range(const Tree& tree, const Key& key)
     380        {
     381            return make_pair(
     382                lower_bound(tree, key),
     383                upper_bound(tree, key)
     384            );
     385        }
     386
     387        template<class Tree, class Key>
     388        static pair<
     389            typename Tree::const_iterator,
     390            typename Tree::const_iterator
     391        > equal_range_const(const Tree& tree, const Key& key)
     392        {
     393            return make_pair(
     394                lower_bound_const(tree, key),
     395                upper_bound_const(tree, key)
     396            );
     397        }
     398
     399        template<class Tree, class... Args>
     400        static typename Tree::iterator emplace(Tree& tree, Args&&... args)
     401        {
     402            using node_type  = typename Tree::node_type;
     403
     404            auto node = node_type{forward<Args>(args)...};
     405
     406            return insert(tree, node);
     407        }
     408
     409        template<class Tree, class Value>
     410        static typename Tree::iterator insert(Tree& tree, const Value& val)
     411        {
     412            using node_type = typename Tree::node_type;
     413
     414            auto node = new node_type{val};
     415
     416            return insert(tree, node);
     417        }
     418
     419        template<class Tree, class Value>
     420        static typename Tree::iterator insert(Tree& tree, Value&& val)
     421        {
     422            using node_type = typename Tree::node_type;
     423
     424            auto node = new node_type{forward<Value>(val)};
     425
     426            return insert(tree, node);
     427        }
     428
     429        template<class Tree>
     430        static typename Tree::iterator insert(Tree& tree, typename Tree::node_type* node)
     431        {
     432            using iterator  = typename Tree::iterator;
     433
     434            auto parent = tree.find_parent_for_insertion(node->value);
     435            if (!parent)
     436                tree.root_ = node;
     437            else if (tree.keys_comp(tree.get_key(node->value), parent->value))
     438                parent->add_left_child(node);
     439            else
     440                parent->add_right_child(node);
     441
     442            ++tree.size_;
     443            tree.repair_after_insert_(node);
     444            tree.update_root_(node);
     445
     446            return iterator{node, false};
     447        }
    298448    };
    299449}
Note: See TracChangeset for help on using the changeset viewer.