[Assorted-commits] SF.net SVN: assorted:[1358] cpp-commons/trunk/src
Brought to you by:
yangzhang
Menu
▾
▴
[Assorted-commits] SF.net SVN: assorted:[1358] cpp-commons/trunk/src
|
From: <yan...@us...> - 2009-04-30 15:57:03
|
Revision: 1358
http://assorted.svn.sourceforge.net/assorted/?rev=1358&view=rev
Author: yangzhang
Date: 2009-04-30 15:56:53 +0000 (Thu, 30 Apr 2009)
Log Message:
-----------
added serialization/deserialization to versioned_heap; added nbits2nints, getbit, setbit
Modified Paths:
--------------
cpp-commons/trunk/src/commons/memory.h
cpp-commons/trunk/src/commons/versioned_heap.h
cpp-commons/trunk/src/test/Makefile
cpp-commons/trunk/src/test/versioned_heap.cc
Modified: cpp-commons/trunk/src/commons/memory.h
===================================================================
--- cpp-commons/trunk/src/commons/memory.h 2009-04-29 20:45:50 UTC (rev 1357)
+++ cpp-commons/trunk/src/commons/memory.h 2009-04-30 15:56:53 UTC (rev 1358)
@@ -61,6 +61,25 @@
void skip(size_t n) { p_ += n; }
};
+ size_t nbits2nints(size_t nbits) {
+ return (nbits + 31) / 32;
+ }
+
+ template<typename T>
+ bool getbit(T x, size_t bit) {
+ return (x >> bit) & 1;
+ }
+
+ template<typename T>
+ T setbit(T x, size_t bit) {
+ return x | (1U << bit);
+ }
+
+ template<typename T>
+ T setbit(T x, size_t bit, T val) {
+ return x | (val << bit);
+ }
+
}
#endif
Modified: cpp-commons/trunk/src/commons/versioned_heap.h
===================================================================
--- cpp-commons/trunk/src/commons/versioned_heap.h 2009-04-29 20:45:50 UTC (rev 1357)
+++ cpp-commons/trunk/src/commons/versioned_heap.h 2009-04-30 15:56:53 UTC (rev 1358)
@@ -5,6 +5,7 @@
#include <cstdlib>
#include <vector>
#include <boost/foreach.hpp>
+#include <commons/memory.h>
#define foreach BOOST_FOREACH
namespace commons
@@ -25,42 +26,69 @@
struct hdr {
version_type version;
uint32_t index;
+ bool managed;
};
versioned_heap(size_t pgsz = 131072) :
- pgsz_(pgsz), pgcnt_((pgsz - sizeof(hdr)) / sizeof(T)) {}
+ last_i_(0), pgsz_(pgsz), pgcnt_((pgsz - sizeof(hdr)) / sizeof(T)) {}
+ /** Frees all pages, without destroying the objects. */
~versioned_heap() {
- foreach (char *page, pages_) ::free(page);
+ foreach (char *page, pages_)
+ if (hdrof(page).managed)
+ ::free(page);
}
- T &construct(version_type version = 0) {
- for (size_t i = 0; i < freemap_.size(); ++i) {
+ char *alloc() {
+ for (size_t counter = 1; counter <= freemap_.size(); ++counter) {
+ size_t i = (last_i_ + counter) % freemap_.size();
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;
+ ++hdrof(pos).version;
+ last_i_ = i;
+ return pos;
}
}
char *page;
posix_memalign(reinterpret_cast<void**>(&page), pgsz_, pgsz_);
hdr &h = *reinterpret_cast<hdr*>(page);
- h.version = version;
+ h.version = 0;
h.index = uint32_t(pages_.size());
+ h.managed = true;
pages_.push_back(page);
freemap_.resize(freemap_.size() + pgcnt_, true);
freemap_[freemap_.size() - pgcnt_] = false;
- return *new (page + sizeof(hdr)) T;
+ return page + sizeof(hdr);
}
- void free(T &x, version_type version = 0) {
- x.~T();
- hdr &h = hdrof(&x);
+ T &construct() {
+ char *buf = alloc();
+ try { return *new (buf) T; }
+ catch (...) { free(buf); throw; }
+ }
+ // TODO: replace with code gen
+ template<typename A0>
+ T &construct(const A0 &a0) {
+ char *buf = alloc();
+ try { return *new (buf) T(a0); }
+ catch (...) { free(buf); throw; }
+ }
+ template<typename A0, typename A1>
+ T &construct(const A0 &a0, const A1 &a1) {
+ char *buf = alloc();
+ try { return *new (buf) T(a0, a1); }
+ catch (...) { free(buf); throw; }
+ }
+ void free(void *p, version_type version = 0) {
+ hdr &h = hdrof(p);
if (version == 0) ++h.version;
else h.version = version;
- char *px = reinterpret_cast<char*>(&x);
+ char *px = reinterpret_cast<char*>(p);
char *p0 = reinterpret_cast<char*>(&h + 1);
freemap_[h.index * pgcnt_ + (px - p0) / sizeof(T)] = true;
}
+ void destroy(T &x, version_type version = 0) {
+ x.~T();
+ free(&x, version);
+ }
void touch(T &p) { ++hdrof(&p).version; }
void touch(T &p, version_type version) { hdrof(&p).version = version; }
size_t pgcnt() const { return pgcnt_; }
@@ -73,13 +101,115 @@
hdr &hdrof(void *p) {
return *reinterpret_cast<hdr*>(uintptr_t(p) & ~(pgsz_ - 1));
}
+
+ /**
+ * Calculate the required space for serializing the metadata.
+ */
+ size_t metasize() const {
+ return sizeof last_i_ + sizeof pgsz_ + sizeof pgcnt_ +
+ sizeof freemap_.size() +
+ nbits2nints(freemap_.size()) * sizeof(uint32_t) +
+ sizeof datasize(*this);
+ }
+
+ /**
+ * Calculate the required space for serializing the metadata and data.
+ */
+ size_t sersize() const {
+ return metasize() + datasize(*this);
+ }
+
+ /**
+ * Serializes metadata and data to out buffer.
+ */
+ void ser(void *meta, void *data) const {
+ raw_writer w(meta);
+
+ // Serialize metadata.
+ w.write(last_i_);
+ w.write(pgsz_);
+ w.write(pgcnt_);
+
+ // Serialize freemap.
+ w.write(freemap_.size());
+ size_t freesize = nbits2nints(freemap_.size());
+ for (size_t i = 0; i < freesize; ++i) {
+ uint32_t val = 0;
+ for (size_t j = 0; j < 32 && 32 * i + j < freemap_.size(); ++j) {
+ val = setbit(val, j, uint32_t(freemap_[32 * i + j]));
+ }
+ w.write(val);
+ }
+
+ // Serialize data.
+ w.write(datasize(*this));
+ serdata(*this, data);
+ }
+
+ /**
+ * Deserializes a heap in-place.
+ */
+ void deser(void *meta, void *data) {
+ raw_reader r(meta);
+
+ // Deserialize metadata.
+ r.read(last_i_);
+ r.read(pgsz_);
+ r.read(pgcnt_);
+
+ // Deserialize freemap.
+ size_t nbits;
+ r.read(nbits);
+ size_t nints = nbits2nints(nbits);
+ for (size_t i = 0; i < nints; ++i) {
+ uint32_t val;
+ r.read(val);
+ for (size_t j = 0; j < nbits && 32 * i + j < nbits; ++j) {
+ freemap_.push_back(getbit(val, j));
+ }
+ }
+
+ // Deserialize data.
+ size_t datasize;
+ r.read(datasize);
+ char *p0 = reinterpret_cast<char*>(data);
+ for (char *p = p0; p < p0 + datasize; p += pgsz_) {
+ hdrof(p).managed = false;
+ pages_.push_back(p);
+ }
+ }
+
private:
+ size_t last_i_;
size_t pgsz_;
size_t pgcnt_;
vector<bool> freemap_;
vector<char*> pages_;
};
+ /**
+ * Calculate the data size of a heap.
+ */
+ template<typename T>
+ size_t datasize(const versioned_heap<T> &h)
+ {
+ return h.pages().size() * h.pgsz();
+ }
+
+ /**
+ * Copies pages from the heap into the out buffer. Assumes out is big enough
+ * (see datasize).
+ */
+ template<typename T>
+ void serdata(const versioned_heap<T> &h, void *out)
+ {
+ char *p = reinterpret_cast<char*>(out);
+ foreach (void *page, h.pages()) {
+ memcpy(p, page, h.pgsz());
+ p += h.pgsz();
+ }
+ }
+
}
#undef foreach
Modified: cpp-commons/trunk/src/test/Makefile
===================================================================
--- cpp-commons/trunk/src/test/Makefile 2009-04-29 20:45:50 UTC (rev 1357)
+++ cpp-commons/trunk/src/test/Makefile 2009-04-30 15:56:53 UTC (rev 1358)
@@ -1,4 +1,5 @@
CXXFLAGS = \
+ -MD \
-g3 \
-Wall \
-Werror \
@@ -46,3 +47,5 @@
squeue: LDLIBS += -lboost_thread-gcc43-mt
.PHONY: all build clean
+
+-include *.d
Modified: cpp-commons/trunk/src/test/versioned_heap.cc
===================================================================
--- cpp-commons/trunk/src/test/versioned_heap.cc 2009-04-29 20:45:50 UTC (rev 1357)
+++ cpp-commons/trunk/src/test/versioned_heap.cc 2009-04-30 15:56:53 UTC (rev 1358)
@@ -1,3 +1,5 @@
+#include <commons/check.h>
+#include <commons/unique_ptr.h>
#include <commons/versioned_heap.h>
#include "test.h"
@@ -4,30 +6,31 @@
struct s { char xs[40000]; };
TEST(versioned_heap, basics) {
- versioned_heap<s> h;
+ typedef versioned_heap<s> heap;
+ heap h;
s &a = h.construct();
- EXPECT_EQ(h.hdrof(&a).version, 0);
+ EXPECT_EQ(0, h.hdrof(&a).version);
s &b = h.construct();
- EXPECT_EQ(h.hdrof(&b).version, 1);
+ EXPECT_EQ(1, h.hdrof(&b).version);
s &c = h.construct();
- EXPECT_EQ(h.hdrof(&c).version, 2);
+ EXPECT_EQ(2, h.hdrof(&c).version);
EXPECT_EQ(&a + 1, &b);
EXPECT_EQ(&b + 1, &c);
s &d = h.construct();
- EXPECT_EQ(h.hdrof(&d).version, 0);
+ EXPECT_EQ(0, h.hdrof(&d).version);
s &e = h.construct();
- EXPECT_EQ(h.hdrof(&e).version, 1);
+ EXPECT_EQ(1, h.hdrof(&e).version);
s &f = h.construct();
- EXPECT_EQ(h.hdrof(&f).version, 2);
+ EXPECT_EQ(2, h.hdrof(&f).version);
EXPECT_EQ(&d + 1, &e);
EXPECT_EQ(&e + 1, &f);
h.touch(d);
EXPECT_EQ(h.hdrof(&d).version, 3);
- h.free(d);
+ h.destroy(d);
EXPECT_EQ(h.hdrof(&d).version, 4);
h.touch(a, 4);
@@ -37,4 +40,22 @@
s &g = h.construct();
EXPECT_EQ(&d, &g);
+
+ void *meta = new char[h.metasize()], *data;
+ check0x(posix_memalign(&data, h.pgsz(), datasize(h)));
+ unique_ptr<char[]> umeta(reinterpret_cast<char*>(meta)),
+ udata(reinterpret_cast<char*>(data));
+ h.ser(meta, data);
+
+ heap h2;
+ h2.deser(meta, data);
+
+ EXPECT_EQ(h.pages().size(), h2.pages().size());
+ for (size_t i = 0; i < h.pages().size(); ++i) {
+ s *p = reinterpret_cast<s*>(h .pages()[i] + sizeof(heap::hdr));
+ s *q = reinterpret_cast<s*>(h2.pages()[i] + sizeof(heap::hdr));
+ for (size_t j = 0; j < h.pgcnt(); ++j) {
+ EXPECT_EQ(0, memcmp(p, q, sizeof(s)));
+ }
+ }
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
