Messages in this thread | | | Date | Tue, 20 Mar 2012 11:00:49 +0100 | Subject | Re: [PATCH 1/2] [RFC] Range tree implementation | From | Dmitry Adamushko <> |
| |
Hi John,
On 16 March 2012 23:51, John Stultz <john.stultz@linaro.org> wrote: > After Andrew suggested something like his mumbletree idea > to better store a list of ranges, I worked on a few different > approaches, and this is what I've finally managed to get working. > > I suspect range-tree isn't a totally accurate name, but I > couldn't quite make out the difference between range trees > and interval trees, so I just picked one to call it. Do > let me know if you have a better name. > > The idea of storing ranges in a tree is nice, but has a number > of complications. When adding a range, its possible that a > large range will consume and merge a number of smaller ranges.
Have you considered using 'prio_tree' (include/linux/prio_tree.h)? If we aim at addressing a wide range of possible use-cases (different patterns of adding/removing volatile ranges), then, at first glance, prio_tree looks like a better approach.
e.g. for the "consume and merge a number of smaller ranges" scenario above, prio_tree gives O(log n) [ O(log n + m) ] behavior iso O(m log n) in your case.
--Dmitry
| |