Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1474071

Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range

From Konstantin Khlebnikov <koct9i@gmail.com>
Newsgroups linux.kernel
Subject Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range
Date 2016-09-01 08:20 +0200
Message-ID <sctvX-510-3@gated-at.bofh.it> (permalink)
References (7 earlier) <sbZex-1ZK-5@gated-at.bofh.it> <sbZod-2i7-1@gated-at.bofh.it> <sbZHE-2pw-15@gated-at.bofh.it> <scf9E-3I8-21@gated-at.bofh.it> <scgS5-4O7-1@gated-at.bofh.it>
Organization linux.* mail to news gateway

Show all headers | View raw

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.

Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

[PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Konstantin Khlebnikov <koct9i@gmail.com> - 2016-08-27 16:20 +0200
  RE: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Matthew Wilcox <mawilcox@microsoft.com> - 2016-08-29 17:40 +0200
    Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Konstantin Khlebnikov <koct9i@gmail.com> - 2016-08-29 18:20 +0200
      Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Konstantin Khlebnikov <koct9i@gmail.com> - 2016-08-29 20:20 +0200
        RE: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Matthew Wilcox <mawilcox@microsoft.com> - 2016-08-29 21:10 +0200
          Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Dan Williams <dan.j.williams@intel.com> - 2016-08-31 00:00 +0200
            Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Ross Zwisler <ross.zwisler@linux.intel.com> - 2016-08-31 00:10 +0200
              Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Dan Williams <dan.j.williams@intel.com> - 2016-08-31 00:30 +0200
                Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Ross Zwisler <ross.zwisler@linux.intel.com> - 2016-08-31 01:00 +0200
                Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Konstantin Khlebnikov <koct9i@gmail.com> - 2016-09-01 08:20 +0200
                RE: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Matthew Wilcox <mawilcox@microsoft.com> - 2016-09-02 20:20 +0200
                Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Konstantin Khlebnikov <koct9i@gmail.com> - 2016-09-03 07:00 +0200
                RE: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Matthew Wilcox <mawilcox@microsoft.com> - 2016-08-31 17:00 +0200
                Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Dan Williams <dan.j.williams@intel.com> - 2016-08-31 18:50 +0200
                Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Konstantin Khlebnikov <koct9i@gmail.com> - 2016-09-01 08:20 +0200
          Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Ross Zwisler <ross.zwisler@linux.intel.com> - 2016-08-31 00:10 +0200
      RE: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Matthew Wilcox <mawilcox@microsoft.com> - 2016-08-29 20:30 +0200
  Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Ross Zwisler <ross.zwisler@linux.intel.com> - 2016-08-31 00:40 +0200

csiph-web