diff options
author | Gabor Greif <ggreif@gmail.com> | 2009-03-12 10:30:31 +0000 |
---|---|---|
committer | Gabor Greif <ggreif@gmail.com> | 2009-03-12 10:30:31 +0000 |
commit | d970d69d8b48c2f246d3d8d31b4440edf5e5ce9b (patch) | |
tree | e016a6a439a9b6c5208f0c2346efe065c433d566 /docs/ProgrammersManual.html | |
parent | e39f0e7330268d58e914e9902fb9a7004deb518b (diff) | |
download | external_llvm-d970d69d8b48c2f246d3d8d31b4440edf5e5ce9b.zip external_llvm-d970d69d8b48c2f246d3d8d31b4440edf5e5ce9b.tar.gz external_llvm-d970d69d8b48c2f246d3d8d31b4440edf5e5ce9b.tar.bz2 |
add some text to explain sentinels
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@66790 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'docs/ProgrammersManual.html')
-rw-r--r-- | docs/ProgrammersManual.html | 39 |
1 files changed, 39 insertions, 0 deletions
diff --git a/docs/ProgrammersManual.html b/docs/ProgrammersManual.html index a990462..e2525ae 100644 --- a/docs/ProgrammersManual.html +++ b/docs/ProgrammersManual.html @@ -901,6 +901,7 @@ Related classes of interest are explained in the following subsections: <li><a href="#dss_ilist_traits">ilist_traits</a></li> <li><a href="#dss_iplist">iplist</a></li> <li><a href="#dss_ilist_node">llvm/ADT/ilist_node.h</a></li> + <li><a href="#dss_ilist_sentinel">Sentinels</a></li> </ul> </div> @@ -946,6 +947,44 @@ in the default manner.</p> <!-- _______________________________________________________________________ --> <div class="doc_subsubsection"> + <a name="dss_ilist_sentinel">Sentinels</a> +</div> + +<div class="doc_text"> +<p><tt>ilist</tt>s have another speciality that must be considered. To be a good +citizen in the C++ ecosystem, it needs to support the standard container +operations, such as <tt>begin</tt> and <tt>end</tt> iterators, etc. Also, the +<tt>operator--</tt> must work correctly on the <tt>end</tt> iterator in the +case of non-empty <tt>ilist</tt>s.</p> + +<p>The only sensible solution to this problem is to allocate a so-called +<i>sentinel</i> along with the intrusive list, which serves as the <tt>end</tt> +iterator, providing the back-link to the last element. However conforming to the +C++ convention it is illegal to <tt>operator++</tt> beyond the sentinel and it +also must not be dereferenced.</p> + +<p>These constraints allow for some implementation freedom to the <tt>ilist</tt> +how to allocate and store the sentinel. The corresponding policy is dictated +by <tt>ilist_traits<T></tt>. By default a <tt>T</tt> gets heap-allocated +whenever the need for a sentinel arises.</p> + +<p>While the default policy is sufficient in most cases, it may break down when +<tt>T</tt> does not provide a default constructor. Also, in the case of many +instances of <tt>ilist</tt>s, the memory overhead of the associated sentinels +is wasted. To alleviate the situation with numerous and voluminous +<tt>T</tt>-sentinels, sometimes a trick is employed, leading to <i>ghostly +sentinels</i>.</p> + +<p>Ghostly sentinels are obtained by specially-crafted <tt>ilist_traits<T></tt> +which superpose the sentinel with the <tt>ilist</tt> instance in memory. Pointer +arithmetic is used to obtain the sentinel, which is relative to the +<tt>ilist</tt>'s <tt>this</tt> pointer. The <tt>ilist</tt> is augmented by an +extra pointer, which serves as the back-link of the sentinel. This is the only +field in the ghostly sentinel which can be legally accessed.</p> +</div> + +<!-- _______________________________________________________________________ --> +<div class="doc_subsubsection"> <a name="dss_other">Other Sequential Container options</a> </div> |