This reverts commit 617330909f0c26a3f2ab8601a029b9bdca48aa61.

It broke the bots:

/home/clangbuild2/clang-ppc64-2/llvm.src/unittests/ADT/SmallVectorTest.cpp:150: PushPopTest
/home/clangbuild2/clang-ppc64-2/llvm.src/unittests/ADT/SmallVectorTest.cpp:118: Failure
Value of: v[i].getValue()
  Actual: 0
Expected: value
Which is: 2

llvm-svn: 178334

being power-of-two sized.

llvm-svn: 178332

DenseMap's hash function uses slightly more entropy and reduces hash collisions
significantly.  I also experimented with Hashing.h, but it didn't gave a lot of
improvement while being much more expensive to compute.

llvm-svn: 154996

llvm-svn: 152254

This fixes a build failure in webkit. Copying all elements shouldn't be
necessary, I'll look out for a better fix soon.

llvm-svn: 152252

SmallPtrSet: Provide a more efficient implementation of swap than the default triple-copy std::swap.

This currently assumes that both sets have the same SmallSize to keep the implementation simple,
a limitation that can be lifted if someone cares.

llvm-svn: 152143

Rehash but don't grow when full of tombstones.

Patch by José Fonseca!

llvm-svn: 128566

replaced by a bigger array in SmallPtrSet (by overridding it), instead just use a
pointer to the start of the storage, and have SmallPtrSet pass in the value to use.
This has the disadvantage that SmallPtrSet becomes bigger by one pointer.  It has
the advantage that it no longer uses tricky C++ rules, and is clearly correct while
I'm not sure the previous version was.  This was inspired by g++-4.6 pointing out
that SmallPtrSetImpl was writing off the end of SmallArray, which it was.  Since
SmallArray is replaced with a bigger array in SmallPtrSet, the write was still to
valid memory.  But it was writing off the end of the declared array type - sounds
kind of dubious to me, like it sounded dubious to g++-4.6.  Maybe g++-4.6 is wrong
and this construct is perfectly valid and correctly compiled by all compilers, but
I think it is better to avoid the whole can of worms by avoiding this construct.

llvm-svn: 107285

llvm-svn: 54349

llvm-svn: 45418

minor bugs.

llvm-svn: 43782

llvm-svn: 41111

contents of the set were small, deallocate and shrink the set.  This
avoids having us to memset as much data, significantly speeding up
some pathological cases.  For example, this speeds up the verifier
from 0.3899s to 0.0763 (5.1x) on the testcase from PR1432 in a 
release build.

llvm-svn: 40837

llvm-svn: 40556

llvm-svn: 40474

llvm-svn: 40043

would result in calling realloc() on a null pointer.  Instead, if we encounter
this situation, make a normal call to malloc().

llvm-svn: 40014

having that implementation file #include <cstdlib>.

llvm-svn: 39952

llvm-svn: 39926

llvm-svn: 38474

Make the assignment operator for SmallPtrSet return a reference, and fix a long-standing bug in the copy
ctor while I'm at it.

Thanks to Chris Lattner for help with this patch.

llvm-svn: 38470

Patch by Chis Lattner.

llvm-svn: 38467

llvm-svn: 38460

llvm-svn: 37697

 1. Make SmallPtrSet::erase faster in the small case by replacing a memmove
    with a pointer copy.
 2. Fix a bug where the null terminator at the end of the array in the small
    case was not copied

llvm-svn: 37696

llvm-svn: 36016

llvm-svn: 33973

element was in the set.

llvm-svn: 33931

llvm-svn: 33581

llvm-svn: 33578

llvm-svn: 33577