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:

Functions
int	atoi (const char *s)
static int	compare_thunk (const void *a, const void *b, void *aux)
void	qsort (void *array, size_t cnt, size_t size, int(*compare)(const void *, const void *))
static void	do_swap (unsigned char *array, size_t a_idx, size_t b_idx, size_t size)
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)
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)
void	sort (void *array, size_t cnt, size_t size, int(*compare)(const void *, const void *, void *aux), void *aux)
void *	bsearch (const void *key, const void *array, size_t cnt, size_t size, int(*compare)(const void *, const void *))
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)

Function Documentation

atoi()

int atoi

(

const char *

s

)

{
  bool negative;
  int value;
 
  ASSERT (s != NULL);
 
  /* Skip white space. */
  while (isspace ((unsigned char) *s))
    s++;
 
  /* Parse sign. */
  negative = false;
  if (*s == '+')
    s++;
  else if (*s == '-')
    {
      negative = true;
      s++;
    }
 
  /* Parse digits.  We always initially parse the value as
     negative, and then make it positive later, because the
     negative range of an int is bigger than the positive range
     on a 2's complement system. */
  for (value = 0; isdigit (*s); s++)
    value = value * 10 - (*s - '0');
  if (!negative)
    value = -value;
 
  return value;
}

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
	)

{
  const unsigned char *first = array;
  const unsigned char *last = array + size * cnt;
 
  while (first < last) 
    {
      size_t range = (last - first) / size;
      const unsigned char *middle = first + (range / 2) * size;
      int cmp = compare (key, middle, aux);
 
      if (cmp < 0) 
        last = middle;
      else if (cmp > 0) 
        first = middle + size;
      else
        return (void *) middle;
    }
  
  return NULL;
}

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
	)

{
  return binary_search (key, array, cnt, size, compare_thunk, &compare);
}

Here is the call graph for this function:

compare_thunk()

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

static

{
  int (**compare) (const void *, const void *) = aux;
  return (*compare) (a, b);
}

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

{
  return compare (array + (a_idx - 1) * size, array + (b_idx - 1) * size, aux);
}

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

{
  unsigned char *a = array + (a_idx - 1) * size;
  unsigned char *b = array + (b_idx - 1) * size;
  size_t i;
 
  for (i = 0; i < size; i++)
    {
      unsigned char t = a[i];
      a[i] = b[i];
      b[i] = t;
    }
}

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

{
  for (;;) 
    {
      /* Set `max' to the index of the largest element among I
         and its children (if any). */
      size_t left = 2 * i;
      size_t right = 2 * i + 1;
      size_t max = i;
      if (left <= cnt && do_compare (array, left, max, size, compare, aux) > 0)
        max = left;
      if (right <= cnt
          && do_compare (array, right, max, size, compare, aux) > 0) 
        max = right;
 
      /* If the maximum value is already in element I, we're
         done. */
      if (max == i)
        break;
 
      /* Swap and continue down the heap. */
      do_swap (array, i, max, size);
      i = max;
    }
}

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
	)

{
  sort (array, cnt, size, compare_thunk, &compare);
}

Here is the call 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
	)

{
  size_t i;
 
  ASSERT (array != NULL || cnt == 0);
  ASSERT (compare != NULL);
  ASSERT (size > 0);
 
  /* Build a heap. */
  for (i = cnt / 2; i > 0; i--)
    heapify (array, i, cnt, size, compare, aux);
 
  /* Sort the heap. */
  for (i = cnt; i > 1; i--) 
    {
      do_swap (array, 1, i, size);
      heapify (array, 1, i - 1, size, compare, aux); 
    }
}

Here is the call graph for this function:

Here is the caller graph for this function: