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 10 typedef unsigned int u_32_t; 11 # define U_32_T 1 12 #endif 13 14 typedef 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 21 typedef 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 43 struct ipf_rdx_head; 44 45 typedef void (* radix_walk_func_t)(ipf_rdx_node_t *, void *); 46 typedef ipf_rdx_node_t *(* idx_hamn_func_t)(struct ipf_rdx_head *, 47 addrfamily_t *, addrfamily_t *, 48 ipf_rdx_node_t *); 49 typedef ipf_rdx_node_t *(* idx_ham_func_t)(struct ipf_rdx_head *, 50 addrfamily_t *, addrfamily_t *); 51 typedef ipf_rdx_node_t *(* idx_ha_func_t)(struct ipf_rdx_head *, 52 addrfamily_t *); 53 typedef void (* idx_walk_func_t)(struct ipf_rdx_head *, 54 radix_walk_func_t, void *); 55 56 typedef 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 67 typedef 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 82 extern void *ipf_rx_create(void); 83 extern int ipf_rx_init(void *); 84 extern void ipf_rx_destroy(void *); 85 extern int ipf_rx_inithead(radix_softc_t *, ipf_rdx_head_t **); 86 extern void ipf_rx_freehead(ipf_rdx_head_t *); 87 extern ipf_rdx_node_t *ipf_rx_addroute(ipf_rdx_head_t *, 88 addrfamily_t *, addrfamily_t *, 89 ipf_rdx_node_t *); 90 extern ipf_rdx_node_t *ipf_rx_delete(ipf_rdx_head_t *, addrfamily_t *, 91 addrfamily_t *); 92 extern void ipf_rx_walktree(ipf_rdx_head_t *, radix_walk_func_t, 93 void *); 94 95 #endif /* __RADIX_IPF_H__ */ 96