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> | 71 template <typename Config> |
72 bool ZoneSplayTree<C>::Insert(const Key& key, Locator* locator) { | 72 ZoneSplayTree<Config>::~ZoneSplayTree() { |
73 if (is_empty()) { | 73 // Reset the root to avoid unneeded iteration over all tree nodes |
74 // If the tree is empty, insert the new node. | 74 // in the destructor. For a zone-allocated tree, nodes will be |
75 root_ = new Node(key, C::kNoValue); | 75 // freed by the Zone. |
76 } else { | 76 SplayTree<Config, ZoneListAllocationPolicy>::ResetRoot(); |
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 } | 77 } |
102 | 78 |
103 | 79 |
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 | 80 } } // namespace v8::internal |
296 | 81 |
297 #endif // V8_ZONE_INL_H_ | 82 #endif // V8_ZONE_INL_H_ |
OLD | NEW |