jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2021, Ali Mohammad Pur <mpfard@serenityos.org>
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#include <LibTest/TestCase.h>
8
9#include <AK/DeprecatedString.h>
10#include <AK/DisjointChunks.h>
11#include <AK/FixedArray.h>
12#include <AK/Vector.h>
13
14TEST_CASE(basic)
15{
16 DisjointChunks<size_t> chunks;
17 EXPECT(chunks.is_empty());
18 chunks.append({});
19 EXPECT(chunks.is_empty());
20 chunks.last_chunk().append(0);
21 EXPECT(!chunks.is_empty());
22 chunks.append({});
23 chunks.last_chunk().append(1);
24 chunks.last_chunk().append(2);
25 chunks.last_chunk().append(3);
26 chunks.append({});
27 chunks.append({});
28 chunks.last_chunk().append(4);
29
30 for (size_t i = 0; i < 5u; ++i)
31 EXPECT_EQ(chunks.at(i), i);
32
33 auto it = chunks.begin();
34 for (size_t i = 0; i < 5u; ++i, ++it)
35 EXPECT_EQ(*it, i);
36
37 EXPECT_EQ(it, chunks.end());
38
39 DisjointChunks<size_t> new_chunks;
40 new_chunks.extend(move(chunks));
41 EXPECT_EQ(new_chunks.size(), 5u);
42
43 new_chunks.last_chunk().append(5);
44
45 auto cut_off_slice = new_chunks.release_slice(2, 3);
46 EXPECT_EQ(new_chunks.size(), 3u);
47 EXPECT_EQ(cut_off_slice.size(), 3u);
48
49 EXPECT_EQ(cut_off_slice[0], 2u);
50 EXPECT_EQ(cut_off_slice[1], 3u);
51 EXPECT_EQ(cut_off_slice[2], 4u);
52
53 EXPECT_EQ(new_chunks[0], 0u);
54 EXPECT_EQ(new_chunks[1], 1u);
55 EXPECT_EQ(new_chunks[2], 5u);
56}
57
58TEST_CASE(fixed_array)
59{
60 DisjointChunks<size_t, FixedArray<size_t>> chunks;
61 EXPECT(chunks.is_empty());
62 chunks.append({});
63 EXPECT(chunks.is_empty());
64 chunks.append(MUST(FixedArray<size_t>::create({ 0, 1 })));
65 EXPECT(!chunks.is_empty());
66 chunks.append({});
67 chunks.append(MUST(FixedArray<size_t>::create(3)));
68 chunks.last_chunk()[0] = 2;
69 chunks.last_chunk()[1] = 3;
70 chunks.last_chunk()[2] = 4;
71 chunks.append({});
72 chunks.append(MUST(FixedArray<size_t>::create(1)));
73 chunks.last_chunk()[0] = 5;
74
75 for (size_t i = 0; i < 6u; ++i)
76 EXPECT_EQ(chunks.at(i), i);
77
78 auto it = chunks.begin();
79 for (size_t i = 0; i < 6u; ++i, ++it)
80 EXPECT_EQ(*it, i);
81
82 EXPECT_EQ(it, chunks.end());
83
84 DisjointChunks<size_t, FixedArray<size_t>> new_chunks;
85 new_chunks.extend(move(chunks));
86 EXPECT_EQ(new_chunks.size(), 6u);
87
88 auto cut_off_slice = new_chunks.release_slice(2, 3);
89 EXPECT_EQ(new_chunks.size(), 3u);
90 EXPECT_EQ(cut_off_slice.size(), 3u);
91
92 EXPECT_EQ(cut_off_slice[0], 2u);
93 EXPECT_EQ(cut_off_slice[1], 3u);
94 EXPECT_EQ(cut_off_slice[2], 4u);
95
96 EXPECT_EQ(new_chunks[0], 0u);
97 EXPECT_EQ(new_chunks[1], 1u);
98}
99
100TEST_CASE(spans)
101{
102 DisjointChunks<size_t> chunks;
103 chunks.append({ 0, 1, 2, 3, 4, 5 });
104 chunks.append({ 6, 7, 8, 9 });
105
106 auto spans = chunks.spans();
107 EXPECT_EQ(spans.size(), 10u);
108
109 auto slice = spans.slice(1, 4);
110 EXPECT_EQ(slice.size(), 4u);
111 EXPECT_EQ(slice[0], 1u);
112 EXPECT_EQ(slice[1], 2u);
113 EXPECT_EQ(slice[2], 3u);
114 EXPECT_EQ(slice[3], 4u);
115
116 auto cross_chunk_slice = spans.slice(4, 4);
117 EXPECT_EQ(cross_chunk_slice.size(), 4u);
118 EXPECT_EQ(cross_chunk_slice[0], 4u);
119 EXPECT_EQ(cross_chunk_slice[1], 5u);
120 EXPECT_EQ(cross_chunk_slice[2], 6u);
121 EXPECT_EQ(cross_chunk_slice[3], 7u);
122
123 auto it = cross_chunk_slice.begin();
124 for (size_t i = 0; i < 4u; ++i, ++it)
125 EXPECT_EQ(*it, i + 4u);
126
127 EXPECT_EQ(it, cross_chunk_slice.end());
128}
129
130#define INIT_ITERATIONS (1'000'000)
131#define ITERATIONS (100)
132
133static DisjointChunks<int> basic_really_empty_chunks;
134
135BENCHMARK_CASE(basic_really_empty)
136{
137 DisjointChunks<int> chunks;
138 for (size_t i = 0; i < ITERATIONS; ++i)
139 EXPECT(chunks.is_empty());
140}
141
142static DisjointChunks<int> basic_really_empty_large_chunks = []() {
143 DisjointChunks<int> chunks;
144 chunks.ensure_capacity(INIT_ITERATIONS);
145 for (size_t i = 0; i < INIT_ITERATIONS; ++i)
146 chunks.append({});
147 return chunks;
148}();
149
150BENCHMARK_CASE(basic_really_empty_large)
151{
152 for (size_t i = 0; i < ITERATIONS; ++i)
153 EXPECT(basic_really_empty_large_chunks.is_empty());
154}
155
156static DisjointChunks<int> basic_mostly_empty_chunks = []() {
157 DisjointChunks<int> chunks;
158 chunks.ensure_capacity(INIT_ITERATIONS + 1);
159 for (size_t i = 0; i < INIT_ITERATIONS; ++i)
160 chunks.append({});
161 chunks.append({ 1, 2, 3 });
162 return chunks;
163}();
164
165BENCHMARK_CASE(basic_mostly_empty)
166{
167 for (size_t i = 0; i < ITERATIONS; ++i) {
168 EXPECT(!basic_mostly_empty_chunks.is_empty());
169 }
170}
171
172static DisjointChunks<int> basic_full_chunks = []() {
173 DisjointChunks<int> chunks;
174 chunks.ensure_capacity(INIT_ITERATIONS + 1);
175 for (size_t i = 0; i < INIT_ITERATIONS; ++i)
176 chunks.append({ 1, 2, 3 });
177 return chunks;
178}();
179
180BENCHMARK_CASE(basic_full)
181{
182 for (size_t i = 0; i < ITERATIONS; ++i)
183 EXPECT(!basic_full_chunks.is_empty());
184}