pintos/src/lib/kernel/list.h File Reference

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

Go to the source code of this file.

Data Structures

struct list_elem

struct list

Defines

#define list_entry(LIST_ELEM, STRUCT, MEMBER)

#define LIST_INITIALIZER(NAME)

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)

Define Documentation

#define list_entry	(	LIST_ELEM,
		STRUCT,
		MEMBER	)

Value:

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

Definition at line 108 of file list.h.

Referenced by block_get_by_name(), cond_signal(), dump_all_qh(), inode_open(), list_elem_to_block(), malloc(), msc_attached(), next_thread_to_run(), pci_get_dev_by_class(), pci_get_device(), pci_interrupt(), pci_io_enum(), pci_print_stats(), sema_up(), test(), thread_foreach(), uhci_destroy_chan(), uhci_process_completed(), uhci_remove_stalled(), usb_apply_class_to_interfaces(), usb_attach_interfaces(), usb_get_class_by_id(), value_less(), verify_list_bkwd(), and verify_list_fwd().

#define LIST_INITIALIZER ( NAME )

Value:

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

Definition at line 122 of file list.h.

Typedef Documentation

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

Definition at line 165 of file list.h.

Function Documentation

struct list_elem* list_back ( struct list * ) [read]

Definition at line 297 of file list.c.

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

Referenced by list_pop_back().

struct list_elem* list_begin ( struct list * ) [read]

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(), dump_all_qh(), 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(), msc_attached(), pci_get_dev_by_class(), pci_get_device(), pci_interrupt(), pci_io_enum(), pci_print_stats(), rehash(), test(), thread_foreach(), uhci_destroy_chan(), uhci_process_completed(), uhci_remove_stalled(), usb_apply_class_to_interfaces(), usb_attach_interfaces(), usb_get_class_by_id(), and verify_list_fwd().

bool list_empty ( struct list * )

Definition at line 318 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().

struct list_elem* list_end ( struct list * ) [read]

Definition at line 94 of file list.c.

References ASSERT, NULL, and list::tail.

Referenced by block_get_by_name(), dump_all_qh(), 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(), msc_attached(), pci_get_dev_by_class(), pci_get_device(), pci_interrupt(), pci_io_enum(), pci_print_stats(), rehash(), test(), thread_foreach(), uhci_destroy_chan(), uhci_process_completed(), uhci_remove_stalled(), usb_apply_class_to_interfaces(), usb_attach_interfaces(), usb_get_class_by_id(), and verify_list_fwd().

struct list_elem* list_front ( struct list * ) [read]

Definition at line 288 of file list.c.

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

Referenced by list_pop_front().

struct list_elem* list_head ( struct list * ) [read]

Definition at line 151 of file list.c.

References ASSERT, list::head, and NULL.

Referenced by hash_first().

void list_init ( struct 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(), is_thread(), malloc_init(), pci_init(), pci_probe(), rehash(), sema_init(), test(), uhci_create_info(), usb_configure_default(), usb_init(), usb_load_config(), usb_register_class(), usb_register_host(), and usb_storage_init().

void list_insert	(	struct list_elem *	,
		struct list_elem *
	)

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().

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

Definition at line 454 of file list.c.

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

Referenced by test().

struct list_elem* list_max	(	struct list *	,
		list_less_func *	,
		void *	aux
	)			`[read]`

Definition at line 501 of file list.c.

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

Referenced by test().

struct list_elem* list_min	(	struct list *	,
		list_less_func *	,
		void *	aux
	)			`[read]`

Definition at line 520 of file list.c.

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

Referenced by test().

struct list_elem* list_next ( struct list_elem * ) [read]

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(), dump_all_qh(), 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(), msc_attached(), pci_get_dev_by_class(), pci_get_device(), pci_interrupt(), pci_io_enum(), pci_print_stats(), rehash(), test(), thread_foreach(), uhci_destroy_chan(), uhci_process_completed(), uhci_remove_stalled(), usb_apply_class_to_interfaces(), usb_attach_interfaces(), usb_get_class_by_id(), and verify_list_fwd().

struct list_elem* list_pop_back ( struct list * ) [read]

Definition at line 278 of file list.c.

References list_back(), and list_remove().

struct list_elem* list_pop_front ( struct list * ) [read]

Definition at line 268 of file list.c.

References list_front(), and list_remove().

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

struct list_elem* list_prev ( struct list_elem * ) [read]

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().

void list_push_back	(	struct list *	,
		struct list_elem *
	)

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(), msc_attached(), pci_probe(), pci_register_irq(), pci_setup_io(), sema_down(), test(), thread_unblock(), thread_yield(), uhci_create_chan(), uhci_tx_pkt_wait(), usb_apply_class_to_interfaces(), usb_attach_interfaces(), usb_load_config(), usb_register_class(), usb_register_host(), and usb_scan_devices().

void list_push_front	(	struct list *	,
		struct list_elem *
	)

Definition at line 209 of file list.c.

References list_begin(), and list_insert().

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

struct list_elem* list_rbegin ( struct list * ) [read]

Definition at line 103 of file list.c.

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

Referenced by verify_list_bkwd().

struct list_elem* list_remove ( struct list_elem * ) [read]

Definition at line 257 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(), pci_unregister_irq(), rehash(), remove_elem(), thread_exit(), uhci_destroy_chan(), uhci_process_completed(), and uhci_remove_stalled().

struct list_elem* list_rend ( struct list * ) [read]

Definition at line 133 of file list.c.

References ASSERT, list::head, and NULL.

Referenced by verify_list_bkwd().

void list_reverse ( struct list * )

Definition at line 334 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().

size_t list_size ( struct list * )

Definition at line 306 of file list.c.

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

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

Definition at line 413 of file list.c.

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

Referenced by test().

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

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().

struct list_elem* list_tail ( struct list * ) [read]

Definition at line 159 of file list.c.

References ASSERT, NULL, and list::tail.

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

Definition at line 474 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().


Data Structures
struct	list_elem
struct	list
Defines
#define	list_entry(LIST_ELEM, STRUCT, MEMBER)
#define	LIST_INITIALIZER(NAME)
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)