PKUOS - Pintos
Pintos source browser for PKU Operating System course
Functions
stdlib.c File Reference
#include <ctype.h>
#include <debug.h>
#include <random.h>
#include <stdlib.h>
#include <stdbool.h>
Include dependency graph for stdlib.c:

Go to the source code of this file.

Functions

int atoi (const char *s)
 Converts a string representation of a signed decimal integer in S into an ‘int’, which is returned. More...
 
static int compare_thunk (const void *a, const void *b, void *aux)
 Compares A and B by calling the AUX function. More...
 
void qsort (void *array, size_t cnt, size_t size, int(*compare)(const void *, const void *))
 Sorts ARRAY, which contains CNT elements of SIZE bytes each, using COMPARE. More...
 
static void do_swap (unsigned char *array, size_t a_idx, size_t b_idx, size_t size)
 Swaps elements with 1-based indexes A_IDX and B_IDX in ARRAY with elements of SIZE bytes each. More...
 
static int do_compare (unsigned char *array, size_t a_idx, size_t b_idx, size_t size, int(*compare)(const void *, const void *, void *aux), void *aux)
 Compares elements with 1-based indexes A_IDX and B_IDX in ARRAY with elements of SIZE bytes each, using COMPARE to compare elements, passing AUX as auxiliary data, and returns a strcmp()-type result. More...
 
static void heapify (unsigned char *array, size_t i, size_t cnt, size_t size, int(*compare)(const void *, const void *, void *aux), void *aux)
 "Float down" the element with 1-based index I in ARRAY of CNT elements of SIZE bytes each, using COMPARE to compare elements, passing AUX as auxiliary data. More...
 
void sort (void *array, size_t cnt, size_t size, int(*compare)(const void *, const void *, void *aux), void *aux)
 Sorts ARRAY, which contains CNT elements of SIZE bytes each, using COMPARE to compare elements, passing AUX as auxiliary data. More...
 
void * bsearch (const void *key, const void *array, size_t cnt, size_t size, int(*compare)(const void *, const void *))
 Searches ARRAY, which contains CNT elements of SIZE bytes each, for the given KEY. More...
 
void * binary_search (const void *key, const void *array, size_t cnt, size_t size, int(*compare)(const void *, const void *, void *aux), void *aux)
 Searches ARRAY, which contains CNT elements of SIZE bytes each, for the given KEY. More...
 

Function Documentation

◆ atoi()

int atoi ( const char *  s)

Converts a string representation of a signed decimal integer in S into an ‘int’, which is returned.

Standard functions.

Definition at line 10 of file stdlib.c.

References ASSERT, isdigit(), isspace(), NULL, and s.

Referenced by expand(), main(), and parse_options().

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

◆ binary_search()

void * binary_search ( const void *  key,
const void *  array,
size_t  cnt,
size_t  size,
int(*)(const void *, const void *, void *aux)  compare,
void *  aux 
)

Searches ARRAY, which contains CNT elements of SIZE bytes each, for the given KEY.

lib/stdlib.h

Returns a match is found, otherwise a null pointer. If there are multiple matches, returns an arbitrary one of them.

ARRAY must be sorted in order according to COMPARE.

Uses COMPARE to compare elements, passing AUX as auxiliary data. When COMPARE is passed a pair of elements A and B, respectively, it must return a strcmp()-type result, i.e. less than zero if A < B, zero if A == B, greater than zero if A > B.

Definition at line 185 of file stdlib.c.

References NULL.

Referenced by bsearch().

Here is the caller graph for this function:

◆ bsearch()

void * bsearch ( const void *  key,
const void *  array,
size_t  cnt,
size_t  size,
int(*)(const void *, const void *)  compare 
)

Searches ARRAY, which contains CNT elements of SIZE bytes each, for the given KEY.

Returns a match is found, otherwise a null pointer. If there are multiple matches, returns an arbitrary one of them.

ARRAY must be sorted in order according to COMPARE.

Uses COMPARE to compare elements. When COMPARE is passed a pair of elements A and B, respectively, it must return a strcmp()-type result, i.e. less than zero if A < B, zero if A == B, greater than zero if A > B.

Definition at line 166 of file stdlib.c.

References binary_search(), and compare_thunk().

Referenced by verify_bsearch().

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

◆ compare_thunk()

static int compare_thunk ( const void *  a,
const void *  b,
void *  aux 
)
static

Compares A and B by calling the AUX function.

Definition at line 45 of file stdlib.c.

Referenced by bsearch(), and qsort().

Here is the caller graph for this function:

◆ do_compare()

static int do_compare ( unsigned char *  array,
size_t  a_idx,
size_t  b_idx,
size_t  size,
int(*)(const void *, const void *, void *aux)  compare,
void *  aux 
)
static

Compares elements with 1-based indexes A_IDX and B_IDX in ARRAY with elements of SIZE bytes each, using COMPARE to compare elements, passing AUX as auxiliary data, and returns a strcmp()-type result.

Definition at line 86 of file stdlib.c.

Referenced by heapify().

Here is the caller graph for this function:

◆ do_swap()

static void do_swap ( unsigned char *  array,
size_t  a_idx,
size_t  b_idx,
size_t  size 
)
static

Swaps elements with 1-based indexes A_IDX and B_IDX in ARRAY with elements of SIZE bytes each.

Definition at line 67 of file stdlib.c.

Referenced by heapify(), and sort().

Here is the caller graph for this function:

◆ heapify()

static void heapify ( unsigned char *  array,
size_t  i,
size_t  cnt,
size_t  size,
int(*)(const void *, const void *, void *aux)  compare,
void *  aux 
)
static

"Float down" the element with 1-based index I in ARRAY of CNT elements of SIZE bytes each, using COMPARE to compare elements, passing AUX as auxiliary data.

Definition at line 97 of file stdlib.c.

References do_compare(), and do_swap().

Referenced by sort().

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

◆ qsort()

void qsort ( void *  array,
size_t  cnt,
size_t  size,
int(*)(const void *, const void *)  compare 
)

Sorts ARRAY, which contains CNT elements of SIZE bytes each, using COMPARE.

When COMPARE is passed a pair of elements A and B, respectively, it must return a strcmp()-type result, i.e. less than zero if A < B, zero if A == B, greater than zero if A > B. Runs in O(n lg n) time and O(1) space in CNT.

Definition at line 58 of file stdlib.c.

References compare_thunk(), and sort().

Referenced by test().

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

◆ sort()

void sort ( void *  array,
size_t  cnt,
size_t  size,
int(*)(const void *, const void *, void *aux)  compare,
void *  aux 
)

Sorts ARRAY, which contains CNT elements of SIZE bytes each, using COMPARE to compare elements, passing AUX as auxiliary data.

Nonstandard functions.

When COMPARE is passed a pair of elements A and B, respectively, it must return a strcmp()-type result, i.e. less than zero if A < B, zero if A == B, greater than zero if A > B. Runs in O(n lg n) time and O(1) space in CNT.

Definition at line 132 of file stdlib.c.

References ASSERT, do_swap(), heapify(), and NULL.

Referenced by qsort().

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