PKUOS - Pintos
Pintos source browser for PKU Operating System course
Data Fields
list_elem Struct Reference

Doubly linked list. More...

#include <list.h>

Collaboration diagram for list_elem:
Collaboration graph
[legend]

Data Fields

struct list_elemprev
 Previous list element. More...
 
struct list_elemnext
 Next list element. More...
 

Detailed Description

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:

Definition at line 90 of file list.h.

Field Documentation

◆ next

struct list_elem* list_elem::next

◆ prev

struct list_elem* list_elem::prev

Previous list element.

Definition at line 92 of file list.h.

Referenced by is_head(), is_interior(), is_tail(), list_back(), list_init(), list_insert(), list_prev(), list_rbegin(), list_remove(), list_reverse(), and list_splice().


The documentation for this struct was generated from the following file: