1311116Sdim//===- llvm/ADT/AllocatorList.h - Custom allocator list ---------*- C++ -*-===// 2311116Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6311116Sdim// 7311116Sdim//===----------------------------------------------------------------------===// 8311116Sdim 9311116Sdim#ifndef LLVM_ADT_ALLOCATORLIST_H 10311116Sdim#define LLVM_ADT_ALLOCATORLIST_H 11311116Sdim 12321369Sdim#include "llvm/ADT/ilist_node.h" 13311116Sdim#include "llvm/ADT/iterator.h" 14311116Sdim#include "llvm/ADT/simple_ilist.h" 15311116Sdim#include "llvm/Support/Allocator.h" 16321369Sdim#include <algorithm> 17321369Sdim#include <cassert> 18321369Sdim#include <cstddef> 19321369Sdim#include <iterator> 20311116Sdim#include <type_traits> 21321369Sdim#include <utility> 22311116Sdim 23311116Sdimnamespace llvm { 24311116Sdim 25311116Sdim/// A linked-list with a custom, local allocator. 26311116Sdim/// 27311116Sdim/// Expose a std::list-like interface that owns and uses a custom LLVM-style 28311116Sdim/// allocator (e.g., BumpPtrAllocator), leveraging \a simple_ilist for the 29311116Sdim/// implementation details. 30311116Sdim/// 31311116Sdim/// Because this list owns the allocator, calling \a splice() with a different 32311116Sdim/// list isn't generally safe. As such, \a splice has been left out of the 33311116Sdim/// interface entirely. 34311116Sdimtemplate <class T, class AllocatorT> class AllocatorList : AllocatorT { 35311116Sdim struct Node : ilist_node<Node> { 36311116Sdim Node(Node &&) = delete; 37311116Sdim Node(const Node &) = delete; 38311116Sdim Node &operator=(Node &&) = delete; 39311116Sdim Node &operator=(const Node &) = delete; 40311116Sdim 41311116Sdim Node(T &&V) : V(std::move(V)) {} 42311116Sdim Node(const T &V) : V(V) {} 43311116Sdim template <class... Ts> Node(Ts &&... Vs) : V(std::forward<Ts>(Vs)...) {} 44311116Sdim T V; 45311116Sdim }; 46311116Sdim 47321369Sdim using list_type = simple_ilist<Node>; 48321369Sdim 49311116Sdim list_type List; 50311116Sdim 51311116Sdim AllocatorT &getAlloc() { return *this; } 52311116Sdim const AllocatorT &getAlloc() const { return *this; } 53311116Sdim 54311116Sdim template <class... ArgTs> Node *create(ArgTs &&... Args) { 55311116Sdim return new (getAlloc()) Node(std::forward<ArgTs>(Args)...); 56311116Sdim } 57311116Sdim 58311116Sdim struct Cloner { 59311116Sdim AllocatorList &AL; 60321369Sdim 61311116Sdim Cloner(AllocatorList &AL) : AL(AL) {} 62321369Sdim 63311116Sdim Node *operator()(const Node &N) const { return AL.create(N.V); } 64311116Sdim }; 65311116Sdim 66311116Sdim struct Disposer { 67311116Sdim AllocatorList &AL; 68321369Sdim 69311116Sdim Disposer(AllocatorList &AL) : AL(AL) {} 70321369Sdim 71311116Sdim void operator()(Node *N) const { 72311116Sdim N->~Node(); 73311116Sdim AL.getAlloc().Deallocate(N); 74311116Sdim } 75311116Sdim }; 76311116Sdim 77311116Sdimpublic: 78321369Sdim using value_type = T; 79321369Sdim using pointer = T *; 80321369Sdim using reference = T &; 81321369Sdim using const_pointer = const T *; 82321369Sdim using const_reference = const T &; 83321369Sdim using size_type = typename list_type::size_type; 84321369Sdim using difference_type = typename list_type::difference_type; 85311116Sdim 86311116Sdimprivate: 87311116Sdim template <class ValueT, class IteratorBase> 88311116Sdim class IteratorImpl 89311116Sdim : public iterator_adaptor_base<IteratorImpl<ValueT, IteratorBase>, 90311116Sdim IteratorBase, 91311116Sdim std::bidirectional_iterator_tag, ValueT> { 92311116Sdim template <class OtherValueT, class OtherIteratorBase> 93311116Sdim friend class IteratorImpl; 94311116Sdim friend AllocatorList; 95311116Sdim 96321369Sdim using base_type = 97321369Sdim iterator_adaptor_base<IteratorImpl<ValueT, IteratorBase>, IteratorBase, 98321369Sdim std::bidirectional_iterator_tag, ValueT>; 99311116Sdim 100311116Sdim public: 101321369Sdim using value_type = ValueT; 102321369Sdim using pointer = ValueT *; 103321369Sdim using reference = ValueT &; 104311116Sdim 105311116Sdim IteratorImpl() = default; 106311116Sdim IteratorImpl(const IteratorImpl &) = default; 107311116Sdim IteratorImpl &operator=(const IteratorImpl &) = default; 108311116Sdim 109311116Sdim explicit IteratorImpl(const IteratorBase &I) : base_type(I) {} 110311116Sdim 111311116Sdim template <class OtherValueT, class OtherIteratorBase> 112311116Sdim IteratorImpl(const IteratorImpl<OtherValueT, OtherIteratorBase> &X, 113311116Sdim typename std::enable_if<std::is_convertible< 114311116Sdim OtherIteratorBase, IteratorBase>::value>::type * = nullptr) 115311116Sdim : base_type(X.wrapped()) {} 116311116Sdim 117321369Sdim ~IteratorImpl() = default; 118321369Sdim 119311116Sdim reference operator*() const { return base_type::wrapped()->V; } 120311116Sdim pointer operator->() const { return &operator*(); } 121311116Sdim 122311116Sdim friend bool operator==(const IteratorImpl &L, const IteratorImpl &R) { 123311116Sdim return L.wrapped() == R.wrapped(); 124311116Sdim } 125311116Sdim friend bool operator!=(const IteratorImpl &L, const IteratorImpl &R) { 126311116Sdim return !(L == R); 127311116Sdim } 128311116Sdim }; 129311116Sdim 130311116Sdimpublic: 131321369Sdim using iterator = IteratorImpl<T, typename list_type::iterator>; 132321369Sdim using reverse_iterator = 133321369Sdim IteratorImpl<T, typename list_type::reverse_iterator>; 134321369Sdim using const_iterator = 135321369Sdim IteratorImpl<const T, typename list_type::const_iterator>; 136321369Sdim using const_reverse_iterator = 137321369Sdim IteratorImpl<const T, typename list_type::const_reverse_iterator>; 138311116Sdim 139311116Sdim AllocatorList() = default; 140311116Sdim AllocatorList(AllocatorList &&X) 141311116Sdim : AllocatorT(std::move(X.getAlloc())), List(std::move(X.List)) {} 142321369Sdim 143311116Sdim AllocatorList(const AllocatorList &X) { 144311116Sdim List.cloneFrom(X.List, Cloner(*this), Disposer(*this)); 145311116Sdim } 146321369Sdim 147311116Sdim AllocatorList &operator=(AllocatorList &&X) { 148311116Sdim clear(); // Dispose of current nodes explicitly. 149311116Sdim List = std::move(X.List); 150311116Sdim getAlloc() = std::move(X.getAlloc()); 151311116Sdim return *this; 152311116Sdim } 153321369Sdim 154311116Sdim AllocatorList &operator=(const AllocatorList &X) { 155311116Sdim List.cloneFrom(X.List, Cloner(*this), Disposer(*this)); 156311116Sdim return *this; 157311116Sdim } 158321369Sdim 159311116Sdim ~AllocatorList() { clear(); } 160311116Sdim 161311116Sdim void swap(AllocatorList &RHS) { 162311116Sdim List.swap(RHS.List); 163311116Sdim std::swap(getAlloc(), RHS.getAlloc()); 164311116Sdim } 165311116Sdim 166311116Sdim bool empty() { return List.empty(); } 167311116Sdim size_t size() { return List.size(); } 168311116Sdim 169311116Sdim iterator begin() { return iterator(List.begin()); } 170311116Sdim iterator end() { return iterator(List.end()); } 171311116Sdim const_iterator begin() const { return const_iterator(List.begin()); } 172311116Sdim const_iterator end() const { return const_iterator(List.end()); } 173311116Sdim reverse_iterator rbegin() { return reverse_iterator(List.rbegin()); } 174311116Sdim reverse_iterator rend() { return reverse_iterator(List.rend()); } 175311116Sdim const_reverse_iterator rbegin() const { 176311116Sdim return const_reverse_iterator(List.rbegin()); 177311116Sdim } 178311116Sdim const_reverse_iterator rend() const { 179311116Sdim return const_reverse_iterator(List.rend()); 180311116Sdim } 181311116Sdim 182311116Sdim T &back() { return List.back().V; } 183311116Sdim T &front() { return List.front().V; } 184311116Sdim const T &back() const { return List.back().V; } 185311116Sdim const T &front() const { return List.front().V; } 186311116Sdim 187311116Sdim template <class... Ts> iterator emplace(iterator I, Ts &&... Vs) { 188311116Sdim return iterator(List.insert(I.wrapped(), *create(std::forward<Ts>(Vs)...))); 189311116Sdim } 190311116Sdim 191311116Sdim iterator insert(iterator I, T &&V) { 192311116Sdim return iterator(List.insert(I.wrapped(), *create(std::move(V)))); 193311116Sdim } 194311116Sdim iterator insert(iterator I, const T &V) { 195311116Sdim return iterator(List.insert(I.wrapped(), *create(V))); 196311116Sdim } 197311116Sdim 198311116Sdim template <class Iterator> 199311116Sdim void insert(iterator I, Iterator First, Iterator Last) { 200311116Sdim for (; First != Last; ++First) 201311116Sdim List.insert(I.wrapped(), *create(*First)); 202311116Sdim } 203311116Sdim 204311116Sdim iterator erase(iterator I) { 205311116Sdim return iterator(List.eraseAndDispose(I.wrapped(), Disposer(*this))); 206311116Sdim } 207311116Sdim 208311116Sdim iterator erase(iterator First, iterator Last) { 209311116Sdim return iterator( 210311116Sdim List.eraseAndDispose(First.wrapped(), Last.wrapped(), Disposer(*this))); 211311116Sdim } 212311116Sdim 213311116Sdim void clear() { List.clearAndDispose(Disposer(*this)); } 214311116Sdim void pop_back() { List.eraseAndDispose(--List.end(), Disposer(*this)); } 215311116Sdim void pop_front() { List.eraseAndDispose(List.begin(), Disposer(*this)); } 216311116Sdim void push_back(T &&V) { insert(end(), std::move(V)); } 217311116Sdim void push_front(T &&V) { insert(begin(), std::move(V)); } 218311116Sdim void push_back(const T &V) { insert(end(), V); } 219311116Sdim void push_front(const T &V) { insert(begin(), V); } 220311116Sdim template <class... Ts> void emplace_back(Ts &&... Vs) { 221311116Sdim emplace(end(), std::forward<Ts>(Vs)...); 222311116Sdim } 223311116Sdim template <class... Ts> void emplace_front(Ts &&... Vs) { 224311116Sdim emplace(begin(), std::forward<Ts>(Vs)...); 225311116Sdim } 226311116Sdim 227311116Sdim /// Reset the underlying allocator. 228311116Sdim /// 229311116Sdim /// \pre \c empty() 230311116Sdim void resetAlloc() { 231311116Sdim assert(empty() && "Cannot reset allocator if not empty"); 232311116Sdim getAlloc().Reset(); 233311116Sdim } 234311116Sdim}; 235311116Sdim 236311116Sdimtemplate <class T> using BumpPtrList = AllocatorList<T, BumpPtrAllocator>; 237311116Sdim 238311116Sdim} // end namespace llvm 239311116Sdim 240311116Sdim#endif // LLVM_ADT_ALLOCATORLIST_H 241