dart::SplayTree< Config, B, Allocator > Class Template Reference

#include <splay-tree.h>

Inheritance diagram for dart::SplayTree< Config, B, Allocator >:

Classes
class	Locator
class	Node

Public Types
typedef Config::Key	Key
typedef Config::Value	Value

Public Member Functions
	SplayTree (Allocator *allocator)
	~SplayTree ()
Allocator *	allocator ()
bool	Contains (const Key &key)
bool	Insert (const Key &key, Locator *locator)
bool	Find (const Key &key, Locator *locator)
bool	FindGreatestLessThan (const Key &key, Locator *locator)
bool	FindGreatest (Locator *locator)
bool	FindLeastGreaterThan (const Key &key, Locator *locator)
bool	FindLeast (Locator *locator)
bool	Move (const Key &old_key, const Key &new_key)
bool	Remove (const Key &key)
void	Clear ()
bool	is_empty ()
void	Splay (const Key &key)
template<class Callback >
void	ForEach (Callback *callback)
Public Member Functions inherited from B
	B ()
void	setValues (int v) override
bool	checkValues (int v) override
Public Member Functions inherited from A
	A ()
virtual	~A ()
void *	operator new (size_t size)
void	operator delete (void *p)

Protected Member Functions
void	ResetRoot ()

Additional Inherited Members
Static Public Member Functions inherited from A
static A *	Create (SkRandom *r)
static void	SetAllocator (size_t preallocSize, size_t minAllocSize)
static void	ResetAllocator ()
static void	ValidatePool ()

Detailed Description

template<typename Config, class B, class Allocator>
class dart::SplayTree< Config, B, Allocator >

Definition at line 29 of file splay-tree.h.

Member Typedef Documentation

Key

template<typename Config , class B , class Allocator >

typedef Config::Key dart::SplayTree< Config, B, Allocator >::Key

Definition at line 31 of file splay-tree.h.

Value

template<typename Config , class B , class Allocator >

typedef Config::Value dart::SplayTree< Config, B, Allocator >::Value

Definition at line 32 of file splay-tree.h.

Constructor & Destructor Documentation

SplayTree()

template<typename Config , class B , class Allocator >

dart::SplayTree< Config, B, Allocator >::SplayTree ( Allocator *  allocator )

inlineexplicit

Definition at line 36 of file splay-tree.h.

      : root_(nullptr), allocator_(allocator) {}

~SplayTree()

template<typename Config , class B , class Allocator >

dart::SplayTree< Config, B, Allocator >::~SplayTree

(

)

Definition at line 18 of file splay-tree-inl.h.

                                            {
  NodeDeleter deleter;
  ForEachNode(&deleter);
}

Member Function Documentation

allocator()

template<typename Config , class B , class Allocator >

Allocator * dart::SplayTree< Config, B, Allocator >::allocator ( )

inline

Definition at line 40 of file splay-tree.h.

{ return allocator_; }

Clear()

template<typename Config , class B , class Allocator >

void dart::SplayTree< Config, B, Allocator >::Clear ( )

inline

Definition at line 76 of file splay-tree.h.

{ ResetRoot(); }

Contains()

template<typename Config , class B , class Allocator >

bool dart::SplayTree< Config, B, Allocator >::Contains

(

const Key &

key

)

Definition at line 68 of file splay-tree-inl.h.

                                                             {
  return FindInternal(key);
}

Find()

template<typename Config , class B , class Allocator >

bool dart::SplayTree< Config, B, Allocator >::Find	(	const Key &	key,
		Locator *	locator
	)

Definition at line 73 of file splay-tree-inl.h.

                                                                           {
  if (FindInternal(key)) {
    locator->bind(root_);
    return true;
  } else {
    return false;
  }
}

FindGreatest()

template<typename Config , class B , class Allocator >

bool dart::SplayTree< Config, B, Allocator >::FindGreatest

(

Locator *

locator

)

Definition at line 127 of file splay-tree-inl.h.

                                                                   {
  if (is_empty()) return false;
  Node* current = root_;
  while (current->right_ != nullptr)
    current = current->right_;
  locator->bind(current);
  return true;
}

FindGreatestLessThan()

template<typename Config , class B , class Allocator >

bool dart::SplayTree< Config, B, Allocator >::FindGreatestLessThan	(	const Key &	key,
		Locator *	locator
	)

Definition at line 83 of file splay-tree-inl.h.

                                                                             {
  if (is_empty()) return false;
  // Splay on the key to move the node with the given key or the last
  // node on the search path to the top of the tree.
  Splay(key);
  // Now the result is either the root node or the greatest node in
  // the left subtree.
  int cmp = Config::Compare(root_->key_, key);
  if (cmp <= 0) {
    locator->bind(root_);
    return true;
  } else {
    Node* temp = root_;
    root_ = root_->left_;
    bool result = FindGreatest(locator);
    root_ = temp;
    return result;
  }
}

FindLeast()

template<typename Config , class B , class Allocator >

bool dart::SplayTree< Config, B, Allocator >::FindLeast

(

Locator *

locator

)

Definition at line 137 of file splay-tree-inl.h.

                                                                {
  if (is_empty()) return false;
  Node* current = root_;
  while (current->left_ != nullptr)
    current = current->left_;
  locator->bind(current);
  return true;
}

FindLeastGreaterThan()

template<typename Config , class B , class Allocator >

bool dart::SplayTree< Config, B, Allocator >::FindLeastGreaterThan	(	const Key &	key,
		Locator *	locator
	)

Definition at line 105 of file splay-tree-inl.h.

                                                                             {
  if (is_empty()) return false;
  // Splay on the key to move the node with the given key or the last
  // node on the search path to the top of the tree.
  Splay(key);
  // Now the result is either the root node or the least node in
  // the right subtree.
  int cmp = Config::Compare(root_->key_, key);
  if (cmp >= 0) {
    locator->bind(root_);
    return true;
  } else {
    Node* temp = root_;
    root_ = root_->right_;
    bool result = FindLeast(locator);
    root_ = temp;
    return result;
  }
}

ForEach()

template<typename Config , class B , class Allocator >

template<class Callback >

void dart::SplayTree< Config, B, Allocator >::ForEach

(

Callback *

callback

)

Definition at line 248 of file splay-tree-inl.h.

                                                                {
  NodeToPairAdaptor<Callback> callback_adaptor(callback);
  ForEachNode(&callback_adaptor);
}

Insert()

template<typename Config , class B , class Allocator >

bool dart::SplayTree< Config, B, Allocator >::Insert	(	const Key &	key,
		Locator *	locator
	)

Definition at line 24 of file splay-tree-inl.h.

                                                                             {
  if (is_empty()) {
    // If the tree is empty, insert the new node.
    root_ = new (allocator_) Node(key, Config::NoValue());
  } else {
    // Splay on the key to move the last node on the search path
    // for the key to the root of the tree.
    Splay(key);
    // Ignore repeated insertions with the same key.
    int cmp = Config::Compare(key, root_->key_);
    if (cmp == 0) {
      locator->bind(root_);
      return false;
    }
    // Insert the new node.
    Node* node = new (allocator_) Node(key, Config::NoValue());
    InsertInternal(cmp, node);
  }
  locator->bind(root_);
  return true;
}

is_empty()

template<typename Config , class B , class Allocator >

bool dart::SplayTree< Config, B, Allocator >::is_empty ( )

inline

Definition at line 78 of file splay-tree.h.

{ return root_ == nullptr; }

Move()

template<typename Config , class B , class Allocator >

bool dart::SplayTree< Config, B, Allocator >::Move	(	const Key &	old_key,
		const Key &	new_key
	)

Definition at line 147 of file splay-tree-inl.h.

                                                               {
  if (!FindInternal(old_key)) return false;
  Node* node_to_move = root_;
  RemoveRootNode(old_key);
  Splay(new_key);
  int cmp = Config::Compare(new_key, root_->key_);
  if (cmp == 0) {
    // A node with the target key already exists.
    delete node_to_move;
    return false;
  }
  node_to_move->key_ = new_key;
  InsertInternal(cmp, node_to_move);
  return true;
}

Remove()

template<typename Config , class B , class Allocator >

bool dart::SplayTree< Config, B, Allocator >::Remove

(

const Key &

key

)

Definition at line 165 of file splay-tree-inl.h.

                                                           {
  if (!FindInternal(key)) return false;
  Node* node_to_remove = root_;
  RemoveRootNode(key);
  delete node_to_remove;
  return true;
}

ResetRoot()

template<typename Config , class B , class Allocator >

void dart::SplayTree< Config, B, Allocator >::ResetRoot ( )

inlineprotected

Definition at line 125 of file splay-tree.h.

{ root_ = nullptr; }

Splay()

template<typename Config , class B , class Allocator >

void dart::SplayTree< Config, B, Allocator >::Splay

(

const Key &

key

)

Definition at line 192 of file splay-tree-inl.h.

                                                          {
  if (is_empty()) return;
  Node dummy_node(Config::kNoKey, Config::NoValue());
  // Create a dummy node.  The use of the dummy node is a bit
  // counter-intuitive: The right child of the dummy node will hold
  // the L tree of the algorithm.  The left child of the dummy node
  // will hold the R tree of the algorithm.  Using a dummy node, left
  // and right will always be nodes and we avoid special cases.
  Node* dummy = &dummy_node;
  Node* left = dummy;
  Node* right = dummy;
  Node* current = root_;
  while (true) {
    int cmp = Config::Compare(key, current->key_);
    if (cmp < 0) {
      if (current->left_ == nullptr) break;
      if (Config::Compare(key, current->left_->key_) < 0) {
        // Rotate right.
        Node* temp = current->left_;
        current->left_ = temp->right_;
        temp->right_ = current;
        current = temp;
        if (current->left_ == nullptr) break;
      }
      // Link right.
      right->left_ = current;
      right = current;
      current = current->left_;
    } else if (cmp > 0) {
      if (current->right_ == nullptr) break;
      if (Config::Compare(key, current->right_->key_) > 0) {
        // Rotate left.
        Node* temp = current->right_;
        current->right_ = temp->left_;
        temp->left_ = current;
        current = temp;
        if (current->right_ == nullptr) break;
      }
      // Link left.
      left->right_ = current;
      left = current;
      current = current->right_;
    } else {
      break;
    }
  }
  // Assemble.
  left->right_ = current->left_;
  right->left_ = current->right_;
  current->left_ = dummy->right_;
  current->right_ = dummy->left_;
  root_ = current;
}

---

The documentation for this class was generated from the following files:

• third_party/dart-lang/sdk/runtime/platform/splay-tree.h
• third_party/dart-lang/sdk/runtime/platform/splay-tree-inl.h