5 #ifndef V8_SPLAY_TREE_INL_H_ 6 #define V8_SPLAY_TREE_INL_H_ 10 #include "src/splay-tree.h" 16 template<
typename Config,
class Allocator>
17 SplayTree<Config, Allocator>::~SplayTree() {
19 ForEachNode(&deleter);
23 template<
typename Config,
class Allocator>
24 bool SplayTree<Config, Allocator>::Insert(
const Key& key,
28 root_ =
new(allocator_) Node(key, Config::NoValue());
34 int cmp = Config::Compare(key, root_->key_);
40 Node* node =
new(allocator_) Node(key, Config::NoValue());
41 InsertInternal(cmp, node);
48 template<
typename Config,
class Allocator>
49 void SplayTree<Config, Allocator>::InsertInternal(
int cmp, Node* node) {
52 node->right_ = root_->right_;
53 root_->right_ =
nullptr;
56 node->left_ = root_->left_;
57 root_->left_ =
nullptr;
63 template<
typename Config,
class Allocator>
64 bool SplayTree<Config, Allocator>::FindInternal(
const Key& key) {
68 return Config::Compare(key, root_->key_) == 0;
72 template<
typename Config,
class Allocator>
73 bool SplayTree<Config, Allocator>::Contains(
const Key& key) {
74 return FindInternal(key);
78 template<
typename Config,
class Allocator>
79 bool SplayTree<Config, Allocator>::Find(
const Key& key, Locator* locator) {
80 if (FindInternal(key)) {
89 template<
typename Config,
class Allocator>
90 bool SplayTree<Config, Allocator>::FindGreatestLessThan(
const Key& key,
99 int cmp = Config::Compare(root_->key_, key);
101 locator->bind(root_);
105 root_ = root_->left_;
106 bool result = FindGreatest(locator);
113 template<
typename Config,
class Allocator>
114 bool SplayTree<Config, Allocator>::FindLeastGreaterThan(
const Key& key,
123 int cmp = Config::Compare(root_->key_, key);
125 locator->bind(root_);
129 root_ = root_->right_;
130 bool result = FindLeast(locator);
137 template<
typename Config,
class Allocator>
138 bool SplayTree<Config, Allocator>::FindGreatest(Locator* locator) {
141 Node* current = root_;
142 while (current->right_ !=
nullptr) current = current->right_;
143 locator->bind(current);
148 template<
typename Config,
class Allocator>
149 bool SplayTree<Config, Allocator>::FindLeast(Locator* locator) {
152 Node* current = root_;
153 while (current->left_ !=
nullptr) current = current->left_;
154 locator->bind(current);
159 template<
typename Config,
class Allocator>
160 bool SplayTree<Config, Allocator>::Move(
const Key& old_key,
161 const Key& new_key) {
162 if (!FindInternal(old_key))
164 Node* node_to_move = root_;
165 RemoveRootNode(old_key);
167 int cmp = Config::Compare(new_key, root_->key_);
173 node_to_move->key_ = new_key;
174 InsertInternal(cmp, node_to_move);
179 template<
typename Config,
class Allocator>
180 bool SplayTree<Config, Allocator>::Remove(
const Key& key) {
181 if (!FindInternal(key))
183 Node* node_to_remove = root_;
185 delete node_to_remove;
190 template<
typename Config,
class Allocator>
191 void SplayTree<Config, Allocator>::RemoveRootNode(
const Key& key) {
192 if (root_->left_ ==
nullptr) {
194 root_ = root_->right_;
197 Node* right = root_->right_;
199 root_ = root_->left_;
204 root_->right_ = right;
209 template<
typename Config,
class Allocator>
210 void SplayTree<Config, Allocator>::Splay(
const Key& key) {
213 Node dummy_node(Config::kNoKey, Config::NoValue());
219 Node* dummy = &dummy_node;
222 Node* current = root_;
224 int cmp = Config::Compare(key, current->key_);
226 if (current->left_ ==
nullptr)
break;
227 if (Config::Compare(key, current->left_->key_) < 0) {
229 Node* temp = current->left_;
230 current->left_ = temp->right_;
231 temp->right_ = current;
233 if (current->left_ ==
nullptr)
break;
236 right->left_ = current;
238 current = current->left_;
239 }
else if (cmp > 0) {
240 if (current->right_ ==
nullptr)
break;
241 if (Config::Compare(key, current->right_->key_) > 0) {
243 Node* temp = current->right_;
244 current->right_ = temp->left_;
245 temp->left_ = current;
247 if (current->right_ ==
nullptr)
break;
250 left->right_ = current;
252 current = current->right_;
258 left->right_ = current->left_;
259 right->left_ = current->right_;
260 current->left_ = dummy->right_;
261 current->right_ = dummy->left_;
266 template <
typename Config,
class Allocator>
template <
class Callback>
267 void SplayTree<Config, Allocator>::ForEach(Callback* callback) {
268 NodeToPairAdaptor<Callback> callback_adaptor(callback);
269 ForEachNode(&callback_adaptor);
273 template <
typename Config,
class Allocator>
template <
class Callback>
274 void SplayTree<Config, Allocator>::ForEachNode(Callback* callback) {
275 if (root_ ==
nullptr)
return;
277 std::vector<Node*> nodes_to_visit;
278 nodes_to_visit.push_back(root_);
280 while (pos < nodes_to_visit.size()) {
281 Node* node = nodes_to_visit[pos++];
282 if (node->left() !=
nullptr) nodes_to_visit.push_back(node->left());
283 if (node->right() !=
nullptr) nodes_to_visit.push_back(node->right());
284 callback->Call(node);
292 #endif // V8_SPLAY_TREE_INL_H_