diff options
Diffstat (limited to 'src/lib/kernel/list.h')
| -rw-r--r-- | src/lib/kernel/list.h | 168 |
1 files changed, 168 insertions, 0 deletions
diff --git a/src/lib/kernel/list.h b/src/lib/kernel/list.h new file mode 100644 index 0000000..2388f9a --- /dev/null +++ b/src/lib/kernel/list.h @@ -0,0 +1,168 @@ +#ifndef __LIB_KERNEL_LIST_H +#define __LIB_KERNEL_LIST_H + +/* Doubly linked list. + + This implementation of a doubly linked list does not require + use of dynamically allocated memory. Instead, each structure + that is a potential list element must embed a struct list_elem + member. All of the list functions operate on these `struct + list_elem's. The list_entry macro allows conversion from a + struct list_elem back to a structure object that contains it. + + For example, suppose there is a needed for a list of `struct + foo'. `struct foo' should contain a `struct list_elem' + member, like so: + + struct foo + { + struct list_elem elem; + int bar; + ...other members... + }; + + Then a list of `struct foo' can be be declared and initialized + like so: + + struct list foo_list; + + list_init (&foo_list); + + Iteration is a typical situation where it is necessary to + convert from a struct list_elem back to its enclosing + structure. Here's an example using foo_list: + + struct list_elem *e; + + for (e = list_begin (&foo_list); e != list_end (&foo_list); + e = list_next (e)) + { + struct foo *f = list_entry (e, struct foo, elem); + ...do something with f... + } + + You can find real examples of list usage throughout the + source; for example, malloc.c, palloc.c, and thread.c in the + threads directory all use lists. + + The interface for this list is inspired by the list<> template + in the C++ STL. If you're familiar with list<>, you should + find this easy to use. However, it should be emphasized that + these lists do *no* type checking and can't do much other + correctness checking. If you screw up, it will bite you. + + Glossary of list terms: + + - "front": The first element in a list. Undefined in an + empty list. Returned by list_front(). + + - "back": The last element in a list. Undefined in an empty + list. Returned by list_back(). + + - "tail": The element figuratively just after the last + element of a list. Well defined even in an empty list. + Returned by list_end(). Used as the end sentinel for an + iteration from front to back. + + - "beginning": In a non-empty list, the front. In an empty + list, the tail. Returned by list_begin(). Used as the + starting point for an iteration from front to back. + + - "head": The element figuratively just before the first + element of a list. Well defined even in an empty list. + Returned by list_rend(). Used as the end sentinel for an + iteration from back to front. + + - "reverse beginning": In a non-empty list, the back. In an + empty list, the head. Returned by list_rbegin(). Used as + the starting point for an iteration from back to front. + + - "interior element": An element that is not the head or + tail, that is, a real list element. An empty list does + not have any interior elements. +*/ + +#include <stdbool.h> +#include <stddef.h> +#include <stdint.h> + +/* List element. */ +struct list_elem + { + struct list_elem *prev; /* Previous list element. */ + struct list_elem *next; /* Next list element. */ + }; + +/* List. */ +struct list + { + struct list_elem head; /* List head. */ + struct list_elem tail; /* List tail. */ + }; + +/* Converts pointer to list element LIST_ELEM into a pointer to + the structure that LIST_ELEM is embedded inside. Supply the + name of the outer structure STRUCT and the member name MEMBER + of the list element. See the big comment at the top of the + file for an example. */ +#define list_entry(LIST_ELEM, STRUCT, MEMBER) \ + ((STRUCT *) ((uint8_t *) &(LIST_ELEM)->next \ + - offsetof (STRUCT, MEMBER.next))) + +void list_init (struct list *); + +/* List traversal. */ +struct list_elem *list_begin (struct list *); +struct list_elem *list_next (struct list_elem *); +struct list_elem *list_end (struct list *); + +struct list_elem *list_rbegin (struct list *); +struct list_elem *list_prev (struct list_elem *); +struct list_elem *list_rend (struct list *); + +struct list_elem *list_head (struct list *); +struct list_elem *list_tail (struct list *); + +/* List insertion. */ +void list_insert (struct list_elem *, struct list_elem *); +void list_splice (struct list_elem *before, + struct list_elem *first, struct list_elem *last); +void list_push_front (struct list *, struct list_elem *); +void list_push_back (struct list *, struct list_elem *); + +/* List removal. */ +struct list_elem *list_remove (struct list_elem *); +struct list_elem *list_pop_front (struct list *); +struct list_elem *list_pop_back (struct list *); + +/* List elements. */ +struct list_elem *list_front (struct list *); +struct list_elem *list_back (struct list *); + +/* List properties. */ +size_t list_size (struct list *); +bool list_empty (struct list *); + +/* Miscellaneous. */ +void list_reverse (struct list *); + +/* Compares the value of two list elements A and B, given + auxiliary data AUX. Returns true if A is less than B, or + false if A is greater than or equal to B. */ +typedef bool list_less_func (const struct list_elem *a, + const struct list_elem *b, + void *aux); + +/* Operations on lists with ordered elements. */ +void list_sort (struct list *, + list_less_func *, void *aux); +void list_insert_ordered (struct list *, struct list_elem *, + list_less_func *, void *aux); +void list_unique (struct list *, struct list *duplicates, + list_less_func *, void *aux); + +/* Max and min. */ +struct list_elem *list_max (struct list *, list_less_func *, void *aux); +struct list_elem *list_min (struct list *, list_less_func *, void *aux); + +#endif /* lib/kernel/list.h */ |