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_ 311
