[LLVMdev] infinite looping on hashtables

[Stuart Hastings]

On OS X, this test:
------------------------------------------------------
#include <llvm/ADT/DenseSet.h>
#include <new>

#include <stdio.h>

int main(int argc, char** argv) {
   llvm::DenseSet<unsigned> set(2);
   set.insert(0);
   set.insert(1);
   if (set.count(2)) printf("error\n");
   return 0;
}
------------------------------------------------------

saved as "dense-map.cpp" and compiled thus:

	% g++ -g -D__STDC_LIMIT_MACROS -D__STDC_CONSTANT_MACROS \
		-I /Developer/usr/local/include dense-map.cpp

hangs on the "set.count(2)" call.

I think this is abusing DenseSet.h, but the bug report says it used to  
work...

There is a simple fix.  Moving this increment "fixes" the test; it  
just prevents the hash table from filling up:

Index: llvm.test/include/llvm/ADT/DenseMap.h
===================================================================
--- llvm.test/include/llvm/ADT/DenseMap.h       (revision 70267)
+++ llvm.test/include/llvm/ADT/DenseMap.h       (working copy)
@@ -346,12 +346,12 @@
      // probe almost the entire table until it found the empty  
bucket.  If the
      // table completely filled with tombstones, no lookup would ever  
succeed,
      // causing infinite loops in lookup.
+    ++NumEntries;
      if (NumEntries*4 >= NumBuckets*3 ||
          NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) {
        this->grow(NumBuckets * 2);
        LookupBucketFor(Key, TheBucket);
      }
-    ++NumEntries;

      // If we are writing over a tombstone, remember this.
      if (!KeyInfoT::isEqual(TheBucket->first, getEmptyKey()))

------------------------------------------------------

Question:  How can I test this?  I was able to create a nifty  
Googletest unit test:

Index: llvm.test/unittests/ADT/DenseSetTest.cpp
===================================================================
--- llvm.test/unittests/ADT/DenseSetTest.cpp    (revision 0)
+++ llvm.test/unittests/ADT/DenseSetTest.cpp    (revision 0)
@@ -0,0 +1,30 @@
+//===- llvm/unittest/ADT/DenseSetTest.cpp - DenseSet unit tests --*- C 
++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open  
Source
+// License. See LICENSE.TXT for details.
+//
+// 
= 
= 
=---------------------------------------------------------------------- 
===//
+
+#include "gtest/gtest.h"
+#include <llvm/ADT/DenseSet.h>
+
+using namespace llvm;
+
+namespace {
+
+// Test fixture
+class DenseSetTest : public testing::Test {
+};
+
+// Test hashing with a set of only two entries.
+TEST_F(DenseSetTest, DoubleEntrySetTest) {
+  llvm::DenseSet<unsigned> set(2);
+  set.insert(0);
+  set.insert(1);
+  // Original failure was an infinite loop in this call:
+  EXPECT_EQ(0, set.count(2));
+}
+
+}
------------------------------------------------------

This test works fine, so long as it passes.  If the observed failure  
happens, it hangs at the set.count(2) call, and the Googletest  
framework apparently doesn't catch hangs.  (At least, it didn't wake  
up after twenty minutes.)

Suggestions?

stuart