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 __UTIL_RADIX_TREE_H__
25 #define __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 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 */
70  /* holds a list of netmaks 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 */
81 } SCRadixNode;
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 *);
94 } SCRadixTree;
95 
96 
97 struct in_addr *SCRadixValidateIPV4Address(const char *);
98 struct in6_addr *SCRadixValidateIPV6Address(const char *);
99 void SCRadixChopIPAddressAgainstNetmask(uint8_t *, uint8_t, uint16_t);
100 
101 SCRadixTree *SCRadixCreateRadixTree(void (*Free)(void*), void (*PrintData)(void*));
103 
104 SCRadixNode *SCRadixAddKeyGeneric(uint8_t *, uint16_t, SCRadixTree *, void *);
105 SCRadixNode *SCRadixAddKeyIPV4(uint8_t *, SCRadixTree *, void *);
106 SCRadixNode *SCRadixAddKeyIPV6(uint8_t *, SCRadixTree *, void *);
108  uint8_t);
110  uint8_t);
111 SCRadixNode *SCRadixAddKeyIPV4String(const char *, SCRadixTree *, void *);
112 SCRadixNode *SCRadixAddKeyIPV6String(const char *, SCRadixTree *, void *);
113 
114 void SCRadixRemoveKeyGeneric(uint8_t *, uint16_t, SCRadixTree *);
115 void SCRadixRemoveKeyIPV4Netblock(uint8_t *, SCRadixTree *, uint8_t);
116 void SCRadixRemoveKeyIPV4(uint8_t *, SCRadixTree *);
117 void SCRadixRemoveKeyIPV6Netblock(uint8_t *, SCRadixTree *, uint8_t);
118 void SCRadixRemoveKeyIPV6(uint8_t *, SCRadixTree *);
119 
120 SCRadixNode *SCRadixFindKeyGeneric(uint8_t *, uint16_t, SCRadixTree *, void **);
121 
123 SCRadixNode *SCRadixFindKeyIPV4Netblock(uint8_t *, SCRadixTree *, uint8_t, void **);
124 SCRadixNode *SCRadixFindKeyIPV4BestMatch(uint8_t *, SCRadixTree *, void **);
125 
127 SCRadixNode *SCRadixFindKeyIPV6Netblock(uint8_t *, SCRadixTree *, uint8_t, void **);
128 SCRadixNode *SCRadixFindKeyIPV6BestMatch(uint8_t *, SCRadixTree *, void **);
129 
131 void SCRadixPrintNodeInfo(SCRadixNode *, int, void (*PrintData)(void*));
132 
133 void SCRadixRegisterTests(void);
134 
135 #endif /* __UTIL_RADIX_TREE_H__ */
struct SCRadixNode_ * parent
SCRadixPrefix * prefix
SCRadixTree * SCRadixCreateRadixTree(void(*Free)(void *), void(*PrintData)(void *))
Creates a new Radix tree.
SCRadixNode * SCRadixFindKeyIPV6BestMatch(uint8_t *, SCRadixTree *, void **)
Checks if an IPV6 address is present in the tree under a netblock.
struct SCRadixUserData_ * next
struct SCRadixNode_ * left
SCRadixNode * SCRadixFindKeyIPV6ExactMatch(uint8_t *, SCRadixTree *, void **)
Checks if an IPV6 address is present in the tree.
uint8_t * stream
SCRadixNode * SCRadixFindKeyIPV6Netblock(uint8_t *, SCRadixTree *, uint8_t, void **)
Checks if an IPV6 Netblock address is present in the tree.
void SCRadixReleaseRadixTree(SCRadixTree *)
Frees a Radix tree and all its nodes.
void SCRadixRemoveKeyIPV6Netblock(uint8_t *, SCRadixTree *, uint8_t)
Removes an IPV6 netblock address key from the Radix tree.
SCRadixNode * SCRadixFindKeyIPV4Netblock(uint8_t *, SCRadixTree *, uint8_t, void **)
Checks if an IPV4 Netblock address is present in the tree.
Structure for the prefix/key in the radix tree.
struct SCRadixPrefix_ SCRadixPrefix
Structure for the prefix/key in the radix tree.
SCRadixNode * SCRadixAddKeyIPV6Netblock(uint8_t *, SCRadixTree *, void *, uint8_t)
Adds a new IPV6 netblock to the Radix tree.
SCRadixNode * SCRadixAddKeyIPV6(uint8_t *, SCRadixTree *, void *)
Adds a new IPV6 address to the Radix tree.
void SCRadixPrintTree(SCRadixTree *)
Prints the Radix Tree. While printing the radix tree we use the following format. ...
SCRadixNode * SCRadixAddKeyIPV4Netblock(uint8_t *, SCRadixTree *, void *, uint8_t)
Adds a new IPV4 netblock to the Radix tree.
struct SCRadixTree_ SCRadixTree
Structure for the radix tree.
void SCRadixRemoveKeyIPV4Netblock(uint8_t *, SCRadixTree *, uint8_t)
Removes an IPV4 address netblock key from the Radix tree.
SCRadixNode * SCRadixAddKeyIPV6String(const char *, SCRadixTree *, void *)
Adds a new IPV6/netblock to the Radix tree from a string.
void SCRadixPrintNodeInfo(SCRadixNode *, int, void(*PrintData)(void *))
Prints the node information from a Radix tree.
struct in_addr * SCRadixValidateIPV4Address(const char *)
Structure for the node in the radix tree.
SCRadixNode * SCRadixFindKeyIPV4BestMatch(uint8_t *, SCRadixTree *, void **)
Checks if an IPV4 address is present in the tree under a netblock.
void SCRadixRemoveKeyIPV6(uint8_t *, SCRadixTree *)
Removes an IPV6 address key(not a netblock) from the Radix tree. Instead of using this function...
SCRadixNode * head
void SCRadixRemoveKeyIPV4(uint8_t *, SCRadixTree *)
Removes an IPV4 address key(not a netblock) from the Radix tree. Instead of using this function...
struct SCRadixNode_ * right
SCRadixNode * SCRadixAddKeyIPV4(uint8_t *, SCRadixTree *, void *)
Adds a new IPV4 address to the Radix tree.
void SCRadixChopIPAddressAgainstNetmask(uint8_t *, uint8_t, uint16_t)
Structure that hold the user data and the netmask associated with it.
SCRadixNode * SCRadixFindKeyGeneric(uint8_t *, uint16_t, SCRadixTree *, void **)
Checks if a key is present in the tree.
void SCRadixRemoveKeyGeneric(uint8_t *, uint16_t, SCRadixTree *)
Removes a key from the Radix tree.
struct SCRadixNode_ SCRadixNode
Structure for the node in the radix tree.
struct in6_addr * SCRadixValidateIPV6Address(const char *)
SCRadixNode * SCRadixAddKeyGeneric(uint8_t *, uint16_t, SCRadixTree *, void *)
Adds a new generic key to the Radix tree.
void SCRadixRegisterTests(void)
Structure for the radix tree.
SCRadixUserData * user_data
struct SCRadixUserData_ SCRadixUserData
Structure that hold the user data and the netmask associated with it.
SCRadixNode * SCRadixFindKeyIPV4ExactMatch(uint8_t *, SCRadixTree *, void **)
Checks if an IPV4 address is present in the tree.
uint8_t * netmasks
SCRadixNode * SCRadixAddKeyIPV4String(const char *, SCRadixTree *, void *)
Adds a new IPV4/netblock to the Radix tree from a string.