1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
|
//===-- Unittests for qsort_r ---------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#include "src/stdlib/qsort_r.h"
#include "test/UnitTest/Test.h"
#include "hdr/types/size_t.h"
static int int_compare_count(const void *l, const void *r, void *count_arg) {
int li = *reinterpret_cast<const int *>(l);
int ri = *reinterpret_cast<const int *>(r);
size_t *count = reinterpret_cast<size_t *>(count_arg);
*count = *count + 1;
if (li == ri)
return 0;
else if (li > ri)
return 1;
else
return -1;
}
TEST(LlvmLibcQsortRTest, SortedArray) {
int array[25] = {10, 23, 33, 35, 55, 70, 71, 100, 110,
123, 133, 135, 155, 170, 171, 1100, 1110, 1123,
1133, 1135, 1155, 1170, 1171, 11100, 12310};
constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int);
size_t count = 0;
LIBC_NAMESPACE::qsort_r(array, ARRAY_SIZE, sizeof(int), int_compare_count,
&count);
ASSERT_LE(array[0], 10);
ASSERT_LE(array[1], 23);
ASSERT_LE(array[2], 33);
ASSERT_LE(array[3], 35);
ASSERT_LE(array[4], 55);
ASSERT_LE(array[5], 70);
ASSERT_LE(array[6], 71);
ASSERT_LE(array[7], 100);
ASSERT_LE(array[8], 110);
ASSERT_LE(array[9], 123);
ASSERT_LE(array[10], 133);
ASSERT_LE(array[11], 135);
ASSERT_LE(array[12], 155);
ASSERT_LE(array[13], 170);
ASSERT_LE(array[14], 171);
ASSERT_LE(array[15], 1100);
ASSERT_LE(array[16], 1110);
ASSERT_LE(array[17], 1123);
ASSERT_LE(array[18], 1133);
ASSERT_LE(array[19], 1135);
ASSERT_LE(array[20], 1155);
ASSERT_LE(array[21], 1170);
ASSERT_LE(array[22], 1171);
ASSERT_LE(array[23], 11100);
ASSERT_LE(array[24], 12310);
// This is a sorted list, but there still have to have been at least N - 1
// comparisons made.
ASSERT_GE(count, ARRAY_SIZE - 1);
}
TEST(LlvmLibcQsortRTest, ReverseSortedArray) {
int array[25] = {25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13,
12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int);
size_t count = 0;
LIBC_NAMESPACE::qsort_r(array, ARRAY_SIZE, sizeof(int), int_compare_count,
&count);
for (int i = 0; i < int(ARRAY_SIZE - 1); ++i)
ASSERT_LE(array[i], i + 1);
ASSERT_GE(count, ARRAY_SIZE);
}
// The following test is intended to mimic the CPP library pattern of having a
// comparison function that takes a specific type, which is passed to a library
// that then needs to sort an array of that type. The library can't safely pass
// the comparison function to qsort because a function that takes const T*
// being cast to a function that takes const void* is undefined behavior. The
// safer pattern is to pass a type erased comparator that calls into the typed
// comparator to qsort_r.
struct PriorityVal {
int priority;
int size;
};
static int compare_priority_val(const PriorityVal *l, const PriorityVal *r) {
// Subtracting the priorities is unsafe, but it's fine for this test.
int priority_diff = l->priority - r->priority;
if (priority_diff != 0) {
return priority_diff;
}
if (l->size == r->size) {
return 0;
} else if (l->size > r->size) {
return 1;
} else {
return -1;
}
}
template <typename T>
static int type_erased_comp(const void *l, const void *r,
void *erased_func_ptr) {
typedef int (*TypedComp)(const T *, const T *);
TypedComp typed_func_ptr = reinterpret_cast<TypedComp>(erased_func_ptr);
const T *lt = reinterpret_cast<const T *>(l);
const T *rt = reinterpret_cast<const T *>(r);
return typed_func_ptr(lt, rt);
}
TEST(LlvmLibcQsortRTest, SafeTypeErasure) {
PriorityVal array[5] = {
{10, 3}, {1, 10}, {-1, 100}, {10, 0}, {3, 3},
};
constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(PriorityVal);
LIBC_NAMESPACE::qsort_r(array, ARRAY_SIZE, sizeof(PriorityVal),
type_erased_comp<PriorityVal>,
reinterpret_cast<void *>(compare_priority_val));
EXPECT_EQ(array[0].priority, -1);
EXPECT_EQ(array[0].size, 100);
EXPECT_EQ(array[1].priority, 1);
EXPECT_EQ(array[1].size, 10);
EXPECT_EQ(array[2].priority, 3);
EXPECT_EQ(array[2].size, 3);
EXPECT_EQ(array[3].priority, 10);
EXPECT_EQ(array[3].size, 0);
EXPECT_EQ(array[4].priority, 10);
EXPECT_EQ(array[4].size, 3);
}
|
