src/3rdparty/v8/src/splay-tree-inl.h

   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, Locator* locator) {
  46   if (is_empty()) {
  47     // If the tree is empty, insert the new node.
  48     root_ = new Node(key, Config::NoValue());
  49   } else {
  50     // Splay on the key to move the last node on the search path
  51     // for the key to the root of the tree.
  52     Splay(key);
  53     // Ignore repeated insertions with the same key.
  54     int cmp = Config::Compare(key, root_->key_);
  55     if (cmp == 0) {
  56       locator->bind(root_);
  57       return false;
  58     }
  59     // Insert the new node.
  60     Node* node = new Node(key, Config::NoValue());
  61     InsertInternal(cmp, node);
  62   }
  63   locator->bind(root_);
  64   return true;
  65 }
  66
  67
  68 template<typename Config, class Allocator>
  69 void SplayTree<Config, Allocator>::InsertInternal(int cmp, Node* node) {
  70   if (cmp > 0) {
  71     node->left_ = root_;
  72     node->right_ = root_->right_;
  73     root_->right_ = NULL;
  74   } else {
  75     node->right_ = root_;
  76     node->left_ = root_->left_;
  77     root_->left_ = NULL;
  78   }
  79   root_ = node;
  80 }
  81
  82
  83 template<typename Config, class Allocator>
  84 bool SplayTree<Config, Allocator>::FindInternal(const Key& key) {
  85   if (is_empty())
  86     return false;
  87   Splay(key);
  88   return Config::Compare(key, root_->key_) == 0;
  89 }
  90
  91
  92 template<typename Config, class Allocator>
  93 bool SplayTree<Config, Allocator>::Find(const Key& key, Locator* locator) {
  94   if (FindInternal(key)) {
  95     locator->bind(root_);
  96     return true;
  97   } else {
  98     return false;
  99   }
 100 }
 101
 102
 103 template<typename Config, class Allocator>
 104 bool SplayTree<Config, Allocator>::FindGreatestLessThan(const Key& key,
 105                                                         Locator* locator) {
 106   if (is_empty())
 107     return false;
 108   // Splay on the key to move the node with the given key or the last
 109   // node on the search path to the top of the tree.
 110   Splay(key);
 111   // Now the result is either the root node or the greatest node in
 112   // the left subtree.
 113   int cmp = Config::Compare(root_->key_, key);
 114   if (cmp <= 0) {
 115     locator->bind(root_);
 116     return true;
 117   } else {
 118     Node* temp = root_;
 119     root_ = root_->left_;
 120     bool result = FindGreatest(locator);
 121     root_ = temp;
 122     return result;
 123   }
 124 }
 125
 126
 127 template<typename Config, class Allocator>
 128 bool SplayTree<Config, Allocator>::FindLeastGreaterThan(const Key& key,
 129                                                         Locator* locator) {
 130   if (is_empty())
 131     return false;
 132   // Splay on the key to move the node with the given key or the last
 133   // node on the search path to the top of the tree.
 134   Splay(key);
 135   // Now the result is either the root node or the least node in
 136   // the right subtree.
 137   int cmp = Config::Compare(root_->key_, key);
 138   if (cmp >= 0) {
 139     locator->bind(root_);
 140     return true;
 141   } else {
 142     Node* temp = root_;
 143     root_ = root_->right_;
 144     bool result = FindLeast(locator);
 145     root_ = temp;
 146     return result;
 147   }
 148 }
 149
 150
 151 template<typename Config, class Allocator>
 152 bool SplayTree<Config, Allocator>::FindGreatest(Locator* locator) {
 153   if (is_empty())
 154     return false;
 155   Node* current = root_;
 156   while (current->right_ != NULL)
 157     current = current->right_;
 158   locator->bind(current);
 159   return true;
 160 }
 161
 162
 163 template<typename Config, class Allocator>
 164 bool SplayTree<Config, Allocator>::FindLeast(Locator* locator) {
 165   if (is_empty())
 166     return false;
 167   Node* current = root_;
 168   while (current->left_ != NULL)
 169     current = current->left_;
 170   locator->bind(current);
 171   return true;
 172 }
 173
 174
 175 template<typename Config, class Allocator>
 176 bool SplayTree<Config, Allocator>::Move(const Key& old_key,
 177                                         const Key& new_key) {
 178   if (!FindInternal(old_key))
 179     return false;
 180   Node* node_to_move = root_;
 181   RemoveRootNode(old_key);
 182   Splay(new_key);
 183   int cmp = Config::Compare(new_key, root_->key_);
 184   if (cmp == 0) {
 185     // A node with the target key already exists.
 186     delete node_to_move;
 187     return false;
 188   }
 189   node_to_move->key_ = new_key;
 190   InsertInternal(cmp, node_to_move);
 191   return true;
 192 }
 193
 194
 195 template<typename Config, class Allocator>
 196 bool SplayTree<Config, Allocator>::Remove(const Key& key) {
 197   if (!FindInternal(key))
 198     return false;
 199   Node* node_to_remove = root_;
 200   RemoveRootNode(key);
 201   delete node_to_remove;
 202   return true;
 203 }
 204
 205
 206 template<typename Config, class Allocator>
 207 void SplayTree<Config, Allocator>::RemoveRootNode(const Key& key) {
 208   if (root_->left_ == NULL) {
 209     // No left child, so the new tree is just the right child.
 210     root_ = root_->right_;
 211   } else {
 212     // Left child exists.
 213     Node* right = root_->right_;
 214     // Make the original left child the new root.
 215     root_ = root_->left_;
 216     // Splay to make sure that the new root has an empty right child.
 217     Splay(key);
 218     // Insert the original right child as the right child of the new
 219     // root.
 220     root_->right_ = right;
 221   }
 222 }
 223
 224
 225 template<typename Config, class Allocator>
 226 void SplayTree<Config, Allocator>::Splay(const Key& key) {
 227   if (is_empty())
 228     return;
 229   Node dummy_node(Config::kNoKey, Config::NoValue());
 230   // Create a dummy node.  The use of the dummy node is a bit
 231   // counter-intuitive: The right child of the dummy node will hold
 232   // the L tree of the algorithm.  The left child of the dummy node
 233   // will hold the R tree of the algorithm.  Using a dummy node, left
 234   // and right will always be nodes and we avoid special cases.
 235   Node* dummy = &dummy_node;
 236   Node* left = dummy;
 237   Node* right = dummy;
 238   Node* current = root_;
 239   while (true) {
 240     int cmp = Config::Compare(key, current->key_);
 241     if (cmp < 0) {
 242       if (current->left_ == NULL)
 243         break;
 244       if (Config::Compare(key, current->left_->key_) < 0) {
 245         // Rotate right.
 246         Node* temp = current->left_;
 247         current->left_ = temp->right_;
 248         temp->right_ = current;
 249         current = temp;
 250         if (current->left_ == NULL)
 251           break;
 252       }
 253       // Link right.
 254       right->left_ = current;
 255       right = current;
 256       current = current->left_;
 257     } else if (cmp > 0) {
 258       if (current->right_ == NULL)
 259         break;
 260       if (Config::Compare(key, current->right_->key_) > 0) {
 261         // Rotate left.
 262         Node* temp = current->right_;
 263         current->right_ = temp->left_;
 264         temp->left_ = current;
 265         current = temp;
 266         if (current->right_ == NULL)
 267           break;
 268       }
 269       // Link left.
 270       left->right_ = current;
 271       left = current;
 272       current = current->right_;
 273     } else {
 274       break;
 275     }
 276   }
 277   // Assemble.
 278   left->right_ = current->left_;
 279   right->left_ = current->right_;
 280   current->left_ = dummy->right_;
 281   current->right_ = dummy->left_;
 282   root_ = current;
 283 }
 284
 285
 286 template <typename Config, class Allocator> template <class Callback>
 287 void SplayTree<Config, Allocator>::ForEach(Callback* callback) {
 288   NodeToPairAdaptor<Callback> callback_adaptor(callback);
 289   ForEachNode(&callback_adaptor);
 290 }
 291
 292
 293 template <typename Config, class Allocator> template <class Callback>
 294 void SplayTree<Config, Allocator>::ForEachNode(Callback* callback) {
 295   // Pre-allocate some space for tiny trees.
 296   List<Node*, Allocator> nodes_to_visit(10);
 297   if (root_ != NULL) nodes_to_visit.Add(root_);
 298   int pos = 0;
 299   while (pos < nodes_to_visit.length()) {
 300     Node* node = nodes_to_visit[pos++];
 301     if (node->left() != NULL) nodes_to_visit.Add(node->left());
 302     if (node->right() != NULL) nodes_to_visit.Add(node->right());
 303     callback->Call(node);
 304   }
 305 }
 306
 307
 308 } }  // namespace v8::internal
 309
 310 #endif  // V8_SPLAY_TREE_INL_H_