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);
Our doubly linked lists have two header elements: the "head"
just before the first element and the "tail" just after the
last element. The prev' link of the front header is null, as
is thenext' link of the back header. Their other two links
point toward each other via the interior elements of the list.
An empty list looks like this:
+------+ +------+
<---| head |<--->| tail |--->
+------+ +------+
A list with two elements in it looks like this:
+------+ +-------+ +-------+ +------+
<---| head |<--->| 1 |<--->| 2 |<--->| tail |<--->
+------+ +-------+ +-------+ +------+
The symmetry of this arrangement eliminates lots of special cases in list processing. For example, take a look at list_remove(): it takes only two pointer assignments and no conditionals. That's a lot simpler than the code would be without header elements.
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...
}
'kernerl/list.c' implements several functions:
A important method we must comprehend:
#define list_entry(LIST_ELEM, STRUCT, MEMBER) \
((STRUCT *) ((uint8_t *) &(LIST_ELEM)->next \
- offsetof (STRUCT, MEMBER.next)))
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.
Initializes LIST as an empty list.
Returns the beginning of LIST.
Returns the element after ELEM in its list. If ELEM is the last element in its list, returns the list tail. Results are undefined if ELEM is itself a list tail.
Returns LIST's tail.
Returns the LIST's reverse beginning, for iterating through LIST in reverse order, from back to front.
Returns the element before ELEM in its list. If ELEM is the first element in its list, returns the list head. Results are undefined if ELEM is itself a list head.
Returns LIST's head.
list_rend() is often used in iterating through a list in reverse order, from back to front. Here's typical usage, following the example from the top of list.h:
for (e = list_rbegin (&foo_list); e != list_rend (&foo_list);
e = list_prev (e))
{
struct foo *f = list_entry (e, struct foo, elem);
...do something with f...
}
Return's LIST's head
Return's LIST's tail.
Inserts ELEM just before BEFORE, which may be either an interior element or a tail. The latter case is equivalent to list_push_back().
Removes elements FIRST though LAST (exclusive) from their current list, then inserts them just before BEFORE, which may be either an interior element or a tail.
Inserts ELEM at the beginning of LIST, so that it becomes the front in LIST.
Inserts ELEM at the end of LIST, so that it becomes the back in LIST.
Removes ELEM from its list and returns the element that followed it. Undefined behavior if ELEM is not in a list.
Removes the front element from LIST and returns it. Undefined behavior if LIST is empty before removal.
Removes the back element from LIST and returns it. Undefined behavior if LIST is empty before removal.
Returns the front element in LIST. Undefined behavior if LIST is empty.
Returns the back element in LIST. Undefined behavior if LIST is empty.
Returns the number of elements in LIST. Runs in O(n) in the number of elements.
Returns true if LIST is empty, false otherwise.
Reverses the order of LIST.
We need to rewrite this function when we need:
eg:
bool
thread_less_func(struct list_elem *a, struct list_elem *b, void *aux) {
return list_entry(a,struct thread,elem)->priority >
list_entry(b,struct thread,elem)->priority;
}
void list_sort (struct list , list_less_func , void *aux);
Sorts LIST according to LESS given auxiliary data AUX, using a natural iterative merge sort that runs in O(n lg n) time and O(1) space in the number of elements in LIST.
void list_insert_ordered (struct list , struct list_elem , list_less_func , void aux);
Inserts ELEM in the proper position in LIST, which must be sorted according to LESS given auxiliary data AUX. Runs in O(n) average case in the number of elements in LIST.
Iterates through LIST and removes all but the first in each set of adjacent elements that are equal according to LESS given auxiliary data AUX. If DUPLICATES is non-null, then the elements from LIST are appended to DUPLICATES.
Returns the element in LIST with the largest value according to LESS given auxiliary data AUX. If there is more than one maximum, returns the one that appears earlier in the list. If the list is empty, returns its tail.
Returns the element in LIST with the smallest value according to LESS given auxiliary data AUX. If there is more than one minimum, returns the one that appears earlier in the list. If the list is empty, returns its tail.