Line data    Source code

       1             : // Copyright 2018 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_COMPILER_FUNCTIONAL_LIST_H_
       6             : #define V8_COMPILER_FUNCTIONAL_LIST_H_
       7             : 
       8             : #include "src/zone/zone.h"
       9             : 
      10             : namespace v8 {
      11             : namespace internal {
      12             : namespace compiler {
      13             : 
      14             : // A generic stack implemented as a purely functional singly-linked list, which
      15             : // results in an O(1) copy operation. It is the equivalent of functional lists
      16             : // in ML-like languages, with the only difference that it also caches the length
      17             : // of the list in each node.
      18             : // TODO(tebbi): Use this implementation also for RedundancyElimination.
      19             : template <class A>
      20             : class FunctionalList {
      21             :  private:
      22             :   struct Cons : ZoneObject {
      23             :     Cons(A top, Cons* rest)
      24     8023932 :         : top(std::move(top)), rest(rest), size(1 + (rest ? rest->size : 0)) {}
      25             :     A const top;
      26             :     Cons* const rest;
      27             :     size_t const size;
      28             :   };
      29             : 
      30             :  public:
      31      928163 :   FunctionalList() : elements_(nullptr) {}
      32             : 
      33    39755110 :   bool operator==(const FunctionalList<A>& other) const {
      34    39755110 :     if (Size() != other.Size()) return false;
      35             :     iterator it = begin();
      36             :     iterator other_it = other.begin();
      37             :     while (true) {
      38    22931848 :       if (it == other_it) return true;
      39         245 :       if (*it != *other_it) return false;
      40             :       ++it;
      41             :       ++other_it;
      42             :     }
      43             :   }
      44             :   bool operator!=(const FunctionalList<A>& other) const {
      45    39755089 :     return !(*this == other);
      46             :   }
      47             : 
      48             :   const A& Front() const {
      49             :     DCHECK_GT(Size(), 0);
      50             :     return elements_->top;
      51             :   }
      52             : 
      53             :   FunctionalList Rest() const {
      54          30 :     FunctionalList result = *this;
      55          30 :     result.DropFront();
      56          30 :     return result;
      57             :   }
      58             : 
      59    13878440 :   void DropFront() {
      60    13878440 :     CHECK_GT(Size(), 0);
      61    13878440 :     elements_ = elements_->rest;
      62    13878440 :   }
      63             : 
      64     8023949 :   void PushFront(A a, Zone* zone) {
      65    24071813 :     elements_ = new (zone) Cons(std::move(a), elements_);
      66     8023932 :   }
      67             : 
      68             :   // If {hint} happens to be exactly what we want to allocate, avoid allocation
      69             :   // by reusing {hint}.
      70     7942277 :   void PushFront(A a, Zone* zone, FunctionalList hint) {
      71    23826863 :     if (hint.Size() == Size() + 1 && hint.Front() == a &&
      72     7942337 :         hint.Rest() == *this) {
      73           0 :       *this = hint;
      74             :     } else {
      75     7942277 :       PushFront(a, zone);
      76             :     }
      77     7942241 :   }
      78             : 
      79             :   // Drop elements until the current stack is equal to the tail shared with
      80             :   // {other}. The shared tail must not only be equal, but also refer to the
      81             :   // same memory.
      82     4638118 :   void ResetToCommonAncestor(FunctionalList other) {
      83    13031106 :     while (other.Size() > Size()) other.DropFront();
      84     5141251 :     while (other.Size() < Size()) DropFront();
      85     2491161 :     while (elements_ != other.elements_) {
      86     2491167 :       DropFront();
      87     2491157 :       other.DropFront();
      88             :     }
      89     4638086 :   }
      90             : 
      91    79748184 :   size_t Size() const { return elements_ ? elements_->size : 0; }
      92             : 
      93             :   class iterator {
      94             :    public:
      95             :     explicit iterator(Cons* cur) : current_(cur) {}
      96             : 
      97             :     const A& operator*() const { return current_->top; }
      98             :     iterator& operator++() {
      99    24440464 :       current_ = current_->rest;
     100             :       return *this;
     101             :     }
     102             :     bool operator==(const iterator& other) const {
     103             :       return this->current_ == other.current_;
     104             :     }
     105             :     bool operator!=(const iterator& other) const { return !(*this == other); }
     106             : 
     107             :    private:
     108             :     Cons* current_;
     109             :   };
     110             : 
     111           0 :   iterator begin() const { return iterator(elements_); }
     112             :   iterator end() const { return iterator(nullptr); }
     113             : 
     114             :  private:
     115             :   Cons* elements_;
     116             : };
     117             : 
     118             : }  // namespace compiler
     119             : }  // namespace internal
     120             : }  // namespace v8
     121             : 
     122             : #endif  // V8_COMPILER_FUNCTIONAL_LIST_H_