From mboxrd@z Thu Jan  1 00:00:00 1970
From: Herbert Poetzl <herbert@13thfloor.at>
Subject: Re: barriers vs. reads
Date: Thu, 24 Jun 2004 10:00:08 +0200
Sender: linux-fsdevel-owner@vger.kernel.org
Message-ID: <20040624080008.GA22997@MAIL.13thfloor.at>
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: <linux-fsdevel-owner@vger.kernel.org>
Received: from MAIL.13thfloor.at ([212.16.62.51]:38603 "EHLO mail.13thfloor.at")
	by vger.kernel.org with ESMTP id S261576AbUFXIAL (ORCPT
	<rfc822;linux-fsdevel@vger.kernel.org>);
	Thu, 24 Jun 2004 04:00:11 -0400
To: Werner Almesberger <wa@almesberger.net>
Content-Disposition: inline
In-Reply-To: <20040624003944.B21586@almesberger.net>
List-Id: linux-fsdevel.vger.kernel.org

On Thu, Jun 24, 2004 at 12:39:44AM -0300, 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).
> 
>   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 :-(

hmm ... there are eight cases how ranges can interact ...

    a     b     		        		a	  b
    |     |			        		|	  |
 1) +-----+       +---------+	       2) +-----+	+---------+
                  |         |	          |	|
		  x         y	          x	y

    a             b		        		a	  b
    |      	  |		        		|	  |
 3) +-------------+---------+	       4) +-------------+---------+
                  |         |	          |		|
		  x         y	          x		y


    a                 b    	        	a		  b
    |                 | 	        	|		  |
 5) +-------------+===+-----+	       6) +-----+========+--------+
                  |         |	          |		 |
		  x         y	          x		 y
	
    a			    b	        	a	 b
    |			    |	        	|	 |
 7) +-----+========+--------+	       8) +-----+========+--------+
          |        |		          |			  |
	  x        y		          x			  y
	

by verifying those eight cases for correctness, you
can conclude, that the sum of N such cases will give
the correct number of overlaps (with a given test
range); verification itself is simple:

case     a<y    b<=x    |{a:a<y}| - |{b:b<= x}|
------+-------+-------+-------------------------
 1)   |  YES  |  YES  |  0
 2)   |  NO   |  NO   |  0
 3)   |  YES  |  YES  |  0
 4)   |  NO   |  NO   |  0
------+-------+-------+-----
 5)   |  YES  |  NO   |  1
 6)   |  YES  |  NO   |  1
 7)   |  YES  |  NO   |  1
 8)   |  YES  |  NO   |  1

HTH,
Herbert

> 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/____________________________________________/
> -
> To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html