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.

Data Structures
struct	list_elem
	Doubly linked list. More...
struct	list
	List. More...

Macros
#define	list_entry(LIST_ELEM, STRUCT, MEMBER)
	Converts pointer to list element LIST_ELEM into a pointer to the structure that LIST_ELEM is embedded inside. More...
#define	LIST_INITIALIZER(NAME)
	List initialization. More...

Typedefs
typedef bool	list_less_func(const struct list_elem *a, const struct list_elem *b, void *aux)
	Compares the value of two list elements A and B, given auxiliary data AUX. More...

Functions
void	list_init (struct list *)
	Initializes LIST as an empty list. More...
struct list_elem *	list_begin (struct list *)
	List traversal. More...
struct list_elem *	list_next (struct list_elem *)
	Returns the element after ELEM in its list. More...
struct list_elem *	list_end (struct list *)
	Returns LIST's tail. More...
struct list_elem *	list_rbegin (struct 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 *)
	Returns the element before ELEM in its list. More...
struct list_elem *	list_rend (struct list *)
	Returns LIST's head. More...
struct list_elem *	list_head (struct list *)
	Return's LIST's head. More...
struct list_elem *	list_tail (struct list *)
	Return's LIST's tail. More...
void	list_insert (struct list_elem *, struct list_elem *)
	List insertion. 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 *, struct list_elem *)
	Inserts ELEM at the beginning of LIST, so that it becomes the front in LIST. More...
void	list_push_back (struct list *, struct list_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 *)
	List removal. More...
struct list_elem *	list_pop_front (struct list *)
	Removes the front element from LIST and returns it. More...
struct list_elem *	list_pop_back (struct list *)
	Removes the back element from LIST and returns it. More...
struct list_elem *	list_front (struct list *)
	List elements. More...
struct list_elem *	list_back (struct list *)
	Returns the back element in LIST. More...
size_t	list_size (struct list *)
	List properties. More...
bool	list_empty (struct list *)
	Returns true if LIST is empty, false otherwise. More...
void	list_reverse (struct list *)
	Miscellaneous. More...
void	list_sort (struct list *, list_less_func *, void *aux)
	Operations on lists with ordered elements. More...
void	list_insert_ordered (struct list *, struct list_elem *, list_less_func *, 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 *, struct list *duplicates, list_less_func *, 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_less_func *, void *aux)
	Max and min. More...
struct list_elem *	list_min (struct list *, list_less_func *, void *aux)
	lib/kernel/list.h More...

Macro Definition Documentation

list_entry

#define list_entry	(		LIST_ELEM,
			STRUCT,
			MEMBER
	)

Value:

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

Converts pointer to list element LIST_ELEM into a pointer to the structure that LIST_ELEM is embedded inside.

Supply the name of the outer structure STRUCT and the member name MEMBER of the list element. See the big comment at the top of the file for an example.

Definition at line 108 of file list.h.

LIST_INITIALIZER

#define LIST_INITIALIZER

(

NAME

)

Value:

                                 { { NULL, &(NAME).tail }, \
                                 { &(NAME).head, NULL } }

List initialization.

A list may be initialized by calling list_init():

struct list my_list;
list_init (&my_list);

or with an initializer using LIST_INITIALIZER:

struct list my_list = LIST_INITIALIZER (my_list); 

Definition at line 122 of file list.h.

Typedef Documentation

list_less_func

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

Compares the value of two list elements A and B, given auxiliary data AUX.

Returns true if A is less than B, or false if A is greater than or equal to B.

Definition at line 165 of file list.h.

Function Documentation

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

)

List traversal.

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

)

List elements.

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
	)

List insertion.

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
	)

Max and min.

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
	)

lib/kernel/list.h

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

)

List removal.

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

)

Miscellaneous.

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

)

List properties.

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
	)

Operations on lists with ordered elements.

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: