#Order of pops is strange#

If I am reading your code correctly, your pop ordering will be different from the push ordering. Suppose we push 1 2 3 4 5 in that order. Your inbox will look like:

5 -> 4 -> 3 -> 2 -> 1

So far so good. But then when we pop for the first time, this is what happens:

ret = 5
outbox = 1 -> 2 -> 3 -> 4

Then the next time we pop:

ret = 1
outbox = 2 -> 3 -> 4

So the full sequence of pops becomes: 5 1 2 3 4 when it should be 5 4 3 2 1. Thus, I don't think you can call this a stack because it doesn't behave like one. Note that this is all with only only thread, so it isn't a multithreading issue.

Furthermore, if additional pushes arrive while there are still items in the outbox, the outbox will be emptied before any new items will be popped. I'm not sure if you intended to do this (because you called your stack "unreliably ordered"). I would think that a stack should always pop the newest item off first, though.

#Potential fix#

For the first problem, you could simply change the put_on_outbox code from this:

 put_on_outbox:
 atomic_thread_fence(memory_order_acquire);
 for (struct linted_node *node = ret->next;;) {
 if (0 == node)
 break;
 struct linted_node *next = node->next;
 node->next = stack->outbox;
 stack->outbox = node;
 node = next;
 }

to this:

 put_on_outbox:
 atomic_thread_fence(memory_order_acquire);
 stack->outbox = ret->next;

Note that when arriving at put_on_outbox:, stack->outbox is guaranteed to be NULL and ret is guaranteed to be non-NULL.

Order of pops is strange

If I am reading your code correctly, your pop ordering will be different from the push ordering. Suppose we push 1 2 3 4 5 in that order. Your inbox will look like:

5 -> 4 -> 3 -> 2 -> 1

So far so good. But then when we pop for the first time, this is what happens:

ret = 5
outbox = 1 -> 2 -> 3 -> 4

Then the next time we pop:

ret = 1
outbox = 2 -> 3 -> 4

So the full sequence of pops becomes: 5 1 2 3 4 when it should be 5 4 3 2 1. Thus, I don't think you can call this a stack because it doesn't behave like one. Note that this is all with only only thread, so it isn't a multithreading issue.

Furthermore, if additional pushes arrive while there are still items in the outbox, the outbox will be emptied before any new items will be popped. I'm not sure if you intended to do this (because you called your stack "unreliably ordered"). I would think that a stack should always pop the newest item off first, though.

Potential fix

For the first problem, you could simply change the put_on_outbox code from this:

 put_on_outbox:
 atomic_thread_fence(memory_order_acquire);
 for (struct linted_node *node = ret->next;;) {
 if (0 == node)
 break;
 struct linted_node *next = node->next;
 node->next = stack->outbox;
 stack->outbox = node;
 node = next;
 }

to this:

 put_on_outbox:
 atomic_thread_fence(memory_order_acquire);
 stack->outbox = ret->next;

Note that when arriving at put_on_outbox:, stack->outbox is guaranteed to be NULL and ret is guaranteed to be non-NULL.

#Order of pops is strange#

If I am reading your code correctly, your pop ordering will be different from the push ordering. Suppose we push 1 2 3 4 5 in that order. Your inbox will look like:

5 -> 4 -> 3 -> 2 -> 1

So far so good. But then when we pop for the first time, this is what happens:

ret = 5
outbox = 1 -> 2 -> 3 -> 4

Then the next time we pop:

ret = 1
outbox = 2 -> 3 -> 4

So the full sequence of pops becomes: 5 1 2 3 4 when it should be 5 4 3 2 1. Thus, I don't think you can call this a stack because it doesn't behave like one. Note that this is all with only only thread, so it isn't a multithreading issue.

Furthermore, if additional pushes arrive while there are still items in the outbox, the outbox will be emptied before any new items will be popped. I'm not sure if you intended to do this (because you called your stack "unreliably ordered"). I would think that a stack should always pop the newest item off first, though.

#Order of pops is strange#

If I am reading your code correctly, your pop ordering will be different from the push ordering. Suppose we push 1 2 3 4 5 in that order. Your inbox will look like:

5 -> 4 -> 3 -> 2 -> 1

So far so good. But then when we pop for the first time, this is what happens:

ret = 5
outbox = 1 -> 2 -> 3 -> 4

Then the next time we pop:

ret = 1
outbox = 2 -> 3 -> 4

So the full sequence of pops becomes: 5 1 2 3 4 when it should be 5 4 3 2 1. Thus, I don't think you can call this a stack because it doesn't behave like one. Note that this is all with only only thread, so it isn't a multithreading issue.

Furthermore, if additional pushes arrive while there are still items in the outbox, the outbox will be emptied before any new items will be popped. I'm not sure if you intended to do this (because you called your stack "unreliably ordered"). I would think that a stack should always pop the newest item off first, though.

#Potential fix#

For the first problem, you could simply change the put_on_outbox code from this:

 put_on_outbox:
 atomic_thread_fence(memory_order_acquire);
 for (struct linted_node *node = ret->next;;) {
 if (0 == node)
 break;
 struct linted_node *next = node->next;
 node->next = stack->outbox;
 stack->outbox = node;
 node = next;
 }

to this:

 put_on_outbox:
 atomic_thread_fence(memory_order_acquire);
 stack->outbox = ret->next;

Note that when arriving at put_on_outbox:, stack->outbox is guaranteed to be NULL and ret is guaranteed to be non-NULL.