From mboxrd@z Thu Jan  1 00:00:00 1970
From: Sasha Levin <levinsasha928@gmail.com>
Subject: Re: RCU red-black tree (was: Re: [PATCH 4/6] kvm tools: Add rwlock
 wrapper)
Date: Mon, 30 May 2011 09:07:11 +0300
Message-ID: <1306735631.14564.34.camel@lappy>
References: <1306426743.3065.34.camel@lappy> <20110526180518.GA3572@elte.hu>
	 <4DDE97CE.4000302@redhat.com>
	 <BANLkTi=bMMr1zHWhwNsD=ah52n3ueoLbUg@mail.gmail.com>
	 <1306436223.3065.36.camel@lappy> <20110526230923.GB15983@Krystal>
	 <1306491547.3217.9.camel@lappy> <20110527131400.GC29744@Krystal>
	 <20110529170104.GA17189@Krystal> <1306691292.14564.12.camel@lappy>
	 <20110530025414.GA25865@Krystal>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
Cc: Pekka Enberg <penberg@kernel.org>, Avi Kivity <avi@redhat.com>,
	Ingo Molnar <mingo@elte.hu>, john@jfloren.net,
	kvm@vger.kernel.org, asias.hejun@gmail.com, gorcunov@gmail.com,
	prasadjoshi124@gmail.com,
	"Paul E. McKenney" <paulmck@linux.vnet.ibm.com>,
	Phil Howard <csbetterthanjava@gmail.com>, rp@svcs.cs.pdx.edu
To: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Return-path: <kvm-owner@vger.kernel.org>
Received: from mail-ww0-f42.google.com ([74.125.82.42]:43555 "EHLO
	mail-ww0-f42.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org
	with ESMTP id S1751889Ab1E3GHl (ORCPT <rfc822;kvm@vger.kernel.org>);
	Mon, 30 May 2011 02:07:41 -0400
Received: by wwk4 with SMTP id 4so1277766wwk.1
        for <kvm@vger.kernel.org>; Sun, 29 May 2011 23:07:40 -0700 (PDT)
In-Reply-To: <20110530025414.GA25865@Krystal>
Sender: kvm-owner@vger.kernel.org
List-ID: <kvm.vger.kernel.org>

On Sun, 2011-05-29 at 22:54 -0400, Mathieu Desnoyers wrote:
> Please note that what I currently have is a normal rbtree, not an
> interval rbtree. Can you elaborate on your use-case so I can try to
> figure out how we could augment it to support the interval rbtree you
> need ?

We don't need anything specific for interval rbtree. The rbtree used in
the kernel provides augmentation functions for insert and erase (see
rb_augment_insert() and rb_augment_erase_begin() +
rb_augment_erase_end()).
What they basically do is call a user-provided callback for each node
from the newly inserted (or deepest after deletion) node up to the root
of the tree. You can see our code at 'tools/kvm/util/rbtree-interval.c',
basically all we need are the 2 augmentation functions I've mentioned
above.

-- 

Sasha.