The kernel manages collections of data using the following high level concepts:

• Map - Name/value map. Name is some key, natively an integer value (pointer sized), but also supports pointers to allow arbitrary formatted keys with the appropriate user provided comparison function. Values are again natively an integer value (pointer sized), and again can be used as pointers to point to arbitrary values. * Linked list - Simple doubly linked lists, using intrusive prev/next data pointers in the data structure being listed.

Map interface

The map interface defines an abstract name/value based dictionary, to allow the storage and lookup of a value keyed by name.

The basic operations of a map are:

• Put - Insert a value by name, returning the previous value, if any.
• Get - Given a name, lookup and return the corresponding value.
• Remove - Delete a value by name, returning the previous value, if any.

The map also provides operations to:

• Walk - Iterate each item.
• Size - Return the number of items currently mapped.
• Optimize - Implementation specific optimisations.

Implementations

Tree map

The tree map implements a binary search tree (BST) implementation of map. At it's most basic level,

Luser_start: box "0x00100085" "user_start" fit
Lheader: box at 1 sw of Luser_start "0x00100020" "header"  fit
move
Lmultiboot_mmap: box at 1 se of Luser_start "0x001000a8" "multiboot_mmap" fit
L_start: box at 1 se of Lheader "0x00100050" "_start" fit
Lmultiboot_mod: box at 1 se of Lmultiboot_mmap "0x001000e5" "multiboot_mod" fit

arrow from Luser_start.s to Lheader.n "left"
arrow from Luser_start.s to Lmultiboot_mmap.n "right"
arrow from Lheader.s to L_start.n "right"
arrow from Lmultiboot_mmap.s to Lmultiboot_mod.n "right"

Vector map

Vector map operates like an array, with the key selecting a value by ordinal position.