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 */
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 
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__ */
SCRadixValidateIPV4Address
struct in_addr * SCRadixValidateIPV4Address(const char *)
SCRadixPrefix_::user_data
SCRadixUserData * user_data
Definition: util-radix-tree.h:55
SCRadixNode_::netmask_cnt
int netmask_cnt
Definition: util-radix-tree.h:69
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:1290
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:1321
SCRadixAddKeyIPV6String
SCRadixNode * SCRadixAddKeyIPV6String(const char *, SCRadixTree *, void *)
Adds a new IPV6/netblock to the Radix tree from a string.
Definition: util-radix-tree.c:985
SCRadixRemoveKeyIPV4Netblock
void SCRadixRemoveKeyIPV4Netblock(uint8_t *, SCRadixTree *, uint8_t)
Removes an IPV4 address netblock key from the Radix tree.
Definition: util-radix-tree.c:1273
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:878
SCRadixFindKeyIPV4ExactMatch
SCRadixNode * SCRadixFindKeyIPV4ExactMatch(uint8_t *, SCRadixTree *, void **)
Checks if an IPV4 address is present in the tree.
Definition: util-radix-tree.c:1478
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:898
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:1544
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:465
SCRadixAddKeyIPV6Netblock
SCRadixNode * SCRadixAddKeyIPV6Netblock(uint8_t *, SCRadixTree *, void *, uint8_t)
Adds a new IPV6 netblock to the Radix tree.
Definition: util-radix-tree.c:918
SCRadixPrintTree
void SCRadixPrintTree(SCRadixTree *)
Prints the Radix Tree. While printing the radix tree we use the following format.
Definition: util-radix-tree.c:1652
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:1502
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:1523
SCRadixAddKeyIPV4String
SCRadixNode * SCRadixAddKeyIPV4String(const char *, SCRadixTree *, void *)
Adds a new IPV4/netblock to the Radix tree from a string.
Definition: util-radix-tree.c:936
SCRadixValidateIPV6Address
struct in6_addr * SCRadixValidateIPV6Address(const char *)
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:1556
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:1567
SCRadixUserData_::user
void * user
Definition: util-radix-tree.h:34
SCRadixAddKeyGeneric
SCRadixNode * SCRadixAddKeyGeneric(uint8_t *, uint16_t, SCRadixTree *, void *)
Adds a new generic key to the Radix tree.
Definition: util-radix-tree.c:840
SCRadixChopIPAddressAgainstNetmask
void SCRadixChopIPAddressAgainstNetmask(uint8_t *, uint8_t, uint16_t)
SCRadixCreateRadixTree
SCRadixTree * SCRadixCreateRadixTree(void(*Free)(void *), void(*PrintData)(void *))
Creates a new Radix tree.
Definition: util-radix-tree.c:426
SCRadixNode_
Structure for the node in the radix tree.
Definition: util-radix-tree.h:61
SCRadixRegisterTests
void SCRadixRegisterTests(void)
Definition: util-radix-tree.c:4046
SCRadixRemoveKeyGeneric
void SCRadixRemoveKeyGeneric(uint8_t *, uint16_t, SCRadixTree *)
Removes a key from the Radix tree.
Definition: util-radix-tree.c:1258
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:1490
SCRadixRemoveKeyIPV6Netblock
void SCRadixRemoveKeyIPV6Netblock(uint8_t *, SCRadixTree *, uint8_t)
Removes an IPV6 netblock address key from the Radix tree.
Definition: util-radix-tree.c:1304
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:859
SCRadixFindKeyGeneric
SCRadixNode * SCRadixFindKeyGeneric(uint8_t *, uint16_t, SCRadixTree *, void **)
Checks if a key is present in the tree.
Definition: util-radix-tree.c:1465
SCRadixPrefix_::bitlen
uint16_t bitlen
Definition: util-radix-tree.h:46