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