This is an archive of the discontinued LLVM Phabricator instance.

Differential D52828

[doc] Update the programmer's manual about SmallSet's iterator
ClosedPublic

Authored by Szelethus on Oct 3 2018, 5:16 AM.

Details

Reviewers
dblaikie
fhahn
Commits
rG969892f271dc: [doc] Update the programmer's manual about SmallSet's iterator
rL343770: [doc] Update the programmer's manual about SmallSet's iterator
Summary

Since rL337818, you can now iterate the SmallSet.

Diff Detail

Repository
rL LLVM

Event Timeline

Szelethus created this revision.Oct 3 2018, 5:16 AM
Herald added a subscriber: llvm-commits. · View Herald TranscriptOct 3 2018, 5:16 AM
Szelethus edited the summary of this revision. (Show Details)Oct 3 2018, 5:17 AM
dblaikie accepted this revision.Oct 3 2018, 9:01 AM

Thanks!

This revision is now accepted and ready to land.Oct 3 2018, 9:01 AM
fhahn accepted this revision.Oct 3 2018, 10:24 AM

Thank you very much for spotting this! LGTM

Closed by commit rL343770: [doc] Update the programmer's manual about SmallSet's iterator (authored by Szelethus). · Explain WhyOct 4 2018, 5:35 AM
This revision was automatically updated to reflect the committed changes.

Revision Contents

PathSize
llvm/
trunk/
docs/
14 lines

Diff 168275

llvm/trunk/docs/ProgrammersManual.rst

Show First 20 Lines • Show All 1,866 Lines • ▼ Show 20 Lines
space for N elements in place (thus, if the set is dynamically smaller than N, space for N elements in place (thus, if the set is dynamically smaller than N,
no malloc traffic is required) and accesses them with a simple linear search. no malloc traffic is required) and accesses them with a simple linear search.
When the set grows beyond N elements, it allocates a more expensive When the set grows beyond N elements, it allocates a more expensive
representation that guarantees efficient access (for most types, it falls back representation that guarantees efficient access (for most types, it falls back
to :ref:`std::set <dss_set>`, but for pointers it uses something far better, to :ref:`std::set <dss_set>`, but for pointers it uses something far better,
:ref:`SmallPtrSet <dss_smallptrset>`. :ref:`SmallPtrSet <dss_smallptrset>`.
The magic of this class is that it handles small sets extremely efficiently, but The magic of this class is that it handles small sets extremely efficiently, but
gracefully handles extremely large sets without loss of efficiency. The gracefully handles extremely large sets without loss of efficiency.
drawback is that the interface is quite small: it supports insertion, queries
and erasing, but does not support iteration.
.. _dss_smallptrset: .. _dss_smallptrset:
llvm/ADT/SmallPtrSet.h llvm/ADT/SmallPtrSet.h
^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^^^
``SmallPtrSet`` has all the advantages of ``SmallSet`` (and a ``SmallSet`` of ``SmallPtrSet`` has all the advantages of ``SmallSet`` (and a ``SmallSet`` of
pointers is transparently implemented with a ``SmallPtrSet``), but also supports pointers is transparently implemented with a ``SmallPtrSet``). If more than N
iterators. If more than N insertions are performed, a single quadratically insertions are performed, a single quadratically probed hash table is allocated
probed hash table is allocated and grows as needed, providing extremely and grows as needed, providing extremely efficient access (constant time
efficient access (constant time insertion/deleting/queries with low constant insertion/deleting/queries with low constant factors) and is very stingy with
factors) and is very stingy with malloc traffic. malloc traffic.
Note that, unlike :ref:`std::set <dss_set>`, the iterators of ``SmallPtrSet`` Note that, unlike :ref:`std::set <dss_set>`, the iterators of ``SmallPtrSet``
are invalidated whenever an insertion occurs. Also, the values visited by the are invalidated whenever an insertion occurs. Also, the values visited by the
iterators are not visited in sorted order. iterators are not visited in sorted order.
.. _dss_stringset: .. _dss_stringset:
llvm/ADT/StringSet.h llvm/ADT/StringSet.h
▲ Show 20 Lines • Show All 2,242 Lines • Show Last 20 Lines