ip4_mtrie.h File Reference

Include dependency graph for ip4_mtrie.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	ip4_fib_mtrie_16_ply_t_
struct	ip4_fib_mtrie_8_ply_t_
	One ply of the 4 ply mtrie fib. More...
struct	ip4_fib_mtrie_t
	The mutiway-TRIE. More...

Macros
#define	IP4_FIB_MTRIE_LEAF_EMPTY   (1 + 2*0)
#define	PLY_16_SIZE   (1<<16)
	the 16 way stride that is the top PLY of the mtrie We do not maintain the count of 'real' leaves in this PLY, since it is never removed. More...

Typedefs
typedef u32	ip4_fib_mtrie_leaf_t
typedef struct ip4_fib_mtrie_16_ply_t_	ip4_fib_mtrie_16_ply_t
typedef struct ip4_fib_mtrie_8_ply_t_	ip4_fib_mtrie_8_ply_t
	One ply of the 4 ply mtrie fib. More...

Functions
	STATIC_ASSERT (0==sizeof(ip4_fib_mtrie_8_ply_t) % CLIB_CACHE_LINE_BYTES, "IP4 Mtrie ply cache line")
void	ip4_mtrie_init (ip4_fib_mtrie_t *m)
	Initialise an mtrie. More...
void	ip4_mtrie_free (ip4_fib_mtrie_t *m)
	Free an mtrie, It must be emty when free'd. More...
void	ip4_fib_mtrie_route_add (ip4_fib_mtrie_t *m, const ip4_address_t *dst_address, u32 dst_address_length, u32 adj_index)
	Add a route/entry to the mtrie. More...
void	ip4_fib_mtrie_route_del (ip4_fib_mtrie_t *m, const ip4_address_t *dst_address, u32 dst_address_length, u32 adj_index, u32 cover_address_length, u32 cover_adj_index)
	remove a route/entry to the mtrie More...
uword	ip4_fib_mtrie_memory_usage (ip4_fib_mtrie_t *m)
	return the memory used by the table More...
static u32	ip4_fib_mtrie_leaf_is_terminal (ip4_fib_mtrie_leaf_t n)
	Is the leaf terminal (i.e. More...
static u32	ip4_fib_mtrie_leaf_get_adj_index (ip4_fib_mtrie_leaf_t n)
	From the stored slot value extract the LB index value. More...
static ip4_fib_mtrie_leaf_t	ip4_fib_mtrie_lookup_step (const ip4_fib_mtrie_t *m, ip4_fib_mtrie_leaf_t current_leaf, const ip4_address_t *dst_address, u32 dst_address_byte_index)
	Lookup step. More...
static ip4_fib_mtrie_leaf_t	ip4_fib_mtrie_lookup_step_one (const ip4_fib_mtrie_t *m, const ip4_address_t *dst_address)
	Lookup step number 1. More...

Variables
format_function_t	format_ip4_fib_mtrie
	Format/display the contents of the mtrie. More...
ip4_fib_mtrie_8_ply_t *	ip4_ply_pool
	A global pool of 8bit stride plys. More...

Macro Definition Documentation

IP4_FIB_MTRIE_LEAF_EMPTY

#define IP4_FIB_MTRIE_LEAF_EMPTY   (1 + 2*0)

Definition at line 54 of file ip4_mtrie.h.

PLY_16_SIZE

#define PLY_16_SIZE   (1<<16)

the 16 way stride that is the top PLY of the mtrie We do not maintain the count of 'real' leaves in this PLY, since it is never removed.

The FIB will destroy the mtrie and the ply once the FIB is destroyed.

Definition at line 62 of file ip4_mtrie.h.

Typedef Documentation

ip4_fib_mtrie_16_ply_t

typedef struct ip4_fib_mtrie_16_ply_t_ ip4_fib_mtrie_16_ply_t

ip4_fib_mtrie_8_ply_t

typedef struct ip4_fib_mtrie_8_ply_t_ ip4_fib_mtrie_8_ply_t

One ply of the 4 ply mtrie fib.

ip4_fib_mtrie_leaf_t

typedef u32 ip4_fib_mtrie_leaf_t

Definition at line 52 of file ip4_mtrie.h.

Function Documentation

ip4_fib_mtrie_leaf_get_adj_index()

static u32 ip4_fib_mtrie_leaf_get_adj_index ( ip4_fib_mtrie_leaf_t  n )

inlinestatic

From the stored slot value extract the LB index value.

Definition at line 192 of file ip4_mtrie.h.

Here is the call graph for this function:

Here is the caller graph for this function:

ip4_fib_mtrie_leaf_is_terminal()

static u32 ip4_fib_mtrie_leaf_is_terminal ( ip4_fib_mtrie_leaf_t  n )

inlinestatic

Is the leaf terminal (i.e.

an LB index) or non-terminal (i.e. a PLY index)

Definition at line 183 of file ip4_mtrie.h.

Here is the caller graph for this function:

ip4_fib_mtrie_lookup_step()

static ip4_fib_mtrie_leaf_t ip4_fib_mtrie_lookup_step ( const ip4_fib_mtrie_t *  m, ip4_fib_mtrie_leaf_t  current_leaf, const ip4_address_t *  dst_address, u32  dst_address_byte_index  )

inlinestatic

Lookup step.

Processes 1 byte of 4 byte ip4 address.

Definition at line 202 of file ip4_mtrie.h.

Here is the call graph for this function:

Here is the caller graph for this function:

ip4_fib_mtrie_lookup_step_one()

static ip4_fib_mtrie_leaf_t ip4_fib_mtrie_lookup_step_one ( const ip4_fib_mtrie_t *  m, const ip4_address_t *  dst_address  )

inlinestatic

Lookup step number 1.

Processes 2 bytes of 4 byte ip4 address.

Definition at line 224 of file ip4_mtrie.h.

Here is the caller graph for this function:

ip4_fib_mtrie_memory_usage()

uword ip4_fib_mtrie_memory_usage

(

ip4_fib_mtrie_t *

m

)

return the memory used by the table

Definition at line 681 of file ip4_mtrie.c.

Here is the call graph for this function:

Here is the caller graph for this function:

ip4_fib_mtrie_route_add()

void ip4_fib_mtrie_route_add	(	ip4_fib_mtrie_t *	m,
		const ip4_address_t *	dst_address,
		u32	dst_address_length,
		u32	adj_index
	)

Add a route/entry to the mtrie.

Definition at line 624 of file ip4_mtrie.c.

Here is the call graph for this function:

Here is the caller graph for this function:

ip4_fib_mtrie_route_del()

void ip4_fib_mtrie_route_del	(	ip4_fib_mtrie_t *	m,
		const ip4_address_t *	dst_address,
		u32	dst_address_length,
		u32	adj_index,
		u32	cover_address_length,
		u32	cover_adj_index
	)

remove a route/entry to the mtrie

Definition at line 641 of file ip4_mtrie.c.

Here is the call graph for this function:

Here is the caller graph for this function:

ip4_mtrie_free()

void ip4_mtrie_free

(

ip4_fib_mtrie_t *

m

)

Free an mtrie, It must be emty when free'd.

Definition at line 199 of file ip4_mtrie.c.

Here is the call graph for this function:

Here is the caller graph for this function:

ip4_mtrie_init()

void ip4_mtrie_init

(

ip4_fib_mtrie_t *

m

)

Initialise an mtrie.

Definition at line 215 of file ip4_mtrie.c.

Here is the call graph for this function:

Here is the caller graph for this function:

STATIC_ASSERT()

STATIC_ASSERT	(	0	= =sizeof(ip4_fib_mtrie_8_ply_t) % CLIB_CACHE_LINE_BYTES,
		"IP4 Mtrie ply cache line"
	)

Variable Documentation

format_ip4_fib_mtrie

format_function_t format_ip4_fib_mtrie

Format/display the contents of the mtrie.

Definition at line 172 of file ip4_mtrie.h.

ip4_ply_pool

ip4_fib_mtrie_8_ply_t* ip4_ply_pool

A global pool of 8bit stride plys.

A global pool of 8bit stride plys.

Definition at line 48 of file ip4_mtrie.c.