OLD | NEW |
1 // Copyright 2006-2008 the V8 project authors. All rights reserved. | 1 // Copyright 2006-2008 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 50 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
61 return segment_bytes_allocated_ > zone_excess_limit_; | 61 return segment_bytes_allocated_ > zone_excess_limit_; |
62 } | 62 } |
63 | 63 |
64 | 64 |
65 void Zone::adjust_segment_bytes_allocated(int delta) { | 65 void Zone::adjust_segment_bytes_allocated(int delta) { |
66 segment_bytes_allocated_ += delta; | 66 segment_bytes_allocated_ += delta; |
67 Counters::zone_segment_bytes.Set(segment_bytes_allocated_); | 67 Counters::zone_segment_bytes.Set(segment_bytes_allocated_); |
68 } | 68 } |
69 | 69 |
70 | 70 |
| 71 template <typename C> |
| 72 bool ZoneSplayTree<C>::Insert(const Key& key, Locator* locator) { |
| 73 if (is_empty()) { |
| 74 // If the tree is empty, insert the new node. |
| 75 root_ = new Node(key, C::kNoValue); |
| 76 } else { |
| 77 // Splay on the key to move the last node on the search path |
| 78 // for the key to the root of the tree. |
| 79 Splay(key); |
| 80 // Ignore repeated insertions with the same key. |
| 81 int cmp = C::Compare(key, root_->key_); |
| 82 if (cmp == 0) { |
| 83 locator->bind(root_); |
| 84 return false; |
| 85 } |
| 86 // Insert the new node. |
| 87 Node* node = new Node(key, C::kNoValue); |
| 88 if (cmp > 0) { |
| 89 node->left_ = root_; |
| 90 node->right_ = root_->right_; |
| 91 root_->right_ = NULL; |
| 92 } else { |
| 93 node->right_ = root_; |
| 94 node->left_ = root_->left_; |
| 95 root_->left_ = NULL; |
| 96 } |
| 97 root_ = node; |
| 98 } |
| 99 locator->bind(root_); |
| 100 return true; |
| 101 } |
| 102 |
| 103 |
| 104 template <typename C> |
| 105 bool ZoneSplayTree<C>::Find(const Key& key, Locator* locator) { |
| 106 if (is_empty()) |
| 107 return false; |
| 108 Splay(key); |
| 109 if (C::Compare(key, root_->key_) == 0) { |
| 110 locator->bind(root_); |
| 111 return true; |
| 112 } else { |
| 113 return false; |
| 114 } |
| 115 } |
| 116 |
| 117 |
| 118 template <typename C> |
| 119 bool ZoneSplayTree<C>::FindGreatestLessThan(const Key& key, |
| 120 Locator* locator) { |
| 121 if (is_empty()) |
| 122 return false; |
| 123 // Splay on the key to move the node with the given key or the last |
| 124 // node on the search path to the top of the tree. |
| 125 Splay(key); |
| 126 // Now the result is either the root node or the greatest node in |
| 127 // the left subtree. |
| 128 int cmp = C::Compare(root_->key_, key); |
| 129 if (cmp <= 0) { |
| 130 locator->bind(root_); |
| 131 return true; |
| 132 } else { |
| 133 Node* temp = root_; |
| 134 root_ = root_->left_; |
| 135 bool result = FindGreatest(locator); |
| 136 root_ = temp; |
| 137 return result; |
| 138 } |
| 139 } |
| 140 |
| 141 |
| 142 template <typename C> |
| 143 bool ZoneSplayTree<C>::FindLeastGreaterThan(const Key& key, |
| 144 Locator* locator) { |
| 145 if (is_empty()) |
| 146 return false; |
| 147 // Splay on the key to move the node with the given key or the last |
| 148 // node on the search path to the top of the tree. |
| 149 Splay(key); |
| 150 // Now the result is either the root node or the least node in |
| 151 // the right subtree. |
| 152 int cmp = C::Compare(root_->key_, key); |
| 153 if (cmp >= 0) { |
| 154 locator->bind(root_); |
| 155 return true; |
| 156 } else { |
| 157 Node* temp = root_; |
| 158 root_ = root_->right_; |
| 159 bool result = FindLeast(locator); |
| 160 root_ = temp; |
| 161 return result; |
| 162 } |
| 163 } |
| 164 |
| 165 |
| 166 template <typename C> |
| 167 bool ZoneSplayTree<C>::FindGreatest(Locator* locator) { |
| 168 if (is_empty()) |
| 169 return false; |
| 170 Node* current = root_; |
| 171 while (current->right_ != NULL) |
| 172 current = current->right_; |
| 173 locator->bind(current); |
| 174 return true; |
| 175 } |
| 176 |
| 177 |
| 178 template <typename C> |
| 179 bool ZoneSplayTree<C>::FindLeast(Locator* locator) { |
| 180 if (is_empty()) |
| 181 return false; |
| 182 Node* current = root_; |
| 183 while (current->left_ != NULL) |
| 184 current = current->left_; |
| 185 locator->bind(current); |
| 186 return true; |
| 187 } |
| 188 |
| 189 |
| 190 template <typename C> |
| 191 bool ZoneSplayTree<C>::Remove(const Key& key) { |
| 192 // Bail if the tree is empty |
| 193 if (is_empty()) |
| 194 return false; |
| 195 // Splay on the key to move the node with the given key to the top. |
| 196 Splay(key); |
| 197 // Bail if the key is not in the tree |
| 198 if (C::Compare(key, root_->key_) != 0) |
| 199 return false; |
| 200 if (root_->left_ == NULL) { |
| 201 // No left child, so the new tree is just the right child. |
| 202 root_ = root_->right_; |
| 203 } else { |
| 204 // Left child exists. |
| 205 Node* right = root_->right_; |
| 206 // Make the original left child the new root. |
| 207 root_ = root_->left_; |
| 208 // Splay to make sure that the new root has an empty right child. |
| 209 Splay(key); |
| 210 // Insert the original right child as the right child of the new |
| 211 // root. |
| 212 root_->right_ = right; |
| 213 } |
| 214 return true; |
| 215 } |
| 216 |
| 217 |
| 218 template <typename C> |
| 219 void ZoneSplayTree<C>::Splay(const Key& key) { |
| 220 if (is_empty()) |
| 221 return; |
| 222 Node dummy_node(C::kNoKey, C::kNoValue); |
| 223 // Create a dummy node. The use of the dummy node is a bit |
| 224 // counter-intuitive: The right child of the dummy node will hold |
| 225 // the L tree of the algorithm. The left child of the dummy node |
| 226 // will hold the R tree of the algorithm. Using a dummy node, left |
| 227 // and right will always be nodes and we avoid special cases. |
| 228 Node* dummy = &dummy_node; |
| 229 Node* left = dummy; |
| 230 Node* right = dummy; |
| 231 Node* current = root_; |
| 232 while (true) { |
| 233 int cmp = C::Compare(key, current->key_); |
| 234 if (cmp < 0) { |
| 235 if (current->left_ == NULL) |
| 236 break; |
| 237 if (C::Compare(key, current->left_->key_) < 0) { |
| 238 // Rotate right. |
| 239 Node* temp = current->left_; |
| 240 current->left_ = temp->right_; |
| 241 temp->right_ = current; |
| 242 current = temp; |
| 243 if (current->left_ == NULL) |
| 244 break; |
| 245 } |
| 246 // Link right. |
| 247 right->left_ = current; |
| 248 right = current; |
| 249 current = current->left_; |
| 250 } else if (cmp > 0) { |
| 251 if (current->right_ == NULL) |
| 252 break; |
| 253 if (C::Compare(key, current->right_->key_) > 0) { |
| 254 // Rotate left. |
| 255 Node* temp = current->right_; |
| 256 current->right_ = temp->left_; |
| 257 temp->left_ = current; |
| 258 current = temp; |
| 259 if (current->right_ == NULL) |
| 260 break; |
| 261 } |
| 262 // Link left. |
| 263 left->right_ = current; |
| 264 left = current; |
| 265 current = current->right_; |
| 266 } else { |
| 267 break; |
| 268 } |
| 269 } |
| 270 // Assemble. |
| 271 left->right_ = current->left_; |
| 272 right->left_ = current->right_; |
| 273 current->left_ = dummy->right_; |
| 274 current->right_ = dummy->left_; |
| 275 root_ = current; |
| 276 } |
| 277 |
| 278 |
| 279 template <typename Node, class Callback> |
| 280 static void DoForEach(Node* node, Callback* callback) { |
| 281 if (node == NULL) return; |
| 282 DoForEach<Node, Callback>(node->left(), callback); |
| 283 callback->Call(node->key(), node->value()); |
| 284 DoForEach<Node, Callback>(node->right(), callback); |
| 285 } |
| 286 |
| 287 |
71 } } // namespace v8::internal | 288 } } // namespace v8::internal |
72 | 289 |
73 #endif // V8_ZONE_INL_H_ | 290 #endif // V8_ZONE_INL_H_ |
OLD | NEW |