1 // Copyright 2006-2008 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_ZONE_INL_H_ 29 #define V8_ZONE_INL_H_ 30 31 #include "zone.h" 32 #include "v8-counters.h" 33 34 namespace v8 { 35 namespace internal { 36 37 38 inline void* Zone::New(int size) { 39 ASSERT(AssertNoZoneAllocation::allow_allocation()); 40 ASSERT(ZoneScope::nesting() > 0); 41 // Round up the requested size to fit the alignment. 42 size = RoundUp(size, kAlignment); 43 44 // Check if the requested size is available without expanding. 45 Address result = position_; 46 if ((position_ += size) > limit_) result = NewExpand(size); 47 48 // Check that the result has the proper alignment and return it. 49 ASSERT(IsAddressAligned(result, kAlignment, 0)); 50 return reinterpret_cast<void*>(result); 51 } 52 53 54 template <typename T> 55 T* Zone::NewArray(int length) { 56 return static_cast<T*>(Zone::New(length * sizeof(T))); 57 } 58 59 60 bool Zone::excess_allocation() { 61 return segment_bytes_allocated_ > zone_excess_limit_; 62 } 63 64 65 void Zone::adjust_segment_bytes_allocated(int delta) { 66 segment_bytes_allocated_ += delta; 67 Counters::zone_segment_bytes.Set(segment_bytes_allocated_); 68 } 69 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 Config> template <class Callback> 280 void ZoneSplayTree<Config>::ForEach(Callback* callback) { 281 // Pre-allocate some space for tiny trees. 282 ZoneList<Node*> nodes_to_visit(10); 283 nodes_to_visit.Add(root_); 284 int pos = 0; 285 while (pos < nodes_to_visit.length()) { 286 Node* node = nodes_to_visit[pos++]; 287 if (node == NULL) continue; 288 callback->Call(node->key(), node->value()); 289 nodes_to_visit.Add(node->left()); 290 nodes_to_visit.Add(node->right()); 291 } 292 } 293 294 295 } } // namespace v8::internal 296 297 #endif // V8_ZONE_INL_H_ 298
