title: TBB concurrent unordered map causes segfault
body: <p>I need to implement a huge hash table which supports multiple threads to insert and get at the same time. The keys are int and the second elements are vectors of object T.</p>
  
  <pre><code>class T { 
          //class definitions here
  }
  </code></pre>
  
  <p>Currently the implementation is helped with tbb::concurrent_unordered_map. On the documentation it seems to allow insertion and traversal at the same time. However, running with multiple pthreads will lead to segmentation fault although sequential test is perfectly fine. Note that there is definitely no erase or pop operations, i.e. the hash table is only allowed to grow.</p>
  
  <pre><code>std::vector&lt;T*&gt; get(int key) {
          //Note that the hash table hashTable is shared by multiple threads
          tbb::concurrent_unordered_map&lt;int, std::vector&lt;T*&gt;&gt;::iterator it = hashTable.find(key);
          if (it != hashTable.end())
                  return it-&gt;second;
          else {
                  std::vector&lt;T*&gt; newvector;
                  return newvector;
          }
  }
  
  void insert(int key, T *t) {
          tbb::concurrent_unordered_map&lt;int, std::vector&lt;T*&gt;&gt;::iterator it = hashTable.find(key);
          if (it != hashTable.end())
                  it-&gt;second.push_back(t);
          else {
                  std::vector&lt;T*&gt; newTs;
                  newTs.push_back(t);
                  hashTable.insert(it, makepair(key, newTs));
          }
  }
  </code></pre>
  
  <p>To debug what happened, I first changed std::vector to tbb::concurrent_vector, and then modify the function get() and insert() as follows.</p>
  
  <pre><code>std::vector&lt;T*&gt; get_test(int key) {
          std::vector&lt;T*&gt; test;
          //Note that the hash table hashTable is shared by multiple threads
          tbb::concurrent_unordered_map&lt;int, tbb::concurrent_vector&lt;T*&gt;&gt;::iterator it = hashTable.find(key);
          if (it != hashTable.end())
                  test.insert(test.end(), it-&gt;second.begin(), it-&gt;second.end());
          for (T* _t : test)
                  if (!_t)
                          printf("Bug happens here!\n"); //Segfault is originated here because a NULL is returned in the vector  
          return test;
  }
  
  void insert_test(int key, T *t) {
          //Here t is guaranteed to be not NULL
          if(!t)
                  std::terminate();
          tbb::concurrent_unordered_map&lt;int, tbb::concurrent_vector&lt;T*&gt;&gt;::iterator it = hashTable.find(key);
          if (it != hashTable.end())
                  it-&gt;second.push_back(t);
          else {
                  std::vector&lt;T*&gt; newTs;
                  newTs.push_back(t);
                  hashTable.insert(it, makepair(key, newTs));
          }
  }
  </code></pre>
  
  <p>Now we can see the reason that the parallel program crashes is some NULL pointer is returned in get_test() function. Recall that in insert_test() function NULL is never inserted as the second elements. </p>
  
  <p>The following are the questions to ask.</p>
  
  <p>(1) I read from somewhere that concurrent insertion in tbb::concurrent_unordered_map may cause some of the insertion attempt failed and then the temp objects is destroyed. Is this the reason that NULL is observed in get_test() function?</p>
  
  <p>(2) Can TBB really allow insertion and traversal at the same time? This means while some threads are inserting, the others might call get() at the same time. </p>
  
  <p>(3) Is there any better implementation, i.e. better concurrent hash table that support concurrent insert and read?</p>
  
  <hr>
  
  <p>As @for_stack suggested, I have verified the second elements are concurrent_vectors and the entire program is runnable. A further test is conducted as follows:</p>
  
  <pre><code>tbb::concurrent_vector&lt;T*&gt; get_test(int key) {
              tbb::concurrent_vector&lt;T*&gt; test;
              //Note that the hash table hashTable is shared by multiple threads
              tbb::concurrent_unordered_map&lt;int, tbb::concurrent_vector&lt;T*&gt;&gt;::iterator it = hashTable.find(key);
              if (it != hashTable.end())
                      test = it-&gt;second;
              int i = 0;
              for (T* _t : test)
                      if (!_t)
                              i++;
              if (i &gt; 0)
                      printf("%d of %lu Ts are NULL\n", i, test.size()); //Segfault is originated here because a NULL is returned in the vector  
              return test;
  }
  
  void insert_test(int key, T *t) {
          //Here t is guaranteed to be not NULL
          if(!t)
                  std::terminate();
          tbb::concurrent_unordered_map&lt;int, tbb::concurrent_vector&lt;T*&gt;&gt;::iterator it = hashTable.find(key);
          if (it != hashTable.end())
                  it-&gt;second.push_back(t);
          else {
                  tbb::concurrent_vector&lt;T*&gt; newTs;
                  newTs.push_back(t);
                  hashTable.insert(it, make_pair(key, newTs));
          }
  }
  </code></pre>
  
  <p>The output is</p>
  
  <pre><code>1 of 2 Ts are NULL
  </code></pre>
  
  <p>This means not all objects (T) returned in get() are NULL.  </p>
  
  <hr>
  
  <p>Again the sequential (or even 1 thread) running is fine.</p>