Skip to content

Commit ac79897

Browse files
dexonsmithdexonsmith
committedAug 30, 2016
ADT: Split out simple_ilist, a simple intrusive list
Split out a new, low-level intrusive list type with clear semantics. Unlike iplist (and ilist), all operations on simple_ilist are intrusive, and simple_ilist never takes ownership of its nodes. This enables an intuitive API that has the right defaults for intrusive lists. - insert() takes references (not pointers!) to nodes (in iplist/ilist, passing a reference will cause the node to be copied). - erase() takes only iterators (like std::list), and does not destroy the nodes. - remove() takes only references and has the same behaviour as erase(). - clear() does not destroy the nodes. - The destructor does not destroy the nodes. - New API {erase,remove,clear}AndDispose() take an extra Disposer functor for callsites that want to call some disposal routine (e.g., std::default_delete). This list is not currently configurable, and has no callbacks. The initial motivation was to fix iplist<>::sort to work correctly (even with callbacks in ilist_traits<>). iplist<> uses simple_ilist<>::sort directly. The new test in unittests/IR/ModuleTest.cpp crashes without this commit. Fixing sort() via a low-level layer provided a good opportunity to: - Unit test the low-level functionality thoroughly. - Modernize the API, largely inspired by other intrusive list implementations. Here's a sketch of a longer-term plan: - Create BumpPtrList<>, a non-intrusive list implemented using simple_ilist<>, and use it for the Token list in lib/Support/YAMLParser.cpp. This will factor out the only real use of createNode(). - Evolve the iplist<> and ilist<> APIs in the direction of simple_ilist<>, making allocation/deallocation explicit at call sites (similar to simple_ilist<>::eraseAndDispose()). - Factor out remaining calls to createNode() and deleteNode() and remove the customization from ilist_traits<>. - Transition uses of iplist<>/ilist<> that don't need callbacks over to simple_ilist<>. llvm-svn: 280107
1 parent c213685 commit ac79897

File tree

9 files changed

+1018
-142
lines changed

9 files changed

+1018
-142
lines changed
 

‎llvm/include/llvm/ADT/ilist.h

Lines changed: 33 additions & 102 deletions
Original file line numberDiff line numberDiff line change
@@ -24,11 +24,8 @@
2424
#ifndef LLVM_ADT_ILIST_H
2525
#define LLVM_ADT_ILIST_H
2626

27-
#include "llvm/ADT/ilist_base.h"
28-
#include "llvm/ADT/ilist_iterator.h"
29-
#include "llvm/ADT/ilist_node.h"
27+
#include "llvm/ADT/simple_ilist.h"
3028
#include "llvm/Support/Compiler.h"
31-
#include <algorithm>
3229
#include <cassert>
3330
#include <cstddef>
3431
#include <iterator>
@@ -119,17 +116,14 @@ struct ilist_traits<const Ty> : public ilist_traits<Ty> {};
119116
/// ilist_sentinel, which holds pointers to the first and last nodes in the
120117
/// list.
121118
template <typename NodeTy, typename Traits = ilist_traits<NodeTy>>
122-
class iplist : public Traits, ilist_base, ilist_node_access {
119+
class iplist : public Traits, simple_ilist<NodeTy> {
123120
// TODO: Drop this assertion and the transitive type traits anytime after
124121
// v4.0 is branched (i.e,. keep them for one release to help out-of-tree code
125122
// update).
126123
static_assert(!ilist_detail::HasObsoleteCustomization<Traits, NodeTy>::value,
127124
"ilist customization points have changed!");
128125

129-
ilist_sentinel<NodeTy> Sentinel;
130-
131-
typedef ilist_node<NodeTy> node_type;
132-
typedef const ilist_node<NodeTy> const_node_type;
126+
typedef simple_ilist<NodeTy> base_list_type;
133127

134128
static bool op_less(NodeTy &L, NodeTy &R) { return L < R; }
135129
static bool op_equal(NodeTy &L, NodeTy &R) { return L == R; }
@@ -139,65 +133,42 @@ class iplist : public Traits, ilist_base, ilist_node_access {
139133
void operator=(const iplist &) = delete;
140134

141135
public:
142-
typedef NodeTy *pointer;
143-
typedef const NodeTy *const_pointer;
144-
typedef NodeTy &reference;
145-
typedef const NodeTy &const_reference;
146-
typedef NodeTy value_type;
147-
typedef ilist_iterator<NodeTy> iterator;
148-
typedef ilist_iterator<const NodeTy> const_iterator;
149-
typedef size_t size_type;
150-
typedef ptrdiff_t difference_type;
151-
typedef ilist_iterator<const NodeTy, true> const_reverse_iterator;
152-
typedef ilist_iterator<NodeTy, true> reverse_iterator;
136+
typedef typename base_list_type::pointer pointer;
137+
typedef typename base_list_type::const_pointer const_pointer;
138+
typedef typename base_list_type::reference reference;
139+
typedef typename base_list_type::const_reference const_reference;
140+
typedef typename base_list_type::value_type value_type;
141+
typedef typename base_list_type::size_type size_type;
142+
typedef typename base_list_type::difference_type difference_type;
143+
typedef typename base_list_type::iterator iterator;
144+
typedef typename base_list_type::const_iterator const_iterator;
145+
typedef typename base_list_type::reverse_iterator reverse_iterator;
146+
typedef
147+
typename base_list_type::const_reverse_iterator const_reverse_iterator;
153148

154149
iplist() = default;
155150
~iplist() { clear(); }
156151

157-
// Iterator creation methods.
158-
iterator begin() { return ++iterator(Sentinel); }
159-
const_iterator begin() const { return ++const_iterator(Sentinel); }
160-
iterator end() { return iterator(Sentinel); }
161-
const_iterator end() const { return const_iterator(Sentinel); }
162-
163-
// reverse iterator creation methods.
164-
reverse_iterator rbegin() { return ++reverse_iterator(Sentinel); }
165-
const_reverse_iterator rbegin() const{ return ++const_reverse_iterator(Sentinel); }
166-
reverse_iterator rend() { return reverse_iterator(Sentinel); }
167-
const_reverse_iterator rend() const { return const_reverse_iterator(Sentinel); }
168-
169152
// Miscellaneous inspection routines.
170153
size_type max_size() const { return size_type(-1); }
171-
bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { return Sentinel.empty(); }
172154

173-
// Front and back accessor functions...
174-
reference front() {
175-
assert(!empty() && "Called front() on empty list!");
176-
return *begin();
177-
}
178-
const_reference front() const {
179-
assert(!empty() && "Called front() on empty list!");
180-
return *begin();
181-
}
182-
reference back() {
183-
assert(!empty() && "Called back() on empty list!");
184-
return *--end();
185-
}
186-
const_reference back() const {
187-
assert(!empty() && "Called back() on empty list!");
188-
return *--end();
189-
}
155+
using base_list_type::begin;
156+
using base_list_type::end;
157+
using base_list_type::rbegin;
158+
using base_list_type::rend;
159+
using base_list_type::empty;
160+
using base_list_type::front;
161+
using base_list_type::back;
190162

191163
void swap(iplist &RHS) {
192164
assert(0 && "Swap does not use list traits callback correctly yet!");
193-
std::swap(Sentinel, RHS.Sentinel);
165+
base_list_type::swap(RHS);
194166
}
195167

196168
iterator insert(iterator where, NodeTy *New) {
197-
ilist_base::insertBefore(*where.getNodePtr(), *this->getNodePtr(New));
198-
169+
auto I = base_list_type::insert(where, *New);
199170
this->addNodeToList(New); // Notify traits that we added a node...
200-
return iterator(New);
171+
return I;
201172
}
202173

203174
iterator insert(iterator where, const NodeTy &New) {
@@ -212,9 +183,8 @@ class iplist : public Traits, ilist_base, ilist_node_access {
212183
}
213184

214185
NodeTy *remove(iterator &IT) {
215-
assert(IT != end() && "Cannot remove end of list!");
216-
NodeTy *Node = &*IT++;
217-
ilist_base::remove(*this->getNodePtr(Node));
186+
NodeTy *Node = &*IT;
187+
base_list_type::erase(IT++);
218188
this->removeNodeFromList(Node); // Notify traits that we removed a node...
219189
return Node;
220190
}
@@ -241,7 +211,7 @@ class iplist : public Traits, ilist_base, ilist_node_access {
241211
///
242212
/// This should only be used immediately before freeing nodes in bulk to
243213
/// avoid traversing the list and bringing all the nodes into cache.
244-
void clearAndLeakNodesUnsafely() { Sentinel.reset(); }
214+
void clearAndLeakNodesUnsafely() { base_list_type::clear(); }
245215

246216
private:
247217
// transfer - The heart of the splice function. Move linked list nodes from
@@ -251,8 +221,7 @@ class iplist : public Traits, ilist_base, ilist_node_access {
251221
if (position == last)
252222
return;
253223

254-
ilist_base::transferBefore(*position.getNodePtr(), *first.getNodePtr(),
255-
*last.getNodePtr());
224+
base_list_type::splice(position, L2, first, last);
256225

257226
// Callback. Note that the nodes have moved from before-last to
258227
// before-position.
@@ -265,9 +234,7 @@ class iplist : public Traits, ilist_base, ilist_node_access {
265234
// Functionality derived from other functions defined above...
266235
//
267236

268-
size_type LLVM_ATTRIBUTE_UNUSED_RESULT size() const {
269-
return std::distance(begin(), end());
270-
}
237+
using base_list_type::size;
271238

272239
iterator erase(iterator first, iterator last) {
273240
while (first != last)
@@ -318,48 +285,12 @@ class iplist : public Traits, ilist_base, ilist_node_access {
318285
void merge(iplist &Right, Compare comp) {
319286
if (this == &Right)
320287
return;
321-
iterator First1 = begin(), Last1 = end();
322-
iterator First2 = Right.begin(), Last2 = Right.end();
323-
while (First1 != Last1 && First2 != Last2) {
324-
if (comp(*First2, *First1)) {
325-
iterator Next = First2;
326-
transfer(First1, Right, First2, ++Next);
327-
First2 = Next;
328-
} else {
329-
++First1;
330-
}
331-
}
332-
if (First2 != Last2)
333-
transfer(Last1, Right, First2, Last2);
288+
this->transferNodesFromList(Right, Right.begin(), Right.end());
289+
base_list_type::merge(Right, comp);
334290
}
335291
void merge(iplist &Right) { return merge(Right, op_less); }
336292

337-
template <class Compare>
338-
void sort(Compare comp) {
339-
// The list is empty, vacuously sorted.
340-
if (empty())
341-
return;
342-
// The list has a single element, vacuously sorted.
343-
if (std::next(begin()) == end())
344-
return;
345-
// Find the split point for the list.
346-
iterator Center = begin(), End = begin();
347-
while (End != end() && std::next(End) != end()) {
348-
Center = std::next(Center);
349-
End = std::next(std::next(End));
350-
}
351-
// Split the list into two.
352-
iplist RightHalf;
353-
RightHalf.splice(RightHalf.begin(), *this, Center, end());
354-
355-
// Sort the two sublists.
356-
sort(comp);
357-
RightHalf.sort(comp);
358-
359-
// Merge the two sublists back together.
360-
merge(RightHalf, comp);
361-
}
362-
void sort() { sort(op_less); }
293+
using base_list_type::sort;
363294

364295
/// \brief Get the previous node, or \c nullptr for the list head.
365296
NodeTy *getPrevNode(NodeTy &N) const {

‎llvm/include/llvm/ADT/ilist_base.h

Lines changed: 17 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -39,10 +39,22 @@ class ilist_base {
3939
N.setNext(nullptr);
4040
}
4141

42+
static void removeRangeImpl(ilist_node_base &First, ilist_node_base &Last) {
43+
ilist_node_base *Prev = First.getPrev();
44+
ilist_node_base *Final = Last.getPrev();
45+
Last.setPrev(Prev);
46+
Prev->setNext(&Last);
47+
48+
// Not strictly necessary, but helps catch a class of bugs.
49+
First.setPrev(nullptr);
50+
Final->setNext(nullptr);
51+
}
52+
4253
static void transferBeforeImpl(ilist_node_base &Next, ilist_node_base &First,
4354
ilist_node_base &Last) {
44-
assert(&Next != &Last && "Should be checked by callers");
45-
assert(&First != &Last && "Should be checked by callers");
55+
if (&Next == &Last || &First == &Last)
56+
return;
57+
4658
// Position cannot be contained in the range to be transferred.
4759
assert(&Next != &First &&
4860
// Check for the most common mistake.
@@ -67,6 +79,9 @@ class ilist_base {
6779
}
6880

6981
template <class T> static void remove(T &N) { removeImpl(N); }
82+
template <class T> static void removeRange(T &First, T &Last) {
83+
removeRangeImpl(First, Last);
84+
}
7085

7186
template <class T> static void transferBefore(T &Next, T &First, T &Last) {
7287
transferBeforeImpl(Next, First, Last);

‎llvm/include/llvm/ADT/simple_ilist.h

Lines changed: 269 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,269 @@
1+
//===- llvm/ADT/simple_ilist.h - Simple Intrusive List ----------*- C++ -*-===//
2+
//
3+
// The LLVM Compiler Infrastructure
4+
//
5+
// This file is distributed under the University of Illinois Open Source
6+
// License. See LICENSE.TXT for details.
7+
//
8+
//===----------------------------------------------------------------------===//
9+
10+
#ifndef LLVM_ADT_SIMPLE_ILIST_H
11+
#define LLVM_ADT_SIMPLE_ILIST_H
12+
13+
#include "llvm/ADT/ilist_base.h"
14+
#include "llvm/ADT/ilist_iterator.h"
15+
#include "llvm/ADT/ilist_node.h"
16+
#include <algorithm>
17+
#include <cassert>
18+
#include <cstddef>
19+
20+
namespace llvm {
21+
22+
/// A simple intrusive list implementation.
23+
///
24+
/// This is a simple intrusive list for a \c T that inherits from \c
25+
/// ilist_node<T>. The list never takes ownership of anything inserted in it.
26+
///
27+
/// Unlike \a iplist<T> and \a ilist<T>, \a simple_ilist<T> never allocates or
28+
/// deletes values, and has no callback traits.
29+
///
30+
/// The API for adding nodes include \a push_front(), \a push_back(), and \a
31+
/// insert(). These all take values by reference (not by pointer), except for
32+
/// the range version of \a insert().
33+
///
34+
/// There are three sets of API for discarding nodes from the list: \a
35+
/// remove(), which takes a reference to the node to remove, \a erase(), which
36+
/// takes an iterator or iterator range and returns the next one, and \a
37+
/// clear(), which empties out the container. All three are constant time
38+
/// operations. None of these deletes any nodes; in particular, if there is a
39+
/// single node in the list, then these have identical semantics:
40+
/// \li \c L.remove(L.front());
41+
/// \li \c L.erase(L.begin());
42+
/// \li \c L.clear();
43+
///
44+
/// As a convenience for callers, there are parallel APIs that take a \c
45+
/// Disposer (such as \c std::default_delete<T>): \a removeAndDispose(), \a
46+
/// eraseAndDispose(), and \a clearAndDispose(). These have different names
47+
/// because the extra semantic is otherwise non-obvious. They are equivalent
48+
/// to calling \a std::for_each() on the range to be discarded.
49+
template <typename T> class simple_ilist : ilist_base, ilist_node_access {
50+
ilist_sentinel<T> Sentinel;
51+
52+
public:
53+
typedef T value_type;
54+
typedef T *pointer;
55+
typedef T &reference;
56+
typedef const T *const_pointer;
57+
typedef const T &const_reference;
58+
typedef ilist_iterator<T> iterator;
59+
typedef ilist_iterator<const T> const_iterator;
60+
typedef size_t size_type;
61+
typedef ptrdiff_t difference_type;
62+
typedef ilist_iterator<const T, true> const_reverse_iterator;
63+
typedef ilist_iterator<T, true> reverse_iterator;
64+
65+
simple_ilist() = default;
66+
~simple_ilist() = default;
67+
68+
// No copy constructors.
69+
simple_ilist(const simple_ilist &) = delete;
70+
simple_ilist &operator=(const simple_ilist &) = delete;
71+
72+
// Move constructors.
73+
simple_ilist(simple_ilist &&X) { splice(end(), X); }
74+
simple_ilist &operator=(simple_ilist &&X) {
75+
clear();
76+
splice(end(), X);
77+
return *this;
78+
}
79+
80+
iterator begin() { return ++iterator(Sentinel); }
81+
const_iterator begin() const { return ++const_iterator(Sentinel); }
82+
iterator end() { return iterator(Sentinel); }
83+
const_iterator end() const { return const_iterator(Sentinel); }
84+
reverse_iterator rbegin() { return ++reverse_iterator(Sentinel); }
85+
const_reverse_iterator rbegin() const {
86+
return ++const_reverse_iterator(Sentinel);
87+
}
88+
reverse_iterator rend() { return reverse_iterator(Sentinel); }
89+
const_reverse_iterator rend() const {
90+
return const_reverse_iterator(Sentinel);
91+
}
92+
93+
/// Check if the list is empty in constant time.
94+
bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { return Sentinel.empty(); }
95+
96+
/// Calculate the size of the list in linear time.
97+
size_type LLVM_ATTRIBUTE_UNUSED_RESULT size() const {
98+
return std::distance(begin(), end());
99+
}
100+
101+
reference front() { return *begin(); }
102+
const_reference front() const { return *begin(); }
103+
reference back() { return *rbegin(); }
104+
const_reference back() const { return *rbegin(); }
105+
106+
/// Insert a node at the front; never copies.
107+
void push_front(reference Node) { insert(begin(), Node); }
108+
109+
/// Insert a node at the back; never copies.
110+
void push_back(reference Node) { insert(end(), Node); }
111+
112+
/// Remove the node at the front; never deletes.
113+
void pop_front() { erase(begin()); }
114+
115+
/// Remove the node at the back; never deletes.
116+
void pop_back() { erase(--end()); }
117+
118+
/// Swap with another list in place using std::swap.
119+
void swap(simple_ilist &X) { std::swap(*this, X); }
120+
121+
/// Insert a node by reference; never copies.
122+
iterator insert(iterator I, reference Node) {
123+
ilist_base::insertBefore(*I.getNodePtr(), *this->getNodePtr(&Node));
124+
return iterator(&Node);
125+
}
126+
127+
/// Insert a range of nodes; never copies.
128+
template <class Iterator>
129+
void insert(iterator I, Iterator First, Iterator Last) {
130+
for (; First != Last; ++First)
131+
insert(I, *First);
132+
}
133+
134+
/// Remove a node by reference; never deletes.
135+
///
136+
/// \see \a erase() for removing by iterator.
137+
/// \see \a removeAndDispose() if the node should be deleted.
138+
void remove(reference N) { ilist_base::remove(*this->getNodePtr(&N)); }
139+
140+
/// Remove a node by reference and dispose of it.
141+
template <class Disposer>
142+
void removeAndDispose(reference N, Disposer dispose) {
143+
remove(N);
144+
dispose(&N);
145+
}
146+
147+
/// Remove a node by iterator; never deletes.
148+
///
149+
/// \see \a remove() for removing by reference.
150+
/// \see \a eraseAndDispose() it the node should be deleted.
151+
iterator erase(iterator I) {
152+
assert(I != end() && "Cannot remove end of list!");
153+
remove(*I++);
154+
return I;
155+
}
156+
157+
/// Remove a range of nodes; never deletes.
158+
///
159+
/// \see \a eraseAndDispose() if the nodes should be deleted.
160+
iterator erase(iterator First, iterator Last) {
161+
ilist_base::removeRange(*First.getNodePtr(), *Last.getNodePtr());
162+
return Last;
163+
}
164+
165+
/// Remove a node by iterator and dispose of it.
166+
template <class Disposer>
167+
iterator eraseAndDispose(iterator I, Disposer dispose) {
168+
auto Next = std::next(I);
169+
erase(I);
170+
dispose(&*I);
171+
return Next;
172+
}
173+
174+
/// Remove a range of nodes and dispose of them.
175+
template <class Disposer>
176+
iterator eraseAndDispose(iterator First, iterator Last, Disposer dispose) {
177+
while (First != Last)
178+
First = eraseAndDispose(First, dispose);
179+
return Last;
180+
}
181+
182+
/// Clear the list; never deletes.
183+
///
184+
/// \see \a clearAndDispose() if the nodes should be deleted.
185+
void clear() { Sentinel.reset(); }
186+
187+
/// Clear the list and dispose of the nodes.
188+
template <class Disposer> void clearAndDispose(Disposer dispose) {
189+
eraseAndDispose(begin(), end(), dispose);
190+
}
191+
192+
/// Splice in another list.
193+
void splice(iterator I, simple_ilist &L2) {
194+
splice(I, L2, L2.begin(), L2.end());
195+
}
196+
197+
/// Splice in a node from another list.
198+
void splice(iterator I, simple_ilist &L2, iterator Node) {
199+
splice(I, L2, Node, std::next(Node));
200+
}
201+
202+
/// Splice in a range of nodes from another list.
203+
void splice(iterator I, simple_ilist &, iterator First, iterator Last) {
204+
ilist_base::transferBefore(*I.getNodePtr(), *First.getNodePtr(),
205+
*Last.getNodePtr());
206+
}
207+
208+
/// Merge in another list.
209+
///
210+
/// \pre \c this and \p RHS are sorted.
211+
///@{
212+
void merge(simple_ilist &RHS) { merge(RHS, std::less<T>()); }
213+
template <class Compare> void merge(simple_ilist &RHS, Compare comp);
214+
///@}
215+
216+
/// Sort the list.
217+
///@{
218+
void sort() { sort(std::less<T>()); }
219+
template <class Compare> void sort(Compare comp);
220+
///@}
221+
};
222+
223+
template <class T>
224+
template <class Compare>
225+
void simple_ilist<T>::merge(simple_ilist<T> &RHS, Compare comp) {
226+
if (this == &RHS || RHS.empty())
227+
return;
228+
iterator LI = begin(), LE = end();
229+
iterator RI = RHS.begin(), RE = RHS.end();
230+
while (LI != LE) {
231+
if (comp(*RI, *LI)) {
232+
// Transfer a run of at least size 1 from RHS to LHS.
233+
iterator RunStart = RI++;
234+
RI = std::find_if(RI, RE, [&](reference RV) { return !comp(RV, *LI); });
235+
splice(LI, RHS, RunStart, RI);
236+
if (RI == RE)
237+
return;
238+
}
239+
++LI;
240+
}
241+
// Transfer the remaining RHS nodes once LHS is finished.
242+
splice(LE, RHS, RI, RE);
243+
}
244+
245+
template <class T>
246+
template <class Compare>
247+
void simple_ilist<T>::sort(Compare comp) {
248+
// Vacuously sorted.
249+
if (empty() || std::next(begin()) == end())
250+
return;
251+
252+
// Split the list in the middle.
253+
iterator Center = begin(), End = begin();
254+
while (End != end() && ++End != end()) {
255+
++Center;
256+
++End;
257+
}
258+
simple_ilist<T> RHS;
259+
RHS.splice(RHS.end(), *this, Center, end());
260+
261+
// Sort the sublists and merge back together.
262+
sort(comp);
263+
RHS.sort(comp);
264+
merge(RHS, comp);
265+
}
266+
267+
} // end namespace llvm
268+
269+
#endif // LLVM_ADT_SIMPLE_ILIST_H

‎llvm/unittests/ADT/CMakeLists.txt

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -44,6 +44,7 @@ set(ADTSources
4444
ScopeExitTest.cpp
4545
SequenceTest.cpp
4646
SetVectorTest.cpp
47+
SimpleIListTest.cpp
4748
SmallPtrSetTest.cpp
4849
SmallStringTest.cpp
4950
SmallVectorTest.cpp

‎llvm/unittests/ADT/IListBaseTest.cpp

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -63,6 +63,46 @@ TEST(IListBaseTest, removeImpl) {
6363
EXPECT_EQ(nullptr, B.getNext());
6464
}
6565

66+
TEST(IListBaseTest, removeRangeImpl) {
67+
ilist_node_base S, A, B, C, D;
68+
69+
// [S] <-> A <-> B <-> C <-> D <-> [S]
70+
S.setPrev(&S);
71+
S.setNext(&S);
72+
ilist_base::insertBeforeImpl(S, A);
73+
ilist_base::insertBeforeImpl(S, B);
74+
ilist_base::insertBeforeImpl(S, C);
75+
ilist_base::insertBeforeImpl(S, D);
76+
77+
// [S] <-> A <-> D <-> [S]
78+
ilist_base::removeRangeImpl(B, D);
79+
EXPECT_EQ(&D, S.getPrev());
80+
EXPECT_EQ(&A, D.getPrev());
81+
EXPECT_EQ(&S, A.getPrev());
82+
EXPECT_EQ(&A, S.getNext());
83+
EXPECT_EQ(&D, A.getNext());
84+
EXPECT_EQ(&S, D.getNext());
85+
EXPECT_EQ(nullptr, B.getPrev());
86+
EXPECT_EQ(nullptr, C.getNext());
87+
}
88+
89+
TEST(IListBaseTest, removeRangeImplAllButSentinel) {
90+
ilist_node_base S, A, B;
91+
92+
// [S] <-> A <-> B <-> [S]
93+
S.setPrev(&S);
94+
S.setNext(&S);
95+
ilist_base::insertBeforeImpl(S, A);
96+
ilist_base::insertBeforeImpl(S, B);
97+
98+
// [S] <-> [S]
99+
ilist_base::removeRangeImpl(A, S);
100+
EXPECT_EQ(&S, S.getPrev());
101+
EXPECT_EQ(&S, S.getNext());
102+
EXPECT_EQ(nullptr, A.getPrev());
103+
EXPECT_EQ(nullptr, B.getNext());
104+
}
105+
66106
TEST(IListBaseTest, transferBeforeImpl) {
67107
ilist_node_base S1, S2, A, B, C, D, E;
68108

‎llvm/unittests/ADT/IListIteratorTest.cpp

Lines changed: 23 additions & 38 deletions
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
//
88
//===----------------------------------------------------------------------===//
99

10-
#include "llvm/ADT/ilist.h"
10+
#include "llvm/ADT/simple_ilist.h"
1111
#include "gtest/gtest.h"
1212

1313
using namespace llvm;
@@ -17,10 +17,10 @@ namespace {
1717
struct Node : ilist_node<Node> {};
1818

1919
TEST(IListIteratorTest, DefaultConstructor) {
20-
iplist<Node>::iterator I;
21-
iplist<Node>::reverse_iterator RI;
22-
iplist<Node>::const_iterator CI;
23-
iplist<Node>::const_reverse_iterator CRI;
20+
simple_ilist<Node>::iterator I;
21+
simple_ilist<Node>::reverse_iterator RI;
22+
simple_ilist<Node>::const_iterator CI;
23+
simple_ilist<Node>::const_reverse_iterator CRI;
2424
EXPECT_EQ(nullptr, I.getNodePtr());
2525
EXPECT_EQ(nullptr, CI.getNodePtr());
2626
EXPECT_EQ(nullptr, RI.getNodePtr());
@@ -38,7 +38,7 @@ TEST(IListIteratorTest, DefaultConstructor) {
3838
}
3939

4040
TEST(IListIteratorTest, Empty) {
41-
iplist<Node> L;
41+
simple_ilist<Node> L;
4242

4343
// Check iterators of L.
4444
EXPECT_EQ(L.begin(), L.end());
@@ -49,21 +49,18 @@ TEST(IListIteratorTest, Empty) {
4949
EXPECT_EQ(L.rend(), L.end().getReverse());
5050

5151
// Iterators shouldn't match default constructors.
52-
iplist<Node>::iterator I;
53-
iplist<Node>::reverse_iterator RI;
52+
simple_ilist<Node>::iterator I;
53+
simple_ilist<Node>::reverse_iterator RI;
5454
EXPECT_NE(I, L.begin());
5555
EXPECT_NE(I, L.end());
5656
EXPECT_NE(RI, L.rbegin());
5757
EXPECT_NE(RI, L.rend());
58-
59-
// Don't delete nodes.
60-
L.clearAndLeakNodesUnsafely();
6158
}
6259

6360
TEST(IListIteratorTest, OneNodeList) {
64-
iplist<Node> L;
61+
simple_ilist<Node> L;
6562
Node A;
66-
L.insert(L.end(), &A);
63+
L.insert(L.end(), A);
6764

6865
// Check address of reference.
6966
EXPECT_EQ(&A, &*L.begin());
@@ -81,16 +78,13 @@ TEST(IListIteratorTest, OneNodeList) {
8178
// Check conversions.
8279
EXPECT_EQ(L.rbegin(), L.begin().getReverse());
8380
EXPECT_EQ(L.begin(), L.rbegin().getReverse());
84-
85-
// Don't delete nodes.
86-
L.clearAndLeakNodesUnsafely();
8781
}
8882

8983
TEST(IListIteratorTest, TwoNodeList) {
90-
iplist<Node> L;
84+
simple_ilist<Node> L;
9185
Node A, B;
92-
L.insert(L.end(), &A);
93-
L.insert(L.end(), &B);
86+
L.insert(L.end(), A);
87+
L.insert(L.end(), B);
9488

9589
// Check order.
9690
EXPECT_EQ(&A, &*L.begin());
@@ -105,45 +99,36 @@ TEST(IListIteratorTest, TwoNodeList) {
10599
EXPECT_EQ(L.rbegin(), (++L.begin()).getReverse());
106100
EXPECT_EQ(++L.begin(), L.rbegin().getReverse());
107101
EXPECT_EQ(L.begin(), (++L.rbegin()).getReverse());
108-
109-
// Don't delete nodes.
110-
L.clearAndLeakNodesUnsafely();
111102
}
112103

113104
TEST(IListIteratorTest, CheckEraseForward) {
114-
iplist<Node> L;
105+
simple_ilist<Node> L;
115106
Node A, B;
116-
L.insert(L.end(), &A);
117-
L.insert(L.end(), &B);
107+
L.insert(L.end(), A);
108+
L.insert(L.end(), B);
118109

119110
// Erase nodes.
120111
auto I = L.begin();
121112
EXPECT_EQ(&A, &*I);
122-
EXPECT_EQ(&A, L.remove(I++));
113+
L.remove(*I++);
123114
EXPECT_EQ(&B, &*I);
124-
EXPECT_EQ(&B, L.remove(I++));
115+
L.remove(*I++);
125116
EXPECT_EQ(L.end(), I);
126-
127-
// Don't delete nodes.
128-
L.clearAndLeakNodesUnsafely();
129117
}
130118

131119
TEST(IListIteratorTest, CheckEraseReverse) {
132-
iplist<Node> L;
120+
simple_ilist<Node> L;
133121
Node A, B;
134-
L.insert(L.end(), &A);
135-
L.insert(L.end(), &B);
122+
L.insert(L.end(), A);
123+
L.insert(L.end(), B);
136124

137125
// Erase nodes.
138126
auto RI = L.rbegin();
139127
EXPECT_EQ(&B, &*RI);
140-
EXPECT_EQ(&B, L.remove(&*RI++));
128+
L.remove(*RI++);
141129
EXPECT_EQ(&A, &*RI);
142-
EXPECT_EQ(&A, L.remove(&*RI++));
130+
L.remove(*RI++);
143131
EXPECT_EQ(L.rend(), RI);
144-
145-
// Don't delete nodes.
146-
L.clearAndLeakNodesUnsafely();
147132
}
148133

149134
} // end namespace

‎llvm/unittests/ADT/SimpleIListTest.cpp

Lines changed: 586 additions & 0 deletions
Large diffs are not rendered by default.

‎llvm/unittests/IR/CMakeLists.txt

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -20,6 +20,7 @@ set(IRSources
2020
LegacyPassManagerTest.cpp
2121
MDBuilderTest.cpp
2222
MetadataTest.cpp
23+
ModuleTest.cpp
2324
PassManagerTest.cpp
2425
PatternMatch.cpp
2526
TypeBuilderTest.cpp

‎llvm/unittests/IR/ModuleTest.cpp

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
//===- unittests/IR/ModuleTest.cpp - Module unit tests --------------------===//
2+
//
3+
// The LLVM Compiler Infrastructure
4+
//
5+
// This file is distributed under the University of Illinois Open Source
6+
// License. See LICENSE.TXT for details.
7+
//
8+
//===----------------------------------------------------------------------===//
9+
10+
#include "llvm/IR/GlobalVariable.h"
11+
#include "llvm/IR/Module.h"
12+
#include "gtest/gtest.h"
13+
14+
using namespace llvm;
15+
16+
namespace {
17+
18+
bool sortByName(const GlobalVariable &L, const GlobalVariable &R) {
19+
return L.getName() < R.getName();
20+
}
21+
22+
bool sortByNameReverse(const GlobalVariable &L, const GlobalVariable &R) {
23+
return sortByName(R, L);
24+
}
25+
26+
TEST(ModuleTest, sortGlobalsByName) {
27+
LLVMContext Context;
28+
for (auto compare : {sortByName, sortByNameReverse}) {
29+
Module M("M", Context);
30+
Type *T = Type::getInt8Ty(Context);
31+
GlobalValue::LinkageTypes L = GlobalValue::ExternalLinkage;
32+
(void)new GlobalVariable(M, T, false, L, nullptr, "A");
33+
(void)new GlobalVariable(M, T, false, L, nullptr, "F");
34+
(void)new GlobalVariable(M, T, false, L, nullptr, "G");
35+
(void)new GlobalVariable(M, T, false, L, nullptr, "E");
36+
(void)new GlobalVariable(M, T, false, L, nullptr, "B");
37+
(void)new GlobalVariable(M, T, false, L, nullptr, "H");
38+
(void)new GlobalVariable(M, T, false, L, nullptr, "C");
39+
(void)new GlobalVariable(M, T, false, L, nullptr, "D");
40+
41+
// Sort the globals by name.
42+
EXPECT_FALSE(std::is_sorted(M.global_begin(), M.global_end(), compare));
43+
M.getGlobalList().sort(compare);
44+
EXPECT_TRUE(std::is_sorted(M.global_begin(), M.global_end(), compare));
45+
}
46+
}
47+
48+
} // end namespace

0 commit comments

Comments
 (0)
Please sign in to comment.