netfilter: nft_rbtree: allow adjacent intervals with dynamic updates
authorPablo Neira Ayuso <pablo@netfilter.org>
Tue, 12 Apr 2016 21:50:37 +0000 (23:50 +0200)
committerPablo Neira Ayuso <pablo@netfilter.org>
Mon, 25 Apr 2016 13:32:41 +0000 (15:32 +0200)
commite701001e7cbe88cdc937037f6f398669eef7e7ff
tree655605696d0fe14f9b7e56d758dc10eb1869cc5d
parentef1d20e0f8a80ba2942a59331d472322794d6748
netfilter: nft_rbtree: allow adjacent intervals with dynamic updates

This patch fixes dynamic element updates for adjacent intervals in the
rb-tree representation.

Since elements are sorted in the rb-tree, in case of adjacent nodes with
the same key, the assumption is that an interval end node must be placed
before an interval opening.

In tree lookup operations, the idea is to search for the closer element
that is smaller than the one we're searching for. Given that we'll have
two possible matchings, we have to take the opening interval in case of
adjacent nodes.

Range merges are not trivial with the current representation,
specifically we have to check if node extensions are equal and make sure
we keep the existing internal states around.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
net/netfilter/nft_rbtree.c