Singly Linked List

Linked List 是程式常見的資料結構，通常是指 Double Linked List (如 linux/list.h)，但這裡說 Singly Linked List。

Singly linked list 第一個 node 透過 head 指標存取，每個 node 有一個 next 指標串下個 node，最後 node (稱為 tail) 的next 為 nil。

移除 node

typedef struct list {
    item *head;
} list;

static inline item **ll_find(list *list, item *node)
{
    item **pp = &list->head;
    while(*pp != node)
        pp = &(*pp)->next;
    return pp;
}

void ll_remove(list *list, item *node)
{
    item **pp = ll_find(list, node);
    *pp = node->next;
}

• https://github.com/mkirchner/linked-list-good-taste：傳統用 prev 和 cur 指標，這裡用 ndirect pointer 是指到 node pointer 的 pointer，可用來移除一個 node (remove 只是將 node 脫離 list，而 delete 還包括抹除) 和在 node 之前插入一個 node。

如果作為 FIFO 常常需要將 node 放到 tail，額外紀錄 tail 指標：

typedef struct list {
    item *head;
    item *tail;
} list;

// 先準備好 node, node->next = null;
void ll_insert_tail(list *list, item *node)
{
    if (list->tail)
        list->tail->next = node; // 避免 node 加入時，tail 剛好刪除
    else
        list->head = node;
    list->tail = node;
}

item *ll_remove_head(list *list)
{
    item *node = list->head;
    list->head = node->next;
    if (list->tail == node)
        list->tail = NULL;
    return node;
}

lock-free linked list 用在 concurrent 環境：兩個或以上 thread 執行操作不干擾彼此間的工作。

基本操作有兩個

1. 插入 node p 之後
2. 移除 node p 之後那個 node
   

// compare and swap
void *cas(void **addr, void *old, void *new)
{
    void *value = ∗addr
    if (value == old)
        ∗add = new
    return value;
}

void ll_insert_after(item *p, item *n)
{
    do {
        item *next = p->next;
        n->next = next;
    } while (cas(address-of(p->next), next, n));
}

itme *ll_remove_after(item *p)
{
}

問題：如何確認某個 node 是否有其它 thread 仍在使用？例如 thread A 停在 node n (可能搜尋一半，或其它)，此時 thread B 移除 node n 並釋出記憶體，會造成 thread A 問題

問題
cache unfriendly

https://en.wikipedia.org/wiki/Non-blocking_linked_list
https://ithelp.ithome.com.tw/articles/10214944
https://gcc.gnu.org/onlinedocs/gcc-4.1.0/gcc/Atomic-Builtins.html

Circular doubly linked list