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

#include "list.h"
#include "../debug.h"

Go to the source code of this file.

Functions

static bool is_sorted (struct list_elem *a, struct list_elem *b, list_less_func *less, void *aux) UNUSED

static bool is_head (struct list_elem *elem)

static bool is_interior (struct list_elem *elem)

static bool is_tail (struct list_elem *elem)

void list_init (struct list *list)

struct list_elem * list_begin (struct list *list)

struct list_elem * list_next (struct list_elem *elem)

struct list_elem * list_end (struct list *list)

struct list_elem * list_rbegin (struct list *list)

struct list_elem * list_prev (struct list_elem *elem)

struct list_elem * list_rend (struct list *list)

struct list_elem * list_head (struct list *list)

struct list_elem * list_tail (struct list *list)

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

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

void list_push_front (struct list *list, struct list_elem *elem)

void list_push_back (struct list *list, struct list_elem *elem)

struct list_elem * list_remove (struct list_elem *elem)

struct list_elem * list_pop_front (struct list *list)

struct list_elem * list_pop_back (struct list *list)

struct list_elem * list_front (struct list *list)

struct list_elem * list_back (struct list *list)

size_t list_size (struct list *list)

bool list_empty (struct list *list)

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

void list_reverse (struct list *list)

static struct list_elem * find_end_of_run (struct list_elem *a, struct list_elem *b, list_less_func *less, void *aux)

static void inplace_merge (struct list_elem *a0, struct list_elem *a1b0, struct list_elem *b1, list_less_func *less, void *aux)

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

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

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

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

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

Function Documentation

static struct list_elem* find_end_of_run	(	struct list_elem *	a,
		struct list_elem *	b,
		list_less_func *	less,
		void *	aux
	)			`[static, read]`

Definition at line 366 of file list.c.

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

Referenced by list_sort().

static void inplace_merge	(	struct list_elem *	a0,
		struct list_elem *	a1b0,
		struct list_elem *	b1,
		list_less_func *	less,
		void *	aux
	)			`[static]`

Definition at line 388 of file list.c.

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

Referenced by list_sort().

static bool is_head ( struct list_elem * elem ) [inline, static]

Definition at line 39 of file list.c.

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

Referenced by list_next().

static bool is_interior ( struct list_elem * elem ) [inline, static]

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

static bool is_sorted	(	struct list_elem *	a,
		struct list_elem *	b,
		list_less_func *	less,
		void *	aux
	)			`[static]`

Definition at line 350 of file list.c.

References list_next(), and list_prev().

Referenced by inplace_merge(), list_sort(), and qsort_bytes().

static bool is_tail ( struct list_elem * elem ) [inline, static]

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

struct list_elem* list_back ( struct list * 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 * 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 * 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 * 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 * 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 * 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 * 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 *	before,
		struct list_elem *	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 *	list,
		struct list_elem *	elem,
		list_less_func *	less,
		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,
		list_less_func *	less,
		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,
		list_less_func *	less,
		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 * 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 * list ) [read]

Definition at line 278 of file list.c.

References list_back(), and list_remove().

struct list_elem* list_pop_front ( struct list * 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 * 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 *	list,
		struct list_elem *	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 *	list,
		struct list_elem *	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 * 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 * 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 * 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 * 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 * list )

Definition at line 306 of file list.c.

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

void list_sort	(	struct list *	list,
		list_less_func *	less,
		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 * list ) [read]

Definition at line 159 of file list.c.

References ASSERT, NULL, and list::tail.

void list_unique	(	struct list *	list,
		struct list *	duplicates,
		list_less_func *	less,
		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().

static void swap	(	struct list_elem **	a,
		struct list_elem **	b
	)			`[static]`

Definition at line 325 of file list.c.

Referenced by list_reverse(), partition(), and shuffle().

Generated on Mon Jan 10 16:43:58 2011 for Pintos by

doxygen

1.5.6