lkml.org 
[lkml]   [2016]   [Sep]   [1]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
Date
SubjectRe: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range
On Wed, Aug 31, 2016 at 7:36 PM, Dan Williams <dan.j.williams@intel.com> wrote:
> On Wed, Aug 31, 2016 at 7:57 AM, Matthew Wilcox <mawilcox@microsoft.com> 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.

\
 
 \ /
  Last update: 2016-09-17 09:58    [W:0.148 / U:0.244 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site