From mboxrd@z Thu Jan 1 00:00:00 1970 From: Werner Almesberger Subject: Re: barriers vs. reads Date: Thu, 24 Jun 2004 00:39:44 -0300 Sender: linux-fsdevel-owner@vger.kernel.org Message-ID: <20040624003944.B21586@almesberger.net> References: <20040623214845.A21586@almesberger.net> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Return-path: Received: from almesberger.net ([63.105.73.238]:23314 "EHLO host.almesberger.net") by vger.kernel.org with ESMTP id S263802AbUFXDjw (ORCPT ); Wed, 23 Jun 2004 23:39:52 -0400 Received: from almesberger.net (vpnwa-home [10.200.0.2]) by host.almesberger.net (8.11.6/8.9.3) with ESMTP id i5O3dq412178 for ; Wed, 23 Jun 2004 20:39:53 -0700 Received: (from werner@localhost) by almesberger.net (8.11.6/8.11.6) id i5O3djG22621 for linux-fsdevel@vger.kernel.org; Thu, 24 Jun 2004 00:39:45 -0300 To: linux-fsdevel@vger.kernel.org Content-Disposition: inline In-Reply-To: <20040623214845.A21586@almesberger.net>; from wa@almesberger.net on Wed, Jun 23, 2004 at 09:48:45PM -0300 List-Id: linux-fsdevel.vger.kernel.org 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). num_overlaps = |{a : a < y}| - |{b : b <= x}| "{a : a < y}" is "the set of all a where a < y". "|...|" is the number of elements in a set. We could obtain such indices by counting the number of nodes in each branch of the tree. That's O(1) for all regular tree operations, and O(log n) for the sum. The index is the size of all the trees under left branches we haven't taken, plus the number of nodes we've left through the right branch. If there are multiple equal entries, we must find the first one. One problem: I did this mostly by instinct. It seems to work perfectly, but I can't quite explain why :-( I put a dirty little program to simulate this on http://abiss.sourceforge.net/t.tar.gz - Werner -- _________________________________________________________________________ / Werner Almesberger, Buenos Aires, Argentina wa@almesberger.net / /_http://www.almesberger.net/____________________________________________/