V8 API Reference, 7.2.502.16 (for Deno 0.2.4)
splay-tree.h
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_
Definition: libplatform.h:13