include/radix.h

   1 #ifndef SQUID_RADIX_H
   2 #define SQUID_RADIX_H
   3
   4 /*
   5  * Copyright (c) 1988, 1989, 1993
   6  *      The Regents of the University of California.  All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 3. All advertising materials mentioning features or use of this software
  17  *    must display the following acknowledgement:
  18  *      This product includes software developed by the University of
  19  *      California, Berkeley and its contributors.
  20  * 4. Neither the name of the University nor the names of its contributors
  21  *    may be used to endorse or promote products derived from this software
  22  *    without specific prior written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34  * SUCH DAMAGE.
  35  *
  36  *      @(#)radix.h     8.2 (Berkeley) 10/31/94
  37  */
  38
  39 #undef RN_DEBUG
  40 /*
  41  * Radix search tree node layout.
  42  */
  43
  44 struct squid_radix_node {
  45
  46     struct squid_radix_mask *rn_mklist; /* list of masks contained in subtree */
  47
  48     struct squid_radix_node *rn_p;      /* parent */
  49     short rn_b;                 /* bit offset; -1-index(netmask) */
  50     char rn_bmask;              /* node: mask for bit test */
  51     unsigned char rn_flags;     /* enumerated next */
  52 #define RNF_NORMAL      1       /* leaf contains normal route */
  53 #define RNF_ROOT        2       /* leaf is root leaf for tree */
  54 #define RNF_ACTIVE      4       /* This node is alive (for rtfree) */
  55
  56     union {
  57
  58         struct {                /* leaf only data: */
  59             char *rn_Key;       /* object of search */
  60             char *rn_Mask;      /* netmask, if present */
  61
  62             struct squid_radix_node *rn_Dupedkey;
  63         } rn_leaf;
  64
  65         struct {                /* node only data: */
  66             int rn_Off;         /* where to start compare */
  67
  68             struct squid_radix_node *rn_L;      /* progeny */
  69
  70             struct squid_radix_node *rn_R;      /* progeny */
  71         } rn_node;
  72     } rn_u;
  73 #ifdef RN_DEBUG
  74
  75     int rn_info;
  76
  77     struct squid_radix_node *rn_twin;
  78
  79     struct squid_radix_node *rn_ybro;
  80 #endif
  81 };
  82
  83 #define rn_key rn_u.rn_leaf.rn_Key
  84 #define rn_mask rn_u.rn_leaf.rn_Mask
  85
  86 /*
  87  * Annotations to tree concerning potential routes applying to subtrees.
  88  */
  89
  90 struct squid_radix_mask {
  91     short rm_b;                 /* bit offset; -1-index(netmask) */
  92     char rm_unused;             /* cf. rn_bmask */
  93     unsigned char rm_flags;     /* cf. rn_flags */
  94
  95     struct squid_radix_mask *rm_mklist; /* more masks to try */
  96     union {
  97         char *rmu_mask;         /* the mask */
  98
  99         struct squid_radix_node *rmu_leaf;      /* for normal routes */
 100     } rm_rmu;
 101     int rm_refs;                /* # of references to this struct */
 102 };
 103
 104 struct squid_radix_node_head {
 105
 106     struct squid_radix_node *rnh_treetop;
 107     int rnh_addrsize;           /* permit, but not require fixed keys */
 108     int rnh_pktsize;            /* permit, but not require fixed keys */
 109
 110     struct squid_radix_node *(*rnh_addaddr)     /* add based on sockaddr */
 111     (void *v, void *mask, struct squid_radix_node_head * head, struct squid_radix_node nodes[]);
 112
 113     struct squid_radix_node *(*rnh_addpkt)      /* add based on packet hdr */
 114     (void *v, void *mask, struct squid_radix_node_head * head, struct squid_radix_node nodes[]);
 115
 116     struct squid_radix_node *(*rnh_deladdr)     /* remove based on sockaddr */
 117     (void *v, void *mask, struct squid_radix_node_head * head);
 118
 119     struct squid_radix_node *(*rnh_delpkt)      /* remove based on packet hdr */
 120     (void *v, void *mask, struct squid_radix_node_head * head);
 121
 122     struct squid_radix_node *(*rnh_matchaddr)           /* locate based on sockaddr */
 123     (void *v, struct squid_radix_node_head * head);
 124
 125     struct squid_radix_node *(*rnh_lookup)      /* locate based on sockaddr */
 126
 127     (void *v, void *mask, struct squid_radix_node_head * head);
 128
 129     struct squid_radix_node *(*rnh_matchpkt)    /* locate based on packet hdr */
 130     (void *v, struct squid_radix_node_head * head);
 131
 132     int (*rnh_walktree)         /* traverse tree */
 133     (struct squid_radix_node_head * head, int (*f) (struct squid_radix_node *, void *), void *w);
 134
 135     struct squid_radix_node rnh_nodes[3];       /* empty tree for common case */
 136 };
 137
 138 SQUIDCEXTERN void squid_rn_init (void);
 139
 140 SQUIDCEXTERN int squid_rn_inithead(struct squid_radix_node_head **, int);
 141 SQUIDCEXTERN int squid_rn_refines(void *, void *);
 142
 143 SQUIDCEXTERN int squid_rn_walktree(struct squid_radix_node_head *, int (*)(struct squid_radix_node *, void *), void *);
 144
 145 SQUIDCEXTERN struct squid_radix_node *squid_rn_addmask(void *, int, int);
 146
 147 SQUIDCEXTERN struct squid_radix_node *squid_rn_addroute(void *, void *, struct squid_radix_node_head *, struct squid_radix_node[2]);
 148
 149 SQUIDCEXTERN struct squid_radix_node *squid_rn_delete(void *, void *, struct squid_radix_node_head *);
 150
 151 SQUIDCEXTERN struct squid_radix_node *squid_rn_insert(void *, struct squid_radix_node_head *, int *, struct squid_radix_node[2]);
 152
 153 SQUIDCEXTERN struct squid_radix_node *squid_rn_match(void *, struct squid_radix_node_head *);
 154
 155 SQUIDCEXTERN struct squid_radix_node *squid_rn_newpair(void *, int, struct squid_radix_node[2]);
 156
 157 SQUIDCEXTERN struct squid_radix_node *squid_rn_search(void *, struct squid_radix_node *);
 158
 159 SQUIDCEXTERN struct squid_radix_node *squid_rn_search_m(void *, struct squid_radix_node *, void *);
 160
 161 SQUIDCEXTERN struct squid_radix_node *squid_rn_lookup(void *, void *, struct squid_radix_node_head *);
 162
 163 #endif /* SQUID_RADIX_H */