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