v8  3.14.5(node0.10.28)
V8 is Google's open source JavaScript engine
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
splay-tree-inl.h
Go to the documentation of this file.
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>
39  NodeDeleter deleter;
40  ForEachNode(&deleter);
41 }
42 
43 
44 template<typename Config, class Allocator>
46  Locator* locator) {
47  if (is_empty()) {
48  // If the tree is empty, insert the new node.
49  root_ = new(allocator_) Node(key, Config::NoValue());
50  } else {
51  // Splay on the key to move the last node on the search path
52  // for the key to the root of the tree.
53  Splay(key);
54  // Ignore repeated insertions with the same key.
55  int cmp = Config::Compare(key, root_->key_);
56  if (cmp == 0) {
57  locator->bind(root_);
58  return false;
59  }
60  // Insert the new node.
61  Node* node = new(allocator_) Node(key, Config::NoValue());
62  InsertInternal(cmp, node);
63  }
64  locator->bind(root_);
65  return true;
66 }
67 
68 
69 template<typename Config, class Allocator>
70 void SplayTree<Config, Allocator>::InsertInternal(int cmp, Node* node) {
71  if (cmp > 0) {
72  node->left_ = root_;
73  node->right_ = root_->right_;
74  root_->right_ = NULL;
75  } else {
76  node->right_ = root_;
77  node->left_ = root_->left_;
78  root_->left_ = NULL;
79  }
80  root_ = node;
81 }
82 
83 
84 template<typename Config, class Allocator>
85 bool SplayTree<Config, Allocator>::FindInternal(const Key& key) {
86  if (is_empty())
87  return false;
88  Splay(key);
89  return Config::Compare(key, root_->key_) == 0;
90 }
91 
92 
93 template<typename Config, class Allocator>
94 bool SplayTree<Config, Allocator>::Find(const Key& key, Locator* locator) {
95  if (FindInternal(key)) {
96  locator->bind(root_);
97  return true;
98  } else {
99  return false;
100  }
101 }
102 
103 
104 template<typename Config, class Allocator>
106  Locator* locator) {
107  if (is_empty())
108  return false;
109  // Splay on the key to move the node with the given key or the last
110  // node on the search path to the top of the tree.
111  Splay(key);
112  // Now the result is either the root node or the greatest node in
113  // the left subtree.
114  int cmp = Config::Compare(root_->key_, key);
115  if (cmp <= 0) {
116  locator->bind(root_);
117  return true;
118  } else {
119  Node* temp = root_;
120  root_ = root_->left_;
121  bool result = FindGreatest(locator);
122  root_ = temp;
123  return result;
124  }
125 }
126 
127 
128 template<typename Config, class Allocator>
130  Locator* locator) {
131  if (is_empty())
132  return false;
133  // Splay on the key to move the node with the given key or the last
134  // node on the search path to the top of the tree.
135  Splay(key);
136  // Now the result is either the root node or the least node in
137  // the right subtree.
138  int cmp = Config::Compare(root_->key_, key);
139  if (cmp >= 0) {
140  locator->bind(root_);
141  return true;
142  } else {
143  Node* temp = root_;
144  root_ = root_->right_;
145  bool result = FindLeast(locator);
146  root_ = temp;
147  return result;
148  }
149 }
150 
151 
152 template<typename Config, class Allocator>
154  if (is_empty())
155  return false;
156  Node* current = root_;
157  while (current->right_ != NULL)
158  current = current->right_;
159  locator->bind(current);
160  return true;
161 }
162 
163 
164 template<typename Config, class Allocator>
166  if (is_empty())
167  return false;
168  Node* current = root_;
169  while (current->left_ != NULL)
170  current = current->left_;
171  locator->bind(current);
172  return true;
173 }
174 
175 
176 template<typename Config, class Allocator>
178  const Key& new_key) {
179  if (!FindInternal(old_key))
180  return false;
181  Node* node_to_move = root_;
182  RemoveRootNode(old_key);
183  Splay(new_key);
184  int cmp = Config::Compare(new_key, root_->key_);
185  if (cmp == 0) {
186  // A node with the target key already exists.
187  delete node_to_move;
188  return false;
189  }
190  node_to_move->key_ = new_key;
191  InsertInternal(cmp, node_to_move);
192  return true;
193 }
194 
195 
196 template<typename Config, class Allocator>
198  if (!FindInternal(key))
199  return false;
200  Node* node_to_remove = root_;
201  RemoveRootNode(key);
202  delete node_to_remove;
203  return true;
204 }
205 
206 
207 template<typename Config, class Allocator>
209  if (root_->left_ == NULL) {
210  // No left child, so the new tree is just the right child.
211  root_ = root_->right_;
212  } else {
213  // Left child exists.
214  Node* right = root_->right_;
215  // Make the original left child the new root.
216  root_ = root_->left_;
217  // Splay to make sure that the new root has an empty right child.
218  Splay(key);
219  // Insert the original right child as the right child of the new
220  // root.
221  root_->right_ = right;
222  }
223 }
224 
225 
226 template<typename Config, class Allocator>
228  if (is_empty())
229  return;
230  Node dummy_node(Config::kNoKey, Config::NoValue());
231  // Create a dummy node. The use of the dummy node is a bit
232  // counter-intuitive: The right child of the dummy node will hold
233  // the L tree of the algorithm. The left child of the dummy node
234  // will hold the R tree of the algorithm. Using a dummy node, left
235  // and right will always be nodes and we avoid special cases.
236  Node* dummy = &dummy_node;
237  Node* left = dummy;
238  Node* right = dummy;
239  Node* current = root_;
240  while (true) {
241  int cmp = Config::Compare(key, current->key_);
242  if (cmp < 0) {
243  if (current->left_ == NULL)
244  break;
245  if (Config::Compare(key, current->left_->key_) < 0) {
246  // Rotate right.
247  Node* temp = current->left_;
248  current->left_ = temp->right_;
249  temp->right_ = current;
250  current = temp;
251  if (current->left_ == NULL)
252  break;
253  }
254  // Link right.
255  right->left_ = current;
256  right = current;
257  current = current->left_;
258  } else if (cmp > 0) {
259  if (current->right_ == NULL)
260  break;
261  if (Config::Compare(key, current->right_->key_) > 0) {
262  // Rotate left.
263  Node* temp = current->right_;
264  current->right_ = temp->left_;
265  temp->left_ = current;
266  current = temp;
267  if (current->right_ == NULL)
268  break;
269  }
270  // Link left.
271  left->right_ = current;
272  left = current;
273  current = current->right_;
274  } else {
275  break;
276  }
277  }
278  // Assemble.
279  left->right_ = current->left_;
280  right->left_ = current->right_;
281  current->left_ = dummy->right_;
282  current->right_ = dummy->left_;
283  root_ = current;
284 }
285 
286 
287 template <typename Config, class Allocator> template <class Callback>
288 void SplayTree<Config, Allocator>::ForEach(Callback* callback) {
289  NodeToPairAdaptor<Callback> callback_adaptor(callback);
290  ForEachNode(&callback_adaptor);
291 }
292 
293 
294 template <typename Config, class Allocator> template <class Callback>
295 void SplayTree<Config, Allocator>::ForEachNode(Callback* callback) {
296  // Pre-allocate some space for tiny trees.
297  List<Node*, Allocator> nodes_to_visit(10, allocator_);
298  if (root_ != NULL) nodes_to_visit.Add(root_, allocator_);
299  int pos = 0;
300  while (pos < nodes_to_visit.length()) {
301  Node* node = nodes_to_visit[pos++];
302  if (node->left() != NULL) nodes_to_visit.Add(node->left(), allocator_);
303  if (node->right() != NULL) nodes_to_visit.Add(node->right(), allocator_);
304  callback->Call(node);
305  }
306 }
307 
308 
309 } } // namespace v8::internal
310 
311 #endif // V8_SPLAY_TREE_INL_H_
bool Find(const Key &key, Locator *locator)
bool Insert(const Key &key, Locator *locator)
bool FindGreatest(Locator *locator)
void Splay(const Key &key)
void ForEach(Callback *callback)
int Compare(const T &a, const T &b)
Definition: utils.h:156
bool FindLeast(Locator *locator)
bool Move(const Key &old_key, const Key &new_key)
bool FindLeastGreaterThan(const Key &key, Locator *locator)
bool Remove(const Key &key)
bool FindGreatestLessThan(const Key &key, Locator *locator)
activate correct semantics for inheriting readonliness enable harmony semantics for typeof enable harmony enable harmony proxies enable all harmony harmony_scoping harmony_proxies harmony_scoping tracks arrays with only smi values automatically unbox arrays of doubles use crankshaft use hydrogen range analysis use hydrogen global value numbering use function inlining maximum number of AST nodes considered for a single inlining loop invariant code motion print statistics for hydrogen trace generated IR for specified phases trace register allocator trace range analysis trace representation types environment for every instruction put a break point before deoptimizing polymorphic inlining perform array bounds checks elimination use dead code elimination trace on stack replacement optimize closures cache optimized code for closures functions with arguments object loop weight for representation inference allow uint32 values on optimize frames if they are used only in safe operations track parallel recompilation enable all profiler experiments number of stack frames inspected by the profiler call recompile stub directly when self optimizing trigger profiler ticks based on counting instead of timing weight back edges by jump distance for interrupt triggering percentage of ICs that must have type info to allow optimization watch_ic_patching retry_self_opt interrupt_at_exit extra verbose compilation tracing generate extra emit comments in code disassembly enable use of SSE3 instructions if available enable use of CMOV instruction if available enable use of SAHF instruction if enable use of VFP3 instructions if available this implies enabling ARMv7 and VFP2 enable use of VFP2 instructions if available enable use of SDIV and UDIV instructions if enable loading bit constant by means of movw movt instruction enable unaligned accesses for enable use of MIPS FPU instructions if NULL
Definition: flags.cc:301