Quote: volatile size_t* popPtr = &popCount volatile size_t* pushPtr = &pushCount return ( (*popPtr) - (*pushPtr) );
How is that not a random number? And why bother doing the pointer stuff?
What guarantees are you trying to pull off? And if your function guarantees nothing, shouldn't it be rather explicit about guaranteeing nothing?
Ie, between reading either of those varibles and reading the other, the other pointer could be increased by an arbitrary amount. Which means that you could get a value anywhere between -infinity and +infinity, regardless of the state of the stack when you enter the function or after you leave the function.
(Note that the order the values are read is undefined by the above code. I don't think there are any sequence points between a() and b() in the expression: a() - b())...
Ayep:
http://en.wikipedia.org/wiki/Sequence_point
Even if there was a sequence point (which you could cause by breaking the statement up a bit), it would still generate an interval of results that was open to infinity or negative infinity.
Quote: size_t elementIndex = ((*pushPtr) & (length-1));
Did you just assume length was a power of two?
You should check that. Ie:
// fails to compile if passed false:template<bool b>struct AssertTrue;template<> struct AssertTrue<true> {};template<size_t n>struct AssertEven: AssertTrue<(n/2)*2 == n> {};template<size_t n>struct AssertPowerOfTwo: AssertEven<n>, AssertPowerOfTwo<n/2>{};template<> struct AssertPowerOfTwo<1>: AssertTrue<true> {};
Then a compile-time assert that your length is a power of two becomes easy.
Quote:
volatile size_t* pushPtr = &pushCount
size_t elementIndex = ((*pushPtr)+1);
*pushPtr = elementIndex;
If you are the only thread writing, you don't have to worry about saying things are volatile.
Quote: size_t elementIndex = (GMAtomicIncrement(popCount) - 1);
return (elementIndex & (length-1));
What guarantees, and or checks, do you have that you won't out-consume the producer?
Or that the producer won't think that you had consumed your element already, and happily write over it before you return?
...
If you are doing an always-incrementing stack with modular arithmetic, and are assuming that the ABA problem will never occur, what you need to do when you pop is:
1> Check that read pointer < write pointer. If not, fail (nothing to read!)
2> Get a copy of the data under the read pointer,
3> Do a CAS increment of the pointer, asserting it used to be pointing to the data you wanted.
4> If 3 fails, goto 1 and repeat until you succeed at step 3.
Then, on the push side:
1> Check that read pointer+length > write pointer (or is it >=? Hmm.). If not, fail (there is no room in the queue)
2> Once the above occurs, as only you are increasing the write pointer, nothing the other threads will do can break it. So now non-atomically:
3> Write to the data under the write pointer.
4> Increment the write pointer (the write has to be atomic -- and it is on most systems so long as your memory is aligned -- but the increment doesn't have to be)
I think the above works.
Note that a CAS increment is not a mere atomic increment. You need to insure both that you are increasing it by 1, and that the old value was the data you made a local copy of.
This makes a couple assumptions (such as reading from the data is thread-safe, and works even if the data is being corrupted or written to by some other thread! I'd make your queue a queue of pointers, and just copy the pointers, and this works nicely.)
