Data structures: linked 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