Home | History | Annotate | Download | only in src
      1 // Copyright 2010 the V8 project authors. All rights reserved.
      2 // Redistribution and use in source and binary forms, with or without
      3 // modification, are permitted provided that the following conditions are
      4 // met:
      5 //
      6 //     * Redistributions of source code must retain the above copyright
      7 //       notice, this list of conditions and the following disclaimer.
      8 //     * Redistributions in binary form must reproduce the above
      9 //       copyright notice, this list of conditions and the following
     10 //       disclaimer in the documentation and/or other materials provided
     11 //       with the distribution.
     12 //     * Neither the name of Google Inc. nor the names of its
     13 //       contributors may be used to endorse or promote products derived
     14 //       from this software without specific prior written permission.
     15 //
     16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
     17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
     18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
     19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
     20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
     21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
     22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
     26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     27 
     28 #ifndef V8_SPLAY_TREE_INL_H_
     29 #define V8_SPLAY_TREE_INL_H_
     30 
     31 #include "splay-tree.h"
     32 
     33 namespace v8 {
     34 namespace internal {
     35 
     36 
     37 template<typename Config, class Allocator>
     38 SplayTree<Config, Allocator>::~SplayTree() {
     39   NodeDeleter deleter;
     40   ForEachNode(&deleter);
     41 }
     42 
     43 
     44 template<typename Config, class Allocator>
     45 bool SplayTree<Config, Allocator>::Insert(const Key& key,
     46                                           Locator* locator) {
     47   if (is_empty()) {
     48     // If the tree is empty, insert the new node.
     49     root_ = new(allocator_) Node(key, Config::NoValue());
     50   } else {
     51     // Splay on the key to move the last node on the search path
     52     // for the key to the root of the tree.
     53     Splay(key);
     54     // Ignore repeated insertions with the same key.
     55     int cmp = Config::Compare(key, root_->key_);
     56     if (cmp == 0) {
     57       locator->bind(root_);
     58       return false;
     59     }
     60     // Insert the new node.
     61     Node* node = new(allocator_) Node(key, Config::NoValue());
     62     InsertInternal(cmp, node);
     63   }
     64   locator->bind(root_);
     65   return true;
     66 }
     67 
     68 
     69 template<typename Config, class Allocator>
     70 void SplayTree<Config, Allocator>::InsertInternal(int cmp, Node* node) {
     71   if (cmp > 0) {
     72     node->left_ = root_;
     73     node->right_ = root_->right_;
     74     root_->right_ = NULL;
     75   } else {
     76     node->right_ = root_;
     77     node->left_ = root_->left_;
     78     root_->left_ = NULL;
     79   }
     80   root_ = node;
     81 }
     82 
     83 
     84 template<typename Config, class Allocator>
     85 bool SplayTree<Config, Allocator>::FindInternal(const Key& key) {
     86   if (is_empty())
     87     return false;
     88   Splay(key);
     89   return Config::Compare(key, root_->key_) == 0;
     90 }
     91 
     92 
     93 template<typename Config, class Allocator>
     94 bool SplayTree<Config, Allocator>::Contains(const Key& key) {
     95   return FindInternal(key);
     96 }
     97 
     98 
     99 template<typename Config, class Allocator>
    100 bool SplayTree<Config, Allocator>::Find(const Key& key, Locator* locator) {
    101   if (FindInternal(key)) {
    102     locator->bind(root_);
    103     return true;
    104   } else {
    105     return false;
    106   }
    107 }
    108 
    109 
    110 template<typename Config, class Allocator>
    111 bool SplayTree<Config, Allocator>::FindGreatestLessThan(const Key& key,
    112                                                         Locator* locator) {
    113   if (is_empty())
    114     return false;
    115   // Splay on the key to move the node with the given key or the last
    116   // node on the search path to the top of the tree.
    117   Splay(key);
    118   // Now the result is either the root node or the greatest node in
    119   // the left subtree.
    120   int cmp = Config::Compare(root_->key_, key);
    121   if (cmp <= 0) {
    122     locator->bind(root_);
    123     return true;
    124   } else {
    125     Node* temp = root_;
    126     root_ = root_->left_;
    127     bool result = FindGreatest(locator);
    128     root_ = temp;
    129     return result;
    130   }
    131 }
    132 
    133 
    134 template<typename Config, class Allocator>
    135 bool SplayTree<Config, Allocator>::FindLeastGreaterThan(const Key& key,
    136                                                         Locator* locator) {
    137   if (is_empty())
    138     return false;
    139   // Splay on the key to move the node with the given key or the last
    140   // node on the search path to the top of the tree.
    141   Splay(key);
    142   // Now the result is either the root node or the least node in
    143   // the right subtree.
    144   int cmp = Config::Compare(root_->key_, key);
    145   if (cmp >= 0) {
    146     locator->bind(root_);
    147     return true;
    148   } else {
    149     Node* temp = root_;
    150     root_ = root_->right_;
    151     bool result = FindLeast(locator);
    152     root_ = temp;
    153     return result;
    154   }
    155 }
    156 
    157 
    158 template<typename Config, class Allocator>
    159 bool SplayTree<Config, Allocator>::FindGreatest(Locator* locator) {
    160   if (is_empty())
    161     return false;
    162   Node* current = root_;
    163   while (current->right_ != NULL)
    164     current = current->right_;
    165   locator->bind(current);
    166   return true;
    167 }
    168 
    169 
    170 template<typename Config, class Allocator>
    171 bool SplayTree<Config, Allocator>::FindLeast(Locator* locator) {
    172   if (is_empty())
    173     return false;
    174   Node* current = root_;
    175   while (current->left_ != NULL)
    176     current = current->left_;
    177   locator->bind(current);
    178   return true;
    179 }
    180 
    181 
    182 template<typename Config, class Allocator>
    183 bool SplayTree<Config, Allocator>::Move(const Key& old_key,
    184                                         const Key& new_key) {
    185   if (!FindInternal(old_key))
    186     return false;
    187   Node* node_to_move = root_;
    188   RemoveRootNode(old_key);
    189   Splay(new_key);
    190   int cmp = Config::Compare(new_key, root_->key_);
    191   if (cmp == 0) {
    192     // A node with the target key already exists.
    193     delete node_to_move;
    194     return false;
    195   }
    196   node_to_move->key_ = new_key;
    197   InsertInternal(cmp, node_to_move);
    198   return true;
    199 }
    200 
    201 
    202 template<typename Config, class Allocator>
    203 bool SplayTree<Config, Allocator>::Remove(const Key& key) {
    204   if (!FindInternal(key))
    205     return false;
    206   Node* node_to_remove = root_;
    207   RemoveRootNode(key);
    208   delete node_to_remove;
    209   return true;
    210 }
    211 
    212 
    213 template<typename Config, class Allocator>
    214 void SplayTree<Config, Allocator>::RemoveRootNode(const Key& key) {
    215   if (root_->left_ == NULL) {
    216     // No left child, so the new tree is just the right child.
    217     root_ = root_->right_;
    218   } else {
    219     // Left child exists.
    220     Node* right = root_->right_;
    221     // Make the original left child the new root.
    222     root_ = root_->left_;
    223     // Splay to make sure that the new root has an empty right child.
    224     Splay(key);
    225     // Insert the original right child as the right child of the new
    226     // root.
    227     root_->right_ = right;
    228   }
    229 }
    230 
    231 
    232 template<typename Config, class Allocator>
    233 void SplayTree<Config, Allocator>::Splay(const Key& key) {
    234   if (is_empty())
    235     return;
    236   Node dummy_node(Config::kNoKey, Config::NoValue());
    237   // Create a dummy node.  The use of the dummy node is a bit
    238   // counter-intuitive: The right child of the dummy node will hold
    239   // the L tree of the algorithm.  The left child of the dummy node
    240   // will hold the R tree of the algorithm.  Using a dummy node, left
    241   // and right will always be nodes and we avoid special cases.
    242   Node* dummy = &dummy_node;
    243   Node* left = dummy;
    244   Node* right = dummy;
    245   Node* current = root_;
    246   while (true) {
    247     int cmp = Config::Compare(key, current->key_);
    248     if (cmp < 0) {
    249       if (current->left_ == NULL)
    250         break;
    251       if (Config::Compare(key, current->left_->key_) < 0) {
    252         // Rotate right.
    253         Node* temp = current->left_;
    254         current->left_ = temp->right_;
    255         temp->right_ = current;
    256         current = temp;
    257         if (current->left_ == NULL)
    258           break;
    259       }
    260       // Link right.
    261       right->left_ = current;
    262       right = current;
    263       current = current->left_;
    264     } else if (cmp > 0) {
    265       if (current->right_ == NULL)
    266         break;
    267       if (Config::Compare(key, current->right_->key_) > 0) {
    268         // Rotate left.
    269         Node* temp = current->right_;
    270         current->right_ = temp->left_;
    271         temp->left_ = current;
    272         current = temp;
    273         if (current->right_ == NULL)
    274           break;
    275       }
    276       // Link left.
    277       left->right_ = current;
    278       left = current;
    279       current = current->right_;
    280     } else {
    281       break;
    282     }
    283   }
    284   // Assemble.
    285   left->right_ = current->left_;
    286   right->left_ = current->right_;
    287   current->left_ = dummy->right_;
    288   current->right_ = dummy->left_;
    289   root_ = current;
    290 }
    291 
    292 
    293 template <typename Config, class Allocator> template <class Callback>
    294 void SplayTree<Config, Allocator>::ForEach(Callback* callback) {
    295   NodeToPairAdaptor<Callback> callback_adaptor(callback);
    296   ForEachNode(&callback_adaptor);
    297 }
    298 
    299 
    300 template <typename Config, class Allocator> template <class Callback>
    301 void SplayTree<Config, Allocator>::ForEachNode(Callback* callback) {
    302   if (root_ == NULL) return;
    303   // Pre-allocate some space for tiny trees.
    304   List<Node*, Allocator> nodes_to_visit(10, allocator_);
    305   nodes_to_visit.Add(root_, allocator_);
    306   int pos = 0;
    307   while (pos < nodes_to_visit.length()) {
    308     Node* node = nodes_to_visit[pos++];
    309     if (node->left() != NULL) nodes_to_visit.Add(node->left(), allocator_);
    310     if (node->right() != NULL) nodes_to_visit.Add(node->right(), allocator_);
    311     callback->Call(node);
    312   }
    313 }
    314 
    315 
    316 } }  // namespace v8::internal
    317 
    318 #endif  // V8_SPLAY_TREE_INL_H_
    319