Messages in this thread | | | Subject | Re: [PATCH 1/3] Range tree implementation | From | Peter Zijlstra <> | Date | Tue, 24 Apr 2012 21:14:20 +0200 |
| |
On Tue, 2012-04-24 at 10:49 -0700, John Stultz wrote: > This makes it > very difficult to provide generic list_head like behavior, as > the parent structures would need to be duplicated and removed, > and that has lots of memory ownership issues.
You can in fact modify the rb-tree to have O(1) iteration by using the empty leaf pointers to keep pointers to next/prev nodes.
Its a bit of a bother since you'd need to wrap ->rb_left and ->rb_right in functions.. but now that we have coccinelle that shouldn't actually be too hard.
| |