singly linked-list design

I can figure out how to make a practical *ordered* singly-linked list, but not a practical *unordered* singly-linked list. Bit of a surprise!

The key problem is iterating over the list.

Imagine you have a list, and you want to iterate over it.

You have a cursor; it points at the element you’re currently looking at, and prevents it from being deallocated. It does not – cannot – prevent it from being *unlinked*.

Now, when you want to move to the next element, you get the next pointer of your current element (which is to say, you point a hazard pointer at it, and then get hold of the value of the hazard pointer, this means the next element also can’t be deallocated – but it still can be unlinked.

So the problem is this : your cursor is on an element, any element, that’s fine (just assume we got there – it doesn’t change anything – we’re setting up a scenario which illustrates the problem). We get our next pointer, that’s fine. Before we move to the next element, though, someone else unlinks it.

Well, huh. So at this point, the next element we’re about to move to is unlinked – but it still points at what was *its* next element, so we’re still okay… (and we know the element has been unlinked, because its unlink warning bit has been set by the thread which unlinked it).

But what now happens if the element *after* our next element is unlinked *and* deallocated – which it can be, as we have no hazard pointer on it.

Because our next element has been unlinked, its next pointer is *not* updated by the unlink of its next element. So now the cursor is pointing at an element which has a next pointer pointing at deallocated store.

So what we see is that if we see the unlink bit is set, we have to abort the iteration.

Now, if we’re aborted the iteration, well, then what? users will often want to iterate over the whole list and look at each element just once. So we need to restart the iteration, at the point we left off.

But in an unordered list, we can have no idea where that point is, because the entire list could have been deallocated and replaced in the meantime.

We can only know where that point is if the list is *ordered*. Then the key held by the unlinked element which derailed us, which we still hold a hazard point to and so which cannot be deallocated, let’s us know how far we have to fast-forward over the list to get back to the point where we can recommence the iteration.