suricata
util-radix-tree.h File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  SCRadixUserData_
 Structure that hold the user data and the netmask associated with it. More...
 
struct  SCRadixPrefix_
 Structure for the prefix/key in the radix tree. More...
 
struct  SCRadixNode_
 Structure for the node in the radix tree. More...
 
struct  SCRadixTree_
 Structure for the radix tree. More...
 

Macros

#define SC_RADIX_BITTEST(x, y)   ((x) & (y))
 

Typedefs

typedef struct SCRadixUserData_ SCRadixUserData
 Structure that hold the user data and the netmask associated with it. More...
 
typedef struct SCRadixPrefix_ SCRadixPrefix
 Structure for the prefix/key in the radix tree. More...
 
typedef struct SCRadixNode_ SCRadixNode
 Structure for the node in the radix tree. More...
 
typedef struct SCRadixTree_ SCRadixTree
 Structure for the radix tree. More...
 

Functions

struct in_addr * SCRadixValidateIPV4Address (const char *)
 
struct in6_addr * SCRadixValidateIPV6Address (const char *)
 
void SCRadixChopIPAddressAgainstNetmask (uint8_t *, uint8_t, uint16_t)
 
SCRadixTreeSCRadixCreateRadixTree (void(*Free)(void *), void(*PrintData)(void *))
 Creates a new Radix tree. More...
 
void SCRadixReleaseRadixTree (SCRadixTree *)
 Frees a Radix tree and all its nodes. More...
 
SCRadixNodeSCRadixAddKeyGeneric (uint8_t *, uint16_t, SCRadixTree *, void *)
 Adds a new generic key to the Radix tree. More...
 
SCRadixNodeSCRadixAddKeyIPV4 (uint8_t *, SCRadixTree *, void *)
 Adds a new IPV4 address to the Radix tree. More...
 
SCRadixNodeSCRadixAddKeyIPV6 (uint8_t *, SCRadixTree *, void *)
 Adds a new IPV6 address to the Radix tree. More...
 
SCRadixNodeSCRadixAddKeyIPV4Netblock (uint8_t *, SCRadixTree *, void *, uint8_t)
 Adds a new IPV4 netblock to the Radix tree. More...
 
SCRadixNodeSCRadixAddKeyIPV6Netblock (uint8_t *, SCRadixTree *, void *, uint8_t)
 Adds a new IPV6 netblock to the Radix tree. More...
 
SCRadixNodeSCRadixAddKeyIPV4String (const char *, SCRadixTree *, void *)
 Adds a new IPV4/netblock to the Radix tree from a string. More...
 
SCRadixNodeSCRadixAddKeyIPV6String (const char *, SCRadixTree *, void *)
 Adds a new IPV6/netblock to the Radix tree from a string. More...
 
void SCRadixRemoveKeyGeneric (uint8_t *, uint16_t, SCRadixTree *)
 Removes a key from the Radix tree. More...
 
void SCRadixRemoveKeyIPV4Netblock (uint8_t *, SCRadixTree *, uint8_t)
 Removes an IPV4 address netblock key from the Radix tree. More...
 
void SCRadixRemoveKeyIPV4 (uint8_t *, SCRadixTree *)
 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 *, SCRadixTree *, uint8_t)
 Removes an IPV6 netblock address key from the Radix tree. More...
 
void SCRadixRemoveKeyIPV6 (uint8_t *, SCRadixTree *)
 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...
 
SCRadixNodeSCRadixFindKeyGeneric (uint8_t *, uint16_t, SCRadixTree *, void **)
 Checks if a key is present in the tree. More...
 
SCRadixNodeSCRadixFindKeyIPV4ExactMatch (uint8_t *, SCRadixTree *, void **)
 Checks if an IPV4 address is present in the tree. More...
 
SCRadixNodeSCRadixFindKeyIPV4Netblock (uint8_t *, SCRadixTree *, uint8_t, void **)
 Checks if an IPV4 Netblock address is present in the tree. More...
 
SCRadixNodeSCRadixFindKeyIPV4BestMatch (uint8_t *, SCRadixTree *, void **)
 Checks if an IPV4 address is present in the tree under a netblock. More...
 
SCRadixNodeSCRadixFindKeyIPV6ExactMatch (uint8_t *, SCRadixTree *, void **)
 Checks if an IPV6 address is present in the tree. More...
 
SCRadixNodeSCRadixFindKeyIPV6Netblock (uint8_t *, SCRadixTree *, uint8_t, void **)
 Checks if an IPV6 Netblock address is present in the tree. More...
 
SCRadixNodeSCRadixFindKeyIPV6BestMatch (uint8_t *, SCRadixTree *, void **)
 Checks if an IPV6 address is present in the tree under a netblock. More...
 
void SCRadixPrintTree (SCRadixTree *)
 Prints the Radix Tree. While printing the radix tree we use the following format. More...
 
void SCRadixPrintNodeInfo (SCRadixNode *, int, void(*PrintData)(void *))
 Prints the node information from a Radix tree. More...
 
void SCRadixRegisterTests (void)
 

Detailed Description

Macro Definition Documentation

#define SC_RADIX_BITTEST (   x,
 
)    ((x) & (y))

Typedef Documentation

typedef struct SCRadixNode_ SCRadixNode

Structure for the node in the radix tree.

typedef struct SCRadixPrefix_ SCRadixPrefix

Structure for the prefix/key in the radix tree.

typedef struct SCRadixTree_ SCRadixTree

Structure for the radix tree.

Structure that hold the user data and the netmask associated with it.

Function Documentation

SCRadixNode* SCRadixAddKeyGeneric ( uint8_t *  key_stream,
uint16_t  key_bitlen,
SCRadixTree tree,
void *  user 
)

Adds a new generic key to the Radix tree.

Parameters
key_streamData that has to be added to the Radix tree
key_bitlenThe bitlen of the the above stream. For example if the stream is the string "abcd", the bitlen would be 32
treePointer to the Radix tree
userPointer to the user data that has to be associated with the key
Return values
nodePointer to the newly created node

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

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

Adds a new IPV4 address to the Radix tree.

Parameters
key_streamData that has to be added to the Radix tree. In this case a pointer to an IPV4 address
treePointer to the Radix tree
userPointer to the user data that has to be associated with the key
Return values
nodePointer to the newly created node

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

Referenced by IPOnlyPrepare(), SCHInfoAddHostOSInfo(), and SCRadixPrintTree().

Here is the caller graph for this function:

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

Adds a new IPV4 netblock to the Radix tree.

Parameters
key_streamData that has to be added to the Radix tree. In this case a pointer to an IPV4 netblock
treePointer to the Radix tree
userPointer to the user data that has to be associated with the key
netmaskThe netmask (cidr) if we are adding a netblock
Return values
nodePointer to the newly created node

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

Referenced by IPOnlyPrepare(), SCHInfoAddHostOSInfo(), and SCRadixPrintTree().

Here is the caller graph for this function:

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

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

Parameters
strIPV4 string with optional /cidr netmask
treePointer to the Radix tree
userPointer to the user data that has to be associated with the key
Return values
nodePointer to the newly created node

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

References strlcpy().

Referenced by HTPFreeConfig(), and SRepResetVersion().

Here is the call graph for this function:

Here is the caller graph for this function:

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

Adds a new IPV6 address to the Radix tree.

Parameters
key_streamData that has to be added to the Radix tree. In this case the pointer to an IPV6 address
treePointer to the Radix tree
userPointer to the user data that has to be associated with the key
Return values
nodePointer to the newly created node

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

Referenced by IPOnlyPrepare(), SCHInfoAddHostOSInfo(), and SCRadixPrintTree().

Here is the caller graph for this function:

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

Adds a new IPV6 netblock to the Radix tree.

Parameters
key_streamData that has to be added to the Radix tree. In this case a pointer to an IPV6 netblock
treePointer to the Radix tree
userPointer to the user data that has to be associated with the key
netmaskThe netmask (cidr) if we are adding a netblock
Return values
nodePointer to the newly created node

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

Referenced by IPOnlyPrepare(), SCHInfoAddHostOSInfo(), and SCRadixPrintTree().

Here is the caller graph for this function:

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

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

Parameters
strIPV6 string with optional /cidr netmask
treePointer to the Radix tree
userPointer to the user data that has to be associated with the key
Return values
nodePointer to the newly created node

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

References SCRadixNode_::bit, SCRadixPrefix_::bitlen, SCRadixTree_::head, SCRadixNode_::left, SCRadixNode_::netmask_cnt, SCRadixNode_::netmasks, SCRadixNode_::parent, SCRadixNode_::prefix, SCRadixNode_::right, SC_ERR_INVALID_ARGUMENTS, SC_RADIX_BITTEST, SCFree, SCLogDebug, SCLogError, SCMemcmp, SCRealloc, src, SCRadixPrefix_::stream, and strlcpy().

Referenced by HTPFreeConfig(), and SRepResetVersion().

Here is the call graph for this function:

Here is the caller graph for this function:

void SCRadixChopIPAddressAgainstNetmask ( uint8_t *  ,
uint8_t  ,
uint16_t   
)
SCRadixTree* SCRadixCreateRadixTree ( void(*)(void *)  Free,
void(*)(void *)  PrintData 
)

Creates a new Radix tree.

Parameters
FreeFunction pointer supplied by the user to be used by the Radix cleanup API to free the user suppplied data
Return values
treeThe newly created radix tree on success

(all radix trees should be created at init)

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

References SCRadixTree_::Free, SCRadixNode_::left, SCRadixTree_::PrintData, SCRadixNode_::right, SC_ERR_FATAL, SCLogError, and SCMalloc.

Referenced by DefragPolicyLoadFromConfig(), HTPConfigure(), IPOnlyInit(), SCHInfoAddHostOSInfo(), SCRadixPrintTree(), and SRepResetVersion().

Here is the caller graph for this function:

SCRadixNode* SCRadixFindKeyGeneric ( uint8_t *  key_stream,
uint16_t  key_bitlen,
SCRadixTree tree,
void **  user_data_result 
)

Checks if a key is present in the tree.

Parameters
key_streamData that has to be found in the Radix tree
key_bitlenThe bitlen of the the above stream.
treePointer to the Radix tree instance

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

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_streamData that has to be found in the Radix tree. In this case an IPV4 address
treePointer to the Radix tree instance

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

Referenced by HtpConfigRestoreBackup(), IPOnlyMatchPacket(), IPOnlyPrepare(), SCHInfoGetHostOSFlavour(), SCHInfoGetIPv4HostOSFlavour(), SCRadixPrintTree(), and SRepResetVersion().

Here is the caller graph for this function:

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

Checks if an IPV4 address is present in the tree.

Parameters
key_streamData that has to be found in the Radix tree. In this case an IPV4 address
treePointer to the Radix tree instance

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

Referenced by IPOnlyPrepare(), and SCRadixPrintTree().

Here is the caller graph for this function:

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_streamData that has to be found in the Radix tree. In this case an IPV4 netblock address
treePointer to the Radix tree instance

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

References SCRadixNode_::prefix.

Referenced by IPOnlyPrepare().

Here is the caller graph for this function:

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_streamData that has to be found in the Radix tree. In this case an IPV6 address
treePointer to the Radix tree instance

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

Referenced by HtpConfigRestoreBackup(), IPOnlyMatchPacket(), IPOnlyPrepare(), SCHInfoGetHostOSFlavour(), SCHInfoGetIPv6HostOSFlavour(), SCRadixPrintTree(), and SRepResetVersion().

Here is the caller graph for this function:

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

Checks if an IPV6 address is present in the tree.

Parameters
key_streamData that has to be found in the Radix tree. In this case an IPV6 address
treePointer to the Radix tree instance

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

Referenced by IPOnlyPrepare(), and SCRadixPrintTree().

Here is the caller graph for this function:

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_streamData that has to be found in the Radix tree. In this case an IPV6 netblock address
treePointer to the Radix tree instance

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

References SCRadixNode_::prefix.

Referenced by IPOnlyPrepare().

Here is the caller graph for this function:

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

Prints the node information from a Radix tree.

Parameters
nodePointer to the Radix node whose information has to be printed
levelUsed for indentation purposes

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

References SCRadixNode_::bit, SCRadixPrefix_::bitlen, SCRadixNode_::left, SCRadixUserData_::netmask, SCRadixNode_::netmask_cnt, SCRadixNode_::netmasks, SCRadixUserData_::next, SCRadixNode_::prefix, SCRadixNode_::right, SCRadixPrintNodeInfo(), SCRadixPrefix_::stream, SCRadixUserData_::user, and SCRadixPrefix_::user_data.

Referenced by SCRadixPrintNodeInfo().

Here is the call graph for this function:

Here is the caller graph for this function:

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
treePointer to the Radix tree that has to be printed

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

References SCRadixTree_::head, SCRadixTree_::PrintData, SCFree, SCMalloc, SCRadixAddKeyIPV4(), SCRadixAddKeyIPV4Netblock(), SCRadixAddKeyIPV6(), SCRadixAddKeyIPV6Netblock(), SCRadixCreateRadixTree(), SCRadixFindKeyIPV4BestMatch(), SCRadixFindKeyIPV4ExactMatch(), SCRadixFindKeyIPV6BestMatch(), SCRadixFindKeyIPV6ExactMatch(), SCRadixReleaseRadixTree(), SCRadixRemoveKeyIPV4(), SCRadixRemoveKeyIPV4Netblock(), SCRadixRemoveKeyIPV6(), SCStrdup, str, and unlikely.

Here is the call graph for this function:

void SCRadixRegisterTests ( void  )

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

References UtRegisterTest().

Here is the call graph for this function:

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

Removes a key from the Radix tree.

Parameters
key_streamData that has to be removed from the Radix tree
key_bitlenThe bitlen of the the above stream.
treePointer to the Radix tree from which the key has to be removed

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

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_streamData that has to be removed from the Radix tree. In this case an IPV4 address
treePointer to the Radix tree from which the key has to be removed

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

Referenced by SCRadixPrintTree().

Here is the caller graph for this function:

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

Removes an IPV4 address netblock key from the Radix tree.

Parameters
key_streamData that has to be removed from the Radix tree. In this case an IPV4 address
treePointer to the Radix tree from which the key has to be removed

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

Referenced by SCHInfoLoadFromConfig(), and SCRadixPrintTree().

Here is the caller graph for this function:

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_streamData that has to be removed from the Radix tree. In this case an IPV6 address
treePointer to the Radix tree from which the key has to be removed

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

References SCRadixNode_::bit, SCRadixTree_::head, SCRadixNode_::left, SCRadixNode_::netmask_cnt, SCRadixNode_::netmasks, SCRadixNode_::parent, SCRadixNode_::prefix, SCRadixNode_::right, SC_RADIX_BITTEST, SCMemcmp, and SCRadixPrefix_::stream.

Referenced by SCRadixPrintTree().

Here is the caller graph for this function:

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

Removes an IPV6 netblock address key from the Radix tree.

Parameters
key_streamData that has to be removed from the Radix tree. In this case an IPV6 address
treePointer to the Radix tree from which the key has to be removed

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

struct in_addr* SCRadixValidateIPV4Address ( const char *  )
struct in6_addr* SCRadixValidateIPV6Address ( const char *  )