list.h File Reference

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

Include dependency graph for list.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	list_elem
struct	list

Macros
#define	list_entry(LIST_ELEM, STRUCT, MEMBER)

Typedefs
typedef bool	list_less_func(const struct list_elem *a, const struct list_elem *b, void *aux)

Functions
void	list_init (struct list *)
struct list_elem *	list_begin (struct list *)
struct list_elem *	list_next (struct list_elem *)
struct list_elem *	list_end (struct list *)
struct list_elem *	list_rbegin (struct list *)
struct list_elem *	list_prev (struct list_elem *)
struct list_elem *	list_rend (struct list *)
struct list_elem *	list_head (struct list *)
struct list_elem *	list_tail (struct list *)
void	list_insert (struct list_elem *, struct list_elem *)
void	list_splice (struct list_elem *before, struct list_elem *first, struct list_elem *last)
void	list_push_front (struct list *, struct list_elem *)
void	list_push_back (struct list *, struct list_elem *)
struct list_elem *	list_remove (struct list_elem *)
struct list_elem *	list_pop_front (struct list *)
struct list_elem *	list_pop_back (struct list *)
struct list_elem *	list_front (struct list *)
struct list_elem *	list_back (struct list *)
size_t	list_size (struct list *)
bool	list_empty (struct list *)
void	list_reverse (struct list *)
void	list_sort (struct list *, list_less_func *, void *aux)
void	list_insert_ordered (struct list *, struct list_elem *, list_less_func *, void *aux)
void	list_unique (struct list *, struct list *duplicates, list_less_func *, void *aux)
struct list_elem *	list_max (struct list *, list_less_func *, void *aux)
struct list_elem *	list_min (struct list *, list_less_func *, void *aux)

Macro Definition Documentation

list_entry

#define list_entry	(		LIST_ELEM,
			STRUCT,
			MEMBER
	)

Value:

    ((STRUCT *) ((uint8_t *) &(LIST_ELEM)->next     \
        - offsetof (STRUCT, MEMBER.next)))

Typedef Documentation

list_less_func

typedef bool list_less_func(const struct list_elem *a, const struct list_elem *b, void *aux)

Function Documentation

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: