diff options
author | Jakob Stoklund Olesen <stoklund@2pi.dk> | 2012-02-22 00:56:08 +0000 |
---|---|---|
committer | Jakob Stoklund Olesen <stoklund@2pi.dk> | 2012-02-22 00:56:08 +0000 |
commit | 62588622d40f6c6f5508496db69e06593b615049 (patch) | |
tree | 71c0226264aba20709e72a0be48064d51dc8418e /docs | |
parent | 5990bd7ba645d6fd067d9f015f4f48a9b8bf872b (diff) | |
download | external_llvm-62588622d40f6c6f5508496db69e06593b615049.zip external_llvm-62588622d40f6c6f5508496db69e06593b615049.tar.gz external_llvm-62588622d40f6c6f5508496db69e06593b615049.tar.bz2 |
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.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151110 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'docs')
-rw-r--r-- | docs/ProgrammersManual.html | 19 |
1 files changed, 19 insertions, 0 deletions
diff --git a/docs/ProgrammersManual.html b/docs/ProgrammersManual.html index 0b1a875..f4c0322 100644 --- a/docs/ProgrammersManual.html +++ b/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"><set></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> |