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 <iterator> 9 #include "src/zone/zone.h" 10 11 namespace v8 { 12 namespace internal { 13 namespace compiler { 14 15 // A generic stack implemented as a purely functional singly-linked list, which 16 // results in an O(1) copy operation. It is the equivalent of functional lists 17 // in ML-like languages, with the only difference that it also caches the length 18 // of the list in each node. 19 // TODO(tebbi): Use this implementation also for RedundancyElimination. 20 template <class A> 21 class FunctionalList { 22 private: 23 struct Cons : ZoneObject { ConsCons24 Cons(A top, Cons* rest) 25 : top(std::move(top)), rest(rest), size(1 + (rest ? rest->size : 0)) {} 26 A const top; 27 Cons* const rest; 28 size_t const size; 29 }; 30 31 public: FunctionalList()32 FunctionalList() : elements_(nullptr) {} 33 34 bool operator==(const FunctionalList<A>& other) const { 35 if (Size() != other.Size()) return false; 36 iterator it = begin(); 37 iterator other_it = other.begin(); 38 while (true) { 39 if (it == other_it) return true; 40 if (*it != *other_it) return false; 41 ++it; 42 ++other_it; 43 } 44 } 45 bool operator!=(const FunctionalList<A>& other) const { 46 return !(*this == other); 47 } 48 TriviallyEquals(const FunctionalList<A> & other)49 bool TriviallyEquals(const FunctionalList<A>& other) const { 50 return elements_ == other.elements_; 51 } 52 Front()53 const A& Front() const { 54 DCHECK_GT(Size(), 0); 55 return elements_->top; 56 } 57 Rest()58 FunctionalList Rest() const { 59 FunctionalList result = *this; 60 result.DropFront(); 61 return result; 62 } 63 DropFront()64 void DropFront() { 65 CHECK_GT(Size(), 0); 66 elements_ = elements_->rest; 67 } 68 PushFront(A a,Zone * zone)69 void PushFront(A a, Zone* zone) { 70 elements_ = zone->New<Cons>(std::move(a), elements_); 71 } 72 73 // If {hint} happens to be exactly what we want to allocate, avoid allocation 74 // by reusing {hint}. PushFront(A a,Zone * zone,FunctionalList hint)75 void PushFront(A a, Zone* zone, FunctionalList hint) { 76 if (hint.Size() == Size() + 1 && hint.Front() == a && 77 hint.Rest() == *this) { 78 *this = hint; 79 } else { 80 PushFront(a, zone); 81 } 82 } 83 84 // Drop elements until the current stack is equal to the tail shared with 85 // {other}. The shared tail must not only be equal, but also refer to the 86 // same memory. ResetToCommonAncestor(FunctionalList other)87 void ResetToCommonAncestor(FunctionalList other) { 88 while (other.Size() > Size()) other.DropFront(); 89 while (other.Size() < Size()) DropFront(); 90 while (elements_ != other.elements_) { 91 DropFront(); 92 other.DropFront(); 93 } 94 } 95 Size()96 size_t Size() const { return elements_ ? elements_->size : 0; } 97 Clear()98 void Clear() { elements_ = nullptr; } 99 100 class iterator : public std::iterator<std::forward_iterator_tag, A> { 101 public: iterator(Cons * cur)102 explicit iterator(Cons* cur) : current_(cur) {} 103 104 const A& operator*() const { return current_->top; } 105 iterator& operator++() { 106 current_ = current_->rest; 107 return *this; 108 } 109 bool operator==(const iterator& other) const { 110 return this->current_ == other.current_; 111 } 112 bool operator!=(const iterator& other) const { return !(*this == other); } 113 114 // Implemented so that std::find and friends can use std::iterator_traits 115 // for this iterator type. 116 typedef std::forward_iterator_tag iterator_category; 117 typedef ptrdiff_t difference_type; 118 typedef A value_type; 119 typedef A* pointer; 120 typedef A& reference; 121 122 private: 123 Cons* current_; 124 }; 125 begin()126 iterator begin() const { return iterator(elements_); } end()127 iterator end() const { return iterator(nullptr); } 128 129 private: 130 Cons* elements_; 131 }; 132 133 } // namespace compiler 134 } // namespace internal 135 } // namespace v8 136 137 #endif // V8_COMPILER_FUNCTIONAL_LIST_H_ 138