OpenCores
URL https://opencores.org/ocsvn/or1k/or1k/trunk

Subversion Repositories or1k

[/] [or1k/] [trunk/] [ecos-2.0/] [packages/] [net/] [tcpip/] [v2_0/] [include/] [net/] [radix.h] - Blame information for rev 1765

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 1254 phoenix
//==========================================================================
2
//
3
//      include/net/radix.h
4
//
5
//      
6
//
7
//==========================================================================
8
//####BSDCOPYRIGHTBEGIN####
9
//
10
// -------------------------------------------
11
//
12
// Portions of this software may have been derived from OpenBSD or other sources,
13
// and are covered by the appropriate copyright disclaimers included herein.
14
//
15
// -------------------------------------------
16
//
17
//####BSDCOPYRIGHTEND####
18
//==========================================================================
19
//#####DESCRIPTIONBEGIN####
20
//
21
// Author(s):    gthomas
22
// Contributors: gthomas
23
// Date:         2000-01-10
24
// Purpose:      
25
// Description:  
26
//              
27
//
28
//####DESCRIPTIONEND####
29
//
30
//==========================================================================
31
 
32
 
33
/*      $OpenBSD: radix.h,v 1.3 1996/09/05 08:42:34 mickey Exp $        */
34
/*      $NetBSD: radix.h,v 1.8 1996/02/13 22:00:37 christos Exp $       */
35
 
36
/*
37
 * Copyright (c) 1988, 1989, 1993
38
 *      The Regents of the University of California.  All rights reserved.
39
 *
40
 * Redistribution and use in source and binary forms, with or without
41
 * modification, are permitted provided that the following conditions
42
 * are met:
43
 * 1. Redistributions of source code must retain the above copyright
44
 *    notice, this list of conditions and the following disclaimer.
45
 * 2. Redistributions in binary form must reproduce the above copyright
46
 *    notice, this list of conditions and the following disclaimer in the
47
 *    documentation and/or other materials provided with the distribution.
48
 * 3. All advertising materials mentioning features or use of this software
49
 *    must display the following acknowledgement:
50
 *      This product includes software developed by the University of
51
 *      California, Berkeley and its contributors.
52
 * 4. Neither the name of the University nor the names of its contributors
53
 *    may be used to endorse or promote products derived from this software
54
 *    without specific prior written permission.
55
 *
56
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
57
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
58
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
59
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
60
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
61
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
62
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
63
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
64
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
65
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
66
 * SUCH DAMAGE.
67
 *
68
 *      @(#)radix.h     8.2 (Berkeley) 10/31/94
69
 */
70
 
71
#ifndef _NET_RADIX_H_
72
#define _NET_RADIX_H_
73
 
74
/*
75
 * Radix search tree node layout.
76
 */
77
 
78
struct radix_node {
79
        struct  radix_mask *rn_mklist;  /* list of masks contained in subtree */
80
        struct  radix_node *rn_p;       /* parent */
81
        short   rn_b;                   /* bit offset; -1-index(netmask) */
82
        char    rn_bmask;               /* node: mask for bit test*/
83
        u_char  rn_flags;               /* enumerated next */
84
#define RNF_NORMAL      1               /* leaf contains normal route */
85
#define RNF_ROOT        2               /* leaf is root leaf for tree */
86
#define RNF_ACTIVE      4               /* This node is alive (for rtfree) */
87
        union {
88
                struct {                        /* leaf only data: */
89
                        caddr_t rn_Key;         /* object of search */
90
                        caddr_t rn_Mask;        /* netmask, if present */
91
                        struct  radix_node *rn_Dupedkey;
92
                } rn_leaf;
93
                struct {                        /* node only data: */
94
                        int     rn_Off;         /* where to start compare */
95
                        struct  radix_node *rn_L;/* progeny */
96
                        struct  radix_node *rn_R;/* progeny */
97
                } rn_node;
98
        }       rn_u;
99
#ifdef RN_DEBUG
100
        int rn_info;
101
        struct radix_node *rn_twin;
102
        struct radix_node *rn_ybro;
103
#endif
104
};
105
 
106
#define rn_dupedkey rn_u.rn_leaf.rn_Dupedkey
107
#define rn_key rn_u.rn_leaf.rn_Key
108
#define rn_mask rn_u.rn_leaf.rn_Mask
109
#define rn_off rn_u.rn_node.rn_Off
110
#define rn_l rn_u.rn_node.rn_L
111
#define rn_r rn_u.rn_node.rn_R
112
 
113
/*
114
 * Annotations to tree concerning potential routes applying to subtrees.
115
 */
116
 
117
extern struct radix_mask {
118
        short   rm_b;                   /* bit offset; -1-index(netmask) */
119
        char    rm_unused;              /* cf. rn_bmask */
120
        u_char  rm_flags;               /* cf. rn_flags */
121
        struct  radix_mask *rm_mklist;  /* more masks to try */
122
        union   {
123
                caddr_t rmu_mask;               /* the mask */
124
                struct  radix_node *rmu_leaf;   /* for normal routes */
125
        }       rm_rmu;
126
        int     rm_refs;                /* # of references to this struct */
127
} *rn_mkfreelist;
128
 
129
#define rm_mask rm_rmu.rmu_mask
130
#define rm_leaf rm_rmu.rmu_leaf         /* extra field would make 32 bytes */
131
 
132
#define MKGet(m) {\
133
        if (rn_mkfreelist) {\
134
                m = rn_mkfreelist; \
135
                rn_mkfreelist = (m)->rm_mklist; \
136
        } else \
137
                R_Malloc(m, struct radix_mask *, sizeof (*(m))); }\
138
 
139
#define MKFree(m) { (m)->rm_mklist = rn_mkfreelist; rn_mkfreelist = (m);}
140
 
141
struct radix_node_head {
142
        struct  radix_node *rnh_treetop;
143
        int     rnh_addrsize;           /* permit, but not require fixed keys */
144
        int     rnh_pktsize;            /* permit, but not require fixed keys */
145
        struct  radix_node *(*rnh_addaddr)      /* add based on sockaddr */
146
                __P((void *v, void *mask,
147
                     struct radix_node_head *head, struct radix_node nodes[]));
148
        struct  radix_node *(*rnh_addpkt)       /* add based on packet hdr */
149
                __P((void *v, void *mask,
150
                     struct radix_node_head *head, struct radix_node nodes[]));
151
        struct  radix_node *(*rnh_deladdr)      /* remove based on sockaddr */
152
                __P((void *v, void *mask, struct radix_node_head *head));
153
        struct  radix_node *(*rnh_delpkt)       /* remove based on packet hdr */
154
                __P((void *v, void *mask, struct radix_node_head *head));
155
        struct  radix_node *(*rnh_matchaddr)    /* locate based on sockaddr */
156
                __P((void *v, struct radix_node_head *head));
157
        struct  radix_node *(*rnh_lookup)       /* locate based on sockaddr */
158
                __P((void *v, void *mask, struct radix_node_head *head));
159
        struct  radix_node *(*rnh_matchpkt)     /* locate based on packet hdr */
160
                __P((void *v, struct radix_node_head *head));
161
        int     (*rnh_walktree)                 /* traverse tree */
162
                __P((struct radix_node_head *,
163
                     int (*)(struct radix_node *, void *), void *));
164
        struct  radix_node rnh_nodes[3];        /* empty tree for common case */
165
};
166
 
167
 
168
#ifndef _KERNEL
169
#define Bcmp(a, b, n) bcmp(((char *)(a)), ((char *)(b)), (n))
170
#define Bcopy(a, b, n) bcopy(((char *)(a)), ((char *)(b)), (unsigned)(n))
171
#define Bzero(p, n) bzero((char *)(p), (int)(n));
172
#define R_Malloc(p, t, n) (p = (t) malloc((unsigned int)(n)))
173
#define Free(p) free((char *)p);
174
#else
175
#define Bcmp(a, b, n) bcmp(((caddr_t)(a)), ((caddr_t)(b)), (unsigned)(n))
176
#define Bcopy(a, b, n) bcopy(((caddr_t)(a)), ((caddr_t)(b)), (unsigned)(n))
177
#define Bzero(p, n) bzero((caddr_t)(p), (unsigned)(n));
178
#define R_Malloc(p, t, n) (p = (t) malloc((unsigned long)(n), M_RTABLE, M_DONTWAIT))
179
#define Free(p) free((caddr_t)p, M_RTABLE);
180
#endif /* !_KERNEL */
181
 
182
#if defined(_KERNEL) || defined(_ROUTED)
183
void     rn_init __P((void));
184
int      rn_inithead __P((void **, int));
185
int      rn_refines __P((void *, void *));
186
int      rn_walktree __P((struct radix_node_head *,
187
                          int (*)(struct radix_node *, void *), void *));
188
struct radix_node
189
         *rn_addmask __P((void *, int, int)),
190
         *rn_addroute __P((void *, void *, struct radix_node_head *,
191
                        struct radix_node [2])),
192
         *rn_delete __P((void *, void *, struct radix_node_head *)),
193
         *rn_insert __P((void *, struct radix_node_head *, int *,
194
                        struct radix_node [2])),
195
         *rn_lookup __P((void *, void *, struct radix_node_head *)),
196
         *rn_match __P((void *, struct radix_node_head *)),
197
         *rn_newpair __P((void *, int, struct radix_node[2])),
198
         *rn_search __P((void *, struct radix_node *)),
199
         *rn_search_m __P((void *, struct radix_node *, void *));
200
#endif /* define(_KERNEL) || defined(_ROUTED) */
201
 
202
#endif /* !_NET_RADIX_H_ */

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.