suricata
util-radix-tree.h
Go to the documentation of this file.
1 /* Copyright (C) 2007-2010 Open Information Security Foundation
2  *
3  * You can copy, redistribute or modify this Program under the terms of
4  * the GNU General Public License version 2 as published by the Free
5  * Software Foundation.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * version 2 along with this program; if not, write to the Free Software
14  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
15  * 02110-1301, USA.
16  */
17 
18 /**
19  * \file
20  *
21  * \author Anoop Saldanha <anoopsaldanha@gmail.com>
22  */
23 
24 #ifndef SURICATA_UTIL_RADIX_TREE_H
25 #define SURICATA_UTIL_RADIX_TREE_H
26 
27 #define SC_RADIX_BITTEST(x, y) ((x) & (y))
28 
29 /**
30  * \brief Structure that hold the user data and the netmask associated with it.
31  */
32 typedef struct SCRadixUserData_ {
33  /* holds a pointer to the user data associated with the particular netmask */
34  void *user;
35  /* pointer to the next user data in the list */
37  /* holds the netmask value that corresponds to this user data pointer */
38  uint8_t netmask;
40 
41 /**
42  * \brief Structure for the prefix/key in the radix tree
43  */
44 typedef struct SCRadixPrefix_ {
45  /* length of the stream */
46  uint16_t bitlen;
47 
48  /* the key that has been stored in the tree */
49  uint8_t *stream;
50 
51  /* any user data that has to be associated with this key. We need a user
52  * data field for each netblock value possible since one ip can be associated
53  * with any of the 32 or 128 netblocks. Also for non-ips, we store the
54  * netmask as 255 in SCRadixUserData->netmask */
57 
58 /**
59  * \brief Structure for the node in the radix tree
60  */
61 typedef struct SCRadixNode_ {
62  /* the bit position where the bits differ in the nodes children. Used
63  * to determine the path to be taken during a lookup*/
64  uint16_t bit;
65 
66  uint16_t pad0;
67 
68  /* total no of netmasks that are registered under this node */
69  uint16_t netmask_cnt;
70  /* holds a list of netmasks that come under this node in the tree */
71  uint8_t *netmasks;
72 
73  /* holds the prefix that the path to this node holds */
75 
76  /* the left and the right children of a node */
77  struct SCRadixNode_ *left, *right;
78 
79  /* the parent node for this tree */
82 
83 /**
84  * \brief Structure for the radix tree
85  */
86 typedef struct SCRadixTree_ {
87  /* the root node in the radix tree */
89 
90  /* function pointer that is supplied by the user to free the user data
91  * held by the user field of SCRadixNode */
92  void (*PrintData)(void *);
93  void (*Free)(void *);
95 
96 SCRadixTree *SCRadixCreateRadixTree(void (*Free)(void*), void (*PrintData)(void*));
98 
99 SCRadixNode *SCRadixAddKeyIPV4(uint8_t *, SCRadixTree *, void *);
100 SCRadixNode *SCRadixAddKeyIPV6(uint8_t *, SCRadixTree *, void *);
102  uint8_t);
104  uint8_t);
105 bool SCRadixAddKeyIPV4String(const char *, SCRadixTree *, void *);
106 bool SCRadixAddKeyIPV6String(const char *, SCRadixTree *, void *);
107 
108 void SCRadixRemoveKeyIPV4Netblock(uint8_t *, SCRadixTree *, uint8_t);
109 void SCRadixRemoveKeyIPV4(uint8_t *, SCRadixTree *);
110 void SCRadixRemoveKeyIPV6Netblock(uint8_t *, SCRadixTree *, uint8_t);
111 void SCRadixRemoveKeyIPV6(uint8_t *, SCRadixTree *);
112 
114 SCRadixNode *SCRadixFindKeyIPV4Netblock(uint8_t *, SCRadixTree *, uint8_t, void **);
115 SCRadixNode *SCRadixFindKeyIPV4BestMatch(uint8_t *, SCRadixTree *, void **);
116 
118 SCRadixNode *SCRadixFindKeyIPV6Netblock(uint8_t *, SCRadixTree *, uint8_t, void **);
119 SCRadixNode *SCRadixFindKeyIPV6BestMatch(uint8_t *, SCRadixTree *, void **);
120 
122 void SCRadixPrintNodeInfo(SCRadixNode *, int, void (*PrintData)(void*));
123 
124 void SCRadixRegisterTests(void);
125 
126 #endif /* SURICATA_UTIL_RADIX_TREE_H */
SCRadixPrefix_::user_data
SCRadixUserData * user_data
Definition: util-radix-tree.h:55
SCRadixRemoveKeyIPV4
void SCRadixRemoveKeyIPV4(uint8_t *, SCRadixTree *)
Removes an IPV4 address key(not a netblock) from the Radix tree. Instead of using this function,...
Definition: util-radix-tree.c:1378
SCRadixRemoveKeyIPV6
void SCRadixRemoveKeyIPV6(uint8_t *, SCRadixTree *)
Removes an IPV6 address key(not a netblock) from the Radix tree. Instead of using this function,...
Definition: util-radix-tree.c:1410
SCRadixAddKeyIPV4String
bool SCRadixAddKeyIPV4String(const char *, SCRadixTree *, void *)
Adds a new IPV4/netblock to the Radix tree from a string.
Definition: util-radix-tree.c:988
SCRadixRemoveKeyIPV4Netblock
void SCRadixRemoveKeyIPV4Netblock(uint8_t *, SCRadixTree *, uint8_t)
Removes an IPV4 address netblock key from the Radix tree.
Definition: util-radix-tree.c:1359
SCRadixNode_::prefix
SCRadixPrefix * prefix
Definition: util-radix-tree.h:74
SCRadixUserData
struct SCRadixUserData_ SCRadixUserData
Structure that hold the user data and the netmask associated with it.
SCRadixNode_::bit
uint16_t bit
Definition: util-radix-tree.h:64
SCRadixAddKeyIPV6
SCRadixNode * SCRadixAddKeyIPV6(uint8_t *, SCRadixTree *, void *)
Adds a new IPV6 address to the Radix tree.
Definition: util-radix-tree.c:876
SCRadixFindKeyIPV4ExactMatch
SCRadixNode * SCRadixFindKeyIPV4ExactMatch(uint8_t *, SCRadixTree *, void **)
Checks if an IPV4 address is present in the tree.
Definition: util-radix-tree.c:1553
SCRadixPrefix_
Structure for the prefix/key in the radix tree.
Definition: util-radix-tree.h:44
SCRadixTree_
Structure for the radix tree.
Definition: util-radix-tree.h:86
SCRadixTree
struct SCRadixTree_ SCRadixTree
Structure for the radix tree.
SCRadixAddKeyIPV4Netblock
SCRadixNode * SCRadixAddKeyIPV4Netblock(uint8_t *, SCRadixTree *, void *, uint8_t)
Adds a new IPV4 netblock to the Radix tree.
Definition: util-radix-tree.c:939
SCRadixUserData_::next
struct SCRadixUserData_ * next
Definition: util-radix-tree.h:36
SCRadixPrefix_::stream
uint8_t * stream
Definition: util-radix-tree.h:49
SCRadixNode_::right
struct SCRadixNode_ * right
Definition: util-radix-tree.h:77
SCRadixFindKeyIPV6ExactMatch
SCRadixNode * SCRadixFindKeyIPV6ExactMatch(uint8_t *, SCRadixTree *, void **)
Checks if an IPV6 address is present in the tree.
Definition: util-radix-tree.c:1611
SCRadixPrefix
struct SCRadixPrefix_ SCRadixPrefix
Structure for the prefix/key in the radix tree.
SCRadixReleaseRadixTree
void SCRadixReleaseRadixTree(SCRadixTree *)
Frees a Radix tree and all its nodes.
Definition: util-radix-tree.c:440
SCRadixAddKeyIPV6Netblock
SCRadixNode * SCRadixAddKeyIPV6Netblock(uint8_t *, SCRadixTree *, void *, uint8_t)
Adds a new IPV6 netblock to the Radix tree.
Definition: util-radix-tree.c:962
SCRadixPrintTree
void SCRadixPrintTree(SCRadixTree *)
Prints the Radix Tree. While printing the radix tree we use the following format.
Definition: util-radix-tree.c:1711
SCRadixTree_::Free
void(* Free)(void *)
Definition: util-radix-tree.h:93
SCRadixUserData_
Structure that hold the user data and the netmask associated with it.
Definition: util-radix-tree.h:32
SCRadixFindKeyIPV4Netblock
SCRadixNode * SCRadixFindKeyIPV4Netblock(uint8_t *, SCRadixTree *, uint8_t, void **)
Checks if an IPV4 Netblock address is present in the tree.
Definition: util-radix-tree.c:1577
SCRadixFindKeyIPV6Netblock
SCRadixNode * SCRadixFindKeyIPV6Netblock(uint8_t *, SCRadixTree *, uint8_t, void **)
Checks if an IPV6 Netblock address is present in the tree.
Definition: util-radix-tree.c:1594
SCRadixFindKeyIPV6BestMatch
SCRadixNode * SCRadixFindKeyIPV6BestMatch(uint8_t *, SCRadixTree *, void **)
Checks if an IPV6 address is present in the tree under a netblock.
Definition: util-radix-tree.c:1623
SCRadixUserData_::netmask
uint8_t netmask
Definition: util-radix-tree.h:38
SCRadixNode_::pad0
uint16_t pad0
Definition: util-radix-tree.h:66
SCRadixTree_::head
SCRadixNode * head
Definition: util-radix-tree.h:88
SCRadixTree_::PrintData
void(* PrintData)(void *)
Definition: util-radix-tree.h:92
SCRadixPrintNodeInfo
void SCRadixPrintNodeInfo(SCRadixNode *, int, void(*PrintData)(void *))
Prints the node information from a Radix tree.
Definition: util-radix-tree.c:1634
SCRadixUserData_::user
void * user
Definition: util-radix-tree.h:34
SCRadixCreateRadixTree
SCRadixTree * SCRadixCreateRadixTree(void(*Free)(void *), void(*PrintData)(void *))
Creates a new Radix tree.
Definition: util-radix-tree.c:405
SCRadixNode_
Structure for the node in the radix tree.
Definition: util-radix-tree.h:61
SCRadixRegisterTests
void SCRadixRegisterTests(void)
Definition: util-radix-tree.c:3770
SCRadixNode_::netmask_cnt
uint16_t netmask_cnt
Definition: util-radix-tree.h:69
SCRadixNode_::netmasks
uint8_t * netmasks
Definition: util-radix-tree.h:71
SCRadixNode
struct SCRadixNode_ SCRadixNode
Structure for the node in the radix tree.
SCRadixNode_::parent
struct SCRadixNode_ * parent
Definition: util-radix-tree.h:80
SCRadixFindKeyIPV4BestMatch
SCRadixNode * SCRadixFindKeyIPV4BestMatch(uint8_t *, SCRadixTree *, void **)
Checks if an IPV4 address is present in the tree under a netblock.
Definition: util-radix-tree.c:1565
SCRadixRemoveKeyIPV6Netblock
void SCRadixRemoveKeyIPV6Netblock(uint8_t *, SCRadixTree *, uint8_t)
Removes an IPV6 netblock address key from the Radix tree.
Definition: util-radix-tree.c:1391
SCRadixAddKeyIPV6String
bool SCRadixAddKeyIPV6String(const char *, SCRadixTree *, void *)
Adds a new IPV6/netblock to the Radix tree from a string.
Definition: util-radix-tree.c:1063
SCRadixNode_::left
struct SCRadixNode_ * left
Definition: util-radix-tree.h:77
SCRadixAddKeyIPV4
SCRadixNode * SCRadixAddKeyIPV4(uint8_t *, SCRadixTree *, void *)
Adds a new IPV4 address to the Radix tree.
Definition: util-radix-tree.c:857
SCRadixPrefix_::bitlen
uint16_t bitlen
Definition: util-radix-tree.h:46