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