#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) |
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().
Definition at line 297 of file list.c.
References ASSERT, list_empty(), list_elem::prev, and list::tail.
Referenced by list_pop_back().
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().
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().
Definition at line 288 of file list.c.
References ASSERT, list::head, list_empty(), and list_elem::next.
Referenced by list_pop_front().
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().
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().
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().
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().
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().
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().
Definition at line 209 of file list.c.
References list_begin(), and list_insert().
Referenced by free(), inode_open(), insert_elem(), and rehash().
Definition at line 103 of file list.c.
References ASSERT, NULL, list_elem::prev, and list::tail.
Referenced by verify_list_bkwd().
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().
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().
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().
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().
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().