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
New(int size)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>
NewArray(int length)55 T* Zone::NewArray(int length) {
56 return static_cast<T*>(Zone::New(length * sizeof(T)));
57 }
58
59
excess_allocation()60 bool Zone::excess_allocation() {
61 return segment_bytes_allocated_ > zone_excess_limit_;
62 }
63
64
adjust_segment_bytes_allocated(int delta)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>
Insert(const Key & key,Locator * locator)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>
Find(const Key & key,Locator * locator)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>
FindGreatestLessThan(const Key & key,Locator * locator)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>
FindLeastGreaterThan(const Key & key,Locator * locator)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>
FindGreatest(Locator * locator)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>
FindLeast(Locator * locator)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>
Remove(const Key & key)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>
Splay(const Key & key)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>
ForEach(Callback * 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