From b1a597e0c3821c791a41278454e74261cf1b95fb Mon Sep 17 00:00:00 2001 From: Ondrej Zajicek Date: Tue, 31 Mar 2009 12:55:57 +0200 Subject: Reimplementation of prefix sets. Prefix sets were broken beyond any repair and have to be reimplemented. They are reimplemented using a trie with bitmasks in nodes. There is also change in the interpretation of minus prefix pattern, but the old interpretation was already inconsistent with the documentation and broken. There is also some bugfixes in filter code related to set variables. --- filter/filter.h | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+) (limited to 'filter/filter.h') diff --git a/filter/filter.h b/filter/filter.h index f71e54d..2277f51 100644 --- a/filter/filter.h +++ b/filter/filter.h @@ -50,6 +50,7 @@ struct f_val { struct f_prefix px; char *s; struct f_tree *t; + struct f_trie *ti; struct adata *ad; struct f_path_mask *path_mask; } val; @@ -69,6 +70,12 @@ struct f_tree *build_tree(struct f_tree *); struct f_tree *find_tree(struct f_tree *t, struct f_val val); int same_tree(struct f_tree *t1, struct f_tree *t2); +struct f_trie *f_new_trie(void); +void trie_add_prefix(struct f_trie *t, struct f_prefix *px); +int trie_match_prefix(struct f_trie *t, struct f_prefix *px); +int trie_same(struct f_trie *t1, struct f_trie *t2); +int trie_print(struct f_trie *t, char *buf, int blen); + struct ea_list; struct rte; @@ -128,6 +135,7 @@ void val_print(struct f_val v); #define T_RETURN 0x40 #define T_SET 0x80 +#define T_PREFIX_SET 0x81 struct f_tree { struct f_tree *left, *right; @@ -135,6 +143,19 @@ struct f_tree { void *data; }; +struct f_trie_node +{ + ip_addr addr, mask, accept; + int plen; + struct f_trie_node *c[2]; +}; + +struct f_trie +{ + int zero; + struct f_trie_node root; +}; + #define NEW_F_VAL struct f_val * val; val = cfg_alloc(sizeof(struct f_val)); #define FF_FORCE_TMPATTR 1 /* Force all attributes to be temporary */ -- cgit v1.2.3