doubly_linked_list_fine_grained_lock.cpp

struct Node {
    int value;
    Node *prev;
    Node *next;
    Lock *lock;
};

struct DList {
    Node *head;
    Lock *lock;
};

void insert(DList *list, int value) {

    Node *n = new Node;
    n->value = value;

    // First, need a lock on the head
    lock(list->lock);
    // Case 1: list is empty
    if (!list->head) {
        n->next = NULL;
        n->prev = NULL;
        list->head = n;
        unlock(list->lock);
        return;
    }

    // Case 2: insert before head
    lock(list->head->lock);
    if (list->head->value > value) {
        n->next = list->head;
        list->head->prev = n;
        list->head = n;
        unlock(n->next->lock);
        unlock(list->lock);
        return;
    }

    // Case 2: list is non-empty
    Node *prev = list->head;
    Node *cur = list->head->next;

    // Already locked the head above
    unlock(list->lock);
    if (cur) lock(cur->lock);

    while (cur) {
        if (cur->value > value)
            break;

        Node * old_prev = prev;
        prev = cur;
        cur = cur->next;
        unlock(old_prev->lock);
        if (cur) lock(cur->lock);
    }

    if (cur) {
        // Sub-case 1: insert before head
        if (cur == list->head) {
            n->next = list->head;
            list->head = n;
            return;
        }

        // Sub-case 2: insert after head
        n->next = cur;
        n->prev = cur->prev;
        cur->prev = n;
        n->prev->next = n;
        unlock(prev->lock);
        unlock(cur->lock);
    } else {
         // Case 3: List insertion is at end of list
         // so cur is empty
         n->next = NULL;
         n->prev = prev;
         prev->next = n;
         unlock(prev->lock);
    }

}

void delete(DList *list, int value) {

    lock(list->lock);
    // Case 1: List is empty
    if (!list->head) {
        return;
    }

    // Case 2: single element list
    lock(list->head->lock);
    if (list->head->value == value && !list->head->next) {
        Node *tmp = list->head;
        list->head = tmp->next;
        unlock(list->lock);
        unlock(tmp->lock);
        delete tmp;
        return;
    }

    Node *prev = list->head;
    Node *cur = list->head->next;

    // Already locked head above
    unlock(list->lock);
    if (cur) lock(cur->lock);

    while (cur) {
        if (cur->value == value)
            break;
        Node *old_prev = prev;
        prev = cur;
        cur = cur->next;
        unlock(old_prev->lock);
        if (cur) lock(cur->lock);
    }

    // Case 3: delete after head
    prev->next = cur->next;
    if (cur && cur->next) {
        cur->next->prev = prev;
    }
    unlock(prev->lock);
    if (cur) {
        unlock(cur->lock);
        delete cur;
    }
}