[A]CID with HashMap

To subtract from a map a needed count of items that stored in other map, I use this code:

// needed, stored are mutableMapOf<Key, Int>()

needed.forEach {
    if (stored.getOrDefault(it.key, 0) < it.value)
        return "Not enough ${it.key}"
}
// Subtract resources
needed.forEach {
    stored.dec(it.key, it.value)
}

fun <T> MutableMap<T, Int>.dec(key: T, value: Int = 1) = merge(key, value, Int::minus)

Is it possible to simplify to a single loop? If return can provide full list of missing items without performance decrease, it could be nice.

I think your code is just fine. If you want to keep the behavior where in the case any of items is missing, you don’t perform any operations, then you need at least two iterations. Which shouldn’t concern you.

You should think on how your function could communicate its result to the caller. Right now you return a string in the case of error, so what to return on success? Another string, empty string or null isn’t the best way to indicate success. You can throw an exception in the case of error, which is easy to do. Better, you can create a result object that describes the result and it could include the list of missing items in the case of error.

edit:
Please be aware your dec() isn’t a general purpose function for decreasing value in a map. In the case key is not present, it will set it to the provided value which is probably not what you want. This is not a problem in your above case, because you don’t invoke dec() if there are missing items, but if you accidentally use this function in another place, it could behave strangely.

Also, there is a corner case where stored doesn’t contain some key and needed contains it with value 0. In this case initial verification will pass and dec() will create that key in stored with value 0. I guess this is fine for your application logic, but it could be seen as a little strange behavior that removing items from a map actually could create entirely new map entries.

edit2:
Ahh and what do you mean with “ACID” in the title? This above code is definitely not thread-safe if this is what you meant. Executing it concurrently for the same map could easily break it.

4 Likes

By Atomic I meant the operation (subtraction in this case) executes fully (decrease all items by needed amount if item value > 0) or not executes at all for all items (map as a single value).
The next question: how to better update the code to subtract a min/max value? E.g. if we can’t subtract max, we are subtracting min (if we can)?

For atomic operations, you either need to make a copy of the entire map, or implement a more sophisticated structure than standard hash or tree maps.

Copying the map, and using a more sophisticated structure, are good options, but not the only ones.

Another might be to use locking/synchronisation to prevent multiple threads updating the map at the same time. And if anything about the update could fail, it could first check for all failure conditions before making any changes (or doing anything else with side-effects). That would make it completely atomic — though of course more complex and harder to get right.

(Which approach to use probably depends on the type of processing you’re doing, and the importance of single-threaded and/or multithreaded performance vs ease of development and maintenance.)

Looks like the property I needed is consistency.