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