concurrent_hash_map.h

/*
    Copyright 2005-2009 Intel Corporation.  All Rights Reserved.

    The source code contained or described herein and all documents related
    to the source code ("Material") are owned by Intel Corporation or its
    suppliers or licensors.  Title to the Material remains with Intel
    Corporation or its suppliers and licensors.  The Material is protected
    by worldwide copyright laws and treaty provisions.  No part of the
    Material may be used, copied, reproduced, modified, published, uploaded,
    posted, transmitted, distributed, or disclosed in any way without
    Intel's prior express written permission.

    No license under any patent, copyright, trade secret or other
    intellectual property right is granted to or conferred upon you by
    disclosure or delivery of the Materials, either expressly, by
    implication, inducement, estoppel or otherwise.  Any license under such
    intellectual property rights must be express and approved by Intel in
    writing.
*/

#ifndef __TBB_concurrent_hash_map_H
#define __TBB_concurrent_hash_map_H

#include <stdexcept>
#include <iterator>
#include <utility>      // Need std::pair
#include <cstring>      // Need std::memset
#include <string>
#include "tbb_stddef.h"
#include "cache_aligned_allocator.h"
#include "tbb_allocator.h"
#include "spin_rw_mutex.h"
#include "atomic.h"
#if TBB_USE_PERFORMANCE_WARNINGS
#include <typeinfo>
#endif

namespace tbb {

template<typename T> struct tbb_hash_compare;
template<typename Key, typename T, typename HashCompare = tbb_hash_compare<Key>, typename A = tbb_allocator<std::pair<Key, T> > >
class concurrent_hash_map;

namespace internal {
    typedef size_t hashcode_t;
    class hash_map_base {
    public:
        // Mutex types for each layer of the container
        typedef spin_rw_mutex node_mutex_t;
        typedef spin_rw_mutex chain_mutex_t;
        typedef spin_rw_mutex segment_mutex_t;

        typedef internal::hashcode_t hashcode_t;
        static const size_t n_segment_bits = 6;
        static const size_t n_segment = size_t(1)<<n_segment_bits; 
        static const size_t max_physical_size = size_t(1)<<(8*sizeof(hashcode_t)-n_segment_bits);
    };

    template<typename Iterator>
    class hash_map_range;

    struct hash_map_segment_base {
        hash_map_base::segment_mutex_t my_mutex;

        // Number of nodes
        atomic<size_t> my_logical_size;

        // Size of chains
        size_t my_physical_size;


        bool __TBB_EXPORTED_METHOD internal_grow_predicate() const;
    };


    template<typename Container, typename Value>
    class hash_map_iterator
        : public std::iterator<std::forward_iterator_tag,Value>
    {
        typedef typename Container::node node;
        typedef typename Container::chain chain;
        typedef typename Container::segment segment;

        Container* my_table;

        node* my_node;

        size_t my_array_index;

        size_t my_segment_index;

        template<typename C, typename T, typename U>
        friend bool operator==( const hash_map_iterator<C,T>& i, const hash_map_iterator<C,U>& j );

        template<typename C, typename T, typename U>
        friend bool operator!=( const hash_map_iterator<C,T>& i, const hash_map_iterator<C,U>& j );

        template<typename C, typename T, typename U>
        friend ptrdiff_t operator-( const hash_map_iterator<C,T>& i, const hash_map_iterator<C,U>& j );
    
        template<typename C, typename U>
        friend class internal::hash_map_iterator;

        template<typename I>
        friend class internal::hash_map_range;

        void advance_to_next_node() {
            size_t i = my_array_index+1;
            do {
                segment &s = my_table->my_segment[my_segment_index];
                while( i<s.my_physical_size ) {
                    my_node = s.my_array[i].node_list;
                    if( my_node ) goto done;
                    ++i;
                }
                i = 0;
            } while( ++my_segment_index<my_table->n_segment );
        done:
            my_array_index = i;
        }
#if !defined(_MSC_VER) || defined(__INTEL_COMPILER)
        template<typename Key, typename T, typename HashCompare, typename A>
        friend class tbb::concurrent_hash_map;
#else
    public: // workaround
#endif
        hash_map_iterator( const Container& table, size_t segment_index, size_t array_index=0, node* b=NULL );
    public:
        hash_map_iterator() {}
        hash_map_iterator( const hash_map_iterator<Container,typename Container::value_type>& other ) :
            my_table(other.my_table),
            my_node(other.my_node),
            my_array_index(other.my_array_index),
            my_segment_index(other.my_segment_index)
        {}
        Value& operator*() const {
            __TBB_ASSERT( my_node, "iterator uninitialized or at end of container?" );
            return my_node->item;
        }
        Value* operator->() const {return &operator*();}
        hash_map_iterator& operator++();
        
        Value* operator++(int) {
            Value* result = &operator*();
            operator++();
            return result;
        }
    };

    template<typename Container, typename Value>
    hash_map_iterator<Container,Value>::hash_map_iterator( const Container& table, size_t segment_index, size_t array_index, node* b ) : 
        my_table(const_cast<Container*>(&table)),
        my_node(b),
        my_array_index(array_index),
        my_segment_index(segment_index)
    {
        if( segment_index<my_table->n_segment ) {
            if( !my_node ) {
                segment &s = my_table->my_segment[segment_index];
                chain* first_chain = s.my_array;
                if( first_chain && my_array_index < s.my_physical_size)
                    my_node = first_chain[my_array_index].node_list;
            }
            if( !my_node ) advance_to_next_node();
        }
    }

    template<typename Container, typename Value>
    hash_map_iterator<Container,Value>& hash_map_iterator<Container,Value>::operator++() {
        my_node=my_node->next;
        if( !my_node ) advance_to_next_node();
        return *this;
    }

    template<typename Container, typename T, typename U>
    bool operator==( const hash_map_iterator<Container,T>& i, const hash_map_iterator<Container,U>& j ) {
        return i.my_node==j.my_node;
    }

    template<typename Container, typename T, typename U>
    bool operator!=( const hash_map_iterator<Container,T>& i, const hash_map_iterator<Container,U>& j ) {
        return i.my_node!=j.my_node;
    }


    template<typename Iterator>
    class hash_map_range {
    private:
        Iterator my_begin;
        Iterator my_end;
        mutable Iterator my_midpoint;
        size_t my_grainsize;
        void set_midpoint() const;
        template<typename U> friend class hash_map_range;
    public:
        typedef std::size_t size_type;
        typedef typename Iterator::value_type value_type;
        typedef typename Iterator::reference reference;
        typedef typename Iterator::difference_type difference_type;
        typedef Iterator iterator;

        bool empty() const {return my_begin==my_end;}

        bool is_divisible() const {
            return my_midpoint!=my_end;
        }
        hash_map_range( hash_map_range& r, split ) : 
            my_end(r.my_end),
            my_grainsize(r.my_grainsize)
        {
            r.my_end = my_begin = r.my_midpoint;
            __TBB_ASSERT( my_begin!=my_end, "Splitting despite the range is not divisible" );
            __TBB_ASSERT( r.my_begin!=r.my_end, "Splitting despite the range is not divisible" );
            set_midpoint();
            r.set_midpoint();
        }
        template<typename U>
        hash_map_range( hash_map_range<U>& r) : 
            my_begin(r.my_begin),
            my_end(r.my_end),
            my_midpoint(r.my_midpoint),
            my_grainsize(r.my_grainsize)
        {}
        hash_map_range( const Iterator& begin_, const Iterator& end_, size_type grainsize = 1 ) : 
            my_begin(begin_), 
            my_end(end_), 
            my_grainsize(grainsize) 
        {
            set_midpoint();
            __TBB_ASSERT( grainsize>0, "grainsize must be positive" );
        }
        const Iterator& begin() const {return my_begin;}
        const Iterator& end() const {return my_end;}
        size_type grainsize() const {return my_grainsize;}
    };

    template<typename Iterator>
    void hash_map_range<Iterator>::set_midpoint() const {
        size_t n = my_end.my_segment_index - my_begin.my_segment_index;
        if( n > 1 || (n == 1 && my_end.my_array_index > my_grainsize/2) ) {
            // Split by groups of segments
            my_midpoint = Iterator(*my_begin.my_table,(my_end.my_segment_index+my_begin.my_segment_index+1)/2u);
        } else {
            // Split by groups of nodes
            size_t m = my_end.my_array_index-my_begin.my_array_index;
            if( n ) m += my_begin.my_table->my_segment[my_begin.my_segment_index].my_physical_size;
            if( m > my_grainsize ) {
                my_midpoint = Iterator(*my_begin.my_table,my_begin.my_segment_index,my_begin.my_array_index + m/2u);
            } else {
                my_midpoint = my_end;
            }
        }
        __TBB_ASSERT( my_begin.my_segment_index < my_midpoint.my_segment_index
            || (my_begin.my_segment_index == my_midpoint.my_segment_index
            && my_begin.my_array_index <= my_midpoint.my_array_index),
            "my_begin is after my_midpoint" );
        __TBB_ASSERT( my_midpoint.my_segment_index < my_end.my_segment_index
            || (my_midpoint.my_segment_index == my_end.my_segment_index
            && my_midpoint.my_array_index <= my_end.my_array_index),
            "my_midpoint is after my_end" );
        __TBB_ASSERT( my_begin != my_midpoint || my_begin == my_end,
            "[my_begin, my_midpoint) range should not be empty" );
    }
    static const hashcode_t hash_multiplier = sizeof(hashcode_t)==4? 2654435769U : 11400714819323198485ULL;
    template<typename T>
    inline static hashcode_t hasher( const T& t ) {
        return static_cast<hashcode_t>( t ) * hash_multiplier;
    }
    template<typename P>
    inline static hashcode_t hasher( P* ptr ) {
        hashcode_t const h = reinterpret_cast<hashcode_t>( ptr );
        return (h >> 3) ^ h;
    }
    template<typename E, typename S, typename A>
    inline static hashcode_t hasher( const std::basic_string<E,S,A>& s ) {
        hashcode_t h = 0;
        for( const E* c = s.c_str(); *c; c++ )
            h = static_cast<hashcode_t>(*c) ^ (h * hash_multiplier);
        return h;
    }
    template<typename F, typename S>
    inline static hashcode_t hasher( const std::pair<F,S>& p ) {
        return hasher(p.first) ^ hasher(p.second);
    }
} // namespace internal

template<typename T>
struct tbb_hash_compare {
    static internal::hashcode_t hash( const T& t ) { return internal::hasher(t); }
    static bool equal( const T& a, const T& b ) { return a == b; }
};


template<typename Key, typename T, typename HashCompare, typename A>
class concurrent_hash_map : protected internal::hash_map_base {
    template<typename Container, typename Value>
    friend class internal::hash_map_iterator;

    template<typename I>
    friend class internal::hash_map_range;

    struct node;
    friend struct node;
    typedef typename A::template rebind<node>::other node_allocator_type;

public:
    class const_accessor;
    friend class const_accessor;
    class accessor;

    typedef Key key_type;
    typedef T mapped_type;
    typedef std::pair<const Key,T> value_type;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    typedef value_type *pointer;
    typedef const value_type *const_pointer;
    typedef value_type &reference;
    typedef const value_type &const_reference;
    typedef internal::hash_map_iterator<concurrent_hash_map,value_type> iterator;
    typedef internal::hash_map_iterator<concurrent_hash_map,const value_type> const_iterator;
    typedef internal::hash_map_range<iterator> range_type;
    typedef internal::hash_map_range<const_iterator> const_range_type;
    typedef A allocator_type;

    class const_accessor {
        friend class concurrent_hash_map<Key,T,HashCompare,A>;
        friend class accessor;
        void operator=( const accessor& ) const; // Deny access
        const_accessor( const accessor& );       // Deny access
    public:
        typedef const std::pair<const Key,T> value_type;

        bool empty() const {return !my_node;}

        void release() {
            if( my_node ) {
                my_lock.release();
                my_node = NULL;
            }
        }

        const_reference operator*() const {
            __TBB_ASSERT( my_node, "attempt to dereference empty accessor" );
            return my_node->item;
        }

        const_pointer operator->() const {
            return &operator*();
        }

        const_accessor() : my_node(NULL) {}

        ~const_accessor() {
            my_node = NULL; // my_lock.release() is called in scoped_lock destructor
        }
    private:
        node* my_node;
        node_mutex_t::scoped_lock my_lock;
        hashcode_t my_hash;
    };

    class accessor: public const_accessor {
    public:
        typedef std::pair<const Key,T> value_type;

        reference operator*() const {
            __TBB_ASSERT( this->my_node, "attempt to dereference empty accessor" );
            return this->my_node->item;
        }

        pointer operator->() const {
            return &operator*();
        }       
    };

    concurrent_hash_map(const allocator_type &a = allocator_type())
        : my_allocator(a)

    {
        initialize();
    }

    concurrent_hash_map( const concurrent_hash_map& table, const allocator_type &a = allocator_type())
        : my_allocator(a)
    {
        initialize();
        internal_copy(table);
    }

    template<typename I>
    concurrent_hash_map(I first, I last, const allocator_type &a = allocator_type())
        : my_allocator(a)
    {
        initialize();
        internal_copy(first, last);
    }

    concurrent_hash_map& operator=( const concurrent_hash_map& table ) {
        if( this!=&table ) {
            clear();
            internal_copy(table);
        } 
        return *this;
    }


    void clear();

    ~concurrent_hash_map();

    //------------------------------------------------------------------------
    // Parallel algorithm support
    //------------------------------------------------------------------------
    range_type range( size_type grainsize=1 ) {
        return range_type( begin(), end(), grainsize );
    }
    const_range_type range( size_type grainsize=1 ) const {
        return const_range_type( begin(), end(), grainsize );
    }

    //------------------------------------------------------------------------
    // STL support - not thread-safe methods
    //------------------------------------------------------------------------
    iterator begin() {return iterator(*this,0);}
    iterator end() {return iterator(*this,n_segment);}
    const_iterator begin() const {return const_iterator(*this,0);}
    const_iterator end() const {return const_iterator(*this,n_segment);}
    std::pair<iterator, iterator> equal_range( const Key& key ) { return internal_equal_range(key, end()); }
    std::pair<const_iterator, const_iterator> equal_range( const Key& key ) const { return internal_equal_range(key, end()); }
    

    size_type size() const;

    bool empty() const;

    size_type max_size() const {return (~size_type(0))/sizeof(node);}

    allocator_type get_allocator() const { return this->my_allocator; }

    void swap(concurrent_hash_map &table);

    //------------------------------------------------------------------------
    // concurrent map operations
    //------------------------------------------------------------------------

    size_type count( const Key& key ) const {
        return const_cast<concurrent_hash_map*>(this)->lookup</*insert*/false>(NULL, key, /*write=*/false, NULL );
    }


    bool find( const_accessor& result, const Key& key ) const {
        return const_cast<concurrent_hash_map*>(this)->lookup</*insert*/false>(&result, key, /*write=*/false, NULL );
    }


    bool find( accessor& result, const Key& key ) {
        return lookup</*insert*/false>(&result, key, /*write=*/true, NULL );
    }
        

    bool insert( const_accessor& result, const Key& key ) {
        return lookup</*insert*/true>(&result, key, /*write=*/false, NULL );
    }


    bool insert( accessor& result, const Key& key ) {
        return lookup</*insert*/true>(&result, key, /*write=*/true, NULL );
    }


    bool insert( const_accessor& result, const value_type& value ) {
        return lookup</*insert*/true>(&result, value.first, /*write=*/false, &value.second );
    }


    bool insert( accessor& result, const value_type& value ) {
        return lookup</*insert*/true>(&result, value.first, /*write=*/true, &value.second );
    }


    bool insert( const value_type& value ) {
        return lookup</*insert*/true>(NULL, value.first, /*write=*/false, &value.second );
    }

    template<typename I>
    void insert(I first, I last) {
        for(; first != last; ++first)
            insert( *first );
    }


    bool erase( const Key& key );


    bool erase( const_accessor& item_accessor ) {
        return exclude( item_accessor, /*readonly=*/ true );
    }


    bool erase( accessor& item_accessor ) {
        return exclude( item_accessor, /*readonly=*/ false );
    }

private:
    struct node: internal::no_copy {
        node* next;
        node_mutex_t mutex;
        value_type item;
        node( const Key& key ) : item(key, T()) {}
        node( const Key& key, const T& t ) : item(key, t) {}
        // exception-safe allocation, see C++ Standard 2003, clause 5.3.4p17
        void* operator new( size_t /*size*/, node_allocator_type& a ) {
            void *ptr = a.allocate(1);
            if(!ptr) throw std::bad_alloc();
            return ptr;
        }
        // match placement-new form above to be called if exception thrown in constructor
        void operator delete( void* ptr, node_allocator_type& a ) {return a.deallocate(static_cast<node*>(ptr),1); }
    };

    struct chain;
    friend struct chain;


    struct chain {
        void push_front( node& b ) {
            b.next = node_list;
            node_list = &b;
        }
        chain_mutex_t mutex;
        node* node_list;
    };

    struct segment;
    friend struct segment;


    struct segment: internal::hash_map_segment_base {
#if TBB_USE_ASSERT
        ~segment() {
            __TBB_ASSERT( !my_array, "should have been cleared earlier" );
        }
#endif /* TBB_USE_ASSERT */

        // Pointer to array of chains
        chain* my_array;

        // Get chain in this segment that corresponds to given hash code.
        chain& get_chain( hashcode_t hashcode, size_t n_segment_bits ) {
            return my_array[(hashcode>>n_segment_bits)&(my_physical_size-1)];
        }
     

        void allocate_array( size_t new_size ) {
            size_t n=(internal::NFS_GetLineSize()+sizeof(chain)-1)/sizeof(chain);
            __TBB_ASSERT((n&(n-1))==0, NULL);
            while( n<new_size ) n<<=1;
            chain* array = cache_aligned_allocator<chain>().allocate( n );
            // storing earlier might help overcome false positives of in deducing "bool grow" in concurrent threads
            __TBB_store_with_release(my_physical_size, n);
            std::memset( array, 0, n*sizeof(chain) );
            my_array = array;
        }
    };

    segment& get_segment( hashcode_t hashcode ) {
        return my_segment[hashcode&(n_segment-1)];
    }

    node_allocator_type my_allocator;

    HashCompare my_hash_compare;

    segment* my_segment;

    node* create_node(const Key& key, const T* t) {
        // exception-safe allocation and construction
        if(t) return new( my_allocator ) node(key, *t);
        else  return new( my_allocator ) node(key);
    }

    void delete_node(node* b) {
        my_allocator.destroy(b);
        my_allocator.deallocate(b, 1);
    }

    node* search_list( const Key& key, chain& c ) const {
        node* b = c.node_list;
        while( b && !my_hash_compare.equal(key, b->item.first) )
            b = b->next;
        return b;
    }
    template<typename I>
    std::pair<I, I> internal_equal_range( const Key& key, I end ) const;

    bool exclude( const_accessor& item_accessor, bool readonly );

    void grow_segment( segment_mutex_t::scoped_lock& segment_lock, segment& s );

    template<bool op_insert>
    bool lookup( const_accessor* result, const Key& key, bool write, const T* t );

    void initialize() {
        my_segment = cache_aligned_allocator<segment>().allocate(n_segment);
        std::memset( my_segment, 0, sizeof(segment)*n_segment );
     }

    void internal_copy( const concurrent_hash_map& source );

    template<typename I>
    void internal_copy(I first, I last);
};

template<typename Key, typename T, typename HashCompare, typename A>
concurrent_hash_map<Key,T,HashCompare,A>::~concurrent_hash_map() {
    clear();
    cache_aligned_allocator<segment>().deallocate( my_segment, n_segment );
}

template<typename Key, typename T, typename HashCompare, typename A>
typename concurrent_hash_map<Key,T,HashCompare,A>::size_type concurrent_hash_map<Key,T,HashCompare,A>::size() const {
    size_type result = 0;
    for( size_t k=0; k<n_segment; ++k )
        result += my_segment[k].my_logical_size;
    return result;
}

template<typename Key, typename T, typename HashCompare, typename A>
bool concurrent_hash_map<Key,T,HashCompare,A>::empty() const {
    for( size_t k=0; k<n_segment; ++k )
        if( my_segment[k].my_logical_size )
            return false;
    return true;
}

#if _MSC_VER && !defined(__INTEL_COMPILER)
    // Suppress "conditional expression is constant" warning.
    #pragma warning( push )
    #pragma warning( disable: 4127 )
#endif

template<typename Key, typename T, typename HashCompare, typename A>
template<bool op_insert>
bool concurrent_hash_map<Key,T,HashCompare,A>::lookup( const_accessor* result, const Key& key, bool write, const T* t ) {
    if( result )
        result->release();
    const hashcode_t h = my_hash_compare.hash( key );
    segment& s = get_segment(h);
restart:
    bool return_value = false;
    // first check in double-check sequence
#if TBB_USE_THREADING_TOOLS
    bool grow = op_insert && s.internal_grow_predicate();
#else
    bool grow = op_insert && s.my_logical_size >= s.my_physical_size
        && s.my_physical_size < max_physical_size; // check whether there are free bits
#endif /* TBB_USE_THREADING_TOOLS */
    segment_mutex_t::scoped_lock segment_lock( s.my_mutex, /*write=*/grow );
    if( grow ) { // Load factor is too high  
        grow_segment( segment_lock, s );
    }
    if( !s.my_array ) {
        __TBB_ASSERT( !op_insert, NULL );
        return false;
    }
    __TBB_ASSERT( (s.my_physical_size&(s.my_physical_size-1))==0, NULL );
    chain& c = s.get_chain( h, n_segment_bits );
    chain_mutex_t::scoped_lock chain_lock( c.mutex, /*write=*/false );

    node* b = search_list( key, c );
    if( op_insert ) {
        if( !b ) {
            b = create_node(key, t);
            // Search failed
            if( !chain_lock.upgrade_to_writer() ) {
                // Rerun search_list, in case another thread inserted the item during the upgrade.
                node* b_temp = search_list( key, c );
                if( b_temp ) { // unfortunately, it did
                    chain_lock.downgrade_to_reader();
                    delete_node( b );
                    b = b_temp;
                    goto done;
                }
            }
            ++s.my_logical_size; // we can't change it earlier due to correctness of size() and exception safety of equal()
            return_value = true;
            c.push_front( *b );
        }
    } else { // find or count
        if( !b )      return false;
        return_value = true;
    }
done:
    if( !result ) return return_value;
    if( !result->my_lock.try_acquire( b->mutex, write ) ) {
        // we are unlucky, prepare for longer wait
        internal::AtomicBackoff trials;
        do {
            if( !trials.bounded_pause() ) {
                // the wait takes really long, restart the operation
                chain_lock.release(); segment_lock.release();
                __TBB_Yield();
                goto restart;
            }
        } while( !result->my_lock.try_acquire( b->mutex, write ) );
    }
    result->my_node = b;
    result->my_hash = h;
    return return_value;
}

#if _MSC_VER && !defined(__INTEL_COMPILER)
    #pragma warning( pop )
#endif // warning 4127 is back

template<typename Key, typename T, typename HashCompare, typename A>
template<typename I>
std::pair<I, I> concurrent_hash_map<Key,T,HashCompare,A>::internal_equal_range( const Key& key, I end ) const {
    hashcode_t h = my_hash_compare.hash( key );
    size_t segment_index = h&(n_segment-1);
    segment& s = my_segment[segment_index ];
    size_t chain_index = (h>>n_segment_bits)&(s.my_physical_size-1);
    if( !s.my_array )
        return std::make_pair(end, end);
    chain& c = s.my_array[chain_index];
    node* b = search_list( key, c );
    if( !b )
        return std::make_pair(end, end);
    iterator lower(*this, segment_index, chain_index, b), upper(lower);
    return std::make_pair(lower, ++upper);
}

template<typename Key, typename T, typename HashCompare, typename A>
bool concurrent_hash_map<Key,T,HashCompare,A>::erase( const Key &key ) {
    hashcode_t h = my_hash_compare.hash( key );
    segment& s = get_segment( h );
    node* b=NULL; // explicitly initialized to prevent compiler warnings
    {
        bool chain_locked_for_write = false;
        segment_mutex_t::scoped_lock segment_lock( s.my_mutex, /*write=*/false );
        if( !s.my_array ) return false;
        __TBB_ASSERT( (s.my_physical_size&(s.my_physical_size-1))==0, NULL );
        chain& c = s.get_chain( h, n_segment_bits );
        chain_mutex_t::scoped_lock chain_lock( c.mutex, /*write=*/false );
    search:
        node** p = &c.node_list;
        b = *p;
        while( b && !my_hash_compare.equal(key, b->item.first ) ) {
            p = &b->next;
            b = *p;
        }
        if( !b ) return false;
        if( !chain_locked_for_write && !chain_lock.upgrade_to_writer() ) {
            chain_locked_for_write = true;
            goto search;
        }
        *p = b->next;
        --s.my_logical_size;
    }
    {
        node_mutex_t::scoped_lock item_locker( b->mutex, /*write=*/true );
    }
    // note: there should be no threads pretending to acquire this mutex again, do not try to upgrade const_accessor!
    delete_node( b ); // Only one thread can delete it due to write lock on the chain_mutex
    return true;        
}

template<typename Key, typename T, typename HashCompare, typename A>
bool concurrent_hash_map<Key,T,HashCompare,A>::exclude( const_accessor &item_accessor, bool readonly ) {
    __TBB_ASSERT( item_accessor.my_node, NULL );
    const hashcode_t h = item_accessor.my_hash;
    node *const b = item_accessor.my_node;
    item_accessor.my_node = NULL; // we ought release accessor anyway
    segment& s = get_segment( h );
    {
        segment_mutex_t::scoped_lock segment_lock( s.my_mutex, /*write=*/false );
        __TBB_ASSERT( s.my_array, NULL );
        __TBB_ASSERT( (s.my_physical_size&(s.my_physical_size-1))==0, NULL );
        chain& c = s.get_chain( h, n_segment_bits );
        chain_mutex_t::scoped_lock chain_lock( c.mutex, /*write=*/true );
        node** p = &c.node_list;
        while( *p && *p != b )
            p = &(*p)->next;
        if( !*p ) { // someone else was the first
            item_accessor.my_lock.release();
            return false;
        }
        __TBB_ASSERT( *p == b, NULL );
        *p = b->next;
        --s.my_logical_size;
    }
    if( readonly ) // need to get exclusive lock
        item_accessor.my_lock.upgrade_to_writer(); // return value means nothing here
    item_accessor.my_lock.release();
    delete_node( b ); // Only one thread can delete it due to write lock on the chain_mutex
    return true;
}

template<typename Key, typename T, typename HashCompare, typename A>
void concurrent_hash_map<Key,T,HashCompare,A>::swap(concurrent_hash_map<Key,T,HashCompare,A> &table) {
    std::swap(this->my_allocator, table.my_allocator);
    std::swap(this->my_hash_compare, table.my_hash_compare);
    std::swap(this->my_segment, table.my_segment);
}

template<typename Key, typename T, typename HashCompare, typename A>
void concurrent_hash_map<Key,T,HashCompare,A>::clear() {
#if TBB_USE_PERFORMANCE_WARNINGS
    size_t total_physical_size = 0, min_physical_size = size_t(-1L), max_physical_size = 0; //< usage statistics
    static bool reported = false;
#endif
    for( size_t i=0; i<n_segment; ++i ) {
        segment& s = my_segment[i];
        size_t n = s.my_physical_size;
        if( chain* array = s.my_array ) {
            s.my_array = NULL;
            s.my_physical_size = 0;
            s.my_logical_size = 0;
            for( size_t j=0; j<n; ++j ) {
                while( node* b = array[j].node_list ) {
                    array[j].node_list = b->next;
                    delete_node(b);
                }
            }
            cache_aligned_allocator<chain>().deallocate( array, n );
        }
#if TBB_USE_PERFORMANCE_WARNINGS
        total_physical_size += n;
        if(min_physical_size > n) min_physical_size = n;
        if(max_physical_size < n) max_physical_size = n;
    }
    if( !reported
        && ( (total_physical_size >= n_segment*48 && min_physical_size < total_physical_size/n_segment/2)
         || (total_physical_size >= n_segment*128 && max_physical_size > total_physical_size/n_segment*2) ) )
    {
        reported = true;
        internal::runtime_warning(
            "Performance is not optimal because the hash function produces bad randomness in lower bits in %s",
            typeid(*this).name() );
#endif
    }
}

template<typename Key, typename T, typename HashCompare, typename A>
void concurrent_hash_map<Key,T,HashCompare,A>::grow_segment( segment_mutex_t::scoped_lock& segment_lock, segment& s ) {
    // Following is second check in a double-check.
    if( s.my_logical_size >= s.my_physical_size ) {
        chain* old_array = s.my_array;
        size_t old_size = s.my_physical_size;
        s.allocate_array( s.my_logical_size+1 );
        for( size_t k=0; k<old_size; ++k )
            while( node* b = old_array[k].node_list ) {
                old_array[k].node_list = b->next;
                hashcode_t h = my_hash_compare.hash( b->item.first );
                __TBB_ASSERT( &get_segment(h)==&s, "hash function changed?" );
                s.get_chain(h,n_segment_bits).push_front(*b);
            }
        cache_aligned_allocator<chain>().deallocate( old_array, old_size );
    }
    segment_lock.downgrade_to_reader();
}

template<typename Key, typename T, typename HashCompare, typename A>
void concurrent_hash_map<Key,T,HashCompare,A>::internal_copy( const concurrent_hash_map& source ) {
    for( size_t i=0; i<n_segment; ++i ) {
        segment& s = source.my_segment[i];
        __TBB_ASSERT( !my_segment[i].my_array, "caller should have cleared" );
        if( s.my_logical_size ) {
            segment& d = my_segment[i];
            d.allocate_array( s.my_logical_size );
            d.my_logical_size = s.my_logical_size;
            size_t s_size = s.my_physical_size;
            chain* s_array = s.my_array;
            chain* d_array = d.my_array;
            for( size_t k=0; k<s_size; ++k )
                for( node* b = s_array[k].node_list; b; b=b->next ) {
                    __TBB_ASSERT( &get_segment(my_hash_compare.hash( b->item.first ))==&d, "hash function changed?" );
                    node* b_new = create_node(b->item.first, &b->item.second);
                    d_array[k].push_front(*b_new); // hashcode is the same and segment and my_physical sizes are the same
                }
        }
    }
}

template<typename Key, typename T, typename HashCompare, typename A>
template<typename I>
void concurrent_hash_map<Key,T,HashCompare,A>::internal_copy(I first, I last) {
    for(; first != last; ++first)
        insert( *first );
}

template<typename Key, typename T, typename HashCompare, typename A1, typename A2>
inline bool operator==(const concurrent_hash_map<Key, T, HashCompare, A1> &a, const concurrent_hash_map<Key, T, HashCompare, A2> &b) {
    if(a.size() != b.size()) return false;
    typename concurrent_hash_map<Key, T, HashCompare, A1>::const_iterator i(a.begin()), i_end(a.end());
    typename concurrent_hash_map<Key, T, HashCompare, A2>::const_iterator j, j_end(b.end());
    for(; i != i_end; ++i) {
        j = b.equal_range(i->first).first;
        if( j == j_end || !(i->second == j->second) ) return false;
    }
    return true;
}

template<typename Key, typename T, typename HashCompare, typename A1, typename A2>
inline bool operator!=(const concurrent_hash_map<Key, T, HashCompare, A1> &a, const concurrent_hash_map<Key, T, HashCompare, A2> &b)
{    return !(a == b); }

template<typename Key, typename T, typename HashCompare, typename A>
inline void swap(concurrent_hash_map<Key, T, HashCompare, A> &a, concurrent_hash_map<Key, T, HashCompare, A> &b)
{    a.swap( b ); }

} // namespace tbb

#endif /* __TBB_concurrent_hash_map_H */

---

Copyright © 2005-2009 Intel Corporation. All Rights Reserved.

Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are registered trademarks or trademarks of Intel Corporation or its subsidiaries in the United States and other countries.

* Other names and brands may be claimed as the property of others.