Table of Contents

Linked Lists

Introduction

PintOS contains a linked list data structure in lib/kernel/list.h that is used for many different purposes. This linked list implementation is different from most other linked list implementations you may have encountered, because it does not use any dynamic memory allocation.

/* 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. */
};

In a PintOS linked list, each list element contains a struct list_elem, which contains the pointers to the next and previous element. Because the list elements themselves have enough space to hold the prev and next pointers, we don’t need to allocate any extra space to support our linked list. Here is an example of a linked list element which can hold an integer:

/* Integer linked list */
struct int_list_elem
{
    int value;
    struct list_elem elem;
};

Next, you must create a struct list to represent the whole list. Initialize it with list_init().

/* Declare and initialize a list */
struct list my_list;
list_init (&my_list);

Now, you can declare a list element and add it to the end of the list. Notice that the second argument of list_push_back() is the address of a struct list_elem, not the struct int_list_elem itself.

/* Declare a list element. */
struct int_list_elem three = {3, {NULL, NULL}};
/* Add it to the list */
list_push_back (&my_list, &three.elem);

We can use the list_entry() macro to convert a generic struct list_elem into our custom struct int_list_elem type. Then, we can grab the value attribute and print it out:

/* Fetch elements from the list */
struct list_elem *first_list_element = list_begin (&my_list);
struct int_list_elem *first_integer = list_entry (first_list_element,
                                                  struct int_list_elem,
                                                  elem);
printf("The first element is: %d\n", first_integer->value);

By storing the prev and next pointers inside the structs themselves, we can avoid creating new linked list element containers. However, this also means that a list_elem can only be part of one list a time. Additionally, our list should be homogeneous (it should only contain one type of element).

The list_entry() macro works by computing the offset of the elem field inside of struct int_list_elem. In our example, this offset is 4 bytes. To convert a pointer to a generic struct list_elem to a pointer to our custom struct int_list_elem, the list_entry() just needs to subtract 4 bytes! (It also casts the pointer, in order to satisfy the C type system.)

Linked lists have 2 sentinel elements: the head and tail elements of the struct list. These sentinel elements can be distinguished by their NULL pointer values. Make sure to distinguish between functions that return the first actual element of a list and functions that return the sentinel head element of the list.

There are also functions that sort a link list (using quicksort) and functions that insert an element into a sorted list. These functions require you to provide a list element comparison function (see lib/kernel/list.h for more details).

List API Documentation

This implementation of a doubly linked list does not require use of dynamically allocated memory for the list itself. Please note however, that the list elements most likely still need to be dynamically allocated using malloc and the memory has to be de-allocated at the end using free. 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 need for a list of struct foo. In this case, struct foo should contain a struct list_elem member, like so:

struct foo
{   
    struct list_elem elem;   
    int bar;   
    // ...other members... 
};

It does not matter at what position inside the struct foo the struct list_elem is positioned. 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 the next 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:

         +------+     +------+
NULL <---| head |<--->| tail |---> NULL
         +------+     +------+

A list with two elements in it looks like this:

         +------+     +-------+     +-------+     +------+
NULL <---| head |<--->|   1   |<--->|   2   |<--->| tail |---> NULL
         +------+     +-------+     +-------+     +------+

The symmetry of this arrangement eliminates lots of special cases in list processing. For example, take a look at the implementation of 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...
}

Adding new elements to a list, traversing it, and deleting all elements from the list again looks like:

int main ()
{
    // create and initialize list
    struct list g_list;
    list_init (&g_list);

    // Create 10 nodes
    struct foo *e;
    for (size_t i = 0; i < 10; ++i)
    {
        e = malloc (sizeof (struct foo));
        e->data = i;
        list_push_back (&g_list, &e->elem);
    }

    // iterate over all nodes and print the stored data
    struct list_elem *k;
    for (k = list_begin (&g_list); k != list_end (&g_list); k = list_next (k))
    {
        struct foo *f = list_entry (k, struct foo, elem);
        printf ("%d\n", f->data);
    }

    // free all memory associated with the list
    for (k = list_begin (&list); k != list_end (&list); k = list_remove (k))
    {
        struct foo *f = list_entry (k, struct foo, elem);
        free(f);
    }
    return 0;
}

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.

List Functions

kernel/list.c implements several functions:

The list_entry macro is an important facility 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 previous section for an example.

void list_init (struct list *l);

Initializes l as an empty list.

struct list_elem *list_begin (struct list *l);

Returns the beginning of l.

struct list_elem *list_next (struct list_elem *elem);

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.

struct list_elem *list_end (struct list *l);

Returns l’s tail.

struct list_elem *list_rbegin (struct list *l);

Returns l’s reverse beginning, for iterating through l in reverse order, from back to front.

struct list_elem *list_prev (struct list_elem *elem);

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.

struct list_elem *list_rend (struct list *l);

Returns l’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...
}

struct list_elem *list_head (struct list *l);

Returns l’s head

struct list_elem *list_tail (struct list *l);

Returns l’s tail.

void list_insert (struct list_elem *before, struct list_elem *elem);

Inserts elem just before before, which may be either an interior element or a tail. The latter case is equivalent to list_push_back().

void list_splice (struct list_elem* before, struct list_elem* first, struct list_elem *last);

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.

void list_push_front (struct list *l, struct list_elem *elem);

Inserts elem at the beginning of l, so that it becomes the front in l.

void list_push_back (struct list *l, struct list_elem *elem);

Inserts elem at the end of l, so that it becomes the back in l.

struct list_elem *list_remove (struct list_elem *elem);

Removes elem from its list and returns the element that followed it. Undefined behavior if elem is not in a list.

struct list_elem *list_pop_front (struct list *l);

Removes the front element from l and returns it. Undefined behavior if l is empty before removal.

struct list_elem *list_pop_back (struct list *l);

Removes the back element from l and returns it. Undefined behavior if l is empty before removal.

struct list_elem *list_front (struct list *l);

Returns the front element in l. Undefined behavior if l is empty.

struct list_elem *list_back (struct list *l);

Returns the back element in l. Undefined behavior if l is empty.

size_t list_size (struct list *l);

Returns the number of elements in l. Runs in O(n) in the number of elements.

bool list_empty(struct list *l);

Returns true if l is empty, false otherwise.

void list_reverse (struct list *l);

Reverses the order of l.

typedef bool list_less_func (const struct list_elem *a, const struct list_elem *b, void *aux);

For sorting, we need to rewrite this function, 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 *l, list_less_func *less, void *aux);

Sorts l 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 l.

void list_insert_ordered (struct list *l, struct list_elem *elem, list_less_func *less, void *aux);

Inserts elem in the proper position in l, which must be sorted according to less given auxiliary data aux. Runs in O(n) average case in the number of elements in l.

void list_unique (struct list *l, struct list *duplicates, list_less_func *less, void *aux);

Iterates through l 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 duplicated elements from l are appended to duplicates.

struct list_elem *list_max (struct list *l, list_less_func *less, void *aux);

Returns the element in l 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.

struct list_elem *list_min (struct list *l, list_less_func *less, void *aux);

Returns the element in l 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.