diff options
Diffstat (limited to 'kernel/include/util/list.h')
| -rw-r--r-- | kernel/include/util/list.h | 224 |
1 files changed, 224 insertions, 0 deletions
diff --git a/kernel/include/util/list.h b/kernel/include/util/list.h new file mode 100644 index 0000000..5fd44c1 --- /dev/null +++ b/kernel/include/util/list.h @@ -0,0 +1,224 @@ +#pragma once + +#include "kernel.h" + +/* + * Generic circular doubly linked list implementation. + * + * list_t is the head of the list. + * list_link_t should be included in structures which want to be + * linked on a list_t. + * + * All of the list functions take pointers to list_t and list_link_t + * types, unless otherwise specified. + * + * list_init(list) initializes a list_t to an empty list. + * + * list_empty(list) returns 1 iff the list is empty. + * + * Insertion functions. + * list_insert_head(list, link) inserts link at the front of the list. + * list_insert_tail(list, link) inserts link at the end of the list. + * list_insert_before(olink, nlink) inserts nlink before olink in list. + * + * Removal functions. + * Head is list->l_next. Tail is list->l_prev. + * The following functions should only be called on non-empty lists. + * list_remove(link) removes a specific element from the list. + * list_remove_head(list) removes the first element of list. + * list_remove_tail(list) removes the last element of list. + * + * Item accessors. + * list_item(link, type, member) + * + * Given a list_link_t* and the name of the type of structure which contains + * the list_link_t and the name of the member corresponding to the list_link_t, + * returns a pointer (of type "type*") to the item. + * + * Example: + * struct my_struct { list_link_t my_link }; + * struct my_struct a; + * list_link_init(&a.my_link); + * + * struct my_struct *b = list_item(&a.my_link, struct my_struct, my_link); + * // b should equal &a here + * + * To iterate over a list, + * list_link_t *link; + * for (link = list->l_next; + * link != list; link = link->l_next) + * ... + * + * Or, use the macros, which will work even if you list_remove() the + * current link: + * list_iterate(list, iterator, type, member) { + * ... use iterator ... + * } + * (see also list_iterate_reverse for iterating in reverse) + * + * Where: + * - list is a pointer to the list_t to iterate over, + * - iterator is a name for the loop variable which will take on the value + * of each item in the list, + * - type is the type of items in the list, + * - member is the name of the field in the item type that is the list_link_t + * + * Example (from kernel/drivers/chardev.c) + * // chardevs is a list_t + * // chardev_t has a cd_link member which is a list_link_t + * list_iterate(&chardevs, cd, chardev_t, cd_link) + * { + * if (dev->cd_id == cd->cd_id) + * { + * return -1; + * } + * } + */ + +/** + * Initialize a list_t. + */ +#define LIST_INITIALIZER(list) \ + { \ + .l_next = &(list), .l_prev = &(list) \ + } + +/** + * Initialize a list link. + */ +#define LIST_LINK_INITIALIZER(list_link) \ + { \ + .l_next = NULL, .l_prev = NULL \ + } + +typedef struct list +{ + struct list *l_next; + struct list *l_prev; +} list_t, list_link_t; + +/** + * Initialize a list link. + */ +void list_link_init(list_link_t *link); + +/** + * Initialize a list_t. + */ +void list_init(list_t *list); + +/** + * Check if a link is linked to some list. + * + * @param link The link to check. + * @return long 1 if linked, 0 otherwise. + */ +long list_link_is_linked(const list_link_t *link); + +/** + * Check if a list is empty. + * + * @param list The list to check. + * @return long 1 if empty, 0 otherwise. + */ +long list_empty(const list_t *list); + +/** + * Assert that the internal state of a list is sane, and + * panic if it is not. + * + * @param list The list to check for sanity. + */ +void list_assert_sanity(const list_t *list); + +/** + * Insert a new link onto a list before another link. + * + * @param link The link before which the new link should be inserted. + * @param to_insert The new link to be inserted. + */ +void list_insert_before(list_link_t *link, list_link_t *to_insert); + +/** + * Insert a new link at the head (beginning) of a given list. + * + * @param list The list to insert on. + * @param link The new link to insert. + */ +void list_insert_head(list_t *list, list_link_t *link); + +/** + * Insert a new link at the tail (end) of a given list. + * + * @param list The list to insert on. + * @param link The new link to insert. + */ +void list_insert_tail(list_t *list, list_link_t *link); + +/** + * Remove a particular link from the list it's on. + * + * @param link The link to be removed from its list. + */ +void list_remove(list_link_t *link); + +/** + * Get a pointer to the item that contains the given link. + * + * For instance, given a list_link_t contained within a proc_t, get a reference + * to the proc_t itself. + * + * @param link The link contained within the item to access. + * @param type The type of the outer item struct (e.g., proc_t) + * @param member The name of the struct member which is the list_link_t (e.g. p_list_link) + * + */ +#define list_item(link, type, member) \ + (type *)((char *)(link)-offsetof(type, member)) + +/** + * Get the item at the head of the list. See list_item for explanation + * of type and member. + */ +#define list_head(list, type, member) list_item((list)->l_next, type, member) + +/** + * Get the item at the tail of the list. See list_item for explanation + * of type and member. + */ +#define list_tail(list, type, member) list_item((list)->l_prev, type, member) + +/** + * Get the next item in a list that occurs after the given item. + * + * @param current An item from the list (e.g. a proc_t) + * See list_item for explanation of type and member. + */ +#define list_next(current, type, member) \ + list_head(&(current)->member, type, member) + +/** + * Get the previous item in a list given an item. See list_next for explanation. + */ +#define list_prev(current, type, member) \ + list_tail(&(current)->member, type, member) + +/** + * Iterate over elements in in a list. See comment at top of list.h for + * detailed description. + */ +#define list_iterate(list, var, type, member) \ + for (type *var = list_head(list, type, member), \ + *__next_##var = list_next(var, type, member); \ + &var->member != (list); \ + var = __next_##var, __next_##var = list_next(var, type, member)) + +/** + * Iterate over the elements of a list in reverse. See comment at top of list.h for + * detailed description. + */ +#define list_iterate_reverse(list, var, type, member) \ + for (type *var = list_tail(list, type, member), \ + *__next_##var = list_prev(var, type, member); \ + &var->member != (list); \ + var = __next_##var, __next_##var = list_prev(var, type, member)) |