1 #ifndef __LIB_KERNEL_LIST_H
2 #define __LIB_KERNEL_LIST_H
6 This implementation of a doubly linked list does not require
7 use of dynamically allocated memory. Instead, each structure
8 that is a potential list element must embed a struct list_elem
9 member. All of the list functions operate on these `struct
10 list_elem's. The list_entry macro allows conversion from a
11 struct list_elem back to a structure object that contains it.
13 For example, suppose there is a needed for a list of `struct
14 foo'. `struct foo' should contain a `struct list_elem'
19 struct list_elem elem;
24 Then a list of `struct foo' can be be declared and initialized
29 list_init (&foo_list);
31 Iteration is a typical situation where it is necessary to
32 convert from a struct list_elem back to its enclosing
33 structure. Here's an example using foo_list:
37 for (e = list_begin (&foo_list); e != list_end (&foo_list);
40 struct foo *f = list_entry (e, struct foo, elem);
41 ...do something with f...
44 You can find real examples of list usage throughout the
45 source; for example, malloc.c, palloc.c, and thread.c in the
46 threads directory all use lists.
48 The interface for this list is inspired by the list<> template
49 in the C++ STL. If you're familiar with list<>, you should
50 find this easy to use. However, it should be emphasized that
51 these lists do *no* type checking and can't do much other
52 correctness checking. If you screw up, it will bite you.
54 Glossary of list terms:
56 - "front": The first element in a list. Undefined in an
57 empty list. Returned by list_front().
59 - "back": The last element in a list. Undefined in an empty
60 list. Returned by list_back().
62 - "tail": The element figuratively just after the last
63 element of a list. Well defined even in an empty list.
64 Returned by list_end(). Used as the end sentinel for an
65 iteration from front to back.
67 - "beginning": In a non-empty list, the front. In an empty
68 list, the tail. Returned by list_begin(). Used as the
69 starting point for an iteration from front to back.
71 - "head": The element figuratively just before the first
72 element of a list. Well defined even in an empty list.
73 Returned by list_rend(). Used as the end sentinel for an
74 iteration from back to front.
76 - "reverse beginning": In a non-empty list, the back. In an
77 empty list, the head. Returned by list_rbegin(). Used as
78 the starting point for an iteration from back to front.
80 - "interior element": An element that is not the head or
81 tail, that is, a real list element. An empty list does
82 not have any interior elements.
92 struct list_elem *prev; /* Previous list element. */
93 struct list_elem *next; /* Next list element. */
99 struct list_elem head; /* List head. */
100 struct list_elem tail; /* List tail. */
103 /* Converts pointer to list element LIST_ELEM into a pointer to
104 the structure that LIST_ELEM is embedded inside. Supply the
105 name of the outer structure STRUCT and the member name MEMBER
106 of the list element. See the big comment at the top of the
107 file for an example. */
108 #define list_entry(LIST_ELEM, STRUCT, MEMBER) \
109 ((STRUCT *) ((uint8_t *) &(LIST_ELEM)->next \
110 - offsetof (STRUCT, MEMBER.next)))
112 void list_init (struct list *);
114 /* List traversal. */
115 struct list_elem *list_begin (struct list *);
116 struct list_elem *list_next (struct list_elem *);
117 struct list_elem *list_end (struct list *);
119 struct list_elem *list_rbegin (struct list *);
120 struct list_elem *list_prev (struct list_elem *);
121 struct list_elem *list_rend (struct list *);
123 struct list_elem *list_head (struct list *);
124 struct list_elem *list_tail (struct list *);
126 /* List insertion. */
127 void list_insert (struct list_elem *, struct list_elem *);
128 void list_splice (struct list_elem *before,
129 struct list_elem *first, struct list_elem *last);
130 void list_push_front (struct list *, struct list_elem *);
131 void list_push_back (struct list *, struct list_elem *);
134 struct list_elem *list_remove (struct list_elem *);
135 struct list_elem *list_pop_front (struct list *);
136 struct list_elem *list_pop_back (struct list *);
139 struct list_elem *list_front (struct list *);
140 struct list_elem *list_back (struct list *);
142 /* List properties. */
143 size_t list_size (struct list *);
144 bool list_empty (struct list *);
147 void list_reverse (struct list *);
149 /* Compares the value of two list elements A and B, given
150 auxiliary data AUX. Returns true if A is less than B, or
151 false if A is greater than or equal to B. */
152 typedef bool list_less_func (const struct list_elem *a,
153 const struct list_elem *b,
156 /* Operations on lists with ordered elements. */
157 void list_sort (struct list *,
158 list_less_func *, void *aux);
159 void list_insert_ordered (struct list *, struct list_elem *,
160 list_less_func *, void *aux);
161 void list_unique (struct list *, struct list *duplicates,
162 list_less_func *, void *aux);
165 struct list_elem *list_max (struct list *, list_less_func *, void *aux);
166 struct list_elem *list_min (struct list *, list_less_func *, void *aux);
168 #endif /* lib/kernel/list.h */