Commits

Anonymous committed b23d31b

gcc 4.4 fixes.

Comments (0)

Files changed (6)

+2010-01-05  scott snyder  <snyder@bnl.gov>
+
+	* Tagging CxxUtils-00-00-43.
+	* test/hashtable_test.cxx: gcc 4.4 fixes.
+	* CxxUtils/fast_push_back.h: gcc 4.4 fixes.
+
 2009-12-09  scott snyder  <snyder@bnl.gov>
 
 	* Tagging CxxUtils-00-00-42.

CxxUtils/chunked_list.h

+// This file's extension implies that it's C, but it's really -*- C++ -*-.
+// $Id$
+/**
+ * xxx
+ * @file  chunked_list.h
+ * @author scott snyder <snyder@bnl.gov>
+ * @date Aug, 2008
+ * @brief A fast way to store a variable-sized collection of pointers.
+ *
+ * ??? Is this of more general use?  Move to another package?
+ *
+ * A fast way to store a variable-sized collection of pointers.
+ *
+ * The list is a set of fixed-size blocks, each holding 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.
+ *
+ * We do allocations from a pool, so we don't worry about deleting these.
+ */
+
+
+#include <iterator>
+#include <algorithm>
+#include <memory>
+
+
+namespace CxxUtils {
+
+
+template <class T>
+struct chunked_list_traits
+{
+  typedef T& reference;
+  typedef const T& const_reference;
+
+  struct holder_type
+  {
+    union
+    {
+      T m_val;
+      void* m_pointer;
+    } m_u;
+    bool m_sentinel;
+
+    holder_type()
+      : m_sentinel (false)
+    {
+    }
+  };
+
+  static bool is_sentinel (const holder_type& t) { return t.m_sentinel; }
+  static void* pointer (const holder_type& t) { return t.m_u.m_pointer; }
+  static reference value (holder_type& t) { return t.m_u.m_val; }
+  static const_reference value (const holder_type& t) { return t.m_u.m_val; }
+  static void store (holder_type& t, const T& v)
+  {
+    t.m_u.m_val = v;
+  }
+  static void make_sentinel (holder_type& t, void* p)
+  {
+    t.m_sentinel = true;
+    t.m_u.m_pointer = p;
+  }
+};
+
+
+template <class T>
+struct chunked_list_traits<T*>
+{
+  typedef T* holder_type;
+  typedef T* & reference;
+  typedef T* const & const_reference;
+  typedef unsigned long ulong;
+
+  static bool is_sentinel (holder_type p)
+  {
+    return (reinterpret_cast<ulong>(p) & 1) != 0;
+  }
+
+  static void* pointer (holder_type p)
+  {
+    return reinterpret_cast<void*>
+      (reinterpret_cast<ulong>(p) & ~(ulong)1 );
+  }
+
+  static reference value (holder_type& p) { return p; }
+  static const_reference value (const holder_type& p) { return p; }
+
+  static void store (holder_type& t, T* v)
+  {
+    t = v;
+  }
+
+  static void make_sentinel (holder_type& t, void* p)
+  {
+    t = reinterpret_cast<holder_type>
+      (reinterpret_cast<ulong>(p) | 1);
+  }
+};
+
+
+template <class traits>
+struct chunked_list_block
+{
+public:
+  static const int nblock = 16;
+  typename traits::holder_type m_data[nblock];
+};
+
+
+template <class T,
+          template <class T> class allocatorT = std::allocator,
+          class traits = chunked_list_traits<T> >
+class chunked_list
+{
+public:
+  typedef chunked_list_block<traits> block;
+  typedef T value_type;
+  typedef typename traits::holder_type holder_type;
+  typedef allocatorT<T> allocator;
+
+  class iterator
+    : public std::iterator<std::forward_iterator_tag, value_type>
+  {
+  public:
+    typedef std::iterator<std::forward_iterator_tag, value_type> Base;
+    typedef typename Base::reference reference;
+
+    iterator (holder_type* p) : m_p (p) {}
+    bool operator== (const iterator& other) { return m_p == other.m_p; }
+    bool operator!= (const iterator& other) { return m_p != other.m_p; }
+    reference operator*() { return traits::value (*m_p); }
+    iterator& operator++()
+    {
+      ++m_p;
+      const holder_type& p = *m_p;
+      if (traits::is_sentinel (p)) {
+        block* next = reinterpret_cast<block*> (traits::pointer (p));
+        if (next)
+          m_p = &next->m_data[0];
+      }
+      return *this;
+    }
+    iterator operator++(int)
+    {
+      iterator ret = *this;
+      ++*this;
+      return ret;
+    }
+    
+  private:
+    holder_type* m_p;
+  };
+
+  chunked_list()
+    : m_head (0),
+      m_insert (0),
+      m_size (0)
+  {}
+
+  void push_back (value_type p, allocator& pool)
+  {
+    if (!m_head)
+      firstblock(pool);
+    else if (traits::is_sentinel (*m_insert))
+      nextblock(pool);
+
+    traits::store (*m_insert, p);
+    ++m_insert;
+    ++m_size;
+
+    if (traits::is_sentinel (*m_insert)) {
+      holder_type* next =
+        reinterpret_cast<holder_type*> (traits::pointer (p));
+      if (next)
+        m_insert = next;
+    }
+  }
+
+  iterator begin()
+  {
+    return iterator (m_head ? &m_head->m_data[0] : 0);
+  }
+
+  iterator end()
+  {
+    return iterator (m_insert);
+  }
+
+  size_t size() const
+  {
+    return m_size;
+  }
+
+
+  void clear();
+
+  void erase (iterator it);
+
+  bool empty() const
+  {
+    return m_size == 0;
+  }
+
+
+private:
+  block* m_head;
+  typename traits::holder_type* m_insert;
+  size_t m_size;
+
+  void firstblock (allocator& pool);
+  void nextblock (allocator& pool);
+  block* allocate_block (allocator& pool);
+};
+
+
+template <class T,
+          template <class T> class allocatorT,
+          class traits>
+void chunked_list<T, allocatorT, traits>::clear()
+{
+  if (m_head)
+    m_insert = &m_head->m_data[0];
+  m_size = 0;
+}
+
+
+template <class T,
+          template <class T> class allocatorT,
+          class traits>
+void chunked_list<T, allocatorT, traits>::erase (iterator it)
+{
+  iterator next = it;
+  ++next;
+  next = std::copy (next, end(), it);
+  m_insert = next.m_p;
+  --m_size;
+}
+
+
+template <class T,
+          template <class T> class allocatorT,
+          class traits>
+typename chunked_list<T, allocatorT, traits>::block*
+chunked_list<T, allocatorT, traits>::allocate_block (allocator& pool)
+{
+  block* b = pool.allocate(1);
+  std::fill (b->m_data, b->m_data + block::nblock-1, holder_type());
+  b->m_data[block::nblock-1] = traits::make_sentinel (0);
+  return b;
+}
+
+
+template <class T,
+          template <class T> class allocatorT,
+          class traits>
+void chunked_list<T, allocatorT, traits>::firstblock (allocator& pool)
+{
+  m_head = allocate_block (pool);
+  m_insert = &m_head->m_data[0];
+}
+
+
+template <class T,
+          template <class T> class allocatorT,
+          class traits>
+void chunked_list<T, allocatorT, traits>::nextblock (allocator& pool)
+{
+  block* newblock = 
+    reinterpret_cast<block*> (traits::pointer (*m_insert));
+  if (!newblock) {
+    newblock = allocate_block (pool);
+    *m_insert = traits::make_sentinel (newblock);
+  }
+  m_insert = &newblock->m_data[0];
+}
+    
+
+
+
+} // namespace CxxUtils

CxxUtils/fast_push_back.h

  * We support up to four arguments to the element constructor.
  *
  * Note that there's standard solution for this in the new C++0x standard.
- * In that version, @c vector supports an emplacement @c push_back,
+ * In that version, @c vector supports an emplacement inserter,
  * where instead of
  *
  *@code
  * one can do 
  *
  *@code
- *  v.push_back (0, 1);
+ *  v.emplace_back (0, 1);
  @endcode
  *
  * to avoid the extra constructors.  We'll use this form if we know
 void fast_push_back (V& v)
 {
 #ifdef HAVE_SG_EMPLACEMENT
-  v.push_back ();
+  v.emplace_back ();
 #else
 # ifdef HAVE_SG_UNINITIALIZED_PUSH_BACK
   new (uninitialized_push_back (v)) typename V::value_type;
 void fast_push_back (V& v, const T1& x1)
 {
 #ifdef HAVE_SG_EMPLACEMENT
-  v.push_back (x1);
+  v.emplace_back (x1);
 #else
 # ifdef HAVE_SG_UNINITIALIZED_PUSH_BACK
   new (uninitialized_push_back (v)) typename V::value_type (x1);
 void fast_push_back (V& v, T1& x1)
 {
 #ifdef HAVE_SG_EMPLACEMENT
-  v.push_back (x1);
+  v.emplace_back (x1);
 #else
 # ifdef HAVE_SG_UNINITIALIZED_PUSH_BACK
   new (uninitialized_push_back (v)) typename V::value_type (x1);
 void fast_push_back (V& v, const T1& x1, const T2& x2)
 {
 #ifdef HAVE_SG_EMPLACEMENT
-  v.push_back (x1, x2);
+  v.emplace_back (x1, x2);
 #else
 # ifdef HAVE_SG_UNINITIALIZED_PUSH_BACK
   new (uninitialized_push_back (v)) typename V::value_type (x1, x2);
 void fast_push_back (V& v, T1& x1, const T2& x2)
 {
 #ifdef HAVE_SG_EMPLACEMENT
-  v.push_back (x1, x2);
+  v.emplace_back (x1, x2);
 #else
 # ifdef HAVE_SG_UNINITIALIZED_PUSH_BACK
   new (uninitialized_push_back (v)) typename V::value_type (x1, x2);
 void fast_push_back (V& v, const T1& x1, const T2& x2, const T3& x3)
 {
 #ifdef HAVE_SG_EMPLACEMENT
-  v.push_back (x1, x2, x3);
+  v.emplace_back (x1, x2, x3);
 #else
 # ifdef HAVE_SG_UNINITIALIZED_PUSH_BACK
   new (uninitialized_push_back (v)) typename V::value_type (x1, x2, x3);
 void fast_push_back (V& v, T1& x1, const T2& x2, const T3& x3)
 {
 #ifdef HAVE_SG_EMPLACEMENT
-  v.push_back (x1, x2, x3);
+  v.emplace_back (x1, x2, x3);
 #else
 # ifdef HAVE_SG_UNINITIALIZED_PUSH_BACK
   new (uninitialized_push_back (v)) typename V::value_type (x1, x2, x3);
                      const T1& x1, const T2& x2, const T3& x3, const T4& x4)
 {
 #ifdef HAVE_SG_EMPLACEMENT
-  v.push_back (x1, x2, x3, x4);
+  v.emplace_back (x1, x2, x3, x4);
 #else
 # ifdef HAVE_SG_UNINITIALIZED_PUSH_BACK
   new (uninitialized_push_back (v)) typename V::value_type (x1, x2, x3, x4);
                      T1& x1, const T2& x2, const T3& x3, const T4& x4)
 {
 #ifdef HAVE_SG_EMPLACEMENT
-  v.push_back (x1, x2, x3, x4);
+  v.emplace_back (x1, x2, x3, x4);
 #else
 # ifdef HAVE_SG_UNINITIALIZED_PUSH_BACK
   new (uninitialized_push_back (v)) typename V::value_type (x1, x2, x3, x4);

src/chunked_list.cxx

+// $Id: pointer_list.cxx,v 1.1 2008/08/28 05:15:06 ssnyder Exp $
+/**
+ * @file  pointer_list.cxx
+ * @author scott snyder <snyder@bnl.gov>
+ * @date Aug, 2008
+ * @brief A fast way to store a variable-sized collection of pointers.
+ */
+
+
+#include "CxxUtils/chunked_list.h"
+
+

test/chunked_list_test.cxx

+// $Id: pointer_list_test.cxx,v 1.2 2008/12/23 02:57:16 ssnyder Exp $
+/**
+ * @file  chunked_list_test.cpp
+ * @author scott snyder <snyder@bnl.gov>
+ * @date Aug, 2008
+ * @brief Unit test for chunked_list.
+ */
+
+#undef NDEBUG
+
+
+#include "CxxUtils/chunked_list.h"
+#include <vector>
+#include <cassert>
+
+
+using namespace CxxUtils;
+
+
+#if 0
+size_t toerase[] = {
+  0, 1, 5, 14, 15, 16, 17, 20, 29, 30, 31, 500
+};
+size_t n_toerase = sizeof (toerase) / sizeof (toerase[0]);
+
+
+void testerase (pointer_list& l,
+                int nerase,
+                std::vector<int>& v)
+{
+  size_t sz = l.size();
+  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();
+  size_t i = 0;
+  while (it != end) {
+    bool skip = false;
+    for (int j=0; j <= nerase; j++) {
+      if (i == toerase[j]+j) {
+        skip = true;
+        break;
+      }
+    }
+    if (!skip) {
+      assert (*it == &v[i]);
+      ++it;
+    }
+    ++i;
+  }
+
+  assert (it == end);
+}
+
+
+void testit1 (pointer_list& l, size_t n, pointer_list_block::pool_type& pool)
+{
+  assert (l.size() == 0);
+  assert (l.empty());
+
+  std::vector<int> v (n);
+  for (size_t i = 0; i < n; i++) {
+    l.push_back (&v[i], pool);
+    assert (l.size() == i+1);
+  }
+
+  pointer_list::iterator beg = l.begin();
+  pointer_list::iterator end = l.end();
+  size_t i = 0;
+  while (beg != end) {
+    assert (*beg == &v[i]);
+    ++beg;
+    ++i;
+  }
+  assert (beg == end);
+  assert (i == n);
+  if (n > 0)
+    assert (!l.empty());
+
+  if (n > 2) {
+    beg = l.begin();
+    assert (*++beg == &v[1]);
+    assert (*beg == &v[1]);
+    beg = l.begin();
+    assert (*beg++ == &v[0]);
+    assert (*beg == &v[1]);
+  }
+
+  for (size_t i = 0; i < n_toerase; i++) {
+    if (toerase[i] >= l.size())
+      break;
+    testerase (l, i, v);
+  }
+}
+#endif
+
+
+template <class list>
+void testit (int n, typename list::allocator& pool)
+{
+  list l;
+#if 0
+  testit1 (l, n, pool);
+
+  // Check that if we clear and refill, we don't allocate more memory.
+  size_t inuse = pool.stats().elts.inuse;
+  l.clear();
+  testit1 (l, n, pool);
+  assert (pool.stats().elts.inuse == inuse);
+#endif
+}
+
+
+void test1()
+{
+  typedef chunked_list<int*> list;
+  list::allocator pool;
+
+  testit<list> (0, pool);
+#if 0
+  testit (1, pool);
+  testit (5, pool);
+  testit (14, pool);
+  testit (15, pool);
+  testit (16, pool);
+  testit (17, pool);
+  testit (29, pool);
+  testit (30, pool);
+  testit (31, pool);
+  testit (1000, pool);
+
+  pool.erase();
+#endif
+}
+
+
+#if 0
+void test2()
+{
+  pointer_list_block::pool_type pool;
+  std::vector<int> v (35);
+  pointer_list l;
+
+  for (size_t i = 0; i < 16; i++)
+    l.push_back (&v[i], pool);
+  pointer_list::iterator pos = l.begin();
+  std::advance (pos, 15);
+  l.erase (pos);
+  pos = l.begin();
+  std::advance (pos, 14);
+  l.erase (pos);
+  l.push_back (&v[14], pool);
+
+  pos = l.begin();
+  pointer_list::iterator end = l.end();
+  size_t j = 0;
+  while (pos != end) {
+    assert (*pos == &v[j]);
+    ++pos;
+    ++j;
+  }
+
+  pool.erase();
+}
+#endif
+
+
+int main()
+{
+  test1();
+  //test2();
+  return 0;
+}

test/hashtable_test.cxx

   using namespace std;
   using namespace SG;
 
-  unordered_map<int, char, hash<int>, equal_to<int>,
+  unordered_map<int, char, SG::hash<int>, equal_to<int>,
     allocator<pair<const int, char> >, true> m;
  
   for (int i = 0; i < 1000; ++i)
 using namespace SG;
 
 // Verify that we can instantiate hash for every required type.
-template class hash<bool>;
-template class hash<char>;
-template class hash<signed char>;
-template class hash<unsigned char>;
-template class hash<short>;
-template class hash<int>;
-template class hash<long>;
-template class hash<unsigned short>;
-template class hash<unsigned int>;
-template class hash<unsigned long>;
-template class hash<float>;
-template class hash<double>;
-template class hash<long double>;
-template class hash<void*>;
-template class hash<std::string>;
+template class SG::hash<bool>;
+template class SG::hash<char>;
+template class SG::hash<signed char>;
+template class SG::hash<unsigned char>;
+template class SG::hash<short>;
+template class SG::hash<int>;
+template class SG::hash<long>;
+template class SG::hash<unsigned short>;
+template class SG::hash<unsigned int>;
+template class SG::hash<unsigned long>;
+template class SG::hash<float>;
+template class SG::hash<double>;
+template class SG::hash<long double>;
+template class SG::hash<void*>;
+template class SG::hash<std::string>;
 
 #ifdef _GLIBCXX_USE_WCHAR_T
-template class hash<wchar_t>;
-template class hash<std::wstring>;
+template class SG::hash<wchar_t>;
+template class SG::hash<std::wstring>;
 #endif
 
 
 template class unordered_map<string, float>;
 template class unordered_map<string, float,
-			     hash<string>, equal_to<string>, 
+			     SG::hash<string>, equal_to<string>, 
 			     allocator<pair<const string, float> >, true>;
 
 
 template class unordered_multimap<string, float>;
 template class unordered_multimap<string, float,
-				  hash<string>, equal_to<string>, 
+				  SG::hash<string>, equal_to<string>, 
 				  allocator<pair<const string, float> >, true>;
 
 
 template class unordered_multiset<int>;
-template class unordered_multiset<int, hash<int>, equal_to<int>,
+template class unordered_multiset<int, SG::hash<int>, equal_to<int>,
 				  allocator<int>, true>;
 
 
 template class unordered_set<int>;
-template class unordered_set<int, hash<int>, equal_to<int>,
+template class unordered_set<int, SG::hash<int>, equal_to<int>,
 			     allocator<int>, true>;