Well, once this thread refuses to die anyway, I am going to make one more post to it
For XOR doubly linked list. Objective is to reduce memory usage w/o compromising OPS time.
After thinking carefully about the whole thing I realised that, in actuality, the whole thing can be,indeed, highly beneficial in some situations.
For example,consider the scenario when you want to have every thread to keep a list of RW locks that it has locked for R access, and every RW lock to keep a list of readers that have locked it. Once the same RW lock may be locked by multiple readers at once, and the same thread may be locking multiple RW locks for R access at the time, a simplistic approach of embedding a pair of LIST_ENTRY structures in the ones that represent a thread and a lock so that the whole thing can get trivially linked together, is not going to work here.
Instead, you would need something more complex, which may be anything from “simplistic” dynamic LIST_ENTRY allocations to Solaris-like turnstiles.
This is where XOR-linked list may come in handy. Once it does not require the target structures to embed a pointer to the next list element you can simply embed a XOR-linked list into the structures that represent a thread and a lock, and that’s it. Certainly, a list like that is not an optimal solution when it comes to removing entries from the middle of the list (i.e.e something that we may be required to do in this case), but let’s get real - in practical terms, our lists are very unlikely to grow long, so that traversing a list in order to remove an an entry from the middle of it is not going to pose any more or less serious practical problem.
In other words, XOR-linked list’s feature of not requiring the target structures to embed a pointer to the next list element may find some useful practical applications other than just saving anything from 8 to 56 bytes of memory (which, IMHO, happens to be of very little practical significance in the year 2018 anyway)…
Anton Bassov