pintos-os.org Git - pintos-anon/blob - src/tests/vm/qsort.c

   1 #include "tests/vm/qsort.h"
   2 #include <stdbool.h>
   3 #include <debug.h>
   4 #include <random.h>
   5
   6 /* Picks a pivot for the quicksort from the SIZE bytes in BUF. */
   7 static unsigned char
   8 pick_pivot (unsigned char *buf, size_t size)
   9 {
  10   ASSERT (size >= 1);
  11   return buf[random_ulong () % size];
  12 }
  13
  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
  17    PIVOT. */
  18 static bool
  19 is_partitioned (const unsigned char *array, size_t size,
  20                 unsigned char pivot, size_t left_size)
  21 {
  22   size_t i;
  23
  24   for (i = 0; i < left_size; i++)
  25     if (array[i] >= pivot)
  26       return false;
  27
  28   for (; i < size; i++)
  29     if (array[i] < pivot)
  30       return false;
  31
  32   return true;
  33 }
  34
  35 /* Swaps the bytes at *A and *B. */
  36 static void
  37 swap (unsigned char *a, unsigned char *b)
  38 {
  39   unsigned char t = *a;
  40   *a = *b;
  41   *b = t;
  42 }
  43
  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. */
  47 static size_t
  48 partition (unsigned char *array, size_t size, int pivot)
  49 {
  50   size_t left_size = size;
  51   unsigned char *first = array;
  52   unsigned char *last = first + left_size;
  53
  54   for (;;)
  55     {
  56       /* Move FIRST forward to point to first element greater than
  57          PIVOT. */
  58       for (;;)
  59         {
  60           if (first == last)
  61             {
  62               ASSERT (is_partitioned (array, size, pivot, left_size));
  63               return left_size;
  64             }
  65           else if (*first >= pivot)
  66             break;
  67
  68           first++;
  69         }
  70       left_size--;
  71
  72       /* Move LAST backward to point to last element no bigger
  73          than PIVOT. */
  74       for (;;)
  75         {
  76           last--;
  77
  78           if (first == last)
  79             {
  80               ASSERT (is_partitioned (array, size, pivot, left_size));
  81               return left_size;
  82             }
  83           else if (*last < pivot)
  84             break;
  85           else
  86             left_size--;
  87         }
  88
  89       /* By swapping FIRST and LAST we extend the starting and
  90          ending sequences that pass and fail, respectively,
  91          PREDICATE. */
  92       swap (first, last);
  93       first++;
  94     }
  95 }
  96
  97 /* Returns true if the SIZE bytes in BUF are in nondecreasing
  98    order, false otherwise. */
  99 static bool
 100 is_sorted (const unsigned char *buf, size_t size)
 101 {
 102   size_t i;
 103
 104   for (i = 1; i < size; i++)
 105     if (buf[i - 1] > buf[i])
 106       return false;
 107
 108   return true;
 109 }
 110
 111 /* Sorts the SIZE bytes in BUF into nondecreasing order, using
 112    the quick-sort algorithm. */
 113 void
 114 qsort_bytes (unsigned char *buf, size_t size)
 115 {
 116   if (!is_sorted (buf, size))
 117     {
 118       int pivot = pick_pivot (buf, size);
 119
 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;
 124
 125       if (left_size <= right_size)
 126         {
 127           qsort_bytes (left_half, left_size);
 128           qsort_bytes (right_half, right_size);
 129         }
 130       else
 131         {
 132           qsort_bytes (right_half, right_size);
 133           qsort_bytes (left_half, left_size);
 134         }
 135     }
 136 }