16ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// Copyright 2010 the V8 project authors. All rights reserved. 2b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Use of this source code is governed by a BSD-style license that can be 3b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// found in the LICENSE file. 46ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 56ded16be15dd865a9b21ea304d5273c8be299c87Steve Block#ifndef V8_SPLAY_TREE_H_ 66ded16be15dd865a9b21ea304d5273c8be299c87Steve Block#define V8_SPLAY_TREE_H_ 76ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 8b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/allocation.h" 9257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch 106ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocknamespace v8 { 116ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocknamespace internal { 126ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 136ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 146ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// A splay tree. The config type parameter encapsulates the different 156ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// configurations of a concrete splay tree: 166ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// 176ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// typedef Key: the key type 186ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// typedef Value: the value type 19b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// static const Key kNoKey: the dummy key used when no key is set 20b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// static Value kNoValue(): the dummy value used to initialize nodes 21b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// static int (Compare)(Key& a, Key& b) -> {-1, 0, 1}: comparison function 226ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// 236ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// The tree is also parameterized by an allocation policy 246ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// (Allocator). The policy is used for allocating lists in the C free 256ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// store or the zone; see zone.h. 266ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 276ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// Forward defined as 286ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// template <typename Config, class Allocator = FreeStoreAllocationPolicy> 296ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// class SplayTree; 30b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochtemplate <typename Config, class AllocationPolicy> 316ded16be15dd865a9b21ea304d5273c8be299c87Steve Blockclass SplayTree { 326ded16be15dd865a9b21ea304d5273c8be299c87Steve Block public: 336ded16be15dd865a9b21ea304d5273c8be299c87Steve Block typedef typename Config::Key Key; 346ded16be15dd865a9b21ea304d5273c8be299c87Steve Block typedef typename Config::Value Value; 356ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 366ded16be15dd865a9b21ea304d5273c8be299c87Steve Block class Locator; 376ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 38b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch explicit SplayTree(AllocationPolicy allocator = AllocationPolicy()) 39b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch : root_(NULL), allocator_(allocator) {} 406ded16be15dd865a9b21ea304d5273c8be299c87Steve Block ~SplayTree(); 416ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 42b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch INLINE(void* operator new(size_t size, 43b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch AllocationPolicy allocator = AllocationPolicy())) { 44b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return allocator.New(static_cast<int>(size)); 45b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 46b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch INLINE(void operator delete(void* p)) { 47b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch AllocationPolicy::Delete(p); 48b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 49b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Please the MSVC compiler. We should never have to execute this. 50b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch INLINE(void operator delete(void* p, AllocationPolicy policy)) { 51b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UNREACHABLE(); 526ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 53b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 54b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch AllocationPolicy allocator() { return allocator_; } 55b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 56b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Checks if there is a mapping for the key. 57b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool Contains(const Key& key); 586ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 596ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Inserts the given key in this tree with the given value. Returns 606ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // true if a node was inserted, otherwise false. If found the locator 616ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // is enabled and provides access to the mapping for the key. 626ded16be15dd865a9b21ea304d5273c8be299c87Steve Block bool Insert(const Key& key, Locator* locator); 636ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 646ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Looks up the key in this tree and returns true if it was found, 656ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // otherwise false. If the node is found the locator is enabled and 666ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // provides access to the mapping for the key. 676ded16be15dd865a9b21ea304d5273c8be299c87Steve Block bool Find(const Key& key, Locator* locator); 686ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 696ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Finds the mapping with the greatest key less than or equal to the 706ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // given key. 716ded16be15dd865a9b21ea304d5273c8be299c87Steve Block bool FindGreatestLessThan(const Key& key, Locator* locator); 726ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 736ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Find the mapping with the greatest key in this tree. 746ded16be15dd865a9b21ea304d5273c8be299c87Steve Block bool FindGreatest(Locator* locator); 756ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 766ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Finds the mapping with the least key greater than or equal to the 776ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // given key. 786ded16be15dd865a9b21ea304d5273c8be299c87Steve Block bool FindLeastGreaterThan(const Key& key, Locator* locator); 796ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 806ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Find the mapping with the least key in this tree. 816ded16be15dd865a9b21ea304d5273c8be299c87Steve Block bool FindLeast(Locator* locator); 826ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 836ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Move the node from one key to another. 846ded16be15dd865a9b21ea304d5273c8be299c87Steve Block bool Move(const Key& old_key, const Key& new_key); 856ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 866ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Remove the node with the given key from the tree. 876ded16be15dd865a9b21ea304d5273c8be299c87Steve Block bool Remove(const Key& key); 886ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 89b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Remove all keys from the tree. 90b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Clear() { ResetRoot(); } 91b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 926ded16be15dd865a9b21ea304d5273c8be299c87Steve Block bool is_empty() { return root_ == NULL; } 936ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 946ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Perform the splay operation for the given key. Moves the node with 956ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // the given key to the top of the tree. If no node has the given 966ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // key, the last node on the search path is moved to the top of the 976ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // tree. 986ded16be15dd865a9b21ea304d5273c8be299c87Steve Block void Splay(const Key& key); 996ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1006ded16be15dd865a9b21ea304d5273c8be299c87Steve Block class Node { 1016ded16be15dd865a9b21ea304d5273c8be299c87Steve Block public: 1026ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Node(const Key& key, const Value& value) 1036ded16be15dd865a9b21ea304d5273c8be299c87Steve Block : key_(key), 1046ded16be15dd865a9b21ea304d5273c8be299c87Steve Block value_(value), 1056ded16be15dd865a9b21ea304d5273c8be299c87Steve Block left_(NULL), 1066ded16be15dd865a9b21ea304d5273c8be299c87Steve Block right_(NULL) { } 1076ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 108b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch INLINE(void* operator new(size_t size, AllocationPolicy allocator)) { 109b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return allocator.New(static_cast<int>(size)); 110b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 111b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch INLINE(void operator delete(void* p)) { 112b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return AllocationPolicy::Delete(p); 1136ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 114b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Please the MSVC compiler. We should never have to execute 115b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // this. 116b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch INLINE(void operator delete(void* p, AllocationPolicy allocator)) { 117b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UNREACHABLE(); 1186ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 1196ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1206ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Key key() { return key_; } 1216ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Value value() { return value_; } 1226ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Node* left() { return left_; } 1236ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Node* right() { return right_; } 1246ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 125589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch private: 1266ded16be15dd865a9b21ea304d5273c8be299c87Steve Block friend class SplayTree; 1276ded16be15dd865a9b21ea304d5273c8be299c87Steve Block friend class Locator; 1286ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Key key_; 1296ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Value value_; 1306ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Node* left_; 1316ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Node* right_; 1326ded16be15dd865a9b21ea304d5273c8be299c87Steve Block }; 1336ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1346ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // A locator provides access to a node in the tree without actually 1356ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // exposing the node. 1366ded16be15dd865a9b21ea304d5273c8be299c87Steve Block class Locator BASE_EMBEDDED { 1376ded16be15dd865a9b21ea304d5273c8be299c87Steve Block public: 1386ded16be15dd865a9b21ea304d5273c8be299c87Steve Block explicit Locator(Node* node) : node_(node) { } 1396ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Locator() : node_(NULL) { } 1406ded16be15dd865a9b21ea304d5273c8be299c87Steve Block const Key& key() { return node_->key_; } 1416ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Value& value() { return node_->value_; } 1426ded16be15dd865a9b21ea304d5273c8be299c87Steve Block void set_value(const Value& value) { node_->value_ = value; } 1436ded16be15dd865a9b21ea304d5273c8be299c87Steve Block inline void bind(Node* node) { node_ = node; } 144589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch 1456ded16be15dd865a9b21ea304d5273c8be299c87Steve Block private: 1466ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Node* node_; 1476ded16be15dd865a9b21ea304d5273c8be299c87Steve Block }; 1486ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1496ded16be15dd865a9b21ea304d5273c8be299c87Steve Block template <class Callback> 1506ded16be15dd865a9b21ea304d5273c8be299c87Steve Block void ForEach(Callback* callback); 1516ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1526ded16be15dd865a9b21ea304d5273c8be299c87Steve Block protected: 1536ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Resets tree root. Existing nodes become unreachable. 1546ded16be15dd865a9b21ea304d5273c8be299c87Steve Block void ResetRoot() { root_ = NULL; } 1556ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1566ded16be15dd865a9b21ea304d5273c8be299c87Steve Block private: 1576ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Search for a node with a given key. If found, root_ points 1586ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // to the node. 1596ded16be15dd865a9b21ea304d5273c8be299c87Steve Block bool FindInternal(const Key& key); 1606ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1616ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Inserts a node assuming that root_ is already set up. 1626ded16be15dd865a9b21ea304d5273c8be299c87Steve Block void InsertInternal(int cmp, Node* node); 1636ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1646ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Removes root_ node. 1656ded16be15dd865a9b21ea304d5273c8be299c87Steve Block void RemoveRootNode(const Key& key); 1666ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1676ded16be15dd865a9b21ea304d5273c8be299c87Steve Block template<class Callback> 1686ded16be15dd865a9b21ea304d5273c8be299c87Steve Block class NodeToPairAdaptor BASE_EMBEDDED { 1696ded16be15dd865a9b21ea304d5273c8be299c87Steve Block public: 1706ded16be15dd865a9b21ea304d5273c8be299c87Steve Block explicit NodeToPairAdaptor(Callback* callback) 1716ded16be15dd865a9b21ea304d5273c8be299c87Steve Block : callback_(callback) { } 1726ded16be15dd865a9b21ea304d5273c8be299c87Steve Block void Call(Node* node) { 1736ded16be15dd865a9b21ea304d5273c8be299c87Steve Block callback_->Call(node->key(), node->value()); 1746ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 1756ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1766ded16be15dd865a9b21ea304d5273c8be299c87Steve Block private: 1776ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Callback* callback_; 1786ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1796ded16be15dd865a9b21ea304d5273c8be299c87Steve Block DISALLOW_COPY_AND_ASSIGN(NodeToPairAdaptor); 1806ded16be15dd865a9b21ea304d5273c8be299c87Steve Block }; 1816ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1826ded16be15dd865a9b21ea304d5273c8be299c87Steve Block class NodeDeleter BASE_EMBEDDED { 1836ded16be15dd865a9b21ea304d5273c8be299c87Steve Block public: 1846ded16be15dd865a9b21ea304d5273c8be299c87Steve Block NodeDeleter() { } 185b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Call(Node* node) { AllocationPolicy::Delete(node); } 1866ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1876ded16be15dd865a9b21ea304d5273c8be299c87Steve Block private: 1886ded16be15dd865a9b21ea304d5273c8be299c87Steve Block DISALLOW_COPY_AND_ASSIGN(NodeDeleter); 1896ded16be15dd865a9b21ea304d5273c8be299c87Steve Block }; 1906ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1916ded16be15dd865a9b21ea304d5273c8be299c87Steve Block template <class Callback> 1926ded16be15dd865a9b21ea304d5273c8be299c87Steve Block void ForEachNode(Callback* callback); 1936ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1946ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Node* root_; 195b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch AllocationPolicy allocator_; 1966ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1976ded16be15dd865a9b21ea304d5273c8be299c87Steve Block DISALLOW_COPY_AND_ASSIGN(SplayTree); 1986ded16be15dd865a9b21ea304d5273c8be299c87Steve Block}; 1996ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 2006ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 2016ded16be15dd865a9b21ea304d5273c8be299c87Steve Block} } // namespace v8::internal 2026ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 2036ded16be15dd865a9b21ea304d5273c8be299c87Steve Block#endif // V8_SPLAY_TREE_H_ 204