Generic radix trees/sparse arrays

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