src/splay-tree.h

   1 // Copyright 2010 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #ifndef V8_SPLAY_TREE_H_
   6 #define V8_SPLAY_TREE_H_
   7
   8 #include "src/allocation.h"
   9
  10 namespace v8 {
  11 namespace internal {
  12
  13
  14 // A splay tree.  The config type parameter encapsulates the different
  15 // configurations of a concrete splay tree:
  16 //
  17 //   typedef Key: the key type
  18 //   typedef Value: the value type
  19 //   static const Key kNoKey: the dummy key used when no key is set
  20 //   static Value kNoValue(): the dummy value used to initialize nodes
  21 //   static int (Compare)(Key& a, Key& b) -> {-1, 0, 1}: comparison function
  22 //
  23 // The tree is also parameterized by an allocation policy
  24 // (Allocator). The policy is used for allocating lists in the C free
  25 // store or the zone; see zone.h.
  26
  27 // Forward defined as
  28 // template <typename Config, class Allocator = FreeStoreAllocationPolicy>
  29 //     class SplayTree;
  30 template <typename Config, class AllocationPolicy>
  31 class SplayTree {
  32  public:
  33   typedef typename Config::Key Key;
  34   typedef typename Config::Value Value;
  35
  36   class Locator;
  37
  38   explicit SplayTree(AllocationPolicy allocator = AllocationPolicy())
  39       : root_(NULL), allocator_(allocator) {}
  40   ~SplayTree();
  41
  42   INLINE(void* operator new(size_t size,
  43                             AllocationPolicy allocator = AllocationPolicy())) {
  44     return allocator.New(static_cast<int>(size));
  45   }
  46   INLINE(void operator delete(void* p)) {
  47     AllocationPolicy::Delete(p);
  48   }
  49   // Please the MSVC compiler.  We should never have to execute this.
  50   INLINE(void operator delete(void* p, AllocationPolicy policy)) {
  51     UNREACHABLE();
  52   }
  53
  54   AllocationPolicy allocator() { return allocator_; }
  55
  56   // Checks if there is a mapping for the key.
  57   bool Contains(const Key& key);
  58
  59   // Inserts the given key in this tree with the given value.  Returns
  60   // true if a node was inserted, otherwise false.  If found the locator
  61   // is enabled and provides access to the mapping for the key.
  62   bool Insert(const Key& key, Locator* locator);
  63
  64   // Looks up the key in this tree and returns true if it was found,
  65   // otherwise false.  If the node is found the locator is enabled and
  66   // provides access to the mapping for the key.
  67   bool Find(const Key& key, Locator* locator);
  68
  69   // Finds the mapping with the greatest key less than or equal to the
  70   // given key.
  71   bool FindGreatestLessThan(const Key& key, Locator* locator);
  72
  73   // Find the mapping with the greatest key in this tree.
  74   bool FindGreatest(Locator* locator);
  75
  76   // Finds the mapping with the least key greater than or equal to the
  77   // given key.
  78   bool FindLeastGreaterThan(const Key& key, Locator* locator);
  79
  80   // Find the mapping with the least key in this tree.
  81   bool FindLeast(Locator* locator);
  82
  83   // Move the node from one key to another.
  84   bool Move(const Key& old_key, const Key& new_key);
  85
  86   // Remove the node with the given key from the tree.
  87   bool Remove(const Key& key);
  88
  89   // Remove all keys from the tree.
  90   void Clear() { ResetRoot(); }
  91
  92   bool is_empty() { return root_ == NULL; }
  93
  94   // Perform the splay operation for the given key. Moves the node with
  95   // the given key to the top of the tree.  If no node has the given
  96   // key, the last node on the search path is moved to the top of the
  97   // tree.
  98   void Splay(const Key& key);
  99
 100   class Node {
 101    public:
 102     Node(const Key& key, const Value& value)
 103         : key_(key),
 104           value_(value),
 105           left_(NULL),
 106           right_(NULL) { }
 107
 108     INLINE(void* operator new(size_t size, AllocationPolicy allocator)) {
 109       return allocator.New(static_cast<int>(size));
 110     }
 111     INLINE(void operator delete(void* p)) {
 112       return AllocationPolicy::Delete(p);
 113     }
 114     // Please the MSVC compiler.  We should never have to execute
 115     // this.
 116     INLINE(void operator delete(void* p, AllocationPolicy allocator)) {
 117       UNREACHABLE();
 118     }
 119
 120     Key key() { return key_; }
 121     Value value() { return value_; }
 122     Node* left() { return left_; }
 123     Node* right() { return right_; }
 124
 125    private:
 126     friend class SplayTree;
 127     friend class Locator;
 128     Key key_;
 129     Value value_;
 130     Node* left_;
 131     Node* right_;
 132   };
 133
 134   // A locator provides access to a node in the tree without actually
 135   // exposing the node.
 136   class Locator BASE_EMBEDDED {
 137    public:
 138     explicit Locator(Node* node) : node_(node) { }
 139     Locator() : node_(NULL) { }
 140     const Key& key() { return node_->key_; }
 141     Value& value() { return node_->value_; }
 142     void set_value(const Value& value) { node_->value_ = value; }
 143     inline void bind(Node* node) { node_ = node; }
 144
 145    private:
 146     Node* node_;
 147   };
 148
 149   template <class Callback>
 150   void ForEach(Callback* callback);
 151
 152  protected:
 153   // Resets tree root. Existing nodes become unreachable.
 154   void ResetRoot() { root_ = NULL; }
 155
 156  private:
 157   // Search for a node with a given key. If found, root_ points
 158   // to the node.
 159   bool FindInternal(const Key& key);
 160
 161   // Inserts a node assuming that root_ is already set up.
 162   void InsertInternal(int cmp, Node* node);
 163
 164   // Removes root_ node.
 165   void RemoveRootNode(const Key& key);
 166
 167   template<class Callback>
 168   class NodeToPairAdaptor BASE_EMBEDDED {
 169    public:
 170     explicit NodeToPairAdaptor(Callback* callback)
 171         : callback_(callback) { }
 172     void Call(Node* node) {
 173       callback_->Call(node->key(), node->value());
 174     }
 175
 176    private:
 177     Callback* callback_;
 178
 179     DISALLOW_COPY_AND_ASSIGN(NodeToPairAdaptor);
 180   };
 181
 182   class NodeDeleter BASE_EMBEDDED {
 183    public:
 184     NodeDeleter() { }
 185     void Call(Node* node) { AllocationPolicy::Delete(node); }
 186
 187    private:
 188     DISALLOW_COPY_AND_ASSIGN(NodeDeleter);
 189   };
 190
 191   template <class Callback>
 192   void ForEachNode(Callback* callback);
 193
 194   Node* root_;
 195   AllocationPolicy allocator_;
 196
 197   DISALLOW_COPY_AND_ASSIGN(SplayTree);
 198 };
 199
 200
 201 }  // namespace internal
 202 }  // namespace v8
 203
 204 #endif  // V8_SPLAY_TREE_H_