XOR Linked list
https://hackmd.io/@sysprog/linux2023-quiz1#測驗-3

Standard Doubly linked list

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};
struct item {                         
    uint16_t i;
    struct list_head list;
};

標準的 doubly linked list node 裡有 prev, next 的位址。
但有另一種 XOR linked list 用一個 link 可以表達雙向 linked list
XOR Linked List

複習基本的 XOR 操作

A^A = 0
A^0 = A
A^B = B^A
A = A^B^B

Example

add    1    2    3    4  
data  HAT  CAT  EAT  BAT
link   2    2    6    3 

2 = 1^3 link(CAT) = add(HAT) ^ add(EAT)
6 = 2^4 link(EAT) = add(CAT) ^ add(BAT)
2 = 1^ 3

要往下一格移動時，我們需要前一格在哪和這一格的位置。例如我們現在在 HAT (1), 已知前一格是 (0)，那麼下一格就是 link(1) XOR 0 = 2 XOR 0 = 2，也就是 CAT。繼續，現在位於 CAT (2)，前一格在 (1)，於是下一格就是 link(2) XOR 1 = 2 XOR 1 = 3，亦即 EAT，依此類推。只要當找出來的下一格是 (0) 就結束。

link(CAT) = add(HAT) ^ add(EAT)
add(EAT) = add(HAT) ^ add(HAT) ^ add(EAT)
         = link(CAT) ^ add(EAT)

實作

考慮一個 xor_list_t 代表整條 list

typedef struct _xor_list_struct {
    xor_node_t head, tail;
    uint32_t count;
} xor_list_t;

xor_node_t 代表單一個 node

typedef struct _xorlist_node {
    struct _xorlist_node *cmp;//just one pointer
} xor_node_t;

有趣的是，這裡的用來放在 list 的 node 跟存資料的 node 會分成兩個資料結構

struct test_node {
    int value;
    xor_node_t xornode;
};

traverse

//rp previous
//rn next
#define xorlist_for_each(node, rp, rn, list)                        \
    for (rp = &(list)->head, node = rp->cmp; node != &(list)->tail; \
        rn = address_of(rp, node->cmp), rp = node, node = rn)

xor_list_t list;
xor_node_t *real_prev, *real_next, *node;
int i = 0;
printf("xorlist_for_each test\n");
xorlist_for_each(node, real_prev, real_next, &list)
{
    printf("node [%d] %d\n", i++,
        container_of(node, struct test_node, xornode)->value);
}

for (int i = 0; i < 1000; i++) {
    struct test_node *new = malloc(sizeof(struct test_node));
    xornode_init(&new->xornode);
    new->value = i;
    xorlist_add(&list, &new->xornode);
}

insert

// add n to list head
int xorlist_add(xor_list_t *list, xor_node_t *n)
{
    if (!n)
        return ENOMEM;

    xor_node_t *real_prev = &list->head;
    xor_node_t *real_next = real_prev->cmp; // real_prev->cmp = 0 ^ real_next = real_next 

    real_prev->cmp = n; //real_prev->cmp = 0 ^ n
    n->cmp = XOR_COMP(real_prev, real_next);
    real_next->cmp = XOR_COMP(n, XOR_COMP(real_prev, real_next->cmp));
    //XOR_COMP(real_prev, real_next->cmp) would be B->next
    list->count++;

    return 0;
}

delete

給定要刪除節點的前一個節點 n 、要刪除的節點 target

int xorlist_del(xor_list_t *list,
                xor_node_t *n,
                xor_node_t *target,
                int (*delete_func)(xor_node_t *))
{
    assert(list && n && target && delete_func);
    assert(&list->head != target && &list->tail != target);
    xor_node_t *nn = address_of(target, n->cmp);//上上個節點
    xor_node_t *an = address_of(n, target->cmp);//下個節點
    xor_node_t *ana = address_of(target, an->cmp);//下下個節點
    n->cmp = XOR_COMP(nn, an);
    an->cmp = XOR_COMP(n, ana);
    delete_func(target);
    list->count--;

    return 0;
}

/*
0 1 2
3 4 5
6 7 8
*/


0   1  2  3
4   5  6  7
8   9 10 11
12 13 14 15

$A={\int }_{-r}^r\sqrt{r^2-x^2}dx$