[comp.theory] Implementation of concurrent balanced trees needed

pugh@panache.cs.umd.edu (Bill Pugh) (12/02/89)

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