Thread Safe Queries on a Trie? Use a Trash Can!
I've been facing this problem with my Trie - seeing as how it's lockless, it's replacing elements very fast, and it's possible that a query of the trie can get you into trouble because during the query, a replacement can come in and the value you're querying gets deleted. Then you're looking at a nasty seg fault.
The problem is, you don't want to put a lock in there of any kind - that's going to defeat the purpose of the trie in the first place. So how do you protect queries, but not slow anything down? I was stumped. Until I had a flash - the trash.
If I used a very simple std::slist<Message *> as the "trash", and then a simple boolean that controlled it's use, I can make the put() method look like:
Message *old = mmap::put(aMessage); if (old != NULL) { if (mUseTrash) { mTrashCan.push_front(old); } else { delete old; } }
Then, when we're done, we can simply run through all the messages in the "trash", and delete them. Very nice and very clean.
The one wrinkle in this is that the Trie itself is not the place to put this code. The Trie doesn't have the behavior that old contents are deleted, they are just passed back to the caller. It's the subclass - my QuickCache, that implements this "delete the old" behavior. This means that I need to put the code there, and that makes it a lot less elegant, but still very nice. The Trie stays clean, and that's good.
Still... nice solution to a nasty problem.