diff options
author | Ashlee Young <ashlee@onosfw.com> | 2015-09-09 22:21:41 -0700 |
---|---|---|
committer | Ashlee Young <ashlee@onosfw.com> | 2015-09-09 22:21:41 -0700 |
commit | 8879b125d26e8db1a5633de5a9c692eb2d1c4f83 (patch) | |
tree | c7259d85a991b83dfa85ab2e339360669fc1f58e /framework/src/suricata/src/util-radix-tree.h | |
parent | 13d05bc8458758ee39cb829098241e89616717ee (diff) |
suricata checkin based on commit id a4bce14770beee46a537eda3c3f6e8e8565d5d0a
Change-Id: I9a214fa0ee95e58fc640e50bd604dac7f42db48f
Diffstat (limited to 'framework/src/suricata/src/util-radix-tree.h')
-rw-r--r-- | framework/src/suricata/src/util-radix-tree.h | 135 |
1 files changed, 135 insertions, 0 deletions
diff --git a/framework/src/suricata/src/util-radix-tree.h b/framework/src/suricata/src/util-radix-tree.h new file mode 100644 index 00000000..e9e63457 --- /dev/null +++ b/framework/src/suricata/src/util-radix-tree.h @@ -0,0 +1,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__ */ |