1 #include "tests/vm/qsort.h"
6 /* Picks a pivot for the quicksort from the SIZE bytes in BUF. */
8 pick_pivot (unsigned char *buf, size_t size)
11 return buf[random_ulong () % size];
14 /* Checks whether the SIZE bytes in ARRAY are divided into an
15 initial LEFT_SIZE elements all less than PIVOT followed by
16 SIZE - LEFT_SIZE elements all greater than or equal to
19 is_partitioned (const unsigned char *array, size_t size,
20 unsigned char pivot, size_t left_size)
24 for (i = 0; i < left_size; i++)
25 if (array[i] >= pivot)
35 /* Swaps the bytes at *A and *B. */
37 swap (unsigned char *a, unsigned char *b)
44 /* Partitions ARRAY in-place in an initial run of bytes all less
45 than PIVOT, followed by a run of bytes all greater than or
46 equal to PIVOT. Returns the length of the initial run. */
48 partition (unsigned char *array, size_t size, int pivot)
50 size_t left_size = size;
51 unsigned char *first = array;
52 unsigned char *last = first + left_size;
56 /* Move FIRST forward to point to first element greater than
62 ASSERT (is_partitioned (array, size, pivot, left_size));
65 else if (*first >= pivot)
72 /* Move LAST backward to point to last element no bigger
80 ASSERT (is_partitioned (array, size, pivot, left_size));
83 else if (*last < pivot)
89 /* By swapping FIRST and LAST we extend the starting and
90 ending sequences that pass and fail, respectively,
97 /* Returns true if the SIZE bytes in BUF are in nondecreasing
98 order, false otherwise. */
100 is_sorted (const unsigned char *buf, size_t size)
104 for (i = 1; i < size; i++)
105 if (buf[i - 1] > buf[i])
111 /* Sorts the SIZE bytes in BUF into nondecreasing order, using
112 the quick-sort algorithm. */
114 qsort_bytes (unsigned char *buf, size_t size)
116 if (!is_sorted (buf, size))
118 int pivot = pick_pivot (buf, size);
120 unsigned char *left_half = buf;
121 size_t left_size = partition (buf, size, pivot);
122 unsigned char *right_half = left_half + left_size;
123 size_t right_size = size - left_size;
125 if (left_size <= right_size)
127 qsort_bytes (left_half, left_size);
128 qsort_bytes (right_half, right_size);
132 qsort_bytes (right_half, right_size);
133 qsort_bytes (left_half, left_size);