OLD | NEW |
| (Empty) |
1 // Copyright 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_JSREGEXP_INL_H_ | |
29 #define V8_JSREGEXP_INL_H_ | |
30 | |
31 | |
32 #include "jsregexp.h" | |
33 #include "regexp-macro-assembler.h" | |
34 | |
35 | |
36 namespace v8 { | |
37 namespace internal { | |
38 | |
39 | |
40 template <typename C> | |
41 bool ZoneSplayTree<C>::Insert(const Key& key, Locator* locator) { | |
42 if (is_empty()) { | |
43 // If the tree is empty, insert the new node. | |
44 root_ = new Node(key, C::kNoValue); | |
45 } else { | |
46 // Splay on the key to move the last node on the search path | |
47 // for the key to the root of the tree. | |
48 Splay(key); | |
49 // Ignore repeated insertions with the same key. | |
50 int cmp = C::Compare(key, root_->key_); | |
51 if (cmp == 0) { | |
52 locator->bind(root_); | |
53 return false; | |
54 } | |
55 // Insert the new node. | |
56 Node* node = new Node(key, C::kNoValue); | |
57 if (cmp > 0) { | |
58 node->left_ = root_; | |
59 node->right_ = root_->right_; | |
60 root_->right_ = NULL; | |
61 } else { | |
62 node->right_ = root_; | |
63 node->left_ = root_->left_; | |
64 root_->left_ = NULL; | |
65 } | |
66 root_ = node; | |
67 } | |
68 locator->bind(root_); | |
69 return true; | |
70 } | |
71 | |
72 | |
73 template <typename C> | |
74 bool ZoneSplayTree<C>::Find(const Key& key, Locator* locator) { | |
75 if (is_empty()) | |
76 return false; | |
77 Splay(key); | |
78 if (C::Compare(key, root_->key_) == 0) { | |
79 locator->bind(root_); | |
80 return true; | |
81 } else { | |
82 return false; | |
83 } | |
84 } | |
85 | |
86 | |
87 template <typename C> | |
88 bool ZoneSplayTree<C>::FindGreatestLessThan(const Key& key, | |
89 Locator* locator) { | |
90 if (is_empty()) | |
91 return false; | |
92 // Splay on the key to move the node with the given key or the last | |
93 // node on the search path to the top of the tree. | |
94 Splay(key); | |
95 // Now the result is either the root node or the greatest node in | |
96 // the left subtree. | |
97 int cmp = C::Compare(root_->key_, key); | |
98 if (cmp <= 0) { | |
99 locator->bind(root_); | |
100 return true; | |
101 } else { | |
102 Node* temp = root_; | |
103 root_ = root_->left_; | |
104 bool result = FindGreatest(locator); | |
105 root_ = temp; | |
106 return result; | |
107 } | |
108 } | |
109 | |
110 | |
111 template <typename C> | |
112 bool ZoneSplayTree<C>::FindLeastGreaterThan(const Key& key, | |
113 Locator* locator) { | |
114 if (is_empty()) | |
115 return false; | |
116 // Splay on the key to move the node with the given key or the last | |
117 // node on the search path to the top of the tree. | |
118 Splay(key); | |
119 // Now the result is either the root node or the least node in | |
120 // the right subtree. | |
121 int cmp = C::Compare(root_->key_, key); | |
122 if (cmp >= 0) { | |
123 locator->bind(root_); | |
124 return true; | |
125 } else { | |
126 Node* temp = root_; | |
127 root_ = root_->right_; | |
128 bool result = FindLeast(locator); | |
129 root_ = temp; | |
130 return result; | |
131 } | |
132 } | |
133 | |
134 | |
135 template <typename C> | |
136 bool ZoneSplayTree<C>::FindGreatest(Locator* locator) { | |
137 if (is_empty()) | |
138 return false; | |
139 Node* current = root_; | |
140 while (current->right_ != NULL) | |
141 current = current->right_; | |
142 locator->bind(current); | |
143 return true; | |
144 } | |
145 | |
146 | |
147 template <typename C> | |
148 bool ZoneSplayTree<C>::FindLeast(Locator* locator) { | |
149 if (is_empty()) | |
150 return false; | |
151 Node* current = root_; | |
152 while (current->left_ != NULL) | |
153 current = current->left_; | |
154 locator->bind(current); | |
155 return true; | |
156 } | |
157 | |
158 | |
159 template <typename C> | |
160 bool ZoneSplayTree<C>::Remove(const Key& key) { | |
161 // Bail if the tree is empty | |
162 if (is_empty()) | |
163 return false; | |
164 // Splay on the key to move the node with the given key to the top. | |
165 Splay(key); | |
166 // Bail if the key is not in the tree | |
167 if (C::Compare(key, root_->key_) != 0) | |
168 return false; | |
169 if (root_->left_ == NULL) { | |
170 // No left child, so the new tree is just the right child. | |
171 root_ = root_->right_; | |
172 } else { | |
173 // Left child exists. | |
174 Node* right = root_->right_; | |
175 // Make the original left child the new root. | |
176 root_ = root_->left_; | |
177 // Splay to make sure that the new root has an empty right child. | |
178 Splay(key); | |
179 // Insert the original right child as the right child of the new | |
180 // root. | |
181 root_->right_ = right; | |
182 } | |
183 return true; | |
184 } | |
185 | |
186 | |
187 template <typename C> | |
188 void ZoneSplayTree<C>::Splay(const Key& key) { | |
189 if (is_empty()) | |
190 return; | |
191 Node dummy_node(C::kNoKey, C::kNoValue); | |
192 // Create a dummy node. The use of the dummy node is a bit | |
193 // counter-intuitive: The right child of the dummy node will hold | |
194 // the L tree of the algorithm. The left child of the dummy node | |
195 // will hold the R tree of the algorithm. Using a dummy node, left | |
196 // and right will always be nodes and we avoid special cases. | |
197 Node* dummy = &dummy_node; | |
198 Node* left = dummy; | |
199 Node* right = dummy; | |
200 Node* current = root_; | |
201 while (true) { | |
202 int cmp = C::Compare(key, current->key_); | |
203 if (cmp < 0) { | |
204 if (current->left_ == NULL) | |
205 break; | |
206 if (C::Compare(key, current->left_->key_) < 0) { | |
207 // Rotate right. | |
208 Node* temp = current->left_; | |
209 current->left_ = temp->right_; | |
210 temp->right_ = current; | |
211 current = temp; | |
212 if (current->left_ == NULL) | |
213 break; | |
214 } | |
215 // Link right. | |
216 right->left_ = current; | |
217 right = current; | |
218 current = current->left_; | |
219 } else if (cmp > 0) { | |
220 if (current->right_ == NULL) | |
221 break; | |
222 if (C::Compare(key, current->right_->key_) > 0) { | |
223 // Rotate left. | |
224 Node* temp = current->right_; | |
225 current->right_ = temp->left_; | |
226 temp->left_ = current; | |
227 current = temp; | |
228 if (current->right_ == NULL) | |
229 break; | |
230 } | |
231 // Link left. | |
232 left->right_ = current; | |
233 left = current; | |
234 current = current->right_; | |
235 } else { | |
236 break; | |
237 } | |
238 } | |
239 // Assemble. | |
240 left->right_ = current->left_; | |
241 right->left_ = current->right_; | |
242 current->left_ = dummy->right_; | |
243 current->right_ = dummy->left_; | |
244 root_ = current; | |
245 } | |
246 | |
247 | |
248 template <typename Node, class Callback> | |
249 static void DoForEach(Node* node, Callback* callback) { | |
250 if (node == NULL) return; | |
251 DoForEach<Node, Callback>(node->left(), callback); | |
252 callback->Call(node->key(), node->value()); | |
253 DoForEach<Node, Callback>(node->right(), callback); | |
254 } | |
255 | |
256 | |
257 }} // namespace v8::internal | |
258 | |
259 | |
260 #endif // V8_JSREGEXP_INL_H_ | |
OLD | NEW |