Data structures: linked list
| The node | |
| Walking the list | |
| Building the list |
The node
A linked-list node is a value plus a pointer to the next node, or zero for the end. With qwords, the layout is 8 bytes of value and 8 bytes of pointer:
NODE_VAL equ 0
NODE_NEXT equ 8
NODE_SIZE equ 16
Walking the list
Start at the head pointer and follow NODE_NEXT until it is zero. Each step is one load, so the walk is memory-bound: nodes scattered in memory defeat the prefetcher, which is why arrays usually beat lists.
mov rsi, [head]
walk:
test rsi, rsi
jz done
mov rax, [rsi + NODE_VAL]
; ... use rax ...
mov rsi, [rsi + NODE_NEXT]
jmp walk
Building the list
Allocate nodes with sys_brk (12) or mmap (9), store the value at NODE_VAL and the old head at NODE_NEXT, then store the new node in head. That push-at-front builds the list in one pass, in reverse order.
Next: A tiny HTTP server
Article author: Arthur Isaev