[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20120531223559.GB19050@quack.suse.cz>
Date: Fri, 1 Jun 2012 00:35:59 +0200
From: Jan Kara <jack@...e.cz>
To: John Stultz <john.stultz@...aro.org>
Cc: Jan Kara <jack@...e.cz>, LKML <linux-kernel@...r.kernel.org>,
Andrew Morton <akpm@...ux-foundation.org>,
Android Kernel Team <kernel-team@...roid.com>,
Robert Love <rlove@...gle.com>, Mel Gorman <mel@....ul.ie>,
Hugh Dickins <hughd@...gle.com>,
Dave Hansen <dave@...ux.vnet.ibm.com>,
Rik van Riel <riel@...hat.com>,
Dmitry Adamushko <dmitry.adamushko@...il.com>,
Dave Chinner <david@...morbit.com>, Neil Brown <neilb@...e.de>,
Andrea Righi <andrea@...terlinux.com>,
"Aneesh Kumar K.V" <aneesh.kumar@...ux.vnet.ibm.com>,
Taras Glek <tgek@...illa.com>, Mike Hommey <mh@...ndium.org>
Subject: Re: [PATCH 2/4] [RFC] Range tree implementation
On Thu 31-05-12 14:04:23, John Stultz wrote:
> On 05/31/2012 01:48 PM, Jan Kara wrote:
> >On Fri 25-05-12 12:17:34, John Stultz wrote:
> >>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.
> > Well, interval tree is a data structure for tracking a set of
> >possibly overlapping intervals. Range tree is a data structure tracking
> >points allowing for fast queries on a set of points contained in a given
> >range (gets useful and interesting when dimension> 1). Your data structure
> >is neither so it would be good to have a different name. OTOH there are so
> >many data structures that it's hard to find a reasonable unused name ;)
>
> Although I'm not sure your interval tree description doesn't match
> what I'm trying to provide. Could you clarify why that doesn't
> match?
Wikipedia has a good description of Interval trees:
http://en.wikipedia.org/wiki/Interval_tree
For example they are tertiary trees.
> >>+ * @root: range_tree root
> >>+ * @start: range start
> >>+ * @end: range end
> >>+ *
> >>+ */
> >>+struct range_tree_node *range_tree_next_in_range(struct range_tree_node *node,
> >>+ u64 start, u64 end)
> >>+{
> >>+ struct rb_node *next;
> >>+ struct range_tree_node *candidate;
> >>+ if (!node)
> >>+ return NULL;
> >>+ next = rb_next(&node->rb);
> >>+ if (!next)
> >>+ return NULL;
> >>+
> >>+ candidate = container_of(next, struct range_tree_node, rb);
> >>+
> >>+ if ((candidate->start> end) || (candidate->end< start))
> >>+ return NULL;
> >>+
> >>+ return candidate;
> >>+}
> >>+
> >>+/**
> >>+ * range_tree_add - Add a node to a range tree
> >>+ * @root: range tree to be added to
> >>+ * @node: range_tree_node to be added
> >>+ *
> >>+ * Adds a node to the range tree.
> > I think you should document here that the added range must not intersect
> >with any other range in the tree.
>
> So for my usage in the volatile range code, I don't want
> intersecting or overlapping ranges added, but I didn't feel it was
> necessary to add this restriction to my rangetree code as well,
> since someone might want to store overlapping ranges.
Ok, but then you should define where an interval that is intersecting
other intervals ends up sorted...
Honza
--
Jan Kara <jack@...e.cz>
SUSE Labs, CR
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists