hi phil,

I understand that your implementation uses tagged pointers to avoid ABA problems. An issue with tagged pointers is that naively they will be 2*sizeof(T*) and systems may not have atomic operations that operate on things of that size. Looking at the code, I see that you also have a "compressed" tagged pointer that is enabled for some architectures. Having found this code, I now vaguely recall some previous mailing list discussions about this.

actually i think that most 64bit architectures do not use the full 64bit address space, but unfortunately this is often not defined in the specifications :/

Sometimes it may be possible to claim that users (& reviewers?) of a library do not need to know about details of this sort because the library "just works", and that if they are curious they can read the source. I don't think this is one of those cases. The documentation should explain in outline how this works, and provide rationale for why it is how it is.

well, this just is the case for these data structures. however there is lock- free dequeue for example, which requires access to two tagged pointers (an implementation of it was posted a few months ago, but i didn't want to include that into boost.lockfree for now). however i could add a section about `internals' of the library to the docs. anyway, yesterday i started to implement a modified version of the freelist, that does not use pointers, but 16bit indices. this limits the possible size of the data structure to 2**16-1 elements, but 16bit pointer and 16bit aba prevention tag can be packed into one 32bit word. it really complicates the implementation, but it should ensure the lock-freedom on many ll/sc-based platforms (like ppc).

IIRC, ARM has 64-bit atomics only from architecture version 6k onwards, and my Boost.Atomic ARM code doesn't use them. This could be fixed.

that would be great! do you know if the pointer compression would be feasible on arm as well? cheers, tim