OSDN Git Service

bpf: Optimize lpm trie delete
authorCraig Gallek <kraig@google.com>
Thu, 21 Sep 2017 22:43:29 +0000 (18:43 -0400)
committerDavid S. Miller <davem@davemloft.net>
Mon, 25 Sep 2017 21:37:54 +0000 (14:37 -0700)
commitb5d7388f9db78f19e6af7b56a469ca8d1860329d
treea7c9ad97a4ff20d6d2e09cfd2a77b3fb2993a6af
parentd835b63cc4ee67e59eed9d1957f729c0a30b7331
bpf: Optimize lpm trie delete

Before the delete operator was added, this datastructure maintained
an invariant that intermediate nodes were only present when necessary
to build the tree.  This patch updates the delete operation to reinstate
that invariant by removing unnecessary intermediate nodes after a node is
removed and thus keeping the tree structure at a minimal size.

Suggested-by: Daniel Mack <daniel@zonque.org>
Signed-off-by: Craig Gallek <kraig@google.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
kernel/bpf/lpm_trie.c