LCOV - code coverage report
Current view: top level - src - splay-tree.h (source / functions) Hit Total Coverage
Test: app.info Lines: 12 12 100.0 %
Date: 2019-04-17 Functions: 1 2 50.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        2652 :       : root_(nullptr), allocator_(allocator) {}
      40             :   ~SplayTree();
      41             : 
      42             :   V8_INLINE void* operator new(
      43             :       size_t size, AllocationPolicy allocator = AllocationPolicy()) {
      44             :     return allocator.New(static_cast<int>(size));
      45             :   }
      46             :   V8_INLINE void operator delete(void* p) { AllocationPolicy::Delete(p); }
      47             :   // Please the MSVC compiler.  We should never have to execute this.
      48             :   V8_INLINE void operator delete(void* p, AllocationPolicy policy) {
      49             :     UNREACHABLE();
      50             :   }
      51             : 
      52             :   AllocationPolicy allocator() { return allocator_; }
      53             : 
      54             :   // Checks if there is a mapping for the key.
      55             :   bool Contains(const Key& key);
      56             : 
      57             :   // Inserts the given key in this tree with the given value.  Returns
      58             :   // true if a node was inserted, otherwise false.  If found the locator
      59             :   // is enabled and provides access to the mapping for the key.
      60             :   bool Insert(const Key& key, Locator* locator);
      61             : 
      62             :   // Looks up the key in this tree and returns true if it was found,
      63             :   // otherwise false.  If the node is found the locator is enabled and
      64             :   // provides access to the mapping for the key.
      65             :   bool Find(const Key& key, Locator* locator);
      66             : 
      67             :   // Finds the mapping with the greatest key less than or equal to the
      68             :   // given key.
      69             :   bool FindGreatestLessThan(const Key& key, Locator* locator);
      70             : 
      71             :   // Find the mapping with the greatest key in this tree.
      72             :   bool FindGreatest(Locator* locator);
      73             : 
      74             :   // Finds the mapping with the least key greater than or equal to the
      75             :   // given key.
      76             :   bool FindLeastGreaterThan(const Key& key, Locator* locator);
      77             : 
      78             :   // Find the mapping with the least key in this tree.
      79             :   bool FindLeast(Locator* locator);
      80             : 
      81             :   // Move the node from one key to another.
      82             :   bool Move(const Key& old_key, const Key& new_key);
      83             : 
      84             :   // Remove the node with the given key from the tree.
      85             :   bool Remove(const Key& key);
      86             : 
      87             :   // Remove all keys from the tree.
      88             :   void Clear() { ResetRoot(); }
      89             : 
      90             :   bool is_empty() { return root_ == nullptr; }
      91             : 
      92             :   // Perform the splay operation for the given key. Moves the node with
      93             :   // the given key to the top of the tree.  If no node has the given
      94             :   // key, the last node on the search path is moved to the top of the
      95             :   // tree.
      96             :   void Splay(const Key& key);
      97             : 
      98             :   class Node {
      99             :    public:
     100             :     Node(const Key& key, const Value& value)
     101     1696090 :         : key_(key), value_(value), left_(nullptr), right_(nullptr) {}
     102             : 
     103             :     V8_INLINE void* operator new(size_t size, AllocationPolicy allocator) {
     104             :       return allocator.New(static_cast<int>(size));
     105             :     }
     106             :     V8_INLINE void operator delete(void* p) {
     107             :       return AllocationPolicy::Delete(p);
     108             :     }
     109             :     // Please the MSVC compiler.  We should never have to execute
     110             :     // this.
     111             :     V8_INLINE void operator delete(void* p, AllocationPolicy allocator) {
     112             :       UNREACHABLE();
     113             :     }
     114             : 
     115             :     Key key() { return key_; }
     116             :     Value value() { return value_; }
     117             :     Node* left() { return left_; }
     118             :     Node* right() { return right_; }
     119             : 
     120             :    private:
     121             :     friend class SplayTree;
     122             :     friend class Locator;
     123             :     Key key_;
     124             :     Value value_;
     125             :     Node* left_;
     126             :     Node* right_;
     127             :   };
     128             : 
     129             :   // A locator provides access to a node in the tree without actually
     130             :   // exposing the node.
     131             :   class Locator {
     132             :    public:
     133             :     explicit Locator(Node* node) : node_(node) { }
     134      305737 :     Locator() : node_(nullptr) {}
     135        1230 :     const Key& key() { return node_->key_; }
     136      307055 :     Value& value() { return node_->value_; }
     137      163721 :     void set_value(const Value& value) { node_->value_ = value; }
     138      479273 :     inline void bind(Node* node) { node_ = node; }
     139             : 
     140             :    private:
     141             :     Node* node_;
     142             :   };
     143             : 
     144             :   template <class Callback>
     145             :   void ForEach(Callback* callback);
     146             : 
     147             :  protected:
     148             :   // Resets tree root. Existing nodes become unreachable.
     149        2652 :   void ResetRoot() { root_ = nullptr; }
     150             : 
     151             :  private:
     152             :   // Search for a node with a given key. If found, root_ points
     153             :   // to the node.
     154             :   bool FindInternal(const Key& key);
     155             : 
     156             :   // Inserts a node assuming that root_ is already set up.
     157             :   void InsertInternal(int cmp, Node* node);
     158             : 
     159             :   // Removes root_ node.
     160             :   void RemoveRootNode(const Key& key);
     161             : 
     162             :   template <class Callback>
     163             :   class NodeToPairAdaptor {
     164             :    public:
     165             :     explicit NodeToPairAdaptor(Callback* callback)
     166        2587 :         : callback_(callback) { }
     167      161041 :     void Call(Node* node) {
     168      161041 :       callback_->Call(node->key(), node->value());
     169      161041 :     }
     170             : 
     171             :    private:
     172             :     Callback* callback_;
     173             : 
     174             :     DISALLOW_COPY_AND_ASSIGN(NodeToPairAdaptor);
     175             :   };
     176             : 
     177             :   class NodeDeleter {
     178             :    public:
     179             :     NodeDeleter() = default;
     180             :     void Call(Node* node) { AllocationPolicy::Delete(node); }
     181             : 
     182             :    private:
     183             :     DISALLOW_COPY_AND_ASSIGN(NodeDeleter);
     184             :   };
     185             : 
     186             :   template <class Callback>
     187             :   void ForEachNode(Callback* callback);
     188             : 
     189             :   Node* root_;
     190             :   AllocationPolicy allocator_;
     191             : 
     192             :   DISALLOW_COPY_AND_ASSIGN(SplayTree);
     193             : };
     194             : 
     195             : 
     196             : }  // namespace internal
     197             : }  // namespace v8
     198             : 
     199             : #endif  // V8_SPLAY_TREE_H_

Generated by: LCOV version 1.10