1/*
2 * Copyright (C) 2012 by Darren Reed.
3 *
4 * See the IPFILTER.LICENCE file for details on licencing.
5 */
6#ifndef __RADIX_IPF_H__
7#define __RADIX_IPF_H__
8
9#ifndef U_32_T
10typedef unsigned int u_32_t;
11# define U_32_T 1
12#endif
13
14typedef struct ipf_rdx_mask {
15 struct ipf_rdx_mask *next;
16 struct ipf_rdx_node *node;
17 u_32_t *mask;
18 int maskbitcount;
19} ipf_rdx_mask_t;
20
21typedef struct ipf_rdx_node {
22 struct ipf_rdx_node *left;
23 struct ipf_rdx_node *right;
24 struct ipf_rdx_node *parent;
25 struct ipf_rdx_node *dupkey;
26 struct ipf_rdx_mask *masks;
27 struct ipf_rdx_mask *mymask;
28 u_32_t *addrkey;
29 u_32_t *maskkey;
30 u_32_t *addroff;
31 u_32_t *maskoff;
32 u_32_t lastmask;
33 u_32_t bitmask;
34 int offset;
35 int index;
36 int maskbitcount;
37 int root;
38#ifdef RDX_DEBUG
39 char name[40];
40#endif
41} ipf_rdx_node_t;
42
43struct ipf_rdx_head;
44
45typedef void (* radix_walk_func_t)(ipf_rdx_node_t *, void *);
46typedef ipf_rdx_node_t *(* idx_hamn_func_t)(struct ipf_rdx_head *,
47 addrfamily_t *, addrfamily_t *,
48 ipf_rdx_node_t *);
49typedef ipf_rdx_node_t *(* idx_ham_func_t)(struct ipf_rdx_head *,
50 addrfamily_t *, addrfamily_t *);
51typedef ipf_rdx_node_t *(* idx_ha_func_t)(struct ipf_rdx_head *,
52 addrfamily_t *);
53typedef void (* idx_walk_func_t)(struct ipf_rdx_head *,
54 radix_walk_func_t, void *);
55
56typedef struct ipf_rdx_head {
57 ipf_rdx_node_t *root;
58 ipf_rdx_node_t nodes[3];
59 ipfmutex_t lock;
60 idx_hamn_func_t addaddr; /* add addr/mask to tree */
61 idx_ham_func_t deladdr; /* delete addr/mask from tree */
62 idx_ham_func_t lookup; /* look for specific addr/mask */
63 idx_ha_func_t matchaddr; /* search tree for address match */
64 idx_walk_func_t walktree; /* walk entire tree */
65} ipf_rdx_head_t;
66
67typedef struct radix_softc {
68 u_char *zeros;
69 u_char *ones;
70} radix_softc_t;
71
72#undef RADIX_NODE_HEAD_LOCK
73#undef RADIX_NODE_HEAD_UNLOCK
74#ifdef _KERNEL
75# define RADIX_NODE_HEAD_LOCK(x) MUTEX_ENTER(&(x)->lock)
76# define RADIX_NODE_HEAD_UNLOCK(x) MUTEX_UNLOCK(&(x)->lock)
77#else
78# define RADIX_NODE_HEAD_LOCK(x)
79# define RADIX_NODE_HEAD_UNLOCK(x)
80#endif
81
82extern void *ipf_rx_create(void);
83extern int ipf_rx_init(void *);
84extern void ipf_rx_destroy(void *);
85extern int ipf_rx_inithead(radix_softc_t *, ipf_rdx_head_t **);
86extern void ipf_rx_freehead(ipf_rdx_head_t *);
87extern ipf_rdx_node_t *ipf_rx_addroute(ipf_rdx_head_t *,
88 addrfamily_t *, addrfamily_t *,
89 ipf_rdx_node_t *);
90extern ipf_rdx_node_t *ipf_rx_delete(ipf_rdx_head_t *, addrfamily_t *,
91 addrfamily_t *);
92extern void ipf_rx_walktree(ipf_rdx_head_t *, radix_walk_func_t,
93 void *);
94
95#endif /* __RADIX_IPF_H__ */