1// Copyright 2010 the V8 project authors. All rights reserved. 2// Redistribution and use in source and binary forms, with or without 3// modification, are permitted provided that the following conditions are 4// met: 5// 6// * Redistributions of source code must retain the above copyright 7// notice, this list of conditions and the following disclaimer. 8// * Redistributions in binary form must reproduce the above 9// copyright notice, this list of conditions and the following 10// disclaimer in the documentation and/or other materials provided 11// with the distribution. 12// * Neither the name of Google Inc. nor the names of its 13// contributors may be used to endorse or promote products derived 14// from this software without specific prior written permission. 15// 16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 28#ifndef V8_SPLAY_TREE_H_ 29#define V8_SPLAY_TREE_H_ 30 31#include "allocation.h" 32 33namespace v8 { 34namespace internal { 35 36 37// A splay tree. The config type parameter encapsulates the different 38// configurations of a concrete splay tree: 39// 40// typedef Key: the key type 41// typedef Value: the value type 42// static const Key kNoKey: the dummy key used when no key is set 43// static Value kNoValue(): the dummy value used to initialize nodes 44// static int (Compare)(Key& a, Key& b) -> {-1, 0, 1}: comparison function 45// 46// The tree is also parameterized by an allocation policy 47// (Allocator). The policy is used for allocating lists in the C free 48// store or the zone; see zone.h. 49 50// Forward defined as 51// template <typename Config, class Allocator = FreeStoreAllocationPolicy> 52// class SplayTree; 53template <typename Config, class AllocationPolicy> 54class SplayTree { 55 public: 56 typedef typename Config::Key Key; 57 typedef typename Config::Value Value; 58 59 class Locator; 60 61 SplayTree(AllocationPolicy allocator = AllocationPolicy()) 62 : root_(NULL), allocator_(allocator) { } 63 ~SplayTree(); 64 65 INLINE(void* operator new(size_t size, 66 AllocationPolicy allocator = AllocationPolicy())) { 67 return allocator.New(static_cast<int>(size)); 68 } 69 INLINE(void operator delete(void* p)) { 70 AllocationPolicy::Delete(p); 71 } 72 // Please the MSVC compiler. We should never have to execute this. 73 INLINE(void operator delete(void* p, AllocationPolicy policy)) { 74 UNREACHABLE(); 75 } 76 77 AllocationPolicy allocator() { return allocator_; } 78 79 // Checks if there is a mapping for the key. 80 bool Contains(const Key& key); 81 82 // Inserts the given key in this tree with the given value. Returns 83 // true if a node was inserted, otherwise false. If found the locator 84 // is enabled and provides access to the mapping for the key. 85 bool Insert(const Key& key, Locator* locator); 86 87 // Looks up the key in this tree and returns true if it was found, 88 // otherwise false. If the node is found the locator is enabled and 89 // provides access to the mapping for the key. 90 bool Find(const Key& key, Locator* locator); 91 92 // Finds the mapping with the greatest key less than or equal to the 93 // given key. 94 bool FindGreatestLessThan(const Key& key, Locator* locator); 95 96 // Find the mapping with the greatest key in this tree. 97 bool FindGreatest(Locator* locator); 98 99 // Finds the mapping with the least key greater than or equal to the 100 // given key. 101 bool FindLeastGreaterThan(const Key& key, Locator* locator); 102 103 // Find the mapping with the least key in this tree. 104 bool FindLeast(Locator* locator); 105 106 // Move the node from one key to another. 107 bool Move(const Key& old_key, const Key& new_key); 108 109 // Remove the node with the given key from the tree. 110 bool Remove(const Key& key); 111 112 // Remove all keys from the tree. 113 void Clear() { ResetRoot(); } 114 115 bool is_empty() { return root_ == NULL; } 116 117 // Perform the splay operation for the given key. Moves the node with 118 // the given key to the top of the tree. If no node has the given 119 // key, the last node on the search path is moved to the top of the 120 // tree. 121 void Splay(const Key& key); 122 123 class Node { 124 public: 125 Node(const Key& key, const Value& value) 126 : key_(key), 127 value_(value), 128 left_(NULL), 129 right_(NULL) { } 130 131 INLINE(void* operator new(size_t size, AllocationPolicy allocator)) { 132 return allocator.New(static_cast<int>(size)); 133 } 134 INLINE(void operator delete(void* p)) { 135 return AllocationPolicy::Delete(p); 136 } 137 // Please the MSVC compiler. We should never have to execute 138 // this. 139 INLINE(void operator delete(void* p, AllocationPolicy allocator)) { 140 UNREACHABLE(); 141 } 142 143 Key key() { return key_; } 144 Value value() { return value_; } 145 Node* left() { return left_; } 146 Node* right() { return right_; } 147 148 private: 149 friend class SplayTree; 150 friend class Locator; 151 Key key_; 152 Value value_; 153 Node* left_; 154 Node* right_; 155 }; 156 157 // A locator provides access to a node in the tree without actually 158 // exposing the node. 159 class Locator BASE_EMBEDDED { 160 public: 161 explicit Locator(Node* node) : node_(node) { } 162 Locator() : node_(NULL) { } 163 const Key& key() { return node_->key_; } 164 Value& value() { return node_->value_; } 165 void set_value(const Value& value) { node_->value_ = value; } 166 inline void bind(Node* node) { node_ = node; } 167 168 private: 169 Node* node_; 170 }; 171 172 template <class Callback> 173 void ForEach(Callback* callback); 174 175 protected: 176 // Resets tree root. Existing nodes become unreachable. 177 void ResetRoot() { root_ = NULL; } 178 179 private: 180 // Search for a node with a given key. If found, root_ points 181 // to the node. 182 bool FindInternal(const Key& key); 183 184 // Inserts a node assuming that root_ is already set up. 185 void InsertInternal(int cmp, Node* node); 186 187 // Removes root_ node. 188 void RemoveRootNode(const Key& key); 189 190 template<class Callback> 191 class NodeToPairAdaptor BASE_EMBEDDED { 192 public: 193 explicit NodeToPairAdaptor(Callback* callback) 194 : callback_(callback) { } 195 void Call(Node* node) { 196 callback_->Call(node->key(), node->value()); 197 } 198 199 private: 200 Callback* callback_; 201 202 DISALLOW_COPY_AND_ASSIGN(NodeToPairAdaptor); 203 }; 204 205 class NodeDeleter BASE_EMBEDDED { 206 public: 207 NodeDeleter() { } 208 void Call(Node* node) { AllocationPolicy::Delete(node); } 209 210 private: 211 DISALLOW_COPY_AND_ASSIGN(NodeDeleter); 212 }; 213 214 template <class Callback> 215 void ForEachNode(Callback* callback); 216 217 Node* root_; 218 AllocationPolicy allocator_; 219 220 DISALLOW_COPY_AND_ASSIGN(SplayTree); 221}; 222 223 224} } // namespace v8::internal 225 226#endif // V8_SPLAY_TREE_H_ 227