Re: [RFC] Generalized prio_tree, revisited

[Werner Almesberger]

Rajesh Venkatasubramanian wrote:
> The "raw" prio_tree can only handle unique intervals, i.e., we cannot
> insert two intervals with the same indices.

Yes, I admit that I found it convenient (laziness is a survival
trait :-) to preserve this property of the underlying code.

In fact, I'm not so sure if we should really offer alternatives at
that level, since it seems that adding a conflict resolution layer
on top of prio_tree (or including it in the user) is about as much
work as including one inside, and the former could be tailored to
the specific needs of the user, e.g.

 - new entry is rejected
 - new entry replaces old entry
 - entries are somehow merged (reference count, add partial
   content, etc.)
 - entries neutralize each other
 - both entries are kept, in a list (like VMA and the ABISS
   elevator do)
 - both entries are kept, ordered by some other key
 - action depends on context

and so on. So it seems to me that we're just at the level of
abstraction that gives us the most narrow interface and that
doesn't hide any information we need to implement the other
cases. And it's just the "engine" that would be used in all
cases anyway.

Besides, handling of non-unique entries shouldn't such a big
deal that the user whould be seriously inconvenienced by having
to do it. E.g. in the case of red-black trees, we also expect
the user to do a lot for us.

> Maybe in your case you don't have to worry about storing multiple
> identical intervals.

I just build a list that's usually read in FIFO order. In
my case, any kind of overlap needs special handling, so
non-unique entries aren't much extra work.

If I was really ambitious, I could try to combine non-unique
requests if they all are writes (but then, having a lot of
these is probably an indication of problems elsewhere).

Thanks,
- Werner

-- 
  _________________________________________________________________________
 / Werner Almesberger, Buenos Aires, Argentina     werner@xxxxxxxxxxxxxxx /
/_http://www.almesberger.net/____________________________________________/
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/