I didn't have time to implement delete, but I think this solution works for just insert operations.

typedef struct Tree
{
    Node* root;
} Tree;

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

void insert(Tree* tree, int value)
{
    lock(tree->root->lock);
    insert_r(tree->root);
}

void insert_r(Node* node, int value)
{
    if (value == node->value) return;
    if (value < node->value)
    {
        lock(node->left->lock);
        if (node->left == NULL)
        {
            Node* n = malloc(sizeof(Node));
            n->left = NULL;
            n->right = NULL;
            n->value = value;
            node->left = n;
            unlock(node->left->lock);
            unlock(node->lock);
        }
        else
        {
            unlock(node->lock);
            insert(node->left, value);
        }
    }
    else if (value > node->value)
    {
        lock(node->right->lock);
        if (node->right == NULL)
        {
            Node* n = malloc(sizeof(Node));
            n->left = NULL;
            n->right = NULL;
            n->value = value;
            node-right = n;
            unlock(node->right->lock);
            unlock(node->lock);
        }
        else
        {
            unlock(node->lock);
            insert(node->right, value);
        }
    }
}

I think the recursive structure of the code makes locks easier to handle. In particular, there are less pointers to deal with. Of course this code could be completely wrong, so let me know!

This comment was marked helpful 0 times.

don't you need unlock for if (value ==node->value) case ?

This comment was marked helpful 0 times.

@sbly The check for if (node->left == NULL) should happen before lock(node->left->lock). Otherwise the code might segfault. I also think you meant to call insert_r instead of insert, otherwise things don't typecheck. Here's a possible delete implementation, using the structs as defined by sbly.

void delete(Tree *tree, int value) {
    // assume tree->root->value != value, don't want to handle that case
    lock(tree->root->lock);
    delete_r(tree->root, value);
}

void delete_r(Node *parent, int value) {
    /* lock on parent is held on entry, so we're guaranteed that
     * there won't be any modifications to parent->left and
     * parent->right
     */

    Node *next;
    next = value < parent->value ? parent->left : parent->right;
    if (next == NULL) {
        unlock(parent->lock);
        return;
    }

    if (next->value == value) {
        Node *new_child = delete_self(next);
        if (next == parent->left) {
            parent->left = new_child;
        } else {
            parent->right = new_child;
        }
        unlock(parent->lock);
        return;
    }

    lock(next->lock);
    unlock(parent->lock);
    delete_r(next, value);
}

I imagine that delete_self deletes the given node, returning NULL or returning the new head of that subtree. This is done by returning the right-most child in the left subtree or the left-most child in the right subtree. This traversal also needs to happen by locking each node, similar to how the linked list traversal was implemented.

This comment was marked helpful 0 times.

@sbly I believe the implementation is right, although if it is a C program, I think one problem happens when calling:

else
{
    unlock(node->lock);
    insert(node->left, value);
}

function insert passes a pointer to Node, whereas according to definition

void insert(Tree* tree, int value)
{
    lock(tree->root->lock);
    insert_r(tree->root);
}

It seems requires a pointer to Tree.

This comment was marked helpful 0 times.

I think the deletion case is not as simple...Because we need to reshuffle the tree, we need to always hold on to the parent's lock as well.

This comment was marked helpful 0 times.

The implementation provided by @sbly is incorrect. If my tree is the node containing value 1 and I call insert(T, 1) then I will lock the root node but never release it.

This comment was marked helpful 0 times.