LCOV - code coverage report
Current view: top level - src - splay-tree.h (source / functions) Hit Total Coverage
Test: app.info Lines: 18 19 94.7 %
Date: 2017-04-26 Functions: 4 5 80.0 %

          Line data    Source code
       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     1638880 :       : 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     2018781 :   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      176139 :   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      185523 :   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     3982628 :   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     5217759 :           right_(NULL) { }
     107             : 
     108             :     INLINE(void* operator new(size_t size, AllocationPolicy allocator)) {
     109     1235131 :       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      795922 :     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     5361854 :     Locator() : node_(NULL) { }
     140           0 :     const Key& key() { return node_->key_; }
     141     2120790 :     Value& value() { return node_->value_; }
     142     2107444 :     void set_value(const Value& value) { node_->value_ = value; }
     143     3303710 :     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        3156 :   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     4512254 :   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     2041144 :         : callback_(callback) { }
     172     2288366 :     void Call(Node* node) {
     173     1492444 :       callback_->Call(node->key(), node->value());
     174      978299 :     }
     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_

Generated by: LCOV version 1.10