ConcurrentHashMap

ConcurrentHashMap

Summary:
A ConcurrentHashMap with wait-free readers, as in Java's ConcurrentHashMap.

It's a pretty generic closed-addressing chaining hashtable, except find() uses two hazard pointers
to do hand-over-hand traversal of the list, so it never takes a lock.

On rehash, only the part of the chain that remains the same (i.e. is still hashed to the same bucket)
is reused, otherwise we have to allocate new nodes.

Reallocating nodes means we either have to copy the value_type, or add in an extra indirection
to access it.  Both are supported.

There's still a couple opportunities to squeeze some more perf out with optimistic loading
of nodes / cachelines, but I didn't go that far yet, it sill looks pretty good.

Reviewed By: davidtgoldblatt

Differential Revision: D5349966

fbshipit-source-id: 022e8adacd0ddd32b2a4563caa99c0c4878851d8