radix tree with multipath support. from kame. deraadt ok

user visible changes:
- you can add multiple routes with same key (route add A B then route add A C)
- you have to specify gateway address if there are multiple entries on the table
  (route delete A B, instead of route delete A)
kernel change:
- radix_node_head has an extra entry
- rnh_deladdr takes extra argument

TODO:
- actually take advantage of multipath (rtalloc -> rtalloc_mpath)

1 files changed, 5 insertions, 3 deletions

diff --git a/sys/net/radix.h b/sys/net/radix.h
index 1ebe63d3978..661858abd36 100644
--- a/sys/net/radix.h
+++ b/sys/net/radix.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: radix.h,v 1.11 2004/04/25 01:38:10 brad Exp $	*/
+/*	$OpenBSD: radix.h,v 1.12 2004/04/25 02:48:03 itojun Exp $	*/
 /*	$NetBSD: radix.h,v 1.8 1996/02/13 22:00:37 christos Exp $	*/
 
 /*
@@ -114,7 +114,7 @@ struct radix_node_head {
 		     struct radix_node_head *head, struct radix_node nodes[]);
 					/* remove based on sockaddr */
 	struct	radix_node *(*rnh_deladdr)(void *v, void *mask,
-		    struct radix_node_head *head);
+		    struct radix_node_head *head, struct radix_node *rn);
 					/* remove based on packet hdr */
 	struct	radix_node *(*rnh_delpkt)(void *v, void *mask,
 		    struct radix_node_head *head);
@@ -131,6 +131,7 @@ struct radix_node_head {
 	int	(*rnh_walktree)(struct radix_node_head *,
 		     int (*)(struct radix_node *, void *), void *);
 	struct	radix_node rnh_nodes[3];/* empty tree for common case */
+	int	rnh_multipath;		/* multipath? */
 };
 
 
@@ -159,7 +160,8 @@ struct radix_node
 	 *rn_addmask(void *, int, int),
 	 *rn_addroute(void *, void *, struct radix_node_head *,
 			struct radix_node [2]),
-	 *rn_delete(void *, void *, struct radix_node_head *),
+	 *rn_delete(void *, void *, struct radix_node_head *,
+			struct radix_node *),
 	 *rn_insert(void *, struct radix_node_head *, int *,
 			struct radix_node [2]),
 	 *rn_lookup(void *, void *, struct radix_node_head *),