1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 /* This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this file,
5 * You can obtain one at http://mozilla.org/MPL/2.0/. */
7 #include "mozilla/Assertions.h"
8 #include "mozilla/DoublyLinkedList.h"
10 using mozilla::DoublyLinkedList
;
11 using mozilla::DoublyLinkedListElement
;
13 struct SomeClass
: public DoublyLinkedListElement
<SomeClass
> {
15 explicit SomeClass(int aValue
) : mValue(aValue
) {}
16 void incr() { ++mValue
; }
17 bool operator==(const SomeClass
& other
) const {
18 return mValue
== other
.mValue
;
22 template <typename ListType
, size_t N
>
23 static void CheckListValues(ListType
& list
, unsigned int (&values
)[N
]) {
25 for (auto& x
: list
) {
26 MOZ_RELEASE_ASSERT(x
.mValue
== values
[count
]);
29 MOZ_RELEASE_ASSERT(count
== N
);
32 static void TestDoublyLinkedList() {
33 DoublyLinkedList
<SomeClass
> list
;
35 SomeClass
one(1), two(2), three(3);
37 MOZ_RELEASE_ASSERT(list
.isEmpty());
38 MOZ_RELEASE_ASSERT(!list
.begin());
39 MOZ_RELEASE_ASSERT(!list
.end());
41 for (SomeClass
& x
: list
) {
42 MOZ_RELEASE_ASSERT(x
.mValue
);
43 MOZ_RELEASE_ASSERT(false);
48 unsigned int check
[]{1};
49 CheckListValues(list
, check
);
52 MOZ_RELEASE_ASSERT(list
.contains(one
));
53 MOZ_RELEASE_ASSERT(!list
.contains(two
));
54 MOZ_RELEASE_ASSERT(!list
.contains(three
));
56 MOZ_RELEASE_ASSERT(!list
.isEmpty());
57 MOZ_RELEASE_ASSERT(list
.begin()->mValue
== 1);
58 MOZ_RELEASE_ASSERT(!list
.end());
62 unsigned int check
[]{2, 1};
63 CheckListValues(list
, check
);
66 MOZ_RELEASE_ASSERT(list
.begin()->mValue
== 2);
67 MOZ_RELEASE_ASSERT(!list
.end());
68 MOZ_RELEASE_ASSERT(!list
.contains(three
));
70 list
.pushBack(&three
);
72 unsigned int check
[]{2, 1, 3};
73 CheckListValues(list
, check
);
76 MOZ_RELEASE_ASSERT(list
.begin()->mValue
== 2);
77 MOZ_RELEASE_ASSERT(!list
.end());
81 unsigned int check
[]{2, 3};
82 CheckListValues(list
, check
);
85 list
.insertBefore(list
.find(three
), &one
);
87 unsigned int check
[]{2, 1, 3};
88 CheckListValues(list
, check
);
93 unsigned int check
[]{2, 1};
94 CheckListValues(list
, check
);
97 list
.insertBefore(list
.find(two
), &three
);
99 unsigned int check
[]{3, 2, 1};
100 CheckListValues(list
, check
);
105 unsigned int check
[]{2, 1};
106 CheckListValues(list
, check
);
109 list
.insertBefore(++list
.find(two
), &three
);
111 unsigned int check
[]{2, 3, 1};
112 CheckListValues(list
, check
);
117 unsigned int check
[]{2, 3};
118 CheckListValues(list
, check
);
123 unsigned int check
[]{3};
124 CheckListValues(list
, check
);
127 list
.insertBefore(list
.find(three
), &two
);
129 unsigned int check
[]{2, 3};
130 CheckListValues(list
, check
);
135 unsigned int check
[]{2};
136 CheckListValues(list
, check
);
140 MOZ_RELEASE_ASSERT(list
.isEmpty());
142 list
.pushBack(&three
);
144 unsigned int check
[]{3};
145 CheckListValues(list
, check
);
148 list
.pushFront(&two
);
150 unsigned int check
[]{2, 3};
151 CheckListValues(list
, check
);
154 // This should modify the values of |two| and |three| as pointers to them are
155 // stored in the list, not copies.
156 for (SomeClass
& x
: list
) {
160 MOZ_RELEASE_ASSERT(*list
.begin() == two
);
161 MOZ_RELEASE_ASSERT(*++list
.begin() == three
);
164 MOZ_RELEASE_ASSERT(++list
.begin() == list
.find(four
));
168 explicit InTwoLists(unsigned int aValue
) : mValue(aValue
) {}
169 DoublyLinkedListElement
<InTwoLists
> mListOne
;
170 DoublyLinkedListElement
<InTwoLists
> mListTwo
;
173 struct GetListOneTrait
{
174 static DoublyLinkedListElement
<InTwoLists
>& Get(InTwoLists
* aThis
) {
175 return aThis
->mListOne
;
183 struct GetDoublyLinkedListElement
<InTwoLists
> {
184 static DoublyLinkedListElement
<InTwoLists
>& Get(InTwoLists
* aThis
) {
185 return aThis
->mListTwo
;
189 } // namespace mozilla
191 static void TestCustomAccessor() {
192 DoublyLinkedList
<InTwoLists
, InTwoLists::GetListOneTrait
> listOne
;
193 DoublyLinkedList
<InTwoLists
> listTwo
;
198 listOne
.pushBack(&one
);
199 listOne
.pushBack(&two
);
201 unsigned int check
[]{1, 2};
202 CheckListValues(listOne
, check
);
205 listTwo
.pushBack(&one
);
206 listTwo
.pushBack(&two
);
208 unsigned int check
[]{1, 2};
209 CheckListValues(listOne
, check
);
212 unsigned int check
[]{1, 2};
213 CheckListValues(listTwo
, check
);
216 (void)listTwo
.popBack();
218 unsigned int check
[]{1, 2};
219 CheckListValues(listOne
, check
);
222 unsigned int check
[]{1};
223 CheckListValues(listTwo
, check
);
226 (void)listOne
.popBack();
228 unsigned int check
[]{1};
229 CheckListValues(listOne
, check
);
232 unsigned int check
[]{1};
233 CheckListValues(listTwo
, check
);
237 static void TestSafeDoubleLinkedList() {
238 mozilla::SafeDoublyLinkedList
<SomeClass
> list
;
239 auto* elt1
= new SomeClass(0);
240 auto* elt2
= new SomeClass(0);
241 auto* elt3
= new SomeClass(0);
242 auto* elt4
= new SomeClass(0);
246 auto iter
= list
.begin();
248 // basic tests for iterator validity
251 "iterator returned by begin() must point to the first element!");
253 &*(iter
.next()) == elt2
,
254 "iterator returned by begin() must have the second element as 'next'!");
257 &*(iter
.next()) == elt3
,
258 "After removal of the 2nd element 'next' must point to the 3rd element!");
262 "After advancing one step the current element must be the 3rd one!");
263 MOZ_RELEASE_ASSERT(!iter
.next(), "This is the last element of the list!");
265 MOZ_RELEASE_ASSERT(&*(iter
.next()) == elt4
,
266 "After adding an element at the end of the list the "
267 "iterator must be updated!");
269 // advance to last element, then remove last element
272 MOZ_RELEASE_ASSERT(bool(iter
) == false,
273 "After removing the last element, the iterator pointing "
274 "to the last element must be empty!");
276 // iterate the whole remaining list, increment values
277 for (auto& el
: list
) {
280 MOZ_RELEASE_ASSERT(elt1
->mValue
== 1);
281 MOZ_RELEASE_ASSERT(elt2
->mValue
== 0);
282 MOZ_RELEASE_ASSERT(elt3
->mValue
== 1);
283 MOZ_RELEASE_ASSERT(elt4
->mValue
== 0);
285 // Removing the first element of the list while iterating must empty the
287 for (auto it
= list
.begin(); it
!= list
.end(); ++it
) {
288 MOZ_RELEASE_ASSERT(bool(it
) == true, "The iterator must contain a value!");
292 "After removing the first element, the iterator must be empty!");
302 TestDoublyLinkedList();
303 TestCustomAccessor();
304 TestSafeDoubleLinkedList();