[pan2: 3/68] Change allocation buffer for article tree.

[Petr Kovář <pmkovar src gnome org>]

commit fd6949eb17f9264ab4aeb8cab322936c56d91937
Author: K. Haley <haleykd users sf net>
Date:   Sun Jul 5 23:51:43 2009 -0600

    Change allocation buffer for article tree.
    
    Previous impelemntation used std::deque as allocation buffer for articles and nodes in tree.  This was not as efficient as it should have been since the gcc implementation only allocated 512 bytes at a time.  I've added a paired down version optimized for this usage that allocates 8KB at a time.

 pan/data-impl/data-impl.h |    7 ++-
 pan/data-impl/memchunk.h  |  111 +++++++++++++++++++++++++++++++++++++++++++++
 pan/data-impl/my-tree.cc  |    5 +-
 3 files changed, 117 insertions(+), 6 deletions(-)
---
diff --git a/pan/data-impl/data-impl.h b/pan/data-impl/data-impl.h
index 87d660f..f573eb1 100644
--- a/pan/data-impl/data-impl.h
+++ b/pan/data-impl/data-impl.h
@@ -40,6 +40,7 @@
 #include <pan/data-impl/data-io.h>
 #include <pan/data-impl/article-filter.h>
 #include <pan/data-impl/profiles.h>
+#include <pan/data-impl/memchunk.h>
 
 namespace pan
 {
@@ -357,8 +358,8 @@ namespace pan
         int _ref;
         bool _dirty;
         nodes_t _nodes;
-        std::deque<Article> _art_chunk;
-        std::deque<ArticleNode> _node_chunk;
+        MemChunk<Article> _art_chunk;
+        MemChunk<ArticleNode> _node_chunk;
 
         GroupHeaders();
         ~GroupHeaders ();
@@ -442,7 +443,7 @@ namespace pan
           const Quark _group;
           DataImpl & _data;
           nodes_t _nodes;
-          std::deque<ArticleNode> _node_chunk;
+          MemChunk<ArticleNode> _node_chunk;
           FilterInfo _filter;
           Data::ShowType _show_type;
           struct NodeMidCompare;
diff --git a/pan/data-impl/memchunk.h b/pan/data-impl/memchunk.h
new file mode 100644
index 0000000..a96ff1c
--- /dev/null
+++ b/pan/data-impl/memchunk.h
@@ -0,0 +1,111 @@
+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/*
+ * Pan - A Newsreader for Gtk+
+ * Copyright (C) 2002-2006  Charles Kerr <charles rebelbase com>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; version 2 of the License.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+#ifndef __MemChunk_h__
+#define __MemChunk_h__
+
+#include <cstring>
+
+namespace pan {
+  template <class T> class MemChunk
+  {
+    public:
+      void push_back(const T& src)
+      {
+        if (count==nelem) grow();
+        T* thead=head;
+        new(thead) T(src);
+        phead=thead;
+        ++head;
+        ++count;
+      }
+      T& back()
+      {
+        return *phead;
+      }
+      T* alloc()
+      {
+        push_back(T());
+        return phead;
+      }
+
+      MemChunk():chunks(0),head(0),phead(0),nelem(Chunk::size/sizeof(T)),count(0)
+      {grow();}
+
+      ~MemChunk()
+      {
+        Chunk *p;
+        T *t;
+        int i;
+        //special handling for first chunk since it's not full
+        t=reinterpret_cast<T*>(chunks->mem);
+        for (i=0;i<count;i++)
+        {
+          t[i].~T();
+        }
+        p=chunks;
+        chunks=chunks->next;
+        delete p;
+
+        while(chunks!=0)
+        {
+          t=reinterpret_cast<T*>(chunks->mem);
+          for (i=0;i<nelem;i++)
+          {
+            t[i].~T();
+          }
+          p=chunks;
+          chunks=chunks->next;
+          delete p;
+        }
+      }
+
+
+    private:
+      template<class U> MemChunk(MemChunk<U>&);
+      MemChunk* operator=(const MemChunk&);
+
+      struct Chunk {
+        enum {size=16*1024-sizeof(Chunk*)-32};
+        char mem[size];
+        Chunk *next;
+      };
+
+      void grow()
+      {
+        Chunk *c=new Chunk;
+        T *p,*n=0;
+        int i;
+
+        memset(c->mem,0,Chunk::size);
+
+        c->next=chunks;
+        count=0;
+        chunks=c;
+        head=reinterpret_cast<T*>(c->mem);
+      };
+
+      Chunk *chunks;
+      T *phead, *head;
+      const int nelem;
+      int count;
+  };
+
+}
+#endif
diff --git a/pan/data-impl/my-tree.cc b/pan/data-impl/my-tree.cc
index 0758195..fa0e3cc 100644
--- a/pan/data-impl/my-tree.cc
+++ b/pan/data-impl/my-tree.cc
@@ -26,6 +26,7 @@
 #include <pan/data/article.h>
 #include "article-filter.h"
 #include "data-impl.h"
+#include "memchunk.h"
 
 using namespace pan;
 
@@ -388,13 +389,11 @@ DataImpl :: MyTree :: add_articles (const const_nodes_v& nodes_in)
   }
 
   // build new MyTree nodes for each of the articles being added
-  int node_index (_node_chunk.size());
-  _node_chunk.resize (_node_chunk.size() + nodes.size());
   nodes_v tree_nodes;
   tree_nodes.reserve (nodes.size());
   foreach_const (const_nodes_v, nodes, it) {
     const Article * a ((*it)->_article);
-    ArticleNode * node (&_node_chunk[node_index++]);
+    ArticleNode * node (_node_chunk.alloc());
     node->_mid = a->message_id;
     node->_article = const_cast<Article*>(a);
     //std::cerr << LINE_ID << " added " << node->_mid << " to the tree\n";