1 /****************************************************************************
2  *
3  * Copyright (C) 2014-2021 Cisco and/or its affiliates. All rights reserved.
4  * Copyright (C) 2006-2013 Sourcefire, Inc.
5  *
6  * This program is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License Version 2 as
8  * published by the Free Software Foundation.  You may not use, modify or
9  * distribute this program under any other version of the GNU General
10  * Public License.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, write to the Free Software
19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
20  *
21  ****************************************************************************/
22 
23 /*
24    trie.h
25 
26    A routing table for wordsized (32bits) bitstrings implemented as a
27    static level- and pathcompressed trie. For details please consult
28 
29       Stefan Nilsson and Gunnar Karlsson. Fast Address Look-Up
30       for Internet Routers. International Conference of Broadband
31       Communications (BC'97).
32 
33       http://www.hut.fi/~sni/papers/router/router.html
34 
35    The code presented in this file has been tested with care but is
36    not guaranteed for any purpose. The writer does not offer any
37    warranties nor does he accept any liabilities with respect to
38    the code.
39 
40    Stefan Nilsson, 4 nov 1997.
41 
42    Laboratory of Information Processing Science
43    Helsinki University of Technology
44    Stefan.Nilsson@hut.fi
45 */
46 
47 /*
48    The trie is represented by an array and each node consists of an
49    unsigned word. The first 5 bits (31-27) indicate the logarithm
50    of the branching factor. The next 5 bits (26-22) indicate the
51    skip value. The final 22 (21-0) bits is an adress, either to
52    another internal node, or the base vector.
53    The maximum capacity is 2^21 strings (or a few more). The trie
54    is prefixfree. All strings that are prefixes of another string
55    are stored separately.
56 */
57 
58 #ifndef RT_TRIE_H
59 #define RT_TRIE_H
60 
61 #define ADRSIZE 32        /* the number of bits in an address */
62 
63 /* A 32-bit word is used to hold the bit patterns of
64    the addresses. In IPv6 this should be 128 bits.
65    The following typedef is machine dependent.
66    A word must be 32 bits long! */
67 typedef unsigned long word;
68 
69 /* The trie is represented by an array and each node in
70    the trie is compactly represented using only 32 bits:
71    5 + 5 + 22 = branch + skip + adr */
72 typedef word node_t;
73 
74 #define NOPRE -1          /* an empty prefix pointer */
75 
76 #define SETBRANCH(branch)   ((branch)<<27)
77 #define GETBRANCH(node)     ((node)>>27)
78 #define SETSKIP(skip)       ((skip)<<22)
79 #define GETSKIP(node)       ((node)>>22 & 037)
80 #define SETADR(adr)         (adr)
81 #define GETADR(node)        ((node) & 017777777)
82 
83 /* extract n bits from str starting at position p */
84 #define EXTRACT(p, n, str) ((str)<<(p)>>(32-(n)))
85 
86 /* remove the first p bits from string */
87 #define REMOVE(p, str)   ((str)<<(p)>>(p))
88 
89 /* A next-hop table entry is a 32 bit string */
90 
91 typedef word policy_t;
92 
93 /* The routing table entries are initially stored in
94    a simple array */
95 
96 typedef struct entryrec *entry_t;
97 struct entryrec {
98    word data;          /* the routing entry */
99    int len;            /* and its length */
100    policy_t policy;  /* the corresponding next-hop */
101    int pre;            /* this auxiliary variable is used in the */
102 };                     /* construction of the final data structure */
103 
104 /* base vector */
105 
106 typedef struct baserec *base_t;
107 struct baserec {
108    word str;    /* the routing entry */
109    int len;     /* and its length */
110    int pre;     /* pointer to prefix table, -1 if no prefix */
111    int policy; /* pointer to next-hop table */
112 };
113 
114 typedef struct { /* compact version of above */
115    word str;
116    int len;
117    int pre;
118    int policy;
119 } comp_base_t;
120 
121 /* prefix vector */
122 
123 typedef struct prerec *pre_t;
124 struct prerec {
125    int len;     /* the length of the prefix */
126    int pre;     /* pointer to prefix, -1 if no prefix */
127    int policy; /* pointer to policy table */
128 };
129 
130 typedef struct { /* compact version of above */
131    int len;
132    int pre;
133    int policy;
134 } comp_pre_t;
135 
136 /* The complete routing table data structure consists of
137    a trie, a base vector, a prefix vector, and a next-hop table. */
138 
139 typedef struct routtablerec *routtable_t;
140 struct routtablerec {
141    node_t *trie;         /* the main trie search structure */
142    int triesize;
143    comp_base_t *base;    /* the base vector */
144    int basesize;
145    comp_pre_t *pre;      /* the prefix vector */
146    int presize;
147    policy_t *policy;     /* the next-hop table */
148    int policysize;
149 
150    int dirty;            /* Whether or not the table needs to be rebuilt */
151 };
152 
153 #endif
154