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/. */
6
7 #include "mozilla/Assertions.h"
8 #include "mozilla/DoublyLinkedList.h"
9
10 using mozilla::DoublyLinkedList;
11 using mozilla::DoublyLinkedListElement;
12
13 struct SomeClass : public DoublyLinkedListElement<SomeClass> {
14 unsigned int mValue;
SomeClassSomeClass15 explicit SomeClass(int aValue) : mValue(aValue) {}
incrSomeClass16 void incr() { ++mValue; }
operator ==SomeClass17 bool operator==(const SomeClass& other) { return mValue == other.mValue; }
18 };
19
20 template <typename ListType, size_t N>
21 static void
CheckListValues(ListType & list,unsigned int (& values)[N])22 CheckListValues(ListType& list, unsigned int (&values)[N])
23 {
24 size_t count = 0;
25 for (auto& x : list) {
26 MOZ_RELEASE_ASSERT(x.mValue == values[count]);
27 ++count;
28 }
29 MOZ_RELEASE_ASSERT(count == N);
30 }
31
32 static void
TestDoublyLinkedList()33 TestDoublyLinkedList()
34 {
35 DoublyLinkedList<SomeClass> list;
36
37 SomeClass one(1), two(2), three(3);
38
39 MOZ_RELEASE_ASSERT(list.isEmpty());
40 MOZ_RELEASE_ASSERT(!list.begin());
41 MOZ_RELEASE_ASSERT(!list.end());
42
43 for (SomeClass& x : list) {
44 MOZ_RELEASE_ASSERT(x.mValue);
45 MOZ_RELEASE_ASSERT(false);
46 }
47
48 list.pushFront(&one);
49 { unsigned int check[] { 1 }; CheckListValues(list, check); }
50
51 MOZ_RELEASE_ASSERT(list.contains(one));
52 MOZ_RELEASE_ASSERT(!list.contains(two));
53 MOZ_RELEASE_ASSERT(!list.contains(three));
54
55 MOZ_RELEASE_ASSERT(!list.isEmpty());
56 MOZ_RELEASE_ASSERT(list.begin()->mValue == 1);
57 MOZ_RELEASE_ASSERT(!list.end());
58
59 list.pushFront(&two);
60 { unsigned int check[] { 2, 1 }; CheckListValues(list, check); }
61
62 MOZ_RELEASE_ASSERT(list.begin()->mValue == 2);
63 MOZ_RELEASE_ASSERT(!list.end());
64 MOZ_RELEASE_ASSERT(!list.contains(three));
65
66 list.pushBack(&three);
67 { unsigned int check[] { 2, 1, 3 }; CheckListValues(list, check); }
68
69 MOZ_RELEASE_ASSERT(list.begin()->mValue == 2);
70 MOZ_RELEASE_ASSERT(!list.end());
71
72 list.remove(&one);
73 { unsigned int check[] { 2, 3 }; CheckListValues(list, check); }
74
75 list.insertBefore(list.find(three), &one);
76 { unsigned int check[] { 2, 1, 3 }; CheckListValues(list, check); }
77
78 list.remove(&three);
79 { unsigned int check[] { 2, 1 }; CheckListValues(list, check); }
80
81 list.insertBefore(list.find(two), &three);
82 { unsigned int check[] { 3, 2, 1 }; CheckListValues(list, check); }
83
84 list.remove(&three);
85 { unsigned int check[] { 2, 1 }; CheckListValues(list, check); }
86
87 list.insertBefore(++list.find(two), &three);
88 { unsigned int check[] { 2, 3, 1 }; CheckListValues(list, check); }
89
90 list.remove(&one);
91 { unsigned int check[] { 2, 3 }; CheckListValues(list, check); }
92
93 list.remove(&two);
94 { unsigned int check[] { 3 }; CheckListValues(list, check); }
95
96 list.insertBefore(list.find(three), &two);
97 { unsigned int check[] { 2, 3 }; CheckListValues(list, check); }
98
99 list.remove(&three);
100 { unsigned int check[] { 2 }; CheckListValues(list, check); }
101
102 list.remove(&two);
103 MOZ_RELEASE_ASSERT(list.isEmpty());
104
105 list.pushBack(&three);
106 { unsigned int check[] { 3 }; CheckListValues(list, check); }
107
108 list.pushFront(&two);
109 { unsigned int check[] { 2, 3 }; CheckListValues(list, check); }
110
111 // This should modify the values of |two| and |three| as pointers to them are
112 // stored in the list, not copies.
113 for (SomeClass& x : list) {
114 x.incr();
115 }
116
117 MOZ_RELEASE_ASSERT(*list.begin() == two);
118 MOZ_RELEASE_ASSERT(*++list.begin() == three);
119
120 SomeClass four(4);
121 MOZ_RELEASE_ASSERT(++list.begin() == list.find(four));
122 }
123
124 struct InTwoLists {
InTwoListsInTwoLists125 explicit InTwoLists(unsigned int aValue) : mValue(aValue) {}
126 DoublyLinkedListElement<InTwoLists> mListOne;
127 DoublyLinkedListElement<InTwoLists> mListTwo;
128 unsigned int mValue;
129
130 struct GetListOneTrait {
GetInTwoLists::GetListOneTrait131 static DoublyLinkedListElement<InTwoLists>& Get(InTwoLists *aThis) { return aThis->mListOne; }
132 };
133 };
134
135 namespace mozilla {
136
137 template<>
138 struct GetDoublyLinkedListElement<InTwoLists> {
Getmozilla::GetDoublyLinkedListElement139 static DoublyLinkedListElement<InTwoLists>& Get(InTwoLists* aThis) { return aThis->mListTwo; }
140 };
141
142 }
143
144 static void
TestCustomAccessor()145 TestCustomAccessor()
146 {
147 DoublyLinkedList<InTwoLists, InTwoLists::GetListOneTrait> listOne;
148 DoublyLinkedList<InTwoLists> listTwo;
149
150 InTwoLists one(1);
151 InTwoLists two(2);
152
153 listOne.pushBack(&one);
154 listOne.pushBack(&two);
155 { unsigned int check[] { 1, 2 }; CheckListValues(listOne, check); }
156
157 listTwo.pushBack(&one);
158 listTwo.pushBack(&two);
159 { unsigned int check[] { 1, 2 }; CheckListValues(listOne, check); }
160 { unsigned int check[] { 1, 2 }; CheckListValues(listTwo, check); }
161
162 (void)listTwo.popBack();
163 { unsigned int check[] { 1, 2 }; CheckListValues(listOne, check); }
164 { unsigned int check[] { 1 }; CheckListValues(listTwo, check); }
165
166 (void)listOne.popBack();
167 { unsigned int check[] { 1 }; CheckListValues(listOne, check); }
168 { unsigned int check[] { 1 }; CheckListValues(listTwo, check); }
169 }
170
171 int
main()172 main()
173 {
174 TestDoublyLinkedList();
175 TestCustomAccessor();
176 return 0;
177 }
178