singly-linked list update

So, it’s all very interesting.

You need a cursor, to iterate over the list – because you need a pair of hazard pointers to iterate. There’s a problem here though I think – when we deregister an SMR hazard pointer per-thread state, there can be allocations still in the list of allocations pending reclamation. An unusued thread state with lingering elements is always checked by the other threads; so either we can’t use it till its clear (which is awkward as hell for the user – remember, we will not look to dynamic allocation as the library performs no allocations) or when we re-use, we then rely upon the now-owning thread to run scans. Problem is, that now-owning thread is expecting to be the sole owner – he has no idea he might have gigabytes of store sitting in his pending reclamation list! so I have to find a nice solution to this.

Another problem I’m currently grappling with is that although the hazard pointers prevent any element you’re using from being deallocated, they don’t stop it from being unlinked.

If you’re unlinked, it could be the element after you is unlinked before you try to get_next with the cursor – problem then is the next pointer in your element is now pointing at a deallocated allocation because of course it’s not updated when that next element was unlinked…!

I’m vaguely thinking there needs to be a “deleted bit” *IN* an element, which is an immediate logical delete, which is followed then by the usual delete bit in the predecessor element, as part of the two-step unlink (which I think is still needed – but not certain).

However, this is because I’ve not got the way it all works clear yet in my head, so it could be complete garbage.