在非阻塞队列 c++ 中使用指针的最高有效位作为标记

Question

我正在尝试实现一个并发非阻塞队列，其中标记位于指针的 16 个最高有效位中。它在这里遵循这个算法： http://www.cs.rochester.edu/research/synchronization/pseudocode/queues.html

但是，该算法假定一个指针结构，该结构具有用于标记的单独计数变量 (

structure pointer_t {ptr: pointer to node_t, count: unsigned integer}

)。但是，我必须像这样用指针来做：

template<class P>
struct pointer_t {
    P* ptr;
    //no uint to store the tag
    P* address(){
        return (P*)(ptr & 0x0000FFFFFFFFFFFF);
    }

    uint count(){
        return ptr & 0xFFFF000000000000;
    }
};

我有几个问题：

1. 如何提取指针地址的计数（16 个最高有效位）并将其转换为

   uint

   以返回？目前我的计数函数只返回 MSB 而不是

   uint

   .

2. 我的地址函数是否正确返回指针的 48 位最低有效位？

3. 算法的比较和交换操作如下：

   CAS(&tail.ptr->下一个，下一个，)

如何在一次操作中同时更新尾部地址和递增计数？我需要使用已经提供的 CAS 函数，但我看不到它。所以我必须用一个同时执行这两个操作的操作来替换

<node, next.count+1>

。我假设这也涉及一些按位运算。

Answer 1

1. 你可以这样做

uint16_t count(){
    return ((uintptr_t)ptr >> 48) & 0xFFFF;
}

2. 不，实际上可能会出现编译错误。我正在使用 c++17，但这是你可以实现的方法。

P* address(){
    return (P*)((uintptr_t)ptr & 0x0000FFFFFFFFFFFF);
}

3. 这好像不是问题

编辑：我很笨，没有意识到它的其余部分是#3

的一部分

你是对的，它会涉及一些按位运算，或者，你可以像这样创建一个指向最后 16 位的指针并通过指针更新它：

uint16_t* count = (uint16_t*)((uint8_t*)&ptr + 6);

*count++;

我可能会自己走指针路线。您甚至可以使用此指针获取当前计数值并将我的#1 答案替换为

uint16_t count(){
    return *count;
}

免责声明：如果您需要优化性能，则这些都没有优化。肯定有办法让它变得更好，但这是我的头等大事，我至少要开始解决这个问题