From mboxrd@z Thu Jan 1 00:00:00 1970 From: Jamie Lokier Subject: Re: barriers vs. reads Date: Thu, 24 Jun 2004 14:36:39 +0100 Sender: linux-fsdevel-owner@vger.kernel.org Message-ID: <20040624133639.GA8440@mail.shareable.org> References: <20040623214845.A21586@almesberger.net> <20040624003944.B21586@almesberger.net> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Cc: linux-fsdevel@vger.kernel.org Return-path: Received: from mail.shareable.org ([81.29.64.88]:18858 "EHLO mail.shareable.org") by vger.kernel.org with ESMTP id S264677AbUFXNgm (ORCPT ); Thu, 24 Jun 2004 09:36:42 -0400 To: Werner Almesberger Content-Disposition: inline In-Reply-To: <20040624003944.B21586@almesberger.net> List-Id: linux-fsdevel.vger.kernel.org Werner Almesberger wrote: > I wrote: > > BTW, regarding overlapping requests, I wonder if there's a data > > structure that gives O(log requests) or such lookups for ranges. > > Seem that I've found one that is maybe 2-4 times as expensive as a > single tree. It works as follows: if we have a set of ranges (a,b) > and want to see if any of them overlap with a range (x,y), we > compare the indices of the matches (or almost-matches). Is the prio_tree data structure, the one being used by recent VM work, which keeps track of ranges, any use? -- Jamie