38 lines
2.6 KiB
Markdown
38 lines
2.6 KiB
Markdown
# Radix trees subsystem
|
|
|
|
## Introduction
|
|
|
|
The memory subsystem require a capable radix trees to unleash the full power of the Pez allocator. It's defined inside `shelter/lib/include/memory/pez/radix.h` and implemented inside `shelter/lib/src/memory/pez/radix.c`.
|
|
|
|
## Overview
|
|
|
|
In Shelter, the radix nodes are 128 bytes wide, capable of storing 16 `sh_uint64` values. This mean all radix trees have a 16 fanout, they filter 4 bits per level, and require 16 levels for 64 bits keys and 8 levels for 32 bits keys.
|
|
|
|
The node is defined by this sructure:
|
|
``` C
|
|
typedef struct {
|
|
sh_page_VIRTUAL_ADDRESS ptr[16];
|
|
} sh_radix_NODE;
|
|
```
|
|
|
|
A radix tree is defined into the following structure:
|
|
``` C
|
|
typedef struct {
|
|
sh_radix_NODE *root_node;
|
|
sh_uint8 depth;
|
|
} sh_radix_TREE;
|
|
```
|
|
|
|
The API for modifying nodes is as follow:
|
|
- `SH_STATUS sh_radix_node_read_value(sh_radix_NODE *node,sh_uint8 index,sh_page_VIRTUAL_ADDRESS* value)`: read a value from the node at the following index
|
|
- `SH_STATUS sh_radix_node_set_value(struct sh_slab_radix_node_SLAB_ALLOCATOR *alloc,sh_radix_NODE *node,sh_uint8 index,sh_page_VIRTUAL_ADDRESS value)`: set the value inside the node at the provided node
|
|
|
|
The API for manipulating radix trees is as follow:
|
|
- `SH_STATUS sh_radix_tree_init(struct sh_slab_radix_node_SLAB_ALLOCATOR *alloc,sh_page_PAGE_TABLE_POOL *ptp,sh_radix_TREE *tree,sh_uint8 depth)`: initialize a radix tree, fail if depth is greater than 16. Allocate the root node
|
|
- `SH_STATUS sh_radix_tree_get_value(sh_radix_TREE *tree,sh_uint64 key,sh_page_VIRTUAL_ADDRESS *value)`: search in a straight line inside the tree to provide the associated value of a key. Stop and return `SH_STATUS_NOT_FOUND` as soon as it hit an empty pointer where there should be one
|
|
- `SH_STATUS sh_radix_tree_insert_value(struct sh_slab_radix_node_SLAB_ALLOCATOR *alloc,sh_page_PAGE_TABLE_POOL *ptp,sh_radix_TREE *tree,sh_uint64 key,sh_page_VIRTUAL_ADDRESS value)`: insert a value associated with a key inside the tree. Can allocates new nodes and overwrite previously setted value.
|
|
- `SH_STATUS sh_radix_tree_delete_value(struct sh_slab_radix_node_SLAB_ALLOCATOR *alloc,sh_radix_TREE *tree,sh_uint64 key)`: delete a vale and deallocates all nodes (including leaf) that form a path to the leaf if the deletion make them empty
|
|
- `SH_STATUS sh_radix_tree_search_smallest_min_bound(struct sh_slab_radix_node_SLAB_ALLOCATOR *alloc,sh_radix_TREE *tree,sh_uint64 lower_bound_key,sh_page_VIRTUAL_ADDRESS *value)`: backtracking algorithm used to quickly search the value with a key equal or greater than the provided key. Can't allocate new nodes
|
|
|
|
The radix trees subsystem uses the same slab allocator for all radix trees.
|