OS pintos链表

OS

https://www.zybuluo.com/SovietPower/note/1828308

list.c

list_elem

链表元素，含有两个双向的链表元素指针。

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

list_entry()

将一个 指向链表元素的指针 转为 指向指定类型元素的指针。
STRUCT为指定类型，MEMBER是该链表元素的变量名称？（因为用的#define不是函数）

链表中存的不是元素值，而只是一个list_elem；结构体的链表元素并不是该结构体，而是一个list_elem，所有对该list_elem的操作都相当于对结构体的操作。
通过调用list_entry()可将list_elem转为原结构体。

#define list_entry(LIST_ELEM, STRUCT, MEMBER)           \
        ((STRUCT *) ((uint8_t *) &(LIST_ELEM)->next     \
                     - offsetof (STRUCT, MEMBER.next)))

LIST_INITIALIZER()

初始化一个空链表。
链表初始化既可以通过调用list_init (&my_list)，也可以通过struct list my_list = LIST_INITIALIZER (my_list)。

#define LIST_INITIALIZER(NAME) { { NULL, &(NAME).tail }, \
                                 { &(NAME).head, NULL } }

list_init()

初始化一个空链表。

void list_init (struct list *list);

is_head()

判断当前元素是否为一个链表的头部。

static inline bool is_head (struct list_elem *elem);

is_interior()

判断当前元素是否为一个链表的内部元素（既不是头也不是尾，为数据元素）。

static inline bool is_interior (struct list_elem *elem);

is_tail()

判断当前元素是否为一个链表的尾部。

static inline bool is_tail (struct list_elem *elem);

list_head()

返回一个链表的头部。

struct list_elem *list_head (struct list *list);

list_tail()

返回一个链表的尾部。

struct list_elem *list_tail (struct list *list);

list_begin()

返回一个链表的第一个元素（头部后的一个元素）。

struct list_elem *list_begin (struct list *list);

list_end()

返回一个链表的尾部（最后一个元素后的一个元素，用于终止迭代）。
同list_tail()。

struct list_elem *list_end (struct list *list);

list_front()

返回一个链表的第一个元素（头部后的一个元素）。
链表必须非空。

struct list_elem *list_front (struct list *list);

list_back()

返回一个链表的最后一个元素（尾部前）。
同list_tail()，但链表必须非空。

struct list_elem *list_back (struct list *list);

list_rbegin()

返回一个链表的一个反向迭代器，指向链表最后一个元素（尾部前的一个元素）。

struct list_elem *list_rbegin (struct list *list);

list_rend()

返回一个链表的一个反向迭代器，指向链表头部（第一个元素前的一个元素，用于终止迭代）。
同list_head()。

struct list_elem *list_rend (struct list *list);

list_next()

返回一个链表元素的后继元素。该元素不能是链表尾部。

struct list_elem *list_next (struct list_elem *elem);

list_prev()

返回一个链表元素的前驱元素。该元素不能是链表头部。

struct list_elem *list_prev (struct list_elem *elem);

list_insert()

在某个链表元素（不能是头部）的前面插入一个元素。

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

list_splice()

将链表中的一串元素移动到某个链表元素（不能是头部）的前面。
移动的那一串连续元素必须都是内部元素，从first到last（不包含last）。

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

list_push_front()

在链表第一个的元素前（头部后）插入一个元素。

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

list_push_back()

在链表最后一个元素后（尾部前）插入一个元素。

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

list_remove()

将一个元素从其链表中删除，并返回该元素之前的后继。
该函数提供了一个删除整个链表的方法：

for (e = list_begin (&list); e != list_end (&list); e = list_remove (e))
    ...do something with e...

注意：
该元素必须是链表元素（但函数内没有对此进行检查），否则会产生未定义行为。
删除后依旧能使用list_prev(), list_next()访问该元素过去的前驱/后继（因为没改指针），但list_prev(list_next())不再是该元素。

struct list_elem *list_remove (struct list_elem *elem);

list_pop_front()

删除链表的第一个元素（头部后）。
注意：该链表必须非空（但函数内没有对此进行检查），否则会产生未定义行为。

struct list_elem *list_pop_front (struct list *list);

list_pop_back()

删除链表的最后一个元素（尾部前）。
注意：该链表必须非空（但函数内没有对此进行检查），否则会产生未定义行为。

struct list_elem *list_pop_back (struct list *list);

list_size()

返回链表中的元素个数。复杂度$O(n)$。

size_t list_size (struct list *list);

list_empty()

判断链表是否为空（只含有头部和尾部两个元素）。

bool list_empty (struct list *list)
{
  return list_begin (list) == list_end (list);
}

swap()

交换两个链表元素指针类型的元素。
同swap。

static void swap (struct list_elem **a, struct list_elem **b);

list_reverse()

反转整个链表。

void list_reverse (struct list *list);

is_sorted()

判断链表的a到b部分是否有序（不包含b）。
大小根据比较函数less(aux)判断。

static bool
is_sorted (struct list_elem *a, struct list_elem *b,
           list_less_func *less, void *aux);

find_end_of_run()

在链表的a到b部分（不包含b），找到从a开始的最长不下降连续序列。返回该最长不下降序列的最后一个元素的下一个元素（不包含该元素）。
大小根据比较函数less(aux)判断。

static struct list_elem *
find_end_of_run (struct list_elem *a, struct list_elem *b,
                 list_less_func *less, void *aux);

inplace_merge()

将a0到a1b0（不包含）之间的元素，与a1b0到b1（不包含）之间的元素归并到一起。用于归并排序。
a0到a1b0（不包含）和a1b0到b1（不包含）必须非空且是两个不下降序列。
大小根据比较函数less(aux)判断。

static void
inplace_merge (struct list_elem *a0, struct list_elem *a1b0,
               struct list_elem *b1,
               list_less_func *less, void *aux);

list_sort()

将链表排好序。利用归并排序，复杂度$O(n\log n)$。
大小根据比较函数less(aux)判断。

void list_sort (struct list *list, list_less_func *less, void *aux);

list_insert_ordered()

在链表的第一个比当前元素小的位置前插入一个元素。没有则插到最后。
复杂度$O(n)$。
大小根据比较函数less(aux)判断。

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

list_unique()

类似unique()，将第一次出现的元素放在链表最开始，重复出现的元素依次放到后面（不保证有序）。
大小根据比较函数less(aux)判断。

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

list_max()

返回链表中最大的元素。若有多个最大值，返回第一次出现的。若链表为空，返回链表尾部。
大小根据比较函数less(aux)判断。

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

list_min()

返回链表中最小的元素。若有多个最小值，返回第一次出现的。若链表为空，返回链表尾部。
大小根据比较函数less(aux)判断。

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