Electroneum
addrtree.h File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  addrtree
 
struct  addrnode
 
struct  addredge
 

Macros

#define KEYWIDTH   8
 

Typedefs

typedef uint8_t addrlen_t
 
typedef uint8_t addrkey_t
 

Functions

size_t addrtree_size (const struct addrtree *tree)
 
struct addrtreeaddrtree_create (addrlen_t max_depth, void(*delfunc)(void *, void *), size_t(*sizefunc)(void *), void *env, unsigned int max_node_count)
 
void addrtree_delete (struct addrtree *tree)
 
void addrtree_insert (struct addrtree *tree, const addrkey_t *addr, addrlen_t sourcemask, addrlen_t scope, void *elem, time_t ttl, time_t now)
 
struct addrnodeaddrtree_find (struct addrtree *tree, const addrkey_t *addr, addrlen_t sourcemask, time_t now)
 
int unittest_wrapper_addrtree_cmpbit (const addrkey_t *key1, const addrkey_t *key2, addrlen_t n)
 
addrlen_t unittest_wrapper_addrtree_bits_common (const addrkey_t *s1, addrlen_t l1, const addrkey_t *s2, addrlen_t l2, addrlen_t skip)
 
int unittest_wrapper_addrtree_getbit (const addrkey_t *addr, addrlen_t addrlen, addrlen_t n)
 
int unittest_wrapper_addrtree_issub (const addrkey_t *s1, addrlen_t l1, const addrkey_t *s2, addrlen_t l2, addrlen_t skip)
 

Detailed Description

The addrtree is a radix tree designed for edns subnet. Most notable is the addition of 'scope' to a node. Scope is only relevant for nodes with elem set, it indicates the number of bits the authority desires.

For retrieving data one needs an address and address length (sourcemask). While traversing the tree the first matching node is returned. A node matches when node.scope<=sourcemask && node.elem!=NULL (This is the most specific answer the authority has.) or node.sourcemask==sourcemask && node.elem!=NULL (This is the most specific question the client can ask.)

Insertion needs an address, sourcemask and scope. The length of the address is capped by min(sourcemask, scope). While traversing the tree the scope of all visited nodes is updated. This ensures we are always able to find the most specific answer available.

Definition in file addrtree.h.

Macro Definition Documentation

◆ KEYWIDTH

#define KEYWIDTH   8

Definition at line 63 of file addrtree.h.

Typedef Documentation

◆ addrkey_t

typedef uint8_t addrkey_t

Definition at line 62 of file addrtree.h.

◆ addrlen_t

typedef uint8_t addrlen_t

Definition at line 61 of file addrtree.h.

Function Documentation

◆ addrtree_create()

struct addrtree* addrtree_create ( addrlen_t  max_depth,
void(*)(void *, void *)  delfunc,
size_t(*)(void *)  sizefunc,
void *  env,
unsigned int  max_node_count 
)

Create a new tree.

Parameters
max_depthTree will cap keys to this length.
delfuncf(element, env) delete element.
sizefuncf(element) returning the size of element.
envModule environment for alloc information.
max_node_countMaximum size of this data structure in nodes. 0 for unlimited.
Returns
new addrtree or NULL on failure.

◆ addrtree_delete()

void addrtree_delete ( struct addrtree tree)

Free tree and all nodes below.

Parameters
treeTree to be freed.

◆ addrtree_find()

struct addrnode* addrtree_find ( struct addrtree tree,
const addrkey_t addr,
addrlen_t  sourcemask,
time_t  now 
)

Find a node containing an element in the tree.

Parameters
treeTree to search.
addrkey for element lookup.
sourcemaskLength of addr in bits.
nowCurrent time in seconds.
Returns
addrnode or NULL on miss.

◆ addrtree_insert()

void addrtree_insert ( struct addrtree tree,
const addrkey_t addr,
addrlen_t  sourcemask,
addrlen_t  scope,
void *  elem,
time_t  ttl,
time_t  now 
)

Insert an element in the tree. Failures are silent. Sourcemask and scope might be changed according to local policy. Caller should no longer access elem, it could be free'd now or later during future inserts.

Parameters
treeTree insert elem in.
addrkey for element lookup.
sourcemaskLength of addr in bits.
scopeNumber of significant bits in addr.
elemdata to store in the tree.
ttlelem is valid up to this time, seconds.
nowCurrent time in seconds.

◆ addrtree_size()

size_t addrtree_size ( const struct addrtree tree)

Size of tree in bytes.

Parameters
treeTree.
Returns
size of tree in bytes.

◆ unittest_wrapper_addrtree_bits_common()

addrlen_t unittest_wrapper_addrtree_bits_common ( const addrkey_t s1,
addrlen_t  l1,
const addrkey_t s2,
addrlen_t  l2,
addrlen_t  skip 
)

◆ unittest_wrapper_addrtree_cmpbit()

int unittest_wrapper_addrtree_cmpbit ( const addrkey_t key1,
const addrkey_t key2,
addrlen_t  n 
)

Wrappers for static functions to unit test

◆ unittest_wrapper_addrtree_getbit()

int unittest_wrapper_addrtree_getbit ( const addrkey_t addr,
addrlen_t  addrlen,
addrlen_t  n 
)

◆ unittest_wrapper_addrtree_issub()

int unittest_wrapper_addrtree_issub ( const addrkey_t s1,
addrlen_t  l1,
const addrkey_t s2,
addrlen_t  l2,
addrlen_t  skip 
)