[libstdc++] Document and tidy up stl_deque.h

[Phil Edwards <pedwards at disaster dot jaj dot com>]

This cleans up stl_deque.h so that other people can work on it.  Ugly spacing
and indentation fixed in a few places, and some notes towards how deque<>
does its work are added.



2001-12-31  Phil Edwards  <pme@gcc.gnu.org>

	* include/bits/stl_deque.h:  Doxygenate with initial/example hooks.
	Clean up spacing and indentation.


Index: include/bits/stl_deque.h
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/bits/stl_deque.h,v
retrieving revision 1.15
diff -u -3 -p -r1.15 stl_deque.h
--- stl_deque.h	2001/12/06 20:29:31	1.15
+++ stl_deque.h	2001/12/31 14:52:06
@@ -65,63 +65,54 @@
 #ifndef __GLIBCPP_INTERNAL_DEQUE_H
 #define __GLIBCPP_INTERNAL_DEQUE_H
 
-/* Class invariants:
- *  For any nonsingular iterator i:
- *    i.node is the address of an element in the map array.  The
- *      contents of i.node is a pointer to the beginning of a node.
- *    i.first == *(i.node) 
- *    i.last  == i.first + node_size
- *    i.cur is a pointer in the range [i.first, i.last).  NOTE:
- *      the implication of this is that i.cur is always a dereferenceable
- *      pointer, even if i is a past-the-end iterator.
- *  Start and Finish are always nonsingular iterators.  NOTE: this means
- *    that an empty deque must have one node, and that a deque
- *    with N elements, where N is the buffer size, must have two nodes.
- *  For every node other than start.node and finish.node, every element
- *    in the node is an initialized object.  If start.node == finish.node,
- *    then [start.cur, finish.cur) are initialized objects, and
- *    the elements outside that range are uninitialized storage.  Otherwise,
- *    [start.cur, start.last) and [finish.first, finish.cur) are initialized
- *    objects, and [start.first, start.cur) and [finish.cur, finish.last)
- *    are uninitialized storage.
- *  [map, map + map_size) is a valid, non-empty range.  
- *  [start.node, finish.node] is a valid range contained within 
- *    [map, map + map_size).  
- *  A pointer in the range [map, map + map_size) points to an allocated node
- *    if and only if the pointer is in the range [start.node, finish.node].
- */
-
-
-/*
- * In previous versions of deque, there was an extra template 
- * parameter so users could control the node size.  This extension
- * turns out to violate the C++ standard (it can be detected using
- * template template parameters), and it has been removed.
- */
 
+// Since this entire file is within namespace std, there's no reason to
+// waste two spaces along the left column.  Thus the leading indentation is
+// slightly violated from here on.
 namespace std
 { 
-  // Note: this function is simply a kludge to work around several compilers'
-  //  bugs in handling constant expressions.
-  inline size_t 
-  __deque_buf_size(size_t __size) 
-  { return __size < 512 ? size_t(512 / __size) : size_t(1); }
 
-  template <class _Tp, class _Ref, class _Ptr>
-  struct _Deque_iterator {
+/**
+ *  @maint
+ *  @brief This function controls the size of memory nodes.
+ *  @param  size  The size of an element.
+ *  @return   The number (not bytesize) of elements per node.
+ *
+ *  This function started off as a compiler kludge from SGI, but seems to
+ *  be a useful wrapper around a repeated constant expression.
+ *  @endmaint
+*/
+inline size_t 
+__deque_buf_size(size_t __size) 
+{ return __size < 512 ? size_t(512 / __size) : size_t(1); }
+
+
+/// A deque::iterator.
+/**
+ *  Quite a bit of intelligence here.  Much of the functionality of deque is
+ *  actually passed off to this class.  A deque holds two of these internally,
+ *  marking its valid range.  Access to elements is done as offsets of either
+ *  of those two, relying on operator overloading in this class.
+ *
+ *  @maint
+ *  All the functions are op overloads except for _M_set_node.
+ *  @endmaint
+*/
+template <class _Tp, class _Ref, class _Ptr>
+struct _Deque_iterator
+{
   typedef _Deque_iterator<_Tp, _Tp&, _Tp*>             iterator;
   typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
   static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
 
   typedef random_access_iterator_tag iterator_category;
-  typedef _Tp value_type;
-  typedef _Ptr pointer;
-  typedef _Ref reference;
-  typedef size_t size_type;
-  typedef ptrdiff_t difference_type;
-  typedef _Tp** _Map_pointer;
-
-  typedef _Deque_iterator _Self;
+  typedef _Tp                        value_type;
+  typedef _Ptr                       pointer;
+  typedef _Ref                       reference;
+  typedef size_t                     size_type;
+  typedef ptrdiff_t                  difference_type;
+  typedef _Tp**                      _Map_pointer;
+  typedef _Deque_iterator            _Self;
 
   _Tp* _M_cur;
   _Tp* _M_first;
@@ -213,6 +204,12 @@ namespace std
   bool operator<=(const _Self& __x) const { return !(__x < *this); }
   bool operator>=(const _Self& __x) const { return !(*this < __x); }
 
+  /** @maint
+   *  Prepares to traverse new_node.  Sets everything except _M_cur, which
+   *  should therefore be set by the caller immediately afterwards, based on
+   *  _M_first and _M_last.
+   *  @endmaint
+  */
   void _M_set_node(_Map_pointer __new_node) {
     _M_node = __new_node;
     _M_first = *__new_node;
@@ -227,16 +224,21 @@ operator+(ptrdiff_t __n, const _Deque_it
   return __x + __n;
 }
 
-
-// Deque base class.  It has two purposes.  First, its constructor
-//  and destructor allocate (but don't initialize) storage.  This makes
-//  exception safety easier.  Second, the base class encapsulates all of
-//  the differences between SGI-style allocators and standard-conforming
-//  allocators.
 
-// Base class for ordinary allocators.
+/// @maint Primary default version.  @endmaint
+/**
+ *  @maint
+ *  Deque base class.  It has two purposes.  First, its constructor
+ *  and destructor allocate (but don't initialize) storage.  This makes
+ *  exception safety easier.  Second, the base class encapsulates all of
+ *  the differences between SGI-style allocators and standard-conforming
+ *  allocators.  There are two versions:  this ordinary one, and the
+ *  space-saving specialization for instanceless allocators.
+ *  @endmaint
+*/
 template <class _Tp, class _Alloc, bool __is_static>
-class _Deque_alloc_base {
+class _Deque_alloc_base
+{
 public:
   typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
   allocator_type get_allocator() const { return _M_node_allocator; }
@@ -268,7 +270,7 @@ protected:
   size_t _M_map_size;
 };
 
-// Specialization for instanceless allocators.
+/// Specialization for instanceless allocators.
 template <class _Tp, class _Alloc>
 class _Deque_alloc_base<_Tp, _Alloc, true>
 {
@@ -297,6 +299,17 @@ protected:
   size_t _M_map_size;
 };
 
+
+/**
+ *  @maint
+ *  Deque base class.  Using _Alloc_traits in the instantiation of the parent
+ *  class provides the compile-time dispatching mentioned in the parent's docs.
+ *  This class provides the unified face for deque's allocation.
+ *
+ *  Nothing in this class ever constructs or destroys an actual Tp element.
+ *  (Deque handles that itself.)  Only/All memory management is performed here.
+ *  @endmaint
+*/
 template <class _Tp, class _Alloc>
 class _Deque_base
   : public _Deque_alloc_base<_Tp,_Alloc,
@@ -306,7 +319,7 @@ public:
   typedef _Deque_alloc_base<_Tp,_Alloc,
                              _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
           _Base;
-  typedef typename _Base::allocator_type allocator_type;
+  typedef typename _Base::allocator_type             allocator_type;
   typedef _Deque_iterator<_Tp,_Tp&,_Tp*>             iterator;
   typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
 
@@ -328,16 +341,25 @@ protected:
   iterator _M_finish;
 };
 
-// Non-inline member functions from _Deque_base.
 
 template <class _Tp, class _Alloc>
-_Deque_base<_Tp,_Alloc>::~_Deque_base() {
+_Deque_base<_Tp,_Alloc>::~_Deque_base()
+{
   if (_M_map) {
     _M_destroy_nodes(_M_start._M_node, _M_finish._M_node + 1);
     _M_deallocate_map(_M_map, _M_map_size);
   }
 }
 
+/**
+ *  @maint
+ *  @brief Layout storage.
+ *  @param  num_elements  The count of T's for which to allocate space at first.
+ *  @return   Nothing.
+ *
+ *  The initial underlying memory layout is a bit complicated...
+ *  @endmaint
+*/
 template <class _Tp, class _Alloc>
 void
 _Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements)
@@ -391,37 +413,109 @@ _Deque_base<_Tp,_Alloc>::_M_destroy_node
     _M_deallocate_node(*__n);
 }
 
-template <class _Tp, class _Alloc = allocator<_Tp> >
-class deque : protected _Deque_base<_Tp, _Alloc> {
 
+/**
+ *  Placeholder:  see http://www.sgi.com/tech/stl/Deque.html for now.
+ *
+ *  In previous HP/SGI versions of deque, there was an extra template parameter
+ *  so users could control the node size.  This extension turned out to violate
+ *  the C++ standard (it can be detected using template template parameters),
+ *  and it was removed.
+ *
+ *  @maint
+ *  Here's how a deque<Tp> manages memory.  Each deque has 4 members:
+ *  
+ *  - Tp**        _M_map
+ *  - size_t      _M_map_size
+ *  - iterator    _M_start, _M_finish
+ *  
+ *  map_size is at least 8.  map is an array of map_size pointers-to-"nodes".
+ *  
+ *  A "node" has no specific type name as such, but it is referred to as
+ *  "node" in this file.  It is a simple array-of-Tp.  If Tp is very large,
+ *  there will be one Tp element per node (i.e., an "array" of one).
+ *  For non-huge Tp's, node size is inversely related to Tp size:  the
+ *  larger the Tp, the fewer Tp's will fit in a node.  The goal here is to
+ *  keep the total size of a node relatively small and constant over different
+ *  Tp's, to improve allocator efficiency.
+ *  
+ *  **** As I write this, the nodes are /not/ allocated using the high-speed
+ *  memory pool.  There are 20 hours left in the year; perhaps I can fix
+ *  this before 2002.
+ *  
+ *  Not every pointer in the map array will point to a node.  If the initial
+ *  number of elements in the deque is small, the /middle/ map pointers will
+ *  be valid, and the ones at the edges will be unused.  This same situation
+ *  will arise as the map grows:  available map pointers, if any, will be on
+ *  the ends.  As new nodes are created, only a subset of the map's pointers
+ *  need to be copied "outward".
+ *
+ *  Class invariants:
+ * - For any nonsingular iterator i:
+ *    - i.node points to a member of the map array.  (Yes, you read that
+ *      correctly:  i.node does not actually point to a node.)  The member of
+ *      the map array is what actually points to the node.
+ *    - i.first == *(i.node)    (This points to the node (first Tp element).)
+ *    - i.last  == i.first + node_size
+ *    - i.cur is a pointer in the range [i.first, i.last).  NOTE:
+ *      the implication of this is that i.cur is always a dereferenceable
+ *      pointer, even if i is a past-the-end iterator.
+ * - Start and Finish are always nonsingular iterators.  NOTE: this means that
+ *   an empty deque must have one node, a deque with <N elements (where N is
+ *   the node buffer size) must have one node, a deque with N through (2N-1)
+ *   elements must have two nodes, etc.
+ * - For every node other than start.node and finish.node, every element in the
+ *   node is an initialized object.  If start.node == finish.node, then
+ *   [start.cur, finish.cur) are initialized objects, and the elements outside
+ *   that range are uninitialized storage.  Otherwise, [start.cur, start.last)
+ *   and [finish.first, finish.cur) are initialized objects, and [start.first,
+ *   start.cur) and [finish.cur, finish.last) are uninitialized storage.
+ * - [map, map + map_size) is a valid, non-empty range.  
+ * - [start.node, finish.node] is a valid range contained within 
+ *   [map, map + map_size).  
+ * - A pointer in the range [map, map + map_size) points to an allocated node
+ *   if and only if the pointer is in the range [start.node, finish.node].
+ *
+ *  Here's the magic:  nothing in deque is "aware" of the discontiguous storage!
+ *
+ *  The memory setup and layout occurs in the parent, _Base, and the iterator
+ *  class is entirely responsible for "leaping" from one node to the next.  All
+ *  the implementation routines for deque itself work only through the start
+ *  and finish iterators.  This keeps the routines simple and sane, and we can
+ *  use other standard algorithms as well.
+ *
+ *  @endmaint
+*/
+template <class _Tp, class _Alloc = allocator<_Tp> >
+class deque : protected _Deque_base<_Tp, _Alloc>
+{
   // concept requirements
   __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
 
   typedef _Deque_base<_Tp, _Alloc> _Base;
-public:                         // Basic types
-  typedef _Tp value_type;
-  typedef value_type* pointer;
-  typedef const value_type* const_pointer;
-  typedef value_type& reference;
-  typedef const value_type& const_reference;
-  typedef size_t size_type;
-  typedef ptrdiff_t difference_type;
+
+public:
+  typedef _Tp                                value_type;
+  typedef value_type*                        pointer;
+  typedef const value_type*                  const_pointer;
+  typedef value_type&                        reference;
+  typedef const value_type&                  const_reference;
+  typedef size_t                             size_type;
+  typedef ptrdiff_t                          difference_type;
 
   typedef typename _Base::allocator_type allocator_type;
   allocator_type get_allocator() const { return _Base::get_allocator(); }
-
-public:                         // Iterators
-  typedef typename _Base::iterator       iterator;
-  typedef typename _Base::const_iterator const_iterator;
 
-  typedef reverse_iterator<const_iterator> const_reverse_iterator;
-  typedef reverse_iterator<iterator> reverse_iterator;
+  typedef typename _Base::iterator           iterator;
+  typedef typename _Base::const_iterator     const_iterator;
+  typedef reverse_iterator<const_iterator>   const_reverse_iterator;
+  typedef reverse_iterator<iterator>         reverse_iterator;
 
-protected:                      // Internal typedefs
+protected:
   typedef pointer* _Map_pointer;
   static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
 
-protected:
+  // Functions controlling memory layout, and nothing else.
   using _Base::_M_initialize_map;
   using _Base::_M_create_nodes;
   using _Base::_M_destroy_nodes;
@@ -430,6 +524,12 @@ protected:
   using _Base::_M_allocate_map;
   using _Base::_M_deallocate_map;
 
+  /** @maint
+   *  A total of four data members accumulated down the heirarchy.  If the
+   *  _Alloc type requires separate instances, then two of them will also be
+   *  included in each deque.
+   *  @endmaint
+  */
   using _Base::_M_map;
   using _Base::_M_map_size;
   using _Base::_M_start;
@@ -935,10 +1035,21 @@ void deque<_Tp,_Alloc>::clear()
   _M_finish = _M_start;
 }
 
-// Precondition: _M_start and _M_finish have already been initialized,
-// but none of the deque's elements have yet been constructed.
+/**
+ *  @maint
+ *  @brief Fills the deque with copies of value.
+ *  @param  value  Initial value.
+ *  @return   Nothing.
+ *  @pre _M_start and _M_finish have already been initialized, but none of the
+ *       deque's elements have yet been constructed.
+ *
+ *  This function is called only when the user provides an explicit size (with
+ *  or without an explicit exemplar value).
+ *  @endmaint
+*/
 template <class _Tp, class _Alloc>
-void deque<_Tp,_Alloc>::_M_fill_initialize(const value_type& __value) {
+void deque<_Tp,_Alloc>::_M_fill_initialize(const value_type& __value)
+{
   _Map_pointer __cur;
   try {
     for (__cur = _M_start._M_node; __cur < _M_finish._M_node; ++__cur)
@@ -952,6 +1063,18 @@ void deque<_Tp,_Alloc>::_M_fill_initiali
     }
 }
 
+/** @{
+ *  @maint
+ *  @brief Fills the deque with whatever is in [first,last).
+ *  @param  first  An input iterator.
+ *  @param  last  An input iterator.
+ *  @return   Nothing.
+ *
+ *  If the iterators are actually forward iterators (or better), then the
+ *  memory layout can be done all at once.  Else we move forward using
+ *  push_back on each value from the iterator.
+ *  @endmaint
+*/
 template <class _Tp, class _Alloc> template <class _InputIterator>
 void deque<_Tp,_Alloc>::_M_range_initialize(_InputIterator __first,
                                             _InputIterator __last,
@@ -996,6 +1119,7 @@ void deque<_Tp,_Alloc>::_M_range_initial
       __throw_exception_again;
     }
 }
+/** @} */
 
 // Called only if _M_finish._M_cur == _M_finish._M_last - 1.
 template <class _Tp, class _Alloc>