ConcurrentSkipList Bug

ConcurrentSkipList Bug

Summary:
Bug reported by Yan Lin (not a facebook employee) through @robbert.

@philipp and @jdelong: you are the only two remaining facebookers to have
made non-trivial changes to this code.

Description of bug: layer 0 is 1->4, and we're looking for 3. We pass
over 4, and see that 1 is less than 3 in the for loop. Now a race
condition: another thread inserts 2, so layer 0 is now 1->2->3. Then,
since ht==0, we return pred->skip(0), which is now 2 instead of 4.

Why this is bad: it really breaks the lower_bound function (lower_bound
calls findNode calls findNodeDownRight), since it returns an element
that is lesser.

This patch doesn't change the behavior of the code in the normal case;
it just recycles previously-computed values so that this race condition
doesn't crash and burn.

Patch based off of Yan Lin's in-email suggestion.

Test Plan:
fbconfig -r folly && fbmake runtests

Reviewed By: philipp@fb.com

Subscribers: sdwilsh, folly-diffs@, jdelong, robbert, philipp

FB internal diff: D1732434

Signature: t1:1732434:1418260198:8c707435825cfa2a1093b681e066f320193e98f2