#include "suricata-common.h"
#include "util-radix-tree.h"
#include "util-debug.h"
#include "util-error.h"
#include "util-ip.h"
#include "util-unittest.h"
#include "util-memcmp.h"
#include "util-byte.h"
#include "util-cidr.h"
#include "util-print.h"
#include "util-validate.h"

Include dependency graph for util-radix-tree.c:

Functions
SCRadixTree *	SCRadixCreateRadixTree (void(Free)(void ), void(PrintData)(void ))
	Creates a new Radix tree. More...

void	SCRadixReleaseRadixTree (SCRadixTree *tree)
	Frees a Radix tree and all its nodes. More...

SCRadixNode *	SCRadixAddKeyIPV4 (uint8_t key_stream, SCRadixTree tree, void *user)
	Adds a new IPV4 address to the Radix tree. More...

SCRadixNode *	SCRadixAddKeyIPV6 (uint8_t key_stream, SCRadixTree tree, void *user)
	Adds a new IPV6 address to the Radix tree. More...

SCRadixNode *	SCRadixAddKeyIPV4Netblock (uint8_t key_stream, SCRadixTree tree, void *user, uint8_t netmask)
	Adds a new IPV4 netblock to the Radix tree. More...

SCRadixNode *	SCRadixAddKeyIPV6Netblock (uint8_t key_stream, SCRadixTree tree, void *user, uint8_t netmask)
	Adds a new IPV6 netblock to the Radix tree. More...

bool	SCRadixAddKeyIPV4String (const char str, SCRadixTree tree, void *user)
	Adds a new IPV4/netblock to the Radix tree from a string. More...

bool	SCRadixAddKeyIPV6String (const char str, SCRadixTree tree, void *user)
	Adds a new IPV6/netblock to the Radix tree from a string. More...

void	SCRadixRemoveKeyGeneric (uint8_t key_stream, uint16_t key_bitlen, SCRadixTree tree)
	Removes a key from the Radix tree. More...

void	SCRadixRemoveKeyIPV4Netblock (uint8_t key_stream, SCRadixTree tree, uint8_t netmask)
	Removes an IPV4 address netblock key from the Radix tree. More...

void	SCRadixRemoveKeyIPV4 (uint8_t key_stream, SCRadixTree tree)
	Removes an IPV4 address key(not a netblock) from the Radix tree. Instead of using this function, we can also used SCRadixRemoveKeyIPV4Netblock(), by supplying a netmask value of 32. More...

void	SCRadixRemoveKeyIPV6Netblock (uint8_t key_stream, SCRadixTree tree, uint8_t netmask)
	Removes an IPV6 netblock address key from the Radix tree. More...

void	SCRadixRemoveKeyIPV6 (uint8_t key_stream, SCRadixTree tree)
	Removes an IPV6 address key(not a netblock) from the Radix tree. Instead of using this function, we can also used SCRadixRemoveKeyIPV6Netblock(), by supplying a netmask value of 128. More...

SCRadixNode *	SCRadixFindKeyIPV4ExactMatch (uint8_t key_stream, SCRadixTree tree, void **user_data_result)
	Checks if an IPV4 address is present in the tree. More...

SCRadixNode *	SCRadixFindKeyIPV4BestMatch (uint8_t key_stream, SCRadixTree tree, void **user_data_result)
	Checks if an IPV4 address is present in the tree under a netblock. More...

SCRadixNode *	SCRadixFindKeyIPV4Netblock (uint8_t key_stream, SCRadixTree tree, uint8_t netmask, void **user_data_result)
	Checks if an IPV4 Netblock address is present in the tree. More...

SCRadixNode *	SCRadixFindKeyIPV6Netblock (uint8_t key_stream, SCRadixTree tree, uint8_t netmask, void **user_data_result)
	Checks if an IPV6 Netblock address is present in the tree. More...

SCRadixNode *	SCRadixFindKeyIPV6ExactMatch (uint8_t key_stream, SCRadixTree tree, void **user_data_result)
	Checks if an IPV6 address is present in the tree. More...

SCRadixNode *	SCRadixFindKeyIPV6BestMatch (uint8_t key_stream, SCRadixTree tree, void **user_data_result)
	Checks if an IPV6 address is present in the tree under a netblock. More...

void	SCRadixPrintNodeInfo (SCRadixNode node, int level, void(PrintData)(void *))
	Prints the node information from a Radix tree. More...

void	SCRadixPrintTree (SCRadixTree *tree)
	Prints the Radix Tree. While printing the radix tree we use the following format. More...

void	SCRadixRegisterTests (void)

Detailed Description

Author: Anoop Saldanha anoop.nosp@m.sald.nosp@m.anha@.nosp@m.gmai.nosp@m.l.com

Implementation of radix trees

Definition in file util-radix-tree.c.

Function Documentation

◆ SCRadixAddKeyIPV4()

SCRadixNode* SCRadixAddKeyIPV4	(	uint8_t *	key_stream,
		SCRadixTree *	tree,
		void *	user
	)

Adds a new IPV4 address to the Radix tree.

Parameters

key_stream	Data that has to be added to the Radix tree. In this case a pointer to an IPV4 address
tree	Pointer to the Radix tree
user	Pointer to the user data that has to be associated with the key

Return values

node	Pointer to the newly created node

Definition at line 866 of file util-radix-tree.c.

◆ SCRadixAddKeyIPV4Netblock()

SCRadixNode* SCRadixAddKeyIPV4Netblock	(	uint8_t *	key_stream,
		SCRadixTree *	tree,
		void *	user,
		uint8_t	netmask
	)

Adds a new IPV4 netblock to the Radix tree.

Parameters

key_stream	Data that has to be added to the Radix tree. In this case a pointer to an IPV4 netblock
tree	Pointer to the Radix tree
user	Pointer to the user data that has to be associated with the key
netmask	The netmask (cidr) if we are adding a netblock

Return values

node	Pointer to the newly created node

Definition at line 948 of file util-radix-tree.c.

◆ SCRadixAddKeyIPV4String()

bool SCRadixAddKeyIPV4String	(	const char *	str,
		SCRadixTree *	tree,
		void *	user
	)

Adds a new IPV4/netblock to the Radix tree from a string.

Parameters

str	IPV4 string with optional /cidr netmask
tree	Pointer to the Radix tree
user	Pointer to the user data that has to be associated with the key

Return values

bool	true (false) if the node was (wasn't) added.

sc_errno is set:

SC_OK: Node added
SC_EEXIST: Node already exists
SC_EINVAL: Parameter value error

Definition at line 997 of file util-radix-tree.c.

References CIDRGet(), PrintInet(), SC_EINVAL, sc_errno, SCLogWarning, str, StringParseU8RangeCheck(), and strlcpy().

Here is the call graph for this function:

◆ SCRadixAddKeyIPV6()

SCRadixNode* SCRadixAddKeyIPV6	(	uint8_t *	key_stream,
		SCRadixTree *	tree,
		void *	user
	)

Adds a new IPV6 address to the Radix tree.

Parameters

key_stream	Data that has to be added to the Radix tree. In this case the pointer to an IPV6 address
tree	Pointer to the Radix tree
user	Pointer to the user data that has to be associated with the key

Return values

node	Pointer to the newly created node

Definition at line 885 of file util-radix-tree.c.

◆ SCRadixAddKeyIPV6Netblock()

SCRadixNode* SCRadixAddKeyIPV6Netblock	(	uint8_t *	key_stream,
		SCRadixTree *	tree,
		void *	user,
		uint8_t	netmask
	)

Adds a new IPV6 netblock to the Radix tree.

Parameters

key_stream	Data that has to be added to the Radix tree. In this case a pointer to an IPV6 netblock
tree	Pointer to the Radix tree
user	Pointer to the user data that has to be associated with the key
netmask	The netmask (cidr) if we are adding a netblock

Return values

node	Pointer to the newly created node

Definition at line 971 of file util-radix-tree.c.

◆ SCRadixAddKeyIPV6String()

bool SCRadixAddKeyIPV6String	(	const char *	str,
		SCRadixTree *	tree,
		void *	user
	)

Adds a new IPV6/netblock to the Radix tree from a string.

Parameters

str	IPV6 string with optional /cidr netmask
tree	Pointer to the Radix tree
user	Pointer to the user data that has to be associated with the key

Return values

bool	true (false) if the node was (wasn't) added. sc_errno is set: SC_OK: Node added SC_EEXIST: Node already exists SC_EINVAL: Parameter value error

Definition at line 1072 of file util-radix-tree.c.

References CIDRGetIPv6(), PrintInet(), SC_EINVAL, sc_errno, SCLogWarning, str, StringParseU8RangeCheck(), and strlcpy().

Here is the call graph for this function:

◆ SCRadixCreateRadixTree()

SCRadixTree* SCRadixCreateRadixTree	(	void()(void )	Free,
		void()(void )	PrintData
	)

Creates a new Radix tree.

Parameters

Free	Function pointer supplied by the user to be used by the Radix cleanup API to free the user supplied data

Return values

tree	The newly created radix tree on success

\initonly (all radix trees should be created at init)

Definition at line 424 of file util-radix-tree.c.

References FatalError, SCRadixTree_::Free, SCRadixTree_::PrintData, and SCMalloc.

Referenced by IPOnlyInit().

Here is the caller graph for this function:

◆ SCRadixFindKeyIPV4BestMatch()

SCRadixNode* SCRadixFindKeyIPV4BestMatch	(	uint8_t *	key_stream,
		SCRadixTree *	tree,
		void **	user_data_result
	)

Checks if an IPV4 address is present in the tree under a netblock.

Parameters

key_stream	Data that has to be found in the Radix tree. In this case an IPV4 address
tree	Pointer to the Radix tree instance

Definition at line 1599 of file util-radix-tree.c.

Referenced by IPOnlyMatchPacket(), IPOnlyPrepare(), and SCHInfoGetIPv4HostOSFlavour().

Here is the caller graph for this function:

◆ SCRadixFindKeyIPV4ExactMatch()

SCRadixNode* SCRadixFindKeyIPV4ExactMatch	(	uint8_t *	key_stream,
		SCRadixTree *	tree,
		void **	user_data_result
	)

Checks if an IPV4 address is present in the tree.

Parameters

key_stream	Data that has to be found in the Radix tree. In this case an IPV4 address
tree	Pointer to the Radix tree instance

Definition at line 1587 of file util-radix-tree.c.

Referenced by IPOnlyPrepare().

Here is the caller graph for this function:

◆ SCRadixFindKeyIPV4Netblock()

SCRadixNode* SCRadixFindKeyIPV4Netblock	(	uint8_t *	key_stream,
		SCRadixTree *	tree,
		uint8_t	netmask,
		void **	user_data_result
	)

Checks if an IPV4 Netblock address is present in the tree.

Parameters

key_stream	Data that has to be found in the Radix tree. In this case an IPV4 netblock address
tree	Pointer to the Radix tree instance

Definition at line 1611 of file util-radix-tree.c.

Referenced by IPOnlyPrepare().

Here is the caller graph for this function:

◆ SCRadixFindKeyIPV6BestMatch()

SCRadixNode* SCRadixFindKeyIPV6BestMatch	(	uint8_t *	key_stream,
		SCRadixTree *	tree,
		void **	user_data_result
	)

Checks if an IPV6 address is present in the tree under a netblock.

Parameters

key_stream	Data that has to be found in the Radix tree. In this case an IPV6 address
tree	Pointer to the Radix tree instance

Definition at line 1657 of file util-radix-tree.c.

Referenced by IPOnlyMatchPacket(), SCHInfoGetHostOSFlavour(), and SCHInfoGetIPv6HostOSFlavour().

Here is the caller graph for this function:

◆ SCRadixFindKeyIPV6ExactMatch()

SCRadixNode* SCRadixFindKeyIPV6ExactMatch	(	uint8_t *	key_stream,
		SCRadixTree *	tree,
		void **	user_data_result
	)

Checks if an IPV6 address is present in the tree.

Parameters

key_stream	Data that has to be found in the Radix tree. In this case an IPV6 address
tree	Pointer to the Radix tree instance

Definition at line 1645 of file util-radix-tree.c.

◆ SCRadixFindKeyIPV6Netblock()

SCRadixNode* SCRadixFindKeyIPV6Netblock	(	uint8_t *	key_stream,
		SCRadixTree *	tree,
		uint8_t	netmask,
		void **	user_data_result
	)

Checks if an IPV6 Netblock address is present in the tree.

Parameters

key_stream	Data that has to be found in the Radix tree. In this case an IPV6 netblock address
tree	Pointer to the Radix tree instance

Definition at line 1628 of file util-radix-tree.c.

◆ SCRadixPrintNodeInfo()

void SCRadixPrintNodeInfo	(	SCRadixNode *	node,
		int	level,
		void()(void )	PrintData
	)

Prints the node information from a Radix tree.

Parameters

node	Pointer to the Radix node whose information has to be printed
level	Used for indentation purposes

Definition at line 1668 of file util-radix-tree.c.

References SCRadixNode_::bit, SCRadixPrefix_::bitlen, SCRadixUserData_::netmask, SCRadixNode_::netmask_cnt, SCRadixNode_::netmasks, SCRadixUserData_::next, SCRadixNode_::prefix, SCRadixPrefix_::stream, SCRadixUserData_::user, and SCRadixPrefix_::user_data.

◆ SCRadixPrintTree()

void SCRadixPrintTree ( SCRadixTree * tree )

Prints the Radix Tree. While printing the radix tree we use the following format.

Parent_0 Left_Child_1 Left_Child_2 Right_Child_2 Right_Child_1 Left_Child_2 Right_Child_2 and so on

Each node printed out holds details on the next bit that differs amongst its children, and if the node holds a prefix, the perfix is printed as well.

Parameters

tree	Pointer to the Radix tree that has to be printed

Definition at line 1749 of file util-radix-tree.c.

◆ SCRadixRegisterTests()

void SCRadixRegisterTests ( void )

Definition at line 3810 of file util-radix-tree.c.

References UtRegisterTest().

Here is the call graph for this function:

◆ SCRadixReleaseRadixTree()

void SCRadixReleaseRadixTree ( SCRadixTree * tree )

Frees a Radix tree and all its nodes.

Parameters

tree	Pointer to the Radix tree that has to be freed

Definition at line 462 of file util-radix-tree.c.

Referenced by IPOnlyDeinit(), and SRepDestroy().

Here is the caller graph for this function:

◆ SCRadixRemoveKeyGeneric()

void SCRadixRemoveKeyGeneric	(	uint8_t *	key_stream,
		uint16_t	key_bitlen,
		SCRadixTree *	tree
	)

Removes a key from the Radix tree.

Parameters

key_stream	Data that has to be removed from the Radix tree
key_bitlen	The bitlen of the above stream.
tree	Pointer to the Radix tree from which the key has to be removed

Definition at line 1374 of file util-radix-tree.c.

◆ SCRadixRemoveKeyIPV4()

void SCRadixRemoveKeyIPV4	(	uint8_t *	key_stream,
		SCRadixTree *	tree
	)

Removes an IPV4 address key(not a netblock) from the Radix tree. Instead of using this function, we can also used SCRadixRemoveKeyIPV4Netblock(), by supplying a netmask value of 32.

Parameters

key_stream	Data that has to be removed from the Radix tree. In this case an IPV4 address
tree	Pointer to the Radix tree from which the key has to be removed

Definition at line 1409 of file util-radix-tree.c.

◆ SCRadixRemoveKeyIPV4Netblock()

void SCRadixRemoveKeyIPV4Netblock	(	uint8_t *	key_stream,
		SCRadixTree *	tree,
		uint8_t	netmask
	)

Removes an IPV4 address netblock key from the Radix tree.

Parameters

key_stream	Data that has to be removed from the Radix tree. In this case an IPV4 address
tree	Pointer to the Radix tree from which the key has to be removed

Definition at line 1389 of file util-radix-tree.c.

◆ SCRadixRemoveKeyIPV6()

void SCRadixRemoveKeyIPV6	(	uint8_t *	key_stream,
		SCRadixTree *	tree
	)

Removes an IPV6 address key(not a netblock) from the Radix tree. Instead of using this function, we can also used SCRadixRemoveKeyIPV6Netblock(), by supplying a netmask value of 128.

Parameters

key_stream	Data that has to be removed from the Radix tree. In this case an IPV6 address
tree	Pointer to the Radix tree from which the key has to be removed

Definition at line 1443 of file util-radix-tree.c.

◆ SCRadixRemoveKeyIPV6Netblock()

void SCRadixRemoveKeyIPV6Netblock	(	uint8_t *	key_stream,
		SCRadixTree *	tree,
		uint8_t	netmask
	)

Removes an IPV6 netblock address key from the Radix tree.

Parameters

key_stream	Data that has to be removed from the Radix tree. In this case an IPV6 address
tree	Pointer to the Radix tree from which the key has to be removed

Definition at line 1423 of file util-radix-tree.c.

Functions

Detailed Description

Function Documentation

◆ SCRadixAddKeyIPV4()

◆ SCRadixAddKeyIPV4Netblock()

◆ SCRadixAddKeyIPV4String()

◆ SCRadixAddKeyIPV6()

◆ SCRadixAddKeyIPV6Netblock()

◆ SCRadixAddKeyIPV6String()

◆ SCRadixCreateRadixTree()

◆ SCRadixFindKeyIPV4BestMatch()

◆ SCRadixFindKeyIPV4ExactMatch()

◆ SCRadixFindKeyIPV4Netblock()

◆ SCRadixFindKeyIPV6BestMatch()

◆ SCRadixFindKeyIPV6ExactMatch()

◆ SCRadixFindKeyIPV6Netblock()

◆ SCRadixPrintNodeInfo()

◆ SCRadixPrintTree()

◆ SCRadixRegisterTests()

◆ SCRadixReleaseRadixTree()

◆ SCRadixRemoveKeyGeneric()

◆ SCRadixRemoveKeyIPV4()

◆ SCRadixRemoveKeyIPV4Netblock()

◆ SCRadixRemoveKeyIPV6()

◆ SCRadixRemoveKeyIPV6Netblock()