list.c File Reference

#include "list.h"
#include "../debug.h"

Include dependency graph for list.c:

Functions
static bool	is_sorted (struct list_elem *a, struct list_elem *b, list_less_func *less, void *aux) UNUSED
static bool	is_head (struct list_elem *elem)
static bool	is_interior (struct list_elem *elem)
static bool	is_tail (struct list_elem *elem)
void	list_init (struct list *list)
struct list_elem *	list_begin (struct list *list)
struct list_elem *	list_next (struct list_elem *elem)
struct list_elem *	list_end (struct list *list)
struct list_elem *	list_rbegin (struct list *list)
struct list_elem *	list_prev (struct list_elem *elem)
struct list_elem *	list_rend (struct list *list)
struct list_elem *	list_head (struct list *list)
struct list_elem *	list_tail (struct list *list)
void	list_insert (struct list_elem *before, struct list_elem *elem)
void	list_splice (struct list_elem *before, struct list_elem *first, struct list_elem *last)
void	list_push_front (struct list *list, struct list_elem *elem)
void	list_push_back (struct list *list, struct list_elem *elem)
struct list_elem *	list_remove (struct list_elem *elem)
struct list_elem *	list_pop_front (struct list *list)
struct list_elem *	list_pop_back (struct list *list)
struct list_elem *	list_front (struct list *list)
struct list_elem *	list_back (struct list *list)
size_t	list_size (struct list *list)
bool	list_empty (struct list *list)
static void	swap (struct list_elem **a, struct list_elem **b)
void	list_reverse (struct list *list)
static struct list_elem *	find_end_of_run (struct list_elem *a, struct list_elem *b, list_less_func *less, void *aux)
static void	inplace_merge (struct list_elem *a0, struct list_elem *a1b0, struct list_elem *b1, list_less_func *less, void *aux)
void	list_sort (struct list *list, list_less_func *less, void *aux)
void	list_insert_ordered (struct list *list, struct list_elem *elem, list_less_func *less, void *aux)
void	list_unique (struct list *list, struct list *duplicates, list_less_func *less, void *aux)
struct list_elem *	list_max (struct list *list, list_less_func *less, void *aux)
struct list_elem *	list_min (struct list *list, list_less_func *less, void *aux)

Function Documentation

find_end_of_run()

static struct list_elem * find_end_of_run ( struct list_elem *  a, struct list_elem *  b, list_less_func *  less, void *  aux  )

static

                                         {
    ASSERT (a != NULL);
    ASSERT (b != NULL);
    ASSERT (less != NULL);
    ASSERT (a != b);
 
    do {
        a = list_next (a);
    } while (a != b && !less (a, list_prev (a), aux));
    return a;
}

Here is the call graph for this function:

Here is the caller graph for this function:

inplace_merge()

static void inplace_merge ( struct list_elem *  a0, struct list_elem *  a1b0, struct list_elem *  b1, list_less_func *  less, void *  aux  )

static

                                         {
    ASSERT (a0 != NULL);
    ASSERT (a1b0 != NULL);
    ASSERT (b1 != NULL);
    ASSERT (less != NULL);
    ASSERT (is_sorted (a0, a1b0, less, aux));
    ASSERT (is_sorted (a1b0, b1, less, aux));
 
    while (a0 != a1b0 && a1b0 != b1)
        if (!less (a1b0, a0, aux))
            a0 = list_next (a0);
        else {
            a1b0 = list_next (a1b0);
            list_splice (a0, list_prev (a1b0), a1b0);
        }
}

Here is the call graph for this function:

Here is the caller graph for this function:

is_head()

static bool is_head ( struct list_elem *  elem )

inlinestatic

                                 {
    return elem != NULL && elem->prev == NULL && elem->next != NULL;
}

Here is the caller graph for this function:

is_interior()

static bool is_interior ( struct list_elem *  elem )

inlinestatic

                                     {
    return elem != NULL && elem->prev != NULL && elem->next != NULL;
}

Here is the caller graph for this function:

is_sorted()

static bool is_sorted ( struct list_elem *  a, struct list_elem *  b, list_less_func *  less, void *  aux  )

static

                                         {
    if (a != b)
        while ((a = list_next (a)) != b)
            if (less (a, list_prev (a), aux))
                return false;
    return true;
}

Here is the call graph for this function:

Here is the caller graph for this function:

is_tail()

static bool is_tail ( struct list_elem *  elem )

inlinestatic

                                 {
    return elem != NULL && elem->prev != NULL && elem->next == NULL;
}

Here is the caller graph for this function:

list_back()

struct list_elem * list_back

(

struct list *

list

)

                              {
    ASSERT (!list_empty (list));
    return list->tail.prev;
}

Here is the call graph for this function:

Here is the caller graph for this function:

list_begin()

struct list_elem * list_begin

(

struct list *

list

)

                               {
    ASSERT (list != NULL);
    return list->head.next;
}

Here is the caller graph for this function:

list_empty()

bool list_empty

(

struct list *

list

)

                               {
    return list_begin (list) == list_end (list);
}

Here is the call graph for this function:

Here is the caller graph for this function:

list_end()

struct list_elem * list_end

(

struct list *

list

)

                             {
    ASSERT (list != NULL);
    return &list->tail;
}

Here is the caller graph for this function:

list_front()

struct list_elem * list_front

(

struct list *

list

)

                               {
    ASSERT (!list_empty (list));
    return list->head.next;
}

Here is the call graph for this function:

Here is the caller graph for this function:

list_head()

struct list_elem * list_head

(

struct list *

list

)

                              {
    ASSERT (list != NULL);
    return &list->head;
}

Here is the caller graph for this function:

list_init()

void list_init

(

struct list *

list

)

                              {
    ASSERT (list != NULL);
    list->head.prev = NULL;
    list->head.next = &list->tail;
    list->tail.prev = &list->head;
    list->tail.next = NULL;
}

Here is the caller graph for this function:

list_insert()

void list_insert	(	struct list_elem *	before,
		struct list_elem *	elem
	)

                                                               {
    ASSERT (is_interior (before) || is_tail (before));
    ASSERT (elem != NULL);
 
    elem->prev = before->prev;
    elem->next = before;
    before->prev->next = elem;
    before->prev = elem;
}

Here is the call graph for this function:

Here is the caller graph for this function:

list_insert_ordered()

void list_insert_ordered	(	struct list *	list,
		struct list_elem *	elem,
		list_less_func *	less,
		void *	aux
	)

                                         {
    struct list_elem *e;
 
    ASSERT (list != NULL);
    ASSERT (elem != NULL);
    ASSERT (less != NULL);
 
    for (e = list_begin (list); e != list_end (list); e = list_next (e))
        if (less (elem, e, aux))
            break;
    return list_insert (e, elem);
}

Here is the call graph for this function:

Here is the caller graph for this function:

list_max()

struct list_elem * list_max	(	struct list *	list,
		list_less_func *	less,
		void *	aux
	)

                                                              {
    struct list_elem *max = list_begin (list);
    if (max != list_end (list)) {
        struct list_elem *e;
 
        for (e = list_next (max); e != list_end (list); e = list_next (e))
            if (less (max, e, aux))
                max = e;
    }
    return max;
}

Here is the call graph for this function:

list_min()

struct list_elem * list_min	(	struct list *	list,
		list_less_func *	less,
		void *	aux
	)

                                                              {
    struct list_elem *min = list_begin (list);
    if (min != list_end (list)) {
        struct list_elem *e;
 
        for (e = list_next (min); e != list_end (list); e = list_next (e))
            if (less (e, min, aux))
                min = e;
    }
    return min;
}

Here is the call graph for this function:

list_next()

struct list_elem * list_next

(

struct list_elem *

elem

)

                                   {
    ASSERT (is_head (elem) || is_interior (elem));
    return elem->next;
}

Here is the call graph for this function:

Here is the caller graph for this function:

list_pop_back()

struct list_elem * list_pop_back

(

struct list *

list

)

                                  {
    struct list_elem *back = list_back (list);
    list_remove (back);
    return back;
}

Here is the call graph for this function:

list_pop_front()

struct list_elem * list_pop_front

(

struct list *

list

)

                                   {
    struct list_elem *front = list_front (list);
    list_remove (front);
    return front;
}

Here is the call graph for this function:

Here is the caller graph for this function:

list_prev()

struct list_elem * list_prev

(

struct list_elem *

elem

)

                                   {
    ASSERT (is_interior (elem) || is_tail (elem));
    return elem->prev;
}

Here is the call graph for this function:

Here is the caller graph for this function:

list_push_back()

void list_push_back	(	struct list *	list,
		struct list_elem *	elem
	)

                                                           {
    list_insert (list_end (list), elem);
}

Here is the call graph for this function:

Here is the caller graph for this function:

list_push_front()

void list_push_front	(	struct list *	list,
		struct list_elem *	elem
	)

                                                            {
    list_insert (list_begin (list), elem);
}

Here is the call graph for this function:

Here is the caller graph for this function:

list_rbegin()

struct list_elem * list_rbegin

(

struct list *

list

)

                                {
    ASSERT (list != NULL);
    return list->tail.prev;
}

list_remove()

struct list_elem * list_remove

(

struct list_elem *

elem

)

                                     {
    ASSERT (is_interior (elem));
    elem->prev->next = elem->next;
    elem->next->prev = elem->prev;
    return elem->next;
}

Here is the call graph for this function:

Here is the caller graph for this function:

list_rend()

struct list_elem * list_rend

(

struct list *

list

)

                              {
    ASSERT (list != NULL);
    return &list->head;
}

list_reverse()

void list_reverse

(

struct list *

list

)

                                 {
    if (!list_empty (list)) {
        struct list_elem *e;
 
        for (e = list_begin (list); e != list_end (list); e = e->prev)
            swap (&e->prev, &e->next);
        swap (&list->head.next, &list->tail.prev);
        swap (&list->head.next->prev, &list->tail.prev->next);
    }
}

Here is the call graph for this function:

list_size()

size_t list_size

(

struct list *

list

)

                              {
    struct list_elem *e;
    size_t cnt = 0;
 
    for (e = list_begin (list); e != list_end (list); e = list_next (e))
        cnt++;
    return cnt;
}

Here is the call graph for this function:

list_sort()

void list_sort	(	struct list *	list,
		list_less_func *	less,
		void *	aux
	)

                                                               {
    size_t output_run_cnt;        /* Number of runs output in current pass. */
 
    ASSERT (list != NULL);
    ASSERT (less != NULL);
 
    /* Pass over the list repeatedly, merging adjacent runs of
       nondecreasing elements, until only one run is left. */
    do {
        struct list_elem *a0;     /* Start of first run. */
        struct list_elem *a1b0;   /* End of first run, start of second. */
        struct list_elem *b1;     /* End of second run. */
 
        output_run_cnt = 0;
        for (a0 = list_begin (list); a0 != list_end (list); a0 = b1) {
            /* Each iteration produces one output run. */
            output_run_cnt++;
 
            /* Locate two adjacent runs of nondecreasing elements
               A0...A1B0 and A1B0...B1. */
            a1b0 = find_end_of_run (a0, list_end (list), less, aux);
            if (a1b0 == list_end (list))
                break;
            b1 = find_end_of_run (a1b0, list_end (list), less, aux);
 
            /* Merge the runs. */
            inplace_merge (a0, a1b0, b1, less, aux);
        }
    }
    while (output_run_cnt > 1);
 
    ASSERT (is_sorted (list_begin (list), list_end (list), less, aux));
}

Here is the call graph for this function:

Here is the caller graph for this function:

list_splice()

void list_splice	(	struct list_elem *	before,
		struct list_elem *	first,
		struct list_elem *	last
	)

                                                         {
    ASSERT (is_interior (before) || is_tail (before));
    if (first == last)
        return;
    last = list_prev (last);
 
    ASSERT (is_interior (first));
    ASSERT (is_interior (last));
 
    /* Cleanly remove FIRST...LAST from its current list. */
    first->prev->next = last->next;
    last->next->prev = first->prev;
 
    /* Splice FIRST...LAST into new list. */
    first->prev = before->prev;
    last->next = before;
    before->prev->next = first;
    before->prev = last;
}

Here is the call graph for this function:

Here is the caller graph for this function:

list_tail()

struct list_elem * list_tail

(

struct list *

list

)

                              {
    ASSERT (list != NULL);
    return &list->tail;
}

list_unique()

void list_unique	(	struct list *	list,
		struct list *	duplicates,
		list_less_func *	less,
		void *	aux
	)

                                         {
    struct list_elem *elem, *next;
 
    ASSERT (list != NULL);
    ASSERT (less != NULL);
    if (list_empty (list))
        return;
 
    elem = list_begin (list);
    while ((next = list_next (elem)) != list_end (list))
        if (!less (elem, next, aux) && !less (next, elem, aux)) {
            list_remove (next);
            if (duplicates != NULL)
                list_push_back (duplicates, next);
        } else
            elem = next;
}

Here is the call graph for this function:

swap()

static void swap ( struct list_elem **  a, struct list_elem **  b  )

static

                                                  {
    struct list_elem *t = *a;
    *a = *b;
    *b = t;
}

Here is the caller graph for this function: