From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S263111AbTDFVoi (for ); Sun, 6 Apr 2003 17:44:38 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S263114AbTDFVoi (for ); Sun, 6 Apr 2003 17:44:38 -0400 Received: from mail.jlokier.co.uk ([81.29.64.88]:45953 "EHLO mail.jlokier.co.uk") by vger.kernel.org with ESMTP id S263111AbTDFVog (for ); Sun, 6 Apr 2003 17:44:36 -0400 Date: Sun, 6 Apr 2003 22:55:30 +0100 From: Jamie Lokier To: Rik van Riel Cc: "Martin J. Bligh" , Alan Cox , Andrew Morton , andrea@suse.de, mingo@elte.hu, hugh@veritas.com, dmccr@us.ibm.com, Linux Kernel Mailing List , linux-mm@kvack.org, Bill Irwin Subject: Re: subobj-rmap Message-ID: <20030406215530.GC24710@mail.jlokier.co.uk> References: <1070000.1049664851@[10.10.2.4]> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.4.1i Sender: linux-kernel-owner@vger.kernel.org X-Mailing-List: linux-kernel@vger.kernel.org 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 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? -- Jamie