suricata
util-radix-tree.c File Reference
#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:

Go to the source code of this file.

Functions

SCRadixTreeSCRadixCreateRadixTree (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...
 
SCRadixNodeSCRadixAddKeyIPV4 (uint8_t *key_stream, SCRadixTree *tree, void *user)
 Adds a new IPV4 address to the Radix tree. More...
 
SCRadixNodeSCRadixAddKeyIPV6 (uint8_t *key_stream, SCRadixTree *tree, void *user)
 Adds a new IPV6 address to the Radix tree. More...
 
SCRadixNodeSCRadixAddKeyIPV4Netblock (uint8_t *key_stream, SCRadixTree *tree, void *user, uint8_t netmask)
 Adds a new IPV4 netblock to the Radix tree. More...
 
SCRadixNodeSCRadixAddKeyIPV6Netblock (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 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...
 
SCRadixNodeSCRadixFindKeyIPV4ExactMatch (uint8_t *key_stream, SCRadixTree *tree, void **user_data_result)
 Checks if an IPV4 address is present in the tree. More...
 
SCRadixNodeSCRadixFindKeyIPV4BestMatch (uint8_t *key_stream, SCRadixTree *tree, void **user_data_result)
 Checks if an IPV4 address is present in the tree under a netblock. More...
 
SCRadixNodeSCRadixFindKeyIPV4Netblock (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...
 
SCRadixNodeSCRadixFindKeyIPV6Netblock (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...
 
SCRadixNodeSCRadixFindKeyIPV6ExactMatch (uint8_t *key_stream, SCRadixTree *tree, void **user_data_result)
 Checks if an IPV6 address is present in the tree. More...
 
SCRadixNodeSCRadixFindKeyIPV6BestMatch (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_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 857 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_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 939 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
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
booltrue (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 988 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_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 876 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_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 962 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
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
booltrue (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 1063 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
FreeFunction pointer supplied by the user to be used by the Radix cleanup API to free the user supplied data
Return values
treeThe newly created radix tree on success

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

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

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

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_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 1565 of file util-radix-tree.c.

Referenced by IPOnlyMatchPacket(), 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_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 1553 of file util-radix-tree.c.

◆ 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_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 1577 of file util-radix-tree.c.

◆ 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_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 1623 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_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 1611 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_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 1594 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
nodePointer to the Radix node whose information has to be printed
levelUsed for indentation purposes

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

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

◆ SCRadixRegisterTests()

void SCRadixRegisterTests ( void  )

Definition at line 3770 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
treePointer to the Radix tree that has to be freed

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

Referenced by IPOnlyDeinit(), and SRepDestroy().

Here is the caller graph for this function:

◆ 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_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 1378 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_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 1359 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_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 1410 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_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 1391 of file util-radix-tree.c.