Question: In class I challenged you to post an implementation of fine-grained locking for a binary search tree that supports node insert and delete. Let's see if someone can do it below!

Binary Search Tree

Binary Search Tree with hand-over-hand fine-grained locking

BTree

To add hand-over-hand locking, don't we need to modify the structure to allow a child node to unlock it's parent's lock?

@leis1, one way to handle this is to maintain a pointer to parent while traversing the tree, just as what TA did in the Exam-2 review session for practice problem 6.

@Renegade Yeah. The solution stores the pointer to parent within delete/insert function. Won't it be better if we keep the pointer in the Binary Tree structure itself? For instance, If we add a Node* parent in Node struct.

@leis1, then every node would increase more than 30% storage overhead...

@Renegade that's right. Then what benefits would we have from the 30% additional storage overhead?

@eknight7 thanks for uploading those implementations, it's a super helpful reference. That being said, I think there might be a bug in your implementation -- in your insert method you have:

// ... insert code

unlock(tree->lock);

insert_helper(tree->root, value, NULL);

And then in insert_helper you start by locking on the root. Consider what would happen though if you tried to take a lock on the root and another node had taken that lock on the same node in delete_helper and deleted that node -- you'd get a segfault. I think you need to first lock on the tree lock before you lock on the root node so you prevent that edge case.

Do you agree? If not, could someone explain where my logic is going astray?