I am trying to implement a concurrent non-blocking queue where the tag is in the 16 most significant bits of the pointer. It follows this algorithm here: http://www.cs.rochester.edu/research/synchronization/pseudocode/queues.html
However, this algorithm assumes a pointer struct with a separate count variable for the tag (structure pointer_t {ptr: pointer to node_t, count: unsigned integer}
). However, I have to do it with just the pointer like so:
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;
}
};
I have a couple of questions:
uint
to return? Currently my count function just returns the MSBs and not the uint
.CAS(&tail.ptr->next, next, <node, next.count+1>)
<node, next.count+1>
with an operation that does both. I am assuming this also involves some bitwise operations.uint16_t count(){
return ((uintptr_t)ptr >> 48) & 0xFFFF;
}
P* address(){
return (P*)((uintptr_t)ptr & 0x0000FFFFFFFFFFFF);
}
uint16_t* count = (uint16_t*)((uint8_t*)&ptr + 6);`
*count++;
I'd probably go the pointer route myself. you could even use this pointer to get the current count value and replace my #1 answer with
uint16_t count(){
return *count;
}
disclaimer: none of this is optimized, if you need to optimize for performance. there are definitely ways to make this better, but this is off the top of my head how i'd at least start to work out this problem