Store An Address And A Bool In One Word For Lock-free Doubly Linked List

I am reading some paper for lock-free doubly linked list. In these papers, they store an address to next and prev node and a flag in one word(int). Is it because in 32-bit architec

Solution 1:

You're more or less correct. It's a common space optimization in very low level code. It is not portable. (You could make it slightly more portable by using intptr_t instead of int.)

Also, of course, the alignment only holds for pointers to more complex types; a char* won't necessarily be aligned. (The only times I've seen this used is in the implementation of memory management, where all of the blocks involved are required to be aligned sufficiently for any type.)

Finally, I'm not sure what the authors' of the paper are trying to do, but the code you post cannot be used in a multithreaded environment, at least on modern machines. To ensure that a modification in one thread is seen in another thread, you need to use atomic types, or some sort of fence or membar.

Solution 2:

Addresses in most 32-bit architectures are not stored in 4-byte boundaries, but 1-byte. They are read from memory at 4-byte (the typical word size) increments. Without seeing the code for this doubly linked list, it sounds like they are enforcing some rules for how the container will store data.