workbench/network/common/include/net/radix.h

   1 /*
   2  * Copyright (C) 1993 AmiTCP/IP Group, <amitcp-group@hut.fi>
   3  *                    Helsinki University of Technology, Finland.
   4  *                    All rights reserved.
   5  * Copyright (C) 2005 Neil Cafferkey
   6  *
   7  * This program is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU General Public License version 2 as
   9  * published by the Free Software Foundation.
  10  *
  11  * This program is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  14  * General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  19  * MA 02111-1307, USA.
  20  *
  21  */
  22
  23 /*
  24  * Mach Operating System
  25  * Copyright (c) 1992 Carnegie Mellon University
  26  * All Rights Reserved.
  27  *
  28  * Permission to use, copy, modify and distribute this software and its
  29  * documentation is hereby granted, provided that both the copyright
  30  * notice and this permission notice appear in all copies of the
  31  * software, derivative works or modified versions, and any portions
  32  * thereof, and that both notices appear in supporting documentation.
  33  *
  34  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
  35  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
  36  * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
  37  *
  38  * Carnegie Mellon requests users of this software to return to
  39  *
  40  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
  41  *  School of Computer Science
  42  *  Carnegie Mellon University
  43  *  Pittsburgh PA 15213-3890
  44  *
  45  * any improvements or extensions that they make and grant Carnegie Mellon
  46  * the rights to redistribute these changes.
  47  */
  48
  49 /*
  50  * Copyright (c) 1988, 1989 Regents of the University of California.
  51  * All rights reserved.
  52  *
  53  * Redistribution and use in source and binary forms, with or without
  54  * modification, are permitted provided that the following conditions
  55  * are met:
  56  * 1. Redistributions of source code must retain the above copyright
  57  *    notice, this list of conditions and the following disclaimer.
  58  * 2. Redistributions in binary form must reproduce the above copyright
  59  *    notice, this list of conditions and the following disclaimer in the
  60  *    documentation and/or other materials provided with the distribution.
  61  * 3. All advertising materials mentioning features or use of this software
  62  *    must display the following acknowledgement:
  63  *      This product includes software developed by the University of
  64  *      California, Berkeley and its contributors.
  65  * 4. Neither the name of the University nor the names of its contributors
  66  *    may be used to endorse or promote products derived from this software
  67  *    without specific prior written permission.
  68  *
  69  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  70  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  71  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  72  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  73  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  74  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  75  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  76  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  77  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  78  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  79  * SUCH DAMAGE.
  80  *
  81  *      @(#)radix.h     7.4 (Berkeley) 6/28/90
  82  */
  83
  84 #ifndef NET_RADIX_H
  85 #define NET_RADIX_H
  86
  87 /*#include <sys/malloc.h>*/
  88
  89 /*
  90  * Radix search tree node layout.
  91  */
  92
  93 struct radix_node {
  94         struct  radix_mask *rn_mklist;  /* list of masks contained in subtree */
  95         struct  radix_node *rn_p;       /* parent */
  96         short   rn_b;                   /* bit offset; -1-index(netmask) */
  97         char    rn_bmask;               /* node: mask for bit test*/
  98         u_char  rn_flags;               /* enumerated next */
  99 #define RNF_NORMAL      1               /* leaf contains normal route */
 100 #define RNF_ROOT        2               /* leaf is root leaf for tree */
 101 #define RNF_ACTIVE      4               /* This node is alive (for rtfree) */
 102         union {
 103                 struct {                        /* leaf only data: */
 104                         caddr_t rn_Key; /* object of search */
 105                         caddr_t rn_Mask;        /* netmask, if present */
 106                         struct  radix_node *rn_Dupedkey;
 107                 } rn_leaf;
 108                 struct {                        /* node only data: */
 109                         int     rn_Off;         /* where to start compare */
 110                         struct  radix_node *rn_L;/* progeny */
 111                         struct  radix_node *rn_R;/* progeny */
 112                 }rn_node;
 113         }               rn_u;
 114 #ifdef RN_DEBUG
 115         int rn_info;
 116         struct radix_node *rn_twin;
 117         struct radix_node *rn_ybro;
 118 #endif
 119 };
 120
 121 #define MAXKEYLEN 32
 122
 123 #define rn_dupedkey rn_u.rn_leaf.rn_Dupedkey
 124 #define rn_key rn_u.rn_leaf.rn_Key
 125 #define rn_mask rn_u.rn_leaf.rn_Mask
 126 #define rn_off rn_u.rn_node.rn_Off
 127 #define rn_l rn_u.rn_node.rn_L
 128 #define rn_r rn_u.rn_node.rn_R
 129
 130 /*
 131  * Annotations to tree concerning potential routes applying to subtrees.
 132  */
 133
 134 extern struct radix_mask {
 135         short   rm_b;                   /* bit offset; -1-index(netmask) */
 136         char    rm_unused;              /* cf. rn_bmask */
 137         u_char  rm_flags;               /* cf. rn_flags */
 138         struct  radix_mask *rm_mklist;  /* more masks to try */
 139         caddr_t rm_mask;                /* the mask */
 140         int     rm_refs;                /* # of references to this struct */
 141 } *rn_mkfreelist;
 142
 143 #define MKGet(m) {\
 144         if (rn_mkfreelist) {\
 145                 m = rn_mkfreelist; \
 146                 rn_mkfreelist = (m)->rm_mklist; \
 147         } else \
 148                 R_Malloc(m, struct radix_mask *, sizeof (*(m))); }\
 149
 150 #define MKFree(m) { (m)->rm_mklist = rn_mkfreelist; rn_mkfreelist = (m);}
 151
 152 extern struct radix_node_head {
 153         struct  radix_node_head *rnh_next;
 154         struct  radix_node *rnh_treetop;
 155         int     rnh_af;
 156         struct  radix_node rnh_nodes[3];
 157 } *radix_node_head;
 158
 159
 160 /*#ifndef KERNEL*/
 161 #if 0
 162 #define Bcmp(a, b, n) bcmp(((char *)(a)), ((char *)(b)), (n))
 163 #define Bzero(p, n) bzero((char *)(p), (int)(n));
 164 #define R_Malloc(p, t, n) (p = (t) malloc((unsigned int)(n)))
 165 #define Free(p) free((char *)p);
 166 #else
 167 #define Bcmp(a, b, n) bcmp(((caddr_t)(a)), ((caddr_t)(b)), (unsigned)(n))
 168 #define Bcopy(a, b, n) bcopy(((caddr_t)(a)), ((caddr_t)(b)), (unsigned)(n))
 169 #define Bzero(p, n) bzero((caddr_t)(p), (unsigned)(n));
 170 #define R_Malloc(p, t, n) (p = (t) bsd_malloc((unsigned long)(n), M_RTABLE, M_DONTWAIT))
 171 #define Free(p) bsd_free((caddr_t)p, M_RTABLE);
 172 #endif /*KERNEL*/
 173
 174 #endif /*NET_RADIX_H*/
 175