Hi,

maybe I'm way off, but have you considered multi state locks for your
problem? I attached a draft-paper; written by a former collegue and
myself; on Concurrent AVL trees that uses multi-state locking. This
paper is unpublished and unfinished but might be illustrative.
Do note that those email addresses are no longer valid AFAIK, reply to
reach me or the co-author.

just my 2ct.

Peter Zijlstra