summaryrefslogtreecommitdiff
path: root/klm/util/stream/sort_test.cc
blob: fd7705cd9dd65be2df46cb2e0209cc99f285d5d9 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include "util/stream/sort.hh"

#define BOOST_TEST_MODULE SortTest
#include <boost/test/unit_test.hpp>

#include <algorithm>

#include <unistd.h>

namespace util { namespace stream { namespace {

struct CompareUInt64 : public std::binary_function<const void *, const void *, bool> {
  bool operator()(const void *first, const void *second) const {
    return *static_cast<const uint64_t*>(first) < *reinterpret_cast<const uint64_t*>(second);
  }
};

const uint64_t kSize = 100000;

struct Putter {
  Putter(std::vector<uint64_t> &shuffled) : shuffled_(shuffled) {}

  void Run(const ChainPosition &position) {
    Stream put_shuffled(position);
    for (uint64_t i = 0; i < shuffled_.size(); ++i, ++put_shuffled) {
      *static_cast<uint64_t*>(put_shuffled.Get()) = shuffled_[i];
    }
    put_shuffled.Poison();
  }
  std::vector<uint64_t> &shuffled_;
};

BOOST_AUTO_TEST_CASE(FromShuffled) {
  std::vector<uint64_t> shuffled;
  shuffled.reserve(kSize);
  for (uint64_t i = 0; i < kSize; ++i) {
    shuffled.push_back(i);
  }
  std::random_shuffle(shuffled.begin(), shuffled.end());
  
  ChainConfig config;
  config.entry_size = 8;
  config.total_memory = 800;
  config.block_count = 3;

  SortConfig merge_config;
  merge_config.temp_prefix = "sort_test_temp";
  merge_config.buffer_size = 800;
  merge_config.total_memory = 3300;

  Chain chain(config);
  chain >> Putter(shuffled);
  BlockingSort(chain, merge_config, CompareUInt64(), NeverCombine());
  Stream sorted;
  chain >> sorted >> kRecycle;
  for (uint64_t i = 0; i < kSize; ++i, ++sorted) {
    BOOST_CHECK_EQUAL(i, *static_cast<const uint64_t*>(sorted.Get()));
  }
  BOOST_CHECK(!sorted);
}

}}} // namespaces