Add a Briggs and Torczon sparse set implementation.

For objects that can be identified by small unsigned keys, SparseSet
provides constant time clear() and fast deterministic iteration. Insert,
erase, and find operations are typically faster than hash tables.

SparseSet is useful for keeping information about physical registers,
virtual registers, or numbered basic blocks.

llvm-svn: 151110

1 files changed, 19 insertions, 0 deletions

diff --git a/llvm/docs/ProgrammersManual.html b/llvm/docs/ProgrammersManual.html
index 0b1a875da1a..f4c03222b20 100644
--- a/llvm/docs/ProgrammersManual.html
+++ b/llvm/docs/ProgrammersManual.html
@@ -81,6 +81,7 @@ option</a></li>
       <li><a href="#dss_smallset">"llvm/ADT/SmallSet.h"</a></li>
       <li><a href="#dss_smallptrset">"llvm/ADT/SmallPtrSet.h"</a></li>
       <li><a href="#dss_denseset">"llvm/ADT/DenseSet.h"</a></li>
+      <li><a href="#dss_sparseset">"llvm/ADT/SparseSet.h"</a></li>
       <li><a href="#dss_FoldingSet">"llvm/ADT/FoldingSet.h"</a></li>
       <li><a href="#dss_set">&lt;set&gt;</a></li>
       <li><a href="#dss_setvector">"llvm/ADT/SetVector.h"</a></li>
@@ -1490,6 +1491,24 @@ href="#dss_densemap">DenseMap</a> has.
 
 <!-- _______________________________________________________________________ -->
 <h4>
+  <a name="dss_sparseset">"llvm/ADT/SparseSet.h"</a>
+</h4>
+
+<div>
+
+<p>SparseSet holds a small number of objects identified by unsigned keys of
+moderate size. It uses a lot of memory, but provides operations that are
+almost as fast as a vector. Typical keys are physical registers, virtual
+registers, or numbered basic blocks.</p>
+
+<p>SparseSet is useful for algorithms that need very fast clear/find/insert/erase
+and fast iteration over small sets.  It is not intended for building composite
+data structures.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<h4>
   <a name="dss_FoldingSet">"llvm/ADT/FoldingSet.h"</a>
 </h4>