PKUOS - Pintos
Pintos source browser for PKU Operating System course
Functions
qsort.c File Reference
#include "tests/vm/qsort.h"
#include <stdbool.h>
#include <debug.h>
#include <random.h>
Include dependency graph for qsort.c:

Go to the source code of this file.

Functions

static unsigned char pick_pivot (unsigned char *buf, size_t size)
 Picks a pivot for the quicksort from the SIZE bytes in BUF. More...
 
static bool is_partitioned (const unsigned char *array, size_t size, unsigned char pivot, size_t left_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. More...
 
static void swap (unsigned char *a, unsigned char *b)
 Swaps the bytes at *A and *B. More...
 
static size_t partition (unsigned char *array, size_t size, int pivot)
 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. More...
 
static bool is_sorted (const unsigned char *buf, size_t size)
 Returns true if the SIZE bytes in BUF are in nondecreasing order, false otherwise. More...
 
void qsort_bytes (unsigned char *buf, size_t size)
 Sorts the SIZE bytes in BUF into nondecreasing order, using the quick-sort algorithm. More...
 

Function Documentation

◆ is_partitioned()

static bool is_partitioned ( const unsigned char *  array,
size_t  size,
unsigned char  pivot,
size_t  left_size 
)
static

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.

Definition at line 19 of file qsort.c.

Referenced by partition().

Here is the caller graph for this function:

◆ is_sorted()

static bool is_sorted ( const unsigned char *  buf,
size_t  size 
)
static

Returns true if the SIZE bytes in BUF are in nondecreasing order, false otherwise.

Definition at line 100 of file qsort.c.

References buf.

Referenced by qsort_bytes().

Here is the caller graph for this function:

◆ partition()

static size_t partition ( unsigned char *  array,
size_t  size,
int  pivot 
)
static

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.

Definition at line 48 of file qsort.c.

References ASSERT, is_partitioned(), and swap().

Referenced by qsort_bytes().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ pick_pivot()

static unsigned char pick_pivot ( unsigned char *  buf,
size_t  size 
)
static

Picks a pivot for the quicksort from the SIZE bytes in BUF.

Definition at line 8 of file qsort.c.

References ASSERT, buf, and random_ulong().

Referenced by qsort_bytes().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ qsort_bytes()

void qsort_bytes ( unsigned char *  buf,
size_t  size 
)

Sorts the SIZE bytes in BUF into nondecreasing order, using the quick-sort algorithm.

tests/vm/qsort.h

Definition at line 114 of file qsort.c.

References buf, is_sorted(), partition(), pick_pivot(), and qsort_bytes().

Referenced by main(), and qsort_bytes().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ swap()

static void swap ( unsigned char *  a,
unsigned char *  b 
)
static

Swaps the bytes at *A and *B.

Definition at line 37 of file qsort.c.

Referenced by partition().

Here is the caller graph for this function: