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