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 { ConsCons23 Cons(A top, Cons* rest) 24 : 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: FunctionalList()31 FunctionalList() : elements_(nullptr) {} 32 33 bool operator==(const FunctionalList<A>& other) const { 34 if (Size() != other.Size()) return false; 35 iterator it = begin(); 36 iterator other_it = other.begin(); 37 while (true) { 38 if (it == other_it) return true; 39 if (*it != *other_it) return false; 40 ++it; 41 ++other_it; 42 } 43 } 44 bool operator!=(const FunctionalList<A>& other) const { 45 return !(*this == other); 46 } 47 Front()48 const A& Front() const { 49 DCHECK_GT(Size(), 0); 50 return elements_->top; 51 } 52 Rest()53 FunctionalList Rest() const { 54 FunctionalList result = *this; 55 result.DropFront(); 56 return result; 57 } 58 DropFront()59 void DropFront() { 60 CHECK_GT(Size(), 0); 61 elements_ = elements_->rest; 62 } 63 PushFront(A a,Zone * zone)64 void PushFront(A a, Zone* zone) { 65 elements_ = new (zone) Cons(std::move(a), elements_); 66 } 67 68 // If {hint} happens to be exactly what we want to allocate, avoid allocation 69 // by reusing {hint}. PushFront(A a,Zone * zone,FunctionalList hint)70 void PushFront(A a, Zone* zone, FunctionalList hint) { 71 if (hint.Size() == Size() + 1 && hint.Front() == a && 72 hint.Rest() == *this) { 73 *this = hint; 74 } else { 75 PushFront(a, zone); 76 } 77 } 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. ResetToCommonAncestor(FunctionalList other)82 void ResetToCommonAncestor(FunctionalList other) { 83 while (other.Size() > Size()) other.DropFront(); 84 while (other.Size() < Size()) DropFront(); 85 while (elements_ != other.elements_) { 86 DropFront(); 87 other.DropFront(); 88 } 89 } 90 Size()91 size_t Size() const { return elements_ ? elements_->size : 0; } 92 93 class iterator { 94 public: iterator(Cons * cur)95 explicit iterator(Cons* cur) : current_(cur) {} 96 97 const A& operator*() const { return current_->top; } 98 iterator& operator++() { 99 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 begin()111 iterator begin() const { return iterator(elements_); } end()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_ 123