Summary of this post: I have an set of ordered items whose order may change over time. I need to be able to iterate through this set from multiple threads, each of which may also want to update the order of the items.
For example, multiple threads need to access String keys in some arbitrary sorted order. They strings are not sorted according to their natural ordering, but by some values that may change (hence, a custom Comparator). My original implementation was to use a TreeSet and synchronize on it. If any of the keys needed to be reordered, a thread would remove the key from the map, update the comparison value, and reinsert the key. To implement this, the keys are native Strings, but the comparator has access to the values. This is a weird arrangement where the order of keys may change over time, but since a changed key is always removed and reinserted when it changes, it seems to work. (I suppose it could also work if the Strings were wrapped inside another object.)
I recently became aware of the ConcurrentSkipListSet/ConcurrentSkipListMap implementations which are basically thread-safe sorted sets (resp. maps.) It seems like I can now iterate through the keys without having to lock the entire data structure. However, is there a way I can use them to atomically remove a key and replace it with another, like the operation I was doing above, so that other iterating threads don't miss the item, and without having to use synchronize blocks?
If anyone can suggest a better data structure for this type of operation, I'm all ears, too!
is there a way I can use them to atomically remove a key and replace it with another, like the operation I was doing above, so that other iterating threads don't miss the item, and without having to use synchronize blocks?
The short answer is no. If you need to remove and reinsert, there is no atomic way to do this with any collection that I know of.
That said, one possibility would be for you to reinsert the item before deleting it from the skip list. This would cause a duplicate but may be easier to handle then a missing entry. You would reinsert it after you changed the object so it would sort differently. This assumes that the object would then be non-equal as well. But if the other threads that are processing the lists can't handle the duplicates then I think you are SOL.