On Wed, Aug 31, 2016 at 7:36 PM, Dan Williams <[email protected]> wrote: > On Wed, Aug 31, 2016 at 7:57 AM, Matthew Wilcox <[email protected]> > wrote: >> I'm not at all against the idea of having a tree which supports ranges, >> except that we already have one; the interval tree. Did you investigate >> using the interval tree for your use case? > > I am continuing to investigate, but that is orthogonal to whether > Konstantin's changes are an improvement for the radix implementation. > Hmm, would we have ended up with two data-structures if a range-based > radix was available?
Interval tree is a augmented rb-tree. AFAIK it doesn't support RCU lookup without special dances with sequential counters - some branches disappears from RCU readers during rebalance. > > The benefits I see is that it simplifies insertion as it no longer > needs to explicitly manage the order of the entries, and, iiuc, let's > the user skip the sibling-to-head conversion when it is not needed > which simplifies lookups.
