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 33namespace v8 { 34namespace internal { 35 36 37template<typename Config, class Allocator> 38SplayTree<Config, Allocator>::~SplayTree() { 39 NodeDeleter deleter; 40 ForEachNode(&deleter); 41} 42 43 44template<typename Config, class Allocator> 45bool 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 69template<typename Config, class Allocator> 70void 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 84template<typename Config, class Allocator> 85bool 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 93template<typename Config, class Allocator> 94bool SplayTree<Config, Allocator>::Contains(const Key& key) { 95 return FindInternal(key); 96} 97 98 99template<typename Config, class Allocator> 100bool 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 110template<typename Config, class Allocator> 111bool 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 134template<typename Config, class Allocator> 135bool 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 158template<typename Config, class Allocator> 159bool 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 170template<typename Config, class Allocator> 171bool 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 182template<typename Config, class Allocator> 183bool 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 202template<typename Config, class Allocator> 203bool 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 213template<typename Config, class Allocator> 214void 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 232template<typename Config, class Allocator> 233void 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 293template <typename Config, class Allocator> template <class Callback> 294void SplayTree<Config, Allocator>::ForEach(Callback* callback) { 295 NodeToPairAdaptor<Callback> callback_adaptor(callback); 296 ForEachNode(&callback_adaptor); 297} 298 299 300template <typename Config, class Allocator> template <class Callback> 301void 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