contrib/ipfilter/radix_ipf.c

88 /* Parameters:  addr(I)  - network address for this radix node              */
142 /* Returns:     ipf_rdx_node_t * - pointer to a node in the radix tree.     */
143 /* Parameters:  tree(I)  - pointer to first right node in tree to search    */
146 /* Walk the radix tree given by "tree", looking for a leaf node that is a   */
170 /* Returns:     ipf_rdx_node_t * - NULL on error, else pointer to the node  */
176 /* "addr" and return a pointer to that node. This search will not match the */
187 	ipf_rdx_node_t *node;
198 	node = ipf_rx_find_addr(head->root, (u_32_t *)addr);
203 	for (cur = node; (cur != NULL) && (cur->root == 0); cur = cur->dupkey) {
214 	prev = node->parent;
217 	for (node = prev; node->root == 0; node = node->parent) {
219 		 * We know that the node hasn't matched so therefore only
221 		 * node nor the dupkey list.
223 		masknode = node->masks;
225 			if (masknode->maskbitcount > node->maskbitcount)
227 			cur = masknode->node;
228 			for (i = ADF_OFF >> 2; i <= node->offset; i++) {
242 /* Returns:     ipf_rdx_node_t * - NULL on error, else pointer to the node  */
257 	ipf_rdx_node_t *node;
280 		node = found;
281 		while (node != NULL && node->maskbitcount != count)
282 			node = node->dupkey;
283 		if (node == NULL)
285 		found = node;
294 /* Parameters:  node(I)  - pointer to a radix tree node                     */
297 /* Add the netmask to the given node in an ordering where the most specific */
301 ipf_rx_attach_mask(node, mask)
302 	ipf_rdx_node_t *node;
308 	for (pm = &node->masks; (m = *pm) != NULL; pm = &m->next)
318 /* Returns:     ipf_rdx_node_t * - NULL on error, else pointer to the node  */
322 /*              dup(O)   - set to 1 if node is a duplicate, else 0.         */
326 /* and the existing node pointer returned if there is a complete key match. */
337 	ipf_rdx_node_t *node;
355 	node = ipf_rx_find_addr(head->root, addr);
358 	data= (u_32_t *)&((addrfamily_t *)node->addrkey)->adf_addr;
365 		return (node);	/* Equal keys */
383 	 * this node. ipf_rx_fin_addr is not used here because the place
384 	 * to attach this node may be an internal node (same key, different
420 	 * Find the node up the tree with the largest pattern that still
421 	 * matches the node being inserted to see if this mask can be
437 	mask->node = &nodes[0];
461 	 * there that can be moved up to this newly inserted node.
490 /* Returns:     ipf_rdx_node_t * - NULL on error, else pointer to the node  */
497 /* Attempt to add a node to the radix tree. The key for the node is the     */
499 /* performed here, the data structure that this radix node is being used to */
500 /* find is expected to house the node data itself however the call to       */
506 /* The mechanics of inserting the node into the tree is handled by the      */
516 	ipf_rdx_node_t *node;
527 		node = &nodes[0];
535 		while ((x != NULL) && (x->maskbitcount > node->maskbitcount)) {
545 		if ((x != NULL) && (x->maskbitcount == node->maskbitcount))
572 /* Returns:     ipf_rdx_node_t * - NULL on error, else node removed from    */
592 	ipf_rdx_node_t *node;
605 		node = found;
606 		while (node != NULL && node->maskbitcount != count)
607 			node = node->dupkey;
608 		if (node == NULL)
610 		if (node != found) {
613 			 * the previous node on the list (rather than tree)
614 			 * and "dupkey" is the next node on the list.
616 			parent = node->parent;
617 			parent->dupkey = node->dupkey;
618 			node->dupkey->parent = parent;
622 			 * When removing the top node of the dupkey list,
627 			node = node->dupkey;
628 			node->parent = found->parent;
629 			node->right = found->right;
630 			node->left = found->left;
631 			found->right->parent = node;
632 			found->left->parent = node;
634 				parent->left = node;
636 				parent->right= node;
642 		 * Remove the node from the tree and reconnect the subtree
687 			 * We found an edge node.
711 	 * Remove mask associated with this node.
722 			if (m->node == cur) {
732 	 * Masks that have been brought up to this node from below need to
737 		cur = m->node;
755 /*              walker(I) - function to call for each node in the tree      */
757 /*                          node pointer                                    */
760 /* than recursive and tracks the next node in case the "walker" function    */
761 /* should happen to delete and free the current node. It thus goes without  */
772 	ipf_rdx_node_t *node = head->root;
775 	while (node->index >= 0)
776 		node = node->left;
779 		base = node;
780 		while ((node->parent->right == node) && (node->root == 0))
781 			node = node->parent;
783 		for (node = node->parent->right; node->index >= 0; )
784 			node = node->left;
785 		next = node;
787 		for (node = base; node != NULL; node = base) {
788 			base = node->dupkey;
789 			if (node->root == 0)
790 				walker(node, arg);
792 		node = next;
793 		if (node->root)
806 /* As a traditional radix tree, node 0 is used as the "0" sentinel and node */
807 /* "2" is used as the all ones sentinel, leaving node "1" as the root from  */
808 /* which the tree is hung with node "0" on its left and node "2" to the     */
818 	ipf_rdx_node_t *node;
825 	node = ptr->nodes;
826 	ptr->root = node + 1;
827 	node[0].index = ADF_OFF_BITS;
828 	node[0].index = -1 - node[0].index;
829 	node[1].index = ADF_OFF_BITS;
830 	node[2].index = node[0].index;
831 	node[0].parent = node + 1;
832 	node[1].parent = node + 1;
833 	node[2].parent = node + 1;
834 	node[1].bitmask = htonl(0x80000000);
835 	node[0].root = 1;
836 	node[1].root = 1;
837 	node[2].root = 1;
838 	node[0].offset = ADF_OFF_BITS >> 5;
839 	node[1].offset = ADF_OFF_BITS >> 5;
840 	node[2].offset = ADF_OFF_BITS >> 5;
841 	node[1].left = &node[0];
842 	node[1].right = &node[2];
843 	node[0].addrkey = (u_32_t *)softr->zeros;
844 	node[2].addrkey = (u_32_t *)softr->ones;
846 	(void) strcpy(node[0].name, "0_ROOT");
847 	(void) strcpy(node[1].name, "1_ROOT");
848 	(void) strcpy(node[2].name, "2_ROOT");
1034 ipf_rx_freenode(node, arg)
1035 	ipf_rdx_node_t *node;
1042 	stp = (myst_t *)node;
1140 nodeprinter(node, arg)
1141 	ipf_rdx_node_t *node;
1144 	myst_t *stp = (myst_t *)node;
1147 		node[0].name,
1148 		GNAME(node[1].left), GNAME(node[1].right),
1149 		GNAME(node[0].parent), GNAME(node[1].parent),
1150 		addrname(&stp->dst), node[0].maskbitcount);
1162 	ipf_rdx_node_t *node = &stp->nodes[0];
1167 	printf("Node %-9.9s ", node[0].name);
1168 	printf("L %-9.9s ", GNAME(node[1].left));
1169 	printf("R %-9.9s ", GNAME(node[1].right));
1170 	printf("P %9.9s", GNAME(node[0].parent));
1171 	printf("/%-9.9s ", GNAME(node[1].parent));