Creating a Thread-Safe List with Iterators
This afternoon I started work on the next component of the greek engine project - a list of pointers (instruments) that is thread-safe, and has iterators that are never invalidated. It's the combination there that's really tricky... how to make a list that has many iterators on it - none of which will be invalidated on an isert or removal operation on the list.
Yeah, that took some thinking.
My initial idea is to have a fixed-length list of nodes. Each node has a value, a 'valid' flag, and a spinlock. In order to add to the list, you need to scan the list looking for the first node that is not valid, but who's try_lock() is successful. You can then place the value into the table. Pretty simple, really. The locks don't effect anyone else, and things are pretty smooth.
The iterators are going to be something where I can step through all the valid values and optionally lock on that node to make sure it gets "stepped over" by the other iterators. It should make for just what I'm looking for.
Lots of coding to do, but I think it's all planned out and should work. I just need to actually do it.