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 ForEachNode(&deleter); 18 } 19 20 21 template<typename Config, class Allocator> 22 bool SplayTree<Config, Allocator>::Insert(const Key& key, 23 Locator* locator) { 24 if (is_empty()) { 25 // If the tree is empty, insert the new node. 26 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 Splay(key); 31 // Ignore repeated insertions with the same key. 32 int cmp = Config::Compare(key, root_->key_); 33 if (cmp == 0) { 34 locator->bind(root_); 35 return false; 36 } 37 // Insert the new node. 38 Node* node = new(allocator_) Node(key, Config::NoValue()); 39 InsertInternal(cmp, node); 40 } 41 locator->bind(root_); 42 return true; 43 } 44 45 46 template<typename Config, class Allocator> 47 void SplayTree<Config, Allocator>::InsertInternal(int cmp, Node* node) { 48 if (cmp > 0) { 49 node->left_ = root_; 50 node->right_ = root_->right_; 51 root_->right_ = NULL; 52 } else { 53 node->right_ = root_; 54 node->left_ = root_->left_; 55 root_->left_ = NULL; 56 } 57 root_ = node; 58 } 59 60 61 template<typename Config, class Allocator> 62 bool SplayTree<Config, Allocator>::FindInternal(const Key& key) { 63 if (is_empty()) 64 return false; 65 Splay(key); 66 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 bool SplayTree<Config, Allocator>::Find(const Key& key, Locator* locator) { 78 if (FindInternal(key)) { 79 locator->bind(root_); 80 return true; 81 } else { 82 return false; 83 } 84 } 85 86 87 template<typename Config, class Allocator> 88 bool SplayTree<Config, Allocator>::FindGreatestLessThan(const Key& key, 89 Locator* locator) { 90 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 Splay(key); 95 // Now the result is either the root node or the greatest node in 96 // the left subtree. 97 int cmp = Config::Compare(root_->key_, key); 98 if (cmp <= 0) { 99 locator->bind(root_); 100 return true; 101 } else { 102 Node* temp = root_; 103 root_ = root_->left_; 104 bool result = FindGreatest(locator); 105 root_ = temp; 106 return result; 107 } 108 } 109 110 111 template<typename Config, class Allocator> 112 bool SplayTree<Config, Allocator>::FindLeastGreaterThan(const Key& key, 113 Locator* locator) { 114 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 Splay(key); 119 // Now the result is either the root node or the least node in 120 // the right subtree. 121 int cmp = Config::Compare(root_->key_, key); 122 if (cmp >= 0) { 123 locator->bind(root_); 124 return true; 125 } else { 126 Node* temp = root_; 127 root_ = root_->right_; 128 bool result = FindLeast(locator); 129 root_ = temp; 130 return result; 131 } 132 } 133 134 135 template<typename Config, class Allocator> 136 bool SplayTree<Config, Allocator>::FindGreatest(Locator* locator) { 137 if (is_empty()) 138 return false; 139 Node* current = root_; 140 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 bool SplayTree<Config, Allocator>::FindLeast(Locator* locator) { 149 if (is_empty()) 150 return false; 151 Node* current = root_; 152 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 bool SplayTree<Config, Allocator>::Remove(const Key& key) { 181 if (!FindInternal(key)) 182 return false; 183 Node* node_to_remove = root_; 184 RemoveRootNode(key); 185 delete node_to_remove; 186 return true; 187 } 188 189 190 template<typename Config, class Allocator> 191 void SplayTree<Config, Allocator>::RemoveRootNode(const Key& key) { 192 if (root_->left_ == NULL) { 193 // No left child, so the new tree is just the right child. 194 root_ = root_->right_; 195 } else { 196 // Left child exists. 197 Node* right = root_->right_; 198 // Make the original left child the new root. 199 root_ = root_->left_; 200 // Splay to make sure that the new root has an empty right child. 201 Splay(key); 202 // Insert the original right child as the right child of the new 203 // root. 204 root_->right_ = right; 205 } 206 } 207 208 209 template<typename Config, class Allocator> 210 void SplayTree<Config, Allocator>::Splay(const Key& key) { 211 if (is_empty()) 212 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 int cmp = Config::Compare(key, current->key_); 225 if (cmp < 0) { 226 if (current->left_ == NULL) 227 break; 228 if (Config::Compare(key, current->left_->key_) < 0) { 229 // Rotate right. 230 Node* temp = current->left_; 231 current->left_ = temp->right_; 232 temp->right_ = current; 233 current = temp; 234 if (current->left_ == NULL) 235 break; 236 } 237 // Link right. 238 right->left_ = current; 239 right = current; 240 current = current->left_; 241 } else if (cmp > 0) { 242 if (current->right_ == NULL) 243 break; 244 if (Config::Compare(key, current->right_->key_) > 0) { 245 // Rotate left. 246 Node* temp = current->right_; 247 current->right_ = temp->left_; 248 temp->left_ = current; 249 current = temp; 250 if (current->right_ == NULL) 251 break; 252 } 253 // Link left. 254 left->right_ = current; 255 left = current; 256 current = current->right_; 257 } else { 258 break; 259 } 260 } 261 // Assemble. 262 left->right_ = current->left_; 263 right->left_ = current->right_; 264 current->left_ = dummy->right_; 265 current->right_ = dummy->left_; 266 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 ForEachNode(&callback_adaptor); 274 } 275 276 277 template <typename Config, class Allocator> template <class Callback> 278 void SplayTree<Config, Allocator>::ForEachNode(Callback* callback) { 279 if (root_ == NULL) return; 280 // Pre-allocate some space for tiny trees. 281 List<Node*, Allocator> nodes_to_visit(10, allocator_); 282 nodes_to_visit.Add(root_, allocator_); 283 int pos = 0; 284 while (pos < nodes_to_visit.length()) { 285 Node* node = nodes_to_visit[pos++]; 286 if (node->left() != NULL) nodes_to_visit.Add(node->left(), allocator_); 287 if (node->right() != NULL) nodes_to_visit.Add(node->right(), allocator_); 288 callback->Call(node); 289 } 290 } 291 292 293 } // namespace internal 294 } // namespace v8 295 296 #endif // V8_SPLAY_TREE_INL_H_ 297
