XOR Linked list
https://hackmd.io/@sysprog/linux2023-quiz1#測驗-3
Standard Doubly linked list
```c
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
```c
typedef struct _xor_list_struct {
xor_node_t head, tail;
uint32_t count;
} xor_list_t;
```
xor_node_t 代表單一個 node
```c
typedef struct _xorlist_node {
struct _xorlist_node *cmp;//just one pointer
} xor_node_t;
```
有趣的是，這裡的用來放在 list 的 node 跟存資料的 node 會分成兩個資料結構
```c
struct test_node {
int value;
xor_node_t xornode;
};
```
### traverse
```c
//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)
```
```c
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);
}
```
```graphviz
digraph list {
rankdir=LR;
node[shape=record, style=bold];
null[label=null][shape=plaintext]
subgraph cluster_0 {
node [shape=record];
head [label="{head}"];
tail [label="{tail}"];
count [label="count"][shape=plaintext];
style=bold;
label=list
}
subgraph cluster_1 {
label="new node 1"
value[label=value]
xornode[label="<label>xornode|{<cmp>cmp}" ]
}
subgraph cluster_2 {
label="new node 2"
value2[label=value]
xornode2[label="<label>xornode|{<cmp>cmp}" ]
}
head->xornode:label
xornode:cmp->xornode2:label
xornode2:cmp->null
}
```
```c
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
```c
// 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;
}
```
```graphviz
digraph list {
rankdir=LR;
node[shape=record, style=bold];
head[label="A|{<cmp>cmp=B}"];
tail[label="B|{<cmp>cmp=C}"];
node1[label="C|{<cmp>cmp=A ^ B}"]
n[label="n"][shape=plaintext]
rn[label="real_next"][shape=plaintext]
rp[label="real_prev"][shape=plaintext]
head:cmp->node1:cmp[dir=both]
node1:cmp->tail:cmp[dir=both]
n->node1
rn->tail
rp->head
}
```
### delete
給定要刪除節點的前一個節點 n 、要刪除的節點 target
```c
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$
Sign in with Wallet
Connect another wallet