Thanks Jim, that helped a lot. I'll try out Professor Eggert's suggestion, of switching to mutexes only at the top level merge. Of the following approaches, which would you guys consider better practice?
1) void pointer, cast as either mutex or spinlock in lock function 2) union of mutex and spinlock, chosen in lock function The idea is basically, in the lock function if we see the node is MERGE_LEVEL_ROOT we'd lock the mutex either via cast or union member, and likewise for other merge levels for spinlock.