5 #ifndef V8_SPLAY_TREE_H_ 6 #define V8_SPLAY_TREE_H_ 8 #include "src/allocation.h" 30 template <
typename Config,
class AllocationPolicy>
33 typedef typename Config::Key Key;
34 typedef typename Config::Value
Value;
38 explicit SplayTree(AllocationPolicy allocator = AllocationPolicy())
39 : root_(nullptr), allocator_(allocator) {}
42 V8_INLINE
void*
operator new(
43 size_t size, AllocationPolicy allocator = AllocationPolicy()) {
44 return allocator.New(static_cast<int>(size));
46 V8_INLINE
void operator delete(
void* p) { AllocationPolicy::Delete(p); }
48 V8_INLINE
void operator delete(
void* p, AllocationPolicy policy) {
52 AllocationPolicy allocator() {
return allocator_; }
55 bool Contains(
const Key& key);
60 bool Insert(
const Key& key, Locator* locator);
65 bool Find(
const Key& key, Locator* locator);
69 bool FindGreatestLessThan(
const Key& key, Locator* locator);
72 bool FindGreatest(Locator* locator);
76 bool FindLeastGreaterThan(
const Key& key, Locator* locator);
79 bool FindLeast(Locator* locator);
82 bool Move(
const Key& old_key,
const Key& new_key);
85 bool Remove(
const Key& key);
88 void Clear() { ResetRoot(); }
90 bool is_empty() {
return root_ ==
nullptr; }
96 void Splay(
const Key& key);
100 Node(
const Key& key,
const Value& value)
101 : key_(key), value_(value), left_(
nullptr), right_(
nullptr) {}
103 V8_INLINE
void*
operator new(
size_t size, AllocationPolicy allocator) {
104 return allocator.New(static_cast<int>(size));
106 V8_INLINE
void operator delete(
void* p) {
107 return AllocationPolicy::Delete(p);
111 V8_INLINE
void operator delete(
void* p, AllocationPolicy allocator) {
115 Key key() {
return key_; }
116 Value value() {
return value_; }
117 Node* left() {
return left_; }
118 Node* right() {
return right_; }
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; }
144 template <
class Callback>
145 void ForEach(Callback* callback);
149 void ResetRoot() { root_ =
nullptr; }
154 bool FindInternal(
const Key& key);
157 void InsertInternal(
int cmp,
Node* node);
160 void RemoveRootNode(
const Key& key);
162 template <
class Callback>
163 class NodeToPairAdaptor {
165 explicit NodeToPairAdaptor(Callback* callback)
166 : callback_(callback) { }
167 void Call(Node* node) {
168 callback_->Call(node->key(), node->value());
174 DISALLOW_COPY_AND_ASSIGN(NodeToPairAdaptor);
179 NodeDeleter() =
default;
180 void Call(Node* node) { AllocationPolicy::Delete(node); }
183 DISALLOW_COPY_AND_ASSIGN(NodeDeleter);
186 template <
class Callback>
187 void ForEachNode(Callback* callback);
190 AllocationPolicy allocator_;
192 DISALLOW_COPY_AND_ASSIGN(SplayTree);
199 #endif // V8_SPLAY_TREE_H_