HomeFreeBSD

pctrie: add parent pointer to nodes

Description

pctrie: add parent pointer to nodes

Add a parent pointer field to the pctrie_node struct, and maintain
it as part of inserting and removing pctrie items.

Much code is written to maintain one, or an array, of trailing
pointers; that maintenance can be dropped with parent pointers
available. Code affected includes remove, reclaim, lookup_le, and
lookup_ge. In places, functions written once for iterator-free
searching and again for iterator-maintaining searching can be replaced
with a single function that serves both purposes.

Fix an overflow error in lower-bound testing for lookup_le.

Reviewed by: markj
Tested by: pho
Differential Revision: https://reviews.freebsd.org/D48588

Details

Provenance
dougmAuthored on Mon, Feb 10, 8:17 PM
Reviewer
markj
Differential Revision
D48588: pctrie: add parent pointer to nodes
Parents
rG4a7f4f289c1a: sockets: make pr_aio_queue the default method
Branches
Unknown
Tags
Unknown