Generic radix trees/sparse arrays¶
Very simple and minimalistic, supporting arbitrary size entries up to PAGE_SIZE.
A genradix is defined with the type it will store, like so:
static GENRADIX(struct foo) foo_genradix;
The main operations are:
- genradix_init(radix) - initialize an empty genradix
- genradix_free(radix) - free all memory owned by the genradix and reinitialize it
- genradix_ptr(radix, idx) - gets a pointer to the entry at idx, returning NULL if that entry does not exist
- genradix_ptr_alloc(radix, idx, gfp) - gets a pointer to an entry, allocating it if necessary
- genradix_for_each(radix, iter, p) - iterate over each entry in a genradix
The radix tree allocates one page of entries at a time, so entries may exist that were never explicitly allocated - they will be initialized to all zeroes.
Internally, a genradix is just a radix tree of pages, and indexing works in terms of byte offsets. The wrappers in this header file use sizeof on the type the radix contains to calculate a byte offset from the index - see __idx_to_offset.
generic radix tree functions¶
-
genradix_init(_radix)¶ initialize a genradix
Parameters
_radix- genradix to initialize
Description
Does not fail
-
genradix_free(_radix)¶
Parameters
_radix- the genradix to free
Description
After freeing, _radix will be reinitialized and empty
-
genradix_ptr(_radix, _idx)¶ get a pointer to a genradix entry
Parameters
_radix- genradix to access
_idx- index to fetch
Description
Returns a pointer to entry at _idx, or NULL if that entry does not exist.
-
genradix_ptr_alloc(_radix, _idx, _gfp)¶ get a pointer to a genradix entry, allocating it if necessary
Parameters
_radix- genradix to access
_idx- index to fetch
_gfp- gfp mask
Description
Returns a pointer to entry at _idx, or NULL on allocation failure
-
genradix_iter_init(_radix, _idx)¶ initialize a genradix_iter
Parameters
_radix- genradix that will be iterated over
_idx- index to start iterating from
-
genradix_iter_peek(_iter, _radix)¶ get first entry at or above iterator’s current position
Parameters
_iter- a genradix_iter
_radix- genradix being iterated over
Description
If no more entries exist at or above _iter’s current position, returns NULL
-
genradix_for_each(_radix, _iter, _p)¶ iterate over entry in a genradix
Parameters
_radix- genradix to iterate over
_iter- a genradix_iter to track current position
_p- pointer to genradix entry type
Description
On every iteration, _p will point to the current entry, and _iter.pos will be the current entry’s index.
-
genradix_prealloc(_radix, _nr, _gfp)¶ preallocate entries in a generic radix tree
Parameters
_radix- genradix to preallocate
_nr- number of entries to preallocate
_gfp- gfp mask
Description
Returns 0 on success, -ENOMEM on failure