#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
	Our doubly linked lists have two header elements: the "head" just before the first element and the "tail" just after the last element. More...

static bool	is_head (struct list_elem *elem)
	Returns true if ELEM is a head, false otherwise. More...

static bool	is_interior (struct list_elem *elem)
	Returns true if ELEM is an interior element, false otherwise. More...

static bool	is_tail (struct list_elem *elem)
	Returns true if ELEM is a tail, false otherwise. More...

void	list_init (struct list *list)
	Initializes LIST as an empty list. More...

struct list_elem *	list_begin (struct list *list)
	Returns the beginning of LIST. More...

struct list_elem *	list_next (struct list_elem *elem)
	Returns the element after ELEM in its list. More...

struct list_elem *	list_end (struct list *list)
	Returns LIST's tail. More...

struct list_elem *	list_rbegin (struct list *list)
	Returns the LIST's reverse beginning, for iterating through LIST in reverse order, from back to front. More...

struct list_elem *	list_prev (struct list_elem *elem)
	Returns the element before ELEM in its list. More...

struct list_elem *	list_rend (struct list *list)
	Returns LIST's head. More...

struct list_elem *	list_head (struct list *list)
	Return's LIST's head. More...

struct list_elem *	list_tail (struct list *list)
	Return's LIST's tail. More...

void	list_insert (struct list_elem before, struct list_elem elem)
	Inserts ELEM just before BEFORE, which may be either an interior element or a tail. More...

void	list_splice (struct list_elem before, struct list_elem first, struct list_elem *last)
	Removes elements FIRST though LAST (exclusive) from their current list, then inserts them just before BEFORE, which may be either an interior element or a tail. More...

void	list_push_front (struct list list, struct list_elem elem)
	Inserts ELEM at the beginning of LIST, so that it becomes the front in LIST. More...

void	list_push_back (struct list list, struct list_elem elem)
	Inserts ELEM at the end of LIST, so that it becomes the back in LIST. More...

struct list_elem *	list_remove (struct list_elem *elem)
	Removes ELEM from its list and returns the element that followed it. More...

struct list_elem *	list_pop_front (struct list *list)
	Removes the front element from LIST and returns it. More...

struct list_elem *	list_pop_back (struct list *list)
	Removes the back element from LIST and returns it. More...

struct list_elem *	list_front (struct list *list)
	Returns the front element in LIST. More...

struct list_elem *	list_back (struct list *list)
	Returns the back element in LIST. More...

size_t	list_size (struct list *list)
	Returns the number of elements in LIST. More...

bool	list_empty (struct list *list)
	Returns true if LIST is empty, false otherwise. More...

static void	swap (struct list_elem a, struct list_elem b)
	Swaps the `struct list_elem *'s that A and B point to. More...

void	list_reverse (struct list *list)
	Reverses the order of LIST. More...

static struct list_elem *	find_end_of_run (struct list_elem a, struct list_elem b, list_less_func less, void aux)
	Finds a run, starting at A and ending not after B, of list elements that are in nondecreasing order according to LESS given auxiliary data AUX. More...

static void	inplace_merge (struct list_elem a0, struct list_elem a1b0, struct list_elem b1, list_less_func less, void *aux)
	Merges A0 through A1B0 (exclusive) with A1B0 through B1 (exclusive) to form a combined range also ending at B1 (exclusive). More...

void	list_sort (struct list list, list_less_func less, void *aux)
	Sorts LIST according to LESS given auxiliary data AUX, using a natural iterative merge sort that runs in O(n lg n) time and O(1) space in the number of elements in LIST. More...

void	list_insert_ordered (struct list list, struct list_elem elem, list_less_func less, void aux)
	Inserts ELEM in the proper position in LIST, which must be sorted according to LESS given auxiliary data AUX. More...

void	list_unique (struct list list, struct list duplicates, list_less_func less, void aux)
	Iterates through LIST and removes all but the first in each set of adjacent elements that are equal according to LESS given auxiliary data AUX. More...

struct list_elem *	list_max (struct list list, list_less_func less, void *aux)
	Returns the element in LIST with the largest value according to LESS given auxiliary data AUX. More...

struct list_elem *	list_min (struct list list, list_less_func less, void *aux)
	Returns the element in LIST with the smallest value according to LESS given auxiliary data AUX. More...

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

Finds a run, starting at A and ending not after B, of list elements that are in nondecreasing order according to LESS given auxiliary data AUX.

Returns the (exclusive) end of the run. A through B (exclusive) must form a non-empty range.

Definition at line 358 of file list.c.

References ASSERT, list_next(), list_prev(), and NULL.

Referenced by list_sort().

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

Merges A0 through A1B0 (exclusive) with A1B0 through B1 (exclusive) to form a combined range also ending at B1 (exclusive).

Both input ranges must be nonempty and sorted in nondecreasing order according to LESS given auxiliary data AUX. The output range will be sorted the same way.

Definition at line 380 of file list.c.

References ASSERT, is_sorted(), list_next(), list_prev(), list_splice(), and NULL.

Referenced by list_sort().

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

Returns true if ELEM is a head, false otherwise.

Definition at line 39 of file list.c.

References list_elem::next, NULL, and list_elem::prev.

Referenced by list_next().

Here is the caller graph for this function:

◆ is_interior()

static bool is_interior ( struct list_elem * elem )

inlinestatic

Returns true if ELEM is an interior element, false otherwise.

Definition at line 47 of file list.c.

References list_elem::next, NULL, and list_elem::prev.

Referenced by list_insert(), list_next(), list_prev(), list_remove(), and list_splice().

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

Our doubly linked lists have two header elements: the "head" just before the first element and the "tail" just after the last element.

Returns true only if the list elements A through B (exclusive) are in order according to LESS given auxiliary data AUX.

The ‘prev’ link of the front header is null, as is the ‘next’ link of the back header. Their other two links point toward each other via the interior elements of the list.

An empty list looks like this:

               +------+     +------+
           <---| head |<--->| tail |--->
               +------+     +------+

A list with two elements in it looks like this:

 +------+     +-------+     +-------+     +------+

<—| head |<—>| 1 |<—>| 2 |<—>| tail |<—> +---—+ +----—+ +----—+ +---—+

The symmetry of this arrangement eliminates lots of special cases in list processing. For example, take a look at list_remove(): it takes only two pointer assignments and no conditionals. That's a lot simpler than the code would be without header elements.

(Because only one of the pointers in each header element is used, we could in fact combine them into a single header element without sacrificing this simplicity. But using two separate elements allows us to do a little bit of checking on some operations, which can be valuable.)

Definition at line 342 of file list.c.

References list_next(), and list_prev().

Referenced by inplace_merge(), and list_sort().

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

Returns true if ELEM is a tail, false otherwise.

Definition at line 54 of file list.c.

References list_elem::next, NULL, and list_elem::prev.

Referenced by list_insert(), list_prev(), and list_splice().

Here is the caller graph for this function:

◆ list_back()

struct list_elem * list_back ( struct list * list )

Returns the back element in LIST.

Undefined behavior if LIST is empty.

Definition at line 289 of file list.c.

References ASSERT, list_empty(), list_elem::prev, and list::tail.

Referenced by list_pop_back().

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 )

Returns the beginning of LIST.

List traversal.

Definition at line 72 of file list.c.

References ASSERT, list::head, list_elem::next, and NULL.

Referenced by block_first(), block_get_by_name(), find_elem(), hash_apply(), hash_next(), inode_open(), list_empty(), list_insert_ordered(), list_max(), list_min(), list_push_front(), list_reverse(), list_size(), list_sort(), list_unique(), rehash(), test(), thread_foreach(), and verify_list_fwd().

Here is the caller graph for this function:

◆ list_empty()

bool list_empty ( struct list * list )

Returns true if LIST is empty, false otherwise.

Definition at line 310 of file list.c.

References list_begin(), and list_end().

Referenced by cond_broadcast(), cond_signal(), hash_clear(), list_back(), list_front(), list_reverse(), list_unique(), malloc(), next_thread_to_run(), and sema_up().

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 )

Returns LIST's tail.

list_end() is often used in iterating through a list from front to back. See the big comment at the top of list.h for an example.

Definition at line 94 of file list.c.

References ASSERT, NULL, and list::tail.

Referenced by block_get_by_name(), find_elem(), hash_apply(), hash_next(), inode_open(), list_elem_to_block(), list_empty(), list_insert_ordered(), list_max(), list_min(), list_push_back(), list_reverse(), list_size(), list_sort(), list_unique(), rehash(), test(), thread_foreach(), and verify_list_fwd().

Here is the caller graph for this function:

◆ list_front()

struct list_elem * list_front ( struct list * list )

Returns the front element in LIST.

List elements.

Undefined behavior if LIST is empty.

Definition at line 280 of file list.c.

References ASSERT, list::head, list_empty(), and list_elem::next.

Referenced by list_pop_front().

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 )

Return's LIST's head.

list_head() can be used for an alternate style of iterating through a list, e.g.:

e = list_head (&list); while ((e = list_next (e)) != list_end (&list)) { ... }

Definition at line 151 of file list.c.

References ASSERT, list::head, and NULL.

Referenced by hash_first().

Here is the caller graph for this function:

◆ list_init()

void list_init ( struct list * list )

Initializes LIST as an empty list.

Definition at line 61 of file list.c.

References ASSERT, list::head, list_elem::next, NULL, list_elem::prev, and list::tail.

Referenced by cond_init(), hash_clear(), inode_init(), malloc_init(), rehash(), sema_init(), and test().

Here is the caller graph for this function:

◆ list_insert()

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

Inserts ELEM just before BEFORE, which may be either an interior element or a tail.

List insertion.

The latter case is equivalent to list_push_back().

Definition at line 169 of file list.c.

References ASSERT, is_interior(), is_tail(), list_elem::next, NULL, and list_elem::prev.

Referenced by list_insert_ordered(), list_push_back(), list_push_front(), and test().

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
	)

Inserts ELEM in the proper position in LIST, which must be sorted according to LESS given auxiliary data AUX.

Runs in O(n) average case in the number of elements in LIST.

Definition at line 446 of file list.c.

References ASSERT, list_begin(), list_end(), list_insert(), list_next(), and NULL.

Referenced by test().

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
	)

Returns the element in LIST with the largest value according to LESS given auxiliary data AUX.

Max and min.

If there is more than one maximum, returns the one that appears earlier in the list. If the list is empty, returns its tail.

Definition at line 493 of file list.c.

References list_begin(), list_end(), and list_next().

Referenced by test().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ list_min()

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

Returns the element in LIST with the smallest value according to LESS given auxiliary data AUX.

lib/kernel/list.h

If there is more than one minimum, returns the one that appears earlier in the list. If the list is empty, returns its tail.

Definition at line 512 of file list.c.

References list_begin(), list_end(), and list_next().

Referenced by test().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ list_next()

struct list_elem * list_next ( struct list_elem * elem )

Returns the element after ELEM in its list.

If ELEM is the last element in its list, returns the list tail. Results are undefined if ELEM is itself a list tail.

Definition at line 82 of file list.c.

References ASSERT, is_head(), is_interior(), and list_elem::next.

Referenced by block_get_by_name(), block_next(), find_elem(), find_end_of_run(), hash_apply(), hash_next(), inode_open(), inplace_merge(), is_sorted(), list_insert_ordered(), list_max(), list_min(), list_size(), list_unique(), rehash(), test(), thread_foreach(), and verify_list_fwd().

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 )

Removes the back element from LIST and returns it.

Undefined behavior if LIST is empty before removal.

Definition at line 270 of file list.c.

References list_back(), and list_remove().

Here is the call graph for this function:

◆ list_pop_front()

struct list_elem * list_pop_front ( struct list * list )

Removes the front element from LIST and returns it.

Undefined behavior if LIST is empty before removal.

Definition at line 260 of file list.c.

References list_front(), and list_remove().

Referenced by cond_signal(), hash_clear(), malloc(), next_thread_to_run(), and sema_up().

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 )

Returns the element before ELEM in its list.

If ELEM is the first element in its list, returns the list head. Results are undefined if ELEM is itself a list head.

Definition at line 113 of file list.c.

References ASSERT, is_interior(), is_tail(), and list_elem::prev.

Referenced by find_end_of_run(), inplace_merge(), is_sorted(), list_splice(), and verify_list_bkwd().

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
	)

Inserts ELEM at the end of LIST, so that it becomes the back in LIST.

Definition at line 217 of file list.c.

References list_end(), and list_insert().

Referenced by block_register(), cond_wait(), init_thread(), list_unique(), malloc(), sema_down(), test(), thread_unblock(), and thread_yield().

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
	)

Inserts ELEM at the beginning of LIST, so that it becomes the front in LIST.

Definition at line 209 of file list.c.

References list_begin(), and list_insert().

Referenced by free(), inode_open(), insert_elem(), and rehash().

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 )

Returns the LIST's reverse beginning, for iterating through LIST in reverse order, from back to front.

Definition at line 103 of file list.c.

References ASSERT, NULL, list_elem::prev, and list::tail.

Referenced by verify_list_bkwd().

Here is the caller graph for this function:

◆ list_remove()

struct list_elem * list_remove ( struct list_elem * elem )

Removes ELEM from its list and returns the element that followed it.

List removal.

Undefined behavior if ELEM is not in a list.

A list element must be treated very carefully after removing it from its list. Calling list_next() or list_prev() on ELEM will return the item that was previously before or after ELEM, but, e.g., list_prev(list_next(ELEM)) is no longer ELEM!

The list_remove() return value provides a convenient way to iterate and remove elements from a list:

for (e = list_begin (&list); e != list_end (&list); e = list_remove (e)) { ...do something with e... }

If you need to free() elements of the list then you need to be more conservative. Here's an alternate strategy that works even in that case:

while (!list_empty (&list)) { struct list_elem *e = list_pop_front (&list); ...do something with e... }

Definition at line 249 of file list.c.

References ASSERT, is_interior(), list_elem::next, and list_elem::prev.

Referenced by free(), inode_close(), list_pop_back(), list_pop_front(), list_unique(), rehash(), remove_elem(), and thread_exit().

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 )

Returns LIST's head.

list_rend() is often used in iterating through a list in reverse order, from back to front. Here's typical usage, following the example from the top of list.h:

for (e = list_rbegin (&foo_list); e != list_rend (&foo_list); e = list_prev (e)) { struct foo *f = list_entry (e, struct foo, elem); ...do something with f... }

Definition at line 133 of file list.c.

References ASSERT, list::head, and NULL.

Referenced by verify_list_bkwd().

Here is the caller graph for this function:

◆ list_reverse()

void list_reverse ( struct list * list )

Reverses the order of LIST.

Miscellaneous.

Definition at line 326 of file list.c.

References list::head, list_begin(), list_empty(), list_end(), list_elem::next, list_elem::prev, swap(), and list::tail.

Referenced by test().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ list_size()

size_t list_size ( struct list * list )

Returns the number of elements in LIST.

List properties.

Runs in O(n) in the number of elements.

Definition at line 298 of file list.c.

References list_begin(), list_end(), and list_next().

Here is the call graph for this function:

◆ list_sort()

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

Sorts LIST according to LESS given auxiliary data AUX, using a natural iterative merge sort that runs in O(n lg n) time and O(1) space in the number of elements in LIST.

Operations on lists with ordered elements.

< Number of runs output in current pass.

< Start of first run.

< End of first run, start of second.

< End of second run.

Definition at line 405 of file list.c.

References ASSERT, find_end_of_run(), inplace_merge(), is_sorted(), list_begin(), list_end(), and NULL.

Referenced by test().

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
	)

Removes elements FIRST though LAST (exclusive) from their current list, then inserts them just before BEFORE, which may be either an interior element or a tail.

Definition at line 184 of file list.c.

References ASSERT, is_interior(), is_tail(), list_prev(), list_elem::next, and list_elem::prev.

Referenced by inplace_merge().

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 )

Return's LIST's tail.

Definition at line 159 of file list.c.

References ASSERT, NULL, and list::tail.

◆ list_unique()

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

Iterates through LIST and removes all but the first in each set of adjacent elements that are equal according to LESS given auxiliary data AUX.

If DUPLICATES is non-null, then the elements from LIST are appended to DUPLICATES.

Definition at line 466 of file list.c.

References ASSERT, list_begin(), list_empty(), list_end(), list_next(), list_push_back(), list_remove(), next(), and NULL.

Referenced by test().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ swap()

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

static

Swaps the `struct list_elem *'s that A and B point to.

Definition at line 317 of file list.c.

Referenced by list_reverse().

Here is the caller graph for this function:

Functions

Function Documentation

◆ find_end_of_run()

◆ inplace_merge()

◆ is_head()

◆ is_interior()

◆ is_sorted()

◆ is_tail()

◆ list_back()

◆ list_begin()

◆ list_empty()

◆ list_end()

◆ list_front()

◆ list_head()

◆ list_init()

◆ list_insert()

◆ list_insert_ordered()

◆ list_max()

◆ list_min()

◆ list_next()

◆ list_pop_back()

◆ list_pop_front()

◆ list_prev()

◆ list_push_back()

◆ list_push_front()

◆ list_rbegin()

◆ list_remove()

◆ list_rend()

◆ list_reverse()

◆ list_size()

◆ list_sort()

◆ list_splice()

◆ list_tail()

◆ list_unique()

◆ swap()