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
|
#include "tests/vm/qsort.h"
#include <stdbool.h>
#include <debug.h>
#include <random.h>
/* Picks a pivot for the quicksort from the SIZE bytes in BUF. */
static unsigned char
pick_pivot (unsigned char *buf, size_t size)
{
ASSERT (size >= 1);
return buf[random_ulong () % size];
}
/* Checks whether the SIZE bytes in ARRAY are divided into an
initial LEFT_SIZE elements all less than PIVOT followed by
SIZE - LEFT_SIZE elements all greater than or equal to
PIVOT. */
static bool
is_partitioned (const unsigned char *array, size_t size,
unsigned char pivot, size_t left_size)
{
size_t i;
for (i = 0; i < left_size; i++)
if (array[i] >= pivot)
return false;
for (; i < size; i++)
if (array[i] < pivot)
return false;
return true;
}
/* Swaps the bytes at *A and *B. */
static void
swap (unsigned char *a, unsigned char *b)
{
unsigned char t = *a;
*a = *b;
*b = t;
}
/* Partitions ARRAY in-place in an initial run of bytes all less
than PIVOT, followed by a run of bytes all greater than or
equal to PIVOT. Returns the length of the initial run. */
static size_t
partition (unsigned char *array, size_t size, int pivot)
{
size_t left_size = size;
unsigned char *first = array;
unsigned char *last = first + left_size;
for (;;)
{
/* Move FIRST forward to point to first element greater than
PIVOT. */
for (;;)
{
if (first == last)
{
ASSERT (is_partitioned (array, size, pivot, left_size));
return left_size;
}
else if (*first >= pivot)
break;
first++;
}
left_size--;
/* Move LAST backward to point to last element no bigger
than PIVOT. */
for (;;)
{
last--;
if (first == last)
{
ASSERT (is_partitioned (array, size, pivot, left_size));
return left_size;
}
else if (*last < pivot)
break;
else
left_size--;
}
/* By swapping FIRST and LAST we extend the starting and
ending sequences that pass and fail, respectively,
PREDICATE. */
swap (first, last);
first++;
}
}
/* Returns true if the SIZE bytes in BUF are in nondecreasing
order, false otherwise. */
static bool
is_sorted (const unsigned char *buf, size_t size)
{
size_t i;
for (i = 1; i < size; i++)
if (buf[i - 1] > buf[i])
return false;
return true;
}
/* Sorts the SIZE bytes in BUF into nondecreasing order, using
the quick-sort algorithm. */
void
qsort_bytes (unsigned char *buf, size_t size)
{
if (!is_sorted (buf, size))
{
int pivot = pick_pivot (buf, size);
unsigned char *left_half = buf;
size_t left_size = partition (buf, size, pivot);
unsigned char *right_half = left_half + left_size;
size_t right_size = size - left_size;
if (left_size <= right_size)
{
qsort_bytes (left_half, left_size);
qsort_bytes (right_half, right_size);
}
else
{
qsort_bytes (right_half, right_size);
qsort_bytes (left_half, left_size);
}
}
}
|
