[Assorted-commits] SF.net SVN: assorted:[1297] ydb/trunk
Brought to you by:
yangzhang
Menu
▾
▴
[Assorted-commits] SF.net SVN: assorted:[1297] ydb/trunk
|
From: <yan...@us...> - 2009-03-17 06:11:50
|
Revision: 1297
http://assorted.svn.sourceforge.net/assorted/?rev=1297&view=rev
Author: yangzhang
Date: 2009-03-17 06:11:47 +0000 (Tue, 17 Mar 2009)
Log Message:
-----------
added iterator (+tests) for btree
Modified Paths:
--------------
ydb/trunk/README
ydb/trunk/src/tpcc/Makefile
ydb/trunk/src/tpcc/btree.h
Added Paths:
-----------
ydb/trunk/src/tpcc/btree_test.cc
Modified: ydb/trunk/README
===================================================================
--- ydb/trunk/README 2009-03-17 02:39:31 UTC (rev 1296)
+++ ydb/trunk/README 2009-03-17 06:11:47 UTC (rev 1297)
@@ -736,7 +736,8 @@
|neworders| = 107973
|history| = 30000
-- TODO add iteration to btree
+- DONE add iteration to btree
+ - added btree_test for this
- TODO try integrating TPC-C; just get txns working for now
- TODO implement TPC-C recovery
Modified: ydb/trunk/src/tpcc/Makefile
===================================================================
--- ydb/trunk/src/tpcc/Makefile 2009-03-17 02:39:31 UTC (rev 1296)
+++ ydb/trunk/src/tpcc/Makefile 2009-03-17 06:11:47 UTC (rev 1297)
@@ -6,12 +6,15 @@
#CXXFLAGS = -g -O3 -DNDEBUG -MD $(WARNINGS)
# Link withthe C++ standard library
-LDFLAGS=-lstdc++
+#LDFLAGS=-lstdc++
+LDLIBS = -lgtest
-BINARIES = tpccclient.o tpccgenerator.o tpcctables.o tpccdb.o clock.o randomgenerator.o
+BINARIES = btree_test.o tpccclient.o tpccgenerator.o tpcctables.o tpccdb.o clock.o randomgenerator.o
all: $(BINARIES)
+btree_test: btree_test.o
+
clean :
rm -f *.o *.d $(BINARIES)
Modified: ydb/trunk/src/tpcc/btree.h
===================================================================
--- ydb/trunk/src/tpcc/btree.h 2009-03-17 02:39:31 UTC (rev 1296)
+++ ydb/trunk/src/tpcc/btree.h 2009-03-17 06:11:47 UTC (rev 1297)
@@ -9,14 +9,25 @@
#include <assert.h>
#include <stdlib.h>
#include <string.h>
+#include <deque>
+#include <utility>
+#include <iostream> // XXX
#include <boost/static_assert.hpp>
#include <boost/pool/object_pool.hpp>
+#include <commons/nullptr.h>
+#ifdef DEBUG
+#include <iostream>
+using namespace std; // XXX
+#endif
+
// DEBUG
-#include <iostream>
using std::cout;
using std::endl;
+using namespace commons;
+using std::deque;
+using std::pair;
#ifdef __linux__
#define HAVE_POSIX_MEMALIGN
@@ -206,6 +217,62 @@
size_t size() const { return size_; }
+ class iterator
+ {
+ public:
+ typedef typename BPlusTree::InnerNode inner_type;
+ typedef typename BPlusTree::LeafNode leaf_type;
+ iterator(BPlusTree &tree) : tree_(tree) {
+ if (tree.size_ > 0) {
+ stack_.push_back(make_pair(tree.root, 0));
+ // If depth = 0, that means we have only a root node.
+ // 1 isn't <= 0 so we don't do anything, which is good.
+ // If depth = 1, that means we have a root and children.
+ // 1 is <= 1 so we do add the first child, which is good.
+ down();
+ }
+ }
+ iterator &operator++() {
+#ifdef DEBUG
+ for (int i = 0; i < stack_.size(); ++i)
+ cout << (i > 0 ? " > " : "") << stack_[i].first << ' ' << stack_[i].second
+ << '/' << (i == tree_.depth ? as_inner(stack_[i].first).num_keys : as_leaf(stack_[i].first).num_keys);
+ cout << endl;
+#endif
+ up(); if (!stack_.empty()) down();
+#ifdef DEBUG
+ for (int i = 0; i < stack_.size(); ++i)
+ cout << (i > 0 ? " > " : "") << stack_[i].first << ' ' << stack_[i].second
+ << '/' << (i == tree_.depth ? as_inner(stack_[i].first).num_keys : as_leaf(stack_[i].first).num_keys);
+ cout << endl;
+#endif
+ return *this;
+ }
+ pair<KEY, VALUE> operator*() {
+ return make_pair(leaf().keys[pos()], leaf().values[pos()]);
+ }
+ bool end() { return stack_.empty(); }
+ private:
+ inner_type &as_inner(void *p) { return *reinterpret_cast<inner_type*>(p); }
+ leaf_type &as_leaf(void *p) { return *reinterpret_cast<leaf_type*>(p); }
+ inner_type &inner() { return as_inner(stack_.back().first); }
+ leaf_type &leaf() { return as_leaf(stack_.back().first); }
+ size_t &pos() { return stack_.back().second; }
+ void down() {
+ while (stack_.size() <= tree_.depth)
+ stack_.push_back(make_pair(inner().children[pos()], 0));
+ }
+ void up() {
+ while (!stack_.empty() &&
+ ++pos() > (stack_.size() == tree_.depth + 1 ?
+ leaf().num_keys - 1 : inner().num_keys))
+ stack_.pop_back(); // back up
+ }
+ BPlusTree &tree_;
+ // stack of (node, pos)
+ deque< pair<void*, size_t> > stack_;
+ };
+
private:
// Used when debugging
enum NodeType {NODE_INNER=0xDEADBEEF, NODE_LEAF=0xC0FFEE};
Added: ydb/trunk/src/tpcc/btree_test.cc
===================================================================
--- ydb/trunk/src/tpcc/btree_test.cc (rev 0)
+++ ydb/trunk/src/tpcc/btree_test.cc 2009-03-17 06:11:47 UTC (rev 1297)
@@ -0,0 +1,61 @@
+#include "btree.h"
+#include <gtest/gtest.h>
+using namespace std;
+using namespace testing;
+
+typedef BPlusTree<int, int, 8, 8> tree_t;
+
+TEST(btree, empty) {
+ tree_t tree;
+ tree_t::iterator it(tree);
+ ASSERT_TRUE(it.end());
+}
+
+TEST(btree, shallow) {
+ tree_t tree;
+ for (int i = 1; i < 4; ++i)
+ tree.insert(2*i, 3*i); // [(2,3),(4,6),(6,9)]
+ {
+ tree_t::iterator it(tree);
+ for (int i = 1; i < 4; ++i) {
+ EXPECT_EQ(2*i, (*it).first);
+ EXPECT_EQ(3*i, (*it).second);
+ ++it;
+ }
+ EXPECT_TRUE(it.end());
+ }
+
+ tree.del(4); // [(2,3),(4,0),(6,9)]
+
+ {
+ tree_t::iterator it(tree);
+ EXPECT_EQ(2, (*it).first);
+ EXPECT_EQ(3, (*it).second);
+ ++it;
+ EXPECT_EQ(4, (*it).first);
+ EXPECT_EQ(0, (*it).second);
+ ++it;
+ EXPECT_EQ(6, (*it).first);
+ EXPECT_EQ(9, (*it).second);
+ ++it;
+ EXPECT_TRUE(it.end());
+ }
+}
+
+TEST(btree, deep) {
+ tree_t tree;
+ for (int i = 1; i < 100; ++i)
+ tree.insert(2*i, 3*i);
+ tree_t::iterator it(tree);
+ for (int i = 1; i < 100; ++i) {
+ EXPECT_EQ(2*i, (*it).first);
+ EXPECT_EQ(3*i, (*it).second);
+ ++it;
+ }
+ EXPECT_TRUE(it.end());
+}
+
+int main(int argc, char **argv) {
+ InitGoogleTest(&argc, argv);
+ return RUN_ALL_TESTS();
+}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
