ipfilter/netinet/radix_ipf.c

33 					  ipf_rdx_node_t nodes[2], int *);
92 /*              nodes(O) - pair of ipf_rdx_node_t's to initialise with data */
95 /* Initialise the fields in a pair of radix tree nodes according to the     */
101 buildnodes(addr, mask, nodes)
103 	ipf_rdx_node_t nodes[2];
120 	bzero(&nodes[0], sizeof(ipf_rdx_node_t) * 2);
121 	nodes[0].maskbitcount = maskbits;
122 	nodes[0].index = -1 - (ADF_OFF_BITS + maskbits);
123 	nodes[0].addrkey = (u_32_t *)addr;
124 	nodes[0].maskkey = (u_32_t *)mask;
125 	nodes[0].addroff = nodes[0].addrkey + masklen;
126 	nodes[0].maskoff = nodes[0].maskkey + masklen;
127 	nodes[0].parent = &nodes[1];
128 	nodes[0].offset = masklen;
129 	nodes[0].lastmask = lastmask;
130 	nodes[1].offset = masklen;
131 	nodes[1].left = &nodes[0];
132 	nodes[1].maskbitcount = maskbits;
134 	(void) strcpy(nodes[0].name, "_BUILD.0");
135 	(void) strcpy(nodes[1].name, "_BUILD.1");
320 /* Paramters:   head(I)  - pointer to tree head to add nodes to             */
321 /*              nodes(I) - pointer to radix nodes to be added               */
324 /* Add the new radix tree entry that owns nodes[] to the tree given by head.*/
331 ipf_rx_insert(head, nodes, dup)
333 	ipf_rdx_node_t nodes[2];
353 	addr = nodes[0].addrkey;
376 	nodes[1].index = nlen;
377 	nodes[1].bitmask = htonl(0x80000000 >> (nlen & 0x1f));
378 	nodes[0].offset = nlen / 32;
379 	nodes[1].offset = nlen / 32;
390 	key = nodes[0].addrkey;
401 		prev->left = &nodes[1];
403 		prev->right = &nodes[1];
405 	cur->parent = &nodes[1];
406 	nodes[1].parent = prev;
407 	if ((key[nodes[1].offset] & nodes[1].bitmask) == 0) {
408 		nodes[1].right = cur;
410 		nodes[1].right = &nodes[0];
411 		nodes[1].left = cur;
414 	nodeoff = nodes[0].offset;
415 	nodekey = nodes[0].addrkey[nodeoff];
416 	nodemask = nodes[0].lastmask;
417 	nodebits = nodes[0].maskbitcount;
424 	for (cur = nodes[1].parent; cur->root == 0; cur = cur->parent) {
437 	mask->node = &nodes[0];
439 	mask->mask = nodes[0].maskkey;
440 	nodes[0].mymask = mask;
452 		 * No higher up nodes qualify, so attach mask locally.
454 		pmask = &nodes[0].masks;
463 	cur = nodes[1].right;
468 				ipf_rx_attach_mask(&nodes[0], mask);
474 	cur = nodes[1].left;
475 	if (cur->root == 0 && cur != &nodes[0]) {
479 				ipf_rx_attach_mask(&nodes[0], mask);
485 	return (&nodes[0]);
495 /*              nodes(I) - radix tree data nodes inside allocate structure  */
498 /* (addr,mask). No memory allocation for the radix nodes themselves is      */
504 /* the key material (addr,mask) and the radix tree nodes[].                 */
511 ipf_rx_addroute(head, addr, mask, nodes)
514 	ipf_rdx_node_t *nodes;
521 	buildnodes(addr, mask, nodes);
522 	x = ipf_rx_insert(head, nodes, &dup);
527 		node = &nodes[0];
549 			nodes[0].dupkey = x;
550 			prev->dupkey = &nodes[0];
551 			nodes[0].parent = prev;
553 				x->parent = &nodes[0];
555 			nodes[0].dupkey = x->dupkey;
557 			nodes[0].parent = prev;
558 			x->parent = &nodes[0];
560 				prev->left = &nodes[0];
562 				prev->right = &nodes[0];
566 	return &nodes[0];
624 			 * to other tree nodes need to be preserved and
825 	node = ptr->nodes;
946 	struct ipf_rdx_node nodes[2];
1162 	ipf_rdx_node_t *node = &stp->nodes[0];
1164 	if (stp->nodes[0].index > 0)
1165 		stp = (myst_t *)&stp->nodes[-1];
1216 		GNAME(&rnh->nodes[0]),
1217 		rnh->nodes[0].index, GNAME(rnh->nodes[0].parent),
1218 		GNAME(rnh->nodes[0].left), GNAME(rnh->nodes[0].right));
1220 		GNAME(&rnh->nodes[1]),
1221 		rnh->nodes[1].index, GNAME(rnh->nodes[1].parent),
1222 		GNAME(rnh->nodes[1].left), GNAME(rnh->nodes[1].right));
1224 		GNAME(&rnh->nodes[2]),
1225 		rnh->nodes[2].index, GNAME(rnh->nodes[2].parent),
1226 		GNAME(rnh->nodes[2].left), GNAME(rnh->nodes[2].right));
1399 	stp->nodes[0].parent = &stp->nodes[0];
1400 	stp->nodes[1].parent = &stp->nodes[1];
1425 	rn = ipf_rx_addroute(rnh, &stp->dst, &stp->mask, stp->nodes);
1447 		rn = &s1->nodes[1];