/* Nothing. Simply nothing. */
T_VOID = 0,
+ T_NONE = 1, /* Special hack to represent missing arguments */
+
/* User visible types, which fit in int */
T_INT = 0x10,
T_BOOL = 0x11,
T_ENUM_ROA = 0x35,
T_ENUM_NETTYPE = 0x36,
T_ENUM_RA_PREFERENCE = 0x37,
+ T_ENUM_AF = 0x38,
/* new enums go here */
T_ENUM_EMPTY = 0x3f, /* Special hack for atomic_aggr */
T_LCLIST = 0x29, /* Large community list */
T_RD = 0x2a, /* Route distinguisher for VPN addresses */
T_PATH_MASK_ITEM = 0x2b, /* Path mask item for path mask constructors */
+ T_BYTESTRING = 0x2c,
T_SET = 0x80,
T_PREFIX_SET = 0x81,
} PACKED;
+struct f_method {
+ struct symbol *sym;
+ struct f_inst *(*new_inst)(struct f_inst *obj, struct f_inst *args);
+ const struct f_method *next;
+ uint arg_num;
+ enum f_type args_type[];
+};
+
/* Filter value; size of this affects filter memory consumption */
struct f_val {
enum f_type type; /* T_* */
lcomm lc;
ip_addr ip;
const net_addr *net;
- char *s;
+ const char *s;
+ const struct bytestring *bs;
const struct f_tree *t;
const struct f_trie *ti;
const struct adata *ad;
SA_DEST,
SA_IFNAME,
SA_IFINDEX,
+ SA_WEIGHT,
+ SA_PREF,
+ SA_GW_MPLS,
+ SA_ONLINK,
} PACKED;
/* Static attribute definition (members of struct rta) */
void *data;
};
+#ifdef ENABLE_COMPACT_TRIES
+/* Compact 4-way tries */
+#define TRIE_STEP 2
+#define TRIE_STACK_LENGTH 65
+#else
+/* Faster 16-way tries */
+#define TRIE_STEP 4
+#define TRIE_STACK_LENGTH 33
+#endif
+
+struct f_trie_node4
+{
+ ip4_addr addr, mask, accept;
+ u16 plen;
+ u16 local;
+ struct f_trie_node4 *c[1 << TRIE_STEP];
+};
+
+struct f_trie_node6
+{
+ ip6_addr addr, mask, accept;
+ u16 plen;
+ u16 local;
+ struct f_trie_node6 *c[1 << TRIE_STEP];
+};
+
struct f_trie_node
{
- ip_addr addr, mask, accept;
- uint plen;
- struct f_trie_node *c[2];
+ union {
+ struct f_trie_node4 v4;
+ struct f_trie_node6 v6;
+ };
};
struct f_trie
{
linpool *lp;
- int zero;
- uint node_size;
- struct f_trie_node root[0]; /* Root trie node follows */
+ u8 zero;
+ s8 ipv4; /* -1 for undefined / empty */
+ u16 data_size; /* Additional data for each trie node */
+ u32 prefix_count; /* Works only for restricted tries (pxlen == l == h) */
+ struct f_trie_node root; /* Root trie node */
+};
+
+struct f_trie_walk_state
+{
+ u8 ipv4;
+ u8 accept_length; /* Current inter-node prefix position */
+ u8 start_pos; /* Initial prefix position in stack[0] */
+ u8 local_pos; /* Current intra-node prefix position */
+ u8 stack_pos; /* Current node in stack below */
+ const struct f_trie_node *stack[TRIE_STACK_LENGTH];
};
struct f_tree *f_new_tree(void);
struct f_tree *build_tree(struct f_tree *);
const struct f_tree *find_tree(const struct f_tree *t, const struct f_val *val);
+const struct f_tree *find_tree_linear(const struct f_tree *t, const struct f_val *val);
int same_tree(const struct f_tree *t0, const struct f_tree *t2);
+int tree_node_count(const struct f_tree *t);
void tree_format(const struct f_tree *t, buffer *buf);
+void tree_walk(const struct f_tree *t, void (*hook)(const struct f_tree *, void *), void *data);
-struct f_trie *f_new_trie(linpool *lp, uint node_size);
+struct f_trie *f_new_trie(linpool *lp, uint data_size);
void *trie_add_prefix(struct f_trie *t, const net_addr *n, uint l, uint h);
int trie_match_net(const struct f_trie *t, const net_addr *n);
+int trie_match_longest_ip4(const struct f_trie *t, const net_addr_ip4 *net, net_addr_ip4 *dst, ip4_addr *found0);
+int trie_match_longest_ip6(const struct f_trie *t, const net_addr_ip6 *net, net_addr_ip6 *dst, ip6_addr *found0);
+void trie_walk_init(struct f_trie_walk_state *s, const struct f_trie *t, const net_addr *from);
+int trie_walk_next(struct f_trie_walk_state *s, net_addr *net);
int trie_same(const struct f_trie *t1, const struct f_trie *t2);
void trie_format(const struct f_trie *t, buffer *buf);
+static inline int
+trie_match_next_longest_ip4(net_addr_ip4 *n, ip4_addr *found)
+{
+ while (n->pxlen)
+ {
+ n->pxlen--;
+ ip4_clrbit(&n->prefix, n->pxlen);
+
+ if (ip4_getbit(*found, n->pxlen))
+ return 1;
+ }
+
+ return 0;
+}
+
+static inline int
+trie_match_next_longest_ip6(net_addr_ip6 *n, ip6_addr *found)
+{
+ while (n->pxlen)
+ {
+ n->pxlen--;
+ ip6_clrbit(&n->prefix, n->pxlen);
+
+ if (ip6_getbit(*found, n->pxlen))
+ return 1;
+ }
+
+ return 0;
+}
+
+
+#define TRIE_WALK_TO_ROOT_IP4(trie, net, dst) ({ \
+ net_addr_ip4 dst; \
+ ip4_addr _found; \
+ for (int _n = trie_match_longest_ip4(trie, net, &dst, &_found); \
+ _n; \
+ _n = trie_match_next_longest_ip4(&dst, &_found))
+
+#define TRIE_WALK_TO_ROOT_IP6(trie, net, dst) ({ \
+ net_addr_ip6 dst; \
+ ip6_addr _found; \
+ for (int _n = trie_match_longest_ip6(trie, net, &dst, &_found); \
+ _n; \
+ _n = trie_match_next_longest_ip6(&dst, &_found))
+
+#define TRIE_WALK_TO_ROOT_END })
+
+
+#define TRIE_WALK(trie, net, from) ({ \
+ net_addr net; \
+ struct f_trie_walk_state tws_; \
+ trie_walk_init(&tws_, trie, from); \
+ while (trie_walk_next(&tws_, &net))
+
+#define TRIE_WALK_END })
+
+
#define F_CMP_ERROR 999
+const char *f_type_name(enum f_type t);
+enum f_type f_type_element_type(enum f_type t);
+struct sym_scope *f_type_method_scope(enum f_type t);
+
int val_same(const struct f_val *v1, const struct f_val *v2);
int val_compare(const struct f_val *v1, const struct f_val *v2);
void val_format(const struct f_val *v, buffer *buf);
int clist_set_type(const struct f_tree *set, struct f_val *v);
static inline int eclist_set_type(const struct f_tree *set)
-{ return set->from.type == T_EC; }
+{ return !set || set->from.type == T_EC; }
static inline int lclist_set_type(const struct f_tree *set)
-{ return set->from.type == T_LC; }
+{ return !set || set->from.type == T_LC; }
+static inline int path_set_type(const struct f_tree *set)
+{ return !set || set->from.type == T_INT; }
+
+int clist_match_set(const struct adata *clist, const struct f_tree *set);
+int eclist_match_set(const struct adata *list, const struct f_tree *set);
+int lclist_match_set(const struct adata *list, const struct f_tree *set);
const struct adata *clist_filter(struct linpool *pool, const struct adata *list, const struct f_val *set, int pos);
const struct adata *eclist_filter(struct linpool *pool, const struct adata *list, const struct f_val *set, int pos);
(v.val.ad == &null_adata);
}
-extern const struct f_val f_const_empty_path, f_const_empty_clist, f_const_empty_eclist, f_const_empty_lclist;
+extern const struct f_val f_const_empty_prefix_set;
enum filter_return f_eval(const struct f_line *expr, struct linpool *tmp_pool, struct f_val *pres);
projects / thirdparty / bird.git / blobdiff