1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
|
/* Copyright (C) 2007-2010 Open Information Security Foundation
*
* You can copy, redistribute or modify this Program under the terms of
* the GNU General Public License version 2 as published by the Free
* Software Foundation.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* version 2 along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
* 02110-1301, USA.
*/
/**
* \file
*
* \author Anoop Saldanha <anoopsaldanha@gmail.com>
*/
#ifndef __UTIL_RADIX_TREE_H__
#define __UTIL_RADIX_TREE_H__
#define SC_RADIX_BITTEST(x, y) ((x) & (y))
/**
* \brief Structure that hold the user data and the netmask associated with it.
*/
typedef struct SCRadixUserData_ {
/* holds a pointer to the user data associated with the particular netmask */
void *user;
/* pointer to the next user data in the list */
struct SCRadixUserData_ *next;
/* holds the netmask value that corresponds to this user data pointer */
uint8_t netmask;
} SCRadixUserData;
/**
* \brief Structure for the prefix/key in the radix tree
*/
typedef struct SCRadixPrefix_ {
/* length of the stream */
uint16_t bitlen;
/* the key that has been stored in the tree */
uint8_t *stream;
/* any user data that has to be associated with this key. We need a user
* data field for each netblock value possible since one ip can be associated
* with any of the the 32 or 128 netblocks. Also for non-ips, we store the
* netmask as 255 in SCRadixUserData->netmask */
SCRadixUserData *user_data;
} SCRadixPrefix;
/**
* \brief Structure for the node in the radix tree
*/
typedef struct SCRadixNode_ {
/* the bit position where the bits differ in the nodes children. Used
* to determine the path to be taken during a lookup*/
uint16_t bit;
uint16_t pad0;
/* total no of netmasks that are registered under this node */
int netmask_cnt;
/* holds a list of netmaks that come under this node in the tree */
uint8_t *netmasks;
/* holds the prefix that the path to this node holds */
SCRadixPrefix *prefix;
/* the left and the right children of a node */
struct SCRadixNode_ *left, *right;
/* the parent node for this tree */
struct SCRadixNode_ *parent;
} SCRadixNode;
/**
* \brief Structure for the radix tree
*/
typedef struct SCRadixTree_ {
/* the root node in the radix tree */
SCRadixNode *head;
/* function pointer that is supplied by the user to free the user data
* held by the user field of SCRadixNode */
void (*PrintData)(void *);
void (*Free)(void *);
} SCRadixTree;
struct in_addr *SCRadixValidateIPV4Address(const char *);
struct in6_addr *SCRadixValidateIPV6Address(const char *);
void SCRadixChopIPAddressAgainstNetmask(uint8_t *, uint8_t, uint16_t);
SCRadixTree *SCRadixCreateRadixTree(void (*Free)(void*), void (*PrintData)(void*));
void SCRadixReleaseRadixTree(SCRadixTree *);
SCRadixNode *SCRadixAddKeyGeneric(uint8_t *, uint16_t, SCRadixTree *, void *);
SCRadixNode *SCRadixAddKeyIPV4(uint8_t *, SCRadixTree *, void *);
SCRadixNode *SCRadixAddKeyIPV6(uint8_t *, SCRadixTree *, void *);
SCRadixNode *SCRadixAddKeyIPV4Netblock(uint8_t *, SCRadixTree *, void *,
uint8_t);
SCRadixNode *SCRadixAddKeyIPV6Netblock(uint8_t *, SCRadixTree *, void *,
uint8_t);
SCRadixNode *SCRadixAddKeyIPV4String(const char *, SCRadixTree *, void *);
SCRadixNode *SCRadixAddKeyIPV6String(const char *, SCRadixTree *, void *);
void SCRadixRemoveKeyGeneric(uint8_t *, uint16_t, SCRadixTree *);
void SCRadixRemoveKeyIPV4Netblock(uint8_t *, SCRadixTree *, uint8_t);
void SCRadixRemoveKeyIPV4(uint8_t *, SCRadixTree *);
void SCRadixRemoveKeyIPV6Netblock(uint8_t *, SCRadixTree *, uint8_t);
void SCRadixRemoveKeyIPV6(uint8_t *, SCRadixTree *);
SCRadixNode *SCRadixFindKeyGeneric(uint8_t *, uint16_t, SCRadixTree *, void **);
SCRadixNode *SCRadixFindKeyIPV4ExactMatch(uint8_t *, SCRadixTree *, void **);
SCRadixNode *SCRadixFindKeyIPV4Netblock(uint8_t *, SCRadixTree *, uint8_t, void **);
SCRadixNode *SCRadixFindKeyIPV4BestMatch(uint8_t *, SCRadixTree *, void **);
SCRadixNode *SCRadixFindKeyIPV6ExactMatch(uint8_t *, SCRadixTree *, void **);
SCRadixNode *SCRadixFindKeyIPV6Netblock(uint8_t *, SCRadixTree *, uint8_t, void **);
SCRadixNode *SCRadixFindKeyIPV6BestMatch(uint8_t *, SCRadixTree *, void **);
void SCRadixPrintTree(SCRadixTree *);
void SCRadixPrintNodeInfo(SCRadixNode *, int, void (*PrintData)(void*));
void SCRadixRegisterTests(void);
#endif /* __UTIL_RADIX_TREE_H__ */
|
