StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I think there is an error in how you use the counter in takeOrNull(), when you remove the stub, you decrease Length by 1, but don't re-increase it when adding the stub back at the end, since you use addNode() instead of add(). Let's say you added an element successfully, so your queue looks like this:</p> <pre><code>Length is 2 STUB -> FIRST_NODE -> NULL ^ ^ | | Head Tail </code></pre> <p>So now one thread starts doing takeOrNull(), length decreases to 1, Head moves to FIRST_NODE, and since this is the STUB node, it gets re-added to the end, so now you have:</p> <pre><code>Length is 1 FIRST_NODE -> STUB -> NULL ^ ^ | | Head Tail </code></pre> <p>Do you see? Length is 1 now! On the next takeOrNull(), you will get NULL, even if FIRST_NODE is still in the queue and has never been returned... You just (temporarily) lost a piece of data. Further, you can now repeat this ad infinitum and start accumulating nodes. Like if you add three nodes, Length is 4 and you have FIRST, STUB, NEW1, NEW2, NEW3. If you then do three takeOrNull(), you end up with NEW2, NEW3, STUB and Length 1. So this way you end up loosing elements, but I admit to not being completely sure about how this would ever trigger the exception. Let me eat and think about it some more. ;-)</p> <p>EDIT: Ok food did me good, I came up with a sequence that triggers the head null exception. Let's start with a valid queue with one element like before:</p> <pre><code>Length is 2 STUB -> FIRST_NODE -> NULL ^ ^ | | Head Tail </code></pre> <p>Now we have four threads, two that try to takeOrNull() and two that add() concurrently. Both add threads have moved the tail pointer correctly, the first one moved tail from FIRST to SECOND, and then was paused. The second add thread moved then tail from SECOND to THIRD, then updated the old tail's (SECOND's) next pointer, and then incremented the counter and exited. We're left with:</p> <pre><code>Length is 3 STUB -> FIRST_NODE -> NULL SECOND_NODE -> THIRD_NODE -> NULL ^ ^ | | Head Tail </code></pre> <p>Now the two takeOrNull threads wake up and execute, since Length is 3, both will be able to get an element! The first one moves Head from STUB to FIRST, the second moves Head from FIRST to NULL. And now HEAD is null, and whenever takeOrNull() gets called next, EXCEPTION!</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload