summaryrefslogtreecommitdiffstats
path: root/llvm
diff options
context:
space:
mode:
Diffstat (limited to 'llvm')
-rw-r--r--llvm/include/llvm/ADT/AllocatorList.h226
-rw-r--r--llvm/include/llvm/ADT/ilist.h3
-rw-r--r--llvm/include/llvm/ADT/simple_ilist.h8
-rw-r--r--llvm/lib/Support/YAMLParser.cpp23
-rw-r--r--llvm/unittests/ADT/BumpPtrListTest.cpp243
-rw-r--r--llvm/unittests/ADT/CMakeLists.txt1
6 files changed, 486 insertions, 18 deletions
diff --git a/llvm/include/llvm/ADT/AllocatorList.h b/llvm/include/llvm/ADT/AllocatorList.h
new file mode 100644
index 00000000000..604de2b7ad8
--- /dev/null
+++ b/llvm/include/llvm/ADT/AllocatorList.h
@@ -0,0 +1,226 @@
+//===- llvm/ADT/AllocatorList.h - Custom allocator list ---------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_ALLOCATORLIST_H
+#define LLVM_ADT_ALLOCATORLIST_H
+
+#include "llvm/ADT/iterator.h"
+#include "llvm/ADT/simple_ilist.h"
+#include "llvm/Support/Allocator.h"
+#include <type_traits>
+
+namespace llvm {
+
+/// A linked-list with a custom, local allocator.
+///
+/// Expose a std::list-like interface that owns and uses a custom LLVM-style
+/// allocator (e.g., BumpPtrAllocator), leveraging \a simple_ilist for the
+/// implementation details.
+///
+/// Because this list owns the allocator, calling \a splice() with a different
+/// list isn't generally safe. As such, \a splice has been left out of the
+/// interface entirely.
+template <class T, class AllocatorT> class AllocatorList : AllocatorT {
+ struct Node : ilist_node<Node> {
+ Node(Node &&) = delete;
+ Node(const Node &) = delete;
+ Node &operator=(Node &&) = delete;
+ Node &operator=(const Node &) = delete;
+
+ Node(T &&V) : V(std::move(V)) {}
+ Node(const T &V) : V(V) {}
+ template <class... Ts> Node(Ts &&... Vs) : V(std::forward<Ts>(Vs)...) {}
+ T V;
+ };
+
+ typedef simple_ilist<Node> list_type;
+ list_type List;
+
+ AllocatorT &getAlloc() { return *this; }
+ const AllocatorT &getAlloc() const { return *this; }
+
+ template <class... ArgTs> Node *create(ArgTs &&... Args) {
+ return new (getAlloc()) Node(std::forward<ArgTs>(Args)...);
+ }
+
+ struct Cloner {
+ AllocatorList &AL;
+ Cloner(AllocatorList &AL) : AL(AL) {}
+ Node *operator()(const Node &N) const { return AL.create(N.V); }
+ };
+
+ struct Disposer {
+ AllocatorList &AL;
+ Disposer(AllocatorList &AL) : AL(AL) {}
+ void operator()(Node *N) const {
+ N->~Node();
+ AL.getAlloc().Deallocate(N);
+ }
+ };
+
+public:
+ typedef T value_type;
+ typedef T *pointer;
+ typedef T &reference;
+ typedef const T *const_pointer;
+ typedef const T &const_reference;
+ typedef typename list_type::size_type size_type;
+ typedef typename list_type::difference_type difference_type;
+
+private:
+ template <class ValueT, class IteratorBase>
+ class IteratorImpl
+ : public iterator_adaptor_base<IteratorImpl<ValueT, IteratorBase>,
+ IteratorBase,
+ std::bidirectional_iterator_tag, ValueT> {
+ template <class OtherValueT, class OtherIteratorBase>
+ friend class IteratorImpl;
+ friend AllocatorList;
+
+ typedef iterator_adaptor_base<IteratorImpl<ValueT, IteratorBase>,
+ IteratorBase, std::bidirectional_iterator_tag,
+ ValueT>
+ iterator_adaptor_base;
+
+ public:
+ typedef ValueT value_type;
+ typedef ValueT *pointer;
+ typedef ValueT &reference;
+
+ IteratorImpl() = default;
+ IteratorImpl(const IteratorImpl &) = default;
+ IteratorImpl &operator=(const IteratorImpl &) = default;
+ ~IteratorImpl() = default;
+
+ explicit IteratorImpl(const IteratorBase &I) : iterator_adaptor_base(I) {}
+
+ template <class OtherValueT, class OtherIteratorBase>
+ IteratorImpl(const IteratorImpl<OtherValueT, OtherIteratorBase> &X,
+ typename std::enable_if<std::is_convertible<
+ OtherIteratorBase, IteratorBase>::value>::type * = nullptr)
+ : iterator_adaptor_base(X.wrapped()) {}
+
+ reference operator*() const { return iterator_adaptor_base::wrapped()->V; }
+ pointer operator->() const { return &operator*(); }
+
+ friend bool operator==(const IteratorImpl &L, const IteratorImpl &R) {
+ return L.wrapped() == R.wrapped();
+ }
+ friend bool operator!=(const IteratorImpl &L, const IteratorImpl &R) {
+ return !(L == R);
+ }
+ };
+
+public:
+ typedef IteratorImpl<T, typename list_type::iterator> iterator;
+ typedef IteratorImpl<T, typename list_type::reverse_iterator>
+ reverse_iterator;
+ typedef IteratorImpl<const T, typename list_type::const_iterator>
+ const_iterator;
+ typedef IteratorImpl<const T, typename list_type::const_reverse_iterator>
+ const_reverse_iterator;
+
+ AllocatorList() = default;
+ AllocatorList(AllocatorList &&X)
+ : AllocatorT(std::move(X.getAlloc())), List(std::move(X.List)) {}
+ AllocatorList(const AllocatorList &X) {
+ List.cloneFrom(X.List, Cloner(*this), Disposer(*this));
+ }
+ AllocatorList &operator=(AllocatorList &&X) {
+ clear(); // Dispose of current nodes explicitly.
+ List = std::move(X.List);
+ getAlloc() = std::move(X.getAlloc());
+ return *this;
+ }
+ AllocatorList &operator=(const AllocatorList &X) {
+ List.cloneFrom(X.List, Cloner(*this), Disposer(*this));
+ return *this;
+ }
+ ~AllocatorList() { clear(); }
+
+ void swap(AllocatorList &RHS) {
+ List.swap(RHS.List);
+ std::swap(getAlloc(), RHS.getAlloc());
+ }
+
+ bool empty() { return List.empty(); }
+ size_t size() { return List.size(); }
+
+ iterator begin() { return iterator(List.begin()); }
+ iterator end() { return iterator(List.end()); }
+ const_iterator begin() const { return const_iterator(List.begin()); }
+ const_iterator end() const { return const_iterator(List.end()); }
+ reverse_iterator rbegin() { return reverse_iterator(List.rbegin()); }
+ reverse_iterator rend() { return reverse_iterator(List.rend()); }
+ const_reverse_iterator rbegin() const {
+ return const_reverse_iterator(List.rbegin());
+ }
+ const_reverse_iterator rend() const {
+ return const_reverse_iterator(List.rend());
+ }
+
+ T &back() { return List.back().V; }
+ T &front() { return List.front().V; }
+ const T &back() const { return List.back().V; }
+ const T &front() const { return List.front().V; }
+
+ template <class... Ts> iterator emplace(iterator I, Ts &&... Vs) {
+ return iterator(List.insert(I.wrapped(), *create(std::forward<Ts>(Vs)...)));
+ }
+
+ iterator insert(iterator I, T &&V) {
+ return iterator(List.insert(I.wrapped(), *create(std::move(V))));
+ }
+ iterator insert(iterator I, const T &V) {
+ return iterator(List.insert(I.wrapped(), *create(V)));
+ }
+
+ template <class Iterator>
+ void insert(iterator I, Iterator First, Iterator Last) {
+ for (; First != Last; ++First)
+ List.insert(I.wrapped(), *create(*First));
+ }
+
+ iterator erase(iterator I) {
+ return iterator(List.eraseAndDispose(I.wrapped(), Disposer(*this)));
+ }
+
+ iterator erase(iterator First, iterator Last) {
+ return iterator(
+ List.eraseAndDispose(First.wrapped(), Last.wrapped(), Disposer(*this)));
+ }
+
+ void clear() { List.clearAndDispose(Disposer(*this)); }
+ void pop_back() { List.eraseAndDispose(--List.end(), Disposer(*this)); }
+ void pop_front() { List.eraseAndDispose(List.begin(), Disposer(*this)); }
+ void push_back(T &&V) { insert(end(), std::move(V)); }
+ void push_front(T &&V) { insert(begin(), std::move(V)); }
+ void push_back(const T &V) { insert(end(), V); }
+ void push_front(const T &V) { insert(begin(), V); }
+ template <class... Ts> void emplace_back(Ts &&... Vs) {
+ emplace(end(), std::forward<Ts>(Vs)...);
+ }
+ template <class... Ts> void emplace_front(Ts &&... Vs) {
+ emplace(begin(), std::forward<Ts>(Vs)...);
+ }
+
+ /// Reset the underlying allocator.
+ ///
+ /// \pre \c empty()
+ void resetAlloc() {
+ assert(empty() && "Cannot reset allocator if not empty");
+ getAlloc().Reset();
+ }
+};
+
+template <class T> using BumpPtrList = AllocatorList<T, BumpPtrAllocator>;
+
+} // end namespace llvm
+
+#endif // LLVM_ADT_ALLOCATORLIST_H
diff --git a/llvm/include/llvm/ADT/ilist.h b/llvm/include/llvm/ADT/ilist.h
index 0f7b37b3765..d0569c9eae2 100644
--- a/llvm/include/llvm/ADT/ilist.h
+++ b/llvm/include/llvm/ADT/ilist.h
@@ -40,6 +40,9 @@ namespace llvm {
///
/// \see ilist_noalloc_traits
template <typename NodeTy> struct ilist_alloc_traits {
+ /// Clone a node.
+ ///
+ /// TODO: Remove this and API that relies on it (it's dead code).
static NodeTy *createNode(const NodeTy &V) { return new NodeTy(V); }
static void deleteNode(NodeTy *V) { delete V; }
};
diff --git a/llvm/include/llvm/ADT/simple_ilist.h b/llvm/include/llvm/ADT/simple_ilist.h
index 0ac5cefc1f9..9235bad6ab3 100644
--- a/llvm/include/llvm/ADT/simple_ilist.h
+++ b/llvm/include/llvm/ADT/simple_ilist.h
@@ -164,6 +164,14 @@ public:
insert(I, *First);
}
+ /// Clone another list.
+ template <class Cloner, class Disposer>
+ void cloneFrom(const simple_ilist &L2, Cloner clone, Disposer dispose) {
+ clearAndDispose(dispose);
+ for (const_reference V : L2)
+ push_back(*clone(V));
+ }
+
/// Remove a node by reference; never deletes.
///
/// \see \a erase() for removing by iterator.
diff --git a/llvm/lib/Support/YAMLParser.cpp b/llvm/lib/Support/YAMLParser.cpp
index c083e1f1ebd..0d169af26be 100644
--- a/llvm/lib/Support/YAMLParser.cpp
+++ b/llvm/lib/Support/YAMLParser.cpp
@@ -17,8 +17,7 @@
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/ADT/Twine.h"
-#include "llvm/ADT/ilist.h"
-#include "llvm/ADT/ilist_node.h"
+#include "llvm/ADT/AllocatorList.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MemoryBuffer.h"
#include "llvm/Support/SourceMgr.h"
@@ -109,7 +108,7 @@ void SequenceNode::anchor() {}
void AliasNode::anchor() {}
/// Token - A single YAML token.
-struct Token : ilist_node<Token> {
+struct Token {
enum TokenKind {
TK_Error, // Uninitialized token.
TK_StreamStart,
@@ -148,18 +147,7 @@ struct Token : ilist_node<Token> {
}
}
-namespace llvm {
-template <> struct ilist_alloc_traits<Token> {
- Token *createNode(const Token &V) {
- return new (Alloc.Allocate<Token>()) Token(V);
- }
- static void deleteNode(Token *V) { V->~Token(); }
-
- BumpPtrAllocator Alloc;
-};
-} // end namespace llvm
-
-typedef ilist<Token> TokenQueueT;
+typedef llvm::BumpPtrList<Token> TokenQueueT;
namespace {
/// @brief This struct is used to track simple keys.
@@ -797,9 +785,8 @@ Token Scanner::getNext() {
// There cannot be any referenced Token's if the TokenQueue is empty. So do a
// quick deallocation of them all.
- if (TokenQueue.empty()) {
- TokenQueue.Alloc.Reset();
- }
+ if (TokenQueue.empty())
+ TokenQueue.resetAlloc();
return Ret;
}
diff --git a/llvm/unittests/ADT/BumpPtrListTest.cpp b/llvm/unittests/ADT/BumpPtrListTest.cpp
new file mode 100644
index 00000000000..be34a71373c
--- /dev/null
+++ b/llvm/unittests/ADT/BumpPtrListTest.cpp
@@ -0,0 +1,243 @@
+//===- unittests/ADT/BumpPtrListTest.cpp - BumpPtrList unit tests ---------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/AllocatorList.h"
+#include "llvm/ADT/STLExtras.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+namespace {
+
+struct CountsDestructors {
+ static unsigned NumCalls;
+ ~CountsDestructors() { ++NumCalls; }
+};
+unsigned CountsDestructors::NumCalls = 0;
+
+struct MoveOnly {
+ int V;
+ explicit MoveOnly(int V) : V(V) {}
+ MoveOnly() = delete;
+ MoveOnly(MoveOnly &&X) { V = X.V; }
+ MoveOnly(const MoveOnly &X) = delete;
+ MoveOnly &operator=(MoveOnly &&X) = delete;
+ MoveOnly &operator=(const MoveOnly &X) = delete;
+};
+
+struct EmplaceOnly {
+ int V1, V2;
+ explicit EmplaceOnly(int V1, int V2) : V1(V1), V2(V2) {}
+ EmplaceOnly() = delete;
+ EmplaceOnly(EmplaceOnly &&X) = delete;
+ EmplaceOnly(const EmplaceOnly &X) = delete;
+ EmplaceOnly &operator=(EmplaceOnly &&X) = delete;
+ EmplaceOnly &operator=(const EmplaceOnly &X) = delete;
+};
+
+TEST(BumpPtrListTest, DefaultConstructor) {
+ BumpPtrList<int> L;
+ EXPECT_TRUE(L.empty());
+}
+
+TEST(BumpPtrListTest, pushPopBack) {
+ // Build a list with push_back.
+ BumpPtrList<int> L;
+ int Ns[] = {1, 3, 9, 5, 7};
+ for (const int N : Ns)
+ L.push_back(N);
+
+ // Use iterators to check contents.
+ auto I = L.begin();
+ for (int N : Ns)
+ EXPECT_EQ(N, *I++);
+ EXPECT_EQ(I, L.end());
+
+ // Unbuild the list with pop_back.
+ for (int N : llvm::reverse(Ns)) {
+ EXPECT_EQ(N, L.back());
+ L.pop_back();
+ }
+ EXPECT_TRUE(L.empty());
+}
+
+TEST(BumpPtrListTest, pushPopFront) {
+ // Build a list with push_front.
+ BumpPtrList<int> L;
+ int Ns[] = {1, 3, 9, 5, 7};
+ for (const int N : Ns)
+ L.push_front(N);
+
+ // Use reverse iterators to check contents.
+ auto I = L.rbegin();
+ for (int N : Ns)
+ EXPECT_EQ(N, *I++);
+ EXPECT_EQ(I, L.rend());
+
+ // Unbuild the list with pop_front.
+ for (int N : llvm::reverse(Ns)) {
+ EXPECT_EQ(N, L.front());
+ L.pop_front();
+ }
+ EXPECT_TRUE(L.empty());
+}
+
+TEST(BumpPtrListTest, pushBackMoveOnly) {
+ BumpPtrList<MoveOnly> L;
+ int Ns[] = {1, 3, 9, 5, 7};
+ for (const int N : Ns) {
+ L.push_back(MoveOnly(N));
+ EXPECT_EQ(N, L.back().V);
+ }
+ // Instantiate with MoveOnly.
+ while (!L.empty())
+ L.pop_back();
+}
+
+TEST(BumpPtrListTest, pushFrontMoveOnly) {
+ BumpPtrList<MoveOnly> L;
+ int Ns[] = {1, 3, 9, 5, 7};
+ for (const int N : Ns) {
+ L.push_front(MoveOnly(N));
+ EXPECT_EQ(N, L.front().V);
+ }
+ // Instantiate with MoveOnly.
+ while (!L.empty())
+ L.pop_front();
+}
+
+TEST(BumpPtrListTest, emplaceBack) {
+ BumpPtrList<EmplaceOnly> L;
+ int N1s[] = {1, 3, 9, 5, 7};
+ int N2s[] = {7, 3, 1, 8, 2};
+ for (int I = 0; I != 5; ++I) {
+ L.emplace_back(N1s[I], N2s[I]);
+ EXPECT_EQ(N1s[I], L.back().V1);
+ EXPECT_EQ(N2s[I], L.back().V2);
+ }
+ // Instantiate with EmplaceOnly.
+ while (!L.empty())
+ L.pop_back();
+}
+
+TEST(BumpPtrListTest, emplaceFront) {
+ BumpPtrList<EmplaceOnly> L;
+ int N1s[] = {1, 3, 9, 5, 7};
+ int N2s[] = {7, 3, 1, 8, 2};
+ for (int I = 0; I != 5; ++I) {
+ L.emplace_front(N1s[I], N2s[I]);
+ EXPECT_EQ(N1s[I], L.front().V1);
+ EXPECT_EQ(N2s[I], L.front().V2);
+ }
+ // Instantiate with EmplaceOnly.
+ while (!L.empty())
+ L.pop_front();
+}
+
+TEST(BumpPtrListTest, swap) {
+ // Build two lists with different lifetimes and swap them.
+ int N1s[] = {1, 3, 5, 7, 9};
+ int N2s[] = {2, 4, 6, 8, 10};
+
+ BumpPtrList<int> L1;
+ L1.insert(L1.end(), std::begin(N1s), std::end(N1s));
+ {
+ BumpPtrList<int> L2;
+ L2.insert(L2.end(), std::begin(N2s), std::end(N2s));
+
+ // Swap the lists.
+ L1.swap(L2);
+
+ // Check L2's contents before it goes out of scope.
+ auto I = L2.begin();
+ for (int N : N1s)
+ EXPECT_EQ(N, *I++);
+ EXPECT_EQ(I, L2.end());
+ }
+
+ // Check L1's contents now that L2 is out of scope (with its allocation
+ // blocks).
+ auto I = L1.begin();
+ for (int N : N2s)
+ EXPECT_EQ(N, *I++);
+ EXPECT_EQ(I, L1.end());
+}
+
+TEST(BumpPtrListTest, clear) {
+ CountsDestructors::NumCalls = 0;
+ CountsDestructors N;
+ BumpPtrList<CountsDestructors> L;
+ L.push_back(N);
+ L.push_back(N);
+ L.push_back(N);
+ EXPECT_EQ(3u, L.size());
+ EXPECT_EQ(0u, CountsDestructors::NumCalls);
+ L.pop_back();
+ EXPECT_EQ(1u, CountsDestructors::NumCalls);
+ L.clear();
+ EXPECT_EQ(3u, CountsDestructors::NumCalls);
+}
+
+TEST(BumpPtrListTest, move) {
+ BumpPtrList<int> L1, L2;
+ L1.push_back(1);
+ L2.push_back(2);
+ L1 = std::move(L2);
+ EXPECT_EQ(1u, L1.size());
+ EXPECT_EQ(2, L1.front());
+ EXPECT_EQ(0u, L2.size());
+}
+
+TEST(BumpPtrListTest, moveCallsDestructors) {
+ CountsDestructors::NumCalls = 0;
+ BumpPtrList<CountsDestructors> L1, L2;
+ L1.emplace_back();
+ EXPECT_EQ(0u, CountsDestructors::NumCalls);
+ L1 = std::move(L2);
+ EXPECT_EQ(1u, CountsDestructors::NumCalls);
+}
+
+TEST(BumpPtrListTest, copy) {
+ BumpPtrList<int> L1, L2;
+ L1.push_back(1);
+ L2.push_back(2);
+ L1 = L2;
+ EXPECT_EQ(1u, L1.size());
+ EXPECT_EQ(2, L1.front());
+ EXPECT_EQ(1u, L2.size());
+ EXPECT_EQ(2, L2.front());
+}
+
+TEST(BumpPtrListTest, copyCallsDestructors) {
+ CountsDestructors::NumCalls = 0;
+ BumpPtrList<CountsDestructors> L1, L2;
+ L1.emplace_back();
+ EXPECT_EQ(0u, CountsDestructors::NumCalls);
+ L1 = L2;
+ EXPECT_EQ(1u, CountsDestructors::NumCalls);
+}
+
+TEST(BumpPtrListTest, resetAlloc) {
+ // Resetting an empty list should work.
+ BumpPtrList<int> L;
+
+ // Resetting an empty list that has allocated should also work.
+ L.resetAlloc();
+ L.push_back(5);
+ L.erase(L.begin());
+ L.resetAlloc();
+
+ // Resetting a non-empty list should crash.
+ L.push_back(5);
+#if defined(GTEST_HAS_DEATH_TEST) && !defined(NDEBUG)
+ EXPECT_DEATH(L.resetAlloc(), "Cannot reset allocator if not empty");
+#endif
+}
+
+} // end namespace
diff --git a/llvm/unittests/ADT/CMakeLists.txt b/llvm/unittests/ADT/CMakeLists.txt
index c8cadc560a6..686e6562af6 100644
--- a/llvm/unittests/ADT/CMakeLists.txt
+++ b/llvm/unittests/ADT/CMakeLists.txt
@@ -9,6 +9,7 @@ set(ADTSources
ArrayRefTest.cpp
BitmaskEnumTest.cpp
BitVectorTest.cpp
+ BumpPtrListTest.cpp
DAGDeltaAlgorithmTest.cpp
DeltaAlgorithmTest.cpp
DenseMapTest.cpp
OpenPOWER on IntegriCloud