in src/clds_sorted_list.c [394:636]
static CLDS_SORTED_LIST_REMOVE_RESULT internal_remove(CLDS_SORTED_LIST_HANDLE clds_sorted_list, CLDS_HAZARD_POINTERS_THREAD_HANDLE clds_hazard_pointers_thread, SORTED_LIST_ITEM_COMPARE_CB item_compare_callback, void* item_compare_target, CLDS_SORTED_LIST_ITEM** item, int64_t* sequence_number)
{
CLDS_SORTED_LIST_REMOVE_RESULT result = CLDS_SORTED_LIST_DELETE_ERROR;
// check that the node is really in the list and obtain
bool restart_needed;
uint64_t iteration_count = 0;
do
{
if (++iteration_count > ITERATION_COUNT_LOG_LIMIT)
{
LogInfo("internal_remove spun for %" PRIu64 " iterations", (uint64_t)ITERATION_COUNT_LOG_LIMIT);
iteration_count = 0;
}
CLDS_HAZARD_POINTER_RECORD_HANDLE previous_hp = NULL;
CLDS_SORTED_LIST_ITEM* previous_item = NULL;
CLDS_SORTED_LIST_ITEM* volatile_atomic* current_item_address = (CLDS_SORTED_LIST_ITEM* volatile_atomic*)&clds_sorted_list->head;
do
{
// get the current_item value
CLDS_SORTED_LIST_ITEM* current_item = interlocked_compare_exchange_pointer((void* volatile_atomic*)current_item_address, NULL, NULL);
// clear any delete lock bit from what we read
current_item = (void*)((uintptr_t)current_item & ~0x1);
if (current_item == 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_SORTED_LIST_01_057: [ If the key is not found, clds_sorted_list_remove_key shall fail and return CLDS_SORTED_LIST_REMOVE_NOT_FOUND. ]*/
result = CLDS_SORTED_LIST_REMOVE_NOT_FOUND;
break;
}
else
{
// acquire hazard pointer
CLDS_HAZARD_POINTER_RECORD_HANDLE current_item_hp = clds_hazard_pointers_acquire(clds_hazard_pointers_thread, (void*)current_item);
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 = CLDS_SORTED_LIST_REMOVE_ERROR;
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*)current_item)
{
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
{
int compare_result = item_compare_callback(clds_sorted_list, (CLDS_SORTED_LIST_ITEM*)current_item, item_compare_target);
if (compare_result == 0)
{
// mark the node as deleted
// get the next pointer as this is the only place where we keep information
volatile_atomic CLDS_SORTED_LIST_ITEM* current_next = interlocked_compare_exchange_pointer((void* volatile_atomic*)¤t_item->next, NULL, NULL);
// clear any delete lock bit from what we read
current_next = (void*)((uintptr_t)current_next & ~0x1);
// mark that the node is deleted
if (interlocked_compare_exchange_pointer((void* volatile_atomic*)¤t_item->next, (void*)((uintptr_t)current_next | 1), (void*)current_next) != (void*)current_next)
{
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
{
int64_t local_seq_no = 0;
/* Codes_SRS_CLDS_SORTED_LIST_01_073: [ If no start sequence number was provided in clds_sorted_list_create and sequence_number is NULL, no sequence number computations shall be done. ]*/
if (clds_sorted_list->sequence_number != NULL)
{
/* Codes_SRS_CLDS_SORTED_LIST_01_074: [ If the sequence_number argument passed to clds_sorted_list_remove_key is NULL, the computed sequence number for the remove shall still be computed but it shall not be provided to the user. ]*/
local_seq_no = interlocked_increment_64(clds_sorted_list->sequence_number);
}
// 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_sorted_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);
if (
(clds_sorted_list->sequence_number != NULL) &&
(clds_sorted_list->skipped_seq_no_cb != NULL)
)
{
clds_sorted_list->skipped_seq_no_cb(clds_sorted_list->skipped_seq_no_cb_context, local_seq_no);
}
restart_needed = true;
break;
}
else
{
/* Codes_SRS_CLDS_SORTED_LIST_01_054: [ On success, the found item shall be returned in the item argument. ]*/
*item = (CLDS_SORTED_LIST_ITEM*)current_item;
clds_sorted_list_node_inc_ref(*item);
if (clds_sorted_list->sequence_number != NULL)
{
if (sequence_number != NULL)
{
// since we deleted the node, simply pick up the current sequence number (has to be greater than the insert)
/* Codes_SRS_CLDS_SORTED_LIST_01_072: [ For each remove key the order of the operation shall be computed based on the start sequence number passed to clds_sorted_list_create. ]*/
*sequence_number = local_seq_no;
}
}
// delete succesfull
clds_hazard_pointers_release(clds_hazard_pointers_thread, current_item_hp);
// reclaim the memory
/* Codes_SRS_CLDS_SORTED_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_SORTED_LIST_01_052: [ On success, clds_sorted_list_remove_key shall return CLDS_SORTED_LIST_REMOVE_OK. ]*/
result = CLDS_SORTED_LIST_REMOVE_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);
if (
(clds_sorted_list->sequence_number != NULL) &&
(clds_sorted_list->skipped_seq_no_cb != NULL)
)
{
clds_sorted_list->skipped_seq_no_cb(clds_sorted_list->skipped_seq_no_cb_context, local_seq_no);
}
restart_needed = true;
break;
}
else
{
/* Codes_SRS_CLDS_SORTED_LIST_01_054: [ On success, the found item shall be returned in the item argument. ]*/
*item = (CLDS_SORTED_LIST_ITEM*)current_item;
clds_sorted_list_node_inc_ref(*item);
if (clds_sorted_list->sequence_number != NULL)
{
if (sequence_number != NULL)
{
// since we deleted the node, simply pick up the current sequence number (has to be greater than the insert)
/* Codes_SRS_CLDS_SORTED_LIST_01_072: [ For each remove key the order of the operation shall be computed based on the start sequence number passed to clds_sorted_list_create. ]*/
*sequence_number = local_seq_no;
}
}
// 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_SORTED_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_SORTED_LIST_01_052: [ On success, clds_sorted_list_remove_key shall return CLDS_SORTED_LIST_REMOVE_OK. ]*/
result = CLDS_SORTED_LIST_REMOVE_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_SORTED_LIST_ITEM* volatile_atomic*)¤t_item->next;
}
}
}
}
} while (1);
} while (restart_needed);
return result;
}