Commits

Anonymous committed c41557b

Make pointer_list more efficient. Add equality test to fpcompare.

Comments (0)

Files changed (7)

+2009-11-19  scott snyder  <snyder@bnl.gov>
+
+	* Tagging CxxUtils-00-00-41.
+
+	* CxxUtils/pointer_list.h, CxxUtils/pointer_list.icc,
+	src/pointer_list.cxx, test/pointer_list_test.cxx: More efficient
+	way of testing for the end of a block.
+
+	* CxxUtils/fpcompare.h: Add equality test.
+	* test/fpcompare_test.cxx: Test it.
+
 2009-11-11  scott snyder  <snyder@bnl.gov>
 
 	* Tagging CxxUtils-00-00-40.

CxxUtils/fpcompare.h

 
 /**
  * @brief Compare two FP numbers, working around x87 precision issues.
+ * @return @a a == @a b
+ */
+inline
+bool equal (double a, double b)
+{
+  CXXUTILS_FPCOMPARE_VOLATILE double va = a;
+  CXXUTILS_FPCOMPARE_VOLATILE double vb = b;
+  return va == vb;
+}
+
+
+/**
+ * @brief Compare two FP numbers, working around x87 precision issues.
+ * @return @a a == @a b
+ */
+inline
+bool equal (float a, float b)
+{
+  CXXUTILS_FPCOMPARE_VOLATILE float va = a;
+  CXXUTILS_FPCOMPARE_VOLATILE float vb = b;
+  return va == vb;
+}
+
+
+/**
+ * @brief Compare two FP numbers, working around x87 precision issues.
  * @return @a a > @a b
  */
 inline
 /**
  * @brief Compare two FP numbers, working around x87 precision issues.
  */
+struct equal
+  : public std::binary_function<double, double, bool>
+{
+  bool
+  operator()(double a, double b) const
+  { return fpcompare::equal (a, b); }
+};
+
+
+/**
+ * @brief Compare two FP numbers, working around x87 precision issues.
+ */
+struct equalf
+  : public std::binary_function<float, float, bool>
+{
+  bool
+  operator()(float a, float b) const
+  { return fpcompare::equal (a, b); }
+};
+
+
+/**
+ * @brief Compare two FP numbers, working around x87 precision issues.
+ */
 struct greater
   : public std::binary_function<double, double, bool>
 {

CxxUtils/pointer_list.h

 #define CXXUTILS_POINTER_LIST_H
 
 
+#include "boost/static_assert.hpp"
 #include <iterator>
 
 
 /**
  * @brief A fast way to store a variable-sized collection of pointers.
  *
+ * See @c pointer_list below for a summary.
+ *
+ * Some extra detail:
+ * The list is a set of fixed-size blocks, each holding (by default)
+ * 15 pointers.  At the end of each block is another pointer
+ * used to form a a linked list.  We used to mark this last pointer
+ * by setting the low bit as a sentinel.  But now that we control our
+ * own allocator we can instead just insist that the blocks have
+ * a size that's a power of 2 and are fully aligned.  We can then
+ * test the low bits of the address to tell if we're looking
+ * at the last pointer of a block.
+ *
+ * We then need to keep pointers to the head block, and to the current
+ * insertion position.  To insert, we see if the insertion position
+ * is pointing at a block end.  If so, we allocate another block, chain
+ * to it, and reset the insertion position to the beginning of the new block.
+ * Then store the pointer in the insertion position and bump it.
+ * Iterators are just pointers to the stored pointers.  We use the
+ * end positions to tell when to chain to a new block.  The insertion
+ * point gives the end iterator.
+ *
+ * pointer_list is templated on the number of pointers stored in each
+ * block.  We put it as a template parameter so that it can be accessed
+ * from the iterator class without having to have a reference from the
+ * iterator back to the containing list.
+ */
+class pointer_list_base
+{
+public:
+  /**
+   * @brief A single block in the list.
+   *
+   * It contains some number of pointers.
+   * The last element of the block contains a link to the next block.
+   * Blocks are aligned so that we can tell if we're looking
+   * at the last element from the low bits of an address.
+   */
+  struct list_block
+  {
+  public:
+    typedef unsigned long ulong;
+
+    /// The element type we store.
+    typedef void* value_type;
+
+    /// The elements.  This structure is variable-sized;
+    /// it will be allocated for the correct number of elements.
+    value_type m_data[1];
+
+    /// Size in bytes of a block holding @c nelt elements
+    /// (excluding the end-pointer).
+    static size_t size (size_t nelt);
+  };
+
+
+  /**
+   * @brief Very simple allocator for use with @c pointer_list.
+   *
+   * We allocate large chunks and divide them up into @c list_block's.
+   * We don't support deleting invidual elements; instead, everything
+   * is deleted when the allocator is.  The chunks are chained together
+   * to allow for this.
+   *
+   * The total size of a block should be a power of two, and blocks
+   * must be aligned to this boundary.
+   */
+  class allocator
+  {
+  public:
+    /**
+     * @brief Constructor.
+     * @param nelt Number of pointers per block
+     *             (excluding the end pointer).
+     *             Must be one less than a power of two.
+     * @param nblock Number of blocks to allocate per chunk.
+     * @param end_mask Mask to use for end-of-block test.
+     * @param end_offs Offset to use for end-of-block test.
+     */
+    allocator (size_t nelt,
+               size_t nblock,
+               unsigned long end_mask,
+               unsigned long end_offs);
+
+    /// Destructor.  Deletes all blocks from this allocator.
+    ~allocator();
+
+    /// Allocate a new block.
+    list_block* allocate();
+
+    /// Return the number of pointers per block
+    /// (excluding the end-pointer).
+    size_t nelt() const;
+
+    /// Return the current number of allocated chunks.
+    size_t nchunks() const;
+
+    /// Test if P is pointing at the end-pointer of a block.
+    bool at_end (const void* p) const;
+
+
+  private:
+    /// Allocate a new chunk of blocks.
+    void refill();
+
+    /// One memory allocation chunk.
+    struct chunk
+    {
+      /// Link to the next chunk.
+      chunk* m_next;
+
+      /// Pointer to the first block contained within this chunk.
+      list_block* m_blocks;
+    };
+
+    /// Number of elements per block (excluding the end-pointer).
+    size_t m_nelt;
+
+    /// Number of blocks per chunk.
+    size_t m_nblock;
+
+    /// Most recent chunk allocated.
+    chunk* m_chunks;
+
+    /// Number of blocks allocated so far from that chunk.
+    size_t m_nthis;
+
+    /// Current number of allocated chunks.
+    size_t m_nchunks;
+
+    /// Mask for testing for an end pointer.
+    unsigned long m_end_mask;
+
+    /// Offset for testing for an end pointer.
+    unsigned long m_end_offs;
+  };
+
+
+  /// Alias for allocator.
+  typedef allocator pool_type;
+
+  /// The stored element type.
+  typedef list_block::value_type value_type;
+
+  /// Constructor.  @c pool gives the allocator for this container.
+  pointer_list_base (pool_type& pool);
+
+  /// Add a new element to the end of the container.  O(1)
+  void push_back (value_type p);
+
+  /// The current size of the container.  O(1).
+  size_t size() const;
+
+  /// Erase the container.  O(1).  Note: doesn't free memory.
+  /// Memory currently in use will be reused when the container
+  /// is filled again.
+  void clear();
+
+  /// Test to see if the container is empty.
+  bool empty() const;
+
+
+protected:
+  /// The first block in the list.
+  list_block* m_head;
+
+  /// The current insertion point in the list.
+  value_type* m_insert;
+
+  /// The current list size.
+  size_t m_size;
+
+  /// The list allocator.
+  allocator& m_pool;
+
+  /// Allocate the first block of the list.
+  void firstblock ();
+
+  /// Extend the list with another block.
+  /// @c m_insert should be at the end of the last block.
+  void nextblock ();
+
+  /// Allocate a new block.
+  list_block* getblock();
+};
+
+
+/**
+ * @brief A fast way to store a variable-sized collection of pointers.
+ *
  * If you're growing a variable-sized collection of things, all the
  * STL containers have some performance issues.  A std::vector
  * needs to reallocate and copy its data as it grows.  The use of
  * gets passed to the @c pointer_list constructor.  Memory is not freed
  * until the allocator is destroyed.
  *
- * In a bit more detail:
- * The list is a set of fixed-size blocks, each holding (by default)
- * 16 pointers.
- * The blocks are chained together in a linked list; the last pointer
- * of each block is the link for the chain.  The low bit of this
- * pointer is set, to serve as a sentinel.
- * We then need to keep pointers to the head block, and to the current
- * insertion position.  To insert, we see if the insertion position
- * is pointing at a sentinel.  If so, we allocate another block, chain
- * to it, and reset the insertion position to the beginning of the new block.
- * Then store the pointer in the insertion position and bump it.
- * Iterators are just pointers to the stored pointers.  We use the
- * sentinels to tell when to chain to a new block.  The insertion
- * point gives the end iterator.
+ * This class is templated on the number of elements stored per block.
+ * This must be one less than a power of two.
  */
+template <size_t NELT = 15>
 class pointer_list
+  : public pointer_list_base
 {
 public:
+  /// Stored value type.
+  typedef pointer_list_base::value_type value_type;
+
+
   /**
-   * @brief A single block in the list.
+   * @brief Allocator for @c pointer_list, specialized for @c NELT.
    *
-   * It contains some number of pointers.
-   * Each element also contains a `sentinel' bit (implemented as the
-   * low bit).  This marks the last element of the block, which is
-   * a link to the next block.
+   * The purpose for thsi is to be able to have the static
+   * @c at_end_static function, which we can call from an iterator.
    */
-  struct list_block
+  class allocator
+    : public pointer_list_base::allocator
   {
   public:
-    typedef unsigned long ulong;
+    /// Verify that @c NELT is one less than a power fo two.
+    BOOST_STATIC_ASSERT (((NELT+1) & NELT) == 0);
 
-    /// The element type we store.
-    typedef void* value_type;
+    /// Constants to use to test if we're at the end of a block.
+    static const unsigned long END_OFFS = NELT * sizeof(value_type);
+    static const unsigned long END_MASK = END_OFFS | (sizeof(value_type)-1);
 
-    /// The elements.  This structure is variable-sized;
-    /// it will be allocated for the correct number of elements.
-    value_type m_data[1];
+    /**
+     * @brief Constructor.
+     * @param nblock Number of blocks to allocate per chunk.
+     */
+    allocator (size_t nblock = 100);
+    
 
-    /// Size in bytes of a block holding @c nelt elements.
-    static size_t size (size_t nelt);
-
-    /// True if @c p has the sentinel bit set.
-    static bool is_sentinel (value_type p);
-
-    /// Turn the sentinel bit on for value @c p.
-    static value_type make_sentinel (value_type p);
-
-    /// Extract a pointer from a value.
-    static value_type pointer (value_type p);
+    /// Test if P is pointing at the end-pointer of a block.
+    static bool at_end_static (const void* p);
   };
 
 
   /**
-   * @brief Very simple allocator for use with @c pointer_list.
-   *
-   * We allocate large chunks and divide them up into @c list_block's.
-   * We don't support deleting invidual elements; instead, everything
-   * is deleted when the allocator is.  The chunks are chained together
-   * to allow for this.
-   */
-  class allocator
-  {
-  public:
-    /**
-     * @brief Constructor.
-     * @param nelt Number of pointers per block.
-     * @param nblock Number of blocks to allocate per chunk.
-     */
-    allocator (size_t nelt = 16, size_t nblock = 100);
-
-    /// Destructor.  Deletes all blocks from this allocator.
-    ~allocator();
-
-    /// Allocate a new block.
-    list_block* allocate();
-
-    /// Return the number of pointers per block.
-    size_t nelt() const;
-
-    /// Return the current number of allocated chunks.
-    size_t nchunks() const;
-
-
-  private:
-    /// Allocate a new chunk of blocks.
-    void refill();
-
-    /// One memory allocation chunk.
-    struct chunk
-    {
-      /// Link to the next chunk.
-      chunk* m_next;
-
-      /// Blocks contained within this chunk.
-      /// (This is a variable-sized structure.)
-      list_block m_blocks[1];
-    };
-
-    /// Number of elements per block.
-    size_t m_nelt;
-
-    /// Number of blocks per chunk.
-    size_t m_nblock;
-
-    /// Most recent chunk allocated.
-    chunk* m_chunks;
-
-    /// Number of blocks allocated so far from that chunk.
-    size_t m_nthis;
-
-    /// Current number of allocated chunks.
-    size_t m_nchunks;
-  };
-
-
-  /// Alias for allocator.
-  typedef allocator pool_type;
-
-  /// The stored element type.
-  typedef list_block::value_type value_type;
-
-
-  /**
-   * @brief Forward iterator over the collection.
+   * @brief Forward iterator over the list.
    */
   class iterator
     : public std::iterator<std::forward_iterator_tag, value_type>
   {
   public:
+    typedef typename std::iterator<std::forward_iterator_tag, value_type>
+      base;
+    typedef typename base::iterator_category iterator_category;
+    typedef typename base::difference_type   difference_type;
+    typedef typename base::pointer            pointer;
+    typedef typename base::reference          reference;
+
     /// Equality comparison.
     bool operator== (const iterator& other) const;
 
 
     /// Advance (post-increment).
     iterator operator++(int);
-    
+
+
   private:
     /// Constructor, from a pointer into a @c pointer_list.
     iterator (value_type* p);
     friend class pointer_list;
   };
 
+  typedef allocator pool_type;
 
   /// Constructor.  @c pool gives the allocator for this container.
   pointer_list (pool_type& pool);
 
-  /// Add a new element to the end of the container.  O(1)
-  void push_back (value_type p);
-
   /// Iterator at the beginning of the container.
   iterator begin();
 
   /// Iterator at the end of the container.
   iterator end();
 
-  /// The current size of the container.  O(1).
-  size_t size() const;
-
-  /// Erase the container.  O(1).  Note: doesn't free memory.
-  /// Memory currently in use will be reused when the container
-  /// is filled again.
-  void clear();
-
   /// Erase one element.  O(n)
   void erase (iterator it);
-
-  /// Test to see if the container is empty.
-  bool empty() const;
-
-
-private:
-  /// The first block in the list.
-  list_block* m_head;
-
-  /// The current insertion point in the list.
-  value_type* m_insert;
-
-  /// The current list size.
-  size_t m_size;
-
-  /// The list allocator.
-  allocator& m_pool;
-
-  /// Allocate the first block of the list.
-  void firstblock ();
-
-  /// Extend the list with another block.
-  /// @c m_insert should be at the end of the last block.
-  void nextblock ();
-
-  /// Allocate a new block.
-  list_block* getblock();
 };
 
 

CxxUtils/pointer_list.icc

 
 
 #include <cassert>
+#include <algorithm>
 
 
 namespace CxxUtils {
 
 /**
  * @brief Size in bytes of a block holding @c nelt elements.
+ *        (excluding the end-pointer).
  * @param nelt Number of elements.
  */
 inline
-size_t pointer_list::list_block::size (size_t nelt)
+size_t pointer_list_base::list_block::size (size_t nelt)
 {
-  return sizeof(list_block) + (nelt-1) * sizeof(value_type);
-}
-
-
-/**
- * @brief True if @c p has the sentinel bit set.
- * @param p Value to test.
- */
-inline
-bool pointer_list::list_block::is_sentinel (value_type p)
-{
-  return (reinterpret_cast<ulong>(p) & 1) != 0;
-}
-
-
-/**
- * @brief Turn the sentinel bit on for value @c p.
- * @param p Value to which to add the sentinel.
- */
-inline
-pointer_list::list_block::value_type
-pointer_list::list_block::make_sentinel (value_type p)
-{
-  assert (!is_sentinel (p));
-  return reinterpret_cast<value_type>
-    (reinterpret_cast<ulong>(p) | 1);
-}
-
-
-
-/**
- * @brief Extract a pointer from a value.
- * @param p Value from which to extract the pointer.
- */
-inline
-pointer_list::list_block::value_type
-pointer_list::list_block::pointer (value_type p)
-{
-  return reinterpret_cast<value_type>
-    (reinterpret_cast<ulong>(p) & ~(ulong)1 );
+  return sizeof(list_block) + nelt * sizeof(value_type);
 }
 
 
  * @brief Allocate a new block.
  */
 inline
-pointer_list::list_block*
-pointer_list::allocator::allocate()
+pointer_list_base::list_block*
+pointer_list_base::allocator::allocate()
 {
   // Get a new chunk if needed.
   if (m_nthis == m_nblock)
     refill();
-  return &m_chunks->m_blocks[(m_nthis++) * m_nelt];
+  return &m_chunks->m_blocks[(m_nthis++) * (m_nelt+1)];
 }
 
 
 /**
- * @brief Return the number of pointers per block.
+ * @brief Return the number of pointers per block (excluding the end-pointer).
  */
 inline
 size_t
-pointer_list::allocator::nelt() const
+pointer_list_base::allocator::nelt() const
 {
   return m_nelt;
 }
  */
 inline
 size_t
-pointer_list::allocator::nchunks() const
+pointer_list_base::allocator::nchunks() const
 {
   return m_nchunks;
 }
 
 
+/**
+ * @brief Test to see if we're looking at the end of a block.
+ * @param p The pointer to test.
+ */
+inline
+bool
+pointer_list_base::allocator::at_end (const void* p) const
+{
+  return (reinterpret_cast<unsigned long>(p) & m_end_mask) == m_end_offs;
+}
+
+
+/**
+ * @brief Constructor.
+ * @param nblock Number of blocks to allocate per chunk.
+ */
+template <size_t NELT>
+pointer_list<NELT>::allocator::allocator (size_t nblock /*= 100*/)
+  : pointer_list_base::allocator (NELT, nblock, END_MASK, END_OFFS)
+{
+}
+
+
+/**
+ * @brief Test to see if we're looking at the end of a block.
+ * @param p The pointer to test.
+ */
+template <size_t NELT>
+inline
+bool
+pointer_list<NELT>::allocator::at_end_static (const void* p)
+{
+  return (reinterpret_cast<unsigned long>(p) & END_MASK) == END_OFFS;
+}
+
+
 //****************************************************************************
 
 
 /**
  * @brief Equality comparison.
  */
+template <size_t NELT>
 inline
 bool
-pointer_list::iterator::operator== (const iterator& other) const
+pointer_list<NELT>::iterator::operator== (const iterator& other) const
 {
   return m_p == other.m_p;
 }
 /**
  * @brief Inequality comparison.
  */
+template <size_t NELT>
 inline
 bool
-pointer_list::iterator::operator!= (const iterator& other) const
+pointer_list<NELT>::iterator::operator!= (const iterator& other) const
 {
   return m_p != other.m_p;
 }
 /**
  * @brief Dereference.
  */
+template <size_t NELT>
 inline
-pointer_list::iterator::reference
-pointer_list::iterator::operator*() const
+typename pointer_list<NELT>::iterator::reference
+pointer_list<NELT>::iterator::operator*() const
 {
   return *m_p;
 }
 /**
  * @brief Advance (pre-increment).
  */
+template <size_t NELT>
 inline
-pointer_list::iterator&
-pointer_list::iterator::operator++()
+typename pointer_list<NELT>::iterator&
+pointer_list<NELT>::iterator::operator++()
 {
   // Move forward.
   ++m_p;
-  value_type p = *m_p;
 
-  // If we've hit a sentinel, chain to the next block,
-  // if there is one.  Otherwise, stay at the sentinel;
+  // If we've hit the end, chain to the next block,
+  // if there is one.  Otherwise, stay at the end;
   // that will be where the end iterator points.
-  if (list_block::is_sentinel (p)) {
-    list_block* next =      reinterpret_cast<list_block*>
-      (list_block::pointer (p));
+  if (pointer_list::allocator::at_end_static (m_p)) {
+    list_block* next = reinterpret_cast<list_block*> (*m_p);
     if (next)
       m_p = &next->m_data[0];
   }
 /**
  * @brief Advance (post-increment).
  */
+template <size_t NELT>
 inline
-pointer_list::iterator
-pointer_list::iterator::operator++(int)
+typename pointer_list<NELT>::iterator
+pointer_list<NELT>::iterator::operator++(int)
 {
   iterator ret = *this;
   ++*this;
  * @brief Constructor.
  * @param p A value within a @c pointer_list.
  */
+template <size_t NELT>
 inline
-pointer_list::iterator::iterator (value_type* p)
+pointer_list<NELT>::iterator::iterator (value_type* p)
   : m_p (p)
 {
 }
  * @param pool The allocator for this container.
  */
 inline
-pointer_list::pointer_list (pool_type& pool)
+pointer_list_base::pointer_list_base (pool_type& pool)
   : m_head (0),
     m_insert (0),
     m_size (0),
  * @brief Add a new element to the end of the container.  O(1)
  */
 inline
-void pointer_list::push_back (value_type p)
+void pointer_list_base::push_back (value_type p)
 {
   // If the container is empty, allocate the first block.
   if (!m_head)
     firstblock();
 
   // Otherwise, if we're at the end of the current block, allocate a new one.
-  else if (list_block::is_sentinel (*m_insert))
+  else if (m_pool.at_end (m_insert))
     nextblock();
 
   // Add the value to the list.
 
   // If we're at the end of this block, and a following block exists,
   // move to the following block.
-  if (list_block::is_sentinel (*m_insert)) {
-    value_type next = list_block::pointer (*m_insert);
+  if (m_pool.at_end (m_insert)) {
+    value_type next = *m_insert;
     if (next)
       m_insert = reinterpret_cast<value_type*> (next);
   }
 
 
 /**
+ * @brief The current size of the container.  O(1)
+ */
+inline
+size_t pointer_list_base::size() const
+{
+  return m_size;
+}
+
+
+/**
+ * @brief Test to see if the container is empty.
+ */
+inline
+bool pointer_list_base::empty() const
+{
+  return m_size == 0;
+}
+
+
+/**
+ * @brief Constructor.
+ * @param pool The allocator for this container.
+ */
+template <size_t NELT>
+inline
+pointer_list<NELT>::pointer_list (pool_type& pool)
+  : pointer_list_base (pool)
+{
+}
+
+
+/**
  * @brief Iterator at the beginning of the container.
  */
+template <size_t NELT>
 inline
-pointer_list::iterator pointer_list::begin()
+typename pointer_list<NELT>::iterator pointer_list<NELT>::begin()
 {
   // Start by pointing at the first element
   // (or null, if the container's empty).
 /**
  * @brief Iterator at the end of the container.
  */
+template <size_t NELT>
 inline
-pointer_list::iterator pointer_list::end()
+typename pointer_list<NELT>::iterator pointer_list<NELT>::end()
 {
   // Point at the current insertion point.
   // (This will be null if the container's empty.)
 
 
 /**
- * @brief The current size of the container.  O(1)
+ * @brief Erase one element.  O(n)
+ * @param it The element to erase.
  */
-inline
-size_t pointer_list::size() const
+template <size_t NELT>
+void pointer_list<NELT>::erase (iterator it)
 {
-  return m_size;
+  // We just copy the elements back by one.
+  iterator next = it;
+  ++next;
+  next = std::copy (next, end(), it);
+
+  // New insertion point is where the copy stopped.
+  m_insert = next.m_p;
+
+  // One less element.
+  --m_size;
 }
 
 
-/**
- * @brief Test to see if the container is empty.
- */
-inline
-bool pointer_list::empty() const
-{
-  return m_size == 0;
-}
-
-
 } // namespace CxxXUtils

src/pointer_list.cxx

 /**
  * @brief Constructor.
  * @param nelt Number of pointers per block.
+ *             (excluding the end pointer).
  * @param nblock Number of blocks to allocate per chunk.
+ * @param end_mask Mask to use for end-of-block test.
+ * @param end_offs Offset to use for end-of-block test.
  */
-pointer_list::allocator::allocator (size_t nelt /*= 16*/,
-                                    size_t nblock /*= 100*/)
+pointer_list_base::allocator::allocator (size_t nelt,
+                                         size_t nblock,
+                                         unsigned long end_mask,
+                                         unsigned long end_offs)
   : m_nelt (nelt),
     m_nblock (nblock),
     m_chunks (0),
     m_nthis (nblock),
-    m_nchunks (0)
+    m_nchunks (0),
+    m_end_mask (end_mask),
+    m_end_offs (end_offs)
 {
 }
 
 /**
  * @brief Destructor.  Deletes all blocks from this allocator.
  */
-pointer_list::allocator::~allocator()
+pointer_list_base::allocator::~allocator()
 {
   // Loop over the chunks, deleting each one.
   chunk* ch = m_chunks;
 /**
  * @brief Allocate a new chunk of blocks.
  */
-void pointer_list::allocator::refill()
+void pointer_list_base::allocator::refill()
 {
   char* p = new char
-    [(sizeof(chunk) + (m_nblock-1)*list_block::size(m_nelt))];
+    [(sizeof(chunk) + m_nblock*list_block::size(m_nelt)) +
+     list_block::size(m_nelt)-1];
   chunk* ch = reinterpret_cast<chunk*> (p);
+
+  // Align.
+  unsigned long pp = reinterpret_cast<unsigned long> (ch+1);
+  pp = (pp + m_end_mask) & ~m_end_mask;
+  ch->m_blocks = reinterpret_cast<list_block*> (pp);
+
   ch->m_next = m_chunks;
   m_chunks = ch;
   ++m_nchunks;
  * Memory currently in use will be reused when the container
  * is filled again.
  */
-void pointer_list::clear()
+void pointer_list_base::clear()
 {
   if (m_head)
     m_insert = &m_head->m_data[0];
 
 
 /**
- * @brief Erase one element.  O(n)
- * @param it The element to erase.
- */
-void pointer_list::erase (iterator it)
-{
-  // We just copy the elements back by one.
-  iterator next = it;
-  ++next;
-  next = std::copy (next, end(), it);
-
-  // New insertion point is where the copy stopped.
-  m_insert = next.m_p;
-
-  // One less element.
-  --m_size;
-}
-
-
-/**
  * @brief Allocate the first block of the list.
  */
-void pointer_list::firstblock ()
+void pointer_list_base::firstblock ()
 {
   m_head = getblock();
   m_insert = &m_head->m_data[0];
  * @brief Extend the list with another block.
  *        @c m_insert should be at the end of the last block.
  */
-void pointer_list::nextblock ()
+void pointer_list_base::nextblock ()
 {
   // There may be one already allocated.  Use it if so.
   list_block* newblock = 
-    reinterpret_cast<list_block*>
-    (list_block::pointer (*m_insert));
+    reinterpret_cast<list_block*> (*m_insert);
   if (!newblock) {
     newblock = getblock();
-    *m_insert = list_block::make_sentinel (newblock);
+    *m_insert = newblock;
   }
   m_insert = &newblock->m_data[0];
 }
 /**
  * @brief Allocate a new block.
  */
-pointer_list::list_block* pointer_list::getblock ()
+pointer_list_base::list_block* pointer_list_base::getblock ()
 {
   list_block* b = m_pool.allocate();
-  size_t maxndx = m_pool.nelt()-1;
+  size_t maxndx = m_pool.nelt();
 
   // Make sure only the last element has the sentinel bit set.
   std::fill (b->m_data, b->m_data + maxndx, value_type());
-  b->m_data[maxndx] = list_block::make_sentinel (0);
+  b->m_data[maxndx] = 0;
 
   return b;
 }

test/fpcompare_test.cxx

 {
   using namespace CxxUtils::fpcompare;
 
+  assert (   equal (a->pt(), a->pt()) );
+  assert ( ! equal (a->pt(), c->pt()) );
+
   assert ( ! greater (a->pt(), b->pt()) ); // FAILX
   assert (   greater (c->pt(), b->pt()) );
   assert ( ! greater (b->pt(), c->pt()) );
 
   //********************************************************
 
+  assert (   equal (a->ptf(), a->ptf()) );
+  assert ( ! equal (a->ptf(), c->ptf()) );
+
   assert ( ! greater (a->ptf(), b->ptf()) );
   assert (   greater (c->ptf(), b->ptf()) );
   assert ( ! greater (b->ptf(), c->ptf()) );
 {
   using namespace CxxUtils::fpcompare_fn;
 
+  equal eq;
+  assert (   eq (a->pt(), a->pt()) );
+  assert ( ! eq (a->pt(), c->pt()) );
+
   greater gt;
   assert ( ! gt (a->pt(), b->pt()) ); // FAILX
   assert (   gt (c->pt(), b->pt()) );
 
   //********************************************************
 
+  equalf eqf;
+  assert (   eqf (a->ptf(), a->ptf()) );
+  assert ( ! eqf (a->ptf(), c->ptf()) );
+
   greaterf gtf;
   assert ( ! gtf (a->ptf(), b->ptf()) );
   assert (   gtf (c->ptf(), b->ptf()) );

test/pointer_list_test.cxx

 size_t n_toerase = sizeof (toerase) / sizeof (toerase[0]);
 
 
-void testerase (pointer_list& l,
+void testerase (pointer_list<>& l,
                 int nerase,
                 std::vector<int>& v)
 {
   size_t sz = l.size();
-  pointer_list::iterator it = l.begin();
+  pointer_list<>::iterator it = l.begin();
   std::advance (it, toerase[nerase]);
   l.erase (it);
   assert (l.size() == sz-1);
 
   it = l.begin();
-  pointer_list::iterator end = l.end();
+  pointer_list<>::iterator end = l.end();
   size_t i = 0;
   while (it != end) {
     bool skip = false;
 }
 
 
-void testit1 (pointer_list& l, size_t n)
+void testit1 (pointer_list<>& l, size_t n)
 {
   assert (l.size() == 0);
   assert (l.empty());
     assert (l.size() == i+1);
   }
 
-  pointer_list::iterator beg = l.begin();
-  pointer_list::iterator end = l.end();
+  pointer_list<>::iterator beg = l.begin();
+  pointer_list<>::iterator end = l.end();
   size_t i = 0;
   while (beg != end) {
     assert (*beg == &v[i]);
 }
 
 
-void testit (int n, pointer_list::pool_type& pool)
+void testit (int n, pointer_list<>::pool_type& pool)
 {
-  pointer_list l (pool);
+  pointer_list<> l (pool);
   testit1 (l, n);
 
   // Check that if we clear and refill, we don't allocate more memory.
 
 void test1()
 {
-  pointer_list::pool_type pool;
+  pointer_list<>::pool_type pool;
 
   testit (0, pool);
   testit (1, pool);
 
 void test2()
 {
-  pointer_list::pool_type pool;
+  pointer_list<>::pool_type pool;
   std::vector<int> v (35);
-  pointer_list l (pool);
+  pointer_list<> l (pool);
 
   for (size_t i = 0; i < 16; i++)
     l.push_back (&v[i]);
-  pointer_list::iterator pos = l.begin();
+  pointer_list<>::iterator pos = l.begin();
   std::advance (pos, 15);
   l.erase (pos);
   pos = l.begin();
   l.push_back (&v[14]);
 
   pos = l.begin();
-  pointer_list::iterator end = l.end();
+  pointer_list<>::iterator end = l.end();
   size_t j = 0;
   while (pos != end) {
     assert (*pos == &v[j]);