xnu-4903.270.47.tar.gz

[apple/xnu.git] / bsd / net / radix.h

diff --git a/bsd/net/radix.h b/bsd/net/radix.h
index 3431a2d2530580329f886c6f29585bfb91da4956..1bf0160107129137889860c8f16ec3312b9a8842 100644 (file)
--- a/bsd/net/radix.h
+++ b/bsd/net/radix.h
@@ -1,8 +1,8 @@
 /*
 /*

- * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
+ * Copyright (c) 2000-2008 Apple Inc. All rights reserved.

  *
  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
  *
  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@

- * 
+ *

  * This file contains Original Code and/or Modifications of Original Code
  * as defined in and that are subject to the Apple Public Source License
  * Version 2.0 (the 'License'). You may not use this file except in
  * This file contains Original Code and/or Modifications of Original Code
  * as defined in and that are subject to the Apple Public Source License
  * Version 2.0 (the 'License'). You may not use this file except in


@@ -11,10 +11,10 @@
  * unlawful or unlicensed copies of an Apple operating system, or to
  * circumvent, violate, or enable the circumvention or violation of, any
  * terms of an Apple operating system software license agreement.
  * unlawful or unlicensed copies of an Apple operating system, or to
  * circumvent, violate, or enable the circumvention or violation of, any
  * terms of an Apple operating system software license agreement.

- * 
+ *

  * Please obtain a copy of the License at
  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  * Please obtain a copy of the License at
  * http://www.opensource.apple.com/apsl/ and read it before using this file.

- * 
+ *

  * The Original Code and all software distributed under the License are
  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  * The Original Code and all software distributed under the License are
  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,


@@ -22,7 +22,7 @@
  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  * Please see the License for the specific language governing rights and
  * limitations under the License.
  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  * Please see the License for the specific language governing rights and
  * limitations under the License.

- * 
+ *

  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  */
 /*
  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  */
 /*


@@ -62,7 +62,7 @@
  */
 
 #ifndef _RADIX_H_
  */
 
 #ifndef _RADIX_H_

-#define        _RADIX_H_
+#define _RADIX_H_

 #include <sys/appleapiopts.h>
 
 #ifdef PRIVATE
 #include <sys/appleapiopts.h>
 
 #ifdef PRIVATE


@@ -76,100 +76,118 @@ MALLOC_DECLARE(M_RTABLE);
  */
 
 struct radix_node {
  */
 
 struct radix_node {

-       struct  radix_mask *rn_mklist;  /* list of masks contained in subtree */
-       struct  radix_node *rn_parent;  /* parent */
-       short   rn_bit;                 /* bit offset; -1-index(netmask) */
-       char    rn_bmask;               /* node: mask for bit test*/
-       u_char  rn_flags;               /* enumerated next */
-#define RNF_NORMAL     1               /* leaf contains normal route */
-#define RNF_ROOT       2               /* leaf is root leaf for tree */
-#define RNF_ACTIVE     4               /* This node is alive (for rtfree) */
+       struct  radix_mask *rn_mklist;  /* list of masks contained in subtree */
+       struct  radix_node *rn_parent;  /* parent */
+       short   rn_bit;                 /* bit offset; -1-index(netmask) */
+       char    rn_bmask;               /* node: mask for bit test*/
+       u_char  rn_flags;               /* enumerated next */
+#define RNF_NORMAL      1               /* leaf contains normal route */
+#define RNF_ROOT        2               /* leaf is root leaf for tree */
+#define RNF_ACTIVE      4               /* This node is alive (for rtfree) */

        union {
        union {

-               struct {                        /* leaf only data: */
-                       caddr_t rn_Key;         /* object of search */
-                       caddr_t rn_Mask;        /* netmask, if present */
-                       struct  radix_node *rn_Dupedkey;
+               struct {                        /* leaf only data: */
+                       caddr_t rn_Key;         /* object of search */
+                       caddr_t rn_Mask;        /* netmask, if present */
+                       struct  radix_node *rn_Dupedkey;

                } rn_leaf;
                } rn_leaf;

-               struct {                        /* node only data: */
-                       int     rn_Off;         /* where to start compare */
-                       struct  radix_node *rn_L;/* progeny */
-                       struct  radix_node *rn_R;/* progeny */
+               struct {                        /* node only data: */
+                       int     rn_Off;         /* where to start compare */
+                       struct  radix_node *rn_L;/* progeny */
+                       struct  radix_node *rn_R;/* progeny */

                } rn_node;
                } rn_node;

-       }               rn_u;
+       }               rn_u;

 #ifdef RN_DEBUG
        int rn_info;
        struct radix_node *rn_twin;
        struct radix_node *rn_ybro;
 #endif
 #ifdef RN_DEBUG
        int rn_info;
        struct radix_node *rn_twin;
        struct radix_node *rn_ybro;
 #endif

+
+#if __arm__ && (__BIGGEST_ALIGNMENT__ > 4)
+/* For the newer ARMv7k ABI where 64-bit types are 64-bit aligned, but pointers
+ * are 32-bit:
+ * Aligned to 64-bit since this is cast to rtentry, which is 64-bit aligned.
+ */
+} __attribute__ ((aligned(8)));
+#else

 };
 };

+#endif

 
 

-#define        rn_dupedkey     rn_u.rn_leaf.rn_Dupedkey
-#define        rn_key          rn_u.rn_leaf.rn_Key
-#define        rn_mask         rn_u.rn_leaf.rn_Mask
-#define        rn_offset       rn_u.rn_node.rn_Off
-#define        rn_left         rn_u.rn_node.rn_L
-#define        rn_right        rn_u.rn_node.rn_R
+#define rn_dupedkey     rn_u.rn_leaf.rn_Dupedkey
+#define rn_key          rn_u.rn_leaf.rn_Key
+#define rn_mask         rn_u.rn_leaf.rn_Mask
+#define rn_offset       rn_u.rn_node.rn_Off
+#define rn_left         rn_u.rn_node.rn_L
+#define rn_right        rn_u.rn_node.rn_R

 
 /*
  * Annotations to tree concerning potential routes applying to subtrees.
  */
 
 struct radix_mask {
 
 /*
  * Annotations to tree concerning potential routes applying to subtrees.
  */
 
 struct radix_mask {

-       short   rm_bit;                 /* 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 */
+       short   rm_bit;                 /* 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 */

 };
 
 };
 

-#define        rm_mask rm_rmu.rmu_mask
-#define        rm_leaf rm_rmu.rmu_leaf         /* extra field would make 32 bytes */
+#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) {\
 
 
 #define MKGet(m) {\
        if (rn_mkfreelist) {\

-               m = rn_mkfreelist; \
-               rn_mkfreelist = (m)->rm_mklist; \
+               m = rn_mkfreelist; \
+               rn_mkfreelist = (m)->rm_mklist; \

        } else \
        } else \

-               R_Malloc(m, struct radix_mask *, sizeof (*(m))); }\
+               R_Malloc(m, struct radix_mask *, sizeof (*(m))); }\

 
 #define MKFree(m) { (m)->rm_mklist = rn_mkfreelist; rn_mkfreelist = (m);}
 
 typedef int walktree_f_t(struct radix_node *, void *);
 
 #define MKFree(m) { (m)->rm_mklist = rn_mkfreelist; rn_mkfreelist = (m);}
 
 typedef int walktree_f_t(struct radix_node *, void *);

+typedef int rn_matchf_t(struct radix_node *, void *);

 
 struct radix_node_head {
 
 struct radix_node_head {

-       struct  radix_node *rnh_treetop;
-       int     rnh_addrsize;           /* permit, but not require fixed keys */
-       int     rnh_pktsize;            /* permit, but not require fixed keys */
-       struct  radix_node *(*rnh_addaddr)      /* add based on sockaddr */
-               (void *v, void *mask,
-                    struct radix_node_head *head, struct radix_node nodes[]);
-       struct  radix_node *(*rnh_addpkt)       /* add based on packet hdr */
-               (void *v, void *mask,
-                    struct radix_node_head *head, struct radix_node nodes[]);
-       struct  radix_node *(*rnh_deladdr)      /* remove based on sockaddr */
-               (void *v, void *mask, struct radix_node_head *head);
-       struct  radix_node *(*rnh_delpkt)       /* remove based on packet hdr */
-               (void *v, void *mask, struct radix_node_head *head);
-       struct  radix_node *(*rnh_matchaddr)    /* locate based on sockaddr */
-               (void *v, struct radix_node_head *head);
-       struct  radix_node *(*rnh_lookup)       /* locate based on sockaddr */
-               (void *v, void *mask, struct radix_node_head *head);
-       struct  radix_node *(*rnh_matchpkt)     /* locate based on packet hdr */
-               (void *v, struct radix_node_head *head);
-       int     (*rnh_walktree)                 /* traverse tree */
-               (struct radix_node_head *head, walktree_f_t *f, void *w);
-       int     (*rnh_walktree_from)            /* traverse tree below a */
-               (struct radix_node_head *head, void *a, void *m,
-                    walktree_f_t *f, void *w);
-       void    (*rnh_close)    /* do something when the last ref drops */
-               (struct radix_node *rn, struct radix_node_head *head);
-       struct  radix_node rnh_nodes[3];        /* empty tree for common case */
-       int     rnh_cnt;                        /* tree dimension */
+       struct  radix_node *rnh_treetop;
+       int     rnh_addrsize;           /* permit, but not require fixed keys */
+       int     rnh_pktsize;            /* permit, but not require fixed keys */
+       struct  radix_node *(*rnh_addaddr)      /* add based on sockaddr */
+       (void *v, void *mask,
+           struct radix_node_head *head, struct radix_node nodes[]);
+       struct  radix_node *(*rnh_addpkt)       /* add based on packet hdr */
+       (void *v, void *mask,
+           struct radix_node_head *head, struct radix_node nodes[]);
+       struct  radix_node *(*rnh_deladdr)      /* remove based on sockaddr */
+       (void *v, void *mask, struct radix_node_head *head);
+       struct  radix_node *(*rnh_delpkt)       /* remove based on packet hdr */
+       (void *v, void *mask, struct radix_node_head *head);
+       struct  radix_node *(*rnh_matchaddr)    /* locate based on sockaddr */
+       (void *v, struct radix_node_head *head);
+       /* locate based on sockaddr and rn_matchf_t() */
+       struct  radix_node *(*rnh_matchaddr_args)
+       (void *v, struct radix_node_head *head,
+           rn_matchf_t *f, void *w);
+       struct  radix_node *(*rnh_lookup)       /* locate based on sockaddr */
+       (void *v, void *mask, struct radix_node_head *head);
+       /* locate based on sockaddr, mask and rn_matchf_t() */
+       struct  radix_node *(*rnh_lookup_args)
+       (void *v, void *mask, struct radix_node_head *head,
+           rn_matchf_t *f, void *);
+       struct  radix_node *(*rnh_matchpkt)     /* locate based on packet hdr */
+       (void *v, struct radix_node_head *head);
+       int     (*rnh_walktree)                 /* traverse tree */
+       (struct radix_node_head *head, walktree_f_t *f, void *w);
+       int     (*rnh_walktree_from)            /* traverse tree below a */
+       (struct radix_node_head *head, void *a, void *m,
+       walktree_f_t *f, void *w);
+       void    (*rnh_close)    /* do something when the last ref drops */
+       (struct radix_node *rn, struct radix_node_head *head);
+       struct  radix_node rnh_nodes[3];        /* empty tree for common case */
+       int     rnh_cnt;                        /* tree dimension */

 };
 
 #ifndef KERNEL
 };
 
 #ifndef KERNEL


@@ -182,20 +200,23 @@ struct radix_node_head {
 #define Bcmp(a, b, n) bcmp(((caddr_t)(a)), ((caddr_t)(b)), (unsigned)(n))
 #define Bcopy(a, b, n) bcopy(((caddr_t)(a)), ((caddr_t)(b)), (unsigned)(n))
 #define Bzero(p, n) bzero((caddr_t)(p), (unsigned)(n));
 #define Bcmp(a, b, n) bcmp(((caddr_t)(a)), ((caddr_t)(b)), (unsigned)(n))
 #define Bcopy(a, b, n) bcopy(((caddr_t)(a)), ((caddr_t)(b)), (unsigned)(n))
 #define Bzero(p, n) bzero((caddr_t)(p), (unsigned)(n));

-#define R_Malloc(p, t, n) (p = (t) _MALLOC((unsigned long)(n), M_RTABLE, M_WAITOK))
-#define R_Free(p) FREE((caddr_t)p, M_RTABLE);
+#define R_Malloc(p, t, n) (p = (t) _MALLOC((uint32_t)(n), M_RTABLE, M_WAITOK))
+#define R_Free(p) _FREE((caddr_t)p, M_RTABLE);

 #endif /*KERNEL*/
 
 #endif /*KERNEL*/
 

-void    rn_init(void) __attribute__((section("__TEXT, initcode")));
-int     rn_inithead(void **, int);
-int     rn_refines(void *, void *);
+void     rn_init(void);
+int      rn_inithead(void **, int);
+int      rn_refines(void *, void *);

 struct radix_node
 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_lookup(void *v_arg, void *m_arg, struct radix_node_head *head),
-        *rn_match(void *, struct radix_node_head *);
+*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_lookup(void *v_arg, void *m_arg, struct radix_node_head *head),
+*rn_lookup_args(void *v_arg, void *m_arg, struct radix_node_head *head,
+    rn_matchf_t *, void *),
+*rn_match(void *, struct radix_node_head *),
+*rn_match_args(void *, struct radix_node_head *, rn_matchf_t *, void *);

 
 #endif /* PRIVATE */
 #endif /* _RADIX_H_ */
 
 #endif /* PRIVATE */
 #endif /* _RADIX_H_ */