3 ms·
How does deletion work in ring-style lists when there's only one element in the list? Wouldn't that break a branchless implementation? How is the empty ring rep
by ced 16y ago
How does deletion work in ring-style lists when there's only one element in the list? Wouldn't that break a branchless implementation? How is the empty ring represented, anyway?
As for his test purportedly showing that A is better than B on Linux... It's only right if you assume that Linux can only use one type of list in all cases.
- rwmj 16y agoAn empty ring never needs to be presented. The point about the Linux list is that it lives inside another struct. If there are no instances of that struct, then there is no need to represent an empty list at all!
- ced 16y agoYeah, I thought about that. But he mentions "emptiness testing" a few times in the rest of the post. If there's no empty list representation, what's the point?
- tedunangst 16y agoI think you're confused. The list head exists outside of the structs that are in the list. The list links (next and prev) live in the struct, but not the head. To answer the original question, you decide a list is empty when prev == next.
- ced 16y agoBut isn't that true if the list has one element? Then A->A, thus prev==next, but the list still isn't empty. And if the head lives outside of the list proper, then you would need special-case code to handle deletion of the first element in the list (since the head contains a pointer to it). It wouldn't be branchless.
- tedunangst 16y agoThere is a fake element that is the head. It doesn't count as part of the list, but it's always in the list. With one element, the list is H->next = A, A->next = H H->prev = A, A->prev = H
- ced 16y agoOh, that's a clever solution. Thanks.