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_mtrie_16_ply_t_
struct	ip4_mtrie_8_ply_t_
	One ply of the 4 ply mtrie fib. More...
struct	ip4_mtrie_16_t
	The mutiway-TRIE with a 16-8-8 stride. More...
struct	ip4_mtrie_8_t
	The mutiway-TRIE with a 8-8-8-8 stride. More...

Macros
#define	IP4_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_mtrie_leaf_t
typedef struct ip4_mtrie_16_ply_t_	ip4_mtrie_16_ply_t
typedef struct ip4_mtrie_8_ply_t_	ip4_mtrie_8_ply_t
	One ply of the 4 ply mtrie fib. More...

Functions
	STATIC_ASSERT (0==sizeof(ip4_mtrie_8_ply_t) % CLIB_CACHE_LINE_BYTES, "IP4 Mtrie ply cache line")
void	ip4_mtrie_16_init (ip4_mtrie_16_t *m)
	Initialise an mtrie. More...
void	ip4_mtrie_8_init (ip4_mtrie_8_t *m)
void	ip4_mtrie_16_free (ip4_mtrie_16_t *m)
	Free an mtrie, It must be empty when free'd. More...
void	ip4_mtrie_8_free (ip4_mtrie_8_t *m)
void	ip4_mtrie_16_route_add (ip4_mtrie_16_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_mtrie_8_route_add (ip4_mtrie_8_t *m, const ip4_address_t *dst_address, u32 dst_address_length, u32 adj_index)
void	ip4_mtrie_16_route_del (ip4_mtrie_16_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...
void	ip4_mtrie_8_route_del (ip4_mtrie_8_t *m, const ip4_address_t *dst_address, u32 dst_address_length, u32 adj_index, u32 cover_address_length, u32 cover_adj_index)
uword	ip4_mtrie_16_memory_usage (ip4_mtrie_16_t *m)
	return the memory used by the table More...
uword	ip4_mtrie_8_memory_usage (ip4_mtrie_8_t *m)
static u32	ip4_mtrie_leaf_is_terminal (ip4_mtrie_leaf_t n)
	Is the leaf terminal (i.e. More...
static u32	ip4_mtrie_leaf_get_adj_index (ip4_mtrie_leaf_t n)
	From the stored slot value extract the LB index value. More...
static ip4_mtrie_leaf_t	ip4_mtrie_16_lookup_step (ip4_mtrie_leaf_t current_leaf, const ip4_address_t *dst_address, u32 dst_address_byte_index)
	Lookup step. More...
static ip4_mtrie_leaf_t	ip4_mtrie_16_lookup_step_one (const ip4_mtrie_16_t *m, const ip4_address_t *dst_address)
	Lookup step number 1. More...
static ip4_mtrie_leaf_t	ip4_mtrie_8_lookup_step (ip4_mtrie_leaf_t current_leaf, const ip4_address_t *dst_address, u32 dst_address_byte_index)
static ip4_mtrie_leaf_t	ip4_mtrie_8_lookup_step_one (const ip4_mtrie_8_t *m, const ip4_address_t *dst_address)

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

Macro Definition Documentation

IP4_MTRIE_LEAF_EMPTY

#define IP4_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_mtrie_16_ply_t

typedef struct ip4_mtrie_16_ply_t_ ip4_mtrie_16_ply_t

ip4_mtrie_8_ply_t

typedef struct ip4_mtrie_8_ply_t_ ip4_mtrie_8_ply_t

One ply of the 4 ply mtrie fib.

ip4_mtrie_leaf_t

typedef u32 ip4_mtrie_leaf_t

Definition at line 52 of file ip4_mtrie.h.

Function Documentation

ip4_mtrie_16_free()

void ip4_mtrie_16_free

(

ip4_mtrie_16_t *

m

)

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

Definition at line 189 of file ip4_mtrie.c.

Here is the caller graph for this function:

ip4_mtrie_16_init()

void ip4_mtrie_16_init

(

ip4_mtrie_16_t *

m

)

Initialise an mtrie.

Definition at line 205 of file ip4_mtrie.c.

Here is the caller graph for this function:

ip4_mtrie_16_lookup_step()

static ip4_mtrie_leaf_t ip4_mtrie_16_lookup_step ( ip4_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 220 of file ip4_mtrie.h.

Here is the call graph for this function:

ip4_mtrie_16_lookup_step_one()

static ip4_mtrie_leaf_t ip4_mtrie_16_lookup_step_one ( const ip4_mtrie_16_t *  m, const ip4_address_t *  dst_address  )

inlinestatic

Lookup step number 1.

Processes 2 bytes of 4 byte ip4 address.

Definition at line 241 of file ip4_mtrie.h.

ip4_mtrie_16_memory_usage()

uword ip4_mtrie_16_memory_usage

(

ip4_mtrie_16_t *

m

)

return the memory used by the table

Definition at line 731 of file ip4_mtrie.c.

ip4_mtrie_16_route_add()

void ip4_mtrie_16_route_add	(	ip4_mtrie_16_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 636 of file ip4_mtrie.c.

Here is the caller graph for this function:

ip4_mtrie_16_route_del()

void ip4_mtrie_16_route_del	(	ip4_mtrie_16_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 670 of file ip4_mtrie.c.

Here is the caller graph for this function:

ip4_mtrie_8_free()

void ip4_mtrie_8_free

(

ip4_mtrie_8_t *

m

)

Definition at line 211 of file ip4_mtrie.c.

Here is the caller graph for this function:

ip4_mtrie_8_init()

void ip4_mtrie_8_init

(

ip4_mtrie_8_t *

m

)

Definition at line 231 of file ip4_mtrie.c.

Here is the caller graph for this function:

ip4_mtrie_8_lookup_step()

static ip4_mtrie_leaf_t ip4_mtrie_8_lookup_step ( ip4_mtrie_leaf_t  current_leaf, const ip4_address_t *  dst_address, u32  dst_address_byte_index  )

inlinestatic

Definition at line 252 of file ip4_mtrie.h.

Here is the call graph for this function:

Here is the caller graph for this function:

ip4_mtrie_8_lookup_step_one()

static ip4_mtrie_leaf_t ip4_mtrie_8_lookup_step_one ( const ip4_mtrie_8_t *  m, const ip4_address_t *  dst_address  )

inlinestatic

Definition at line 270 of file ip4_mtrie.h.

Here is the caller graph for this function:

ip4_mtrie_8_memory_usage()

uword ip4_mtrie_8_memory_usage

(

ip4_mtrie_8_t *

m

)

Definition at line 746 of file ip4_mtrie.c.

ip4_mtrie_8_route_add()

void ip4_mtrie_8_route_add	(	ip4_mtrie_8_t *	m,
		const ip4_address_t *	dst_address,
		u32	dst_address_length,
		u32	adj_index
	)

Definition at line 652 of file ip4_mtrie.c.

Here is the caller graph for this function:

ip4_mtrie_8_route_del()

void ip4_mtrie_8_route_del	(	ip4_mtrie_8_t *	m,
		const ip4_address_t *	dst_address,
		u32	dst_address_length,
		u32	adj_index,
		u32	cover_address_length,
		u32	cover_adj_index
	)

Definition at line 690 of file ip4_mtrie.c.

Here is the caller graph for this function:

ip4_mtrie_leaf_get_adj_index()

static u32 ip4_mtrie_leaf_get_adj_index ( ip4_mtrie_leaf_t  n )

inlinestatic

From the stored slot value extract the LB index value.

Definition at line 210 of file ip4_mtrie.h.

Here is the call graph for this function:

Here is the caller graph for this function:

ip4_mtrie_leaf_is_terminal()

static u32 ip4_mtrie_leaf_is_terminal ( ip4_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 201 of file ip4_mtrie.h.

Here is the caller graph for this function:

STATIC_ASSERT()

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

Variable Documentation

format_ip4_mtrie_16

format_function_t format_ip4_mtrie_16

Format/display the contents of the mtrie.

Definition at line 189 of file ip4_mtrie.h.

format_ip4_mtrie_8

format_function_t format_ip4_mtrie_8

Definition at line 190 of file ip4_mtrie.h.

ip4_ply_pool

ip4_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.