in src/clds_hash_table.c [811:1021]
CLDS_HASH_TABLE_SET_VALUE_RESULT clds_hash_table_set_value(CLDS_HASH_TABLE_HANDLE clds_hash_table, CLDS_HAZARD_POINTERS_THREAD_HANDLE clds_hazard_pointers_thread, void* key, CLDS_HASH_TABLE_ITEM* new_item, CONDITION_CHECK_CB condition_check_func, void* condition_check_context, CLDS_HASH_TABLE_ITEM** old_item, int64_t* sequence_number)
{
CLDS_HASH_TABLE_SET_VALUE_RESULT result;
if (
/* Codes_SRS_CLDS_HASH_TABLE_01_079: [ If clds_hash_table is NULL, clds_hash_table_set_value shall fail and return CLDS_HASH_TABLE_SET_VALUE_ERROR. ]*/
(clds_hash_table == NULL) ||
/* Codes_SRS_CLDS_HASH_TABLE_01_080: [ If clds_hazard_pointers_thread is NULL, clds_hash_table_set_value shall fail and return CLDS_HASH_TABLE_SET_VALUE_ERROR. ]*/
(clds_hazard_pointers_thread == NULL) ||
/* Codes_SRS_CLDS_HASH_TABLE_01_081: [ If key is NULL, clds_hash_table_set_value shall fail and return CLDS_HASH_TABLE_SET_VALUE_ERROR. ]*/
(key == NULL) ||
/* Codes_SRS_CLDS_HASH_TABLE_01_082: [ If new_item is NULL, clds_hash_table_set_value shall fail and return CLDS_HASH_TABLE_SET_VALUE_ERROR. ]*/
(new_item == NULL) ||
/* Codes_SRS_CLDS_HASH_TABLE_01_083: [ If old_item is NULL, clds_hash_table_set_value shall fail and return CLDS_HASH_TABLE_SET_VALUE_ERROR. ]*/
(old_item == NULL) ||
/* Codes_SRS_CLDS_HASH_TABLE_01_084: [ If the sequence_number argument is non-NULL, but no start sequence number was specified in clds_hash_table_create, clds_hash_table_set_value shall fail and return CLDS_HASH_TABLE_SET_VALUE_ERROR. ]*/
((sequence_number != NULL) && (clds_hash_table->sequence_number == NULL))
)
{
LogError("Invalid arguments: CLDS_HASH_TABLE_HANDLE clds_hash_table=%p, CLDS_HAZARD_POINTERS_THREAD_HANDLE clds_hazard_pointers_thread=%p, void* key=%p, CLDS_HASH_TABLE_ITEM* new_item=%p, CONDITION_CHECK_CB condition_check_func=%p, void* condition_check_context=%p, CLDS_HASH_TABLE_ITEM** old_item=%p, int64_t* sequence_number=%p",
clds_hash_table, key, clds_hazard_pointers_thread, new_item, condition_check_func, condition_check_context, old_item, sequence_number);
result = CLDS_HASH_TABLE_SET_VALUE_ERROR;
}
else
{
uint64_t bucket_index;
CLDS_SORTED_LIST_HANDLE bucket_list;
/* Codes_SRS_CLDS_HASH_TABLE_42_055: [ clds_hash_table_set_value shall try the following until it acquires a write lock for the table: ]*/
/* Codes_SRS_CLDS_HASH_TABLE_42_056: [ clds_hash_table_set_value shall increment the count of pending write operations. ]*/
/* Codes_SRS_CLDS_HASH_TABLE_42_057: [ If the counter to lock the table for writes is non-zero then: ]*/
/* Codes_SRS_CLDS_HASH_TABLE_42_058: [ clds_hash_table_set_value shall decrement the count of pending write operations. ]*/
/* Codes_SRS_CLDS_HASH_TABLE_42_059: [ clds_hash_table_set_value shall wait for the counter to lock the table for writes to reach 0 and repeat. ]*/
check_lock_and_begin_write_operation(clds_hash_table);
// compute the hash
uint64_t hash = clds_hash_table->compute_hash(key);
// find or allocate a new bucket array
BUCKET_ARRAY* first_bucket_array = get_first_bucket_array(clds_hash_table);
// increment pending inserts count
(void)interlocked_increment(&first_bucket_array->pending_insert_count);
BUCKET_ARRAY* next_bucket_array = interlocked_compare_exchange_pointer((void* volatile_atomic*)&first_bucket_array->next_bucket, NULL, NULL);
if (next_bucket_array != NULL)
{
// wait for all outstanding inserts in the lower levels to complete
do
{
if (interlocked_add(&next_bucket_array->pending_insert_count, 0) == 0)
{
break;
}
} while (1);
}
/* Codes_SRS_CLDS_HASH_TABLE_01_085: [ clds_hash_table_set_value shall go through all non top level bucket arrays and: ]*/
bool set_value_in_top_level = true;
result = CLDS_HASH_TABLE_SET_VALUE_ERROR;
BUCKET_ARRAY* find_bucket_array = next_bucket_array;
while (find_bucket_array != NULL)
{
next_bucket_array = interlocked_compare_exchange_pointer((void* volatile_atomic*)&find_bucket_array->next_bucket, NULL, NULL);
bucket_index = hash % interlocked_add(&find_bucket_array->bucket_count, 0);
bucket_list = interlocked_compare_exchange_pointer((void* volatile_atomic*)&find_bucket_array->hash_table[bucket_index], NULL, NULL);
if (bucket_list != NULL)
{
/* Codes_SRS_CLDS_HASH_TABLE_01_108: [ If there is a sorted list in the bucket identified by the hash of the key, clds_hash_table_set_value shall find the key in the list. ]*/
CLDS_SORTED_LIST_ITEM* sorted_list_item = clds_sorted_list_find_key(bucket_list, clds_hazard_pointers_thread, key);
if (sorted_list_item != NULL)
{
clds_sorted_list_node_release(sorted_list_item);
HASH_TABLE_ITEM* hash_table_item = CLDS_SORTED_LIST_GET_VALUE(HASH_TABLE_ITEM, new_item);
hash_table_item->key = key;
/* Codes_SRS_CLDS_HASH_TABLE_01_110: [ If the key is found, clds_hash_table_set_value shall call clds_sorted_list_set_value with the key, new_item, condition_check_func, condition_check_context and old_item and only_if_exists set to true. ]*/
CLDS_SORTED_LIST_SET_VALUE_RESULT sorted_list_set_value_result = clds_sorted_list_set_value(bucket_list, clds_hazard_pointers_thread, key, (void*)new_item, condition_check_func, condition_check_context, (void*)old_item, sequence_number, true);
switch (sorted_list_set_value_result)
{
default:
case CLDS_SORTED_LIST_SET_VALUE_ERROR:
/* Codes_SRS_CLDS_HASH_TABLE_01_111: [ If clds_sorted_list_set_value fails, clds_hash_table_set_value shall fail and return CLDS_HASH_TABLE_SET_VALUE_ERROR. ]*/
LogError("Cannot set key in sorted list: failed with %" PRI_MU_ENUM "", MU_ENUM_VALUE(CLDS_SORTED_LIST_SET_VALUE_RESULT, sorted_list_set_value_result));
set_value_in_top_level = false;
break;
case CLDS_SORTED_LIST_SET_VALUE_OK:
/* Codes_SRS_CLDS_HASH_TABLE_01_112: [ If clds_sorted_list_set_value succeeds, clds_hash_table_set_value shall return CLDS_HASH_TABLE_SET_VALUE_OK. ]*/
result = CLDS_HASH_TABLE_SET_VALUE_OK;
set_value_in_top_level = false;
break;
case CLDS_SORTED_LIST_SET_VALUE_CONDITION_NOT_MET:
/* Codes_SRS_CLDS_HASH_TABLE_04_001: [ If clds_sorted_list_set_value returns CLDS_SORTED_LIST_SET_VALUE_CONDITION_NOT_MET, clds_hash_table_set_value shall fail and return CLDS_HASH_TABLE_SET_VALUE_CONDITION_NOT_MET. ]*/
result = CLDS_HASH_TABLE_SET_VALUE_CONDITION_NOT_MET;
set_value_in_top_level = false;
break;
case CLDS_SORTED_LIST_SET_VALUE_NOT_FOUND:
/* Codes_SRS_CLDS_HASH_TABLE_01_109: [ If the key is not found, clds_hash_table_set_value shall advance to the next level of buckets. ]*/
break;
}
}
}
else
{
/* Codes_SRS_CLDS_HASH_TABLE_01_107: [ If there is no sorted list in the bucket identified by the hash of the key, clds_hash_table_set_value shall advance to the next level of buckets. ]*/
}
find_bucket_array = next_bucket_array;
}
if (set_value_in_top_level)
{
/* Codes_SRS_CLDS_HASH_TABLE_01_102: [ If the key is not found in any of the non top level buckets arrays, clds_hash_table_set_value: ]*/
BUCKET_ARRAY* current_bucket_array = first_bucket_array;
// look for the item in this bucket array
// find the bucket
bucket_index = hash % interlocked_add(¤t_bucket_array->bucket_count, 0);
bool restart_needed = false;
do
{
/* Codes_SRS_CLDS_HASH_TABLE_01_103: [ clds_hash_table_set_value shall obtain the sorted list at the bucket corresponding to the hash of the key. ]*/
// do we have a list here or do we create one?
bucket_list = interlocked_compare_exchange_pointer((void* volatile_atomic*) ¤t_bucket_array->hash_table[bucket_index], NULL, NULL);
if (bucket_list != NULL)
{
restart_needed = false;
}
else
{
// create a list
/* Codes_SRS_CLDS_HASH_TABLE_01_104: [ If no list exists at the designated bucket, one shall be created. ]*/
bucket_list = clds_sorted_list_create(clds_hash_table->clds_hazard_pointers, get_item_key_cb, clds_hash_table, key_compare_cb, clds_hash_table, clds_hash_table->sequence_number, clds_hash_table->sequence_number == NULL ? NULL : on_sorted_list_skipped_seq_no, clds_hash_table);
if (bucket_list == NULL)
{
/* Codes_SRS_CLDS_HASH_TABLE_01_106: [ If any error occurs, clds_hash_table_set_value shall fail and return CLDS_HASH_TABLE_SET_VALUE_ERROR. ]*/
LogError("Cannot allocate list for hash table bucket");
restart_needed = false;
}
else
{
// now put the list in the bucket
if (interlocked_compare_exchange_pointer((void* volatile_atomic*)¤t_bucket_array->hash_table[bucket_index], bucket_list, NULL) != NULL)
{
// oops, someone else inserted a new list, just bail on our list and restart
clds_sorted_list_destroy(bucket_list);
restart_needed = true;
}
else
{
// set new list
restart_needed = false;
}
}
}
} while (restart_needed);
if (bucket_list == NULL)
{
LogError("Cannot acquire bucket list");
result = CLDS_HASH_TABLE_SET_VALUE_ERROR;
}
else
{
HASH_TABLE_ITEM* hash_table_item = CLDS_SORTED_LIST_GET_VALUE(HASH_TABLE_ITEM, new_item);
hash_table_item->key = key;
/* Codes_SRS_CLDS_HASH_TABLE_01_105: [ clds_hash_table_set_value shall call clds_hash_table_set_value on the top level bucket array, passing key, new_item, condition_check_func, condition_check_context, old_item and only_if_exists set to false. ]*/
CLDS_SORTED_LIST_SET_VALUE_RESULT sorted_list_set_value = clds_sorted_list_set_value(bucket_list, clds_hazard_pointers_thread, key, (void*)new_item, condition_check_func, condition_check_context, (void*)old_item, sequence_number, false);
if (sorted_list_set_value == CLDS_SORTED_LIST_SET_VALUE_CONDITION_NOT_MET)
{
/* Codes_SRS_CLDS_HASH_TABLE_04_002: [ If clds_sorted_list_set_value returns CLDS_SORTED_LIST_SET_VALUE_CONDITION_NOT_MET, clds_hash_table_set_value shall fail and return CLDS_HASH_TABLE_SET_VALUE_CONDITION_NOT_MET. ]*/
LogError("Condition not met during set value - %" PRI_MU_ENUM "", MU_ENUM_VALUE(CLDS_SORTED_LIST_SET_VALUE_RESULT, sorted_list_set_value));
result = CLDS_HASH_TABLE_SET_VALUE_CONDITION_NOT_MET;
}
else if (sorted_list_set_value != CLDS_SORTED_LIST_SET_VALUE_OK)
{
/* Codes_SRS_CLDS_HASH_TABLE_01_100: [ If clds_sorted_list_set_value returns any other value, clds_hash_table_set_value shall fail and return CLDS_HASH_TABLE_SET_VALUE_ERROR. ]*/
LogError("Cannot set key in sorted list - %" PRI_MU_ENUM "", MU_ENUM_VALUE(CLDS_SORTED_LIST_SET_VALUE_RESULT, sorted_list_set_value));
result = CLDS_HASH_TABLE_SET_VALUE_ERROR;
}
else
{
if (*old_item == NULL)
{
(void)interlocked_increment(&first_bucket_array->item_count);
}
/* Codes_SRS_CLDS_HASH_TABLE_01_099: [ If clds_sorted_list_set_value returns CLDS_SORTED_LIST_SET_VALUE_OK, clds_hash_table_set_value shall succeed and return CLDS_HASH_TABLE_SET_VALUE_OK. ]*/
result = CLDS_HASH_TABLE_SET_VALUE_OK;
}
}
}
(void)interlocked_decrement(&first_bucket_array->pending_insert_count);
/* Codes_SRS_CLDS_HASH_TABLE_42_060: [ clds_hash_table_set_value shall decrement the count of pending write operations. ]*/
end_write_operation(clds_hash_table);
}
return result;
}