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: