Revision 51762a45

View differences:

filter/config.Y
592 592
 ;
593 593

  
594 594
fprefix_set:
595
   fprefix { $$ = f_new_trie(cfg_mem); trie_add_fprefix($$, &($1.val.px)); }
595
   fprefix { $$ = f_new_trie(cfg_mem, sizeof(struct f_trie_node)); trie_add_fprefix($$, &($1.val.px)); }
596 596
 | fprefix_set ',' fprefix { $$ = $1; trie_add_fprefix($$, &($3.val.px)); }
597 597
 ;
598 598

  
filter/filter.h
80 80
int same_tree(struct f_tree *t1, struct f_tree *t2);
81 81
void tree_format(struct f_tree *t, buffer *buf);
82 82

  
83
struct f_trie *f_new_trie(linpool *lp);
84
void trie_add_prefix(struct f_trie *t, ip_addr px, int plen, int l, int h);
83
struct f_trie *f_new_trie(linpool *lp, uint node_size);
84
void *trie_add_prefix(struct f_trie *t, ip_addr px, int plen, int l, int h);
85 85
int trie_match_prefix(struct f_trie *t, ip_addr px, int plen);
86 86
int trie_same(struct f_trie *t1, struct f_trie *t2);
87 87
void trie_format(struct f_trie *t, buffer *buf);
......
204 204
{
205 205
  linpool *lp;
206 206
  int zero;
207
  struct f_trie_node root;
207
  uint node_size;
208
  struct f_trie_node root[0];		/* Root trie node follows */
208 209
};
209 210

  
210 211
#define NEW_F_VAL struct f_val * val; val = cfg_alloc(sizeof(struct f_val));
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] != '[')
nest/rt-table.c
1988 1988
  hc->slab = sl_new(rt_table_pool, sizeof(struct hostentry));
1989 1989

  
1990 1990
  hc->lp = lp_new(rt_table_pool, 1008);
1991
  hc->trie = f_new_trie(hc->lp);
1991
  hc->trie = f_new_trie(hc->lp, sizeof(struct f_trie_node));
1992 1992

  
1993 1993
  tab->hostcache = hc;
1994 1994
}
......
2136 2136

  
2137 2137
  /* Reset the trie */
2138 2138
  lp_flush(hc->lp);
2139
  hc->trie = f_new_trie(hc->lp);
2139
  hc->trie = f_new_trie(hc->lp, sizeof(struct f_trie_node));
2140 2140

  
2141 2141
  WALK_LIST_DELSAFE(n, x, hc->hostentries)
2142 2142
    {

Also available in: Unified diff