in src/clds_sorted_list.c [1236:1742]
CLDS_SORTED_LIST_SET_VALUE_RESULT clds_sorted_list_set_value(CLDS_SORTED_LIST_HANDLE clds_sorted_list, CLDS_HAZARD_POINTERS_THREAD_HANDLE clds_hazard_pointers_thread, void* key, CLDS_SORTED_LIST_ITEM* new_item, CONDITION_CHECK_CB condition_check_func, void* condition_check_context, CLDS_SORTED_LIST_ITEM** old_item, int64_t* sequence_number, bool only_if_exists)
{
CLDS_SORTED_LIST_SET_VALUE_RESULT result;
if (
/* Codes_SRS_CLDS_SORTED_LIST_01_081: [ If clds_sorted_list is NULL, clds_sorted_list_set_value shall fail and return CLDS_SORTED_LIST_SET_VALUE_ERROR. ]*/
(clds_sorted_list == NULL) ||
/* Codes_SRS_CLDS_SORTED_LIST_01_082: [ If clds_hazard_pointers_thread is NULL, clds_sorted_list_set_value shall fail and return CLDS_SORTED_LIST_SET_VALUE_ERROR. ]*/
(clds_hazard_pointers_thread == NULL) ||
/* Codes_SRS_CLDS_SORTED_LIST_01_083: [ If key is NULL, clds_sorted_list_set_value shall fail and return CLDS_SORTED_LIST_SET_VALUE_ERROR. ]*/
(key == NULL) ||
/* Codes_SRS_CLDS_SORTED_LIST_01_084: [ If new_item is NULL, clds_sorted_list_set_value shall fail and return CLDS_SORTED_LIST_SET_VALUE_ERROR. ]*/
(new_item == NULL) ||
/* Codes_SRS_CLDS_SORTED_LIST_01_085: [ If old_item is NULL, clds_sorted_list_set_value shall fail and return CLDS_SORTED_LIST_SET_VALUE_ERROR. ]*/
(old_item == NULL) ||
/* Codes_SRS_CLDS_SORTED_LIST_01_086: [ If the sequence_number argument is non-NULL, but no start sequence number was specified in clds_sorted_list_create, clds_sorted_list_set_value shall fail and return CLDS_SORTED_LIST_SET_VALUE_ERROR. ]*/
((sequence_number != NULL) && (clds_sorted_list->sequence_number == NULL))
)
{
LogError("Invalid arguments: CLDS_SORTED_LIST_HANDLE clds_sorted_list=%p, CLDS_HAZARD_POINTERS_THREAD_HANDLE clds_hazard_pointers_thread=%p, void* key=%p, CLDS_SORTED_LIST_ITEM* new_item=%p, CONDITION_CHECK_CB condition_check_func=%p, void* condition_check_context=%p, CLDS_SORTED_LIST_ITEM** old_item=%p, int64_t* sequence_number=%p",
clds_sorted_list, clds_hazard_pointers_thread, key, new_item, condition_check_func, condition_check_context, old_item, sequence_number);
result = CLDS_SORTED_LIST_SET_VALUE_ERROR;
}
else
{
/*Codes_SRS_CLDS_SORTED_LIST_42_024: [ clds_sorted_list_set_value shall try the following until it acquires a write lock for the list: ]*/
/*Codes_SRS_CLDS_SORTED_LIST_42_025: [ clds_sorted_list_set_value shall increment the count of pending write operations. ]*/
/*Codes_SRS_CLDS_SORTED_LIST_42_026: [ If the counter to lock the list for writes is non-zero then: ]*/
/*Codes_SRS_CLDS_SORTED_LIST_42_027: [ clds_sorted_list_set_value shall decrement the count of pending write operations. ]*/
/*Codes_SRS_CLDS_SORTED_LIST_42_028: [ clds_sorted_list_set_value shall wait for the counter to lock the list for writes to reach 0 and repeat. ]*/
check_lock_and_begin_write_operation(clds_sorted_list);
bool restart_needed;
void* new_item_key = clds_sorted_list->get_item_key_cb(clds_sorted_list->get_item_key_cb_context, new_item);
int64_t insert_seq_no = 0;
/* Codes_SRS_CLDS_SORTED_LIST_01_091: [ 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_090: [ For each set value the order of the operation shall be computed based on the start sequence number passed to clds_sorted_list_create. ]*/
insert_seq_no = interlocked_increment_64(clds_sorted_list->sequence_number);
/* Codes_SRS_CLDS_SORTED_LIST_01_092: [ If the sequence_number argument passed to clds_sorted_list_set_value is NULL, the computed sequence number for the remove shall still be computed but it shall not be provided to the user. ]*/
if (sequence_number != NULL)
{
*sequence_number = insert_seq_no;
}
}
uint64_t iteration_count = 0;
do
{
if (++iteration_count > ITERATION_COUNT_LOG_LIMIT)
{
LogInfo("clds_sorted_list_set_value 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;
volatile_atomic CLDS_SORTED_LIST_ITEM** current_item_address = &clds_sorted_list->head;
result = CLDS_SORTED_LIST_SET_VALUE_ERROR;
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 (only_if_exists)
{
if (previous_item != NULL)
{
clds_hazard_pointers_release(clds_hazard_pointers_thread, previous_hp);
}
/* Codes_SRS_CLDS_SORTED_LIST_01_093: [ If the key entry does not exist and only_if_exists is true, clds_sorted_list_set_value shall return CLDS_SORTED_LIST_SET_VALUE_NOT_FOUND. ]*/
result = CLDS_SORTED_LIST_SET_VALUE_NOT_FOUND;
restart_needed = false;
break;
}
new_item->next = NULL;
// not found, so insert it here
if (previous_item != NULL)
{
// have a previous item
/* Codes_SRS_CLDS_SORTED_LIST_01_087: [ If the key entry does not exist in the list and only_if_exists is false, new_item shall be inserted at the key position. ]*/
if (interlocked_compare_exchange_pointer((void* volatile_atomic*)&previous_item->next, (void*)new_item, NULL) != NULL)
{
// let go of previous hazard pointer
clds_hazard_pointers_release(clds_hazard_pointers_thread, previous_hp);
restart_needed = true;
break;
}
else
{
clds_hazard_pointers_release(clds_hazard_pointers_thread, previous_hp);
restart_needed = false;
/* Codes_SRS_CLDS_SORTED_LIST_01_089: [ The previous value shall be returned in old_item. ]*/
*old_item = NULL;
/* Codes_SRS_CLDS_SORTED_LIST_01_080: [ clds_sorted_list_set_value shall replace in the list the item that matches the criteria given by the compare function passed to clds_sorted_list_create with new_item and on success it shall return CLDS_SORTED_LIST_SET_VALUE_OK. ]*/
result = CLDS_SORTED_LIST_SET_VALUE_OK;
break;
}
}
else
{
// no previous item, replace the head
/* Codes_SRS_CLDS_SORTED_LIST_01_087: [ If the key entry does not exist in the list and only_if_exists is false, new_item shall be inserted at the key position. ]*/
if (interlocked_compare_exchange_pointer((void* volatile_atomic*)&clds_sorted_list->head, new_item, NULL) != NULL)
{
restart_needed = true;
break;
}
else
{
// insert done
restart_needed = false;
/* Codes_SRS_CLDS_SORTED_LIST_01_089: [ The previous value shall be returned in old_item. ]*/
*old_item = NULL;
/* Codes_SRS_CLDS_SORTED_LIST_01_080: [ clds_sorted_list_set_value shall replace in the list the item that matches the criteria given by the compare function passed to clds_sorted_list_create with new_item and on success it shall return CLDS_SORTED_LIST_SET_VALUE_OK. ]*/
result = CLDS_SORTED_LIST_SET_VALUE_OK;
break;
}
}
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_SET_VALUE_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
{
// we are in a stable state, compare the current item key to our key
void* current_item_key = clds_sorted_list->get_item_key_cb(clds_sorted_list->get_item_key_cb_context, (struct CLDS_SORTED_LIST_ITEM_TAG*)current_item);
int compare_result = clds_sorted_list->key_compare_cb(clds_sorted_list->key_compare_cb_context, new_item_key, current_item_key);
if (compare_result == 0)
{
if (condition_check_func != NULL)
{
/* Codes_SRS_CLDS_SORTED_LIST_04_001: [ If condition_check_func is not NULL it shall be called passing condition_check_context and the new and old keys. ]*/
CLDS_CONDITION_CHECK_RESULT condition_check_result = condition_check_func(condition_check_context, new_item_key, current_item_key);
switch (condition_check_result)
{
case CLDS_CONDITION_CHECK_RESULT_INVALID:
case CLDS_CONDITION_CHECK_ERROR:
{
LogError("Condition check failed - %" PRI_MU_ENUM "", MU_ENUM_VALUE(CLDS_CONDITION_CHECK_RESULT, condition_check_result));
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);
/* Codes_SRS_CLDS_SORTED_LIST_04_002: [ If condition_check_func returns CLDS_CONDITION_CHECK_ERROR then clds_sorted_list_set_value shall fail and return CLDS_SORTED_LIST_SET_VALUE_ERROR. ]*/
result = CLDS_SORTED_LIST_SET_VALUE_ERROR;
break;
}
case CLDS_CONDITION_CHECK_NOT_MET:
{
LogError("Condition check not met - %" PRI_MU_ENUM "", MU_ENUM_VALUE(CLDS_CONDITION_CHECK_RESULT, condition_check_result));
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);
/* Codes_SRS_CLDS_SORTED_LIST_04_003: [ If condition_check_func returns CLDS_CONDITION_CHECK_NOT_MET then clds_sorted_list_set_value shall fail and return CLDS_SORTED_LIST_SET_VALUE_CONDITION_NOT_MET. ]*/
result = CLDS_SORTED_LIST_SET_VALUE_CONDITION_NOT_MET;
break;
}
case CLDS_CONDITION_CHECK_OK:
{
/* Nothing to do. Life continues like normal. */
break;
}
}
/* Codes_SRS_CLDS_SORTED_LIST_04_004: [ If condition_check_func returns CLDS_CONDITION_CHECK_OK then clds_sorted_list_set_value continues. ]*/
if (condition_check_result != CLDS_CONDITION_CHECK_OK)
{
restart_needed = false;
break;
}
}
/* Codes_SRS_CLDS_SORTED_LIST_01_088: [ If the key entry exists in the list, its value shall be replaced with new_item. ]*/
CLDS_SORTED_LIST_ITEM* volatile_atomic 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);
if (interlocked_compare_exchange_pointer((void* volatile_atomic*)¤t_item->next, (void*)((uintptr_t)current_next | 0x1), (void*)current_next) != (void*)current_next)
{
if (previous_item != NULL)
{
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;
}
if (clds_sorted_list->sequence_number != NULL)
{
if (interlocked_add_64(clds_sorted_list->sequence_number, 0) != insert_seq_no)
{
if (clds_sorted_list->skipped_seq_no_cb != NULL)
{
clds_sorted_list->skipped_seq_no_cb(clds_sorted_list->skipped_seq_no_cb_context, insert_seq_no);
}
/* Codes_SRS_CLDS_SORTED_LIST_01_090: [ For each set value the order of the operation shall be computed based on the start sequence number passed to clds_sorted_list_create. ]*/
insert_seq_no = interlocked_increment_64(clds_sorted_list->sequence_number);
/* Codes_SRS_CLDS_SORTED_LIST_01_092: [ If the sequence_number argument passed to clds_sorted_list_set_value is NULL, the computed sequence number for the remove shall still be computed but it shall not be provided to the user. ]*/
if (sequence_number != NULL)
{
*sequence_number = insert_seq_no;
}
}
}
// same item!, locked, noone changes it now, so we can set the seq no.
if (current_item == new_item)
{
if (interlocked_compare_exchange_pointer((void* volatile_atomic*)¤t_item->next, (void*)current_next, (void*)((uintptr_t)current_next | 0x1)) != (void*)((uintptr_t)current_next | 0x1))
{
LogError("This should not happen");
if (previous_item != NULL)
{
clds_hazard_pointers_release(clds_hazard_pointers_thread, previous_hp);
}
clds_hazard_pointers_release(clds_hazard_pointers_thread, current_item_hp);
restart_needed = false;
result = CLDS_SORTED_LIST_SET_VALUE_ERROR;
break;
}
else
{
if (previous_item != NULL)
{
clds_hazard_pointers_release(clds_hazard_pointers_thread, previous_hp);
}
clds_hazard_pointers_release(clds_hazard_pointers_thread, current_item_hp);
/* Codes_SRS_CLDS_SORTED_LIST_01_089: [ The previous value shall be returned in old_item. ]*/
*old_item = (CLDS_SORTED_LIST_ITEM*)current_item;
// no need to inc_ref or similar as the item is going to be held in the list
restart_needed = false;
/* Codes_SRS_CLDS_SORTED_LIST_01_080: [ clds_sorted_list_set_value shall replace in the list the item that matches the criteria given by the compare function passed to clds_sorted_list_create with new_item and on success it shall return CLDS_SORTED_LIST_SET_VALUE_OK. ]*/
result = CLDS_SORTED_LIST_SET_VALUE_OK;
break;
}
}
// set the new_item->next to point to the next item in the list
new_item->next = current_next;
// now its locked, no insert/delete should be happening on current->next
if (previous_item != NULL)
{
// have a previous item
if (interlocked_compare_exchange_pointer((void* volatile_atomic*)&previous_item->next, (void*)new_item, (void*)current_item) != current_item)
{
if (interlocked_compare_exchange_pointer((void* volatile_atomic*)¤t_item->next, (void*)current_next, (void*)((uintptr_t)current_next | 0x1)) != (void*)((uintptr_t)current_next | 0x1))
{
LogError("This should not happen");
clds_hazard_pointers_release(clds_hazard_pointers_thread, previous_hp);
clds_hazard_pointers_release(clds_hazard_pointers_thread, current_item_hp);
restart_needed = false;
result = CLDS_SORTED_LIST_SET_VALUE_ERROR;
break;
}
else
{
// 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_needed = true;
break;
}
}
else
{
clds_hazard_pointers_release(clds_hazard_pointers_thread, previous_hp);
clds_hazard_pointers_release(clds_hazard_pointers_thread, current_item_hp);
restart_needed = false;
/* Codes_SRS_CLDS_SORTED_LIST_01_089: [ The previous value shall be returned in old_item. ]*/
*old_item = (CLDS_SORTED_LIST_ITEM*)current_item;
(void)clds_sorted_list_node_inc_ref(*old_item);
clds_hazard_pointers_reclaim(clds_hazard_pointers_thread, (void*)current_item, reclaim_list_node);
/* Codes_SRS_CLDS_SORTED_LIST_01_080: [ clds_sorted_list_set_value shall replace in the list the item that matches the criteria given by the compare function passed to clds_sorted_list_create with new_item and on success it shall return CLDS_SORTED_LIST_SET_VALUE_OK. ]*/
result = CLDS_SORTED_LIST_SET_VALUE_OK;
break;
}
}
else
{
if (interlocked_compare_exchange_pointer((void* volatile_atomic*)&clds_sorted_list->head, (void*)new_item, (void*)current_item) != current_item)
{
if (interlocked_compare_exchange_pointer((void* volatile_atomic*)¤t_item->next, (void*)current_next, (void*)((uintptr_t)current_next | 0x1)) != (void*)((uintptr_t)current_next | 0x1))
{
LogError("This should not happen");
clds_hazard_pointers_release(clds_hazard_pointers_thread, current_item_hp);
restart_needed = false;
result = CLDS_SORTED_LIST_SET_VALUE_ERROR;
break;
}
else
{
// let go of previous hazard pointer
clds_hazard_pointers_release(clds_hazard_pointers_thread, current_item_hp);
restart_needed = true;
break;
}
}
else
{
clds_hazard_pointers_release(clds_hazard_pointers_thread, current_item_hp);
restart_needed = false;
/* Codes_SRS_CLDS_SORTED_LIST_01_089: [ The previous value shall be returned in old_item. ]*/
*old_item = (CLDS_SORTED_LIST_ITEM*)current_item;
(void)clds_sorted_list_node_inc_ref(*old_item);
clds_hazard_pointers_reclaim(clds_hazard_pointers_thread, (void*)current_item, reclaim_list_node);
/* Codes_SRS_CLDS_SORTED_LIST_01_080: [ clds_sorted_list_set_value shall replace in the list the item that matches the criteria given by the compare function passed to clds_sorted_list_create with new_item and on success it shall return CLDS_SORTED_LIST_SET_VALUE_OK. ]*/
result = CLDS_SORTED_LIST_SET_VALUE_OK;
break;
}
}
break;
}
else if (compare_result < 0)
{
if (only_if_exists)
{
if (previous_item != NULL)
{
clds_hazard_pointers_release(clds_hazard_pointers_thread, previous_hp);
}
clds_hazard_pointers_release(clds_hazard_pointers_thread, current_item_hp);
/* Codes_SRS_CLDS_SORTED_LIST_01_093: [ If the key entry does not exist and only_if_exists is true, clds_sorted_list_set_value shall return CLDS_SORTED_LIST_SET_VALUE_NOT_FOUND. ]*/
result = CLDS_SORTED_LIST_SET_VALUE_NOT_FOUND;
restart_needed = false;
break;
}
else
{
// need to insert between these 2 nodes
new_item->next = current_item;
if (previous_item != NULL)
{
// have a previous item
/* Codes_SRS_CLDS_SORTED_LIST_01_087: [ If the key entry does not exist in the list and only_if_exists is false, new_item shall be inserted at the key position. ]*/
if (interlocked_compare_exchange_pointer((void* volatile_atomic*)&previous_item->next, (void*)new_item, (void*)current_item) != current_item)
{
// 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_needed = true;
break;
}
else
{
clds_hazard_pointers_release(clds_hazard_pointers_thread, previous_hp);
clds_hazard_pointers_release(clds_hazard_pointers_thread, current_item_hp);
restart_needed = false;
/* Codes_SRS_CLDS_SORTED_LIST_01_089: [ The previous value shall be returned in old_item. ]*/
*old_item = NULL;
/* Codes_SRS_CLDS_SORTED_LIST_01_080: [ clds_sorted_list_set_value shall replace in the list the item that matches the criteria given by the compare function passed to clds_sorted_list_create with new_item and on success it shall return CLDS_SORTED_LIST_SET_VALUE_OK. ]*/
result = CLDS_SORTED_LIST_SET_VALUE_OK;
break;
}
}
else
{
/* Codes_SRS_CLDS_SORTED_LIST_01_087: [ If the key entry does not exist in the list and only_if_exists is false, new_item shall be inserted at the key position. ]*/
if (interlocked_compare_exchange_pointer((void* volatile_atomic*)&clds_sorted_list->head, (void*)new_item, (void*)current_item) != current_item)
{
// let go of previous hazard pointer
clds_hazard_pointers_release(clds_hazard_pointers_thread, current_item_hp);
restart_needed = true;
break;
}
else
{
clds_hazard_pointers_release(clds_hazard_pointers_thread, current_item_hp);
restart_needed = false;
/* Codes_SRS_CLDS_SORTED_LIST_01_089: [ The previous value shall be returned in old_item. ]*/
*old_item = NULL;
/* Codes_SRS_CLDS_SORTED_LIST_01_080: [ clds_sorted_list_set_value shall replace in the list the item that matches the criteria given by the compare function passed to clds_sorted_list_create with new_item and on success it shall return CLDS_SORTED_LIST_SET_VALUE_OK. ]*/
result = CLDS_SORTED_LIST_SET_VALUE_OK;
break;
}
}
}
}
else // item is less than the current, so move on
{
// 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 = (volatile_atomic CLDS_SORTED_LIST_ITEM**)¤t_item->next;
}
}
}
}
} while (1);
} while (restart_needed);
/*Codes_SRS_CLDS_SORTED_LIST_42_029: [ clds_sorted_list_set_value shall decrement the count of pending write operations. ]*/
end_write_operation(clds_sorted_list);
if (result != CLDS_SORTED_LIST_SET_VALUE_OK)
{
// the insert as part of set value did not really materialize
if (clds_sorted_list->skipped_seq_no_cb != NULL)
{
clds_sorted_list->skipped_seq_no_cb(clds_sorted_list->skipped_seq_no_cb_context, insert_seq_no);
}
}
}
return result;
}