in src/clds_singly_linked_list.c [62:247]
static CLDS_SINGLY_LINKED_LIST_DELETE_RESULT internal_delete(CLDS_SINGLY_LINKED_LIST_HANDLE clds_singly_linked_list, CLDS_HAZARD_POINTERS_THREAD_HANDLE clds_hazard_pointers_thread, SINGLY_LINKED_LIST_ITEM_COMPARE_CB item_compare_callback, void* item_compare_callback_context)
{
CLDS_SINGLY_LINKED_LIST_DELETE_RESULT result = CLDS_SINGLY_LINKED_LIST_DELETE_ERROR;
bool restart_needed;
do
{
// check that the node is really in the list and obtain
CLDS_HAZARD_POINTER_RECORD_HANDLE previous_hp = NULL;
CLDS_SINGLY_LINKED_LIST_ITEM* previous_item = NULL;
CLDS_SINGLY_LINKED_LIST_ITEM* volatile_atomic* current_item_address = (CLDS_SINGLY_LINKED_LIST_ITEM* volatile_atomic*)&clds_singly_linked_list->head;
do
{
// get the current_item value
CLDS_SINGLY_LINKED_LIST_ITEM* current_item = interlocked_compare_exchange_pointer((void* volatile_atomic*)current_item_address, NULL, NULL);
if ((void*)((uintptr_t)current_item & (~0x1)) == NULL)
{
if (previous_hp != NULL)
{
// let go of previous hazard pointer
clds_hazard_pointers_release(clds_hazard_pointers_thread, previous_hp);
}
restart_needed = false;
/* Codes_SRS_CLDS_SINGLY_LINKED_LIST_01_018: [ If the item does not exist in the list, clds_singly_linked_list_delete shall fail and return CLDS_SINGLY_LINKED_LIST_DELETE_NOT_FOUND. ]*/
/* Codes_SRS_CLDS_SINGLY_LINKED_LIST_01_024: [ If no item matches the criteria, clds_singly_linked_list_delete_if shall fail and return CLDS_SINGLY_LINKED_LIST_DELETE_NOT_FOUND. ]*/
result = CLDS_SINGLY_LINKED_LIST_DELETE_NOT_FOUND;
break;
}
else
{
// acquire hazard pointer
CLDS_HAZARD_POINTER_RECORD_HANDLE current_item_hp = clds_hazard_pointers_acquire(clds_hazard_pointers_thread, (void*)((uintptr_t)current_item & ~0x1));
if (current_item_hp == NULL)
{
if (previous_hp != NULL)
{
// let go of previous hazard pointer
clds_hazard_pointers_release(clds_hazard_pointers_thread, previous_hp);
}
LogError("Cannot acquire hazard pointer");
restart_needed = false;
result = MU_FAILURE;
break;
}
else
{
// now make sure the item has not changed
if (interlocked_compare_exchange_pointer((void* volatile_atomic*)current_item_address, (void*)current_item, (void*)current_item) != (void*)((uintptr_t)current_item & ~0x1))
{
if (previous_hp != NULL)
{
// let go of previous hazard pointer
clds_hazard_pointers_release(clds_hazard_pointers_thread, previous_hp);
}
// item changed, it is likely that the node is no longer reachable, so we should not use its memory, restart
clds_hazard_pointers_release(clds_hazard_pointers_thread, current_item_hp);
restart_needed = true;
break;
}
else
{
// clear any leftover delete lock bit, since we made sure it is not set
current_item = (void*)((uintptr_t)current_item & ~0x1);
if (item_compare_callback(item_compare_callback_context, (CLDS_SINGLY_LINKED_LIST_ITEM*)current_item))
{
// mark the node as deleted
// get the next pointer as this is the only place where we keep information
CLDS_SINGLY_LINKED_LIST_ITEM* current_next = interlocked_compare_exchange_pointer((void* volatile_atomic*)¤t_item->next, NULL, NULL);
// mark that the node is deleted
if (interlocked_compare_exchange_pointer((void* volatile_atomic*)¤t_item->next, (void*)((uintptr_t)current_next | 1), (void*)((uintptr_t)current_next & (~0x1))) != (void*)((uintptr_t)current_next & (~0x1)))
{
if (previous_hp != NULL)
{
// let go of previous hazard pointer
clds_hazard_pointers_release(clds_hazard_pointers_thread, previous_hp);
}
clds_hazard_pointers_release(clds_hazard_pointers_thread, current_item_hp);
// restart
restart_needed = true;
break;
}
else
{
// clear any leftover delete lock bit, since we made sure of its state and
// we don't want to accidentaly reference memory with the delete lock flag in the pointer
current_next = (void*)((uintptr_t)current_next & ~0x1);
// the current node is marked for deletion, now try to change the previous link to the next value
// If in the meanwhile someone would be deleting node A they would have to first set the
// deleted flag on it, in which case we'd see the CAS fail
if (previous_item == NULL)
{
// we are removing the head
if (interlocked_compare_exchange_pointer((void* volatile_atomic*)&clds_singly_linked_list->head, (void*)current_next, (void*)current_item) != (void*)current_item)
{
// head changed, restart
(void)interlocked_compare_exchange_pointer((void* volatile_atomic*)¤t_item->next, (void*)current_next, (void*)((uintptr_t)current_next | 1));
clds_hazard_pointers_release(clds_hazard_pointers_thread, current_item_hp);
restart_needed = true;
break;
}
else
{
// delete succesfull
clds_hazard_pointers_release(clds_hazard_pointers_thread, current_item_hp);
// reclaim the memory
/* Codes_SRS_CLDS_SINGLY_LINKED_LIST_01_042: [ When an item is deleted it shall be indicated to the hazard pointers instance as reclaimed by calling clds_hazard_pointers_reclaim. ]*/
clds_hazard_pointers_reclaim(clds_hazard_pointers_thread, (void*)current_item, reclaim_list_node);
restart_needed = false;
/* Codes_SRS_CLDS_SINGLY_LINKED_LIST_01_026: [ On success, clds_singly_linked_list_delete shall return CLDS_SINGLY_LINKED_LIST_DELETE_OK. ]*/
/* Codes_SRS_CLDS_SINGLY_LINKED_LIST_01_025: [ On success, clds_singly_linked_list_delete_if shall return CLDS_SINGLY_LINKED_LIST_DELETE_OK. ]*/
result = CLDS_SINGLY_LINKED_LIST_DELETE_OK;
break;
}
}
else
{
if (interlocked_compare_exchange_pointer((void* volatile_atomic*)&previous_item->next, (void*)current_next, (void*)current_item) != (void*)current_item)
{
// someone is deleting our left node, restart, but first unlock our own delete mark
(void)interlocked_compare_exchange_pointer((void* volatile_atomic*)¤t_item->next, (void*)current_next, (void*)((uintptr_t)current_next | 1));
clds_hazard_pointers_release(clds_hazard_pointers_thread, previous_hp);
clds_hazard_pointers_release(clds_hazard_pointers_thread, current_item_hp);
restart_needed = true;
break;
}
else
{
// delete succesfull, no-one deleted the left node in the meanwhile
clds_hazard_pointers_release(clds_hazard_pointers_thread, previous_hp);
clds_hazard_pointers_release(clds_hazard_pointers_thread, current_item_hp);
// reclaim the memory
/* Codes_SRS_CLDS_SINGLY_LINKED_LIST_01_042: [ When an item is deleted it shall be indicated to the hazard pointers instance as reclaimed by calling clds_hazard_pointers_reclaim. ]*/
clds_hazard_pointers_reclaim(clds_hazard_pointers_thread, (void*)current_item, reclaim_list_node);
/* Codes_SRS_CLDS_SINGLY_LINKED_LIST_01_026: [ On success, clds_singly_linked_list_delete shall return CLDS_SINGLY_LINKED_LIST_DELETE_OK. ]*/
/* Codes_SRS_CLDS_SINGLY_LINKED_LIST_01_025: [ On success, clds_singly_linked_list_delete_if shall return CLDS_SINGLY_LINKED_LIST_DELETE_OK. ]*/
result = CLDS_SINGLY_LINKED_LIST_DELETE_OK;
restart_needed = false;
break;
}
}
}
}
else
{
// we have a stable pointer to the current item, now simply set the previous to be this
if (previous_hp != NULL)
{
// let go of previous hazard pointer
clds_hazard_pointers_release(clds_hazard_pointers_thread, previous_hp);
}
previous_hp = current_item_hp;
previous_item = current_item;
current_item_address = (CLDS_SINGLY_LINKED_LIST_ITEM* volatile_atomic*)¤t_item->next;
}
}
}
}
} while (1);
} while (restart_needed);
return result;
}