[Assorted-commits] SF.net SVN: assorted:[1346] cpp-commons/trunk/src/commons/versioned_heap.h

[<yan...@us...>]

Revision: 1346
          http://assorted.svn.sourceforge.net/assorted/?rev=1346&view=rev
Author:   yangzhang
Date:     2009-04-29 02:07:17 +0000 (Wed, 29 Apr 2009)

Log Message:
-----------
added versioned heap

Added Paths:
-----------
    cpp-commons/trunk/src/commons/versioned_heap.h

Added: cpp-commons/trunk/src/commons/versioned_heap.h
===================================================================
--- cpp-commons/trunk/src/commons/versioned_heap.h	                        (rev 0)
+++ cpp-commons/trunk/src/commons/versioned_heap.h	2009-04-29 02:07:17 UTC (rev 1346)
@@ -0,0 +1,86 @@
+#ifndef VERSIONED_HEAP_H
+#define VERSIONED_HEAP_H
+
+#define _POSIX_C_SOURCE 200112L
+#include <cstdlib>
+#include <vector>
+#include <boost/foreach.hpp>
+#define foreach BOOST_FOREACH
+
+namespace commons
+{
+
+  using namespace std;
+
+  /**
+   * A simple object memory pool that places things into pages that are tagged
+   * with a version number.
+   */
+  template<typename T, typename VersionType = int>
+  class versioned_heap
+  {
+    public:
+      typedef VersionType version_type;
+      typedef T value_type;
+      struct hdr {
+        version_type version;
+        uint32_t index;
+      };
+      versioned_heap(size_t pgsz = 131072) :
+        pgsz_(pgsz), pgcnt_((pgsz - sizeof(hdr)) / sizeof(T)) {}
+      ~versioned_heap() {
+        foreach (char *page, pages_) ::free(page);
+      }
+      T &construct(version_type version = 0) {
+        for (size_t i = 0; i < freemap_.size(); ++i) {
+          if (freemap_[i]) {
+            freemap_[i] = false;
+            char *pos = pages_[i / pgcnt_] + sizeof(hdr) +
+                        (i % pgcnt_) * sizeof(T);
+            if (version == 0) ++hdrof(pos).version;
+            else hdrof(pos).version = version;
+            return *new (pos) T;
+          }
+        }
+        char *page;
+        posix_memalign(reinterpret_cast<void**>(&page), pgsz_, pgsz_);
+        hdr &h = *reinterpret_cast<hdr*>(page);
+        h.version = version;
+        h.index = uint32_t(pages_.size());
+        pages_.push_back(page);
+        freemap_.resize(freemap_.size() + pgcnt_, true);
+        freemap_[freemap_.size() - pgcnt_] = false;
+        return *new (page + sizeof(hdr)) T;
+      }
+      void free(T &x, version_type version = 0) {
+        x.~T();
+        hdr &h = hdrof(&x);
+        if (version == 0) ++h.version;
+        else h.version = version;
+        char *px = reinterpret_cast<char*>(&x);
+        char *p0 = reinterpret_cast<char*>(&h + 1);
+        freemap_[h.index * pgcnt_ + (px - p0) / sizeof(T)] = true;
+      }
+      void touch(T &p) { ++hdrof(&p).version; }
+      void touch(T &p, version_type version) { hdrof(&p).version = version; }
+      size_t pgcnt() const { return pgcnt_; }
+      size_t pgsz() const { return pgsz_; }
+      const vector<char*> &pages() const { return pages_; }
+      /** Pronounced "header of". */
+      const hdr &hdrof(void *p) const {
+        return *reinterpret_cast<hdr*>(uintptr_t(p) & ~(pgsz_ - 1));
+      }
+      hdr &hdrof(void *p) {
+        return *reinterpret_cast<hdr*>(uintptr_t(p) & ~(pgsz_ - 1));
+      }
+    private:
+      size_t pgsz_;
+      size_t pgcnt_;
+      vector<bool> freemap_;
+      vector<char*> pages_;
+  };
+
+}
+
+#undef foreach
+#endif


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.