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_INL_H_ 296ded16be15dd865a9b21ea304d5273c8be299c87Steve Block#define V8_SPLAY_TREE_INL_H_ 306ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 316ded16be15dd865a9b21ea304d5273c8be299c87Steve Block#include "splay-tree.h" 326ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 336ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocknamespace v8 { 346ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocknamespace internal { 356ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 366ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 376ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocktemplate<typename Config, class Allocator> 386ded16be15dd865a9b21ea304d5273c8be299c87Steve BlockSplayTree<Config, Allocator>::~SplayTree() { 396ded16be15dd865a9b21ea304d5273c8be299c87Steve Block NodeDeleter deleter; 406ded16be15dd865a9b21ea304d5273c8be299c87Steve Block ForEachNode(&deleter); 416ded16be15dd865a9b21ea304d5273c8be299c87Steve Block} 426ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 436ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 446ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocktemplate<typename Config, class Allocator> 456ded16be15dd865a9b21ea304d5273c8be299c87Steve Blockbool SplayTree<Config, Allocator>::Insert(const Key& key, Locator* locator) { 466ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (is_empty()) { 476ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // If the tree is empty, insert the new node. 483ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch root_ = new Node(key, Config::NoValue()); 496ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } else { 506ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Splay on the key to move the last node on the search path 516ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // for the key to the root of the tree. 526ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Splay(key); 536ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Ignore repeated insertions with the same key. 546ded16be15dd865a9b21ea304d5273c8be299c87Steve Block int cmp = Config::Compare(key, root_->key_); 556ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (cmp == 0) { 566ded16be15dd865a9b21ea304d5273c8be299c87Steve Block locator->bind(root_); 576ded16be15dd865a9b21ea304d5273c8be299c87Steve Block return false; 586ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 596ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Insert the new node. 603ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Node* node = new Node(key, Config::NoValue()); 616ded16be15dd865a9b21ea304d5273c8be299c87Steve Block InsertInternal(cmp, node); 626ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 636ded16be15dd865a9b21ea304d5273c8be299c87Steve Block locator->bind(root_); 646ded16be15dd865a9b21ea304d5273c8be299c87Steve Block return true; 656ded16be15dd865a9b21ea304d5273c8be299c87Steve Block} 666ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 676ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 686ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocktemplate<typename Config, class Allocator> 696ded16be15dd865a9b21ea304d5273c8be299c87Steve Blockvoid SplayTree<Config, Allocator>::InsertInternal(int cmp, Node* node) { 706ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (cmp > 0) { 716ded16be15dd865a9b21ea304d5273c8be299c87Steve Block node->left_ = root_; 726ded16be15dd865a9b21ea304d5273c8be299c87Steve Block node->right_ = root_->right_; 736ded16be15dd865a9b21ea304d5273c8be299c87Steve Block root_->right_ = NULL; 746ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } else { 756ded16be15dd865a9b21ea304d5273c8be299c87Steve Block node->right_ = root_; 766ded16be15dd865a9b21ea304d5273c8be299c87Steve Block node->left_ = root_->left_; 776ded16be15dd865a9b21ea304d5273c8be299c87Steve Block root_->left_ = NULL; 786ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 796ded16be15dd865a9b21ea304d5273c8be299c87Steve Block root_ = node; 806ded16be15dd865a9b21ea304d5273c8be299c87Steve Block} 816ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 826ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 836ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocktemplate<typename Config, class Allocator> 846ded16be15dd865a9b21ea304d5273c8be299c87Steve Blockbool SplayTree<Config, Allocator>::FindInternal(const Key& key) { 856ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (is_empty()) 866ded16be15dd865a9b21ea304d5273c8be299c87Steve Block return false; 876ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Splay(key); 886ded16be15dd865a9b21ea304d5273c8be299c87Steve Block return Config::Compare(key, root_->key_) == 0; 896ded16be15dd865a9b21ea304d5273c8be299c87Steve Block} 906ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 916ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 926ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocktemplate<typename Config, class Allocator> 936ded16be15dd865a9b21ea304d5273c8be299c87Steve Blockbool SplayTree<Config, Allocator>::Find(const Key& key, Locator* locator) { 946ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (FindInternal(key)) { 956ded16be15dd865a9b21ea304d5273c8be299c87Steve Block locator->bind(root_); 966ded16be15dd865a9b21ea304d5273c8be299c87Steve Block return true; 976ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } else { 986ded16be15dd865a9b21ea304d5273c8be299c87Steve Block return false; 996ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 1006ded16be15dd865a9b21ea304d5273c8be299c87Steve Block} 1016ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1026ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1036ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocktemplate<typename Config, class Allocator> 1046ded16be15dd865a9b21ea304d5273c8be299c87Steve Blockbool SplayTree<Config, Allocator>::FindGreatestLessThan(const Key& key, 1056ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Locator* locator) { 1066ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (is_empty()) 1076ded16be15dd865a9b21ea304d5273c8be299c87Steve Block return false; 1086ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Splay on the key to move the node with the given key or the last 1096ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // node on the search path to the top of the tree. 1106ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Splay(key); 1116ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Now the result is either the root node or the greatest node in 1126ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // the left subtree. 1136ded16be15dd865a9b21ea304d5273c8be299c87Steve Block int cmp = Config::Compare(root_->key_, key); 1146ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (cmp <= 0) { 1156ded16be15dd865a9b21ea304d5273c8be299c87Steve Block locator->bind(root_); 1166ded16be15dd865a9b21ea304d5273c8be299c87Steve Block return true; 1176ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } else { 1186ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Node* temp = root_; 1196ded16be15dd865a9b21ea304d5273c8be299c87Steve Block root_ = root_->left_; 1206ded16be15dd865a9b21ea304d5273c8be299c87Steve Block bool result = FindGreatest(locator); 1216ded16be15dd865a9b21ea304d5273c8be299c87Steve Block root_ = temp; 1226ded16be15dd865a9b21ea304d5273c8be299c87Steve Block return result; 1236ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 1246ded16be15dd865a9b21ea304d5273c8be299c87Steve Block} 1256ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1266ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1276ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocktemplate<typename Config, class Allocator> 1286ded16be15dd865a9b21ea304d5273c8be299c87Steve Blockbool SplayTree<Config, Allocator>::FindLeastGreaterThan(const Key& key, 1296ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Locator* locator) { 1306ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (is_empty()) 1316ded16be15dd865a9b21ea304d5273c8be299c87Steve Block return false; 1326ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Splay on the key to move the node with the given key or the last 1336ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // node on the search path to the top of the tree. 1346ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Splay(key); 1356ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Now the result is either the root node or the least node in 1366ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // the right subtree. 1376ded16be15dd865a9b21ea304d5273c8be299c87Steve Block int cmp = Config::Compare(root_->key_, key); 1386ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (cmp >= 0) { 1396ded16be15dd865a9b21ea304d5273c8be299c87Steve Block locator->bind(root_); 1406ded16be15dd865a9b21ea304d5273c8be299c87Steve Block return true; 1416ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } else { 1426ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Node* temp = root_; 1436ded16be15dd865a9b21ea304d5273c8be299c87Steve Block root_ = root_->right_; 1446ded16be15dd865a9b21ea304d5273c8be299c87Steve Block bool result = FindLeast(locator); 1456ded16be15dd865a9b21ea304d5273c8be299c87Steve Block root_ = temp; 1466ded16be15dd865a9b21ea304d5273c8be299c87Steve Block return result; 1476ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 1486ded16be15dd865a9b21ea304d5273c8be299c87Steve Block} 1496ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1506ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1516ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocktemplate<typename Config, class Allocator> 1526ded16be15dd865a9b21ea304d5273c8be299c87Steve Blockbool SplayTree<Config, Allocator>::FindGreatest(Locator* locator) { 1536ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (is_empty()) 1546ded16be15dd865a9b21ea304d5273c8be299c87Steve Block return false; 1556ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Node* current = root_; 1566ded16be15dd865a9b21ea304d5273c8be299c87Steve Block while (current->right_ != NULL) 1576ded16be15dd865a9b21ea304d5273c8be299c87Steve Block current = current->right_; 1586ded16be15dd865a9b21ea304d5273c8be299c87Steve Block locator->bind(current); 1596ded16be15dd865a9b21ea304d5273c8be299c87Steve Block return true; 1606ded16be15dd865a9b21ea304d5273c8be299c87Steve Block} 1616ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1626ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1636ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocktemplate<typename Config, class Allocator> 1646ded16be15dd865a9b21ea304d5273c8be299c87Steve Blockbool SplayTree<Config, Allocator>::FindLeast(Locator* locator) { 1656ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (is_empty()) 1666ded16be15dd865a9b21ea304d5273c8be299c87Steve Block return false; 1676ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Node* current = root_; 1686ded16be15dd865a9b21ea304d5273c8be299c87Steve Block while (current->left_ != NULL) 1696ded16be15dd865a9b21ea304d5273c8be299c87Steve Block current = current->left_; 1706ded16be15dd865a9b21ea304d5273c8be299c87Steve Block locator->bind(current); 1716ded16be15dd865a9b21ea304d5273c8be299c87Steve Block return true; 1726ded16be15dd865a9b21ea304d5273c8be299c87Steve Block} 1736ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1746ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1756ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocktemplate<typename Config, class Allocator> 1766ded16be15dd865a9b21ea304d5273c8be299c87Steve Blockbool SplayTree<Config, Allocator>::Move(const Key& old_key, 1776ded16be15dd865a9b21ea304d5273c8be299c87Steve Block const Key& new_key) { 1786ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (!FindInternal(old_key)) 1796ded16be15dd865a9b21ea304d5273c8be299c87Steve Block return false; 1806ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Node* node_to_move = root_; 1816ded16be15dd865a9b21ea304d5273c8be299c87Steve Block RemoveRootNode(old_key); 1826ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Splay(new_key); 1836ded16be15dd865a9b21ea304d5273c8be299c87Steve Block int cmp = Config::Compare(new_key, root_->key_); 1846ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (cmp == 0) { 1856ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // A node with the target key already exists. 1866ded16be15dd865a9b21ea304d5273c8be299c87Steve Block delete node_to_move; 1876ded16be15dd865a9b21ea304d5273c8be299c87Steve Block return false; 1886ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 1896ded16be15dd865a9b21ea304d5273c8be299c87Steve Block node_to_move->key_ = new_key; 1906ded16be15dd865a9b21ea304d5273c8be299c87Steve Block InsertInternal(cmp, node_to_move); 1916ded16be15dd865a9b21ea304d5273c8be299c87Steve Block return true; 1926ded16be15dd865a9b21ea304d5273c8be299c87Steve Block} 1936ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1946ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1956ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocktemplate<typename Config, class Allocator> 1966ded16be15dd865a9b21ea304d5273c8be299c87Steve Blockbool SplayTree<Config, Allocator>::Remove(const Key& key) { 1976ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (!FindInternal(key)) 1986ded16be15dd865a9b21ea304d5273c8be299c87Steve Block return false; 1996ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Node* node_to_remove = root_; 2006ded16be15dd865a9b21ea304d5273c8be299c87Steve Block RemoveRootNode(key); 2016ded16be15dd865a9b21ea304d5273c8be299c87Steve Block delete node_to_remove; 2026ded16be15dd865a9b21ea304d5273c8be299c87Steve Block return true; 2036ded16be15dd865a9b21ea304d5273c8be299c87Steve Block} 2046ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 2056ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 2066ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocktemplate<typename Config, class Allocator> 2076ded16be15dd865a9b21ea304d5273c8be299c87Steve Blockvoid SplayTree<Config, Allocator>::RemoveRootNode(const Key& key) { 2086ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (root_->left_ == NULL) { 2096ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // No left child, so the new tree is just the right child. 2106ded16be15dd865a9b21ea304d5273c8be299c87Steve Block root_ = root_->right_; 2116ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } else { 2126ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Left child exists. 2136ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Node* right = root_->right_; 2146ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Make the original left child the new root. 2156ded16be15dd865a9b21ea304d5273c8be299c87Steve Block root_ = root_->left_; 2166ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Splay to make sure that the new root has an empty right child. 2176ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Splay(key); 2186ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Insert the original right child as the right child of the new 2196ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // root. 2206ded16be15dd865a9b21ea304d5273c8be299c87Steve Block root_->right_ = right; 2216ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 2226ded16be15dd865a9b21ea304d5273c8be299c87Steve Block} 2236ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 2246ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 2256ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocktemplate<typename Config, class Allocator> 2266ded16be15dd865a9b21ea304d5273c8be299c87Steve Blockvoid SplayTree<Config, Allocator>::Splay(const Key& key) { 2276ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (is_empty()) 2286ded16be15dd865a9b21ea304d5273c8be299c87Steve Block return; 2293ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Node dummy_node(Config::kNoKey, Config::NoValue()); 2306ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Create a dummy node. The use of the dummy node is a bit 2316ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // counter-intuitive: The right child of the dummy node will hold 2326ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // the L tree of the algorithm. The left child of the dummy node 2336ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // will hold the R tree of the algorithm. Using a dummy node, left 2346ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // and right will always be nodes and we avoid special cases. 2356ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Node* dummy = &dummy_node; 2366ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Node* left = dummy; 2376ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Node* right = dummy; 2386ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Node* current = root_; 2396ded16be15dd865a9b21ea304d5273c8be299c87Steve Block while (true) { 2406ded16be15dd865a9b21ea304d5273c8be299c87Steve Block int cmp = Config::Compare(key, current->key_); 2416ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (cmp < 0) { 2426ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (current->left_ == NULL) 2436ded16be15dd865a9b21ea304d5273c8be299c87Steve Block break; 2446ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (Config::Compare(key, current->left_->key_) < 0) { 2456ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Rotate right. 2466ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Node* temp = current->left_; 2476ded16be15dd865a9b21ea304d5273c8be299c87Steve Block current->left_ = temp->right_; 2486ded16be15dd865a9b21ea304d5273c8be299c87Steve Block temp->right_ = current; 2496ded16be15dd865a9b21ea304d5273c8be299c87Steve Block current = temp; 2506ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (current->left_ == NULL) 2516ded16be15dd865a9b21ea304d5273c8be299c87Steve Block break; 2526ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 2536ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Link right. 2546ded16be15dd865a9b21ea304d5273c8be299c87Steve Block right->left_ = current; 2556ded16be15dd865a9b21ea304d5273c8be299c87Steve Block right = current; 2566ded16be15dd865a9b21ea304d5273c8be299c87Steve Block current = current->left_; 2576ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } else if (cmp > 0) { 2586ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (current->right_ == NULL) 2596ded16be15dd865a9b21ea304d5273c8be299c87Steve Block break; 2606ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (Config::Compare(key, current->right_->key_) > 0) { 2616ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Rotate left. 2626ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Node* temp = current->right_; 2636ded16be15dd865a9b21ea304d5273c8be299c87Steve Block current->right_ = temp->left_; 2646ded16be15dd865a9b21ea304d5273c8be299c87Steve Block temp->left_ = current; 2656ded16be15dd865a9b21ea304d5273c8be299c87Steve Block current = temp; 2666ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (current->right_ == NULL) 2676ded16be15dd865a9b21ea304d5273c8be299c87Steve Block break; 2686ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 2696ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Link left. 2706ded16be15dd865a9b21ea304d5273c8be299c87Steve Block left->right_ = current; 2716ded16be15dd865a9b21ea304d5273c8be299c87Steve Block left = current; 2726ded16be15dd865a9b21ea304d5273c8be299c87Steve Block current = current->right_; 2736ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } else { 2746ded16be15dd865a9b21ea304d5273c8be299c87Steve Block break; 2756ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 2766ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 2776ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Assemble. 2786ded16be15dd865a9b21ea304d5273c8be299c87Steve Block left->right_ = current->left_; 2796ded16be15dd865a9b21ea304d5273c8be299c87Steve Block right->left_ = current->right_; 2806ded16be15dd865a9b21ea304d5273c8be299c87Steve Block current->left_ = dummy->right_; 2816ded16be15dd865a9b21ea304d5273c8be299c87Steve Block current->right_ = dummy->left_; 2826ded16be15dd865a9b21ea304d5273c8be299c87Steve Block root_ = current; 2836ded16be15dd865a9b21ea304d5273c8be299c87Steve Block} 2846ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 2856ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 2866ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocktemplate <typename Config, class Allocator> template <class Callback> 2876ded16be15dd865a9b21ea304d5273c8be299c87Steve Blockvoid SplayTree<Config, Allocator>::ForEach(Callback* callback) { 2886ded16be15dd865a9b21ea304d5273c8be299c87Steve Block NodeToPairAdaptor<Callback> callback_adaptor(callback); 2896ded16be15dd865a9b21ea304d5273c8be299c87Steve Block ForEachNode(&callback_adaptor); 2906ded16be15dd865a9b21ea304d5273c8be299c87Steve Block} 2916ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 2926ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 2936ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocktemplate <typename Config, class Allocator> template <class Callback> 2946ded16be15dd865a9b21ea304d5273c8be299c87Steve Blockvoid SplayTree<Config, Allocator>::ForEachNode(Callback* callback) { 2956ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Pre-allocate some space for tiny trees. 2966ded16be15dd865a9b21ea304d5273c8be299c87Steve Block List<Node*, Allocator> nodes_to_visit(10); 2976ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (root_ != NULL) nodes_to_visit.Add(root_); 2986ded16be15dd865a9b21ea304d5273c8be299c87Steve Block int pos = 0; 2996ded16be15dd865a9b21ea304d5273c8be299c87Steve Block while (pos < nodes_to_visit.length()) { 3006ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Node* node = nodes_to_visit[pos++]; 3016ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (node->left() != NULL) nodes_to_visit.Add(node->left()); 3026ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (node->right() != NULL) nodes_to_visit.Add(node->right()); 3036ded16be15dd865a9b21ea304d5273c8be299c87Steve Block callback->Call(node); 3046ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 3056ded16be15dd865a9b21ea304d5273c8be299c87Steve Block} 3066ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 3076ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 3086ded16be15dd865a9b21ea304d5273c8be299c87Steve Block} } // namespace v8::internal 3096ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 3106ded16be15dd865a9b21ea304d5273c8be299c87Steve Block#endif // V8_SPLAY_TREE_INL_H_ 311