projects / unix-history / blobdiff
? search:
summary | tags | clone url | shortlog | log | commit | commitdiff | tree
raw | inline | side by side
BSD 4_4_Lite2 release
[unix-history] / usr / src / sys / net / radix.h
diff --git a/usr/src/sys/net/radix.h b/usr/src/sys/net/radix.h
index 013397a..35f8a89 100644 (file)
--- a/usr/src/sys/net/radix.h
+++ b/usr/src/sys/net/radix.h
@@ -2,9 +2,35 @@
  * Copyright (c) 1988, 1989, 1993
  *     The Regents of the University of California.  All rights reserved.
  *
  * Copyright (c) 1988, 1989, 1993
  *     The Regents of the University of California.  All rights reserved.
  *
- * %sccs.include.redist.c%
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *     This product includes software developed by the University of
+ *     California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
  *
  *
- *     @(#)radix.h     8.2 (Berkeley) %G%
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ *     @(#)radix.h     8.2 (Berkeley) 10/31/94
  */
 
 #ifndef _RADIX_H_
  */
 
 #ifndef _RADIX_H_
@@ -15,7 +41,7 @@
  */
 
 struct radix_node {
  */
 
 struct radix_node {
-       struct  radix_node *rn_mklist;  /* list of masks contained in subtree */
+       struct  radix_mask *rn_mklist;  /* list of masks contained in subtree */
        struct  radix_node *rn_p;       /* parent */
        short   rn_b;                   /* bit offset; -1-index(netmask) */
        char    rn_bmask;               /* node: mask for bit test*/
        struct  radix_node *rn_p;       /* parent */
        short   rn_b;                   /* bit offset; -1-index(netmask) */
        char    rn_bmask;               /* node: mask for bit test*/
@@ -49,6 +75,34 @@ struct radix_node {
 #define rn_l rn_u.rn_node.rn_L
 #define rn_r rn_u.rn_node.rn_R
 
 #define rn_l rn_u.rn_node.rn_L
 #define rn_r rn_u.rn_node.rn_R
 
+/*
+ * Annotations to tree concerning potential routes applying to subtrees.
+ */
+
+extern struct radix_mask {
+       short   rm_b;                   /* bit offset; -1-index(netmask) */
+       char    rm_unused;              /* cf. rn_bmask */
+       u_char  rm_flags;               /* cf. rn_flags */
+       struct  radix_mask *rm_mklist;  /* more masks to try */
+       union   {
+               caddr_t rmu_mask;               /* the mask */
+               struct  radix_node *rmu_leaf;   /* for normal routes */
+       }       rm_rmu;
+       int     rm_refs;                /* # of references to this struct */
+} *rn_mkfreelist;
+
+#define rm_mask rm_rmu.rmu_mask
+#define rm_leaf rm_rmu.rmu_leaf                /* extra field would make 32 bytes */
+
+#define MKGet(m) {\
+       if (rn_mkfreelist) {\
+               m = rn_mkfreelist; \
+               rn_mkfreelist = (m)->rm_mklist; \
+       } else \
+               R_Malloc(m, struct radix_mask *, sizeof (*(m))); }\
+
+#define MKFree(m) { (m)->rm_mklist = rn_mkfreelist; rn_mkfreelist = (m);}
+
 struct radix_node_head {
        struct  radix_node *rnh_treetop;
        int     rnh_addrsize;           /* permit, but not require fixed keys */
 struct radix_node_head {
        struct  radix_node *rnh_treetop;
        int     rnh_addrsize;           /* permit, but not require fixed keys */
@@ -67,25 +121,10 @@ struct radix_node_head {
                __P((void *v, struct radix_node_head *head));
        struct  radix_node *(*rnh_lookup)       /* locate based on sockaddr */
                __P((void *v, void *mask, struct radix_node_head *head));
                __P((void *v, struct radix_node_head *head));
        struct  radix_node *(*rnh_lookup)       /* locate based on sockaddr */
                __P((void *v, void *mask, struct radix_node_head *head));
-       struct  radix_node *(*rnh_lookup)       /* locate based on sockaddr */
-               __P((void *v, void *mask, struct radix_node_head *head));
        struct  radix_node *(*rnh_matchpkt)     /* locate based on packet hdr */
                __P((void *v, struct radix_node_head *head));
        int     (*rnh_walktree)                 /* traverse tree */
                __P((struct radix_node_head *head, int (*f)(), void *w));
        struct  radix_node *(*rnh_matchpkt)     /* locate based on packet hdr */
                __P((void *v, struct radix_node_head *head));
        int     (*rnh_walktree)                 /* traverse tree */
                __P((struct radix_node_head *head, int (*f)(), void *w));
-/* mapping stuff */
-       struct  radix_index_table  {
-               short   limit;
-               short   offset;
-       }       *rnh_table;                     /* how to re-order the bits */
-       int     rnh_offset;                     /* for martialed keys */
-       int     (*rnh_bits_matched)             /* used in matching, insert */
-               __P((void *trial, void *ref,
-                    struct radix_node_head *head, int masklen));
-       int     (*rnh_set_mask)                 /* used in insertion */
-               __P((int index,
-                    struct radix_node *rn, struct radix_node_head *rnh));
-/* the treetop itself */
        struct  radix_node rnh_nodes[3];        /* empty tree for common case */
 };
 
        struct  radix_node rnh_nodes[3];        /* empty tree for common case */
 };
 
@@ -93,7 +132,6 @@ struct radix_node_head {
 #ifndef KERNEL
 #define Bcmp(a, b, n) bcmp(((char *)(a)), ((char *)(b)), (n))
 #define Bcopy(a, b, n) bcopy(((char *)(a)), ((char *)(b)), (unsigned)(n))
 #ifndef KERNEL
 #define Bcmp(a, b, n) bcmp(((char *)(a)), ((char *)(b)), (n))
 #define Bcopy(a, b, n) bcopy(((char *)(a)), ((char *)(b)), (unsigned)(n))
-#define Bcopy(a, b, n) bcopy(((char *)(a)), ((char *)(b)), (unsigned)(n))
 #define Bzero(p, n) bzero((char *)(p), (int)(n));
 #define R_Malloc(p, t, n) (p = (t) malloc((unsigned int)(n)))
 #define Free(p) free((char *)p);
 #define Bzero(p, n) bzero((char *)(p), (int)(n));
 #define R_Malloc(p, t, n) (p = (t) malloc((unsigned int)(n)))
 #define Free(p) free((char *)p);
@@ -104,8 +142,6 @@ struct radix_node_head {
 #define R_Malloc(p, t, n) (p = (t) malloc((unsigned long)(n), M_RTABLE, M_DONTWAIT))
 #define Free(p) free((caddr_t)p, M_RTABLE);
 #endif /*KERNEL*/
 #define R_Malloc(p, t, n) (p = (t) malloc((unsigned long)(n), M_RTABLE, M_DONTWAIT))
 #define Free(p) free((caddr_t)p, M_RTABLE);
 #endif /*KERNEL*/
-#endif /*KERNEL*/
-#endif /*KERNEL*/
 
 void    rn_init __P((void));
 int     rn_inithead __P((void **, int));
 
 void    rn_init __P((void));
 int     rn_inithead __P((void **, int));
@@ -121,16 +157,6 @@ struct radix_node
         *rn_match __P((void *, struct radix_node_head *)),
         *rn_newpair __P((void *, int, struct radix_node[2])),
         *rn_search __P((void *, struct radix_node *)),
         *rn_match __P((void *, struct radix_node_head *)),
         *rn_newpair __P((void *, int, struct radix_node[2])),
         *rn_search __P((void *, struct radix_node *)),
-        *rn_search_unmapped __P((void *, struct radix_node_head *));
-
-int     rn_set_unmapped_mask
-               __P((int, struct radix_node *, struct radix_node_head *)),
-        rn_set_mapped_mask
-               __P((int, struct radix_node *, struct radix_node_head *)),
-        rn_mapped_bits_matched
-               __P((void *, void *, struct radix_node_head *, int)),
-        rn_unmapped_bits_matched
-               __P((void *, void *, struct radix_node_head *, int));
-                                       
+        *rn_search_m __P((void *, struct radix_node *, void *));
 
 #endif /* _RADIX_H_ */
 
 #endif /* _RADIX_H_ */
Continuous source code history from original PDP-7 UNIX to FreeBSD 2, the first fully unencumbered FreeBSD release.