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)

free all memory owned by a genradix

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