Changeset 7644d6e 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:
a2f01c4
Parents:
369f5df
git-author:
Dzejrou <dzejrou@…> (2018-04-30 20:07:09)
git-committer:
Dzejrou <dzejrou@…> (2018-07-05 21:41:22)
Message:

cpp: moved actual node insertion to the tree and removed repetitious code from policies

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

Legend:

Unmodified
Added
Removed

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

    r369f5df r7644d6e  
    380380            }
    381381
     382            void insert_node(node_type* node, node_type* parent)
     383            {
     384                ++size_;
     385                if (!parent)
     386                    root_ = node;
     387                else
     388                {
     389                    if (keys_comp(get_key(node->value), parent->value))
     390                        parent->add_left_child(node);
     391                    else
     392                        parent->add_right_child(node);
     393
     394                    repair_after_insert_(node);
     395                    update_root_(node);
     396                }
     397            }
     398
    382399        private:
    383400            node_type* root_;

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

    r369f5df r7644d6e  
    171171            auto val = value_type{forward<Args>(args)...};
    172172            auto parent = tree.find_parent_for_insertion(val);
    173             if (!parent)
    174             {
    175                 tree.root_ = new node_type{move(val)};
    176                 ++tree.size_;
    177 
    178                 return make_pair(iterator{tree.root_, false}, true);
    179             }
    180 
    181             if (tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
     173
     174            if (parent && tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
    182175                return make_pair(iterator{parent, false}, false);
    183176
    184177            auto node = new node_type{move(val)};
    185             if (tree.keys_comp(tree.get_key(val), parent->value))
    186                 parent->add_left_child(node);
    187             else
    188                 parent->add_right_child(node);
    189 
    190             ++tree.size_;
    191             tree.repair_after_insert_(node);
    192             tree.update_root_(node);
     178            tree.insert_node(node, parent);
    193179
    194180            return make_pair(iterator{node, false}, true);
    … …  
    204190
    205191            auto parent = tree.find_parent_for_insertion(val);
    206             if (!parent)
    207             {
    208                 tree.root_ = new node_type{val};
    209                 ++tree.size_;
    210 
    211                 return make_pair(iterator{tree.root_}, true);
    212             }
    213 
    214             if (tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
     192            if (parent && tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
    215193                return make_pair(iterator{parent, false}, false);
    216194
    217195            auto node = new node_type{val};
    218             if (tree.keys_comp(tree.get_key(val), parent->value))
    219                 parent->add_left_child(node);
    220             else
    221                 parent->add_right_child(node);
    222 
    223             ++tree.size_;
    224             tree.repair_after_insert_(node);
    225             tree.update_root_(node);
     196            tree.insert_node(node, parent);
    226197
    227198            return make_pair(iterator{node, false}, true);
    … …  
    237208
    238209            auto parent = tree.find_parent_for_insertion(val);
    239             if (!parent)
    240             {
    241                 tree.root_ = new node_type{forward<Value>(val)};
    242                 ++tree.size_;
    243 
    244                 return make_pair(iterator{tree.root_, false}, true);
    245             }
    246 
    247             if (tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
     210            if (parent && tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
    248211                return make_pair(iterator{parent, false}, false);
    249212
    250213            auto node = new node_type{forward<Value>(val)};
    251             if (tree.keys_comp(tree.get_key(val), parent->value))
    252                 parent->add_left_child(node);
    253             else
    254                 parent->add_right_child(node);
    255 
    256             ++tree.size_;
    257             tree.repair_after_insert_(node);
    258             tree.update_root_(node);
     214            tree.insert_node(node, parent);
    259215
    260216            return make_pair(iterator{node, false}, true);
    … …  
    433389
    434390            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);
     391            tree.insert_node(node, parent);
    445392
    446393            return iterator{node, false};
Note: See TracChangeset for help on using the changeset viewer.