LCOV - code coverage report
Current view: top level - src - splay-tree-inl.h (source / functions) Hit Total Coverage
Test: app.info Lines: 81 100 81.0 %
Date: 2017-04-26 Functions: 13 21 61.9 %

          Line data    Source code
       1             : // Copyright 2010 the V8 project authors. All rights reserved.
       2             : // Use of this source code is governed by a BSD-style license that can be
       3             : // found in the LICENSE file.
       4             : 
       5             : #ifndef V8_SPLAY_TREE_INL_H_
       6             : #define V8_SPLAY_TREE_INL_H_
       7             : 
       8             : #include "src/splay-tree.h"
       9             : 
      10             : namespace v8 {
      11             : namespace internal {
      12             : 
      13             : 
      14             : template<typename Config, class Allocator>
      15             : SplayTree<Config, Allocator>::~SplayTree() {
      16             :   NodeDeleter deleter;
      17        3156 :   ForEachNode(&deleter);
      18             : }
      19             : 
      20             : 
      21             : template<typename Config, class Allocator>
      22     2018781 : bool SplayTree<Config, Allocator>::Insert(const Key& key,
      23           0 :                                           Locator* locator) {
      24     2018781 :   if (is_empty()) {
      25             :     // If the tree is empty, insert the new node.
      26      945822 :     root_ = new(allocator_) Node(key, Config::NoValue());
      27             :   } else {
      28             :     // Splay on the key to move the last node on the search path
      29             :     // for the key to the root of the tree.
      30     1545870 :     Splay(key);
      31             :     // Ignore repeated insertions with the same key.
      32     1545870 :     int cmp = Config::Compare(key, root_->key_);
      33     1545870 :     if (cmp == 0) {
      34             :       locator->bind(root_);
      35      783650 :       return false;
      36             :     }
      37             :     // Insert the new node.
      38      762220 :     Node* node = new(allocator_) Node(key, Config::NoValue());
      39             :     InsertInternal(cmp, node);
      40             :   }
      41     1235131 :   locator->bind(root_);
      42     1235131 :   return true;
      43             : }
      44             : 
      45             : 
      46             : template<typename Config, class Allocator>
      47             : void SplayTree<Config, Allocator>::InsertInternal(int cmp, Node* node) {
      48      762220 :   if (cmp > 0) {
      49      390084 :     node->left_ = root_;
      50      390084 :     node->right_ = root_->right_;
      51      390084 :     root_->right_ = NULL;
      52             :   } else {
      53      372136 :     node->right_ = root_;
      54      372136 :     node->left_ = root_->left_;
      55      372136 :     root_->left_ = NULL;
      56             :   }
      57      762220 :   root_ = node;
      58             : }
      59             : 
      60             : 
      61             : template<typename Config, class Allocator>
      62           0 : bool SplayTree<Config, Allocator>::FindInternal(const Key& key) {
      63     4512254 :   if (is_empty())
      64             :     return false;
      65     2075096 :   Splay(key);
      66     2075096 :   return Config::Compare(key, root_->key_) == 0;
      67             : }
      68             : 
      69             : 
      70             : template<typename Config, class Allocator>
      71             : bool SplayTree<Config, Allocator>::Contains(const Key& key) {
      72             :   return FindInternal(key);
      73             : }
      74             : 
      75             : 
      76             : template<typename Config, class Allocator>
      77     4366399 : bool SplayTree<Config, Allocator>::Find(const Key& key, Locator* locator) {
      78     4366399 :   if (FindInternal(key)) {
      79     1012603 :     locator->bind(root_);
      80     1012603 :     return true;
      81             :   } else {
      82             :     return false;
      83             :   }
      84             : }
      85             : 
      86             : 
      87             : template<typename Config, class Allocator>
      88      176139 : bool SplayTree<Config, Allocator>::FindGreatestLessThan(const Key& key,
      89           0 :                                                         Locator* locator) {
      90      176139 :   if (is_empty())
      91             :     return false;
      92             :   // Splay on the key to move the node with the given key or the last
      93             :   // node on the search path to the top of the tree.
      94      176139 :   Splay(key);
      95             :   // Now the result is either the root node or the greatest node in
      96             :   // the left subtree.
      97      176139 :   int cmp = Config::Compare(root_->key_, key);
      98      176139 :   if (cmp <= 0) {
      99             :     locator->bind(root_);
     100      133866 :     return true;
     101             :   } else {
     102             :     Node* temp = root_;
     103       42273 :     root_ = root_->left_;
     104             :     bool result = FindGreatest(locator);
     105       42273 :     root_ = temp;
     106       42273 :     return result;
     107             :   }
     108             : }
     109             : 
     110             : 
     111             : template<typename Config, class Allocator>
     112      185523 : bool SplayTree<Config, Allocator>::FindLeastGreaterThan(const Key& key,
     113           0 :                                                         Locator* locator) {
     114      185523 :   if (is_empty())
     115             :     return false;
     116             :   // Splay on the key to move the node with the given key or the last
     117             :   // node on the search path to the top of the tree.
     118      185523 :   Splay(key);
     119             :   // Now the result is either the root node or the least node in
     120             :   // the right subtree.
     121      185523 :   int cmp = Config::Compare(root_->key_, key);
     122      185523 :   if (cmp >= 0) {
     123             :     locator->bind(root_);
     124       94140 :     return true;
     125             :   } else {
     126             :     Node* temp = root_;
     127       91383 :     root_ = root_->right_;
     128             :     bool result = FindLeast(locator);
     129       91383 :     root_ = temp;
     130       91383 :     return result;
     131             :   }
     132             : }
     133             : 
     134             : 
     135             : template<typename Config, class Allocator>
     136             : bool SplayTree<Config, Allocator>::FindGreatest(Locator* locator) {
     137       42273 :   if (is_empty())
     138             :     return false;
     139             :   Node* current = root_;
     140       40626 :   while (current->right_ != NULL)
     141             :     current = current->right_;
     142             :   locator->bind(current);
     143             :   return true;
     144             : }
     145             : 
     146             : 
     147             : template<typename Config, class Allocator>
     148           0 : bool SplayTree<Config, Allocator>::FindLeast(Locator* locator) {
     149       91383 :   if (is_empty())
     150             :     return false;
     151             :   Node* current = root_;
     152        3904 :   while (current->left_ != NULL)
     153             :     current = current->left_;
     154             :   locator->bind(current);
     155             :   return true;
     156             : }
     157             : 
     158             : 
     159             : template<typename Config, class Allocator>
     160             : bool SplayTree<Config, Allocator>::Move(const Key& old_key,
     161             :                                         const Key& new_key) {
     162             :   if (!FindInternal(old_key))
     163             :     return false;
     164             :   Node* node_to_move = root_;
     165             :   RemoveRootNode(old_key);
     166             :   Splay(new_key);
     167             :   int cmp = Config::Compare(new_key, root_->key_);
     168             :   if (cmp == 0) {
     169             :     // A node with the target key already exists.
     170             :     delete node_to_move;
     171             :     return false;
     172             :   }
     173             :   node_to_move->key_ = new_key;
     174             :   InsertInternal(cmp, node_to_move);
     175             :   return true;
     176             : }
     177             : 
     178             : 
     179             : template<typename Config, class Allocator>
     180           0 : bool SplayTree<Config, Allocator>::Remove(const Key& key) {
     181           0 :   if (!FindInternal(key))
     182             :     return false;
     183           0 :   Node* node_to_remove = root_;
     184           0 :   RemoveRootNode(key);
     185             :   delete node_to_remove;
     186           0 :   return true;
     187             : }
     188             : 
     189             : 
     190             : template<typename Config, class Allocator>
     191           0 : void SplayTree<Config, Allocator>::RemoveRootNode(const Key& key) {
     192           0 :   if (root_->left_ == NULL) {
     193             :     // No left child, so the new tree is just the right child.
     194           0 :     root_ = root_->right_;
     195             :   } else {
     196             :     // Left child exists.
     197           0 :     Node* right = root_->right_;
     198             :     // Make the original left child the new root.
     199           0 :     root_ = root_->left_;
     200             :     // Splay to make sure that the new root has an empty right child.
     201           0 :     Splay(key);
     202             :     // Insert the original right child as the right child of the new
     203             :     // root.
     204           0 :     root_->right_ = right;
     205             :   }
     206           0 : }
     207             : 
     208             : 
     209             : template<typename Config, class Allocator>
     210     3982628 : void SplayTree<Config, Allocator>::Splay(const Key& key) {
     211     3982628 :   if (is_empty())
     212           0 :     return;
     213             :   Node dummy_node(Config::kNoKey, Config::NoValue());
     214             :   // Create a dummy node.  The use of the dummy node is a bit
     215             :   // counter-intuitive: The right child of the dummy node will hold
     216             :   // the L tree of the algorithm.  The left child of the dummy node
     217             :   // will hold the R tree of the algorithm.  Using a dummy node, left
     218             :   // and right will always be nodes and we avoid special cases.
     219             :   Node* dummy = &dummy_node;
     220             :   Node* left = dummy;
     221             :   Node* right = dummy;
     222             :   Node* current = root_;
     223             :   while (true) {
     224     6253809 :     int cmp = Config::Compare(key, current->key_);
     225     6253809 :     if (cmp < 0) {
     226     1850180 :       if (current->left_ == NULL)
     227             :         break;
     228     2397244 :       if (Config::Compare(key, current->left_->key_) < 0) {
     229             :         // Rotate right.
     230             :         Node* temp = current->left_;
     231      472974 :         current->left_ = temp->right_;
     232      472974 :         temp->right_ = current;
     233             :         current = temp;
     234      472974 :         if (current->left_ == NULL)
     235             :           break;
     236             :       }
     237             :       // Link right.
     238     1132599 :       right->left_ = current;
     239             :       right = current;
     240     1132599 :       current = current->left_;
     241     4403629 :     } else if (cmp > 0) {
     242     2571787 :       if (current->right_ == NULL)
     243             :         break;
     244     2466244 :       if (Config::Compare(key, current->right_->key_) > 0) {
     245             :         // Rotate left.
     246             :         Node* temp = current->right_;
     247      633021 :         current->right_ = temp->left_;
     248      633021 :         temp->left_ = current;
     249             :         current = temp;
     250      633021 :         if (current->right_ == NULL)
     251             :           break;
     252             :       }
     253             :       // Link left.
     254     1138582 :       left->right_ = current;
     255             :       left = current;
     256     1138582 :       current = current->right_;
     257             :     } else {
     258             :       break;
     259             :     }
     260             :   }
     261             :   // Assemble.
     262     3982628 :   left->right_ = current->left_;
     263     3982628 :   right->left_ = current->right_;
     264     3982628 :   current->left_ = dummy->right_;
     265     3982628 :   current->right_ = dummy->left_;
     266     3982628 :   root_ = current;
     267             : }
     268             : 
     269             : 
     270             : template <typename Config, class Allocator> template <class Callback>
     271             : void SplayTree<Config, Allocator>::ForEach(Callback* callback) {
     272             :   NodeToPairAdaptor<Callback> callback_adaptor(callback);
     273     2041144 :   ForEachNode(&callback_adaptor);
     274             : }
     275             : 
     276             : 
     277             : template <typename Config, class Allocator> template <class Callback>
     278     2044300 : void SplayTree<Config, Allocator>::ForEachNode(Callback* callback) {
     279     3601270 :   if (root_ == NULL) return;
     280             :   // Pre-allocate some space for tiny trees.
     281             :   List<Node*, Allocator> nodes_to_visit(10, allocator_);
     282      487330 :   nodes_to_visit.Add(root_, allocator_);
     283             :   int pos = 0;
     284     2467104 :   while (pos < nodes_to_visit.length()) {
     285     4477332 :     Node* node = nodes_to_visit[pos++];
     286     1492444 :     if (node->left() != NULL) nodes_to_visit.Add(node->left(), allocator_);
     287     1492444 :     if (node->right() != NULL) nodes_to_visit.Add(node->right(), allocator_);
     288      978299 :     callback->Call(node);
     289             :   }
     290             : }
     291             : 
     292             : 
     293             : }  // namespace internal
     294             : }  // namespace v8
     295             : 
     296             : #endif  // V8_SPLAY_TREE_INL_H_

Generated by: LCOV version 1.10