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