Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!zaphod.mps.ohio-state.edu!gem.mps.ohio-state.edu!mips!excelan!unix!hplabs!hp-sdd!ncr-sd!ncrcae!hubcap!pugh
From: pugh@panache.cs.umd.edu (Bill Pugh)
Newsgroups: comp.parallel
Subject: Implementation of concurrent balanced trees needed
Message-ID: <7263@hubcap.clemson.edu>
Date: 30 Nov 89 19:06:40 GMT
Sender: fpst@hubcap.clemson.edu
Lines: 15
Approved: parallel@hubcap.clemson.edu

For some research I'm doing, I need to benchmark a fast implementation
of a concurrent (shared-memory)  balanced tree algorithm. Unfortunately, 
all of the concurrent balanced tree implementations I'm aware of are very 
complicated, and I don't really want to have to code them up myself. Does
anyone have a copy of the source code for a concurrent balanced tree
algorithm, hopefully in C? I want an algorithm that allows lots of concurrency
so I exclude any algorithm in which each updating process obtains a write lock 
on the root of the tree, since this limits you to only O(log n) busy writers.


	Thanks in advance,

		William Pugh
		Assistant Professor
		Univ. of Maryland, College Park