Several fixes to the "SWMRList" example in experimental/hazptr. v2017.03.27.00
authorArthur O'Dwyer <arthur.j.odwyer@gmail.com>
Sat, 25 Mar 2017 20:43:31 +0000 (13:43 -0700)
committerFacebook Github Bot <facebook-github-bot@users.noreply.github.com>
Sat, 25 Mar 2017 20:49:52 +0000 (13:49 -0700)
commit4cc8030e3bdc894c3979529e025c3160fd39ecd9
treede686aa05455f24511c1124b47b93ef5392f4d1d
parent2e0f52d25a6e165f406a922c2ab657b43e315eae
Several fixes to the "SWMRList" example in experimental/hazptr.

Summary:
Fix a correctness bug in "SWMRList.h".

Thanks to Maged for the tip! The old code omitted setting a removed node's
"next" pointer to `nullptr`, which meant that if the writer removed node
A and then node B = A->next while the reader was looking at B, then the reader
might happily keep chasing pointers B->next, B->next->next,... without ever
noticing that it was now on a "dead branch" of the linked list.

(And then there's a bit of a trick: you really do have to remove the node
first and *then* set its "next" pointer to null, because if you do the null
assignment first, you'll truncate the list, which means that some readers
will see a truncated list and return the wrong answer. I've added comments
to try to explain this to future-me.)

Style nit: Avoid doing multiple atomic operations on the same line of code.

----

Modernize the parameter-passing conventions in SWMRList.h.

Pass `T`s by const reference, except in `add` where we're likely to want to
make a copy of the `T` anyway. In that case it would be more "STL-correct"
to supply two different overloads `add(T&&)` and `add(const T&)`, but this
is just an example so it makes sense to keep things simple.

----

Fix an undefined behavior in SWMRList example.

Searching an empty SWMRList<int> always invokes undefined behavior by
comparing an uninitialized `T elem` against `val` on the final line of
the `contains` function. Besides, this patch allows SWMRList to work
with `T`s that aren't default-constructible or even copy-constructible.

----

Closes https://github.com/facebook/folly/pull/566

Reviewed By: djwatson

Differential Revision: D4772359

Pulled By: yfeldblum

fbshipit-source-id: 8f96573530800675cb56006aa91e7a5c5c1fb85d
folly/experimental/hazptr/example/SWMRList.h