1// Copyright (c) 2019, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#include "vm/intrusive_dlist.h"
6#include "vm/unit_test.h"
7
8namespace dart {
9
10class Base {
11 public:
12 explicit Base(int arg) : base(arg) {}
13
14 int base;
15};
16
17class Item : public Base,
18 public IntrusiveDListEntry<Item>,
19 public IntrusiveDListEntry<Item, 2> {
20 public:
21 explicit Item(int arg0, int arg1) : Base(arg0), item(arg1) {}
22
23 int item;
24};
25
26UNIT_TEST_CASE(IntrusiveDListMultiEntryTest) {
27 Item a1(1, 11), a2(2, 12), a3(3, 13);
28
29 IntrusiveDList<Item> all;
30 IntrusiveDList<Item, 2> ready;
31
32 EXPECT(all.IsEmpty());
33 EXPECT(ready.IsEmpty());
34
35 all.Append(&a2);
36 all.Append(&a3);
37 all.Prepend(&a1);
38 EXPECT_EQ(all.First()->item, 11);
39 EXPECT_EQ(all.Last()->item, 13);
40
41 ready.Append(&a1);
42 ready.Append(&a2);
43 EXPECT_EQ(ready.First()->item, 11);
44 EXPECT_EQ(ready.Last()->item, 12);
45
46 int i = 0;
47 for (auto it = all.Begin(); it != all.End(); ++it) {
48 i++;
49 EXPECT_EQ(it->base, i);
50 EXPECT_EQ((*it)->base, i);
51 EXPECT_EQ(it->item, 10 + i);
52 EXPECT_EQ((*it)->item, 10 + i);
53 }
54 EXPECT_EQ(i, 3);
55
56 i = 0;
57 for (auto it = ready.Begin(); it != ready.End(); ++it) {
58 i++;
59 EXPECT_EQ(it->base, i);
60 EXPECT_EQ((*it)->base, i);
61 EXPECT_EQ(it->item, 10 + i);
62 EXPECT_EQ((*it)->item, 10 + i);
63 }
64 EXPECT_EQ(i, 2);
65
66 ready.Remove(&a1);
67 ready.Remove(&a2);
68
69 all.Remove(&a1);
70 all.Remove(&a2);
71 all.Remove(&a3);
72
73 EXPECT(all.IsEmpty());
74 EXPECT(ready.IsEmpty());
75}
76
77UNIT_TEST_CASE(IntrusiveDListRemoveFirstTest) {
78 Item a1(1, 11), a2(2, 12), a3(3, 13);
79
80 IntrusiveDList<Item> all;
81
82 all.Append(&a2);
83 all.Append(&a3);
84 all.Prepend(&a1);
85
86 EXPECT_EQ(&a1, all.RemoveFirst());
87 EXPECT_EQ(&a2, all.RemoveFirst());
88 EXPECT_EQ(&a3, all.RemoveFirst());
89
90 EXPECT(all.IsEmpty());
91}
92
93UNIT_TEST_CASE(IntrusiveDListRemoveLastTest) {
94 Item a1(1, 11), a2(2, 12), a3(3, 13);
95
96 IntrusiveDList<Item> all;
97
98 all.Append(&a2);
99 all.Append(&a3);
100 all.Prepend(&a1);
101
102 EXPECT_EQ(&a3, all.RemoveLast());
103 EXPECT_EQ(&a2, all.RemoveLast());
104 EXPECT_EQ(&a1, all.RemoveLast());
105 EXPECT(all.IsEmpty());
106}
107
108UNIT_TEST_CASE(IntrusiveDListIsInList) {
109 Item a1(1, 11), a2(2, 12), a3(3, 13);
110
111 IntrusiveDList<Item> all;
112
113 all.Append(&a2);
114 all.Append(&a3);
115 all.Prepend(&a1);
116
117 ASSERT(all.IsInList(&a1));
118 ASSERT(all.IsInList(&a2));
119 ASSERT(all.IsInList(&a3));
120
121 EXPECT_EQ(&a1, all.RemoveFirst());
122 EXPECT(!all.IsInList(&a1));
123 EXPECT_EQ(&a3, all.RemoveLast());
124 EXPECT(!all.IsInList(&a3));
125 EXPECT_EQ(&a2, all.RemoveFirst());
126 EXPECT(!all.IsInList(&a2));
127
128 EXPECT(all.IsEmpty());
129}
130
131UNIT_TEST_CASE(IntrusiveDListEraseIterator) {
132 Item a1(1, 11), a2(2, 12), a3(3, 13);
133
134 IntrusiveDList<Item> all;
135
136 all.Append(&a2);
137 all.Append(&a3);
138 all.Prepend(&a1);
139
140 auto it = all.Begin();
141 it = all.Erase(++it);
142 EXPECT_EQ(*it, &a3);
143 EXPECT_EQ(*it, all.Last());
144
145 it = all.Erase(all.Begin());
146 EXPECT_EQ(*it, &a3);
147 EXPECT_EQ(*it, all.First());
148 EXPECT_EQ(*it, all.Last());
149
150 it = all.Erase(all.Begin());
151 EXPECT(it == all.End());
152 EXPECT(all.IsEmpty());
153}
154
155UNIT_TEST_CASE(IntrusiveDListAppendListTest) {
156 // Append to empty list.
157 {
158 IntrusiveDList<Item> all;
159 IntrusiveDList<Item> other;
160
161 Item a1(1, 11), a2(2, 12);
162 all.Append(&a1);
163 all.Append(&a2);
164
165 other.AppendList(&all);
166
167 EXPECT(all.IsEmpty());
168 EXPECT(!other.IsEmpty());
169 EXPECT_EQ(&a1, other.First());
170 EXPECT_EQ(&a2, other.Last());
171
172 auto it = other.Begin();
173 EXPECT_EQ(&a1, *it);
174 it = other.Erase(it);
175 EXPECT_EQ(&a2, *it);
176 it = other.Erase(it);
177 EXPECT(it == other.end());
178 }
179 // Append to non-empty list.
180 {
181 IntrusiveDList<Item> all;
182 IntrusiveDList<Item> other;
183
184 Item a1(1, 11), a2(2, 12);
185 all.Append(&a1);
186 all.Append(&a2);
187
188 Item o1(1, 11);
189 other.Append(&o1);
190
191 other.AppendList(&all);
192
193 EXPECT(all.IsEmpty());
194 EXPECT(!other.IsEmpty());
195 EXPECT_EQ(&o1, other.First());
196 EXPECT_EQ(&a2, other.Last());
197
198 auto it = other.Begin();
199 EXPECT_EQ(&o1, *it);
200 it = other.Erase(it);
201 EXPECT_EQ(&a1, *it);
202 it = other.Erase(it);
203 EXPECT_EQ(&a2, *it);
204 it = other.Erase(it);
205 EXPECT(it == other.end());
206 }
207}
208
209} // namespace dart.
210