SkipMap::compare_insert is not a CAS operation if the key is not present.

[VernonLD]

From the documentation, it appears that SkipMap::compare_insert directly inserts the value without invoking the closure function if the key is absent. This behavior does not align with a true CAS (Compare-And-Swap) operation, as it bypasses the condition check against the old value, even when the key is not present.

Is it possible to do a CAS operation with the closure function called that includes cases where the key is absent?

[taiki-e]

Could you elaborate on the behavior you are hoping for? If the key does not exist, what do you want it to be compared to?

[VernonLD]

If the key is not exist, is it possible to skip the insert? If there is nothing to compare, it shouldn't do the swap.

[VernonLD]

Add more details about the use case I am about to implement with the compare_insert.

We use skipmap as the underlying in memory data structure to store some data. And we are trying to achieve the similar CAS operation as in tikv.

https://docs.rs/tikv-client/latest/tikv_client/struct.RawClient.html#method.compare_and_swap

pseudo code for the behavior i am hoping for:

async fn compare_and_swap(
    &self,
    key: Key,
    previous_value: Option<Value>,
    new_value: Value,
) -> Result<(Option<Value>, bool), Error> {
    match previous_value {
        None =>
          /// atomically associate new_value against the key iff key does not exist
        Some(prev) =>
          /// atomically associate new_value against the key iff a value exist for provided key and the existing value in the skipmap is `prev`
    }
    ///( return///)
}

[taiki-e]

cc @Tianion (who added compare_insert in https://github.com/crossbeam-rs/crossbeam/pull/976)

Perhaps a good solution here would be to change the closure of compare_insert to take Option<&V>? or add new variant that do it?

[Tianion]

I'm not sure how take Option<&V> solves this. Adding a variable is feasible, but I'm not sure if it's better to not insert if the key doesn't exist. Traditional CAS doesn't deal with missing keys. Maybe it would be better to return an Err in this case?

[taiki-e]

I was thinking a closure that takes Option<&V> (Some if key is present, None if key is not present) could handle both use cases:

• If the user want not to insert if key is not present, they can return false for None.
• If the user want to insert if key is not present, they can return true for None.

However, that might be an idea that would complicate the API.