From 6a65f4208f05af4cd2d76ae71c956b426d9e2373 Mon Sep 17 00:00:00 2001
From: Gabor Greif <ggreif@gmail.com>
Date: Thu, 12 Mar 2009 10:30:31 +0000
Subject: [PATCH] add some text to explain sentinels

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@66790 91177308-0d34-0410-b5e6-96231b3b80d8
---
 docs/ProgrammersManual.html | 39 +++++++++++++++++++++++++++++++++++++
 1 file changed, 39 insertions(+)

diff --git a/docs/ProgrammersManual.html b/docs/ProgrammersManual.html
index a990462c253..e2525ae84e0 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>
 
@@ -944,6 +945,44 @@ in the default manner.</p>
 <tt>ilist_node&lt;T&gt;</tt>.</p>
 </div>
 
+<!-- _______________________________________________________________________ -->
+<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&lt;T&gt;</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&lt;T&gt;</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>
-- 
2.34.1