]> git.baikalelectronics.ru Git - kernel.git/commit
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)
commitdedcbaf67b9b54c12e54ec41490dbd8ecf7f5816
treea7c9ad97a4ff20d6d2e09cfd2a77b3fb2993a6af
parent04c434842b55443d39c0025700740b4e8fc9e231
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