16ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// Copyright 2010 the V8 project authors. All rights reserved. 26ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// Redistribution and use in source and binary forms, with or without 36ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// modification, are permitted provided that the following conditions are 46ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// met: 56ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// 66ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// * Redistributions of source code must retain the above copyright 76ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// notice, this list of conditions and the following disclaimer. 86ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// * Redistributions in binary form must reproduce the above 96ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// copyright notice, this list of conditions and the following 106ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// disclaimer in the documentation and/or other materials provided 116ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// with the distribution. 126ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// * Neither the name of Google Inc. nor the names of its 136ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// contributors may be used to endorse or promote products derived 146ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// from this software without specific prior written permission. 156ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// 166ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 176ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 186ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 196ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 206ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 216ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 226ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 236ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 246ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 256ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 266ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 276ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 286ded16be15dd865a9b21ea304d5273c8be299c87Steve Block#ifndef V8_SPLAY_TREE_H_ 296ded16be15dd865a9b21ea304d5273c8be299c87Steve Block#define V8_SPLAY_TREE_H_ 306ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 31257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch#include "allocation.h" 32257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch 336ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocknamespace v8 { 346ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocknamespace internal { 356ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 366ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 376ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// A splay tree. The config type parameter encapsulates the different 386ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// configurations of a concrete splay tree: 396ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// 406ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// typedef Key: the key type 416ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// typedef Value: the value type 426ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// static const kNoKey: the dummy key used when no key is set 436ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// static const kNoValue: the dummy value used to initialize nodes 446ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// int (Compare)(Key& a, Key& b) -> {-1, 0, 1}: comparison function 456ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// 466ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// The tree is also parameterized by an allocation policy 476ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// (Allocator). The policy is used for allocating lists in the C free 486ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// store or the zone; see zone.h. 496ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 506ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// Forward defined as 516ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// template <typename Config, class Allocator = FreeStoreAllocationPolicy> 526ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// class SplayTree; 536ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocktemplate <typename Config, class Allocator> 546ded16be15dd865a9b21ea304d5273c8be299c87Steve Blockclass SplayTree { 556ded16be15dd865a9b21ea304d5273c8be299c87Steve Block public: 566ded16be15dd865a9b21ea304d5273c8be299c87Steve Block typedef typename Config::Key Key; 576ded16be15dd865a9b21ea304d5273c8be299c87Steve Block typedef typename Config::Value Value; 586ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 596ded16be15dd865a9b21ea304d5273c8be299c87Steve Block class Locator; 606ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 616ded16be15dd865a9b21ea304d5273c8be299c87Steve Block SplayTree() : root_(NULL) { } 626ded16be15dd865a9b21ea304d5273c8be299c87Steve Block ~SplayTree(); 636ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 646ded16be15dd865a9b21ea304d5273c8be299c87Steve Block INLINE(void* operator new(size_t size)) { 656ded16be15dd865a9b21ea304d5273c8be299c87Steve Block return Allocator::New(static_cast<int>(size)); 666ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 676ded16be15dd865a9b21ea304d5273c8be299c87Steve Block INLINE(void operator delete(void* p, size_t)) { return Allocator::Delete(p); } 686ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 696ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Inserts the given key in this tree with the given value. Returns 706ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // true if a node was inserted, otherwise false. If found the locator 716ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // is enabled and provides access to the mapping for the key. 726ded16be15dd865a9b21ea304d5273c8be299c87Steve Block bool Insert(const Key& key, Locator* locator); 736ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 746ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Looks up the key in this tree and returns true if it was found, 756ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // otherwise false. If the node is found the locator is enabled and 766ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // provides access to the mapping for the key. 776ded16be15dd865a9b21ea304d5273c8be299c87Steve Block bool Find(const Key& key, Locator* locator); 786ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 796ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Finds the mapping with the greatest key less than or equal to the 806ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // given key. 816ded16be15dd865a9b21ea304d5273c8be299c87Steve Block bool FindGreatestLessThan(const Key& key, Locator* locator); 826ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 836ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Find the mapping with the greatest key in this tree. 846ded16be15dd865a9b21ea304d5273c8be299c87Steve Block bool FindGreatest(Locator* locator); 856ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 866ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Finds the mapping with the least key greater than or equal to the 876ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // given key. 886ded16be15dd865a9b21ea304d5273c8be299c87Steve Block bool FindLeastGreaterThan(const Key& key, Locator* locator); 896ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 906ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Find the mapping with the least key in this tree. 916ded16be15dd865a9b21ea304d5273c8be299c87Steve Block bool FindLeast(Locator* locator); 926ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 936ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Move the node from one key to another. 946ded16be15dd865a9b21ea304d5273c8be299c87Steve Block bool Move(const Key& old_key, const Key& new_key); 956ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 966ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Remove the node with the given key from the tree. 976ded16be15dd865a9b21ea304d5273c8be299c87Steve Block bool Remove(const Key& key); 986ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 996ded16be15dd865a9b21ea304d5273c8be299c87Steve Block bool is_empty() { return root_ == NULL; } 1006ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1016ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Perform the splay operation for the given key. Moves the node with 1026ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // the given key to the top of the tree. If no node has the given 1036ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // key, the last node on the search path is moved to the top of the 1046ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // tree. 1056ded16be15dd865a9b21ea304d5273c8be299c87Steve Block void Splay(const Key& key); 1066ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1076ded16be15dd865a9b21ea304d5273c8be299c87Steve Block class Node { 1086ded16be15dd865a9b21ea304d5273c8be299c87Steve Block public: 1096ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Node(const Key& key, const Value& value) 1106ded16be15dd865a9b21ea304d5273c8be299c87Steve Block : key_(key), 1116ded16be15dd865a9b21ea304d5273c8be299c87Steve Block value_(value), 1126ded16be15dd865a9b21ea304d5273c8be299c87Steve Block left_(NULL), 1136ded16be15dd865a9b21ea304d5273c8be299c87Steve Block right_(NULL) { } 1146ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1156ded16be15dd865a9b21ea304d5273c8be299c87Steve Block INLINE(void* operator new(size_t size)) { 1166ded16be15dd865a9b21ea304d5273c8be299c87Steve Block return Allocator::New(static_cast<int>(size)); 1176ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 1186ded16be15dd865a9b21ea304d5273c8be299c87Steve Block INLINE(void operator delete(void* p, size_t)) { 1196ded16be15dd865a9b21ea304d5273c8be299c87Steve Block return Allocator::Delete(p); 1206ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 1216ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1226ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Key key() { return key_; } 1236ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Value value() { return value_; } 1246ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Node* left() { return left_; } 1256ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Node* right() { return right_; } 1266ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 127589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch private: 1286ded16be15dd865a9b21ea304d5273c8be299c87Steve Block friend class SplayTree; 1296ded16be15dd865a9b21ea304d5273c8be299c87Steve Block friend class Locator; 1306ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Key key_; 1316ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Value value_; 1326ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Node* left_; 1336ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Node* right_; 1346ded16be15dd865a9b21ea304d5273c8be299c87Steve Block }; 1356ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1366ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // A locator provides access to a node in the tree without actually 1376ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // exposing the node. 1386ded16be15dd865a9b21ea304d5273c8be299c87Steve Block class Locator BASE_EMBEDDED { 1396ded16be15dd865a9b21ea304d5273c8be299c87Steve Block public: 1406ded16be15dd865a9b21ea304d5273c8be299c87Steve Block explicit Locator(Node* node) : node_(node) { } 1416ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Locator() : node_(NULL) { } 1426ded16be15dd865a9b21ea304d5273c8be299c87Steve Block const Key& key() { return node_->key_; } 1436ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Value& value() { return node_->value_; } 1446ded16be15dd865a9b21ea304d5273c8be299c87Steve Block void set_value(const Value& value) { node_->value_ = value; } 1456ded16be15dd865a9b21ea304d5273c8be299c87Steve Block inline void bind(Node* node) { node_ = node; } 146589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch 1476ded16be15dd865a9b21ea304d5273c8be299c87Steve Block private: 1486ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Node* node_; 1496ded16be15dd865a9b21ea304d5273c8be299c87Steve Block }; 1506ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1516ded16be15dd865a9b21ea304d5273c8be299c87Steve Block template <class Callback> 1526ded16be15dd865a9b21ea304d5273c8be299c87Steve Block void ForEach(Callback* callback); 1536ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1546ded16be15dd865a9b21ea304d5273c8be299c87Steve Block protected: 1556ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Resets tree root. Existing nodes become unreachable. 1566ded16be15dd865a9b21ea304d5273c8be299c87Steve Block void ResetRoot() { root_ = NULL; } 1576ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1586ded16be15dd865a9b21ea304d5273c8be299c87Steve Block private: 1596ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Search for a node with a given key. If found, root_ points 1606ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // to the node. 1616ded16be15dd865a9b21ea304d5273c8be299c87Steve Block bool FindInternal(const Key& key); 1626ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1636ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Inserts a node assuming that root_ is already set up. 1646ded16be15dd865a9b21ea304d5273c8be299c87Steve Block void InsertInternal(int cmp, Node* node); 1656ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1666ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Removes root_ node. 1676ded16be15dd865a9b21ea304d5273c8be299c87Steve Block void RemoveRootNode(const Key& key); 1686ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1696ded16be15dd865a9b21ea304d5273c8be299c87Steve Block template<class Callback> 1706ded16be15dd865a9b21ea304d5273c8be299c87Steve Block class NodeToPairAdaptor BASE_EMBEDDED { 1716ded16be15dd865a9b21ea304d5273c8be299c87Steve Block public: 1726ded16be15dd865a9b21ea304d5273c8be299c87Steve Block explicit NodeToPairAdaptor(Callback* callback) 1736ded16be15dd865a9b21ea304d5273c8be299c87Steve Block : callback_(callback) { } 1746ded16be15dd865a9b21ea304d5273c8be299c87Steve Block void Call(Node* node) { 1756ded16be15dd865a9b21ea304d5273c8be299c87Steve Block callback_->Call(node->key(), node->value()); 1766ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 1776ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1786ded16be15dd865a9b21ea304d5273c8be299c87Steve Block private: 1796ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Callback* callback_; 1806ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1816ded16be15dd865a9b21ea304d5273c8be299c87Steve Block DISALLOW_COPY_AND_ASSIGN(NodeToPairAdaptor); 1826ded16be15dd865a9b21ea304d5273c8be299c87Steve Block }; 1836ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1846ded16be15dd865a9b21ea304d5273c8be299c87Steve Block class NodeDeleter BASE_EMBEDDED { 1856ded16be15dd865a9b21ea304d5273c8be299c87Steve Block public: 1866ded16be15dd865a9b21ea304d5273c8be299c87Steve Block NodeDeleter() { } 1876ded16be15dd865a9b21ea304d5273c8be299c87Steve Block void Call(Node* node) { delete node; } 1886ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1896ded16be15dd865a9b21ea304d5273c8be299c87Steve Block private: 1906ded16be15dd865a9b21ea304d5273c8be299c87Steve Block DISALLOW_COPY_AND_ASSIGN(NodeDeleter); 1916ded16be15dd865a9b21ea304d5273c8be299c87Steve Block }; 1926ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1936ded16be15dd865a9b21ea304d5273c8be299c87Steve Block template <class Callback> 1946ded16be15dd865a9b21ea304d5273c8be299c87Steve Block void ForEachNode(Callback* callback); 1956ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1966ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Node* root_; 1976ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1986ded16be15dd865a9b21ea304d5273c8be299c87Steve Block DISALLOW_COPY_AND_ASSIGN(SplayTree); 1996ded16be15dd865a9b21ea304d5273c8be299c87Steve Block}; 2006ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 2016ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 2026ded16be15dd865a9b21ea304d5273c8be299c87Steve Block} } // namespace v8::internal 2036ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 2046ded16be15dd865a9b21ea304d5273c8be299c87Steve Block#endif // V8_SPLAY_TREE_H_ 205