jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2020, Sahan Fernando <sahan.h.fernando@gmail.com>
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#include <LibTest/TestCase.h>
8
9#include <AK/DeprecatedString.h>
10#include <AK/QuickSort.h>
11#include <AK/Random.h>
12#include <AK/Vector.h>
13#include <stdlib.h>
14
15const size_t NUM_RUNS = 10;
16
17struct SortableObject {
18 int m_key;
19 int m_payload;
20};
21
22static int compare_sortable_object(void const* a, void const* b)
23{
24 int const key1 = static_cast<SortableObject const*>(a)->m_key;
25 int const key2 = static_cast<SortableObject const*>(b)->m_key;
26 if (key1 < key2) {
27 return -1;
28 } else if (key1 == key2) {
29 return 0;
30 } else {
31 return 1;
32 }
33}
34
35static int calc_payload_for_pos(size_t pos)
36{
37 pos *= 231;
38 return pos ^ (pos << 8) ^ (pos << 16) ^ (pos << 24);
39}
40
41TEST_CASE(quick_sort)
42{
43 // Generate vector of SortableObjects in sorted order, with payloads determined by their sorted positions
44 Vector<SortableObject> test_objects;
45 for (auto i = 0; i < 1024; ++i) {
46 test_objects.append({ i * 137, calc_payload_for_pos(i) });
47 }
48 for (size_t i = 0; i < NUM_RUNS; i++) {
49 // Shuffle the vector, then sort it again
50 shuffle(test_objects);
51 qsort(test_objects.data(), test_objects.size(), sizeof(SortableObject), compare_sortable_object);
52 // Check that the objects are sorted by key
53 for (auto i = 0u; i + 1 < test_objects.size(); ++i) {
54 auto const& key1 = test_objects[i].m_key;
55 auto const& key2 = test_objects[i + 1].m_key;
56 if (key1 > key2) {
57 FAIL(DeprecatedString::formatted("saw key {} before key {}\n", key1, key2));
58 }
59 }
60 // Check that the object's payloads have not been corrupted
61 for (auto i = 0u; i < test_objects.size(); ++i) {
62 auto const expected = calc_payload_for_pos(i);
63 auto const payload = test_objects[i].m_payload;
64 if (payload != expected) {
65 FAIL(DeprecatedString::formatted("Expected payload {} for pos {}, got payload {}", expected, i, payload));
66 }
67 }
68 }
69}