From 9195bef7fb0ba0a91d5ffa566bcf8e007e3c7172 Mon Sep 17 00:00:00 2001 From: Stephen Hemminger Date: Tue, 22 Jan 2008 21:56:34 -0800 Subject: [IPV4] fib_trie: avoid extra search on delete Get rid of extra search that made route deletion O(n). Signed-off-by: Stephen Hemminger Signed-off-by: David S. Miller --- net/ipv4/fib_trie.c | 50 ++++++++++++-------------------------------------- 1 file changed, 12 insertions(+), 38 deletions(-) (limited to 'net/ipv4/fib_trie.c') diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c index 2ea94ebe19f8..441c4eafb9e0 100644 --- a/net/ipv4/fib_trie.c +++ b/net/ipv4/fib_trie.c @@ -1545,49 +1545,23 @@ found: return ret; } -/* only called from updater side */ -static int trie_leaf_remove(struct trie *t, t_key key) +/* + * Remove the leaf and return parent. + */ +static void trie_leaf_remove(struct trie *t, struct leaf *l) { - t_key cindex; - struct tnode *tp = NULL; - struct node *n = t->trie; - struct leaf *l; - - pr_debug("entering trie_leaf_remove(%p)\n", n); + struct tnode *tp = node_parent((struct node *) l); - /* Note that in the case skipped bits, those bits are *not* checked! - * When we finish this, we will have NULL or a T_LEAF, and the - * T_LEAF may or may not match our key. - */ - - while (n != NULL && IS_TNODE(n)) { - struct tnode *tn = (struct tnode *) n; - check_tnode(tn); - n = tnode_get_child(tn, tkey_extract_bits(key, - tn->pos, tn->bits)); - - BUG_ON(n && node_parent(n) != tn); - } - l = (struct leaf *) n; - - if (!n || !tkey_equals(l->key, key)) - return 0; - - /* - * Key found. - * Remove the leaf and rebalance the tree - */ - tp = node_parent(n); - tnode_free((struct tnode *) n); + pr_debug("entering trie_leaf_remove(%p)\n", l); if (tp) { - cindex = tkey_extract_bits(key, tp->pos, tp->bits); + t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits); put_child(t, (struct tnode *)tp, cindex, NULL); rcu_assign_pointer(t->trie, trie_rebalance(t, tp)); } else rcu_assign_pointer(t->trie, NULL); - return 1; + tnode_free((struct tnode *) l); } /* @@ -1665,7 +1639,7 @@ static int fn_trie_delete(struct fib_table *tb, struct fib_config *cfg) } if (hlist_empty(&l->list)) - trie_leaf_remove(t, key); + trie_leaf_remove(t, l); if (fa->fa_state & FA_S_ACCESSED) rt_cache_flush(-1); @@ -1778,19 +1752,19 @@ static struct leaf *trie_nextleaf(struct leaf *l) static int fn_trie_flush(struct fib_table *tb) { struct trie *t = (struct trie *) tb->tb_data; - struct leaf *ll = NULL, *l = NULL; + struct leaf *l, *ll = NULL; int found = 0; for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) { found += trie_flush_leaf(t, l); if (ll && hlist_empty(&ll->list)) - trie_leaf_remove(t, ll->key); + trie_leaf_remove(t, ll); ll = l; } if (ll && hlist_empty(&ll->list)) - trie_leaf_remove(t, ll->key); + trie_leaf_remove(t, ll); pr_debug("trie_flush found=%d\n", found); return found; -- cgit v1.2.3-59-g8ed1b