Line data Source code
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 1638880 : : root_(NULL), allocator_(allocator) {}
40 : ~SplayTree();
41 :
42 : INLINE(void* operator new(size_t size,
43 : AllocationPolicy allocator = AllocationPolicy())) {
44 : return allocator.New(static_cast<int>(size));
45 : }
46 : INLINE(void operator delete(void* p)) {
47 : AllocationPolicy::Delete(p);
48 : }
49 : // Please the MSVC compiler. We should never have to execute this.
50 : INLINE(void operator delete(void* p, AllocationPolicy policy)) {
51 : UNREACHABLE();
52 : }
53 :
54 : AllocationPolicy allocator() { return allocator_; }
55 :
56 : // Checks if there is a mapping for the key.
57 : bool Contains(const Key& key);
58 :
59 : // Inserts the given key in this tree with the given value. Returns
60 : // true if a node was inserted, otherwise false. If found the locator
61 : // is enabled and provides access to the mapping for the key.
62 2018781 : bool Insert(const Key& key, Locator* locator);
63 :
64 : // Looks up the key in this tree and returns true if it was found,
65 : // otherwise false. If the node is found the locator is enabled and
66 : // provides access to the mapping for the key.
67 : bool Find(const Key& key, Locator* locator);
68 :
69 : // Finds the mapping with the greatest key less than or equal to the
70 : // given key.
71 176139 : bool FindGreatestLessThan(const Key& key, Locator* locator);
72 :
73 : // Find the mapping with the greatest key in this tree.
74 : bool FindGreatest(Locator* locator);
75 :
76 : // Finds the mapping with the least key greater than or equal to the
77 : // given key.
78 185523 : bool FindLeastGreaterThan(const Key& key, Locator* locator);
79 :
80 : // Find the mapping with the least key in this tree.
81 : bool FindLeast(Locator* locator);
82 :
83 : // Move the node from one key to another.
84 : bool Move(const Key& old_key, const Key& new_key);
85 :
86 : // Remove the node with the given key from the tree.
87 : bool Remove(const Key& key);
88 :
89 : // Remove all keys from the tree.
90 : void Clear() { ResetRoot(); }
91 :
92 : bool is_empty() { return root_ == NULL; }
93 :
94 : // Perform the splay operation for the given key. Moves the node with
95 : // the given key to the top of the tree. If no node has the given
96 : // key, the last node on the search path is moved to the top of the
97 : // tree.
98 3982628 : void Splay(const Key& key);
99 :
100 : class Node {
101 : public:
102 : Node(const Key& key, const Value& value)
103 : : key_(key),
104 : value_(value),
105 : left_(NULL),
106 5217759 : right_(NULL) { }
107 :
108 : INLINE(void* operator new(size_t size, AllocationPolicy allocator)) {
109 1235131 : return allocator.New(static_cast<int>(size));
110 : }
111 : INLINE(void operator delete(void* p)) {
112 : return AllocationPolicy::Delete(p);
113 : }
114 : // Please the MSVC compiler. We should never have to execute
115 : // this.
116 : INLINE(void operator delete(void* p, AllocationPolicy allocator)) {
117 : UNREACHABLE();
118 : }
119 :
120 : Key key() { return key_; }
121 795922 : Value value() { return value_; }
122 : Node* left() { return left_; }
123 : Node* right() { return right_; }
124 :
125 : private:
126 : friend class SplayTree;
127 : friend class Locator;
128 : Key key_;
129 : Value value_;
130 : Node* left_;
131 : Node* right_;
132 : };
133 :
134 : // A locator provides access to a node in the tree without actually
135 : // exposing the node.
136 : class Locator BASE_EMBEDDED {
137 : public:
138 : explicit Locator(Node* node) : node_(node) { }
139 5361854 : Locator() : node_(NULL) { }
140 0 : const Key& key() { return node_->key_; }
141 2120790 : Value& value() { return node_->value_; }
142 2107444 : void set_value(const Value& value) { node_->value_ = value; }
143 3303710 : inline void bind(Node* node) { node_ = node; }
144 :
145 : private:
146 : Node* node_;
147 : };
148 :
149 : template <class Callback>
150 : void ForEach(Callback* callback);
151 :
152 : protected:
153 : // Resets tree root. Existing nodes become unreachable.
154 3156 : void ResetRoot() { root_ = NULL; }
155 :
156 : private:
157 : // Search for a node with a given key. If found, root_ points
158 : // to the node.
159 4512254 : bool FindInternal(const Key& key);
160 :
161 : // Inserts a node assuming that root_ is already set up.
162 : void InsertInternal(int cmp, Node* node);
163 :
164 : // Removes root_ node.
165 : void RemoveRootNode(const Key& key);
166 :
167 : template<class Callback>
168 : class NodeToPairAdaptor BASE_EMBEDDED {
169 : public:
170 : explicit NodeToPairAdaptor(Callback* callback)
171 2041144 : : callback_(callback) { }
172 2288366 : void Call(Node* node) {
173 1492444 : callback_->Call(node->key(), node->value());
174 978299 : }
175 :
176 : private:
177 : Callback* callback_;
178 :
179 : DISALLOW_COPY_AND_ASSIGN(NodeToPairAdaptor);
180 : };
181 :
182 : class NodeDeleter BASE_EMBEDDED {
183 : public:
184 : NodeDeleter() { }
185 : void Call(Node* node) { AllocationPolicy::Delete(node); }
186 :
187 : private:
188 : DISALLOW_COPY_AND_ASSIGN(NodeDeleter);
189 : };
190 :
191 : template <class Callback>
192 : void ForEachNode(Callback* callback);
193 :
194 : Node* root_;
195 : AllocationPolicy allocator_;
196 :
197 : DISALLOW_COPY_AND_ASSIGN(SplayTree);
198 : };
199 :
200 :
201 : } // namespace internal
202 : } // namespace v8
203 :
204 : #endif // V8_SPLAY_TREE_H_
|
