iof-bird-daemon / nest / rt-fib.c @ 04632fd7
History | View | Annotate | Download (14.5 KB)
1 |
/*
|
---|---|
2 |
* BIRD -- Forwarding Information Base -- Data Structures
|
3 |
*
|
4 |
* (c) 1998--2000 Martin Mares <mj@ucw.cz>
|
5 |
*
|
6 |
* Can be freely distributed and used under the terms of the GNU GPL.
|
7 |
*/
|
8 |
|
9 |
/**
|
10 |
* DOC: Forwarding Information Base
|
11 |
*
|
12 |
* FIB is a data structure designed for storage of routes indexed by their
|
13 |
* network prefixes. It supports insertion, deletion, searching by prefix,
|
14 |
* `routing' (in CIDR sense, that is searching for a longest prefix matching
|
15 |
* a given IP address) and (which makes the structure very tricky to implement)
|
16 |
* asynchronous reading, that is enumerating the contents of a FIB while other
|
17 |
* modules add, modify or remove entries.
|
18 |
*
|
19 |
* Internally, each FIB is represented as a collection of nodes of type &fib_node
|
20 |
* indexed using a sophisticated hashing mechanism.
|
21 |
* We use two-stage hashing where we calculate a 16-bit primary hash key independent
|
22 |
* on hash table size and then we just divide the primary keys modulo table size
|
23 |
* to get a real hash key used for determining the bucket containing the node.
|
24 |
* The lists of nodes in each bucket are sorted according to the primary hash
|
25 |
* key, hence if we keep the total number of buckets to be a power of two,
|
26 |
* re-hashing of the structure keeps the relative order of the nodes.
|
27 |
*
|
28 |
* To get the asynchronous reading consistent over node deletions, we need to
|
29 |
* keep a list of readers for each node. When a node gets deleted, its readers
|
30 |
* are automatically moved to the next node in the table.
|
31 |
*
|
32 |
* Basic FIB operations are performed by functions defined by this module,
|
33 |
* enumerating of FIB contents is accomplished by using the FIB_WALK() macro
|
34 |
* or FIB_ITERATE_START() if you want to do it asynchronously.
|
35 |
*/
|
36 |
|
37 |
#undef LOCAL_DEBUG
|
38 |
|
39 |
#include "nest/bird.h" |
40 |
#include "nest/route.h" |
41 |
#include "lib/string.h" |
42 |
|
43 |
#define HASH_DEF_ORDER 10 |
44 |
#define HASH_HI_MARK *4 |
45 |
#define HASH_HI_STEP 2 |
46 |
#define HASH_HI_MAX 16 |
47 |
#define HASH_LO_MARK /5 |
48 |
#define HASH_LO_STEP 2 |
49 |
#define HASH_LO_MIN 10 |
50 |
|
51 |
|
52 |
static void |
53 |
fib_ht_alloc(struct fib *f)
|
54 |
{ |
55 |
f->hash_size = 1 << f->hash_order;
|
56 |
f->hash_shift = 32 - f->hash_order;
|
57 |
if (f->hash_order > HASH_HI_MAX - HASH_HI_STEP)
|
58 |
f->entries_max = ~0;
|
59 |
else
|
60 |
f->entries_max = f->hash_size HASH_HI_MARK; |
61 |
if (f->hash_order < HASH_LO_MIN + HASH_LO_STEP)
|
62 |
f->entries_min = 0;
|
63 |
else
|
64 |
f->entries_min = f->hash_size HASH_LO_MARK; |
65 |
DBG("Allocating FIB hash of order %d: %d entries, %d low, %d high\n",
|
66 |
f->hash_order, f->hash_size, f->entries_min, f->entries_max); |
67 |
f->hash_table = mb_alloc(f->fib_pool, f->hash_size * sizeof(struct fib_node *)); |
68 |
} |
69 |
|
70 |
static inline void |
71 |
fib_ht_free(struct fib_node **h)
|
72 |
{ |
73 |
mb_free(h); |
74 |
} |
75 |
|
76 |
|
77 |
static u32
|
78 |
fib_hash(struct fib *f, const net_addr *a); |
79 |
|
80 |
/**
|
81 |
* fib_init - initialize a new FIB
|
82 |
* @f: the FIB to be initialized (the structure itself being allocated by the caller)
|
83 |
* @p: pool to allocate the nodes in
|
84 |
* @node_size: node size to be used (each node consists of a standard header &fib_node
|
85 |
* followed by user data)
|
86 |
* @hash_order: initial hash order (a binary logarithm of hash table size), 0 to use default order
|
87 |
* (recommended)
|
88 |
* @init: pointer a function to be called to initialize a newly created node
|
89 |
*
|
90 |
* This function initializes a newly allocated FIB and prepares it for use.
|
91 |
*/
|
92 |
void
|
93 |
fib_init(struct fib *f, pool *p, uint addr_type, uint node_size, uint node_offset, uint hash_order, fib_init_fn init)
|
94 |
{ |
95 |
uint addr_length = net_addr_length[addr_type]; |
96 |
|
97 |
if (!hash_order)
|
98 |
hash_order = HASH_DEF_ORDER; |
99 |
f->fib_pool = p; |
100 |
f->fib_slab = addr_length ? sl_new(p, node_size + addr_length) : NULL;
|
101 |
f->addr_type = addr_type; |
102 |
f->node_size = node_size; |
103 |
f->node_offset = node_offset; |
104 |
f->hash_order = hash_order; |
105 |
fib_ht_alloc(f); |
106 |
bzero(f->hash_table, f->hash_size * sizeof(struct fib_node *)); |
107 |
f->entries = 0;
|
108 |
f->entries_min = 0;
|
109 |
f->init = init; |
110 |
} |
111 |
|
112 |
static void |
113 |
fib_rehash(struct fib *f, int step) |
114 |
{ |
115 |
unsigned old, new, oldn, newn, ni, nh;
|
116 |
struct fib_node **n, *e, *x, **t, **m, **h;
|
117 |
|
118 |
old = f->hash_order; |
119 |
oldn = f->hash_size; |
120 |
new = old + step; |
121 |
m = h = f->hash_table; |
122 |
DBG("Re-hashing FIB from order %d to %d\n", old, new);
|
123 |
f->hash_order = new; |
124 |
fib_ht_alloc(f); |
125 |
t = n = f->hash_table; |
126 |
newn = f->hash_size; |
127 |
ni = 0;
|
128 |
|
129 |
while (oldn--)
|
130 |
{ |
131 |
x = *h++; |
132 |
while (e = x)
|
133 |
{ |
134 |
x = e->next; |
135 |
nh = fib_hash(f, e->addr); |
136 |
while (nh > ni)
|
137 |
{ |
138 |
*t = NULL;
|
139 |
ni++; |
140 |
t = ++n; |
141 |
} |
142 |
*t = e; |
143 |
t = &e->next; |
144 |
} |
145 |
} |
146 |
while (ni < newn)
|
147 |
{ |
148 |
*t = NULL;
|
149 |
ni++; |
150 |
t = ++n; |
151 |
} |
152 |
fib_ht_free(m); |
153 |
} |
154 |
|
155 |
#define CAST(t) (const net_addr_##t *) |
156 |
#define CAST2(t) (net_addr_##t *) |
157 |
|
158 |
#define FIB_HASH(f,a,t) (net_hash_##t(CAST(t) a) >> f->hash_shift) |
159 |
|
160 |
#define FIB_FIND(f,a,t) \
|
161 |
({ \ |
162 |
struct fib_node *e = f->hash_table[FIB_HASH(f, a, t)]; \
|
163 |
while (e && !net_equal_##t(CAST(t) e->addr, CAST(t) a)) \ |
164 |
e = e->next; \ |
165 |
fib_node_to_user(f, e); \ |
166 |
}) |
167 |
|
168 |
#define FIB_INSERT(f,a,e,t) \
|
169 |
({ \ |
170 |
u32 h = net_hash_##t(CAST(t) a); \ |
171 |
struct fib_node **ee = f->hash_table + (h >> f->hash_shift); \
|
172 |
struct fib_node *g; \
|
173 |
\ |
174 |
while ((g = *ee) && (net_hash_##t(CAST(t) g->addr) < h)) \ |
175 |
ee = &g->next; \ |
176 |
\ |
177 |
net_copy_##t(CAST2(t) e->addr, CAST(t) a); \ |
178 |
e->next = *ee; \ |
179 |
*ee = e; \ |
180 |
}) |
181 |
|
182 |
|
183 |
static u32
|
184 |
fib_hash(struct fib *f, const net_addr *a) |
185 |
{ |
186 |
switch (f->addr_type)
|
187 |
{ |
188 |
case NET_IP4: return FIB_HASH(f, a, ip4); |
189 |
case NET_IP6: return FIB_HASH(f, a, ip6); |
190 |
case NET_VPN4: return FIB_HASH(f, a, vpn4); |
191 |
case NET_VPN6: return FIB_HASH(f, a, vpn6); |
192 |
default: bug("invalid type"); |
193 |
} |
194 |
} |
195 |
|
196 |
/**
|
197 |
* fib_find - search for FIB node by prefix
|
198 |
* @f: FIB to search in
|
199 |
* @n: network address
|
200 |
*
|
201 |
* Search for a FIB node corresponding to the given prefix, return
|
202 |
* a pointer to it or %NULL if no such node exists.
|
203 |
*/
|
204 |
void *
|
205 |
fib_find(struct fib *f, const net_addr *a) |
206 |
{ |
207 |
ASSERT(f->addr_type == a->type); |
208 |
|
209 |
switch (f->addr_type)
|
210 |
{ |
211 |
case NET_IP4: return FIB_FIND(f, a, ip4); |
212 |
case NET_IP6: return FIB_FIND(f, a, ip6); |
213 |
case NET_VPN4: return FIB_FIND(f, a, vpn4); |
214 |
case NET_VPN6: return FIB_FIND(f, a, vpn6); |
215 |
default: bug("invalid type"); |
216 |
} |
217 |
} |
218 |
|
219 |
static void |
220 |
fib_insert(struct fib *f, const net_addr *a, struct fib_node *e) |
221 |
{ |
222 |
switch (f->addr_type)
|
223 |
{ |
224 |
case NET_IP4: FIB_INSERT(f, a, e, ip4); return; |
225 |
case NET_IP6: FIB_INSERT(f, a, e, ip6); return; |
226 |
case NET_VPN4: FIB_INSERT(f, a, e, vpn4); return; |
227 |
case NET_VPN6: FIB_INSERT(f, a, e, vpn6); return; |
228 |
default: bug("invalid type"); |
229 |
} |
230 |
} |
231 |
|
232 |
|
233 |
/**
|
234 |
* fib_get - find or create a FIB node
|
235 |
* @f: FIB to work with
|
236 |
* @n: network address
|
237 |
*
|
238 |
* Search for a FIB node corresponding to the given prefix and
|
239 |
* return a pointer to it. If no such node exists, create it.
|
240 |
*/
|
241 |
void *
|
242 |
fib_get(struct fib *f, const net_addr *a) |
243 |
{ |
244 |
void *b = fib_find(f, a);
|
245 |
if (b)
|
246 |
return b;
|
247 |
|
248 |
if (f->fib_slab)
|
249 |
b = sl_alloc(f->fib_slab); |
250 |
else
|
251 |
b = mb_alloc(f->fib_pool, f->node_size + a->length); |
252 |
|
253 |
struct fib_node *e = fib_user_to_node(f, b);
|
254 |
e->readers = NULL;
|
255 |
e->flags = 0;
|
256 |
e->uid = 0;
|
257 |
fib_insert(f, a, e); |
258 |
|
259 |
memset(b, 0, f->node_offset);
|
260 |
if (f->init)
|
261 |
f->init(b); |
262 |
|
263 |
if (f->entries++ > f->entries_max)
|
264 |
fib_rehash(f, HASH_HI_STEP); |
265 |
|
266 |
return b;
|
267 |
} |
268 |
|
269 |
static inline void * |
270 |
fib_route_ip4(struct fib *f, net_addr_ip4 *n)
|
271 |
{ |
272 |
void *r;
|
273 |
|
274 |
while (!(r = fib_find(f, (net_addr *) n)) && (n->pxlen > 0)) |
275 |
{ |
276 |
n->pxlen--; |
277 |
ip4_clrbit(&n->prefix, n->pxlen); |
278 |
} |
279 |
|
280 |
return r;
|
281 |
} |
282 |
|
283 |
static inline void * |
284 |
fib_route_ip6(struct fib *f, net_addr_ip6 *n)
|
285 |
{ |
286 |
void *r;
|
287 |
|
288 |
while (!(r = fib_find(f, (net_addr *) n)) && (n->pxlen > 0)) |
289 |
{ |
290 |
n->pxlen--; |
291 |
ip6_clrbit(&n->prefix, n->pxlen); |
292 |
} |
293 |
|
294 |
return r;
|
295 |
} |
296 |
|
297 |
/**
|
298 |
* fib_route - CIDR routing lookup
|
299 |
* @f: FIB to search in
|
300 |
* @n: network address
|
301 |
*
|
302 |
* Search for a FIB node with longest prefix matching the given
|
303 |
* network, that is a node which a CIDR router would use for routing
|
304 |
* that network.
|
305 |
*/
|
306 |
void *
|
307 |
fib_route(struct fib *f, const net_addr *n) |
308 |
{ |
309 |
ASSERT(f->addr_type == n->type); |
310 |
|
311 |
net_addr *n0 = alloca(n->length); |
312 |
net_copy(n0, n); |
313 |
|
314 |
switch (n->type)
|
315 |
{ |
316 |
case NET_IP4:
|
317 |
case NET_VPN4:
|
318 |
return fib_route_ip4(f, (net_addr_ip4 *) n0);
|
319 |
|
320 |
case NET_IP6:
|
321 |
case NET_VPN6:
|
322 |
return fib_route_ip6(f, (net_addr_ip6 *) n0);
|
323 |
|
324 |
default:
|
325 |
return NULL; |
326 |
} |
327 |
} |
328 |
|
329 |
|
330 |
static inline void |
331 |
fib_merge_readers(struct fib_iterator *i, struct fib_node *to) |
332 |
{ |
333 |
if (to)
|
334 |
{ |
335 |
struct fib_iterator *j = to->readers;
|
336 |
if (!j)
|
337 |
{ |
338 |
/* Fast path */
|
339 |
to->readers = i; |
340 |
i->prev = (struct fib_iterator *) to;
|
341 |
} |
342 |
else
|
343 |
{ |
344 |
/* Really merging */
|
345 |
while (j->next)
|
346 |
j = j->next; |
347 |
j->next = i; |
348 |
i->prev = j; |
349 |
} |
350 |
while (i && i->node)
|
351 |
{ |
352 |
i->node = NULL;
|
353 |
i = i->next; |
354 |
} |
355 |
} |
356 |
else /* No more nodes */ |
357 |
while (i)
|
358 |
{ |
359 |
i->prev = NULL;
|
360 |
i = i->next; |
361 |
} |
362 |
} |
363 |
|
364 |
/**
|
365 |
* fib_delete - delete a FIB node
|
366 |
* @f: FIB to delete from
|
367 |
* @E: entry to delete
|
368 |
*
|
369 |
* This function removes the given entry from the FIB,
|
370 |
* taking care of all the asynchronous readers by shifting
|
371 |
* them to the next node in the canonical reading order.
|
372 |
*/
|
373 |
void
|
374 |
fib_delete(struct fib *f, void *E) |
375 |
{ |
376 |
struct fib_node *e = fib_user_to_node(f, E);
|
377 |
uint h = fib_hash(f, e->addr); |
378 |
struct fib_node **ee = f->hash_table + h;
|
379 |
struct fib_iterator *it;
|
380 |
|
381 |
while (*ee)
|
382 |
{ |
383 |
if (*ee == e)
|
384 |
{ |
385 |
*ee = e->next; |
386 |
if (it = e->readers)
|
387 |
{ |
388 |
struct fib_node *l = e->next;
|
389 |
while (!l)
|
390 |
{ |
391 |
h++; |
392 |
if (h >= f->hash_size)
|
393 |
break;
|
394 |
else
|
395 |
l = f->hash_table[h]; |
396 |
} |
397 |
fib_merge_readers(it, l); |
398 |
} |
399 |
|
400 |
if (f->fib_slab)
|
401 |
sl_free(f->fib_slab, E); |
402 |
else
|
403 |
mb_free(E); |
404 |
|
405 |
if (f->entries-- < f->entries_min)
|
406 |
fib_rehash(f, -HASH_LO_STEP); |
407 |
return;
|
408 |
} |
409 |
ee = &((*ee)->next); |
410 |
} |
411 |
bug("fib_delete() called for invalid node");
|
412 |
} |
413 |
|
414 |
/**
|
415 |
* fib_free - delete a FIB
|
416 |
* @f: FIB to be deleted
|
417 |
*
|
418 |
* This function deletes a FIB -- it frees all memory associated
|
419 |
* with it and all its entries.
|
420 |
*/
|
421 |
void
|
422 |
fib_free(struct fib *f)
|
423 |
{ |
424 |
fib_ht_free(f->hash_table); |
425 |
rfree(f->fib_slab); |
426 |
} |
427 |
|
428 |
void
|
429 |
fit_init(struct fib_iterator *i, struct fib *f) |
430 |
{ |
431 |
unsigned h;
|
432 |
struct fib_node *n;
|
433 |
|
434 |
i->efef = 0xff;
|
435 |
for(h=0; h<f->hash_size; h++) |
436 |
if (n = f->hash_table[h])
|
437 |
{ |
438 |
i->prev = (struct fib_iterator *) n;
|
439 |
if (i->next = n->readers)
|
440 |
i->next->prev = i; |
441 |
n->readers = i; |
442 |
i->node = n; |
443 |
return;
|
444 |
} |
445 |
/* The fib is empty, nothing to do */
|
446 |
i->prev = i->next = NULL;
|
447 |
i->node = NULL;
|
448 |
} |
449 |
|
450 |
struct fib_node *
|
451 |
fit_get(struct fib *f, struct fib_iterator *i) |
452 |
{ |
453 |
struct fib_node *n;
|
454 |
struct fib_iterator *j, *k;
|
455 |
|
456 |
if (!i->prev)
|
457 |
{ |
458 |
/* We are at the end */
|
459 |
i->hash = ~0 - 1; |
460 |
return NULL; |
461 |
} |
462 |
if (!(n = i->node))
|
463 |
{ |
464 |
/* No node info available, we are a victim of merging. Try harder. */
|
465 |
j = i; |
466 |
while (j->efef == 0xff) |
467 |
j = j->prev; |
468 |
n = (struct fib_node *) j;
|
469 |
} |
470 |
j = i->prev; |
471 |
if (k = i->next)
|
472 |
k->prev = j; |
473 |
j->next = k; |
474 |
i->hash = fib_hash(f, n->addr); |
475 |
return n;
|
476 |
} |
477 |
|
478 |
void
|
479 |
fit_put(struct fib_iterator *i, struct fib_node *n) |
480 |
{ |
481 |
struct fib_iterator *j;
|
482 |
|
483 |
i->node = n; |
484 |
if (j = n->readers)
|
485 |
j->prev = i; |
486 |
i->next = j; |
487 |
n->readers = i; |
488 |
i->prev = (struct fib_iterator *) n;
|
489 |
} |
490 |
|
491 |
void
|
492 |
fit_put_next(struct fib *f, struct fib_iterator *i, struct fib_node *n, uint hpos) |
493 |
{ |
494 |
if (n = n->next)
|
495 |
goto found;
|
496 |
|
497 |
while (++hpos < f->hash_size)
|
498 |
if (n = f->hash_table[hpos])
|
499 |
goto found;
|
500 |
|
501 |
/* We are at the end */
|
502 |
i->prev = i->next = NULL;
|
503 |
i->node = NULL;
|
504 |
return;
|
505 |
|
506 |
found:
|
507 |
fit_put(i, n); |
508 |
} |
509 |
|
510 |
#ifdef DEBUGGING
|
511 |
|
512 |
/**
|
513 |
* fib_check - audit a FIB
|
514 |
* @f: FIB to be checked
|
515 |
*
|
516 |
* This debugging function audits a FIB by checking its internal consistency.
|
517 |
* Use when you suspect somebody of corrupting innocent data structures.
|
518 |
*/
|
519 |
void
|
520 |
fib_check(struct fib *f)
|
521 |
{ |
522 |
#if 0
|
523 |
uint i, ec, lo, nulls;
|
524 |
|
525 |
ec = 0;
|
526 |
for(i=0; i<f->hash_size; i++)
|
527 |
{
|
528 |
struct fib_node *n;
|
529 |
lo = 0;
|
530 |
for(n=f->hash_table[i]; n; n=n->next)
|
531 |
{
|
532 |
struct fib_iterator *j, *j0;
|
533 |
uint h0 = ipa_hash(n->prefix);
|
534 |
if (h0 < lo)
|
535 |
bug("fib_check: discord in hash chains");
|
536 |
lo = h0;
|
537 |
if ((h0 >> f->hash_shift) != i)
|
538 |
bug("fib_check: mishashed %x->%x (order %d)", h0, i, f->hash_order);
|
539 |
j0 = (struct fib_iterator *) n;
|
540 |
nulls = 0;
|
541 |
for(j=n->readers; j; j=j->next)
|
542 |
{
|
543 |
if (j->prev != j0)
|
544 |
bug("fib_check: iterator->prev mismatch");
|
545 |
j0 = j;
|
546 |
if (!j->node)
|
547 |
nulls++;
|
548 |
else if (nulls)
|
549 |
bug("fib_check: iterator nullified");
|
550 |
else if (j->node != n)
|
551 |
bug("fib_check: iterator->node mismatch");
|
552 |
}
|
553 |
ec++;
|
554 |
}
|
555 |
}
|
556 |
if (ec != f->entries)
|
557 |
bug("fib_check: invalid entry count (%d != %d)", ec, f->entries);
|
558 |
#endif
|
559 |
return;
|
560 |
} |
561 |
|
562 |
/*
|
563 |
int
|
564 |
fib_histogram(struct fib *f)
|
565 |
{
|
566 |
log(L_WARN "Histogram dump start %d %d", f->hash_size, f->entries);
|
567 |
|
568 |
int i, j;
|
569 |
struct fib_node *e;
|
570 |
|
571 |
for (i = 0; i < f->hash_size; i++)
|
572 |
{
|
573 |
j = 0;
|
574 |
for (e = f->hash_table[i]; e != NULL; e = e->next)
|
575 |
j++;
|
576 |
if (j > 0)
|
577 |
log(L_WARN "Histogram line %d: %d", i, j);
|
578 |
}
|
579 |
|
580 |
log(L_WARN "Histogram dump end");
|
581 |
}
|
582 |
*/
|
583 |
|
584 |
#endif
|
585 |
|
586 |
#ifdef TEST
|
587 |
|
588 |
#include "lib/resource.h" |
589 |
|
590 |
struct fib f;
|
591 |
|
592 |
void dump(char *m) |
593 |
{ |
594 |
uint i; |
595 |
|
596 |
debug("%s ... order=%d, size=%d, entries=%d\n", m, f.hash_order, f.hash_size, f.hash_size);
|
597 |
for(i=0; i<f.hash_size; i++) |
598 |
{ |
599 |
struct fib_node *n;
|
600 |
struct fib_iterator *j;
|
601 |
for(n=f.hash_table[i]; n; n=n->next)
|
602 |
{ |
603 |
debug("%04x %08x %p %N", i, ipa_hash(n->prefix), n, n->addr);
|
604 |
for(j=n->readers; j; j=j->next)
|
605 |
debug(" %p[%p]", j, j->node);
|
606 |
debug("\n");
|
607 |
} |
608 |
} |
609 |
fib_check(&f); |
610 |
debug("-----\n");
|
611 |
} |
612 |
|
613 |
void init(struct fib_node *n) |
614 |
{ |
615 |
} |
616 |
|
617 |
int main(void) |
618 |
{ |
619 |
struct fib_node *n;
|
620 |
struct fib_iterator i, j;
|
621 |
ip_addr a; |
622 |
int c;
|
623 |
|
624 |
log_init_debug(NULL);
|
625 |
resource_init(); |
626 |
fib_init(&f, &root_pool, sizeof(struct fib_node), 4, init); |
627 |
dump("init");
|
628 |
|
629 |
a = ipa_from_u32(0x01020304); n = fib_get(&f, &a, 32); |
630 |
a = ipa_from_u32(0x02030405); n = fib_get(&f, &a, 32); |
631 |
a = ipa_from_u32(0x03040506); n = fib_get(&f, &a, 32); |
632 |
a = ipa_from_u32(0x00000000); n = fib_get(&f, &a, 32); |
633 |
a = ipa_from_u32(0x00000c01); n = fib_get(&f, &a, 32); |
634 |
a = ipa_from_u32(0xffffffff); n = fib_get(&f, &a, 32); |
635 |
dump("fill");
|
636 |
|
637 |
fit_init(&i, &f); |
638 |
dump("iter init");
|
639 |
|
640 |
fib_rehash(&f, 1);
|
641 |
dump("rehash up");
|
642 |
|
643 |
fib_rehash(&f, -1);
|
644 |
dump("rehash down");
|
645 |
|
646 |
next:
|
647 |
c = 0;
|
648 |
FIB_ITERATE_START(&f, &i, z) |
649 |
{ |
650 |
if (c)
|
651 |
{ |
652 |
FIB_ITERATE_PUT(&i, z); |
653 |
dump("iter");
|
654 |
goto next;
|
655 |
} |
656 |
c = 1;
|
657 |
debug("got %p\n", z);
|
658 |
} |
659 |
FIB_ITERATE_END(z); |
660 |
dump("iter end");
|
661 |
|
662 |
fit_init(&i, &f); |
663 |
fit_init(&j, &f); |
664 |
dump("iter init 2");
|
665 |
|
666 |
n = fit_get(&f, &i); |
667 |
dump("iter step 2");
|
668 |
|
669 |
fit_put(&i, n->next); |
670 |
dump("iter step 3");
|
671 |
|
672 |
a = ipa_from_u32(0xffffffff); n = fib_get(&f, &a, 32); |
673 |
fib_delete(&f, n); |
674 |
dump("iter step 3");
|
675 |
|
676 |
return 0; |
677 |
} |
678 |
|
679 |
#endif
|