jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#include <AK/Assertions.h>
8#include <AK/QuickSort.h>
9#include <stdlib.h>
10#include <sys/types.h>
11
12class SizedObject {
13public:
14 SizedObject() = delete;
15 SizedObject(void* data, size_t size)
16 : m_data(data)
17 , m_size(size)
18 {
19 }
20 void* data() const { return m_data; }
21 size_t size() const { return m_size; }
22
23private:
24 void* m_data;
25 size_t m_size;
26};
27
28namespace AK {
29
30template<>
31inline void swap(SizedObject const& a, SizedObject const& b)
32{
33 VERIFY(a.size() == b.size());
34 const size_t size = a.size();
35 auto const a_data = reinterpret_cast<char*>(a.data());
36 auto const b_data = reinterpret_cast<char*>(b.data());
37 for (auto i = 0u; i < size; ++i) {
38 swap(a_data[i], b_data[i]);
39 }
40}
41
42}
43
44class SizedObjectSlice {
45public:
46 SizedObjectSlice() = delete;
47 SizedObjectSlice(void* data, size_t element_size)
48 : m_data(data)
49 , m_element_size(element_size)
50 {
51 }
52 const SizedObject operator[](size_t index)
53 {
54 return { static_cast<char*>(m_data) + index * m_element_size, m_element_size };
55 }
56
57private:
58 void* m_data;
59 size_t m_element_size;
60};
61
62// https://pubs.opengroup.org/onlinepubs/9699919799/functions/qsort.html
63void qsort(void* bot, size_t nmemb, size_t size, int (*compar)(void const*, void const*))
64{
65 if (nmemb <= 1) {
66 return;
67 }
68
69 SizedObjectSlice slice { bot, size };
70
71 AK::dual_pivot_quick_sort(slice, 0, nmemb - 1, [=](SizedObject const& a, SizedObject const& b) { return compar(a.data(), b.data()) < 0; });
72}
73
74void qsort_r(void* bot, size_t nmemb, size_t size, int (*compar)(void const*, void const*, void*), void* arg)
75{
76 if (nmemb <= 1) {
77 return;
78 }
79
80 SizedObjectSlice slice { bot, size };
81
82 AK::dual_pivot_quick_sort(slice, 0, nmemb - 1, [=](SizedObject const& a, SizedObject const& b) { return compar(a.data(), b.data(), arg) < 0; });
83}