src/parsec/disk-image/parsec/parsec-benchmark/pkgs/libs/tbblib/src/doc/html/a00325.html - public/gem5-resources - Git at Google

 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
 <html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
 <title>concurrent_hash_map.h Source File</title>
 <link href="doxygen.css" rel="stylesheet" type="text/css">
 <link href="tabs.css" rel="stylesheet" type="text/css">
 </head><body>
 <!-- Generated by Doxygen 1.4.7 -->
 <div class="tabs">
   <ul>
     <li><a href="index.html"><span>Main&nbsp;Page</span></a></li>
     <li><a href="modules.html"><span>Modules</span></a></li>
     <li><a href="namespaces.html"><span>Namespaces</span></a></li>
     <li><a href="annotated.html"><span>Classes</span></a></li>
     <li id="current"><a href="files.html"><span>Files</span></a></li>
     <li><a href="pages.html"><span>Related&nbsp;Pages</span></a></li>
   </ul></div>
 <div class="tabs">
   <ul>
     <li><a href="files.html"><span>File&nbsp;List</span></a></li>
     <li><a href="globals.html"><span>File&nbsp;Members</span></a></li>
   </ul></div>
 <h1>concurrent_hash_map.h</h1><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">/*</span>
 <a name="l00002"></a>00002 <span class="comment">    Copyright 2005-2010 Intel Corporation.  All Rights Reserved.</span>
 <a name="l00003"></a>00003 <span class="comment"></span>
 <a name="l00004"></a>00004 <span class="comment">    The source code contained or described herein and all documents related</span>
 <a name="l00005"></a>00005 <span class="comment">    to the source code ("Material") are owned by Intel Corporation or its</span>
 <a name="l00006"></a>00006 <span class="comment">    suppliers or licensors.  Title to the Material remains with Intel</span>
 <a name="l00007"></a>00007 <span class="comment">    Corporation or its suppliers and licensors.  The Material is protected</span>
 <a name="l00008"></a>00008 <span class="comment">    by worldwide copyright laws and treaty provisions.  No part of the</span>
 <a name="l00009"></a>00009 <span class="comment">    Material may be used, copied, reproduced, modified, published, uploaded,</span>
 <a name="l00010"></a>00010 <span class="comment">    posted, transmitted, distributed, or disclosed in any way without</span>
 <a name="l00011"></a>00011 <span class="comment">    Intel's prior express written permission.</span>
 <a name="l00012"></a>00012 <span class="comment"></span>
 <a name="l00013"></a>00013 <span class="comment">    No license under any patent, copyright, trade secret or other</span>
 <a name="l00014"></a>00014 <span class="comment">    intellectual property right is granted to or conferred upon you by</span>
 <a name="l00015"></a>00015 <span class="comment">    disclosure or delivery of the Materials, either expressly, by</span>
 <a name="l00016"></a>00016 <span class="comment">    implication, inducement, estoppel or otherwise.  Any license under such</span>
 <a name="l00017"></a>00017 <span class="comment">    intellectual property rights must be express and approved by Intel in</span>
 <a name="l00018"></a>00018 <span class="comment">    writing.</span>
 <a name="l00019"></a>00019 <span class="comment">*/</span>
 <a name="l00020"></a>00020
 <a name="l00021"></a>00021 <span class="preprocessor">#ifndef __TBB_concurrent_hash_map_H</span>
 <a name="l00022"></a>00022 <span class="preprocessor"></span><span class="preprocessor">#define __TBB_concurrent_hash_map_H</span>
 <a name="l00023"></a>00023 <span class="preprocessor"></span>
 <a name="l00024"></a>00024 <span class="preprocessor">#include "tbb_stddef.h"</span>
 <a name="l00025"></a>00025
 <a name="l00026"></a>00026 <span class="preprocessor">#if !TBB_USE_EXCEPTIONS &amp;&amp; _MSC_VER</span>
 <a name="l00027"></a>00027 <span class="preprocessor"></span>    <span class="comment">// Suppress "C++ exception handler used, but unwind semantics are not enabled" warning in STL headers</span>
 <a name="l00028"></a>00028 <span class="preprocessor">    #pragma warning (push)</span>
 <a name="l00029"></a>00029 <span class="preprocessor"></span><span class="preprocessor">    #pragma warning (disable: 4530)</span>
 <a name="l00030"></a>00030 <span class="preprocessor"></span><span class="preprocessor">#endif</span>
 <a name="l00031"></a>00031 <span class="preprocessor"></span>
 <a name="l00032"></a>00032 <span class="preprocessor">#include &lt;iterator&gt;</span>
 <a name="l00033"></a>00033 <span class="preprocessor">#include &lt;utility&gt;</span>      <span class="comment">// Need std::pair</span>
 <a name="l00034"></a>00034 <span class="preprocessor">#include &lt;cstring&gt;</span>      <span class="comment">// Need std::memset</span>
 <a name="l00035"></a>00035
 <a name="l00036"></a>00036 <span class="preprocessor">#if !TBB_USE_EXCEPTIONS &amp;&amp; _MSC_VER</span>
 <a name="l00037"></a>00037 <span class="preprocessor"></span><span class="preprocessor">    #pragma warning (pop)</span>
 <a name="l00038"></a>00038 <span class="preprocessor"></span><span class="preprocessor">#endif</span>
 <a name="l00039"></a>00039 <span class="preprocessor"></span>
 <a name="l00040"></a>00040 <span class="preprocessor">#include "cache_aligned_allocator.h"</span>
 <a name="l00041"></a>00041 <span class="preprocessor">#include "tbb_allocator.h"</span>
 <a name="l00042"></a>00042 <span class="preprocessor">#include "spin_rw_mutex.h"</span>
 <a name="l00043"></a>00043 <span class="preprocessor">#include "atomic.h"</span>
 <a name="l00044"></a>00044 <span class="preprocessor">#include "aligned_space.h"</span>
 <a name="l00045"></a>00045 <span class="preprocessor">#include "tbb_exception.h"</span>
 <a name="l00046"></a>00046 <span class="preprocessor">#include "_concurrent_unordered_internal.h"</span> <span class="comment">// Need tbb_hasher</span>
 <a name="l00047"></a>00047 <span class="preprocessor">#if TBB_USE_PERFORMANCE_WARNINGS</span>
 <a name="l00048"></a>00048 <span class="preprocessor"></span><span class="preprocessor">#include &lt;typeinfo&gt;</span>
 <a name="l00049"></a>00049 <span class="preprocessor">#endif</span>
 <a name="l00050"></a>00050 <span class="preprocessor"></span>
 <a name="l00051"></a>00051 <span class="keyword">namespace </span>tbb {
 <a name="l00052"></a>00052
 <a name="l00054"></a>00054 <span class="keyword">namespace </span>internal {
 <a name="l00056"></a>00056     <span class="keywordtype">void</span>* __TBB_EXPORTED_FUNC itt_load_pointer_with_acquire_v3( <span class="keyword">const</span> <span class="keywordtype">void</span>* src );
 <a name="l00058"></a>00058     <span class="keywordtype">void</span> __TBB_EXPORTED_FUNC itt_store_pointer_with_release_v3( <span class="keywordtype">void</span>* dst, <span class="keywordtype">void</span>* src );
 <a name="l00060"></a>00060     <span class="keywordtype">void</span>* __TBB_EXPORTED_FUNC itt_load_pointer_v3( <span class="keyword">const</span> <span class="keywordtype">void</span>* src );
 <a name="l00061"></a>00061 }
 <a name="l00063"></a>00063
 <a name="l00065"></a>00065 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Key&gt;
 <a name="l00066"></a><a class="code" href="a00208.html">00066</a> <span class="keyword">struct </span><a class="code" href="a00208.html">tbb_hash_compare</a> {
 <a name="l00067"></a>00067     <span class="keyword">static</span> size_t hash( <span class="keyword">const</span> Key&amp; a ) { <span class="keywordflow">return</span> tbb_hasher(a); }
 <a name="l00068"></a>00068     <span class="keyword">static</span> <span class="keywordtype">bool</span> equal( <span class="keyword">const</span> Key&amp; a, <span class="keyword">const</span> Key&amp; b ) { <span class="keywordflow">return</span> a == b; }
 <a name="l00069"></a>00069 };
 <a name="l00070"></a>00070
 <a name="l00071"></a>00071 <span class="keyword">namespace </span>interface4 {
 <a name="l00072"></a>00072
 <a name="l00073"></a>00073     <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Key, <span class="keyword">typename</span> T, <span class="keyword">typename</span> HashCompare = tbb_hash_compare&lt;Key&gt;, <span class="keyword">typename</span> A = tbb_allocator&lt;std::pair&lt;Key, T&gt; &gt; &gt;
 <a name="l00074"></a>00074     <span class="keyword">class </span><a class="code" href="a00156.html">concurrent_hash_map</a>;
 <a name="l00075"></a>00075
 <a name="l00077"></a>00077     <span class="keyword">namespace </span>internal {
 <a name="l00078"></a>00078
 <a name="l00079"></a>00079
 <a name="l00081"></a>00081     <span class="keyword">typedef</span> size_t hashcode_t;
 <a name="l00083"></a>00083     <span class="keyword">struct </span>hash_map_node_base : tbb::internal::no_copy {
 <a name="l00085"></a>00085         <span class="keyword">typedef</span> <a class="code" href="a00196.html">spin_rw_mutex</a> mutex_t;
 <a name="l00087"></a>00087         <span class="keyword">typedef</span> mutex_t::scoped_lock scoped_t;
 <a name="l00089"></a>00089         hash_map_node_base *next;
 <a name="l00090"></a>00090         mutex_t <a class="code" href="a00172.html">mutex</a>;
 <a name="l00091"></a>00091     };
 <a name="l00093"></a>00093     <span class="keyword">static</span> hash_map_node_base *<span class="keyword">const</span> rehash_req = reinterpret_cast&lt;hash_map_node_base*&gt;(size_t(3));
 <a name="l00095"></a>00095     <span class="keyword">static</span> hash_map_node_base *<span class="keyword">const</span> empty_rehashed = reinterpret_cast&lt;hash_map_node_base*&gt;(size_t(0));
 <a name="l00097"></a>00097     <span class="keyword">class </span>hash_map_base {
 <a name="l00098"></a>00098     <span class="keyword">public</span>:
 <a name="l00100"></a>00100         <span class="keyword">typedef</span> size_t size_type;
 <a name="l00102"></a>00102         <span class="keyword">typedef</span> size_t hashcode_t;
 <a name="l00104"></a>00104         <span class="keyword">typedef</span> size_t segment_index_t;
 <a name="l00106"></a>00106         <span class="keyword">typedef</span> hash_map_node_base node_base;
 <a name="l00108"></a>00108         <span class="keyword">struct </span>bucket : tbb::internal::no_copy {
 <a name="l00110"></a>00110             <span class="keyword">typedef</span> spin_rw_mutex mutex_t;
 <a name="l00112"></a>00112             <span class="keyword">typedef</span> mutex_t::scoped_lock scoped_t;
 <a name="l00113"></a>00113             mutex_t mutex;
 <a name="l00114"></a>00114             node_base *node_list;
 <a name="l00115"></a>00115         };
 <a name="l00117"></a>00117         <span class="keyword">static</span> size_type <span class="keyword">const</span> embedded_block = 1;
 <a name="l00119"></a>00119         <span class="keyword">static</span> size_type <span class="keyword">const</span> embedded_buckets = 1&lt;&lt;embedded_block;
 <a name="l00121"></a>00121         <span class="keyword">static</span> size_type <span class="keyword">const</span> first_block = 8; <span class="comment">//including embedded_block. perfect with bucket size 16, so the allocations are power of 4096</span>
 <a name="l00123"></a>00123 <span class="comment"></span>        <span class="keyword">static</span> size_type <span class="keyword">const</span> pointers_per_table = <span class="keyword">sizeof</span>(segment_index_t) * 8; <span class="comment">// one segment per bit</span>
 <a name="l00125"></a>00125 <span class="comment"></span>        <span class="keyword">typedef</span> bucket *segment_ptr_t;
 <a name="l00127"></a>00127         <span class="keyword">typedef</span> segment_ptr_t segments_table_t[pointers_per_table];
 <a name="l00129"></a>00129         atomic&lt;hashcode_t&gt; my_mask;
 <a name="l00131"></a>00131         segments_table_t my_table;
 <a name="l00133"></a>00133         atomic&lt;size_type&gt; my_size; <span class="comment">// It must be in separate cache line from my_mask due to performance effects</span>
 <a name="l00135"></a>00135 <span class="comment"></span>        bucket my_embedded_segment[embedded_buckets];
 <a name="l00136"></a>00136
 <a name="l00138"></a>00138         hash_map_base() {
 <a name="l00139"></a>00139             std::memset( <span class="keyword">this</span>, 0, pointers_per_table*<span class="keyword">sizeof</span>(segment_ptr_t) <span class="comment">// 32*4=128   or 64*8=512</span>
 <a name="l00140"></a>00140                 + <span class="keyword">sizeof</span>(my_size) + <span class="keyword">sizeof</span>(my_mask)  <span class="comment">// 4+4 or 8+8</span>
 <a name="l00141"></a>00141                 + embedded_buckets*<span class="keyword">sizeof</span>(bucket) ); <span class="comment">// n*8 or n*16</span>
 <a name="l00142"></a>00142             <span class="keywordflow">for</span>( size_type i = 0; i &lt; embedded_block; i++ ) <span class="comment">// fill the table</span>
 <a name="l00143"></a>00143                 my_table[i] = my_embedded_segment + segment_base(i);
 <a name="l00144"></a>00144             my_mask = embedded_buckets - 1;
 <a name="l00145"></a>00145             __TBB_ASSERT( embedded_block &lt;= first_block, <span class="stringliteral">"The first block number must include embedded blocks"</span>);
 <a name="l00146"></a>00146         }
 <a name="l00147"></a>00147
 <a name="l00149"></a>00149         <span class="keyword">static</span> segment_index_t segment_index_of( size_type index ) {
 <a name="l00150"></a>00150             <span class="keywordflow">return</span> segment_index_t( __TBB_Log2( index|1 ) );
 <a name="l00151"></a>00151         }
 <a name="l00152"></a>00152
 <a name="l00154"></a>00154         <span class="keyword">static</span> segment_index_t segment_base( segment_index_t k ) {
 <a name="l00155"></a>00155             <span class="keywordflow">return</span> (segment_index_t(1)&lt;&lt;k &amp; ~segment_index_t(1));
 <a name="l00156"></a>00156         }
 <a name="l00157"></a>00157
 <a name="l00159"></a>00159         <span class="keyword">static</span> size_type segment_size( segment_index_t k ) {
 <a name="l00160"></a>00160             <span class="keywordflow">return</span> size_type(1)&lt;&lt;k; <span class="comment">// fake value for k==0</span>
 <a name="l00161"></a>00161         }
 <a name="l00162"></a>00162
 <a name="l00164"></a>00164         <span class="keyword">static</span> <span class="keywordtype">bool</span> is_valid( <span class="keywordtype">void</span> *ptr ) {
 <a name="l00165"></a>00165             <span class="keywordflow">return</span> reinterpret_cast&lt;size_t&gt;(ptr) &gt; size_t(63);
 <a name="l00166"></a>00166         }
 <a name="l00167"></a>00167
 <a name="l00169"></a>00169         <span class="keyword">static</span> <span class="keywordtype">void</span> init_buckets( segment_ptr_t ptr, size_type sz, <span class="keywordtype">bool</span> is_initial ) {
 <a name="l00170"></a>00170             <span class="keywordflow">if</span>( is_initial ) std::memset(ptr, 0, sz*<span class="keyword">sizeof</span>(bucket) );
 <a name="l00171"></a>00171             <span class="keywordflow">else</span> <span class="keywordflow">for</span>(size_type i = 0; i &lt; sz; i++, ptr++) {
 <a name="l00172"></a>00172                     *reinterpret_cast&lt;intptr_t*&gt;(&amp;ptr-&gt;mutex) = 0;
 <a name="l00173"></a>00173                     ptr-&gt;node_list = rehash_req;
 <a name="l00174"></a>00174                 }
 <a name="l00175"></a>00175         }
 <a name="l00176"></a>00176
 <a name="l00178"></a>00178         <span class="keyword">static</span> <span class="keywordtype">void</span> add_to_bucket( bucket *b, node_base *n ) {
 <a name="l00179"></a>00179             __TBB_ASSERT(b-&gt;node_list != rehash_req, NULL);
 <a name="l00180"></a>00180             n-&gt;next = b-&gt;node_list;
 <a name="l00181"></a>00181             b-&gt;node_list = n; <span class="comment">// its under lock and flag is set</span>
 <a name="l00182"></a>00182         }
 <a name="l00183"></a>00183
 <a name="l00185"></a>00185         <span class="keyword">struct </span>enable_segment_failsafe {
 <a name="l00186"></a>00186             segment_ptr_t *my_segment_ptr;
 <a name="l00187"></a>00187             enable_segment_failsafe(segments_table_t &amp;table, segment_index_t k) : my_segment_ptr(&amp;table[k]) {}
 <a name="l00188"></a>00188             ~enable_segment_failsafe() {
 <a name="l00189"></a>00189                 <span class="keywordflow">if</span>( my_segment_ptr ) *my_segment_ptr = 0; <span class="comment">// indicate no allocation in progress</span>
 <a name="l00190"></a>00190             }
 <a name="l00191"></a>00191         };
 <a name="l00192"></a>00192
 <a name="l00194"></a>00194         <span class="keywordtype">void</span> enable_segment( segment_index_t k, <span class="keywordtype">bool</span> is_initial = <span class="keyword">false</span> ) {
 <a name="l00195"></a>00195             __TBB_ASSERT( k, <span class="stringliteral">"Zero segment must be embedded"</span> );
 <a name="l00196"></a>00196             enable_segment_failsafe watchdog( my_table, k );
 <a name="l00197"></a>00197             cache_aligned_allocator&lt;bucket&gt; alloc;
 <a name="l00198"></a>00198             size_type sz;
 <a name="l00199"></a>00199             __TBB_ASSERT( !is_valid(my_table[k]), <span class="stringliteral">"Wrong concurrent assignment"</span>);
 <a name="l00200"></a>00200             <span class="keywordflow">if</span>( k &gt;= first_block ) {
 <a name="l00201"></a>00201                 sz = segment_size( k );
 <a name="l00202"></a>00202                 segment_ptr_t ptr = alloc.allocate( sz );
 <a name="l00203"></a>00203                 init_buckets( ptr, sz, is_initial );
 <a name="l00204"></a>00204 <span class="preprocessor">#if TBB_USE_THREADING_TOOLS</span>
 <a name="l00205"></a>00205 <span class="preprocessor"></span>                <span class="comment">// TODO: actually, fence and notification are unnecessary here and below</span>
 <a name="l00206"></a>00206                 itt_store_pointer_with_release_v3( my_table + k, ptr );
 <a name="l00207"></a>00207 <span class="preprocessor">#else</span>
 <a name="l00208"></a>00208 <span class="preprocessor"></span>                my_table[k] = ptr;<span class="comment">// my_mask has release fence</span>
 <a name="l00209"></a>00209 <span class="preprocessor">#endif</span>
 <a name="l00210"></a>00210 <span class="preprocessor"></span>                sz &lt;&lt;= 1;<span class="comment">// double it to get entire capacity of the container</span>
 <a name="l00211"></a>00211             } <span class="keywordflow">else</span> { <span class="comment">// the first block</span>
 <a name="l00212"></a>00212                 __TBB_ASSERT( k == embedded_block, <span class="stringliteral">"Wrong segment index"</span> );
 <a name="l00213"></a>00213                 sz = segment_size( first_block );
 <a name="l00214"></a>00214                 segment_ptr_t ptr = alloc.allocate( sz - embedded_buckets );
 <a name="l00215"></a>00215                 init_buckets( ptr, sz - embedded_buckets, is_initial );
 <a name="l00216"></a>00216                 ptr -= segment_base(embedded_block);
 <a name="l00217"></a>00217                 <span class="keywordflow">for</span>(segment_index_t i = embedded_block; i &lt; first_block; i++) <span class="comment">// calc the offsets</span>
 <a name="l00218"></a>00218 #<span class="keywordflow">if</span> TBB_USE_THREADING_TOOLS
 <a name="l00219"></a>00219                     itt_store_pointer_with_release_v3( my_table + i, ptr + segment_base(i) );
 <a name="l00220"></a>00220 <span class="preprocessor">#else</span>
 <a name="l00221"></a>00221 <span class="preprocessor"></span>                    my_table[i] = ptr + segment_base(i);
 <a name="l00222"></a>00222 <span class="preprocessor">#endif</span>
 <a name="l00223"></a>00223 <span class="preprocessor"></span>            }
 <a name="l00224"></a>00224 <span class="preprocessor">#if TBB_USE_THREADING_TOOLS</span>
 <a name="l00225"></a>00225 <span class="preprocessor"></span>            itt_store_pointer_with_release_v3( &amp;my_mask, (<span class="keywordtype">void</span>*)(sz-1) );
 <a name="l00226"></a>00226 <span class="preprocessor">#else</span>
 <a name="l00227"></a>00227 <span class="preprocessor"></span>            my_mask = sz - 1;
 <a name="l00228"></a>00228 <span class="preprocessor">#endif</span>
 <a name="l00229"></a>00229 <span class="preprocessor"></span>            watchdog.my_segment_ptr = 0;
 <a name="l00230"></a>00230         }
 <a name="l00231"></a>00231
 <a name="l00233"></a>00233         bucket *get_bucket( hashcode_t h ) <span class="keyword">const</span> <span class="keywordflow">throw</span>() { <span class="comment">// TODO: add throw() everywhere?</span>
 <a name="l00234"></a>00234             segment_index_t s = segment_index_of( h );
 <a name="l00235"></a>00235             h -= segment_base(s);
 <a name="l00236"></a>00236             segment_ptr_t seg = my_table[s];
 <a name="l00237"></a>00237             __TBB_ASSERT( is_valid(seg), <span class="stringliteral">"hashcode must be cut by valid mask for allocated segments"</span> );
 <a name="l00238"></a>00238             <span class="keywordflow">return</span> &amp;seg[h];
 <a name="l00239"></a>00239         }
 <a name="l00240"></a>00240
 <a name="l00241"></a>00241         <span class="comment">// internal serial rehashing helper</span>
 <a name="l00242"></a>00242         <span class="keywordtype">void</span> mark_rehashed_levels( hashcode_t h ) <span class="keywordflow">throw</span> () {
 <a name="l00243"></a>00243             segment_index_t s = segment_index_of( h );
 <a name="l00244"></a>00244             <span class="keywordflow">while</span>( segment_ptr_t seg = my_table[++s] )
 <a name="l00245"></a>00245                 <span class="keywordflow">if</span>( seg[h].node_list == rehash_req ) {
 <a name="l00246"></a>00246                     seg[h].node_list = empty_rehashed;
 <a name="l00247"></a>00247                     mark_rehashed_levels( h + segment_base(s) );
 <a name="l00248"></a>00248                 }
 <a name="l00249"></a>00249         }
 <a name="l00250"></a>00250
 <a name="l00252"></a>00252         <span class="comment">// Splitting into two functions should help inlining</span>
 <a name="l00253"></a>00253         <span class="keyword">inline</span> <span class="keywordtype">bool</span> check_mask_race( <span class="keyword">const</span> hashcode_t h, hashcode_t &amp;m )<span class="keyword"> const </span>{
 <a name="l00254"></a>00254             hashcode_t m_now, m_old = m;
 <a name="l00255"></a>00255 <span class="preprocessor">#if TBB_USE_THREADING_TOOLS</span>
 <a name="l00256"></a>00256 <span class="preprocessor"></span>            m_now = (hashcode_t) itt_load_pointer_with_acquire_v3( &amp;my_mask );
 <a name="l00257"></a>00257 <span class="preprocessor">#else</span>
 <a name="l00258"></a>00258 <span class="preprocessor"></span>            m_now = my_mask;
 <a name="l00259"></a>00259 <span class="preprocessor">#endif</span>
 <a name="l00260"></a>00260 <span class="preprocessor"></span>            <span class="keywordflow">if</span>( m_old != m_now )
 <a name="l00261"></a>00261                 <span class="keywordflow">return</span> check_rehashing_collision( h, m_old, m = m_now );
 <a name="l00262"></a>00262             <span class="keywordflow">return</span> <span class="keyword">false</span>;
 <a name="l00263"></a>00263         }
 <a name="l00264"></a>00264
 <a name="l00266"></a>00266         <span class="keywordtype">bool</span> check_rehashing_collision( <span class="keyword">const</span> hashcode_t h, hashcode_t m_old, hashcode_t m )<span class="keyword"> const </span>{
 <a name="l00267"></a>00267             __TBB_ASSERT(m_old != m, NULL); <span class="comment">// TODO?: m arg could be optimized out by passing h = h&amp;m</span>
 <a name="l00268"></a>00268             <span class="keywordflow">if</span>( (h &amp; m_old) != (h &amp; m) ) { <span class="comment">// mask changed for this hashcode, rare event</span>
 <a name="l00269"></a>00269                 <span class="comment">// condition above proves that 'h' has some other bits set beside 'm_old'</span>
 <a name="l00270"></a>00270                 <span class="comment">// find next applicable mask after m_old    //TODO: look at bsl instruction</span>
 <a name="l00271"></a>00271                 <span class="keywordflow">for</span>( ++m_old; !(h &amp; m_old); m_old &lt;&lt;= 1 ) <span class="comment">// at maximum few rounds depending on the first block size</span>
 <a name="l00272"></a>00272                     ;
 <a name="l00273"></a>00273                 m_old = (m_old&lt;&lt;1) - 1; <span class="comment">// get full mask from a bit</span>
 <a name="l00274"></a>00274                 __TBB_ASSERT((m_old&amp;(m_old+1))==0 &amp;&amp; m_old &lt;= m, NULL);
 <a name="l00275"></a>00275                 <span class="comment">// check whether it is rehashing/ed</span>
 <a name="l00276"></a>00276 <span class="preprocessor">#if TBB_USE_THREADING_TOOLS</span>
 <a name="l00277"></a>00277 <span class="preprocessor"></span>                <span class="keywordflow">if</span>( itt_load_pointer_with_acquire_v3(&amp;( get_bucket(h &amp; m_old)-&gt;node_list )) != rehash_req )
 <a name="l00278"></a>00278 <span class="preprocessor">#else</span>
 <a name="l00279"></a>00279 <span class="preprocessor"></span>                <span class="keywordflow">if</span>( __TBB_load_with_acquire(get_bucket( h &amp; m_old )-&gt;node_list) != rehash_req )
 <a name="l00280"></a>00280 <span class="preprocessor">#endif</span>
 <a name="l00281"></a>00281 <span class="preprocessor"></span>                    <span class="keywordflow">return</span> <span class="keyword">true</span>;
 <a name="l00282"></a>00282             }
 <a name="l00283"></a>00283             <span class="keywordflow">return</span> <span class="keyword">false</span>;
 <a name="l00284"></a>00284         }
 <a name="l00285"></a>00285
 <a name="l00287"></a>00287         segment_index_t insert_new_node( bucket *b, node_base *n, hashcode_t mask ) {
 <a name="l00288"></a>00288             size_type sz = ++my_size; <span class="comment">// prefix form is to enforce allocation after the first item inserted</span>
 <a name="l00289"></a>00289             add_to_bucket( b, n );
 <a name="l00290"></a>00290             <span class="comment">// check load factor</span>
 <a name="l00291"></a>00291             <span class="keywordflow">if</span>( sz &gt;= mask ) { <span class="comment">// TODO: add custom load_factor </span>
 <a name="l00292"></a>00292                 segment_index_t new_seg = segment_index_of( mask+1 );
 <a name="l00293"></a>00293                 __TBB_ASSERT( is_valid(my_table[new_seg-1]), <span class="stringliteral">"new allocations must not publish new mask until segment has allocated"</span>);
 <a name="l00294"></a>00294 <span class="preprocessor">#if TBB_USE_THREADING_TOOLS</span>
 <a name="l00295"></a>00295 <span class="preprocessor"></span>                <span class="keywordflow">if</span>( !itt_load_pointer_v3(my_table+new_seg)
 <a name="l00296"></a>00296 #<span class="keywordflow">else</span>
 <a name="l00297"></a>00297                 <span class="keywordflow">if</span>( !my_table[new_seg]
 <a name="l00298"></a>00298 #endif
 <a name="l00299"></a>00299                   &amp;&amp; __TBB_CompareAndSwapW(&amp;my_table[new_seg], 2, 0) == 0 )
 <a name="l00300"></a>00300                     <span class="keywordflow">return</span> new_seg; <span class="comment">// The value must be processed</span>
 <a name="l00301"></a>00301             }
 <a name="l00302"></a>00302             <span class="keywordflow">return</span> 0;
 <a name="l00303"></a>00303         }
 <a name="l00304"></a>00304
 <a name="l00306"></a>00306         <span class="keywordtype">void</span> reserve(size_type buckets) {
 <a name="l00307"></a>00307             <span class="keywordflow">if</span>( !buckets-- ) <span class="keywordflow">return</span>;
 <a name="l00308"></a>00308             <span class="keywordtype">bool</span> is_initial = !my_size;
 <a name="l00309"></a>00309             <span class="keywordflow">for</span>( size_type m = my_mask; buckets &gt; m; m = my_mask )
 <a name="l00310"></a>00310                 enable_segment( segment_index_of( m+1 ), is_initial );
 <a name="l00311"></a>00311         }
 <a name="l00313"></a>00313         <span class="keywordtype">void</span> internal_swap(hash_map_base &amp;table) {
 <a name="l00314"></a>00314             std::swap(this-&gt;my_mask, table.my_mask);
 <a name="l00315"></a>00315             std::swap(this-&gt;my_size, table.my_size);
 <a name="l00316"></a>00316             <span class="keywordflow">for</span>(size_type i = 0; i &lt; embedded_buckets; i++)
 <a name="l00317"></a>00317                 std::swap(this-&gt;my_embedded_segment[i].node_list, table.my_embedded_segment[i].node_list);
 <a name="l00318"></a>00318             <span class="keywordflow">for</span>(size_type i = embedded_block; i &lt; pointers_per_table; i++)
 <a name="l00319"></a>00319                 std::swap(this-&gt;my_table[i], table.my_table[i]);
 <a name="l00320"></a>00320         }
 <a name="l00321"></a>00321     };
 <a name="l00322"></a>00322
 <a name="l00323"></a>00323     <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Iterator&gt;
 <a name="l00324"></a>00324     <span class="keyword">class </span>hash_map_range;
 <a name="l00325"></a>00325
 <a name="l00327"></a>00327
 <a name="l00329"></a>00329     <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Container, <span class="keyword">typename</span> Value&gt;
 <a name="l00330"></a>00330     <span class="keyword">class </span>hash_map_iterator
 <a name="l00331"></a>00331         : <span class="keyword">public</span> std::iterator&lt;std::forward_iterator_tag,Value&gt;
 <a name="l00332"></a>00332     {
 <a name="l00333"></a>00333         <span class="keyword">typedef</span> Container map_type;
 <a name="l00334"></a>00334         <span class="keyword">typedef</span> <span class="keyword">typename</span> Container::node node;
 <a name="l00335"></a>00335         <span class="keyword">typedef</span> hash_map_base::node_base node_base;
 <a name="l00336"></a>00336         <span class="keyword">typedef</span> hash_map_base::bucket bucket;
 <a name="l00337"></a>00337
 <a name="l00338"></a>00338         <span class="keyword">template</span>&lt;<span class="keyword">typename</span> C, <span class="keyword">typename</span> T, <span class="keyword">typename</span> U&gt;
 <a name="l00339"></a>00339         <span class="keyword">friend</span> <span class="keywordtype">bool</span> operator==( <span class="keyword">const</span> hash_map_iterator&lt;C,T&gt;&amp; i, <span class="keyword">const</span> hash_map_iterator&lt;C,U&gt;&amp; j );
 <a name="l00340"></a>00340
 <a name="l00341"></a>00341         <span class="keyword">template</span>&lt;<span class="keyword">typename</span> C, <span class="keyword">typename</span> T, <span class="keyword">typename</span> U&gt;
 <a name="l00342"></a>00342         <span class="keyword">friend</span> <span class="keywordtype">bool</span> operator!=( <span class="keyword">const</span> hash_map_iterator&lt;C,T&gt;&amp; i, <span class="keyword">const</span> hash_map_iterator&lt;C,U&gt;&amp; j );
 <a name="l00343"></a>00343
 <a name="l00344"></a>00344         <span class="keyword">template</span>&lt;<span class="keyword">typename</span> C, <span class="keyword">typename</span> T, <span class="keyword">typename</span> U&gt;
 <a name="l00345"></a>00345         <span class="keyword">friend</span> ptrdiff_t operator-( <span class="keyword">const</span> hash_map_iterator&lt;C,T&gt;&amp; i, <span class="keyword">const</span> hash_map_iterator&lt;C,U&gt;&amp; j );
 <a name="l00346"></a>00346
 <a name="l00347"></a>00347         <span class="keyword">template</span>&lt;<span class="keyword">typename</span> C, <span class="keyword">typename</span> U&gt;
 <a name="l00348"></a>00348         <span class="keyword">friend</span> <span class="keyword">class </span>hash_map_iterator;
 <a name="l00349"></a>00349
 <a name="l00350"></a>00350         <span class="keyword">template</span>&lt;<span class="keyword">typename</span> I&gt;
 <a name="l00351"></a>00351         <span class="keyword">friend</span> <span class="keyword">class </span>hash_map_range;
 <a name="l00352"></a>00352
 <a name="l00353"></a>00353         <span class="keywordtype">void</span> advance_to_next_bucket() { <span class="comment">// TODO?: refactor to iterator_base class</span>
 <a name="l00354"></a>00354             size_t k = my_index+1;
 <a name="l00355"></a>00355             <span class="keywordflow">while</span>( my_bucket &amp;&amp; k &lt;= my_map-&gt;my_mask ) {
 <a name="l00356"></a>00356                 <span class="comment">// Following test uses 2's-complement wizardry</span>
 <a name="l00357"></a>00357                 <span class="keywordflow">if</span>( k&amp; (k-2) ) <span class="comment">// not the beginning of a segment</span>
 <a name="l00358"></a>00358                     ++my_bucket;
 <a name="l00359"></a>00359                 <span class="keywordflow">else</span> my_bucket = my_map-&gt;get_bucket( k );
 <a name="l00360"></a>00360                 my_node = static_cast&lt;node*&gt;( my_bucket-&gt;node_list );
 <a name="l00361"></a>00361                 <span class="keywordflow">if</span>( hash_map_base::is_valid(my_node) ) {
 <a name="l00362"></a>00362                     my_index = k; <span class="keywordflow">return</span>;
 <a name="l00363"></a>00363                 }
 <a name="l00364"></a>00364                 ++k;
 <a name="l00365"></a>00365             }
 <a name="l00366"></a>00366             my_bucket = 0; my_node = 0; my_index = k; <span class="comment">// the end</span>
 <a name="l00367"></a>00367         }
 <a name="l00368"></a>00368 <span class="preprocessor">#if !defined(_MSC_VER) || defined(__INTEL_COMPILER)</span>
 <a name="l00369"></a>00369 <span class="preprocessor"></span>        <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Key, <span class="keyword">typename</span> T, <span class="keyword">typename</span> HashCompare, <span class="keyword">typename</span> A&gt;
 <a name="l00370"></a>00370         <span class="keyword">friend</span> <span class="keyword">class </span>interface4::concurrent_hash_map;
 <a name="l00371"></a>00371 <span class="preprocessor">#else</span>
 <a name="l00372"></a>00372 <span class="preprocessor"></span>    <span class="keyword">public</span>: <span class="comment">// workaround</span>
 <a name="l00373"></a>00373 <span class="preprocessor">#endif</span>
 <a name="l00375"></a>00375 <span class="preprocessor">        const Container *my_map;</span>
 <a name="l00376"></a>00376 <span class="preprocessor"></span>
 <a name="l00378"></a>00378         size_t my_index;
 <a name="l00379"></a>00379
 <a name="l00381"></a>00381         <span class="keyword">const</span> bucket *my_bucket;
 <a name="l00382"></a>00382
 <a name="l00384"></a>00384         node *my_node;
 <a name="l00385"></a>00385
 <a name="l00386"></a>00386         hash_map_iterator( <span class="keyword">const</span> Container &amp;map, size_t index, <span class="keyword">const</span> bucket *b, node_base *n );
 <a name="l00387"></a>00387
 <a name="l00388"></a>00388     <span class="keyword">public</span>:
 <a name="l00390"></a>00390         hash_map_iterator() {}
 <a name="l00391"></a>00391         hash_map_iterator( <span class="keyword">const</span> hash_map_iterator&lt;Container,typename Container::value_type&gt; &amp;other ) :
 <a name="l00392"></a>00392             my_map(other.my_map),
 <a name="l00393"></a>00393             my_index(other.my_index),
 <a name="l00394"></a>00394             my_bucket(other.my_bucket),
 <a name="l00395"></a>00395             my_node(other.my_node)
 <a name="l00396"></a>00396         {}
 <a name="l00397"></a>00397         Value&amp; operator*()<span class="keyword"> const </span>{
 <a name="l00398"></a>00398             __TBB_ASSERT( hash_map_base::is_valid(my_node), <span class="stringliteral">"iterator uninitialized or at end of container?"</span> );
 <a name="l00399"></a>00399             <span class="keywordflow">return</span> my_node-&gt;item;
 <a name="l00400"></a>00400         }
 <a name="l00401"></a>00401         Value* operator-&gt;()<span class="keyword"> const </span>{<span class="keywordflow">return</span> &amp;operator*();}
 <a name="l00402"></a>00402         hash_map_iterator&amp; operator++();
 <a name="l00403"></a>00403
 <a name="l00405"></a>00405         Value* operator++(<span class="keywordtype">int</span>) {
 <a name="l00406"></a>00406             Value* result = &amp;operator*();
 <a name="l00407"></a>00407             operator++();
 <a name="l00408"></a>00408             <span class="keywordflow">return</span> result;
 <a name="l00409"></a>00409         }
 <a name="l00410"></a>00410     };
 <a name="l00411"></a>00411
 <a name="l00412"></a>00412     <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Container, <span class="keyword">typename</span> Value&gt;
 <a name="l00413"></a>00413     hash_map_iterator&lt;Container,Value&gt;::hash_map_iterator( <span class="keyword">const</span> Container &amp;map, size_t index, <span class="keyword">const</span> bucket *b, node_base *n ) :
 <a name="l00414"></a>00414         my_map(&amp;map),
 <a name="l00415"></a>00415         my_index(index),
 <a name="l00416"></a>00416         my_bucket(b),
 <a name="l00417"></a>00417         my_node( static_cast&lt;node*&gt;(n) )
 <a name="l00418"></a>00418     {
 <a name="l00419"></a>00419         <span class="keywordflow">if</span>( b &amp;&amp; !hash_map_base::is_valid(n) )
 <a name="l00420"></a>00420             advance_to_next_bucket();
 <a name="l00421"></a>00421     }
 <a name="l00422"></a>00422
 <a name="l00423"></a>00423     <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Container, <span class="keyword">typename</span> Value&gt;
 <a name="l00424"></a>00424     hash_map_iterator&lt;Container,Value&gt;&amp; hash_map_iterator&lt;Container,Value&gt;::operator++() {
 <a name="l00425"></a>00425         my_node = static_cast&lt;node*&gt;( my_node-&gt;next );
 <a name="l00426"></a>00426         <span class="keywordflow">if</span>( !my_node ) advance_to_next_bucket();
 <a name="l00427"></a>00427         <span class="keywordflow">return</span> *<span class="keyword">this</span>;
 <a name="l00428"></a>00428     }
 <a name="l00429"></a>00429
 <a name="l00430"></a>00430     <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Container, <span class="keyword">typename</span> T, <span class="keyword">typename</span> U&gt;
 <a name="l00431"></a>00431     <span class="keywordtype">bool</span> operator==( <span class="keyword">const</span> hash_map_iterator&lt;Container,T&gt;&amp; i, <span class="keyword">const</span> hash_map_iterator&lt;Container,U&gt;&amp; j ) {
 <a name="l00432"></a>00432         <span class="keywordflow">return</span> i.my_node == j.my_node &amp;&amp; i.my_map == j.my_map;
 <a name="l00433"></a>00433     }
 <a name="l00434"></a>00434
 <a name="l00435"></a>00435     <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Container, <span class="keyword">typename</span> T, <span class="keyword">typename</span> U&gt;
 <a name="l00436"></a>00436     <span class="keywordtype">bool</span> operator!=( <span class="keyword">const</span> hash_map_iterator&lt;Container,T&gt;&amp; i, <span class="keyword">const</span> hash_map_iterator&lt;Container,U&gt;&amp; j ) {
 <a name="l00437"></a>00437         <span class="keywordflow">return</span> i.my_node != j.my_node || i.my_map != j.my_map;
 <a name="l00438"></a>00438     }
 <a name="l00439"></a>00439
 <a name="l00441"></a>00441
 <a name="l00442"></a>00442     <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Iterator&gt;
 <a name="l00443"></a>00443     <span class="keyword">class </span>hash_map_range {
 <a name="l00444"></a>00444         <span class="keyword">typedef</span> <span class="keyword">typename</span> Iterator::map_type map_type;
 <a name="l00445"></a>00445         Iterator my_begin;
 <a name="l00446"></a>00446         Iterator my_end;
 <a name="l00447"></a>00447         <span class="keyword">mutable</span> Iterator my_midpoint;
 <a name="l00448"></a>00448         size_t my_grainsize;
 <a name="l00450"></a>00450         <span class="keywordtype">void</span> set_midpoint() <span class="keyword">const</span>;
 <a name="l00451"></a>00451         <span class="keyword">template</span>&lt;<span class="keyword">typename</span> U&gt; <span class="keyword">friend</span> <span class="keyword">class </span>hash_map_range;
 <a name="l00452"></a>00452     <span class="keyword">public</span>:
 <a name="l00454"></a>00454         <span class="keyword">typedef</span> std::size_t size_type;
 <a name="l00455"></a>00455         <span class="keyword">typedef</span> <span class="keyword">typename</span> Iterator::value_type value_type;
 <a name="l00456"></a>00456         <span class="keyword">typedef</span> <span class="keyword">typename</span> Iterator::reference reference;
 <a name="l00457"></a>00457         <span class="keyword">typedef</span> <span class="keyword">typename</span> Iterator::difference_type difference_type;
 <a name="l00458"></a>00458         <span class="keyword">typedef</span> Iterator iterator;
 <a name="l00459"></a>00459
 <a name="l00461"></a>00461         <span class="keywordtype">bool</span> empty()<span class="keyword"> const </span>{<span class="keywordflow">return</span> my_begin==my_end;}
 <a name="l00462"></a>00462
 <a name="l00464"></a>00464         <span class="keywordtype">bool</span> is_divisible()<span class="keyword"> const </span>{
 <a name="l00465"></a>00465             <span class="keywordflow">return</span> my_midpoint!=my_end;
 <a name="l00466"></a>00466         }
 <a name="l00468"></a>00468         hash_map_range( hash_map_range&amp; r, split ) :
 <a name="l00469"></a>00469             my_end(r.my_end),
 <a name="l00470"></a>00470             my_grainsize(r.my_grainsize)
 <a name="l00471"></a>00471         {
 <a name="l00472"></a>00472             r.my_end = my_begin = r.my_midpoint;
 <a name="l00473"></a>00473             __TBB_ASSERT( !empty(), <span class="stringliteral">"Splitting despite the range is not divisible"</span> );
 <a name="l00474"></a>00474             __TBB_ASSERT( !r.empty(), <span class="stringliteral">"Splitting despite the range is not divisible"</span> );
 <a name="l00475"></a>00475             set_midpoint();
 <a name="l00476"></a>00476             r.set_midpoint();
 <a name="l00477"></a>00477         }
 <a name="l00479"></a>00479         <span class="keyword">template</span>&lt;<span class="keyword">typename</span> U&gt;
 <a name="l00480"></a>00480         hash_map_range( hash_map_range&lt;U&gt;&amp; r) :
 <a name="l00481"></a>00481             my_begin(r.my_begin),
 <a name="l00482"></a>00482             my_end(r.my_end),
 <a name="l00483"></a>00483             my_midpoint(r.my_midpoint),
 <a name="l00484"></a>00484             my_grainsize(r.my_grainsize)
 <a name="l00485"></a>00485         {}
 <a name="l00486"></a>00486 <span class="preprocessor">#if TBB_DEPRECATED</span>
 <a name="l00488"></a>00488 <span class="preprocessor">        hash_map_range( const Iterator&amp; begin_, const Iterator&amp; end_, size_type grainsize_ = 1 ) : </span>
 <a name="l00489"></a>00489 <span class="preprocessor"></span>            my_begin(begin_),
 <a name="l00490"></a>00490             my_end(end_),
 <a name="l00491"></a>00491             my_grainsize(grainsize_)
 <a name="l00492"></a>00492         {
 <a name="l00493"></a>00493             <span class="keywordflow">if</span>(!my_end.my_index &amp;&amp; !my_end.my_bucket) <span class="comment">// end</span>
 <a name="l00494"></a>00494                 my_end.my_index = my_end.my_map-&gt;my_mask + 1;
 <a name="l00495"></a>00495             set_midpoint();
 <a name="l00496"></a>00496             __TBB_ASSERT( grainsize_&gt;0, <span class="stringliteral">"grainsize must be positive"</span> );
 <a name="l00497"></a>00497         }
 <a name="l00498"></a>00498 <span class="preprocessor">#endif</span>
 <a name="l00500"></a>00500 <span class="preprocessor">        hash_map_range( const map_type &amp;map, size_type grainsize_ = 1 ) : </span>
 <a name="l00501"></a>00501 <span class="preprocessor"></span>            my_begin( Iterator( map, 0, map.my_embedded_segment, map.my_embedded_segment-&gt;node_list ) ),
 <a name="l00502"></a>00502             my_end( Iterator( map, map.my_mask + 1, 0, 0 ) ),
 <a name="l00503"></a>00503             my_grainsize( grainsize_ )
 <a name="l00504"></a>00504         {
 <a name="l00505"></a>00505             __TBB_ASSERT( grainsize_&gt;0, <span class="stringliteral">"grainsize must be positive"</span> );
 <a name="l00506"></a>00506             set_midpoint();
 <a name="l00507"></a>00507         }
 <a name="l00508"></a>00508         <span class="keyword">const</span> Iterator&amp; begin()<span class="keyword"> const </span>{<span class="keywordflow">return</span> my_begin;}
 <a name="l00509"></a>00509         <span class="keyword">const</span> Iterator&amp; end()<span class="keyword"> const </span>{<span class="keywordflow">return</span> my_end;}
 <a name="l00511"></a>00511         size_type grainsize()<span class="keyword"> const </span>{<span class="keywordflow">return</span> my_grainsize;}
 <a name="l00512"></a>00512     };
 <a name="l00513"></a>00513
 <a name="l00514"></a>00514     <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Iterator&gt;
 <a name="l00515"></a>00515     <span class="keywordtype">void</span> hash_map_range&lt;Iterator&gt;::set_midpoint()<span class="keyword"> const </span>{
 <a name="l00516"></a>00516         <span class="comment">// Split by groups of nodes</span>
 <a name="l00517"></a>00517         size_t m = my_end.my_index-my_begin.my_index;
 <a name="l00518"></a>00518         <span class="keywordflow">if</span>( m &gt; my_grainsize ) {
 <a name="l00519"></a>00519             m = my_begin.my_index + m/2u;
 <a name="l00520"></a>00520             hash_map_base::bucket *b = my_begin.my_map-&gt;get_bucket(m);
 <a name="l00521"></a>00521             my_midpoint = Iterator(*my_begin.my_map,m,b,b-&gt;node_list);
 <a name="l00522"></a>00522         } <span class="keywordflow">else</span> {
 <a name="l00523"></a>00523             my_midpoint = my_end;
 <a name="l00524"></a>00524         }
 <a name="l00525"></a>00525         __TBB_ASSERT( my_begin.my_index &lt;= my_midpoint.my_index,
 <a name="l00526"></a>00526             <span class="stringliteral">"my_begin is after my_midpoint"</span> );
 <a name="l00527"></a>00527         __TBB_ASSERT( my_midpoint.my_index &lt;= my_end.my_index,
 <a name="l00528"></a>00528             <span class="stringliteral">"my_midpoint is after my_end"</span> );
 <a name="l00529"></a>00529         __TBB_ASSERT( my_begin != my_midpoint || my_begin == my_end,
 <a name="l00530"></a>00530             <span class="stringliteral">"[my_begin, my_midpoint) range should not be empty"</span> );
 <a name="l00531"></a>00531     }
 <a name="l00532"></a>00532
 <a name="l00533"></a>00533     } <span class="comment">// internal</span>
 <a name="l00535"></a>00535 <span class="comment"></span>
 <a name="l00537"></a>00537
 <a name="l00566"></a>00566 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Key, <span class="keyword">typename</span> T, <span class="keyword">typename</span> HashCompare, <span class="keyword">typename</span> Allocator&gt;
 <a name="l00567"></a><a class="code" href="a00156.html">00567</a> <span class="keyword">class </span><a class="code" href="a00156.html">concurrent_hash_map</a> : <span class="keyword">protected</span> internal::hash_map_base {
 <a name="l00568"></a>00568     <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Container, <span class="keyword">typename</span> Value&gt;
 <a name="l00569"></a>00569     <span class="keyword">friend</span> <span class="keyword">class </span>internal::hash_map_iterator;
 <a name="l00570"></a>00570
 <a name="l00571"></a>00571     <span class="keyword">template</span>&lt;<span class="keyword">typename</span> I&gt;
 <a name="l00572"></a>00572     <span class="keyword">friend</span> <span class="keyword">class </span>internal::hash_map_range;
 <a name="l00573"></a>00573
 <a name="l00574"></a>00574 <span class="keyword">public</span>:
 <a name="l00575"></a>00575     <span class="keyword">typedef</span> Key key_type;
 <a name="l00576"></a>00576     <span class="keyword">typedef</span> T mapped_type;
 <a name="l00577"></a>00577     <span class="keyword">typedef</span> std::pair&lt;const Key,T&gt; value_type;
 <a name="l00578"></a>00578     <span class="keyword">typedef</span> hash_map_base::size_type size_type;
 <a name="l00579"></a>00579     <span class="keyword">typedef</span> ptrdiff_t difference_type;
 <a name="l00580"></a>00580     <span class="keyword">typedef</span> value_type *pointer;
 <a name="l00581"></a>00581     <span class="keyword">typedef</span> <span class="keyword">const</span> value_type *const_pointer;
 <a name="l00582"></a>00582     <span class="keyword">typedef</span> value_type &amp;reference;
 <a name="l00583"></a>00583     <span class="keyword">typedef</span> <span class="keyword">const</span> value_type &amp;const_reference;
 <a name="l00584"></a>00584     <span class="keyword">typedef</span> internal::hash_map_iterator&lt;concurrent_hash_map,value_type&gt; iterator;
 <a name="l00585"></a>00585     <span class="keyword">typedef</span> internal::hash_map_iterator&lt;concurrent_hash_map,const value_type&gt; const_iterator;
 <a name="l00586"></a>00586     <span class="keyword">typedef</span> internal::hash_map_range&lt;iterator&gt; range_type;
 <a name="l00587"></a>00587     <span class="keyword">typedef</span> internal::hash_map_range&lt;const_iterator&gt; const_range_type;
 <a name="l00588"></a>00588     <span class="keyword">typedef</span> Allocator allocator_type;
 <a name="l00589"></a>00589
 <a name="l00590"></a>00590 <span class="keyword">protected</span>:
 <a name="l00591"></a>00591     <span class="keyword">friend</span> <span class="keyword">class </span><a class="code" href="a00159.html">const_accessor</a>;
 <a name="l00592"></a>00592     <span class="keyword">struct </span>node;
 <a name="l00593"></a>00593     <span class="keyword">typedef</span> <span class="keyword">typename</span> Allocator::template rebind&lt;node&gt;::other node_allocator_type;
 <a name="l00594"></a>00594     node_allocator_type my_allocator;
 <a name="l00595"></a>00595     HashCompare my_hash_compare;
 <a name="l00596"></a>00596
 <a name="l00597"></a>00597     <span class="keyword">struct </span>node : <span class="keyword">public</span> node_base {
 <a name="l00598"></a>00598         value_type item;
 <a name="l00599"></a>00599         node( <span class="keyword">const</span> Key &amp;key ) : item(key, T()) {}
 <a name="l00600"></a>00600         node( <span class="keyword">const</span> Key &amp;key, <span class="keyword">const</span> T &amp;t ) : item(key, t) {}
 <a name="l00601"></a>00601         <span class="comment">// exception-safe allocation, see C++ Standard 2003, clause 5.3.4p17</span>
 <a name="l00602"></a>00602         <span class="keywordtype">void</span> *operator new( size_t <span class="comment">/*size*/</span>, node_allocator_type &amp;a ) {
 <a name="l00603"></a>00603             <span class="keywordtype">void</span> *ptr = a.allocate(1);
 <a name="l00604"></a>00604             <span class="keywordflow">if</span>(!ptr)
 <a name="l00605"></a>00605                 tbb::internal::throw_exception(tbb::internal::eid_bad_alloc);
 <a name="l00606"></a>00606             <span class="keywordflow">return</span> ptr;
 <a name="l00607"></a>00607         }
 <a name="l00608"></a>00608         <span class="comment">// match placement-new form above to be called if exception thrown in constructor</span>
 <a name="l00609"></a>00609         <span class="keywordtype">void</span> operator delete( <span class="keywordtype">void</span> *ptr, node_allocator_type &amp;a ) {<span class="keywordflow">return</span> a.deallocate(static_cast&lt;node*&gt;(ptr),1); }
 <a name="l00610"></a>00610     };
 <a name="l00611"></a>00611
 <a name="l00612"></a>00612     <span class="keywordtype">void</span> delete_node( node_base *n ) {
 <a name="l00613"></a>00613         my_allocator.destroy( static_cast&lt;node*&gt;(n) );
 <a name="l00614"></a>00614         my_allocator.deallocate( static_cast&lt;node*&gt;(n), 1);
 <a name="l00615"></a>00615     }
 <a name="l00616"></a>00616
 <a name="l00617"></a>00617     node *search_bucket( <span class="keyword">const</span> key_type &amp;key, bucket *b )<span class="keyword"> const </span>{
 <a name="l00618"></a>00618         node *n = static_cast&lt;node*&gt;( b-&gt;node_list );
 <a name="l00619"></a>00619         <span class="keywordflow">while</span>( is_valid(n) &amp;&amp; !my_hash_compare.equal(key, n-&gt;item.first) )
 <a name="l00620"></a>00620             n = static_cast&lt;node*&gt;( n-&gt;next );
 <a name="l00621"></a>00621         __TBB_ASSERT(n != internal::rehash_req, <span class="stringliteral">"Search can be executed only for rehashed bucket"</span>);
 <a name="l00622"></a>00622         <span class="keywordflow">return</span> n;
 <a name="l00623"></a>00623     }
 <a name="l00624"></a>00624
 <a name="l00626"></a><a class="code" href="a00158.html">00626</a>     <span class="keyword">class </span><a class="code" href="a00158.html">bucket_accessor</a> : <span class="keyword">public</span> bucket::scoped_t {
 <a name="l00627"></a>00627         <span class="keywordtype">bool</span> my_is_writer; <span class="comment">// TODO: use it from base type</span>
 <a name="l00628"></a>00628         bucket *my_b;
 <a name="l00629"></a>00629     <span class="keyword">public</span>:
 <a name="l00630"></a>00630         <a class="code" href="a00158.html">bucket_accessor</a>( <a class="code" href="a00156.html">concurrent_hash_map</a> *base, <span class="keyword">const</span> hashcode_t h, <span class="keywordtype">bool</span> writer = <span class="keyword">false</span> ) { <a class="code" href="a00267.html#a8686246bb5d3664bd07563749970fef5f1fafe8d229d348ff91d937f64e79c7">acquire</a>( base, h, writer ); }
 <a name="l00632"></a><a class="code" href="a00158.html#26b4fe0ca87a7ad4852cb787db880119">00632</a>         <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="a00267.html#a8686246bb5d3664bd07563749970fef5f1fafe8d229d348ff91d937f64e79c7">acquire</a>( <a class="code" href="a00156.html">concurrent_hash_map</a> *base, <span class="keyword">const</span> hashcode_t h, <span class="keywordtype">bool</span> writer = <span class="keyword">false</span> ) {
 <a name="l00633"></a>00633             my_b = base-&gt;get_bucket( h );
 <a name="l00634"></a>00634 <span class="preprocessor">#if TBB_USE_THREADING_TOOLS</span>
 <a name="l00635"></a>00635 <span class="preprocessor"></span>            <span class="comment">// TODO: actually, notification is unnecessary here, just hiding double-check</span>
 <a name="l00636"></a>00636             <span class="keywordflow">if</span>( itt_load_pointer_with_acquire_v3(&amp;my_b-&gt;node_list) == internal::rehash_req
 <a name="l00637"></a>00637 #<span class="keywordflow">else</span>
 <a name="l00638"></a>00638             <span class="keywordflow">if</span>( __TBB_load_with_acquire(my_b-&gt;node_list) == internal::rehash_req
 <a name="l00639"></a>00639 #endif
 <a name="l00640"></a>00640                 &amp;&amp; try_acquire( my_b-&gt;mutex, <span class="comment">/*write=*/</span><span class="keyword">true</span> ) )
 <a name="l00641"></a>00641             {
 <a name="l00642"></a>00642                 <span class="keywordflow">if</span>( my_b-&gt;node_list == internal::rehash_req ) base-&gt;<a class="code" href="a00156.html#571d635fd206d9985cf20a1a659ea476">rehash_bucket</a>( my_b, h ); <span class="comment">//recursive rehashing</span>
 <a name="l00643"></a>00643                 my_is_writer = <span class="keyword">true</span>;
 <a name="l00644"></a>00644             }
 <a name="l00645"></a>00645             <span class="keywordflow">else</span> bucket::scoped_t::acquire( my_b-&gt;mutex, <span class="comment">/*write=*/</span>my_is_writer = writer );
 <a name="l00646"></a>00646             __TBB_ASSERT( my_b-&gt;node_list != internal::rehash_req, NULL);
 <a name="l00647"></a>00647         }
 <a name="l00649"></a><a class="code" href="a00158.html#fc194e3a186dc935a5fb513cc9f8e898">00649</a>         <span class="keywordtype">bool</span> is_writer() { <span class="keywordflow">return</span> my_is_writer; }
 <a name="l00651"></a><a class="code" href="a00158.html#57c6110bd20e95c06de5a199de988941">00651</a>         bucket *operator() () { <span class="keywordflow">return</span> my_b; }
 <a name="l00652"></a>00652         <span class="comment">// TODO: optimize out</span>
 <a name="l00653"></a>00653         <span class="keywordtype">bool</span> upgrade_to_writer() { my_is_writer = <span class="keyword">true</span>; <span class="keywordflow">return</span> bucket::scoped_t::upgrade_to_writer(); }
 <a name="l00654"></a>00654     };
 <a name="l00655"></a>00655
 <a name="l00656"></a>00656     <span class="comment">// TODO refactor to hash_base</span>
 <a name="l00657"></a>00657     <span class="keywordtype">void</span> rehash_bucket( bucket *b_new, <span class="keyword">const</span> hashcode_t h ) {
 <a name="l00658"></a>00658         __TBB_ASSERT( *(intptr_t*)(&amp;b_new-&gt;mutex), <span class="stringliteral">"b_new must be locked (for write)"</span>);
 <a name="l00659"></a>00659         __TBB_ASSERT( h &gt; 1, <span class="stringliteral">"The lowermost buckets can't be rehashed"</span> );
 <a name="l00660"></a>00660         __TBB_store_with_release(b_new-&gt;node_list, internal::empty_rehashed); <span class="comment">// mark rehashed</span>
 <a name="l00661"></a>00661         hashcode_t mask = ( 1u&lt;&lt;__TBB_Log2( h ) ) - 1; <span class="comment">// get parent mask from the topmost bit</span>
 <a name="l00662"></a>00662
 <a name="l00663"></a>00663         bucket_accessor b_old( <span class="keyword">this</span>, h &amp; mask );
 <a name="l00664"></a>00664
 <a name="l00665"></a>00665         mask = (mask&lt;&lt;1) | 1; <span class="comment">// get full mask for new bucket</span>
 <a name="l00666"></a>00666         __TBB_ASSERT( (mask&amp;(mask+1))==0 &amp;&amp; (h &amp; mask) == h, NULL );
 <a name="l00667"></a>00667     restart:
 <a name="l00668"></a>00668         <span class="keywordflow">for</span>( node_base **p = &amp;b_old()-&gt;node_list, *n = __TBB_load_with_acquire(*p); is_valid(n); n = *p ) {
 <a name="l00669"></a>00669             hashcode_t c = my_hash_compare.hash( static_cast&lt;node*&gt;(n)-&gt;item.first );
 <a name="l00670"></a>00670 <span class="preprocessor">#if TBB_USE_ASSERT</span>
 <a name="l00671"></a>00671 <span class="preprocessor"></span>            hashcode_t bmask = h &amp; (mask&gt;&gt;1);
 <a name="l00672"></a>00672             bmask = bmask==0? 1 : ( 1u&lt;&lt;(__TBB_Log2( bmask )+1 ) ) - 1; <span class="comment">// minimal mask of parent bucket</span>
 <a name="l00673"></a>00673             __TBB_ASSERT( (c &amp; bmask) == (h &amp; bmask), <span class="stringliteral">"hash() function changed for key in table"</span> );
 <a name="l00674"></a>00674 <span class="preprocessor">#endif</span>
 <a name="l00675"></a>00675 <span class="preprocessor"></span>            <span class="keywordflow">if</span>( (c &amp; mask) == h ) {
 <a name="l00676"></a>00676                 <span class="keywordflow">if</span>( !b_old.is_writer() )
 <a name="l00677"></a>00677                     <span class="keywordflow">if</span>( !b_old.upgrade_to_writer() ) {
 <a name="l00678"></a>00678                         <span class="keywordflow">goto</span> restart; <span class="comment">// node ptr can be invalid due to concurrent erase</span>
 <a name="l00679"></a>00679                     }
 <a name="l00680"></a>00680                 *p = n-&gt;next; <span class="comment">// exclude from b_old</span>
 <a name="l00681"></a>00681                 add_to_bucket( b_new, n );
 <a name="l00682"></a>00682             } <span class="keywordflow">else</span> p = &amp;n-&gt;next; <span class="comment">// iterate to next item</span>
 <a name="l00683"></a>00683         }
 <a name="l00684"></a>00684     }
 <a name="l00685"></a>00685
 <a name="l00686"></a>00686 <span class="keyword">public</span>:
 <a name="l00687"></a>00687
 <a name="l00688"></a>00688     <span class="keyword">class </span>accessor;
 <a name="l00690"></a><a class="code" href="a00159.html">00690</a>     <span class="keyword">class </span><a class="code" href="a00159.html">const_accessor</a> {
 <a name="l00691"></a>00691         <span class="keyword">friend</span> <span class="keyword">class </span><a class="code" href="a00156.html">concurrent_hash_map</a>&lt;Key,T,HashCompare,Allocator&gt;;
 <a name="l00692"></a>00692         <span class="keyword">friend</span> <span class="keyword">class </span><a class="code" href="a00157.html">accessor</a>;
 <a name="l00693"></a>00693         <span class="keywordtype">void</span> operator=( <span class="keyword">const</span> <a class="code" href="a00157.html">accessor</a> &amp; ) <span class="keyword">const</span>; <span class="comment">// Deny access</span>
 <a name="l00694"></a>00694         <a class="code" href="a00159.html">const_accessor</a>( <span class="keyword">const</span> <a class="code" href="a00157.html">accessor</a> &amp; );       <span class="comment">// Deny access</span>
 <a name="l00695"></a>00695     <span class="keyword">public</span>:
 <a name="l00697"></a><a class="code" href="a00159.html#48647ca0d79c1233b997f5768403c926">00697</a>         <span class="keyword">typedef</span> <span class="keyword">const</span> <span class="keyword">typename</span> concurrent_hash_map::value_type value_type;
 <a name="l00698"></a>00698
 <a name="l00700"></a><a class="code" href="a00159.html#5cce3104cb0a52e08d2131370871c614">00700</a>         <span class="keywordtype">bool</span> empty()<span class="keyword"> const </span>{<span class="keywordflow">return</span> !my_node;}
 <a name="l00701"></a>00701
 <a name="l00703"></a><a class="code" href="a00159.html#d5ce4f88d8870290238a8ad621e6f270">00703</a>         <span class="keywordtype">void</span> <a class="code" href="a00267.html#a8686246bb5d3664bd07563749970fefaa1fa107db0245c41fb109d976ae8d70">release</a>() {
 <a name="l00704"></a>00704             <span class="keywordflow">if</span>( my_node ) {
 <a name="l00705"></a>00705                 my_lock.release();
 <a name="l00706"></a>00706                 my_node = 0;
 <a name="l00707"></a>00707             }
 <a name="l00708"></a>00708         }
 <a name="l00709"></a>00709
 <a name="l00711"></a><a class="code" href="a00159.html#30f31106840700a4c3664b9cb1c31ca7">00711</a>         const_reference operator*()<span class="keyword"> const </span>{
 <a name="l00712"></a>00712             __TBB_ASSERT( my_node, <span class="stringliteral">"attempt to dereference empty accessor"</span> );
 <a name="l00713"></a>00713             <span class="keywordflow">return</span> my_node-&gt;item;
 <a name="l00714"></a>00714         }
 <a name="l00715"></a>00715
 <a name="l00717"></a><a class="code" href="a00159.html#3d03a48ecb8cd9549bd8be64b09c9b0d">00717</a>         const_pointer operator-&gt;()<span class="keyword"> const </span>{
 <a name="l00718"></a>00718             <span class="keywordflow">return</span> &amp;operator*();
 <a name="l00719"></a>00719         }
 <a name="l00720"></a>00720
 <a name="l00722"></a><a class="code" href="a00159.html#a9ead65cca68d4c49c7ef64d7899a4c8">00722</a>         <a class="code" href="a00159.html">const_accessor</a>() : my_node(NULL) {}
 <a name="l00723"></a>00723
 <a name="l00725"></a><a class="code" href="a00159.html#752b0c1ec74b94786403a75e42917d01">00725</a>         ~<a class="code" href="a00159.html">const_accessor</a>() {
 <a name="l00726"></a>00726             my_node = NULL; <span class="comment">// my_lock.release() is called in scoped_lock destructor</span>
 <a name="l00727"></a>00727         }
 <a name="l00728"></a>00728     <span class="keyword">private</span>:
 <a name="l00729"></a>00729         node *my_node;
 <a name="l00730"></a>00730         <span class="keyword">typename</span> node::scoped_t my_lock;
 <a name="l00731"></a>00731         hashcode_t my_hash;
 <a name="l00732"></a>00732     };
 <a name="l00733"></a>00733
 <a name="l00735"></a><a class="code" href="a00157.html">00735</a>     <span class="keyword">class </span><a class="code" href="a00157.html">accessor</a>: <span class="keyword">public</span> <a class="code" href="a00159.html">const_accessor</a> {
 <a name="l00736"></a>00736     <span class="keyword">public</span>:
 <a name="l00738"></a><a class="code" href="a00157.html#49eec74f272bab187d176c0d9d16a7fe">00738</a>         <span class="keyword">typedef</span> <span class="keyword">typename</span> concurrent_hash_map::value_type value_type;
 <a name="l00739"></a>00739
 <a name="l00741"></a><a class="code" href="a00157.html#e8938f0cd1211e88a1d73527ed3636c4">00741</a>         reference operator*()<span class="keyword"> const </span>{
 <a name="l00742"></a>00742             __TBB_ASSERT( this-&gt;my_node, <span class="stringliteral">"attempt to dereference empty accessor"</span> );
 <a name="l00743"></a>00743             <span class="keywordflow">return</span> this-&gt;my_node-&gt;item;
 <a name="l00744"></a>00744         }
 <a name="l00745"></a>00745
 <a name="l00747"></a><a class="code" href="a00157.html#fcebc32c020202cc37e60eadef157569">00747</a>         pointer operator-&gt;()<span class="keyword"> const </span>{
 <a name="l00748"></a>00748             <span class="keywordflow">return</span> &amp;operator*();
 <a name="l00749"></a>00749         }
 <a name="l00750"></a>00750     };
 <a name="l00751"></a>00751
 <a name="l00753"></a><a class="code" href="a00156.html#d827bb5e4f61de1916ab67d51c7c6e60">00753</a>     <a class="code" href="a00156.html">concurrent_hash_map</a>(<span class="keyword">const</span> allocator_type &amp;a = allocator_type())
 <a name="l00754"></a>00754         : internal::hash_map_base(), my_allocator(a)
 <a name="l00755"></a>00755     {}
 <a name="l00756"></a>00756
 <a name="l00758"></a><a class="code" href="a00156.html#a4612d5c7233712d455496641e9b31ff">00758</a>     <a class="code" href="a00156.html">concurrent_hash_map</a>(size_type n, <span class="keyword">const</span> allocator_type &amp;a = allocator_type())
 <a name="l00759"></a>00759         : my_allocator(a)
 <a name="l00760"></a>00760     {
 <a name="l00761"></a>00761         reserve( n );
 <a name="l00762"></a>00762     }
 <a name="l00763"></a>00763
 <a name="l00765"></a><a class="code" href="a00156.html#df0cd14eaddb17f10929c91519e65be9">00765</a>     <a class="code" href="a00156.html">concurrent_hash_map</a>( <span class="keyword">const</span> <a class="code" href="a00156.html">concurrent_hash_map</a>&amp; table, <span class="keyword">const</span> allocator_type &amp;a = allocator_type())
 <a name="l00766"></a>00766         : internal::hash_map_base(), my_allocator(a)
 <a name="l00767"></a>00767     {
 <a name="l00768"></a>00768         internal_copy(table);
 <a name="l00769"></a>00769     }
 <a name="l00770"></a>00770
 <a name="l00772"></a>00772     <span class="keyword">template</span>&lt;<span class="keyword">typename</span> I&gt;
 <a name="l00773"></a><a class="code" href="a00156.html#3bfe75fcb350ce39cf610c164f233edc">00773</a>     <a class="code" href="a00156.html">concurrent_hash_map</a>(I first, I last, <span class="keyword">const</span> allocator_type &amp;a = allocator_type())
 <a name="l00774"></a>00774         : my_allocator(a)
 <a name="l00775"></a>00775     {
 <a name="l00776"></a>00776         reserve( std::distance(first, last) ); <span class="comment">// TODO: load_factor?</span>
 <a name="l00777"></a>00777         internal_copy(first, last);
 <a name="l00778"></a>00778     }
 <a name="l00779"></a>00779
 <a name="l00781"></a><a class="code" href="a00156.html#2c0c42a2e1b5282b6739157df9ce2304">00781</a>     <a class="code" href="a00156.html">concurrent_hash_map</a>&amp; operator=( <span class="keyword">const</span> <a class="code" href="a00156.html">concurrent_hash_map</a>&amp; table ) {
 <a name="l00782"></a>00782         <span class="keywordflow">if</span>( <span class="keyword">this</span>!=&amp;table ) {
 <a name="l00783"></a>00783             clear();
 <a name="l00784"></a>00784             internal_copy(table);
 <a name="l00785"></a>00785         }
 <a name="l00786"></a>00786         <span class="keywordflow">return</span> *<span class="keyword">this</span>;
 <a name="l00787"></a>00787     }
 <a name="l00788"></a>00788
 <a name="l00789"></a>00789
 <a name="l00791"></a>00791
 <a name="l00793"></a>00793     <span class="keywordtype">void</span> rehash(size_type n = 0);
 <a name="l00794"></a>00794
 <a name="l00796"></a>00796     <span class="keywordtype">void</span> clear();
 <a name="l00797"></a>00797
 <a name="l00799"></a><a class="code" href="a00156.html#a1ac58997d8fbf242b266e3691573481">00799</a>     ~<a class="code" href="a00156.html">concurrent_hash_map</a>() { clear(); }
 <a name="l00800"></a>00800
 <a name="l00801"></a>00801     <span class="comment">//------------------------------------------------------------------------</span>
 <a name="l00802"></a>00802     <span class="comment">// Parallel algorithm support</span>
 <a name="l00803"></a>00803     <span class="comment">//------------------------------------------------------------------------</span>
 <a name="l00804"></a>00804     range_type range( size_type grainsize=1 ) {
 <a name="l00805"></a>00805         <span class="keywordflow">return</span> range_type( *<span class="keyword">this</span>, grainsize );
 <a name="l00806"></a>00806     }
 <a name="l00807"></a>00807     const_range_type range( size_type grainsize=1 )<span class="keyword"> const </span>{
 <a name="l00808"></a>00808         <span class="keywordflow">return</span> const_range_type( *<span class="keyword">this</span>, grainsize );
 <a name="l00809"></a>00809     }
 <a name="l00810"></a>00810
 <a name="l00811"></a>00811     <span class="comment">//------------------------------------------------------------------------</span>
 <a name="l00812"></a>00812     <span class="comment">// STL support - not thread-safe methods</span>
 <a name="l00813"></a>00813     <span class="comment">//------------------------------------------------------------------------</span>
 <a name="l00814"></a>00814     iterator begin() {<span class="keywordflow">return</span> iterator(*<span class="keyword">this</span>,0,my_embedded_segment,my_embedded_segment-&gt;node_list);}
 <a name="l00815"></a>00815     iterator end() {<span class="keywordflow">return</span> iterator(*<span class="keyword">this</span>,0,0,0);}
 <a name="l00816"></a>00816     const_iterator begin()<span class="keyword"> const </span>{<span class="keywordflow">return</span> const_iterator(*<span class="keyword">this</span>,0,my_embedded_segment,my_embedded_segment-&gt;node_list);}
 <a name="l00817"></a>00817     const_iterator end()<span class="keyword"> const </span>{<span class="keywordflow">return</span> const_iterator(*<span class="keyword">this</span>,0,0,0);}
 <a name="l00818"></a>00818     std::pair&lt;iterator, iterator&gt; equal_range( <span class="keyword">const</span> Key&amp; key ) { <span class="keywordflow">return</span> internal_equal_range(key, end()); }
 <a name="l00819"></a>00819     std::pair&lt;const_iterator, const_iterator&gt; equal_range( <span class="keyword">const</span> Key&amp; key )<span class="keyword"> const </span>{ <span class="keywordflow">return</span> internal_equal_range(key, end()); }
 <a name="l00820"></a>00820
 <a name="l00822"></a><a class="code" href="a00156.html#17fd8c5fe8c6a86075f34aa4e8412ba3">00822</a>     size_type size()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> my_size; }
 <a name="l00823"></a>00823
 <a name="l00825"></a><a class="code" href="a00156.html#6cab7d029a3e73a653ef0faeac4d1586">00825</a>     <span class="keywordtype">bool</span> empty()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> my_size == 0; }
 <a name="l00826"></a>00826
 <a name="l00828"></a><a class="code" href="a00156.html#1e45d3cbd1e2ae06f365f1b48e0df0b5">00828</a>     size_type max_size()<span class="keyword"> const </span>{<span class="keywordflow">return</span> (~size_type(0))/<span class="keyword">sizeof</span>(node);}
 <a name="l00829"></a>00829
 <a name="l00831"></a><a class="code" href="a00156.html#414d15033d36c63aa3a40666dc4d6f5e">00831</a>     size_type bucket_count()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> my_mask+1; }
 <a name="l00832"></a>00832
 <a name="l00834"></a><a class="code" href="a00156.html#199208eed6f09e200cda364f906be0fe">00834</a>     allocator_type get_allocator()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> this-&gt;my_allocator; }
 <a name="l00835"></a>00835
 <a name="l00837"></a>00837     <span class="keywordtype">void</span> swap(<a class="code" href="a00156.html">concurrent_hash_map</a> &amp;table);
 <a name="l00838"></a>00838
 <a name="l00839"></a>00839     <span class="comment">//------------------------------------------------------------------------</span>
 <a name="l00840"></a>00840     <span class="comment">// concurrent map operations</span>
 <a name="l00841"></a>00841     <span class="comment">//------------------------------------------------------------------------</span>
 <a name="l00842"></a>00842
 <a name="l00844"></a><a class="code" href="a00156.html#74f5ef06a06c5e619f156a1c76c04969">00844</a>     size_type count( <span class="keyword">const</span> Key &amp;key )<span class="keyword"> const </span>{
 <a name="l00845"></a>00845         <span class="keywordflow">return</span> const_cast&lt;concurrent_hash_map*&gt;(<span class="keyword">this</span>)-&gt;lookup(<span class="comment">/*insert*/</span><span class="keyword">false</span>, key, NULL, NULL, <span class="comment">/*write=*/</span><span class="keyword">false</span> );
 <a name="l00846"></a>00846     }
 <a name="l00847"></a>00847
 <a name="l00849"></a>00849
 <a name="l00850"></a><a class="code" href="a00156.html#64338d7f2e35df586af4cb0145cd910f">00850</a>     <span class="keywordtype">bool</span> find( <a class="code" href="a00159.html">const_accessor</a> &amp;result, <span class="keyword">const</span> Key &amp;key )<span class="keyword"> const </span>{
 <a name="l00851"></a>00851         result.<a class="code" href="a00159.html#d5ce4f88d8870290238a8ad621e6f270">release</a>();
 <a name="l00852"></a>00852         <span class="keywordflow">return</span> const_cast&lt;concurrent_hash_map*&gt;(<span class="keyword">this</span>)-&gt;lookup(<span class="comment">/*insert*/</span><span class="keyword">false</span>, key, NULL, &amp;result, <span class="comment">/*write=*/</span><span class="keyword">false</span> );
 <a name="l00853"></a>00853     }
 <a name="l00854"></a>00854
 <a name="l00856"></a>00856
 <a name="l00857"></a><a class="code" href="a00156.html#bce7bdf46435115a95cca2aa73c5da83">00857</a>     <span class="keywordtype">bool</span> find( <a class="code" href="a00157.html">accessor</a> &amp;result, <span class="keyword">const</span> Key &amp;key ) {
 <a name="l00858"></a>00858         result.<a class="code" href="a00159.html#d5ce4f88d8870290238a8ad621e6f270">release</a>();
 <a name="l00859"></a>00859         <span class="keywordflow">return</span> lookup(<span class="comment">/*insert*/</span><span class="keyword">false</span>, key, NULL, &amp;result, <span class="comment">/*write=*/</span><span class="keyword">true</span> );
 <a name="l00860"></a>00860     }
 <a name="l00861"></a>00861
 <a name="l00863"></a>00863
 <a name="l00864"></a><a class="code" href="a00156.html#58c38b27273de6c670568633c0931854">00864</a>     <span class="keywordtype">bool</span> insert( <a class="code" href="a00159.html">const_accessor</a> &amp;result, <span class="keyword">const</span> Key &amp;key ) {
 <a name="l00865"></a>00865         result.<a class="code" href="a00159.html#d5ce4f88d8870290238a8ad621e6f270">release</a>();
 <a name="l00866"></a>00866         <span class="keywordflow">return</span> lookup(<span class="comment">/*insert*/</span><span class="keyword">true</span>, key, NULL, &amp;result, <span class="comment">/*write=*/</span><span class="keyword">false</span> );
 <a name="l00867"></a>00867     }
 <a name="l00868"></a>00868
 <a name="l00870"></a>00870
 <a name="l00871"></a><a class="code" href="a00156.html#ccfecaa3e71d92be61fb3d811dd264eb">00871</a>     <span class="keywordtype">bool</span> insert( <a class="code" href="a00157.html">accessor</a> &amp;result, <span class="keyword">const</span> Key &amp;key ) {
 <a name="l00872"></a>00872         result.<a class="code" href="a00159.html#d5ce4f88d8870290238a8ad621e6f270">release</a>();
 <a name="l00873"></a>00873         <span class="keywordflow">return</span> lookup(<span class="comment">/*insert*/</span><span class="keyword">true</span>, key, NULL, &amp;result, <span class="comment">/*write=*/</span><span class="keyword">true</span> );
 <a name="l00874"></a>00874     }
 <a name="l00875"></a>00875
 <a name="l00877"></a>00877
 <a name="l00878"></a><a class="code" href="a00156.html#d4a2816129e38c53128c6d0c7b6b7370">00878</a>     <span class="keywordtype">bool</span> insert( <a class="code" href="a00159.html">const_accessor</a> &amp;result, <span class="keyword">const</span> value_type &amp;value ) {
 <a name="l00879"></a>00879         result.<a class="code" href="a00159.html#d5ce4f88d8870290238a8ad621e6f270">release</a>();
 <a name="l00880"></a>00880         <span class="keywordflow">return</span> lookup(<span class="comment">/*insert*/</span><span class="keyword">true</span>, value.first, &amp;value.second, &amp;result, <span class="comment">/*write=*/</span><span class="keyword">false</span> );
 <a name="l00881"></a>00881     }
 <a name="l00882"></a>00882
 <a name="l00884"></a>00884
 <a name="l00885"></a><a class="code" href="a00156.html#a657e61cd2b13164764ca2708875784a">00885</a>     <span class="keywordtype">bool</span> insert( <a class="code" href="a00157.html">accessor</a> &amp;result, <span class="keyword">const</span> value_type &amp;value ) {
 <a name="l00886"></a>00886         result.<a class="code" href="a00159.html#d5ce4f88d8870290238a8ad621e6f270">release</a>();
 <a name="l00887"></a>00887         <span class="keywordflow">return</span> lookup(<span class="comment">/*insert*/</span><span class="keyword">true</span>, value.first, &amp;value.second, &amp;result, <span class="comment">/*write=*/</span><span class="keyword">true</span> );
 <a name="l00888"></a>00888     }
 <a name="l00889"></a>00889
 <a name="l00891"></a>00891
 <a name="l00892"></a><a class="code" href="a00156.html#52bffd1066b3d7b793945bc6fa1a71a1">00892</a>     <span class="keywordtype">bool</span> insert( <span class="keyword">const</span> value_type &amp;value ) {
 <a name="l00893"></a>00893         <span class="keywordflow">return</span> lookup(<span class="comment">/*insert*/</span><span class="keyword">true</span>, value.first, &amp;value.second, NULL, <span class="comment">/*write=*/</span><span class="keyword">false</span> );
 <a name="l00894"></a>00894     }
 <a name="l00895"></a>00895
 <a name="l00897"></a>00897     <span class="keyword">template</span>&lt;<span class="keyword">typename</span> I&gt;
 <a name="l00898"></a><a class="code" href="a00156.html#cfe172677e5987004ef4a03e22fa338a">00898</a>     <span class="keywordtype">void</span> insert(I first, I last) {
 <a name="l00899"></a>00899         <span class="keywordflow">for</span>(; first != last; ++first)
 <a name="l00900"></a>00900             insert( *first );
 <a name="l00901"></a>00901     }
 <a name="l00902"></a>00902
 <a name="l00904"></a>00904
 <a name="l00905"></a>00905     <span class="keywordtype">bool</span> erase( <span class="keyword">const</span> Key&amp; key );
 <a name="l00906"></a>00906
 <a name="l00908"></a>00908
 <a name="l00909"></a><a class="code" href="a00156.html#da7e4a50f6bb06191817425ec85fe760">00909</a>     <span class="keywordtype">bool</span> erase( <a class="code" href="a00159.html">const_accessor</a>&amp; item_accessor ) {
 <a name="l00910"></a>00910         <span class="keywordflow">return</span> exclude( item_accessor, <span class="comment">/*readonly=*/</span> <span class="keyword">true</span> );
 <a name="l00911"></a>00911     }
 <a name="l00912"></a>00912
 <a name="l00914"></a>00914
 <a name="l00915"></a><a class="code" href="a00156.html#0f500842d0cf791f8fa61662edb1b311">00915</a>     <span class="keywordtype">bool</span> erase( <a class="code" href="a00157.html">accessor</a>&amp; item_accessor ) {
 <a name="l00916"></a>00916         <span class="keywordflow">return</span> exclude( item_accessor, <span class="comment">/*readonly=*/</span> <span class="keyword">false</span> );
 <a name="l00917"></a>00917     }
 <a name="l00918"></a>00918
 <a name="l00919"></a>00919 <span class="keyword">protected</span>:
 <a name="l00921"></a>00921     <span class="keywordtype">bool</span> lookup( <span class="keywordtype">bool</span> op_insert, <span class="keyword">const</span> Key &amp;key, <span class="keyword">const</span> T *t, const_accessor *result, <span class="keywordtype">bool</span> write );
 <a name="l00922"></a>00922
 <a name="l00924"></a>00924     <span class="keywordtype">bool</span> exclude( const_accessor &amp;item_accessor, <span class="keywordtype">bool</span> readonly );
 <a name="l00925"></a>00925
 <a name="l00927"></a>00927     <span class="keyword">template</span>&lt;<span class="keyword">typename</span> I&gt;
 <a name="l00928"></a>00928     std::pair&lt;I, I&gt; internal_equal_range( <span class="keyword">const</span> Key&amp; key, I end ) <span class="keyword">const</span>;
 <a name="l00929"></a>00929
 <a name="l00931"></a>00931     <span class="keywordtype">void</span> internal_copy( <span class="keyword">const</span> <a class="code" href="a00156.html">concurrent_hash_map</a>&amp; source );
 <a name="l00932"></a>00932
 <a name="l00933"></a>00933     <span class="keyword">template</span>&lt;<span class="keyword">typename</span> I&gt;
 <a name="l00934"></a>00934     <span class="keywordtype">void</span> internal_copy(I first, I last);
 <a name="l00935"></a>00935
 <a name="l00937"></a>00937
 <a name="l00939"></a><a class="code" href="a00156.html#2f76ed101a0ccc8875b846c2f747897e">00939</a>     const_pointer internal_fast_find( <span class="keyword">const</span> Key&amp; key )<span class="keyword"> const </span>{
 <a name="l00940"></a>00940         hashcode_t h = my_hash_compare.hash( key );
 <a name="l00941"></a>00941 <span class="preprocessor">#if TBB_USE_THREADING_TOOLS</span>
 <a name="l00942"></a>00942 <span class="preprocessor"></span>        hashcode_t m = (hashcode_t) itt_load_pointer_with_acquire_v3( &amp;my_mask );
 <a name="l00943"></a>00943 <span class="preprocessor">#else</span>
 <a name="l00944"></a>00944 <span class="preprocessor"></span>        hashcode_t m = my_mask;
 <a name="l00945"></a>00945 <span class="preprocessor">#endif</span>
 <a name="l00946"></a>00946 <span class="preprocessor"></span>        node *n;
 <a name="l00947"></a>00947     restart:
 <a name="l00948"></a>00948         __TBB_ASSERT((m&amp;(m+1))==0, NULL);
 <a name="l00949"></a>00949         bucket *b = get_bucket( h &amp; m );
 <a name="l00950"></a>00950 <span class="preprocessor">#if TBB_USE_THREADING_TOOLS</span>
 <a name="l00951"></a>00951 <span class="preprocessor"></span>        <span class="comment">// TODO: actually, notification is unnecessary here, just hiding double-check</span>
 <a name="l00952"></a>00952         <span class="keywordflow">if</span>( itt_load_pointer_with_acquire_v3(&amp;b-&gt;node_list) == internal::rehash_req )
 <a name="l00953"></a>00953 <span class="preprocessor">#else</span>
 <a name="l00954"></a>00954 <span class="preprocessor"></span>        <span class="keywordflow">if</span>( __TBB_load_with_acquire(b-&gt;node_list) == internal::rehash_req )
 <a name="l00955"></a>00955 <span class="preprocessor">#endif</span>
 <a name="l00956"></a>00956 <span class="preprocessor"></span>        {
 <a name="l00957"></a>00957             bucket::scoped_t lock;
 <a name="l00958"></a>00958             <span class="keywordflow">if</span>( lock.try_acquire( b-&gt;mutex, <span class="comment">/*write=*/</span><span class="keyword">true</span> ) ) {
 <a name="l00959"></a>00959                 <span class="keywordflow">if</span>( b-&gt;node_list == internal::rehash_req)
 <a name="l00960"></a>00960                     const_cast&lt;concurrent_hash_map*&gt;(<span class="keyword">this</span>)-&gt;rehash_bucket( b, h &amp; m ); <span class="comment">//recursive rehashing</span>
 <a name="l00961"></a>00961             }
 <a name="l00962"></a>00962             <span class="keywordflow">else</span> lock.acquire( b-&gt;mutex, <span class="comment">/*write=*/</span><span class="keyword">false</span> );
 <a name="l00963"></a>00963             __TBB_ASSERT(b-&gt;node_list!=internal::rehash_req,NULL);
 <a name="l00964"></a>00964         }
 <a name="l00965"></a>00965         n = search_bucket( key, b );
 <a name="l00966"></a>00966         <span class="keywordflow">if</span>( n )
 <a name="l00967"></a>00967             <span class="keywordflow">return</span> &amp;n-&gt;item;
 <a name="l00968"></a>00968         <span class="keywordflow">else</span> <span class="keywordflow">if</span>( check_mask_race( h, m ) )
 <a name="l00969"></a>00969             <span class="keywordflow">goto</span> restart;
 <a name="l00970"></a>00970         <span class="keywordflow">return</span> 0;
 <a name="l00971"></a>00971     }
 <a name="l00972"></a>00972 };
 <a name="l00973"></a>00973
 <a name="l00974"></a>00974 <span class="preprocessor">#if _MSC_VER &amp;&amp; !defined(__INTEL_COMPILER)</span>
 <a name="l00975"></a>00975 <span class="preprocessor"></span>    <span class="comment">// Suppress "conditional expression is constant" warning.</span>
 <a name="l00976"></a>00976 <span class="preprocessor">    #pragma warning( push )</span>
 <a name="l00977"></a>00977 <span class="preprocessor"></span><span class="preprocessor">    #pragma warning( disable: 4127 )</span>
 <a name="l00978"></a>00978 <span class="preprocessor"></span><span class="preprocessor">#endif</span>
 <a name="l00979"></a>00979 <span class="preprocessor"></span>
 <a name="l00980"></a>00980 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Key, <span class="keyword">typename</span> T, <span class="keyword">typename</span> HashCompare, <span class="keyword">typename</span> A&gt;
 <a name="l00981"></a><a class="code" href="a00156.html#1f22480a290ddc6c145888d8f985531a">00981</a> <span class="keywordtype">bool</span> <a class="code" href="a00156.html">concurrent_hash_map&lt;Key,T,HashCompare,A&gt;::lookup</a>( <span class="keywordtype">bool</span> op_insert, <span class="keyword">const</span> Key &amp;key, <span class="keyword">const</span> T *t, <a class="code" href="a00159.html">const_accessor</a> *result, <span class="keywordtype">bool</span> write ) {
 <a name="l00982"></a>00982     __TBB_ASSERT( !result || !result-&gt;<a class="code" href="a00159.html#74e5fd476c306e90361f3377f0fec6d8">my_node</a>, NULL );
 <a name="l00983"></a>00983     segment_index_t grow_segment;
 <a name="l00984"></a>00984     <span class="keywordtype">bool</span> return_value;
 <a name="l00985"></a>00985     node *n, *tmp_n = 0;
 <a name="l00986"></a>00986     hashcode_t <span class="keyword">const</span> h = my_hash_compare.hash( key );
 <a name="l00987"></a>00987 <span class="preprocessor">#if TBB_USE_THREADING_TOOLS</span>
 <a name="l00988"></a>00988 <span class="preprocessor"></span>    hashcode_t m = (hashcode_t) itt_load_pointer_with_acquire_v3( &amp;my_mask );
 <a name="l00989"></a>00989 <span class="preprocessor">#else</span>
 <a name="l00990"></a>00990 <span class="preprocessor"></span>    hashcode_t m = my_mask;
 <a name="l00991"></a>00991 <span class="preprocessor">#endif</span>
 <a name="l00992"></a>00992 <span class="preprocessor"></span>    restart:
 <a name="l00993"></a>00993     {<span class="comment">//lock scope</span>
 <a name="l00994"></a>00994         __TBB_ASSERT((m&amp;(m+1))==0, NULL);
 <a name="l00995"></a>00995         return_value = <span class="keyword">false</span>;
 <a name="l00996"></a>00996         <span class="comment">// get bucket</span>
 <a name="l00997"></a>00997         <a class="code" href="a00158.html">bucket_accessor</a> b( <span class="keyword">this</span>, h &amp; m );
 <a name="l00998"></a>00998
 <a name="l00999"></a>00999         <span class="comment">// find a node</span>
 <a name="l01000"></a>01000         n = search_bucket( key, b() );
 <a name="l01001"></a>01001         <span class="keywordflow">if</span>( op_insert ) {
 <a name="l01002"></a>01002             <span class="comment">// [opt] insert a key</span>
 <a name="l01003"></a>01003             <span class="keywordflow">if</span>( !n ) {
 <a name="l01004"></a>01004                 <span class="keywordflow">if</span>( !tmp_n ) {
 <a name="l01005"></a>01005                     <span class="keywordflow">if</span>(t) tmp_n = <span class="keyword">new</span>( my_allocator ) node(key, *t);
 <a name="l01006"></a>01006                     <span class="keywordflow">else</span>  tmp_n = <span class="keyword">new</span>( my_allocator ) node(key);
 <a name="l01007"></a>01007                 }
 <a name="l01008"></a>01008                 <span class="keywordflow">if</span>( !b.<a class="code" href="a00158.html#fc194e3a186dc935a5fb513cc9f8e898">is_writer</a>() &amp;&amp; !b.<a class="code" href="a00158.html#8f7f0dc61f528de29d06e6054b4a9835">upgrade_to_writer</a>() ) { <span class="comment">// TODO: improved insertion</span>
 <a name="l01009"></a>01009                     <span class="comment">// Rerun search_list, in case another thread inserted the item during the upgrade.</span>
 <a name="l01010"></a>01010                     n = search_bucket( key, b() );
 <a name="l01011"></a>01011                     <span class="keywordflow">if</span>( is_valid(n) ) { <span class="comment">// unfortunately, it did</span>
 <a name="l01012"></a>01012                         b.downgrade_to_reader();
 <a name="l01013"></a>01013                         <span class="keywordflow">goto</span> exists;
 <a name="l01014"></a>01014                     }
 <a name="l01015"></a>01015                 }
 <a name="l01016"></a>01016                 <span class="keywordflow">if</span>( check_mask_race(h, m) )
 <a name="l01017"></a>01017                     <span class="keywordflow">goto</span> restart; <span class="comment">// b.release() is done in ~b().</span>
 <a name="l01018"></a>01018                 <span class="comment">// insert and set flag to grow the container</span>
 <a name="l01019"></a>01019                 grow_segment = insert_new_node( b(), n = tmp_n, m );
 <a name="l01020"></a>01020                 tmp_n = 0;
 <a name="l01021"></a>01021                 return_value = <span class="keyword">true</span>;
 <a name="l01022"></a>01022             } <span class="keywordflow">else</span> {
 <a name="l01023"></a>01023     exists:     grow_segment = 0;
 <a name="l01024"></a>01024             }
 <a name="l01025"></a>01025         } <span class="keywordflow">else</span> { <span class="comment">// find or count</span>
 <a name="l01026"></a>01026             <span class="keywordflow">if</span>( !n ) {
 <a name="l01027"></a>01027                 <span class="keywordflow">if</span>( check_mask_race( h, m ) )
 <a name="l01028"></a>01028                     <span class="keywordflow">goto</span> restart; <span class="comment">// b.release() is done in ~b(). TODO: replace by continue</span>
 <a name="l01029"></a>01029                 <span class="keywordflow">return</span> <span class="keyword">false</span>;
 <a name="l01030"></a>01030             }
 <a name="l01031"></a>01031             return_value = <span class="keyword">true</span>;
 <a name="l01032"></a>01032             grow_segment = 0;
 <a name="l01033"></a>01033         }
 <a name="l01034"></a>01034         <span class="keywordflow">if</span>( !result ) <span class="keywordflow">goto</span> check_growth;
 <a name="l01035"></a>01035         <span class="comment">// TODO: the following seems as generic/regular operation</span>
 <a name="l01036"></a>01036         <span class="comment">// acquire the item</span>
 <a name="l01037"></a>01037         <span class="keywordflow">if</span>( !result-&gt;<a class="code" href="a00159.html#b57d7e72014cd2ae5a915606410615ce">my_lock</a>.try_acquire( n-&gt;mutex, write ) ) {
 <a name="l01038"></a>01038             <span class="comment">// we are unlucky, prepare for longer wait</span>
 <a name="l01039"></a>01039             <a class="code" href="a00145.html">tbb::internal::atomic_backoff</a> trials;
 <a name="l01040"></a>01040             <span class="keywordflow">do</span> {
 <a name="l01041"></a>01041                 <span class="keywordflow">if</span>( !trials.bounded_pause() ) {
 <a name="l01042"></a>01042                     <span class="comment">// the wait takes really long, restart the operation</span>
 <a name="l01043"></a>01043                     b.release();
 <a name="l01044"></a>01044                     __TBB_ASSERT( !op_insert || !return_value, <span class="stringliteral">"Can't acquire new item in locked bucket?"</span> );
 <a name="l01045"></a>01045                     __TBB_Yield();
 <a name="l01046"></a>01046 <span class="preprocessor">#if TBB_USE_THREADING_TOOLS</span>
 <a name="l01047"></a>01047 <span class="preprocessor"></span>                    m = (hashcode_t) itt_load_pointer_with_acquire_v3( &amp;my_mask );
 <a name="l01048"></a>01048 <span class="preprocessor">#else</span>
 <a name="l01049"></a>01049 <span class="preprocessor"></span>                    m = my_mask;
 <a name="l01050"></a>01050 <span class="preprocessor">#endif</span>
 <a name="l01051"></a>01051 <span class="preprocessor"></span>                    <span class="keywordflow">goto</span> restart;
 <a name="l01052"></a>01052                 }
 <a name="l01053"></a>01053             } <span class="keywordflow">while</span>( !result-&gt;<a class="code" href="a00159.html#b57d7e72014cd2ae5a915606410615ce">my_lock</a>.try_acquire( n-&gt;mutex, write ) );
 <a name="l01054"></a>01054         }
 <a name="l01055"></a>01055     }<span class="comment">//lock scope</span>
 <a name="l01056"></a>01056     result-&gt;<a class="code" href="a00159.html#74e5fd476c306e90361f3377f0fec6d8">my_node</a> = n;
 <a name="l01057"></a>01057     result-&gt;<a class="code" href="a00159.html#88e677d4e26a67d65d81af524ddd483a">my_hash</a> = h;
 <a name="l01058"></a>01058 check_growth:
 <a name="l01059"></a>01059     <span class="comment">// [opt] grow the container</span>
 <a name="l01060"></a>01060     <span class="keywordflow">if</span>( grow_segment )
 <a name="l01061"></a>01061         enable_segment( grow_segment );
 <a name="l01062"></a>01062     <span class="keywordflow">if</span>( tmp_n ) <span class="comment">// if op_insert only</span>
 <a name="l01063"></a>01063         delete_node( tmp_n );
 <a name="l01064"></a>01064     <span class="keywordflow">return</span> return_value;
 <a name="l01065"></a>01065 }
 <a name="l01066"></a>01066
 <a name="l01067"></a>01067 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Key, <span class="keyword">typename</span> T, <span class="keyword">typename</span> HashCompare, <span class="keyword">typename</span> A&gt;
 <a name="l01068"></a>01068 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> I&gt;
 <a name="l01069"></a><a class="code" href="a00156.html#976c57edfb7f22b9f91a2e11f141eb4a">01069</a> std::pair&lt;I, I&gt; <a class="code" href="a00156.html">concurrent_hash_map&lt;Key,T,HashCompare,A&gt;::internal_equal_range</a>( <span class="keyword">const</span> Key&amp; key, I end_ )<span class="keyword"> const </span>{
 <a name="l01070"></a>01070     hashcode_t h = my_hash_compare.hash( key );
 <a name="l01071"></a>01071     hashcode_t m = my_mask;
 <a name="l01072"></a>01072     __TBB_ASSERT((m&amp;(m+1))==0, NULL);
 <a name="l01073"></a>01073     h &amp;= m;
 <a name="l01074"></a>01074     bucket *b = get_bucket( h );
 <a name="l01075"></a>01075     <span class="keywordflow">while</span>( b-&gt;node_list == internal::rehash_req ) {
 <a name="l01076"></a>01076         m = ( 1u&lt;&lt;__TBB_Log2( h ) ) - 1; <span class="comment">// get parent mask from the topmost bit</span>
 <a name="l01077"></a>01077         b = get_bucket( h &amp;= m );
 <a name="l01078"></a>01078     }
 <a name="l01079"></a>01079     node *n = search_bucket( key, b );
 <a name="l01080"></a>01080     <span class="keywordflow">if</span>( !n )
 <a name="l01081"></a>01081         <span class="keywordflow">return</span> std::make_pair(end_, end_);
 <a name="l01082"></a>01082     iterator lower(*<span class="keyword">this</span>, h, b, n), upper(lower);
 <a name="l01083"></a>01083     <span class="keywordflow">return</span> std::make_pair(lower, ++upper);
 <a name="l01084"></a>01084 }
 <a name="l01085"></a>01085
 <a name="l01086"></a>01086 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Key, <span class="keyword">typename</span> T, <span class="keyword">typename</span> HashCompare, <span class="keyword">typename</span> A&gt;
 <a name="l01087"></a><a class="code" href="a00156.html#faad2108bd2be75e52293486af59f11e">01087</a> <span class="keywordtype">bool</span> <a class="code" href="a00156.html">concurrent_hash_map&lt;Key,T,HashCompare,A&gt;::exclude</a>( <a class="code" href="a00159.html">const_accessor</a> &amp;item_accessor, <span class="keywordtype">bool</span> readonly ) {
 <a name="l01088"></a>01088     __TBB_ASSERT( item_accessor.<a class="code" href="a00159.html#74e5fd476c306e90361f3377f0fec6d8">my_node</a>, NULL );
 <a name="l01089"></a>01089     node_base *<span class="keyword">const</span> n = item_accessor.<a class="code" href="a00159.html#74e5fd476c306e90361f3377f0fec6d8">my_node</a>;
 <a name="l01090"></a>01090     item_accessor.<a class="code" href="a00159.html#74e5fd476c306e90361f3377f0fec6d8">my_node</a> = NULL; <span class="comment">// we ought release accessor anyway</span>
 <a name="l01091"></a>01091     hashcode_t <span class="keyword">const</span> h = item_accessor.<a class="code" href="a00159.html#88e677d4e26a67d65d81af524ddd483a">my_hash</a>;
 <a name="l01092"></a>01092 <span class="preprocessor">#if TBB_USE_THREADING_TOOLS</span>
 <a name="l01093"></a>01093 <span class="preprocessor"></span>    hashcode_t m = (hashcode_t) itt_load_pointer_with_acquire_v3( &amp;my_mask );
 <a name="l01094"></a>01094 <span class="preprocessor">#else</span>
 <a name="l01095"></a>01095 <span class="preprocessor"></span>    hashcode_t m = my_mask;
 <a name="l01096"></a>01096 <span class="preprocessor">#endif</span>
 <a name="l01097"></a>01097 <span class="preprocessor"></span>    <span class="keywordflow">do</span> {
 <a name="l01098"></a>01098         <span class="comment">// get bucket</span>
 <a name="l01099"></a>01099         <a class="code" href="a00158.html">bucket_accessor</a> b( <span class="keyword">this</span>, h &amp; m, <span class="comment">/*writer=*/</span><span class="keyword">true</span> );
 <a name="l01100"></a>01100         node_base **p = &amp;b()-&gt;node_list;
 <a name="l01101"></a>01101         <span class="keywordflow">while</span>( *p &amp;&amp; *p != n )
 <a name="l01102"></a>01102             p = &amp;(*p)-&gt;next;
 <a name="l01103"></a>01103         <span class="keywordflow">if</span>( !*p ) { <span class="comment">// someone else was the first</span>
 <a name="l01104"></a>01104             <span class="keywordflow">if</span>( check_mask_race( h, m ) )
 <a name="l01105"></a>01105                 <span class="keywordflow">continue</span>;
 <a name="l01106"></a>01106             item_accessor.<a class="code" href="a00159.html#b57d7e72014cd2ae5a915606410615ce">my_lock</a>.release();
 <a name="l01107"></a>01107             <span class="keywordflow">return</span> <span class="keyword">false</span>;
 <a name="l01108"></a>01108         }
 <a name="l01109"></a>01109         __TBB_ASSERT( *p == n, NULL );
 <a name="l01110"></a>01110         *p = n-&gt;next; <span class="comment">// remove from container</span>
 <a name="l01111"></a>01111         my_size--;
 <a name="l01112"></a>01112         <span class="keywordflow">break</span>;
 <a name="l01113"></a>01113     } <span class="keywordflow">while</span>(<span class="keyword">true</span>);
 <a name="l01114"></a>01114     <span class="keywordflow">if</span>( readonly ) <span class="comment">// need to get exclusive lock</span>
 <a name="l01115"></a>01115         item_accessor.<a class="code" href="a00159.html#b57d7e72014cd2ae5a915606410615ce">my_lock</a>.upgrade_to_writer(); <span class="comment">// return value means nothing here</span>
 <a name="l01116"></a>01116     item_accessor.<a class="code" href="a00159.html#b57d7e72014cd2ae5a915606410615ce">my_lock</a>.release();
 <a name="l01117"></a>01117     delete_node( n ); <span class="comment">// Only one thread can delete it due to write lock on the chain_mutex</span>
 <a name="l01118"></a>01118     <span class="keywordflow">return</span> <span class="keyword">true</span>;
 <a name="l01119"></a>01119 }
 <a name="l01120"></a>01120
 <a name="l01121"></a>01121 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Key, <span class="keyword">typename</span> T, <span class="keyword">typename</span> HashCompare, <span class="keyword">typename</span> A&gt;
 <a name="l01122"></a><a class="code" href="a00156.html#034c3b3ee419edee78e0f2f2b1f0d7ca">01122</a> <span class="keywordtype">bool</span> <a class="code" href="a00156.html">concurrent_hash_map&lt;Key,T,HashCompare,A&gt;::erase</a>( <span class="keyword">const</span> Key &amp;key ) {
 <a name="l01123"></a>01123     node_base *n;
 <a name="l01124"></a>01124     hashcode_t <span class="keyword">const</span> h = my_hash_compare.hash( key );
 <a name="l01125"></a>01125 <span class="preprocessor">#if TBB_USE_THREADING_TOOLS</span>
 <a name="l01126"></a>01126 <span class="preprocessor"></span>    hashcode_t m = (hashcode_t) itt_load_pointer_with_acquire_v3( &amp;my_mask );
 <a name="l01127"></a>01127 <span class="preprocessor">#else</span>
 <a name="l01128"></a>01128 <span class="preprocessor"></span>    hashcode_t m = my_mask;
 <a name="l01129"></a>01129 <span class="preprocessor">#endif</span>
 <a name="l01130"></a>01130 <span class="preprocessor"></span>restart:
 <a name="l01131"></a>01131     {<span class="comment">//lock scope</span>
 <a name="l01132"></a>01132         <span class="comment">// get bucket</span>
 <a name="l01133"></a>01133         <a class="code" href="a00158.html">bucket_accessor</a> b( <span class="keyword">this</span>, h &amp; m );
 <a name="l01134"></a>01134     search:
 <a name="l01135"></a>01135         node_base **p = &amp;b()-&gt;node_list;
 <a name="l01136"></a>01136         n = *p;
 <a name="l01137"></a>01137         <span class="keywordflow">while</span>( is_valid(n) &amp;&amp; !my_hash_compare.equal(key, static_cast&lt;node*&gt;(n)-&gt;item.first ) ) {
 <a name="l01138"></a>01138             p = &amp;n-&gt;next;
 <a name="l01139"></a>01139             n = *p;
 <a name="l01140"></a>01140         }
 <a name="l01141"></a>01141         <span class="keywordflow">if</span>( !n ) { <span class="comment">// not found, but mask could be changed</span>
 <a name="l01142"></a>01142             <span class="keywordflow">if</span>( check_mask_race( h, m ) )
 <a name="l01143"></a>01143                 <span class="keywordflow">goto</span> restart;
 <a name="l01144"></a>01144             <span class="keywordflow">return</span> <span class="keyword">false</span>;
 <a name="l01145"></a>01145         }
 <a name="l01146"></a>01146         <span class="keywordflow">else</span> <span class="keywordflow">if</span>( !b.<a class="code" href="a00158.html#fc194e3a186dc935a5fb513cc9f8e898">is_writer</a>() &amp;&amp; !b.<a class="code" href="a00158.html#8f7f0dc61f528de29d06e6054b4a9835">upgrade_to_writer</a>() ) {
 <a name="l01147"></a>01147             <span class="keywordflow">if</span>( check_mask_race( h, m ) ) <span class="comment">// contended upgrade, check mask</span>
 <a name="l01148"></a>01148                 <span class="keywordflow">goto</span> restart;
 <a name="l01149"></a>01149             <span class="keywordflow">goto</span> search;
 <a name="l01150"></a>01150         }
 <a name="l01151"></a>01151         *p = n-&gt;next;
 <a name="l01152"></a>01152         my_size--;
 <a name="l01153"></a>01153     }
 <a name="l01154"></a>01154     {
 <a name="l01155"></a>01155         <span class="keyword">typename</span> node::scoped_t item_locker( n-&gt;mutex, <span class="comment">/*write=*/</span><span class="keyword">true</span> );
 <a name="l01156"></a>01156     }
 <a name="l01157"></a>01157     <span class="comment">// note: there should be no threads pretending to acquire this mutex again, do not try to upgrade const_accessor!</span>
 <a name="l01158"></a>01158     delete_node( n ); <span class="comment">// Only one thread can delete it due to write lock on the bucket</span>
 <a name="l01159"></a>01159     <span class="keywordflow">return</span> <span class="keyword">true</span>;
 <a name="l01160"></a>01160 }
 <a name="l01161"></a>01161
 <a name="l01162"></a>01162 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Key, <span class="keyword">typename</span> T, <span class="keyword">typename</span> HashCompare, <span class="keyword">typename</span> A&gt;
 <a name="l01163"></a>01163 <span class="keywordtype">void</span> <a class="code" href="a00156.html">concurrent_hash_map&lt;Key,T,HashCompare,A&gt;::swap</a>(<a class="code" href="a00156.html">concurrent_hash_map&lt;Key,T,HashCompare,A&gt;</a> &amp;table) {
 <a name="l01164"></a>01164     std::swap(this-&gt;my_allocator, table.<a class="code" href="a00156.html#252e91d8029f6308db7179557e3b1436">my_allocator</a>);
 <a name="l01165"></a>01165     std::swap(this-&gt;my_hash_compare, table.<a class="code" href="a00156.html#f738f241c8500ce3dbf0f9028ca8b602">my_hash_compare</a>);
 <a name="l01166"></a>01166     internal_swap(table);
 <a name="l01167"></a>01167 }
 <a name="l01168"></a>01168
 <a name="l01169"></a>01169 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Key, <span class="keyword">typename</span> T, <span class="keyword">typename</span> HashCompare, <span class="keyword">typename</span> A&gt;
 <a name="l01170"></a><a class="code" href="a00156.html#13f3f2e8de7564be03882c31559493c9">01170</a> <span class="keywordtype">void</span> <a class="code" href="a00156.html">concurrent_hash_map&lt;Key,T,HashCompare,A&gt;::rehash</a>(size_type sz) {
 <a name="l01171"></a>01171     reserve( sz ); <span class="comment">// TODO: add reduction of number of buckets as well</span>
 <a name="l01172"></a>01172     hashcode_t mask = my_mask;
 <a name="l01173"></a>01173     hashcode_t b = (mask+1)&gt;&gt;1; <span class="comment">// size or first index of the last segment</span>
 <a name="l01174"></a>01174     __TBB_ASSERT((b&amp;(b-1))==0, NULL);
 <a name="l01175"></a>01175     bucket *bp = get_bucket( b ); <span class="comment">// only the last segment should be scanned for rehashing</span>
 <a name="l01176"></a>01176     <span class="keywordflow">for</span>(; b &lt;= mask; b++, bp++ ) {
 <a name="l01177"></a>01177         node_base *n = bp-&gt;node_list;
 <a name="l01178"></a>01178         __TBB_ASSERT( is_valid(n) || n == internal::empty_rehashed || n == internal::rehash_req, <span class="stringliteral">"Broken internal structure"</span> );
 <a name="l01179"></a>01179         __TBB_ASSERT( *reinterpret_cast&lt;intptr_t*&gt;(&amp;bp-&gt;mutex) == 0, <span class="stringliteral">"concurrent or unexpectedly terminated operation during rehash() execution"</span> );
 <a name="l01180"></a>01180         <span class="keywordflow">if</span>( n == internal::rehash_req ) { <span class="comment">// rehash bucket, conditional because rehashing of a previous bucket may affect this one</span>
 <a name="l01181"></a>01181             hashcode_t h = b; bucket *b_old = bp;
 <a name="l01182"></a>01182             <span class="keywordflow">do</span> {
 <a name="l01183"></a>01183                 __TBB_ASSERT( h &gt; 1, <span class="stringliteral">"The lowermost buckets can't be rehashed"</span> );
 <a name="l01184"></a>01184                 hashcode_t m = ( 1u&lt;&lt;__TBB_Log2( h ) ) - 1; <span class="comment">// get parent mask from the topmost bit</span>
 <a name="l01185"></a>01185                 b_old = get_bucket( h &amp;= m );
 <a name="l01186"></a>01186             } <span class="keywordflow">while</span>( b_old-&gt;node_list == internal::rehash_req );
 <a name="l01187"></a>01187             <span class="comment">// now h - is index of the root rehashed bucket b_old</span>
 <a name="l01188"></a>01188             mark_rehashed_levels( h ); <span class="comment">// mark all non-rehashed children recursively across all segments</span>
 <a name="l01189"></a>01189             <span class="keywordflow">for</span>( node_base **p = &amp;b_old-&gt;node_list, *q = *p; is_valid(q); q = *p ) {
 <a name="l01190"></a>01190                 hashcode_t c = my_hash_compare.hash( static_cast&lt;node*&gt;(q)-&gt;item.first );
 <a name="l01191"></a>01191                 <span class="keywordflow">if</span>( (c &amp; mask) != h ) { <span class="comment">// should be rehashed</span>
 <a name="l01192"></a>01192                     *p = q-&gt;next; <span class="comment">// exclude from b_old</span>
 <a name="l01193"></a>01193                     bucket *b_new = get_bucket( c &amp; mask );
 <a name="l01194"></a>01194                     __TBB_ASSERT( b_new-&gt;node_list != internal::rehash_req, <span class="stringliteral">"hash() function changed for key in table or internal error"</span> );
 <a name="l01195"></a>01195                     add_to_bucket( b_new, q );
 <a name="l01196"></a>01196                 } <span class="keywordflow">else</span> p = &amp;q-&gt;next; <span class="comment">// iterate to next item</span>
 <a name="l01197"></a>01197             }
 <a name="l01198"></a>01198         }
 <a name="l01199"></a>01199     }
 <a name="l01200"></a>01200 <span class="preprocessor">#if TBB_USE_PERFORMANCE_WARNINGS</span>
 <a name="l01201"></a>01201 <span class="preprocessor"></span>    <span class="keywordtype">int</span> current_size = int(my_size), buckets = int(mask)+1, empty_buckets = 0, overpopulated_buckets = 0; <span class="comment">// usage statistics</span>
 <a name="l01202"></a>01202     <span class="keyword">static</span> <span class="keywordtype">bool</span> reported = <span class="keyword">false</span>;
 <a name="l01203"></a>01203 <span class="preprocessor">#endif</span>
 <a name="l01204"></a>01204 <span class="preprocessor"></span><span class="preprocessor">#if TBB_USE_ASSERT || TBB_USE_PERFORMANCE_WARNINGS</span>
 <a name="l01205"></a>01205 <span class="preprocessor"></span>    <span class="keywordflow">for</span>( b = 0; b &lt;= mask; b++ ) {<span class="comment">// only last segment should be scanned for rehashing</span>
 <a name="l01206"></a>01206         <span class="keywordflow">if</span>( b &amp; (b-2) ) ++bp; <span class="comment">// not the beginning of a segment</span>
 <a name="l01207"></a>01207         <span class="keywordflow">else</span> bp = get_bucket( b );
 <a name="l01208"></a>01208         node_base *n = bp-&gt;node_list;
 <a name="l01209"></a>01209         __TBB_ASSERT( *reinterpret_cast&lt;intptr_t*&gt;(&amp;bp-&gt;mutex) == 0, <span class="stringliteral">"concurrent or unexpectedly terminated operation during rehash() execution"</span> );
 <a name="l01210"></a>01210         __TBB_ASSERT( is_valid(n) || n == internal::empty_rehashed, <span class="stringliteral">"Broken internal structure"</span> );
 <a name="l01211"></a>01211 <span class="preprocessor">#if TBB_USE_PERFORMANCE_WARNINGS</span>
 <a name="l01212"></a>01212 <span class="preprocessor"></span>        <span class="keywordflow">if</span>( n == internal::empty_rehashed ) empty_buckets++;
 <a name="l01213"></a>01213         <span class="keywordflow">else</span> <span class="keywordflow">if</span>( n-&gt;next ) overpopulated_buckets++;
 <a name="l01214"></a>01214 <span class="preprocessor">#endif</span>
 <a name="l01215"></a>01215 <span class="preprocessor"></span><span class="preprocessor">#if TBB_USE_ASSERT</span>
 <a name="l01216"></a>01216 <span class="preprocessor"></span>        <span class="keywordflow">for</span>( ; is_valid(n); n = n-&gt;next ) {
 <a name="l01217"></a>01217             hashcode_t h = my_hash_compare.hash( static_cast&lt;node*&gt;(n)-&gt;item.first ) &amp; mask;
 <a name="l01218"></a>01218             __TBB_ASSERT( h == b, <span class="stringliteral">"hash() function changed for key in table or internal error"</span> );
 <a name="l01219"></a>01219         }
 <a name="l01220"></a>01220 <span class="preprocessor">#endif</span>
 <a name="l01221"></a>01221 <span class="preprocessor"></span>    }
 <a name="l01222"></a>01222 <span class="preprocessor">#endif // TBB_USE_ASSERT || TBB_USE_PERFORMANCE_WARNINGS</span>
 <a name="l01223"></a>01223 <span class="preprocessor"></span><span class="preprocessor">#if TBB_USE_PERFORMANCE_WARNINGS</span>
 <a name="l01224"></a>01224 <span class="preprocessor"></span>    <span class="keywordflow">if</span>( buckets &gt; current_size) empty_buckets -= buckets - current_size;
 <a name="l01225"></a>01225     <span class="keywordflow">else</span> overpopulated_buckets -= current_size - buckets; <span class="comment">// TODO: load_factor?</span>
 <a name="l01226"></a>01226     <span class="keywordflow">if</span>( !reported &amp;&amp; buckets &gt;= 512 &amp;&amp; ( 2*empty_buckets &gt; current_size || 2*overpopulated_buckets &gt; current_size ) ) {
 <a name="l01227"></a>01227         tbb::internal::runtime_warning(
 <a name="l01228"></a>01228             <span class="stringliteral">"Performance is not optimal because the hash function produces bad randomness in lower bits in %s.\nSize: %d  Empties: %d  Overlaps: %d"</span>,
 <a name="l01229"></a>01229             <span class="keyword">typeid</span>(*this).name(), current_size, empty_buckets, overpopulated_buckets );
 <a name="l01230"></a>01230         reported = <span class="keyword">true</span>;
 <a name="l01231"></a>01231     }
 <a name="l01232"></a>01232 <span class="preprocessor">#endif</span>
 <a name="l01233"></a>01233 <span class="preprocessor"></span>}
 <a name="l01234"></a>01234
 <a name="l01235"></a>01235 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Key, <span class="keyword">typename</span> T, <span class="keyword">typename</span> HashCompare, <span class="keyword">typename</span> A&gt;
 <a name="l01236"></a><a class="code" href="a00156.html#a9f89be8fe28835749529d91081a2511">01236</a> <span class="keywordtype">void</span> <a class="code" href="a00156.html">concurrent_hash_map&lt;Key,T,HashCompare,A&gt;::clear</a>() {
 <a name="l01237"></a>01237     hashcode_t m = my_mask;
 <a name="l01238"></a>01238     __TBB_ASSERT((m&amp;(m+1))==0, NULL);
 <a name="l01239"></a>01239 <span class="preprocessor">#if TBB_USE_ASSERT || TBB_USE_PERFORMANCE_WARNINGS</span>
 <a name="l01240"></a>01240 <span class="preprocessor"></span><span class="preprocessor">#if TBB_USE_PERFORMANCE_WARNINGS</span>
 <a name="l01241"></a>01241 <span class="preprocessor"></span>    <span class="keywordtype">int</span> current_size = int(my_size), buckets = int(m)+1, empty_buckets = 0, overpopulated_buckets = 0; <span class="comment">// usage statistics</span>
 <a name="l01242"></a>01242     <span class="keyword">static</span> <span class="keywordtype">bool</span> reported = <span class="keyword">false</span>;
 <a name="l01243"></a>01243 <span class="preprocessor">#endif</span>
 <a name="l01244"></a>01244 <span class="preprocessor"></span>    bucket *bp = 0;
 <a name="l01245"></a>01245     <span class="comment">// check consistency</span>
 <a name="l01246"></a>01246     <span class="keywordflow">for</span>( segment_index_t b = 0; b &lt;= m; b++ ) {
 <a name="l01247"></a>01247         <span class="keywordflow">if</span>( b &amp; (b-2) ) ++bp; <span class="comment">// not the beginning of a segment</span>
 <a name="l01248"></a>01248         <span class="keywordflow">else</span> bp = get_bucket( b );
 <a name="l01249"></a>01249         node_base *n = bp-&gt;node_list;
 <a name="l01250"></a>01250         __TBB_ASSERT( is_valid(n) || n == internal::empty_rehashed || n == internal::rehash_req, <span class="stringliteral">"Broken internal structure"</span> );
 <a name="l01251"></a>01251         __TBB_ASSERT( *reinterpret_cast&lt;intptr_t*&gt;(&amp;bp-&gt;mutex) == 0, <span class="stringliteral">"concurrent or unexpectedly terminated operation during clear() execution"</span> );
 <a name="l01252"></a>01252 <span class="preprocessor">#if TBB_USE_PERFORMANCE_WARNINGS</span>
 <a name="l01253"></a>01253 <span class="preprocessor"></span>        <span class="keywordflow">if</span>( n == internal::empty_rehashed ) empty_buckets++;
 <a name="l01254"></a>01254         <span class="keywordflow">else</span> <span class="keywordflow">if</span>( n == internal::rehash_req ) buckets--;
 <a name="l01255"></a>01255         <span class="keywordflow">else</span> <span class="keywordflow">if</span>( n-&gt;next ) overpopulated_buckets++;
 <a name="l01256"></a>01256 <span class="preprocessor">#endif</span>
 <a name="l01257"></a>01257 <span class="preprocessor"></span><span class="preprocessor">#if __TBB_EXTRA_DEBUG</span>
 <a name="l01258"></a>01258 <span class="preprocessor"></span>        <span class="keywordflow">for</span>(; is_valid(n); n = n-&gt;next ) {
 <a name="l01259"></a>01259             hashcode_t h = my_hash_compare.hash( static_cast&lt;node*&gt;(n)-&gt;item.first );
 <a name="l01260"></a>01260             h &amp;= m;
 <a name="l01261"></a>01261             __TBB_ASSERT( h == b || get_bucket(h)-&gt;node_list == internal::rehash_req, <span class="stringliteral">"hash() function changed for key in table or internal error"</span> );
 <a name="l01262"></a>01262         }
 <a name="l01263"></a>01263 <span class="preprocessor">#endif</span>
 <a name="l01264"></a>01264 <span class="preprocessor"></span>    }
 <a name="l01265"></a>01265 <span class="preprocessor">#if TBB_USE_PERFORMANCE_WARNINGS</span>
 <a name="l01266"></a>01266 <span class="preprocessor"></span>    <span class="keywordflow">if</span>( buckets &gt; current_size) empty_buckets -= buckets - current_size;
 <a name="l01267"></a>01267     <span class="keywordflow">else</span> overpopulated_buckets -= current_size - buckets; <span class="comment">// TODO: load_factor?</span>
 <a name="l01268"></a>01268     <span class="keywordflow">if</span>( !reported &amp;&amp; buckets &gt;= 512 &amp;&amp; ( 2*empty_buckets &gt; current_size || 2*overpopulated_buckets &gt; current_size ) ) {
 <a name="l01269"></a>01269         tbb::internal::runtime_warning(
 <a name="l01270"></a>01270             <span class="stringliteral">"Performance is not optimal because the hash function produces bad randomness in lower bits in %s.\nSize: %d  Empties: %d  Overlaps: %d"</span>,
 <a name="l01271"></a>01271             <span class="keyword">typeid</span>(*this).name(), current_size, empty_buckets, overpopulated_buckets );
 <a name="l01272"></a>01272         reported = <span class="keyword">true</span>;
 <a name="l01273"></a>01273     }
 <a name="l01274"></a>01274 <span class="preprocessor">#endif</span>
 <a name="l01275"></a>01275 <span class="preprocessor"></span><span class="preprocessor">#endif//TBB_USE_ASSERT || TBB_USE_PERFORMANCE_WARNINGS</span>
 <a name="l01276"></a>01276 <span class="preprocessor"></span>    my_size = 0;
 <a name="l01277"></a>01277     segment_index_t s = segment_index_of( m );
 <a name="l01278"></a>01278     __TBB_ASSERT( s+1 == pointers_per_table || !my_table[s+1], <span class="stringliteral">"wrong mask or concurrent grow"</span> );
 <a name="l01279"></a>01279     <a class="code" href="a00151.html">cache_aligned_allocator&lt;bucket&gt;</a> alloc;
 <a name="l01280"></a>01280     <span class="keywordflow">do</span> {
 <a name="l01281"></a>01281         __TBB_ASSERT( is_valid( my_table[s] ), <span class="stringliteral">"wrong mask or concurrent grow"</span> );
 <a name="l01282"></a>01282         segment_ptr_t buckets_ptr = my_table[s];
 <a name="l01283"></a>01283         size_type sz = segment_size( s ? s : 1 );
 <a name="l01284"></a>01284         <span class="keywordflow">for</span>( segment_index_t i = 0; i &lt; sz; i++ )
 <a name="l01285"></a>01285             <span class="keywordflow">for</span>( node_base *n = buckets_ptr[i].node_list; is_valid(n); n = buckets_ptr[i].node_list ) {
 <a name="l01286"></a>01286                 buckets_ptr[i].node_list = n-&gt;next;
 <a name="l01287"></a>01287                 delete_node( n );
 <a name="l01288"></a>01288             }
 <a name="l01289"></a>01289         <span class="keywordflow">if</span>( s &gt;= first_block) <span class="comment">// the first segment or the next</span>
 <a name="l01290"></a>01290             alloc.<a class="code" href="a00151.html#3d4eadf188f7d85d3805ae534e0b8e1c">deallocate</a>( buckets_ptr, sz );
 <a name="l01291"></a>01291         <span class="keywordflow">else</span> <span class="keywordflow">if</span>( s == embedded_block &amp;&amp; embedded_block != first_block )
 <a name="l01292"></a>01292             alloc.<a class="code" href="a00151.html#3d4eadf188f7d85d3805ae534e0b8e1c">deallocate</a>( buckets_ptr, segment_size(first_block)-embedded_buckets );
 <a name="l01293"></a>01293         <span class="keywordflow">if</span>( s &gt;= embedded_block ) my_table[s] = 0;
 <a name="l01294"></a>01294     } <span class="keywordflow">while</span>(s-- &gt; 0);
 <a name="l01295"></a>01295     my_mask = embedded_buckets - 1;
 <a name="l01296"></a>01296 }
 <a name="l01297"></a>01297
 <a name="l01298"></a>01298 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Key, <span class="keyword">typename</span> T, <span class="keyword">typename</span> HashCompare, <span class="keyword">typename</span> A&gt;
 <a name="l01299"></a><a class="code" href="a00156.html#3c27779fe66b79505390d084310d997e">01299</a> <span class="keywordtype">void</span> <a class="code" href="a00156.html">concurrent_hash_map&lt;Key,T,HashCompare,A&gt;::internal_copy</a>( <span class="keyword">const</span> <a class="code" href="a00156.html">concurrent_hash_map</a>&amp; source ) {
 <a name="l01300"></a>01300     reserve( source.my_size ); <span class="comment">// TODO: load_factor?</span>
 <a name="l01301"></a>01301     hashcode_t mask = source.my_mask;
 <a name="l01302"></a>01302     <span class="keywordflow">if</span>( my_mask == mask ) { <span class="comment">// optimized version</span>
 <a name="l01303"></a>01303         bucket *dst = 0, *src = 0;
 <a name="l01304"></a>01304         <span class="keywordtype">bool</span> rehash_required = <span class="keyword">false</span>;
 <a name="l01305"></a>01305         <span class="keywordflow">for</span>( hashcode_t k = 0; k &lt;= mask; k++ ) {
 <a name="l01306"></a>01306             <span class="keywordflow">if</span>( k &amp; (k-2) ) ++dst,src++; <span class="comment">// not the beginning of a segment</span>
 <a name="l01307"></a>01307             <span class="keywordflow">else</span> { dst = get_bucket( k ); src = source.get_bucket( k ); }
 <a name="l01308"></a>01308             __TBB_ASSERT( dst-&gt;node_list != internal::rehash_req, <span class="stringliteral">"Invalid bucket in destination table"</span>);
 <a name="l01309"></a>01309             node *n = static_cast&lt;node*&gt;( src-&gt;node_list );
 <a name="l01310"></a>01310             <span class="keywordflow">if</span>( n == internal::rehash_req ) { <span class="comment">// source is not rehashed, items are in previous buckets</span>
 <a name="l01311"></a>01311                 rehash_required = <span class="keyword">true</span>;
 <a name="l01312"></a>01312                 dst-&gt;node_list = internal::rehash_req;
 <a name="l01313"></a>01313             } <span class="keywordflow">else</span> <span class="keywordflow">for</span>(; n; n = static_cast&lt;node*&gt;( n-&gt;next ) ) {
 <a name="l01314"></a>01314                 add_to_bucket( dst, <span class="keyword">new</span>( my_allocator ) node(n-&gt;item.first, n-&gt;item.second) );
 <a name="l01315"></a>01315                 ++my_size; <span class="comment">// TODO: replace by non-atomic op</span>
 <a name="l01316"></a>01316             }
 <a name="l01317"></a>01317         }
 <a name="l01318"></a>01318         <span class="keywordflow">if</span>( rehash_required ) <a class="code" href="a00156.html#13f3f2e8de7564be03882c31559493c9">rehash</a>();
 <a name="l01319"></a>01319     } <span class="keywordflow">else</span> <a class="code" href="a00156.html#3c27779fe66b79505390d084310d997e">internal_copy</a>( source.<a class="code" href="a00156.html#4a3c58cf1234b74ca796dcf555d32f53">begin</a>(), source.<a class="code" href="a00156.html#28c690486d8db5783475f5b1a59d21bc">end</a>() );
 <a name="l01320"></a>01320 }
 <a name="l01321"></a>01321
 <a name="l01322"></a>01322 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Key, <span class="keyword">typename</span> T, <span class="keyword">typename</span> HashCompare, <span class="keyword">typename</span> A&gt;
 <a name="l01323"></a>01323 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> I&gt;
 <a name="l01324"></a>01324 <span class="keywordtype">void</span> <a class="code" href="a00156.html">concurrent_hash_map&lt;Key,T,HashCompare,A&gt;::internal_copy</a>(I first, I last) {
 <a name="l01325"></a>01325     hashcode_t m = my_mask;
 <a name="l01326"></a>01326     <span class="keywordflow">for</span>(; first != last; ++first) {
 <a name="l01327"></a>01327         hashcode_t h = my_hash_compare.hash( first-&gt;first );
 <a name="l01328"></a>01328         bucket *b = get_bucket( h &amp; m );
 <a name="l01329"></a>01329         __TBB_ASSERT( b-&gt;node_list != internal::rehash_req, <span class="stringliteral">"Invalid bucket in destination table"</span>);
 <a name="l01330"></a>01330         node *n = <span class="keyword">new</span>( my_allocator ) node(first-&gt;first, first-&gt;second);
 <a name="l01331"></a>01331         add_to_bucket( b, n );
 <a name="l01332"></a>01332         ++my_size; <span class="comment">// TODO: replace by non-atomic op</span>
 <a name="l01333"></a>01333     }
 <a name="l01334"></a>01334 }
 <a name="l01335"></a>01335
 <a name="l01336"></a>01336 } <span class="comment">// namespace interface4</span>
 <a name="l01337"></a>01337
 <a name="l01338"></a>01338 <span class="keyword">using</span> interface4::concurrent_hash_map;
 <a name="l01339"></a>01339
 <a name="l01340"></a>01340
 <a name="l01341"></a>01341 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Key, <span class="keyword">typename</span> T, <span class="keyword">typename</span> HashCompare, <span class="keyword">typename</span> A1, <span class="keyword">typename</span> A2&gt;
 <a name="l01342"></a>01342 <span class="keyword">inline</span> <span class="keywordtype">bool</span> operator==(<span class="keyword">const</span> concurrent_hash_map&lt;Key, T, HashCompare, A1&gt; &amp;a, <span class="keyword">const</span> concurrent_hash_map&lt;Key, T, HashCompare, A2&gt; &amp;b) {
 <a name="l01343"></a>01343     <span class="keywordflow">if</span>(a.size() != b.size()) <span class="keywordflow">return</span> <span class="keyword">false</span>;
 <a name="l01344"></a>01344     <span class="keyword">typename</span> concurrent_hash_map&lt;Key, T, HashCompare, A1&gt;::const_iterator i(a.begin()), i_end(a.end());
 <a name="l01345"></a>01345     <span class="keyword">typename</span> concurrent_hash_map&lt;Key, T, HashCompare, A2&gt;::const_iterator j, j_end(b.end());
 <a name="l01346"></a>01346     <span class="keywordflow">for</span>(; i != i_end; ++i) {
 <a name="l01347"></a>01347         j = b.equal_range(i-&gt;first).first;
 <a name="l01348"></a>01348         <span class="keywordflow">if</span>( j == j_end || !(i-&gt;second == j-&gt;second) ) <span class="keywordflow">return</span> <span class="keyword">false</span>;
 <a name="l01349"></a>01349     }
 <a name="l01350"></a>01350     <span class="keywordflow">return</span> <span class="keyword">true</span>;
 <a name="l01351"></a>01351 }
 <a name="l01352"></a>01352
 <a name="l01353"></a>01353 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Key, <span class="keyword">typename</span> T, <span class="keyword">typename</span> HashCompare, <span class="keyword">typename</span> A1, <span class="keyword">typename</span> A2&gt;
 <a name="l01354"></a>01354 <span class="keyword">inline</span> <span class="keywordtype">bool</span> operator!=(<span class="keyword">const</span> concurrent_hash_map&lt;Key, T, HashCompare, A1&gt; &amp;a, <span class="keyword">const</span> concurrent_hash_map&lt;Key, T, HashCompare, A2&gt; &amp;b)
 <a name="l01355"></a>01355 {    <span class="keywordflow">return</span> !(a == b); }
 <a name="l01356"></a>01356
 <a name="l01357"></a>01357 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Key, <span class="keyword">typename</span> T, <span class="keyword">typename</span> HashCompare, <span class="keyword">typename</span> A&gt;
 <a name="l01358"></a>01358 <span class="keyword">inline</span> <span class="keywordtype">void</span> swap(concurrent_hash_map&lt;Key, T, HashCompare, A&gt; &amp;a, concurrent_hash_map&lt;Key, T, HashCompare, A&gt; &amp;b)
 <a name="l01359"></a>01359 {    a.swap( b ); }
 <a name="l01360"></a>01360
 <a name="l01361"></a>01361 <span class="preprocessor">#if _MSC_VER &amp;&amp; !defined(__INTEL_COMPILER)</span>
 <a name="l01362"></a>01362 <span class="preprocessor"></span><span class="preprocessor">    #pragma warning( pop )</span>
 <a name="l01363"></a>01363 <span class="preprocessor"></span><span class="preprocessor">#endif // warning 4127 is back</span>
 <a name="l01364"></a>01364 <span class="preprocessor"></span>
 <a name="l01365"></a>01365 } <span class="comment">// namespace tbb</span>
 <a name="l01366"></a>01366
 <a name="l01367"></a>01367 <span class="preprocessor">#endif </span><span class="comment">/* __TBB_concurrent_hash_map_H */</span>
 </pre></div><hr>
 <p></p>
 Copyright &copy; 2005-2010 Intel Corporation.  All Rights Reserved.
 <p></p>
 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.
 <p></p>
 * Other names and brands may be claimed as the property of others.