Messages in this thread | | | Date | Sun, 6 Apr 2003 15:39:28 -0700 | From | William Lee Irwin III <> | Subject | Re: subobj-rmap |
| |
Rik van Riel wrote: >> I don't see how the data structure you describe >> would allow us to efficiently select the subset >> of VMAs for which: >> 1) the start address is smaller than the address we want >> and >> 2) the end address is larger than the address we want
On Sun, Apr 06, 2003 at 10:55:30PM +0100, Jamie Lokier wrote: > Think about the data structures some text editors use to describe > special regions of the text. A common operation is to search for all > the special regions covering a particular cursor position. > Several data structures are available. I'm not aware of any that have > perfect behaviour in all corner cases. > It might be worth noting that these data structures are good at > determining the set of regions covering position X+1 having recently > calculated the set for position X. Perhaps that has relevance for > speeding up page scanning?
Multidimensional search trees are routine and decades old last I checked; why do none of them suffice and why would they be good at sequential queries?
-- wli - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |