Doubly linked list

Doubly linked list header. More...

Data Structures
struct	list_entry_t
	A entry in a doubly linked list. More...
struct	list_t
	A doubly linked list. More...

Macros
#define	LIST_FOR_EACH(elem, list, member)
	Iterates over a list.
#define	LIST_FOR_EACH_SAFE(elem, temp, list, member)
	Safely iterates over a list, allowing for element removal during iteration.
#define	LIST_FOR_EACH_REVERSE(elem, list, member)
	Iterates over a list in reverse.
#define	LIST_FOR_EACH_FROM(elem, start, list, member)
	Iterates over a list starting from a specific element.
#define	LIST_FOR_EACH_FROM_REVERSE(elem, start, list, member)
	Iterates over a list in reverse order starting from a specific element.
#define	LIST_FOR_EACH_TO(elem, end, list, member)
	Iterates over a list up to a specific element.
#define	LIST_FOR_EACH_TO_REVERSE(elem, end, list, member)
	Iterates over a list in reverse order up to a specific element.
#define	LIST_ENTRY_CREATE(name)
	Creates a list entry initializer.
#define	LIST_CREATE(name)   (list_t){.head = {.prev = &(name).head, .next = &(name).head, .list = &(name)}, .length = 0}
	Creates a list initializer.

Typedefs
typedef struct list	list_t

Functions
static void	list_entry_init (list_entry_t *entry)
	Initializes a list entry.
static void	list_init (list_t *list)
	Initializes a list.
static bool	list_contains_entry (list_t *list, list_entry_t *entry)
	Check if an entry belongs to a specific list.
static bool	list_is_empty (list_t *list)
	Checks if a list is empty.
static uint64_t	list_length (list_t *list)
	Gets the length of the list.
static void	list_add (list_t *list, list_entry_t *prev, list_entry_t *next, list_entry_t *entry)
	Adds a new element between two existing list entries.
static void	list_append (list_t *list, list_entry_t *prev, list_entry_t *entry)
	Appends an entry to the list.
static void	list_prepend (list_t *list, list_entry_t *head, list_entry_t *entry)
	Prepends an entry to the list.
static void	list_remove (list_t *list, list_entry_t *entry)
	Removes a list entry from its current list.
static void	list_push (list_t *list, list_entry_t *entry)
	Pushes an entry to the end of the list.
static list_entry_t *	list_pop (list_t *list)
	Pops the first entry from the list.
static list_entry_t *	list_first (list_t *list)
	Gets the first entry in the list without removing it.
static list_entry_t *	list_last (list_t *list)
	Gets the last entry in the list without removing it.

Detailed Description

Doubly linked list header.

The sys/list.h header implements a doubly linked list inspired by the linked list implementation used in the Linux kernel, where the linked list entry structure is stored within each entry instead of each entry having a pointer to each stucture, the structure itself can then be accessed by using CONTAINER_OF.

It might seem a bit unusual to include something as significant as a doubly linked list in the C standard library, but it is something used to often that having to implemented it for every single program in the OS is massively redundant.

Macro Definition Documentation

LIST_CREATE

#define LIST_CREATE

(

name

)

(list_t){.head = {.prev = &(name).head, .next = &(name).head, .list = &(name)}, .length = 0}

Creates a list initializer.

Parameters

name	The name of the list variable to initialize.

Returns

A list_t initializer for the specified list variable.

Definition at line 176 of file list.h.

LIST_ENTRY_CREATE

#define LIST_ENTRY_CREATE

(

name

)

Value:

    (list_entry_t) \
    { \
        .prev = &(name), .next = &(name), .list = NULL \
    }

Creates a list entry initializer.

Parameters

name	The name of the entry variable to initialize.

Returns

A list_entry_t initializer for the specified entry variable.

Definition at line 164 of file list.h.

LIST_FOR_EACH

#define LIST_FOR_EACH	(		elem,
			list,
			member
	)

Value:

    for ((elem) = CONTAINER_OF((list)->head.next, typeof(*elem), member); &(elem)->member != &((list)->head); \
        (elem) = CONTAINER_OF((elem)->member.next, typeof(*elem), member))

Iterates over a list.

Parameters

elem	The loop variable, a pointer to the structure containing the list entry.
list	A pointer to the list_t structure to iterate over.
member	The name of the list_entry_t member within the structure elem.

Definition at line 65 of file list.h.

LIST_FOR_EACH_FROM

#define LIST_FOR_EACH_FROM	(		elem,
			start,
			list,
			member
	)

Value:

    for ((elem) = CONTAINER_OF(start, typeof(*elem), member); &(elem)->member != &((list)->head); \
        (elem) = CONTAINER_OF((elem)->member.next, typeof(*elem), member))

Iterates over a list starting from a specific element.

The LIST_FOR_EACH_FROM() macro iterates from a specific element, inclusive, until the end of the list.

Parameters

elem	The loop variable, a pointer to the structure containing the list entry.
start	A pointer to the list_entry_t from which to start iteration.
list	A pointer to the list_t structure to iterate over.
member	The name of the list_entry_t member within the structure elem.

Definition at line 110 of file list.h.

LIST_FOR_EACH_FROM_REVERSE

#define LIST_FOR_EACH_FROM_REVERSE	(		elem,
			start,
			list,
			member
	)

Value:

    for ((elem) = CONTAINER_OF(start, typeof(*elem), member); &(elem)->member != &((list)->head); \
        (elem) = CONTAINER_OF((elem)->member.prev, typeof(*elem), member))

Iterates over a list in reverse order starting from a specific element.

Parameters

elem	The loop variable, a pointer to the structure containing the list entry.
start	A pointer to the list_entry_t from which to start reverse iteration.
list	A pointer to the list_t structure to iterate over.
member	The name of the list_entry_t member within the structure elem.

Definition at line 123 of file list.h.

LIST_FOR_EACH_REVERSE

#define LIST_FOR_EACH_REVERSE	(		elem,
			list,
			member
	)

Value:

    for ((elem) = CONTAINER_OF((list)->head.prev, typeof(*elem), member); &(elem)->member != &((list)->head); \
        (elem) = CONTAINER_OF((elem)->member.prev, typeof(*elem), member))

Iterates over a list in reverse.

Parameters

elem	The loop variable, a pointer to the structure containing the list entry.
list	A pointer to the list_t structure to iterate over.
member	The name of the list_entry_t member within the structure elem.

Definition at line 95 of file list.h.

LIST_FOR_EACH_SAFE

#define LIST_FOR_EACH_SAFE	(		elem,
			temp,
			list,
			member
	)

Value:

    for ((elem) = CONTAINER_OF((list)->head.next, typeof(*elem), member), \
        (temp) = CONTAINER_OF((elem)->member.next, typeof(*elem), member); \
        &(elem)->member != &((list)->head); \
        (elem) = (temp), (temp) = CONTAINER_OF((elem)->member.next, typeof(*elem), member))

Safely iterates over a list, allowing for element removal during iteration.

The LIST_FOR_EACH_SAFE() macro is similar to LIST_FOR_EACH() but uses a temporary variable to store the next element, making it safe to remove the current element during iteration.

Parameters

elem	The loop variable, a pointer to the structure containing the list entry.
temp	A temporary loop variable, a pointer to the structure containing the next list entry.
list	A pointer to the list_t structure to iterate over.
member	The name of the list_entry_t member within the structure elem.

Definition at line 81 of file list.h.

LIST_FOR_EACH_TO

#define LIST_FOR_EACH_TO	(		elem,
			end,
			list,
			member
	)

Value:

    for ((elem) = CONTAINER_OF((list)->head.next, typeof(*elem), member); \
        &(elem)->member != &((list)->head) && &(elem)->member != (end); \
        (elem) = CONTAINER_OF((elem)->member.next, typeof(*elem), member))

Iterates over a list up to a specific element.

The LIST_FOR_EACH_TO() macro iterates from the start of the list, inclusive, until a specified element, not inclusive.

Parameters

elem	The loop variable, a pointer to the structure containing the list entry.
end	A pointer to the list_entry_t at which to stop iteration (exclusive).
list	A pointer to the list_t structure to iterate over.
member	The name of the list_entry_t member within the structure elem.

Definition at line 139 of file list.h.

LIST_FOR_EACH_TO_REVERSE

#define LIST_FOR_EACH_TO_REVERSE	(		elem,
			end,
			list,
			member
	)

Value:

    for ((elem) = CONTAINER_OF((list)->head.prev, typeof(*elem), member); \
        &(elem)->member != &((list)->head) && &(elem)->member != (end); \
        (elem) = CONTAINER_OF((elem)->member.prev, typeof(*elem), member))

Iterates over a list in reverse order up to a specific element.

Parameters

elem	The loop variable, a pointer to the structure containing the list entry.
end	A pointer to the list_entry_t at which to stop reverse iteration (exclusive).
list	A pointer to the list_t structure to iterate over.
member	The name of the list_entry_t member within the structure elem.

Definition at line 153 of file list.h.

Typedef Documentation

list_t

typedef struct list list_t

Definition at line 27 of file list.h.

Function Documentation

list_add()

static void list_add ( list_t *  list, list_entry_t *  prev, list_entry_t *  next, list_entry_t *  entry  )

inlinestatic

Adds a new element between two existing list entries.

Parameters

list	A pointer to the list_t that will contain the new element.
prev	A pointer to the list entry that will precede the new element.
next	A pointer to the list entry that will follow the new element.
elem	A pointer to the list_entry_t to add.

Definition at line 263 of file list.h.

References assert, list_t::length, list_entry_t::list, list_entry_t::next, next, NULL, and list_entry_t::prev.

Referenced by list_append(), list_prepend(), and list_push().

list_append()

static void list_append ( list_t *  list, list_entry_t *  prev, list_entry_t *  entry  )

inlinestatic

Appends an entry to the list.

Parameters

list	A pointer to the list_t to append to.
prev	A pointer to the list entry after which the new entry will be appended.
entry	A pointer to the list_entry_t to append.

Definition at line 292 of file list.h.

References list_add(), and list_entry_t::next.

Referenced by _heap_block_new(), and _heap_block_split().

list_contains_entry()

static bool list_contains_entry ( list_t *  list, list_entry_t *  entry  )

inlinestatic

Check if an entry belongs to a specific list.

Parameters

list	A pointer to the list_t to search in.
entry	A pointer to the list_entry_t to search for.

Returns

true if the entry is in the list, false otherwise.

Definition at line 214 of file list.h.

References assert, list_entry_t::list, and NULL.

list_entry_init()

static void list_entry_init ( list_entry_t *  entry )

inlinestatic

Initializes a list entry.

Parameters

entry

A pointer to the list_entry_t to initialize.

Definition at line 184 of file list.h.

References assert, list_entry_t::list, list_entry_t::next, NULL, and list_entry_t::prev.

Referenced by _file_new(), _heap_alloc(), _heap_block_new(), _heap_block_split(), _std_stream_init(), _thread_init(), aml_mutex_stack_push(), aml_object_new(), aml_patch_up_add_unresolved(), client_new(), config_open(), dentry_new(), disk_load_dir(), element_new_raw(), font_new(), image_new_blank(), key_share(), list_init(), list_remove(), local_conn_new(), panic_symbols_init(), process_init(), ram_disk_load_file(), socket_family_register(), superblock_new(), surface_new(), taskbar_entry_add(), thread_init(), vfs_register_fs(), vmm_cpu_ctx_init_common(), wait_block_setup(), and window_new().

list_first()

static list_entry_t * list_first ( list_t *  list )

inlinestatic

Gets the first entry in the list without removing it.

Parameters

list	A pointer to the list_t.

Returns

A pointer to the first list_entry_t in the list, or NULL if the list is empty.

Definition at line 382 of file list.h.

References assert, list_t::head, list_is_empty(), list_entry_t::next, and NULL.

Referenced by process_note_write(), and wait_timer_handler().

list_init()

static void list_init ( list_t *  list )

inlinestatic

Initializes a list.

Parameters

list	A pointer to the list_t to initialize.

Definition at line 198 of file list.h.

References assert, list_t::head, list_t::length, list_entry_init(), list_entry_t::next, and NULL.

Referenced by _files_init(), _heap_init(), _threading_init(), aml_mutex_stack_push(), aml_namespace_overlay_init(), aml_object_new(), aml_patch_up_init(), client_new(), config_open(), dentry_new(), disk_load_dir(), display_new(), dwm_init(), element_new_raw(), key_init(), local_listen_new(), panic_symbols_init(), process_init(), ramfs_mount(), sched_queues_init(), socket_family_register(), space_init(), taskbar_procedure(), vfs_list_init(), wait_cpu_ctx_init(), wait_queue_init(), and wait_thread_ctx_init().

list_is_empty()

static bool list_is_empty ( list_t *  list )

inlinestatic

Checks if a list is empty.

Parameters

list	A pointer to the list_t to check.

Returns

true if the list is empty, false otherwise.

Definition at line 229 of file list.h.

References assert, list_t::head, list_t::length, list_entry_t::next, and NULL.

Referenced by _heap_alloc(), _heap_remove_from_free_list(), aml_namespace_commit(), aml_object_new(), boot_dir_free(), config_close(), list_first(), list_last(), list_pop(), local_socket_accept(), process_free(), ramfs_remove(), sched_queues_pop(), space_deinit(), wait_block_finalize(), and wait_queue_deinit().

list_last()

static list_entry_t * list_last ( list_t *  list )

inlinestatic

Gets the last entry in the list without removing it.

Parameters

list	A pointer to the list_t.

Returns

A pointer to the last list_entry_t in the list, or NULL if the list is empty.

Definition at line 400 of file list.h.

References assert, list_t::head, list_is_empty(), NULL, and list_entry_t::prev.

Referenced by _heap_block_new(), aml_mutex_stack_pop(), and wait_block_finalize().

list_length()

static uint64_t list_length ( list_t *  list )

inlinestatic

Gets the length of the list.

Parameters

list	A pointer to the list_t.

Returns

The number of elements in the list.

Definition at line 248 of file list.h.

References assert, list_t::length, and NULL.

Referenced by aml_mutex_stack_pop(), aml_object_free(), aml_patch_up_unresolved_count(), key_share(), taskbar_entry_add(), and taskbar_get_task_button_rect().

list_pop()

static list_entry_t * list_pop ( list_t *  list )

inlinestatic

Pops the first entry from the list.

Parameters

list	A pointer to the list_t to pop the entry from.

Returns

A pointer to the removed list_entry_t, or NULL if the list is empty.

Definition at line 361 of file list.h.

References assert, list_t::head, list_is_empty(), list_remove(), list_entry_t::next, and NULL.

Referenced by _heap_alloc(), aml_object_new(), boot_dir_free(), config_close(), local_socket_accept(), sched_queues_pop(), and wait_block_setup().

list_prepend()

static void list_prepend ( list_t *  list, list_entry_t *  head, list_entry_t *  entry  )

inlinestatic

Prepends an entry to the list.

Parameters

list	A pointer to the list_t to prepend to.
head	A pointer to the list entry before which the new entry will be prepended.
entry	A pointer to the list_entry_t to prepend.

Definition at line 305 of file list.h.

References list_add(), and list_entry_t::prev.

Referenced by key_share(), and wait_block_finalize().

list_push()

static void list_push ( list_t *  list, list_entry_t *  entry  )

inlinestatic

Pushes an entry to the end of the list.

Parameters

list	A pointer to the list_t to push the entry to.
entry	A pointer to the list_entry_t to push.

Definition at line 345 of file list.h.

References assert, list_t::head, list_add(), list_entry_t::next, NULL, and list_entry_t::prev.

Referenced by _files_push(), _heap_add_to_free_list(), _heap_block_new(), _thread_new(), _threading_init(), aml_mutex_stack_push(), aml_namespace_add_child(), aml_namespace_commit(), aml_object_free(), aml_patch_up_add_unresolved(), client_action_surface_new(), config_open(), dentry_make_positive(), disk_load_dir(), dwm_attach(), dwm_client_accept(), dwm_focus_set(), element_new(), font_new(), image_new_blank(), key_share(), local_socket_connect(), panic_symbols_init(), process_init(), process_kill(), sched_queues_push(), socket_family_register(), space_load(), taskbar_entry_add(), thread_init(), vfs_register_fs(), vmm_cpu_ctx_init_common(), wait_block_finalize(), wait_block_setup(), and window_new().

list_remove()

static void list_remove ( list_t *  list, list_entry_t *  entry  )

inlinestatic

Removes a list entry from its current list.

Parameters

list	A pointer to the list_t that contains the entry.
entry	A pointer to the list_entry_t to remove.

Definition at line 317 of file list.h.

References assert, list_t::head, list_t::length, list_entry_t::list, list_entry_init(), list_entry_t::next, NULL, and list_entry_t::prev.

Referenced by _files_remove(), _heap_free(), _heap_remove_from_free_list(), _thread_free(), aml_mutex_stack_pop(), aml_namespace_commit(), aml_namespace_remove(), aml_patch_up_remove_unresolved(), client_action_surface_free(), client_free(), dentry_free(), dwm_client_disconnect(), dwm_detach(), dwm_focus_set(), element_free(), element_free_children(), font_free(), image_free(), key_claim(), key_timer_handler(), list_pop(), process_free(), ramfs_dentry_deinit(), realloc(), socket_family_get_and_remove(), space_load(), taskbar_entry_add(), taskbar_entry_remove(), taskbar_procedure(), thread_free(), vfs_remove_superblock(), vfs_unregister_fs(), wait_block_finalize(), wait_remove_wait_entries(), wait_timer_handler(), wait_unblock(), wait_unblock_thread(), and window_free().