• Dave Watson's avatar
    ConcurrentHashMap · f0b5826b
    Dave Watson authored
    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
    f0b5826b
hazptr-impl.h 15.2 KB