int lock_free_set_insert()

in src/lock_free_set.c [83:168]

• 57 lines of code
• 8 McCabe index (conditional complexity)

int lock_free_set_insert(LOCK_FREE_SET_HANDLE lock_free_set, LOCK_FREE_SET_ITEM* item)
{
    int result;

    if (
        /* Codes_SRS_LOCK_FREE_SET_01_011: [ If lock_free_set or item is NULL, lock_free_set_insert shall fail and return a non-zero value. ]*/
        (lock_free_set == NULL) ||
        (item == NULL)
        )
    {
        LogError("Invalid arguments: LOCK_FREE_SET_HANDLE lock_free_set=%p, LOCK_FREE_SET_ITEM* item=%p",
            lock_free_set, item);
        result = MU_FAILURE;
    }
    else
    {
        bool restart_needed;
        result = MU_FAILURE;

        /* Codes_SRS_LOCK_FREE_SET_01_013: [ lock_free_set_insert and lock_free_set_remove shall be safe to be called from multiple threads. ]*/

        /* Codes_SRS_LOCK_FREE_SET_01_009: [ lock_free_set_insert shall insert the item item in the set. ]*/
        do
        {
            LOCK_FREE_SET_ITEM* current_head = interlocked_compare_exchange_pointer(&lock_free_set->head, NULL, NULL);

            (void)interlocked_exchange_pointer(&item->previous, NULL);
            (void)interlocked_exchange_pointer(&item->next, current_head);

            // insert our new item as the head
            LOCK_FREE_SET_ITEM* expected_head = current_head;
            if (interlocked_compare_exchange_pointer(&lock_free_set->head, item, expected_head) != expected_head)
            {
                // unable to lock the head, it has already changed, restart
                restart_needed = true;
            }
            else
            {
                // replaced it, yay
                if (current_head == NULL)
                {
                    // the list was empty, we have nothing else to do
                    /* Codes_SRS_LOCK_FREE_SET_01_010: [ On success it shall return 0. ]*/
                    restart_needed = false;
                    result = 0;
                }
                else
                {
                    // Now we have
                    //         item              current_head          next_item
                    // [NULL, current_head]    [NULL, next item]    [ current_head, ...]

                    // we have to exchange the previous of "current_head" with our new item that just became the head
                    // Possible concurrent operations:
                    // - insert - any insert that attempts to change the head would fail and restart as it would notice the value of the head changed
                    // - a remove that tried to remove cuurent_head - a remove that tried to delete "current_head" would see that the head has changed in the meanwhile and it would need to restart
                    // - remove that removed from the middle - a remove that tried to delete "current_head" from the middle would see NULL, which is not OK for removing from the middle, thus it would restart

                    // Conclusion: current_head can not be deleted until we complete if we got far enough to change the head of the list

                    bool wait_for_next_node;
                    restart_needed = true;

                    do
                    {
                        LOCK_FREE_SET_ITEM* expected_current_head_previous = NULL;
                        if (interlocked_compare_exchange_pointer(&current_head->previous, item, expected_current_head_previous) != expected_current_head_previous)
                        {
                            // if the current_head->previous is not NULL, it can only mean that a remove is in progress, we'll wait
                            wait_for_next_node = true;
                        }
                        else
                        {
                            /* Codes_SRS_LOCK_FREE_SET_01_010: [ On success it shall return 0. ]*/
                            wait_for_next_node = false;
                            restart_needed = false;
                            result = 0;
                        }
                    } while (wait_for_next_node);
                }
            }
        } while (restart_needed);
    }

    return result;
}