## Revision 51762a45 filter/trie.c

View differences:

filter/trie.c
21 21
``` *
```
22 22
``` * We use a bitmask (&accept) to represent accepted prefix lengths
```
23 23
``` * at a node. As there are 33 prefix lengths (0..32 for IPv4), but
```
24
``` * there is just one prefix of zero length in the whole trie so we
```
24
``` * there is just one prefix of zero length in the whole trie so we
```
25 25
``` * have &zero flag in &f_trie (indicating whether the trie accepts
```
26 26
``` * prefix 0.0.0.0/0) as a special case, and &accept bitmask
```
27 27
``` * represents accepted prefix lengths from 1 to 32.
```
......
75 75
```#include "filter/filter.h"
```
76 76

77 77
```/**
```
78
``` * f_new_trie
```
79
``` *
```
80
``` * Allocates and returns a new empty trie.
```
78
``` * f_new_trie - allocates and returns a new empty trie
```
79
``` * @lp: linear pool to allocate items from
```
80
``` * @node_size: node size to be used (&f_trie_node and user data)
```
81 81
``` */
```
82 82
```struct f_trie *
```
83
```f_new_trie(linpool *lp)
```
83
```f_new_trie(linpool *lp, uint node_size)
```
84 84
```{
```
85 85
```  struct f_trie * ret;
```
86
```  ret = lp_allocz(lp, sizeof(struct f_trie));
```
86
```  ret = lp_allocz(lp, sizeof(struct f_trie) + node_size);
```
87 87
```  ret->lp = lp;
```
88
```  ret->node_size = node_size;
```
88 89
```  return ret;
```
89 90
```}
```
90 91

91 92
```static inline struct f_trie_node *
```
92 93
```new_node(struct f_trie *t, int plen, ip_addr paddr, ip_addr pmask, ip_addr amask)
```
93 94
```{
```
94
```  struct f_trie_node *n = lp_allocz(t->lp, sizeof(struct f_trie_node));
```
95
```  struct f_trie_node *n = lp_allocz(t->lp, t->node_size);
```
95 96
```  n->plen = plen;
```
96 97
```  n->addr = paddr;
```
97 98
```  n->mask = pmask;
```
......
110 111
``` * @t: trie to add to
```
111 112
``` * @px: prefix address
```
112 113
``` * @plen: prefix length
```
113
``` * @l: prefix lower bound
```
114
``` * @l: prefix lower bound
```
114 115
``` * @h: prefix upper bound
```
115 116
``` *
```
116 117
``` * Adds prefix (prefix pattern) @px/@plen to trie @t.  @l and @h are lower
```
117 118
``` * and upper bounds on accepted prefix lengths, both inclusive.
```
118 119
``` * 0 <= l, h <= 32 (128 for IPv6).
```
120
``` *
```
121
``` * Returns a pointer to the allocated node. The function can return a pointer to
```
122
``` * an existing node if @px and @plen are the same. If px/plen == 0/0 (or ::/0),
```
123
``` * a pointer to the root node is returned.
```
119 124
``` */
```
120 125

121
```void
```
126
```void *
```
122 127
```trie_add_prefix(struct f_trie *t, ip_addr px, int plen, int l, int h)
```
123 128
```{
```
124 129
```  if (l == 0)
```
......
133 138
```  ip_addr pmask = ipa_mkmask(plen);
```
134 139
```  ip_addr paddr = ipa_and(px, pmask);
```
135 140
```  struct f_trie_node *o = NULL;
```
136
```  struct f_trie_node *n = &t->root;
```
141
```  struct f_trie_node *n = t->root;
```
137 142

138 143
```  while(n)
```
139 144
```    {
```
......
156 161
```	  attach_node(o, b);
```
157 162
```	  attach_node(b, n);
```
158 163
```	  attach_node(b, a);
```
159
```	  return;
```
164
```	  return a;
```
160 165
```	}
```
161 166

162 167
```      if (plen < n->plen)
```
......
166 171
```	  struct f_trie_node *a = new_node(t, plen, paddr, pmask, amask);
```
167 172
```	  attach_node(o, a);
```
168 173
```	  attach_node(a, n);
```
169
```	  return;
```
174
```	  return a;
```
170 175
```	}
```
171
```
```
176

172 177
```      if (plen == n->plen)
```
173 178
```	{
```
174 179
```	  /* We already found added node in trie. Just update accept mask */
```
175 180
```	  n->accept = ipa_or(n->accept, amask);
```
176
```	  return;
```
181
```	  return n;
```
177 182
```	}
```
178 183

179 184
```      /* Update accept mask part M2 and go deeper */
```
......
187 192
```  /* We add new tail node 'a' after node 'o' */
```
188 193
```  struct f_trie_node *a = new_node(t, plen, paddr, pmask, amask);
```
189 194
```  attach_node(o, a);
```
195

196
```  return a;
```
190 197
```}
```
191 198

192 199
```/**
```
193
``` * trie_match
```
200
``` * trie_match_prefix
```
194 201
``` * @t: trie
```
195 202
``` * @px: prefix address
```
196 203
``` * @plen: prefix length
```
......
209 216
```    return t->zero;
```
210 217

211 218
```  int plentest = plen - 1;
```
212
```  struct f_trie_node *n = &t->root;
```
219
```  struct f_trie_node *n = t->root;
```
213 220

214 221
```  while(n)
```
215 222
```    {
```
......
261 268
```int
```
262 269
```trie_same(struct f_trie *t1, struct f_trie *t2)
```
263 270
```{
```
264
```  return (t1->zero == t2->zero) && trie_node_same(&t1->root, &t2->root);
```
271
```  return (t1->zero == t2->zero) && trie_node_same(t1->root, t2->root);
```
265 272
```}
```
266 273

267 274
```static void
```
......
291 298

292 299
```  if (t->zero)
```
293 300
```    buffer_print(buf, "%I/%d", IPA_NONE, 0);
```
294
```  trie_node_format(&t->root, buf);
```
301
```  trie_node_format(t->root, buf);
```
295 302

296 303
```  /* Undo last separator */
```
297 304
```  if (buf->pos[-1] != '[')
```

Also available in: Unified diff