Предполагая, что ваш ЦП имеет функцию сравнения и замены по всему указателю (compxchg8b на 486 или выше, compxchg16b на большинстве машин amd64 [не представлен на некоторых ранних моделях Intel]) ... Есть алгоритм здесь .
Обновление: нетрудно перевести это на C ++, если вы не боитесь делать немного работы. : P
Этот алгоритм предполагает структуру "указатель с тегом", которая выглядит следующим образом:
// Be aware that copying this structure has to be done atomically...
template <class T>
struct pointer
{
T *ptr;
uintptr_t tag;
};
Затем вы хотите обернуть инструкции lock cmpxchg{8|16}b некоторым встроенным ассемблером ...
Может быть, тогда вы можете написать узел очереди следующим образом:
template <class T>
struct queue_node
{
T value;
pointer<queue_node<T> > next;
};
Остальное - более или менее расшифровка алгоритма, с которым я связался ...