PKUOS - Pintos
Pintos source browser for PKU Operating System course
Data Structures | Macros | Typedefs | Functions
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_elemlist_begin (struct list *)
 List traversal. More...
 
struct list_elemlist_next (struct list_elem *)
 Returns the element after ELEM in its list. More...
 
struct list_elemlist_end (struct list *)
 Returns LIST's tail. More...
 
struct list_elemlist_rbegin (struct list *)
 Returns the LIST's reverse beginning, for iterating through LIST in reverse order, from back to front. More...
 
struct list_elemlist_prev (struct list_elem *)
 Returns the element before ELEM in its list. More...
 
struct list_elemlist_rend (struct list *)
 Returns LIST's head. More...
 
struct list_elemlist_head (struct list *)
 Return's LIST's head. More...
 
struct list_elemlist_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_elemlist_remove (struct list_elem *)
 List removal. More...
 
struct list_elemlist_pop_front (struct list *)
 Removes the front element from LIST and returns it. More...
 
struct list_elemlist_pop_back (struct list *)
 Removes the back element from LIST and returns it. More...
 
struct list_elemlist_front (struct list *)
 List elements. More...
 
struct list_elemlist_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_elemlist_max (struct list *, list_less_func *, void *aux)
 Max and min. More...
 
struct list_elemlist_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)))
static int next(int pos)
Returns the position after POS within an intq.
Definition: intq.c:79
#define offsetof(TYPE, MEMBER)
Definition: stddef.h:5
unsigned char uint8_t
Definition: stdint.h:20

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 } }
#define NULL
Definition: stddef.h:4

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_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: