splay-tree-inl.h 7.95 KB
Newer Older
1
// Copyright 2010 the V8 project authors. All rights reserved.
2 3
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4 5 6 7

#ifndef V8_SPLAY_TREE_INL_H_
#define V8_SPLAY_TREE_INL_H_

8 9
#include <vector>

10
#include "src/splay-tree.h"
11 12 13 14 15 16 17 18 19 20 21 22 23

namespace v8 {
namespace internal {


template<typename Config, class Allocator>
SplayTree<Config, Allocator>::~SplayTree() {
  NodeDeleter deleter;
  ForEachNode(&deleter);
}


template<typename Config, class Allocator>
24
bool SplayTree<Config, Allocator>::Insert(const Key& key,
25
                                          Locator* locator) {
26 27
  if (is_empty()) {
    // If the tree is empty, insert the new node.
28
    root_ = new(allocator_) Node(key, Config::NoValue());
29 30 31 32 33 34 35 36 37 38 39
  } 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.
40
    Node* node = new(allocator_) Node(key, Config::NoValue());
41
    InsertInternal(cmp, node);
42 43 44 45 46 47 48
  }
  locator->bind(root_);
  return true;
}


template<typename Config, class Allocator>
49 50 51 52
void SplayTree<Config, Allocator>::InsertInternal(int cmp, Node* node) {
  if (cmp > 0) {
    node->left_ = root_;
    node->right_ = root_->right_;
53
    root_->right_ = nullptr;
54 55 56
  } else {
    node->right_ = root_;
    node->left_ = root_->left_;
57
    root_->left_ = nullptr;
58 59 60 61 62 63 64
  }
  root_ = node;
}


template<typename Config, class Allocator>
bool SplayTree<Config, Allocator>::FindInternal(const Key& key) {
65 66 67
  if (is_empty())
    return false;
  Splay(key);
68 69 70 71
  return Config::Compare(key, root_->key_) == 0;
}


72 73 74 75 76 77
template<typename Config, class Allocator>
bool SplayTree<Config, Allocator>::Contains(const Key& key) {
  return FindInternal(key);
}


78 79 80
template<typename Config, class Allocator>
bool SplayTree<Config, Allocator>::Find(const Key& key, Locator* locator) {
  if (FindInternal(key)) {
81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141
    locator->bind(root_);
    return true;
  } else {
    return false;
  }
}


template<typename Config, class Allocator>
bool SplayTree<Config, Allocator>::FindGreatestLessThan(const Key& key,
                                                        Locator* locator) {
  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;
  }
}


template<typename Config, class Allocator>
bool SplayTree<Config, Allocator>::FindLeastGreaterThan(const Key& key,
                                                        Locator* locator) {
  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;
  }
}


template<typename Config, class Allocator>
bool SplayTree<Config, Allocator>::FindGreatest(Locator* locator) {
  if (is_empty())
    return false;
  Node* current = root_;
142
  while (current->right_ != nullptr) current = current->right_;
143 144 145 146 147 148 149 150 151 152
  locator->bind(current);
  return true;
}


template<typename Config, class Allocator>
bool SplayTree<Config, Allocator>::FindLeast(Locator* locator) {
  if (is_empty())
    return false;
  Node* current = root_;
153
  while (current->left_ != nullptr) current = current->left_;
154 155 156 157 158 159
  locator->bind(current);
  return true;
}


template<typename Config, class Allocator>
160 161 162
bool SplayTree<Config, Allocator>::Move(const Key& old_key,
                                        const Key& new_key) {
  if (!FindInternal(old_key))
163
    return false;
164 165 166 167 168 169 170
  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;
171
    return false;
172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191
  }
  node_to_move->key_ = new_key;
  InsertInternal(cmp, node_to_move);
  return true;
}


template<typename Config, class Allocator>
bool SplayTree<Config, Allocator>::Remove(const Key& key) {
  if (!FindInternal(key))
    return false;
  Node* node_to_remove = root_;
  RemoveRootNode(key);
  delete node_to_remove;
  return true;
}


template<typename Config, class Allocator>
void SplayTree<Config, Allocator>::RemoveRootNode(const Key& key) {
192
  if (root_->left_ == nullptr) {
193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212
    // No left child, so the new tree is just the right child.
    root_ = root_->right_;
  } else {
    // Left child exists.
    Node* right = root_->right_;
    // Make the original left child the new root.
    root_ = root_->left_;
    // Splay to make sure that the new root has an empty right child.
    Splay(key);
    // Insert the original right child as the right child of the new
    // root.
    root_->right_ = right;
  }
}


template<typename Config, class Allocator>
void SplayTree<Config, Allocator>::Splay(const Key& key) {
  if (is_empty())
    return;
213
  Node dummy_node(Config::kNoKey, Config::NoValue());
214 215 216 217 218 219 220 221 222 223 224 225
  // 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) {
226
      if (current->left_ == nullptr) break;
227 228 229 230 231 232
      if (Config::Compare(key, current->left_->key_) < 0) {
        // Rotate right.
        Node* temp = current->left_;
        current->left_ = temp->right_;
        temp->right_ = current;
        current = temp;
233
        if (current->left_ == nullptr) break;
234 235 236 237 238 239
      }
      // Link right.
      right->left_ = current;
      right = current;
      current = current->left_;
    } else if (cmp > 0) {
240
      if (current->right_ == nullptr) break;
241 242 243 244 245 246
      if (Config::Compare(key, current->right_->key_) > 0) {
        // Rotate left.
        Node* temp = current->right_;
        current->right_ = temp->left_;
        temp->left_ = current;
        current = temp;
247
        if (current->right_ == nullptr) break;
248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273
      }
      // 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;
}


template <typename Config, class Allocator> template <class Callback>
void SplayTree<Config, Allocator>::ForEach(Callback* callback) {
  NodeToPairAdaptor<Callback> callback_adaptor(callback);
  ForEachNode(&callback_adaptor);
}


template <typename Config, class Allocator> template <class Callback>
274
void SplayTree<Config, Allocator>::ForEachNode(Callback* callback) {
275
  if (root_ == nullptr) return;
276
  // Pre-allocate some space for tiny trees.
277 278 279 280
  std::vector<Node*> nodes_to_visit;
  nodes_to_visit.push_back(root_);
  size_t pos = 0;
  while (pos < nodes_to_visit.size()) {
281
    Node* node = nodes_to_visit[pos++];
282 283
    if (node->left() != nullptr) nodes_to_visit.push_back(node->left());
    if (node->right() != nullptr) nodes_to_visit.push_back(node->right());
284 285 286 287 288
    callback->Call(node);
  }
}


289 290
}  // namespace internal
}  // namespace v8
291 292

#endif  // V8_SPLAY_TREE_INL_H_