home *** CD-ROM | disk | FTP | other *** search
/ Amiga Plus Leser 19 / Amiga Plus Leser CD 19.iso / Tools / MorphOS / cvs-1.11.2 / source / amiga / netinclude / net / radix.h < prev    next >
Encoding:
C/C++ Source or Header  |  2002-11-18  |  4.2 KB  |  112 lines
  1. /*
  2.  * Copyright (c) 1988, 1989, 1993
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  * 1. Redistributions of source code must retain the above copyright
  9.  *    notice, this list of conditions and the following disclaimer.
  10.  * 2. Redistributions in binary form must reproduce the above copyright
  11.  *    notice, this list of conditions and the following disclaimer in the
  12.  *    documentation and/or other materials provided with the distribution.
  13.  * 3. All advertising materials mentioning features or use of this software
  14.  *    must display the following acknowledgement:
  15.  *    This product includes software developed by the University of
  16.  *    California, Berkeley and its contributors.
  17.  * 4. Neither the name of the University nor the names of its contributors
  18.  *    may be used to endorse or promote products derived from this software
  19.  *    without specific prior written permission.
  20.  *
  21.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31.  * SUCH DAMAGE.
  32.  *
  33.  *    @(#)radix.h    8.2 (Berkeley) 10/31/94
  34.  */
  35.  
  36. #ifndef _NET_RADIX_H_
  37. #define    _NET_RADIX_H_
  38.  
  39. #ifndef EXEC_TYPES_H
  40. #include <exec/types.h>
  41. #endif /* EXEC_TYPES_H */
  42.  
  43. /*
  44.  * Radix search tree node layout.
  45.  */
  46.  
  47. struct radix_node {
  48.     struct    radix_mask *rn_mklist;    /* list of masks contained in subtree */
  49.     struct    radix_node *rn_p;    /* parent */
  50.     WORD    rn_b;            /* bit offset; -1-index(netmask) */
  51.     UBYTE    rn_bmask;        /* node: mask for bit test*/
  52.     UBYTE    rn_flags;        /* enumerated next */
  53. #define RNF_NORMAL    1        /* leaf contains normal route */
  54. #define RNF_ROOT    2        /* leaf is root leaf for tree */
  55. #define RNF_ACTIVE    4        /* This node is alive (for rtfree) */
  56.     union {
  57.         struct {            /* leaf only data: */
  58.             APTR    rn_Key;    /* object of search */
  59.             APTR    rn_Mask;    /* netmask, if present */
  60.             struct    radix_node *rn_Dupedkey;
  61.         } rn_leaf;
  62.         struct {            /* node only data: */
  63.             LONG    rn_Off;        /* where to start compare */
  64.             struct    radix_node *rn_L;/* progeny */
  65.             struct    radix_node *rn_R;/* progeny */
  66.         } rn_node;
  67.     } rn_u;
  68. };
  69.  
  70. #define rn_dupedkey rn_u.rn_leaf.rn_Dupedkey
  71. #define rn_key rn_u.rn_leaf.rn_Key
  72. #define rn_mask rn_u.rn_leaf.rn_Mask
  73. #define rn_off rn_u.rn_node.rn_Off
  74. #define rn_l rn_u.rn_node.rn_L
  75. #define rn_r rn_u.rn_node.rn_R
  76.  
  77. /*
  78.  * Annotations to tree concerning potential routes applying to subtrees.
  79.  */
  80.  
  81. struct radix_mask {
  82.     WORD    rm_b;            /* bit offset; -1-index(netmask) */
  83.     UBYTE    rm_unused;        /* cf. rn_bmask */
  84.     UBYTE    rm_flags;        /* cf. rn_flags */
  85.     struct    radix_mask *rm_mklist;    /* more masks to try */
  86.     union    {
  87.         APTR    rmu_mask;        /* the mask */
  88.         struct    radix_node *rmu_leaf;    /* for normal routes */
  89.     } rm_rmu;
  90.     LONG    rm_refs;        /* # of references to this struct */
  91. };
  92.  
  93. #define rm_mask rm_rmu.rmu_mask
  94. #define rm_leaf rm_rmu.rmu_leaf        /* extra field would make 32 bytes */
  95.  
  96. struct radix_node_head {
  97.     struct    radix_node *rnh_treetop;
  98.     LONG    rnh_addrsize;            /* permit, but not require fixed keys */
  99.     LONG    rnh_pktsize;            /* permit, but not require fixed keys */
  100.     APTR    rnh_addaddr;            /* add based on sockaddr */
  101.     APTR    rnh_addpkt;            /* add based on packet hdr */
  102.     APTR    rnh_deladdr;            /* remove based on sockaddr */
  103.     APTR    rnh_delpkt;            /* remove based on packet hdr */
  104.     APTR    rnh_matchaddr;            /* locate based on sockaddr */
  105.     APTR    rnh_lookup;            /* locate based on sockaddr */
  106.     APTR    rnh_matchpkt;            /* locate based on packet hdr */
  107.     APTR    rnh_walktree;            /* traverse tree */
  108.     struct    radix_node rnh_nodes[3];    /* empty tree for common case */
  109. };
  110.  
  111. #endif /* _NET_RADIX_H_ */
  112.