A circular, doubly-linked list. More...

Collaboration diagram for libs.LinkedList:

Classes
struct	list_node_t
	A node in a linked list. More...

Macros
#define	as_linked_list list_node_t list_node
	Embed a list node into a struct.

#define	LIST_HEAD_INIT(container)

#define	LIST_NODE_INIT(container)

#define	list_entry(node, type)
	Get the container struct of a list node.

#define	list_prev_entry(item, type)
	Get the next element in a list.

#define	list_next_entry(item, type)
	Get the next element in a list.

#define	list_node_next_entry(node, type)
	Get the next list node.

#define	list_node(element)
	Get the ‘list_node’ of a list element. This is exactly the reverse of ‘list_entry’ above.

#define	list_prepend(element, item)

#define	list_append(element, item)

#define	list_insert_before(element, item)

#define	list_insert_after(element, item)

#define	list_remove(element)

#define	list_foreach(t, v, h)
	Iterate over a list.

#define	list_foreach_reverse(t, v, h)

#define	list_node_foreach(v, h)

#define	list_node_foreach_reverse(v, h)

#define	list_headless_foreach(t, v, h)

#define	list_headless_foreach_reverse(t, v, h)

Typedefs
typedef list_node_t	list_head
	A linked list head.

Functions
MOSAPI void	linked_list_init (list_node_t *head_node)
	Initialise a circular double linked list.

MOSAPI bool	list_is_empty (const list_node_t *head)

MOSAPI void	list_node_remove (list_node_t *link)

MOSAPI list_node_t *	list_node_pop (list_node_t *head)

MOSAPI void	list_node_prepend (list_node_t head, list_node_t item)

MOSAPI void	list_node_append (list_node_t head, list_node_t item)

MOSAPI void	list_node_insert_before (list_node_t element, list_node_t item)

MOSAPI void	list_node_insert_after (list_node_t element, list_node_t item)

Detailed Description

A circular, doubly-linked list.

Macro Definition Documentation

◆ as_linked_list

#define as_linked_list list_node_t list_node

Embed a list node into a struct.

Definition at line 35 of file list.h.

◆ LIST_HEAD_INIT

#define LIST_HEAD_INIT ( container )

Value:

{ .prev = &(container), .next = &(container) }

Definition at line 38 of file list.h.

Referenced by MOS_TEST_CASE(), MOS_TEST_CASE(), MOS_TEST_CASE(), MOS_TEST_CASE(), MOS_TEST_CASE(), MOS_TEST_CASE(), MOS_TEST_CASE(), and MOS_TEST_CASE().

◆ LIST_NODE_INIT

#define LIST_NODE_INIT ( container )

Value:

LIST_HEAD_INIT(container.list_node)

LIST_HEAD_INIT

#define LIST_HEAD_INIT(container)

Definition list.h:38

Definition at line 41 of file list.h.

Referenced by MOS_TEST_CASE(), MOS_TEST_CASE(), MOS_TEST_CASE(), MOS_TEST_CASE(), MOS_TEST_CASE(), MOS_TEST_CASE(), MOS_TEST_CASE(), MOS_TEST_CASE(), MOS_TEST_CASE(), and timer_msleep().

◆ list_entry

#define list_entry	(		node,
			type )

Value:

container_of((node), type, list_node)

container_of

#define container_of(ptr, type, member)

Definition mos_global.h:50

list_node

A node in a linked list.

Definition list.h:27

Get the container struct of a list node.

Definition at line 46 of file list.h.

Referenced by break_the_order(), buddy_alloc_n_exact(), MOS_TEST_CASE(), naive_sched_select_next(), and waitlist_wake().

◆ list_prev_entry

#define list_prev_entry	(		item,
			type )

Value:

list_entry(list_node(item)->prev, type)

list_node

#define list_node(element)

Get the ‘list_node’ of a list element. This is exactly the reverse of ‘list_entry’ above.

Definition list.h:68

list_entry

#define list_entry(node, type)

Get the container struct of a list node.

Definition list.h:46

Get the next element in a list.

Definition at line 51 of file list.h.

◆ list_next_entry

#define list_next_entry	(		item,
			type )

Value:

list_entry(list_node(item)->next, type)

Get the next element in a list.

Definition at line 56 of file list.h.

Referenced by MOS_TEST_CASE().

◆ list_node_next_entry

#define list_node_next_entry	(		node,
			type )

Value:

container_of((node)->next, type, list_node)

Get the next list node.

Definition at line 62 of file list.h.

Referenced by ipc_server_accept().

◆ list_node

#define list_node ( element )

Value:

(&((element)->list_node))

Get the ‘list_node’ of a list element. This is exactly the reverse of ‘list_entry’ above.

Definition at line 68 of file list.h.

Referenced by add_to_freelist(), break_the_order(), break_this_pfn(), buddy_free_n(), clocksource_register(), console_register(), dentry_mount(), dentry_unmount(), dirter_add(), do_attach_vmap(), futex_wait(), ipc_connect_to_server(), ipc_server_create(), MOS_TEST_CASE(), naive_sched_add_thread(), pmm_free_frames(), populate_freelist(), power_register_shutdown_callback(), process_do_fork(), process_exit(), serial_console_setup(), signal_send_to_thread(), slab_init_one(), sysfs_register(), sysfs_register_file(), thread_allocate(), timer_msleep(), try_merge(), userfs_manager_register_filesystem(), vfs_register_filesystem(), vmap_create(), and vmap_split().

◆ list_prepend

#define list_prepend	(		element,
			item )

Value:

list_node_prepend(list_node(element), list_node(item))

list_node_prepend

MOSAPI void list_node_prepend(list_node_t *head, list_node_t *item)

Definition list.c:63

Definition at line 70 of file list.h.

◆ list_append

#define list_append	(		element,
			item )

Value:

list_node_append(list_node(element), list_node(item))

list_node_append

MOSAPI void list_node_append(list_node_t *head, list_node_t *item)

Definition list.c:68

Definition at line 71 of file list.h.

Referenced by MOS_TEST_CASE().

◆ list_insert_before

#define list_insert_before	(		element,
			item )

Value:

list_node_insert_before(list_node(element), list_node(item))

list_node_insert_before

MOSAPI void list_node_insert_before(list_node_t *element, list_node_t *item)

Definition list.c:74

Definition at line 72 of file list.h.

Referenced by do_attach_vmap().

◆ list_insert_after

#define list_insert_after	(		element,
			item )

Value:

list_node_insert_after(list_node(element), list_node(item))

list_node_insert_after

MOSAPI void list_node_insert_after(list_node_t *element, list_node_t *item)

Definition list.c:79

Definition at line 73 of file list.h.

◆ list_remove

#define list_remove ( element )

Value:

list_node_remove(list_node(element))

list_node_remove

MOSAPI void list_node_remove(list_node_t *link)

Definition list.c:26

Definition at line 74 of file list.h.

Referenced by break_the_order(), break_this_pfn(), dentry_try_release(), extract_exact_range(), ipc_server_accept(), ipc_server_close(), naive_sched_remove_thread(), naive_sched_select_next(), power_shutdown(), process_exit(), process_wait_for_pid(), signal_get_next_pending(), timer_msleep(), timer_tick(), try_merge(), vfs_io_ops_close_dir(), vmap_destroy(), and waitlist_remove_me().

◆ list_foreach

#define list_foreach	(	t,
		v,
		h )

Value:

for (__typeof(list_entry(&(h), t)) v = list_entry((h).next, t), __next = list_next_entry(v, t); list_node(v) != &(h); v = __next, __next = list_next_entry(v, t))

list_next_entry

#define list_next_entry(item, type)

Get the next element in a list.

Definition list.h:56

Iterate over a list.

Parameters

t	Type of the list elements (e.g. ‘struct foo’)
v	Name of the variable to use for the current element (e.g. ‘item’)
h	List Head (e.g. ‘consoles’)

Definition at line 83 of file list.h.

Referenced by console_get(), console_get_by_prefix(), console_putc(), do_attach_vmap(), dump_list(), extract_exact_range(), futex_wait(), futex_wake(), interrupt_entry(), ipc_connect_to_server(), ipc_dump_name_waitlist(), ipc_get_server(), ipc_server_close(), ipc_server_create(), ipc_sysfs_list_ipcs(), ipc_sysfs_lookup_ipc(), ipc_sysfs_servers(), lvprintk(), mm_get_free_vaddr_locked(), mm_get_is_mapped_locked(), mmstat_sysfs_vmaps_show(), MOS_TEST_CASE(), MOS_TEST_CASE(), naive_sched_remove_thread(), power_shutdown(), process_destroy(), process_do_execveat(), process_do_fork(), process_dump_mmaps(), process_exit(), process_sysfs_process_stat(), process_sysfs_vmap_stat(), process_wait_for_pid(), signal_get_next_pending(), signal_has_pending(), signal_send_to_process(), signal_send_to_thread(), slab_sysfs_slabinfo(), timer_tick(), vfs_find_filesystem(), vfs_io_ops_close_dir(), vfs_list_dir(), vfs_sysfs_filesystems(), vfs_sysfs_mountpoints(), vmap_obtain(), and waitlist_remove_me().

◆ list_foreach_reverse

#define list_foreach_reverse	(	t,
		v,
		h )

Value:

for (__typeof(list_entry(&(h), t)) v = list_entry((h).prev, t), __next = list_prev_entry(v, t); list_node(v) != &(h); v = __next, __next = list_prev_entry(v, t))

list_prev_entry

#define list_prev_entry(item, type)

Get the next element in a list.

Definition list.h:51

Definition at line 86 of file list.h.

◆ list_node_foreach

#define list_node_foreach	(		v,
			h )

Value:

for (list_node_t *v = (h)->next, *__next = v->next; v != (h); v = __next, __next = v->next)

Definition at line 89 of file list.h.

Referenced by sysfs_iops_create(), sysfs_iops_iterate_dir(), and sysfs_iops_lookup().

◆ list_node_foreach_reverse

#define list_node_foreach_reverse	(		v,
			h )

Value:

for (list_node_t *v = (h)->prev, *__next = v->prev; v != (h); v = __next, __next = v->prev)

Definition at line 90 of file list.h.

◆ list_headless_foreach

#define list_headless_foreach	(	t,
		v,
		h )

Value:

for (__typeof(&(h)) v = &(h), __next = list_next_entry(v, t), __head = NULL; (v) != __head; \

v = __next, __next = list_next_entry(v, t), __head = __head == NULL ? &(h) : __head)

NULL

#define NULL

Definition pb_syshdr.h:46

Definition at line 92 of file list.h.

Referenced by MOS_TEST_CASE().

◆ list_headless_foreach_reverse

#define list_headless_foreach_reverse	(	t,
		v,
		h )

Value:

for (__typeof(h) v = (h), __next = list_prev_entry(v, t), __head = NULL; (v) != __head; \

v = __next, __next = list_prev_entry(v, t), __head = __head == NULL ? (h) : __head)

Definition at line 96 of file list.h.

Referenced by MOS_TEST_CASE().

Typedef Documentation

◆ list_head

typedef list_node_t list_head

A linked list head.

Note: The list head should be placed in the heap, not on the stack. This is because the list head is a circular list, and the ‘prev’ and ‘next’ pointers of the list head point to itself.

Definition at line 23 of file list.h.

Function Documentation

◆ linked_list_init()

MOSAPI void linked_list_init ( list_node_t * node )

Initialise a circular double linked list.

Postcondition: head_node->next == head_node; head_node->prev == head_node

Parameters

node	The list head node (and thus, the only element in the newly created list)

Definition at line 15 of file list.c.

Referenced by break_the_order(), break_this_pfn(), buddy_init(), dentry_mount(), dirter_add(), ipc_connect_to_server(), ipc_server_create(), mm_create_context(), mos_start_kernel(), naive_sched_add_thread(), naive_sched_init(), pmm_free_frames(), populate_freelist(), power_register_shutdown_callback(), process_allocate(), process_do_fork(), process_exit(), serial_console_setup(), signal_send_to_thread(), slab_init_one(), sysfs_register(), sysfs_register_file(), thread_allocate(), tree_add_child(), tree_node_init(), try_merge(), userfs_manager_register_filesystem(), vfs_list_dir(), vmap_create(), vmap_split(), and waitlist_init().

◆ list_is_empty()

MOSAPI bool list_is_empty ( const list_node_t * head )

◆ list_node_remove()

MOSAPI void list_node_remove ( list_node_t * link )

Definition at line 26 of file list.c.

Referenced by dentry_unmount(), list_node_pop(), MOS_TEST_CASE(), and MOS_TEST_CASE().