00001 #include "util/stream/sort.hh"
00002
00003 #define BOOST_TEST_MODULE SortTest
00004 #include <boost/test/unit_test.hpp>
00005
00006 #include <algorithm>
00007
00008 #include <unistd.h>
00009
00010 namespace util { namespace stream { namespace {
00011
00012 struct CompareUInt64 : public std::binary_function<const void *, const void *, bool> {
00013 bool operator()(const void *first, const void *second) const {
00014 return *static_cast<const uint64_t*>(first) < *reinterpret_cast<const uint64_t*>(second);
00015 }
00016 };
00017
00018 const uint64_t kSize = 100000;
00019
00020 struct Putter {
00021 Putter(std::vector<uint64_t> &shuffled) : shuffled_(shuffled) {}
00022
00023 void Run(const ChainPosition &position) {
00024 Stream put_shuffled(position);
00025 for (uint64_t i = 0; i < shuffled_.size(); ++i, ++put_shuffled) {
00026 *static_cast<uint64_t*>(put_shuffled.Get()) = shuffled_[i];
00027 }
00028 put_shuffled.Poison();
00029 }
00030 std::vector<uint64_t> &shuffled_;
00031 };
00032
00033 BOOST_AUTO_TEST_CASE(FromShuffled) {
00034 std::vector<uint64_t> shuffled;
00035 shuffled.reserve(kSize);
00036 for (uint64_t i = 0; i < kSize; ++i) {
00037 shuffled.push_back(i);
00038 }
00039 std::random_shuffle(shuffled.begin(), shuffled.end());
00040
00041 ChainConfig config;
00042 config.entry_size = 8;
00043 config.total_memory = 800;
00044 config.block_count = 3;
00045
00046 SortConfig merge_config;
00047 merge_config.temp_prefix = "sort_test_temp";
00048 merge_config.buffer_size = 800;
00049 merge_config.total_memory = 3300;
00050
00051 Chain chain(config);
00052 chain >> Putter(shuffled);
00053 BlockingSort(chain, merge_config, CompareUInt64(), NeverCombine());
00054 Stream sorted;
00055 chain >> sorted >> kRecycle;
00056 for (uint64_t i = 0; i < kSize; ++i, ++sorted) {
00057 BOOST_CHECK_EQUAL(i, *static_cast<const uint64_t*>(sorted.Get()));
00058 }
00059 BOOST_CHECK(!sorted);
00060 }
00061
00062 }}}