binary_search_tree_fine_grained_lock.cpp

struct Node {
    int value;
    Node *left;
    Node *right;
};

struct Tree {
    Node *root;
};

void insert_helper(Node *root, int value, Node *parent) {
    if (root) {
        lock(root->lock);
        if (parent) unlock(parent->lock);
        if (root->value > value) {
            if (root->left) {
                insert_helper(root->left, value, root);
            } else {
                Node *n = new Node;
                n->value = value;
                n->left = NULL;
                n->right = NULL;
                root->left = n;
                unlock(root->lock);
            }
        } else if (root->value < value){
            if (root->right) {
                insert_helper(root->right, value, root);
            } else {
                Node *n = new Node;
                n->value = value;
                n->left = NULL;
                n->right = NULL;
                root->right = n;
                unlock(root->lock);
            }
        } else {
            // do nothing, value exists
            unlock(root->lock);
            return;
        }
    }
}

void insert(Tree *tree, int value) {

    // Case 1: tree is empty
    lock(tree->lock);
    if (!tree->root) {
        Node *n = new Node;
        n->value = value;
        n->left = NULL;
        n->right = NULL;
        tree->root = n;
        unlock(tree->lock);
        return;
    }

    // Case 2: Tree is non-empty
    unlock(tree->lock);
    insert_helper(tree->root, value, NULL);
}

Node* getMin(Node *root, Node *parent) {

    if (root) {
        lock(root->lock);
        if (parent) unlock(parent->lock);
        if (root->left) {
            return getMin(root->left, root);
        } else {
            unlock(root->lock);
            return root;
        }
    } else {
        // Shouldn't happen
        return NULL;
    }
}

Node *delete_helper(Node *root, int value, Node *parent) {

    if (root) {
        lock(root->lock);
        if (root->value == value) {
            // Case 1: root has no children
            if (!root->left && !root->right) {
                Node *tmp = root;
                root = NULL;
                // Modify parent after this node is fixed
                if (parent) unlock(parent->lock);
                unlock(tmp->lock);
                delete tmp;
                return root;
            }
            // Case 2: root has 1 child
            if (!root->left && root->right) {
                Node *tmp = root;
                root = root->right;
                // Modify parent after this node is fixed
                if (parent) unlock(parent->lock);
                unlock(tmp->lock);
                delete tmp;
                return root;
            }
            if (!root->right && root->left) {
                Node *tmp = root;
                root = root->left;
                // Modify parent after this node is fixed
                if (parent) unlock(parent->lock);
                unlock(tmp->lock);
                delete tmp;
                return root;
            }
            // Case 3: root has 2 children
            // Replace root with highest value smaller than root
            Node *minRight = getMin(root->right);
            root->value = minRight->value;
            // Now delete minRight node; set its parent's left child to NULL or
            // to minRight node's right child
            // We pass NULL as parent as we unlock root after deletion is complete
            root->right = delete_helper(root->right, minRight->value, NULL);
            // Unlock after this sub-tree root is fixed to avoid violating
            // BST invariants when other threads insert simultaneously
            unlock(root->lock);
        }
        else if (root->value > value) {
            // We can releas parent as we modify root and root->left now
            if (parent) unlock(parent->lock);
            // Delete value node from left sub-tree
            root->left = delete_helper(root->left, value, root);
        } else {
            // We can releas parent as we modify root and root->right now
            if (parent) unlock(parent->lock);
            // Delete value node from right sub-tree
            root->right = delete_helper(root->right, value, root);
        }
    } else {
        // Nothing to delete
        return root;
    }
}

void delete(Tree *tree, int value) {

    // Case 1: tree is empty
    lock(tree->lock);
    if (!tree->root){
        unlock(tree->lock);
        return;
    }

    // Case 2: Tree is non-empty
    unlock(tree->lock);
    tree->root = delete_helper(tree->root, value, NULL);
}