1// Copyright (c) 2010, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4//
5// The original file can be found at:
6// https://github.com/v8/v8/blob/master/src/splay-tree.h
7
8#ifndef RUNTIME_PLATFORM_SPLAY_TREE_H_
9#define RUNTIME_PLATFORM_SPLAY_TREE_H_
10
11#include "platform/allocation.h"
12
13namespace dart {
14
15// A splay tree. The config type parameter encapsulates the different
16// configurations of a concrete splay tree:
17//
18// typedef Key: the key type
19// typedef Value: the value type
20// static const Key kNoKey: the dummy key used when no key is set
21// static Value kNoValue(): the dummy value used to initialize nodes
22// static int (Compare)(Key& a, Key& b) -> {-1, 0, 1}: comparison function
23//
24// The tree is also parameterized by an allocation policy
25// (Allocator). The policy is used for allocating lists in the C free
26// store or the zone; see zone.h.
27
28template <typename Config, class B, class Allocator>
29class SplayTree : public B {
30 public:
31 typedef typename Config::Key Key;
32 typedef typename Config::Value Value;
33
34 class Locator;
35
36 explicit SplayTree(Allocator* allocator)
37 : root_(nullptr), allocator_(allocator) {}
38 ~SplayTree();
39
40 Allocator* allocator() { return allocator_; }
41
42 // Checks if there is a mapping for the key.
43 bool Contains(const Key& key);
44
45 // Inserts the given key in this tree with the given value. Returns
46 // true if a node was inserted, otherwise false. If found the locator
47 // is enabled and provides access to the mapping for the key.
48 bool Insert(const Key& key, Locator* locator);
49
50 // Looks up the key in this tree and returns true if it was found,
51 // otherwise false. If the node is found the locator is enabled and
52 // provides access to the mapping for the key.
53 bool Find(const Key& key, Locator* locator);
54
55 // Finds the mapping with the greatest key less than or equal to the
56 // given key.
57 bool FindGreatestLessThan(const Key& key, Locator* locator);
58
59 // Find the mapping with the greatest key in this tree.
60 bool FindGreatest(Locator* locator);
61
62 // Finds the mapping with the least key greater than or equal to the
63 // given key.
64 bool FindLeastGreaterThan(const Key& key, Locator* locator);
65
66 // Find the mapping with the least key in this tree.
67 bool FindLeast(Locator* locator);
68
69 // Move the node from one key to another.
70 bool Move(const Key& old_key, const Key& new_key);
71
72 // Remove the node with the given key from the tree.
73 bool Remove(const Key& key);
74
75 // Remove all keys from the tree.
76 void Clear() { ResetRoot(); }
77
78 bool is_empty() { return root_ == nullptr; }
79
80 // Perform the splay operation for the given key. Moves the node with
81 // the given key to the top of the tree. If no node has the given
82 // key, the last node on the search path is moved to the top of the
83 // tree.
84 void Splay(const Key& key);
85
86 class Node : public B {
87 public:
88 Node(const Key& key, const Value& value)
89 : key_(key), value_(value), left_(nullptr), right_(nullptr) {}
90
91 Key key() { return key_; }
92 Value value() { return value_; }
93 Node* left() { return left_; }
94 Node* right() { return right_; }
95
96 private:
97 friend class SplayTree;
98 friend class Locator;
99 Key key_;
100 Value value_;
101 Node* left_;
102 Node* right_;
103 };
104
105 // A locator provides access to a node in the tree without actually
106 // exposing the node.
107 class Locator : public B {
108 public:
109 explicit Locator(Node* node) : node_(node) {}
110 Locator() : node_(nullptr) {}
111 const Key& key() { return node_->key_; }
112 Value& value() { return node_->value_; }
113 void set_value(const Value& value) { node_->value_ = value; }
114 inline void bind(Node* node) { node_ = node; }
115
116 private:
117 Node* node_;
118 };
119
120 template <class Callback>
121 void ForEach(Callback* callback);
122
123 protected:
124 // Resets tree root. Existing nodes become unreachable.
125 void ResetRoot() { root_ = nullptr; }
126
127 private:
128 // Search for a node with a given key. If found, root_ points
129 // to the node.
130 bool FindInternal(const Key& key);
131
132 // Inserts a node assuming that root_ is already set up.
133 void InsertInternal(int cmp, Node* node);
134
135 // Removes root_ node.
136 void RemoveRootNode(const Key& key);
137
138 template <class Callback>
139 class NodeToPairAdaptor : public B {
140 public:
141 explicit NodeToPairAdaptor(Callback* callback) : callback_(callback) {}
142 void Call(Node* node) { callback_->Call(node->key(), node->value()); }
143
144 private:
145 Callback* callback_;
146
147 DISALLOW_COPY_AND_ASSIGN(NodeToPairAdaptor);
148 };
149
150 class NodeDeleter : public B {
151 public:
152 NodeDeleter() = default;
153 void Call(Node* node) { delete node; }
154
155 private:
156 DISALLOW_COPY_AND_ASSIGN(NodeDeleter);
157 };
158
159 template <class Callback>
160 void ForEachNode(Callback* callback);
161
162 Node* root_;
163 Allocator* allocator_;
164
165 DISALLOW_COPY_AND_ASSIGN(SplayTree);
166};
167
168} // namespace dart
169
170#endif // RUNTIME_PLATFORM_SPLAY_TREE_H_
171