jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2021, the SerenityOS developers.
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#include <LibTest/TestCase.h>
8
9#include <AK/SinglyLinkedList.h>
10
11static SinglyLinkedList<int> make_list()
12{
13 SinglyLinkedList<int> list {};
14 list.append(0);
15 list.append(1);
16 list.append(2);
17 list.append(3);
18 list.append(4);
19 list.append(5);
20 list.append(6);
21 list.append(7);
22 list.append(8);
23 list.append(9);
24 return list;
25}
26
27TEST_CASE(should_find_mutable)
28{
29 auto sut = make_list();
30
31 EXPECT_EQ(4, *sut.find(4));
32
33 EXPECT_EQ(sut.end(), sut.find(42));
34}
35
36TEST_CASE(should_find_mutable_with_predicate)
37{
38 auto sut = make_list();
39
40 EXPECT_EQ(4, *sut.find_if([](auto const v) { return v == 4; }));
41
42 EXPECT_EQ(sut.end(), sut.find_if([](auto const v) { return v == 42; }));
43}
44
45TEST_CASE(should_find_const)
46{
47 auto const sut = make_list();
48
49 EXPECT_EQ(4, *sut.find(4));
50
51 EXPECT_EQ(sut.end(), sut.find(42));
52}
53
54TEST_CASE(should_find_const_with_predicate)
55{
56 auto const sut = make_list();
57
58 EXPECT_EQ(4, *sut.find_if([](auto const v) { return v == 4; }));
59
60 EXPECT_EQ(sut.end(), sut.find_if([](auto const v) { return v == 42; }));
61}
62
63TEST_CASE(removal_during_iteration)
64{
65 auto list = make_list();
66 auto size = list.size();
67
68 for (auto it = list.begin(); it != list.end(); ++it, --size) {
69 VERIFY(list.size() == size);
70 it.remove(list);
71 }
72}
73
74static size_t calls_to_increase { 0 };
75static size_t calls_to_decrease { 0 };
76static size_t calls_to_reset { 0 };
77static size_t calls_to_get_size { 0 };
78
79static void setup()
80{
81 calls_to_increase = 0;
82 calls_to_decrease = 0;
83 calls_to_reset = 0;
84 calls_to_get_size = 0;
85}
86
87struct TestSizeCalculationPolicy {
88 void increase_size(auto const&) { ++calls_to_increase; }
89
90 void decrease_size(auto const&) { ++calls_to_decrease; }
91
92 void reset() { ++calls_to_reset; }
93
94 size_t size(auto const*) const
95 {
96 ++calls_to_get_size;
97 return 42;
98 }
99};
100
101TEST_CASE(should_increase_size_when_appending)
102{
103 setup();
104 SinglyLinkedList<int, TestSizeCalculationPolicy> list {};
105 list.append(0);
106 EXPECT_EQ(1u, calls_to_increase);
107}
108
109TEST_CASE(should_decrease_size_when_removing)
110{
111 setup();
112 SinglyLinkedList<int, TestSizeCalculationPolicy> list {};
113 list.append(0);
114 auto begin = list.begin();
115 list.remove(begin);
116 EXPECT_EQ(1u, calls_to_decrease);
117}
118
119TEST_CASE(should_reset_size_when_clearing)
120{
121 setup();
122 SinglyLinkedList<int, TestSizeCalculationPolicy> list {};
123 list.append(0);
124 list.clear();
125 EXPECT_EQ(1u, calls_to_reset);
126}
127
128TEST_CASE(should_get_size_from_policy)
129{
130 setup();
131 SinglyLinkedList<int, TestSizeCalculationPolicy> list {};
132 EXPECT_EQ(42u, list.size());
133 EXPECT_EQ(1u, calls_to_get_size);
134}
135
136TEST_CASE(should_decrease_size_when_taking_first)
137{
138 setup();
139 SinglyLinkedList<int, TestSizeCalculationPolicy> list {};
140 list.append(0);
141 list.take_first();
142 EXPECT_EQ(1u, calls_to_decrease);
143}
144
145TEST_CASE(should_increase_size_when_try_appending)
146{
147 setup();
148 SinglyLinkedList<int, TestSizeCalculationPolicy> list {};
149 MUST(list.try_append(0));
150 EXPECT_EQ(1u, calls_to_increase);
151}
152
153TEST_CASE(should_increase_size_when_try_prepending)
154{
155 setup();
156 SinglyLinkedList<int, TestSizeCalculationPolicy> list {};
157 MUST(list.try_prepend(0));
158 EXPECT_EQ(1u, calls_to_increase);
159}
160
161TEST_CASE(should_increase_size_when_try_inserting_before)
162{
163 setup();
164 SinglyLinkedList<int, TestSizeCalculationPolicy> list {};
165 MUST(list.try_insert_before(list.begin(), 42));
166 EXPECT_EQ(1u, calls_to_increase);
167}
168
169TEST_CASE(should_increase_size_when_try_inserting_after)
170{
171 setup();
172 SinglyLinkedList<int, TestSizeCalculationPolicy> list {};
173 MUST(list.try_insert_after(list.begin(), 42));
174 EXPECT_EQ(1u, calls_to_increase);
175}
176
177TEST_CASE(should_increase_size_when_inserting_before)
178{
179 setup();
180 SinglyLinkedList<int, TestSizeCalculationPolicy> list {};
181 list.insert_before(list.begin(), 42);
182 EXPECT_EQ(1u, calls_to_increase);
183}
184
185TEST_CASE(should_increase_size_when_inserting_after)
186{
187 setup();
188 SinglyLinkedList<int, TestSizeCalculationPolicy> list {};
189 list.insert_after(list.begin(), 42);
190 EXPECT_EQ(1u, calls_to_increase);
191}