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