text:
/*
 * Copyright (c) 2013 Turi Inc.
 *     All rights reserved.
 *
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing,
 *  software distributed under the License is distributed on an "AS
 *  IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
 *  express or implied.  See the License for the specific language
 *  governing permissions and limitations under the License.
 *
 * For more about this software visit:
 *
 *      http://turicreate.com
 *
 */

#define BOOST_TEST_MODULE
#include <boost/test/unit_test.hpp>
#include <util/test_macros.hpp>
#include <iostream>
#include <typeinfo>       // operator typeid
#include <cstddef>
#include <functional>
#include <iterator>
#include <type_traits>
#include <iterator>

#include <generics/is_memmovable.hpp>
#include <generics/gl_vector.hpp>
#include <generics/gl_string.hpp>
#include <util/basic_types.hpp>
#include <util/testing_utils.hpp>

using namespace turi;

BOOST_TEST_DONT_PRINT_LOG_VALUE(gl_vector<int>)
BOOST_TEST_DONT_PRINT_LOG_VALUE(gl_vector<gl_vector<int>>)
BOOST_TEST_DONT_PRINT_LOG_VALUE(gl_vector<gl_vector<gl_string>>)
BOOST_TEST_DONT_PRINT_LOG_VALUE(gl_vector<double>)
BOOST_TEST_DONT_PRINT_LOG_VALUE(gl_vector<turi::gl_string>)
BOOST_TEST_DONT_PRINT_LOG_VALUE(gl_vector<std::shared_ptr<turi::gl_string>>)
BOOST_TEST_DONT_PRINT_LOG_VALUE(gl_vector<std::shared_ptr<int>>)
BOOST_TEST_DONT_PRINT_LOG_VALUE(std::shared_ptr<turi::gl_string>)

template <typename T>
size_t alignment_round(size_t n) {
  return size_t(std::ceil(double(n * sizeof(T)) / 16.0) * 16.0) / sizeof(T);
}

int random_int() {
  return random::fast_uniform<int>(0, std::numeric_limits<int>::max());
}

template <typename T>
void verify_serialization(const gl_vector<T>& v) {

  // into gl_vector
  gl_vector<T> v1;
  save_and_load_object(v1, v);
  DASSERT_TRUE(v == v1);

  // Into std
  std::vector<T> v2;
  save_and_load_object(v2, v);
  DASSERT_EQ(v2.size(), v.size());
  DASSERT_TRUE(std::equal(v2.begin(), v2.end(), v.begin()));

  // from std into empty
  std::vector<T> v3;
  v3 = v;
  gl_vector<T> v4;
  save_and_load_object(v4, v3);
  DASSERT_TRUE(v4 == v);

  // from std into non-empty
  save_and_load_object(v1, v3);
  DASSERT_TRUE(v1 == v);
}

template <typename T>
void verify_consistency(const gl_vector<T>& v) {

  // Constructor 1
  {
    gl_vector<T> v2(v);
    DASSERT_TRUE(v == v2);
  }

  // Constructor 2
  {
    gl_vector<T> v2(v.begin(), v.end());
    DASSERT_TRUE(v == v2);
  }

  // Assignment
  {
    gl_vector<T> v2;
    v2 = v;
    DASSERT_TRUE(v == v2);
  }

  // Assignment
  {
    gl_vector<T> v2;
    v2.assign(v.begin(), v.end());
    DASSERT_TRUE(v == v2);
  }

  // Assignment by insert
  {
    gl_vector<T> v2;
    v2.insert(v2.end(), v.begin(), v.end());
    DASSERT_TRUE(v == v2);
  }

  // Assignment by insert into cleared vector
  {
    gl_vector<T> v2;
    v2.resize(1);
    v2.clear();
    v2.insert(v2.end(), v.begin(), v.end());
    DASSERT_TRUE(v == v2);
  }

  // construction by empty, then resize, then index fill
  {
    gl_vector<T> v2;
    v2.resize(v.size());
    for(size_t i = 0; i < v.size(); ++i) {
      v2[i] = v[i];
    }
    DASSERT_TRUE(v == v2);
  }

  // construction by empty, then resize, then
  {
    gl_vector<T> v2;
    v2.reserve(v.size());
    for(auto e : v) {
      v2.push_back(e);
    }
    DASSERT_TRUE(v == v2);
  }

  // construction by empty, then resize, then iteration
  {
    gl_vector<T> v2;
    v2.resize(v.size());
    auto it = v2.begin();
    for(size_t i = 0; i < v.size(); ++i, ++it) {
      *it = v[i];
    }
    DASSERT_TRUE(v == v2);
  }

  // construction by empty, then resize, then reverse iteration
  {
    gl_vector<T> v2;
    v2.resize(v.size());
    auto it = v2.rbegin();
    for(size_t i = v.size(); (i--) != 0; ++it) {
      *it = v[i];
    }
    DASSERT_TRUE(v == v2);
  }

  // Assignment by insert into cleared vector.
  {
    gl_vector<T> v2;
    v2.resize(1);
    v2.insert(v2.begin(), v.begin(), v.end());
    v2.resize(v.size());
    DASSERT_TRUE(v == v2);
  }

  // Assignment by insert into cleared vector, then erase
  {
    gl_vector<T> v2;
    v2.resize(1);
    v2.insert(v2.end(), v.begin(), v.end());
    v2.erase(v2.begin());
    DASSERT_TRUE(v == v2);
  }

  ////////////////////////////////////////////////////////////////////////////////
  // test casting.
  {
    std::vector<T> v_stl;

    v_stl = v;

    TS_ASSERT_EQUALS(v_stl.size(), v.size());
    TS_ASSERT(std::equal(v.begin(), v.end(), v_stl.begin()));

    // Assignment
    gl_vector<T> v2(20);

    v2 = v_stl;

    TS_ASSERT_EQUALS(v2, v);

    // Construction
    gl_vector<T> v3(v_stl);

    TS_ASSERT_EQUALS(v3, v);
  }
}

using namespace turi;

// Full compiler initialization
template class turi::gl_vector<int>;
template class turi::gl_vector<gl_vector<int> >;

class A
{
  int i_;
  double d_;

  A(const A&);
  A& operator=(const A&);
 public:
  A(int i, double d)
      : i_(i), d_(d) {}

  A(A&& a)
  : i_(a.i_),
    d_(a.d_)
  {
    a.i_ = 0;
    a.d_ = 0;
  }

  A& operator=(A&& a)
  {
    i_ = a.i_;
    d_ = a.d_;
    a.i_ = 0;
    a.d_ = 0;
    return *this;
  }

  int geti() const {return i_;}
  double getd() const {return d_;}
};
namespace turi {
template <>
struct is_memmovable<A> {
  static constexpr bool value = true;
};
}

////////////////////////////////////////////////////////////////////////////////

class Copyable
{
 public:
};

////////////////////////////////////////////////////////////////////////////////

class MoveOnly
{
  MoveOnly(const MoveOnly&) = delete;
  MoveOnly& operator=(const MoveOnly&) = delete;

  int data_;
 public:
  MoveOnly(int data = 1) : data_(data) {}
  MoveOnly(MoveOnly&& x)
  : data_(x.data_) {x.data_ = 0;}
  MoveOnly& operator=(MoveOnly&& x)
  {data_ = x.data_; x.data_ = 0; return *this;}

  int get() const {return data_;}

  bool operator==(const MoveOnly& x) const {return data_ == x.data_;}
  bool operator< (const MoveOnly& x) const {return data_ <  x.data_;}
};

namespace turi {
template <>
struct is_memmovable<MoveOnly> {
  static constexpr bool value = true;
};
}
////////////////////////////////////////////////////////////////////////////////

template <class C, class Iterator>
void test_iterator_fill(Iterator first, Iterator last)
{
  C c(first, last);
  TS_ASSERT(c.size() == size_t(std::distance(first, last)));
  for (typename C::const_iterator i = c.cbegin(), e = c.cend(); i != e; ++i, ++first)
    TS_ASSERT(*i == *first);
}

////////////////////////////////////////////////////////////////////////////////

namespace std {

template <>
struct hash<MoveOnly>
    : public std::unary_function<MoveOnly, std::size_t>
{
  std::size_t operator()(const MoveOnly& x) const {return x.get();}
};

}

////////////////////////////////////////////////////////////////////////////////

// we declare shared_ptr to be memmovable for this test . It is not guaranteed
// to be the case, but it certainly does appear to be the case.
namespace turi {
template <typename T>
struct is_memmovable<std::shared_ptr<T> > {
  static constexpr bool value = true;
};
}
struct gl_vector_datatype_test  {

 public:

  void test_sanity() {
    gl_vector<int> v;
    TS_ASSERT_EQUALS(v.size(), 0);
    verify_consistency(v);
    verify_serialization(v);
  }

  void test_default_size_constructor() {
    size_t n = 10;

    gl_vector<int> c(n);
    TS_ASSERT(c.size() == n);

    for (typename gl_vector<int>::const_iterator i = c.cbegin(), e = c.cend(); i != e; ++i)
      TS_ASSERT(*i == typename gl_vector<int>::value_type());

    verify_consistency(c);
    verify_serialization(c);
  }

  void test_default_size_constructor_2() {
    size_t n = 10;
    gl_vector<int> c(n, 5);
    TS_ASSERT(c.size() == n);

    for (typename gl_vector<int>::const_iterator i = c.cbegin(), e = c.cend(); i != e; ++i)
      TS_ASSERT(*i == 5);
    verify_consistency(c);
    verify_serialization(c);
  }

  void test_fill_from_iterator() {
    int a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5, 4, 3, 1, 0};
    int* an = a + sizeof(a)/sizeof(a[0]);

    test_iterator_fill<gl_vector<int> >(a, an);

    std::list<int> al(a, an);
    test_iterator_fill<gl_vector<int> >(al.begin(), al.end());
  }

  void test_back() {
    typedef int T;
    typedef gl_vector<T> C;
    C c(1, 0);
    TS_ASSERT_EQUALS(c.back(), 0);
    verify_consistency(c);
    verify_serialization(c);
  }

  void test_front() {
    typedef int T;
    typedef gl_vector<T> C;
    C c(1, 0);
    TS_ASSERT_EQUALS(c.front(), 0);
    verify_consistency(c);
    verify_serialization(c);
  }

  void test_emplace() {
    gl_vector<A> c;
    gl_vector<A>::iterator i = c.emplace(c.cbegin(), 2, 3.5);

    TS_ASSERT(i == c.begin());
    TS_ASSERT_EQUALS(c.size(), 1);
    TS_ASSERT_EQUALS(c.front().geti(), 2);
    TS_ASSERT_EQUALS(c.front().getd(), 3.5);
    i = c.emplace(c.cend(), 3, 4.5);

    TS_ASSERT(i == c.end()-1);
    TS_ASSERT_EQUALS(c.size(), 2);
    TS_ASSERT_EQUALS(c.front().geti(), 2);
    TS_ASSERT_EQUALS(c.front().getd(), 3.5);
    TS_ASSERT_EQUALS(c.back().geti(), 3);
    TS_ASSERT_EQUALS(c.back().getd(), 4.5);

    i = c.emplace(c.cbegin()+1, 4, 6.5);
    TS_ASSERT(i == c.begin()+1);
    TS_ASSERT_EQUALS(c.size(), 3);
    TS_ASSERT_EQUALS(c.front().geti(), 2);
    TS_ASSERT_EQUALS(c.front().getd(), 3.5);
    TS_ASSERT_EQUALS(c[1].geti(), 4);
    TS_ASSERT_EQUALS(c[1].getd(), 6.5);
    TS_ASSERT_EQUALS(c.back().geti(), 3);
    TS_ASSERT_EQUALS(c.back().getd(), 4.5);
  }

  void test_emplace_back() {
    gl_vector<A> c;
    c.emplace_back(2, 3.5);
    TS_ASSERT_EQUALS(c.size(), 1);
    TS_ASSERT_EQUALS(c.front().geti(), 2);
    TS_ASSERT_EQUALS(c.front().getd(), 3.5);

    c.emplace_back(3, 4.5);
    TS_ASSERT_EQUALS(c.size(), 2);
    TS_ASSERT_EQUALS(c.front().geti(), 2);
    TS_ASSERT_EQUALS(c.front().getd(), 3.5);
    TS_ASSERT_EQUALS(c.back().geti(), 3);
    TS_ASSERT_EQUALS(c.back().getd(), 4.5);
  }

  void test_erase() {
    int a1[] = {1, 2, 3};
    gl_vector<int> l1(a1, a1+3);
    gl_vector<int>::const_iterator i = l1.begin();
    ++i;
    gl_vector<int>::iterator j = l1.erase(i);
    TS_ASSERT_EQUALS(l1.size(), 2);
    TS_ASSERT_EQUALS(std::distance(l1.begin(), l1.end()), 2);
    TS_ASSERT_EQUALS(*j, 3);
    TS_ASSERT_EQUALS(*l1.begin(), 1);
    TS_ASSERT_EQUALS(*std::next(l1.begin()), 3);

    verify_consistency(l1);
    verify_serialization(l1);

    j = l1.erase(j);
    TS_ASSERT_EQUALS(j, l1.end());
    TS_ASSERT_EQUALS(l1.size(), 1);
    TS_ASSERT_EQUALS(std::distance(l1.begin(), l1.end()), 1);
    TS_ASSERT_EQUALS(*l1.begin(), 1);

    verify_consistency(l1);
    verify_serialization(l1);

    j = l1.erase(l1.begin());
    TS_ASSERT_EQUALS(j, l1.end());
    TS_ASSERT_EQUALS(l1.size(), 0);
    TS_ASSERT_EQUALS(std::distance(l1.begin(), l1.end()), 0);

    verify_consistency(l1);
    verify_serialization(l1);

  }

  void test_erase_iter_iter() {

    int a1[] = {1, 2, 3};
    {
      gl_vector<int> l1(a1, a1+3);
      gl_vector<int>::iterator i = l1.erase(l1.cbegin(), l1.cbegin());
      TS_ASSERT_EQUALS(l1.size(), 3);
      TS_ASSERT(std::distance(l1.cbegin(), l1.cend()) == 3);
      TS_ASSERT(i == l1.begin());

      verify_consistency(l1);
      verify_serialization(l1);
    }
    {
      gl_vector<int> l1(a1, a1+3);
      gl_vector<int>::iterator i = l1.erase(l1.cbegin(), std::next(l1.cbegin()));
      TS_ASSERT_EQUALS(l1.size(), 2);
      TS_ASSERT_EQUALS(std::distance(l1.cbegin(), l1.cend()), 2);
      TS_ASSERT_EQUALS(i, l1.begin());
      TS_ASSERT(l1 == gl_vector<int>(a1+1, a1+3));

      verify_consistency(l1);
      verify_serialization(l1);
    }
    {
      gl_vector<int> l1(a1, a1+3);
      gl_vector<int>::iterator i = l1.erase(l1.cbegin(), std::next(l1.cbegin(), 2));
      TS_ASSERT_EQUALS(l1.size(), 1);
      TS_ASSERT_EQUALS(std::distance(l1.cbegin(), l1.cend()), 1);
      TS_ASSERT(i == l1.begin());
      TS_ASSERT(l1 == gl_vector<int>(a1+2, a1+3));
      verify_consistency(l1);
      verify_serialization(l1);
    }
    {
      gl_vector<int> l1(a1, a1+3);
      gl_vector<int>::iterator i = l1.erase(l1.cbegin(), std::next(l1.cbegin(), 3));
      TS_ASSERT_EQUALS(l1.size(), 0);
      TS_ASSERT_EQUALS(std::distance(l1.cbegin(), l1.cend()), 0);
      TS_ASSERT(i == l1.begin());
      verify_consistency(l1);
      verify_serialization(l1);
    }
    {
      gl_vector<gl_vector<int> > outer(2, gl_vector<int>(1));
      outer.erase(outer.begin(), outer.begin());
      TS_ASSERT_EQUALS(outer.size(), 2);
      TS_ASSERT_EQUALS(outer[0].size(), 1);
      TS_ASSERT_EQUALS(outer[1].size(), 1);
      verify_consistency(outer);
      verify_serialization(outer);
    }
  }

  void test_insert_initializer_list() {
    gl_vector<int> d(10, 1);
    gl_vector<int>::iterator i = d.insert(d.cbegin() + 2, {3, 4, 5, 6});
    TS_ASSERT(d.size() == 14);
    TS_ASSERT(i == d.begin() + 2);
    TS_ASSERT_EQUALS(d[0], 1);
    TS_ASSERT_EQUALS(d[1], 1);
    TS_ASSERT_EQUALS(d[2], 3);
    TS_ASSERT_EQUALS(d[3], 4);
    TS_ASSERT_EQUALS(d[4], 5);
    TS_ASSERT_EQUALS(d[5], 6);
    TS_ASSERT_EQUALS(d[6], 1);
    TS_ASSERT_EQUALS(d[7], 1);
    TS_ASSERT_EQUALS(d[8], 1);
    TS_ASSERT_EQUALS(d[9], 1);
    TS_ASSERT_EQUALS(d[10], 1);
    TS_ASSERT_EQUALS(d[11], 1);
    TS_ASSERT_EQUALS(d[12], 1);
    TS_ASSERT_EQUALS(d[13], 1);

    verify_consistency(d);
    verify_serialization(d);
  }

  void test_move()
  {
    gl_vector<MoveOnly> v(100);
    gl_vector<MoveOnly>::iterator i = v.insert(v.cbegin() + 10, MoveOnly(3));
    TS_ASSERT_EQUALS(v.size(), 101);
    TS_ASSERT(i == v.begin() + 10);
    int j;
    for (j = 0; j < 10; ++j)
      TS_ASSERT(v[j] == MoveOnly());
    TS_ASSERT(v[j] == MoveOnly(3));
    for (++j; j < 101; ++j)
      TS_ASSERT(v[j] == MoveOnly());
  }

  void test_insert_by_value_1()
  {
    gl_vector<int> v(100);
    int j;

    for (j = 0; j < 100; ++j)
      TS_ASSERT_EQUALS(v[j], 0);

    gl_vector<int>::iterator i = v.insert(v.cbegin() + 10, 1);

    TS_ASSERT_EQUALS(v.size(), 101);
    TS_ASSERT(i == v.begin() + 10);
    for (j = 0; j < 10; ++j)
      TS_ASSERT_EQUALS(v[j], 0);
    for (; j < 11; ++j)
      TS_ASSERT_EQUALS(v[j], 1);
    for (++j; j < 101; ++j)
      TS_ASSERT_EQUALS(v[j], 0);

    verify_consistency(v);
    verify_serialization(v);
  }

  void test_insert_by_value_2()
  {
    gl_vector<int> v(100);
    gl_vector<int>::iterator i = v.insert(v.cbegin() + 10, 5, 1);
    TS_ASSERT_EQUALS(v.size(), 105);
    TS_ASSERT(i == v.begin() + 10);
    int j;
    for (j = 0; j < 10; ++j)
      TS_ASSERT_EQUALS(v[j], 0);
    for (; j < 15; ++j)
      TS_ASSERT_EQUALS(v[j], 1);
    for (++j; j < 105; ++j)
      TS_ASSERT_EQUALS(v[j], 0);

    verify_consistency(v);
    verify_serialization(v);
  }

  void test_insert_by_iter()
  {
    gl_vector<int> v(100);
    int a[] = {1, 2, 3, 4, 5};
    const int N = sizeof(a)/sizeof(a[0]);
    gl_vector<int>::iterator i = v.insert(v.cbegin() + 10, (const int*)a, (const int*)(a + N));

    TS_ASSERT_EQUALS(v.size(), 100 + N);
    TS_ASSERT(i == v.begin() + 10);
    int j;
    for (j = 0; j < 10; ++j)
      TS_ASSERT_EQUALS(v[j], 0);
    for (int k = 0; k < N; ++j, ++k)
      TS_ASSERT_EQUALS(v[j], a[k]);
    for (; j < 105; ++j)
      TS_ASSERT_EQUALS(v[j], 0);

    verify_consistency(v);
    verify_serialization(v);
  }

  void test_insert_by_iter_move()
  {
    gl_vector<MoveOnly> v(100);
    gl_vector<MoveOnly>::iterator i = v.insert(v.cbegin() + 10, MoveOnly(3));

    TS_ASSERT(v.size() == 101);
    TS_ASSERT(i == v.begin() + 10);

    int j;
    for (j = 0; j < 10; ++j)
      TS_ASSERT(v[j] == MoveOnly());

    TS_ASSERT(v[j] == MoveOnly(3));

    for (++j; j < 101; ++j)
      TS_ASSERT(v[j] == MoveOnly());
  }

  void test_iterators_1()
  {
    typedef int T;
    typedef gl_vector<T> C;
    C c(1);
    C::iterator i = c.end();
    --i;
    TS_ASSERT(i == c.begin());
    TS_ASSERT(i == c.cbegin());

    verify_serialization(c);
    verify_consistency(c);
  }

  void test_iterators_1_const()
  {
    typedef int T;
    typedef gl_vector<T> C;
    C c(1);
    auto i = c.cend();
    --i;
    TS_ASSERT(i == c.begin());
    TS_ASSERT(i == c.cbegin());

    verify_serialization(c);
    verify_consistency(c);
  }

  void test_swap_1()
  {
    gl_vector<int> v1(100);
    gl_vector<int> v2(200);

    int* ptr_1 = v1.data();
    int* ptr_2 = v2.data();

    v1.swap(v2);

    TS_ASSERT_EQUALS(v1.size(), 200);
    TS_ASSERT_EQUALS(v2.size(), 100);
    TS_ASSERT_EQUALS(v1.capacity(), 200);
    TS_ASSERT_EQUALS(v2.capacity(), 100);
    TS_ASSERT_EQUALS(v1.data(), ptr_2);
    TS_ASSERT_EQUALS(v2.data(), ptr_1);

    verify_serialization(v1);
    verify_consistency(v1);
    verify_serialization(v2);
    verify_consistency(v2);
  }

  void test_swap_2()
  {
    int a1[] = {1, 3, 7, 9, 10};
    int a2[] = {0, 2, 4, 5, 6, 8, 11};
    gl_vector<int> c1(a1, a1+sizeof(a1)/sizeof(a1[0]));
    gl_vector<int> c2(a2, a2+sizeof(a2)/sizeof(a2[0]));

    verify_serialization(c1);
    verify_consistency(c1);
    verify_serialization(c2);
    verify_consistency(c2);

    std::swap(c1, c2);

    TS_ASSERT(c1 == gl_vector<int>(a2, a2+sizeof(a2)/sizeof(a2[0])));
    TS_ASSERT(c2 == gl_vector<int>(a1, a1+sizeof(a1)/sizeof(a1[0])));

    verify_serialization(c1);
    verify_consistency(c1);
    verify_serialization(c2);
    verify_consistency(c2);
  }

  void test_shrink_to_fit_1()
  {
    gl_vector<int> v(100);
    v.push_back(1);
    v.shrink_to_fit();
    TS_ASSERT_EQUALS(v.capacity(), alignment_round<int>(101));
    TS_ASSERT_EQUALS(v.size(), 101);

    verify_serialization(v);
    verify_consistency(v);
  }

  void test_shrink_to_fit_2()
  {
    gl_vector<int> v(100);
    v.reserve(200);
    v.shrink_to_fit();
    TS_ASSERT_EQUALS(v.capacity(), alignment_round<int>(100));
    TS_ASSERT_EQUALS(v.size(), 100);

    verify_serialization(v);
    verify_consistency(v);
  }

  void test_resize_1()
  {
    gl_vector<int> v(100);
    v.resize(50, 1);
    TS_ASSERT(v.size() == 50);
    TS_ASSERT(v.capacity() == 100);
    TS_ASSERT(v == gl_vector<int>(50));
    v.resize(200, 1);
    TS_ASSERT(v.size() == 200);
    TS_ASSERT(v.capacity() >= 200);
    for (unsigned i = 0; i < 50; ++i)
      TS_ASSERT(v[i] == 0);
    for (unsigned i = 50; i < 200; ++i)
      TS_ASSERT(v[i] == 1);

    verify_serialization(v);
    verify_consistency(v);
  }

  void test_resize_2()
  {
    gl_vector<int> v(100);
    v.resize(50);
    TS_ASSERT(v.size() == 50);
    TS_ASSERT(v.capacity() == alignment_round<int>(100));

    v.resize(200);
    TS_ASSERT(v.size() == 200);
    TS_ASSERT(v.capacity() >= 200);

    verify_serialization(v);
    verify_consistency(v);
  }

  void test_resize_2_move()
  {
    gl_vector<MoveOnly> v(100);
    v.resize(50);
    TS_ASSERT(v.size() == 50);
    TS_ASSERT(v.capacity() == alignment_round<int>(100));

    v.resize(200);
    TS_ASSERT(v.size() == 200);
    TS_ASSERT(v.capacity() >= 200);
  }

  void test_reserve_1() {
    gl_vector<int> v;
    v.reserve(10);
    TS_ASSERT(v.capacity() >= 10);

    verify_serialization(v);
    verify_consistency(v);
  }

  void test_reserve_2() {
    gl_vector<int> v(100);
    TS_ASSERT_EQUALS(v.capacity(), alignment_round<int>(100));
    v.reserve(50);
    TS_ASSERT_EQUALS(v.size(), 100);
    TS_ASSERT_EQUALS(v.capacity(), alignment_round<int>(100));
    v.reserve(150);
    TS_ASSERT_EQUALS(v.size(), 100);
    TS_ASSERT_EQUALS(v.capacity(), alignment_round<int>(150));

    verify_serialization(v);
    verify_consistency(v);
  }

  void test_reserve_2_move() {
    gl_vector<MoveOnly> v(100);
    TS_ASSERT_EQUALS(v.capacity(), alignment_round<int>(100));
    v.reserve(50);
    TS_ASSERT_EQUALS(v.size(), 100);
    TS_ASSERT_EQUALS(v.capacity(), alignment_round<int>(100));
    v.reserve(150);
    TS_ASSERT_EQUALS(v.size(), 100);
    TS_ASSERT_EQUALS(v.capacity(), alignment_round<int>(150));
  }

  void test_assign_1() {
    gl_vector<int> l(3, 2);
    gl_vector<int> l2(l);
    l2 = l;

    TS_ASSERT(l2 == l);

    verify_serialization(l);
    verify_consistency(l);
    verify_serialization(l2);
    verify_consistency(l2);
  }

  void test_assign_initializers() {
    gl_vector<int> d;
    d.assign({3, 4, 5, 6});
    TS_ASSERT(d.size() == 4);
    TS_ASSERT(d[0] == 3);
    TS_ASSERT(d[1] == 4);
    TS_ASSERT(d[2] == 5);
    TS_ASSERT(d[3] == 6);

    verify_serialization(d);
    verify_consistency(d);
  }

  void test_assign_move() {
    gl_vector<MoveOnly> l;
    gl_vector<MoveOnly> lo;

    for (int i = 1; i <= 3; ++i)
    {
      l.push_back(i);
      lo.push_back(i);
    }

    gl_vector<MoveOnly> l2;
    l2 = std::move(l);

    TS_ASSERT(l2 == lo);
  }

  void test_assign_constructors() {
    gl_vector<double> f2;
    auto f = gl_vector<double>{1.1, 2.2, 3.3};

    TS_ASSERT_EQUALS(f.size(), 3);

    TS_ASSERT_DELTA(f[0], 1.1, 1E-6);
    TS_ASSERT_DELTA(f[1], 2.2, 1E-6);
    TS_ASSERT_DELTA(f[2], 3.3, 1E-6);
    f2 = f;

    TS_ASSERT_EQUALS(f.size(), 3);
    TS_ASSERT_DELTA(f[0], 1.1, 1E-6);
    TS_ASSERT_DELTA(f[1], 2.2, 1E-6);
    TS_ASSERT_DELTA(f[2], 3.3, 1E-6);

    TS_ASSERT_EQUALS(f2.size(), 3);
    TS_ASSERT_DELTA(f2[0], 1.1, 1E-6);
    TS_ASSERT_DELTA(f2[1], 2.2, 1E-6);
    TS_ASSERT_DELTA(f2[2], 3.3, 1E-6);

    verify_serialization(f);
    verify_consistency(f);
    verify_serialization(f2);
    verify_consistency(f2);
  }

  void test_pop_back_1() {
    gl_vector<int> c;
    c.push_back(1);
    TS_ASSERT(c.size() == 1);

    verify_serialization(c);
    verify_consistency(c);

    c.pop_back();
    TS_ASSERT(c.size() == 0);

    verify_serialization(c);
    verify_consistency(c);
  }

  void test_pop_back_2() {
    gl_vector<std::shared_ptr<int> > c;

    std::shared_ptr<int> i(new int);

    TS_ASSERT(i.use_count() == 1);

    c.emplace_back(i);

    TS_ASSERT(i.use_count() == 2);
    TS_ASSERT(c.size() == 1);

    verify_consistency(c);

    c.pop_back();
    TS_ASSERT(c.size() == 0);
    TS_ASSERT(i.use_count() == 1);

    verify_consistency(c);
  }

};

struct gl_vector_string_test  {

 public:

  void test_string_sanity() {
    gl_vector<gl_string> v;
    TS_ASSERT_EQUALS(v.size(), 0);
    verify_consistency(v);
    verify_serialization(v);
  }

  void test_string_default_size_constructor() {
    size_t n = 10;

    gl_vector<gl_string> c(n);
    TS_ASSERT(c.size() == n);

    for (typename gl_vector<gl_string>::const_iterator i = c.cbegin(), e = c.cend(); i != e; ++i)
      TS_ASSERT(*i == typename gl_vector<gl_string>::value_type());

    verify_consistency(c);
    verify_serialization(c);
  }

  void test_string_default_size_constructor_2() {
    size_t n = 10;
    gl_vector<gl_string> c(n, "test");
    TS_ASSERT(c.size() == n);

    for (typename gl_vector<gl_string>::const_iterator i = c.cbegin(), e = c.cend(); i != e; ++i)
      TS_ASSERT(*i == "test");

    verify_consistency(c);
    verify_serialization(c);
  }

  void test_string_fill_from_iterator() {
    const char* a[] = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "8", "7", "6", "5", "4", "3", "1", "0"};
    const char** an = a + sizeof(a)/sizeof(a[0]);

    test_iterator_fill<gl_vector<gl_string> >(a, an);

    std::list<gl_string> al(a, an);
    test_iterator_fill<gl_vector<gl_string> >(al.begin(), al.end());
  }

  void test_string_back() {
    typedef gl_string T;
    typedef gl_vector<T> C;
    C c(1, "0");
    TS_ASSERT_EQUALS(c.back(), "0");
    verify_consistency(c);
    verify_serialization(c);
  }

  void test_string_front() {
    typedef gl_string T;
    typedef gl_vector<T> C;
    C c(1, "0");
    TS_ASSERT_EQUALS(c.front(), "0");
    verify_consistency(c);
    verify_serialization(c);
  }

  void test_string_erase() {
    const char* a1[] = {"1", "2", "3"};
    gl_vector<gl_string> l1(a1, a1+3);
    gl_vector<gl_string>::const_iterator i = l1.begin();
    ++i;
    gl_vector<gl_string>::iterator j = l1.erase(i);
    TS_ASSERT_EQUALS(l1.size(), 2);
    TS_ASSERT_EQUALS(std::distance(l1.begin(), l1.end()), 2);
    TS_ASSERT_EQUALS(*j, "3");
    TS_ASSERT_EQUALS(*l1.begin(), "1");
    TS_ASSERT_EQUALS(*std::next(l1.begin()), "3");

    verify_consistency(l1);
    verify_serialization(l1);

    j = l1.erase(j);
    TS_ASSERT_EQUALS(j, l1.end());
    TS_ASSERT_EQUALS(l1.size(), 1);
    TS_ASSERT_EQUALS(std::distance(l1.begin(), l1.end()), 1);
    TS_ASSERT_EQUALS(*l1.begin(), "1");

    verify_consistency(l1);
    verify_serialization(l1);

    j = l1.erase(l1.begin());
    TS_ASSERT_EQUALS(j, l1.end());
    TS_ASSERT_EQUALS(l1.size(), 0);
    TS_ASSERT_EQUALS(std::distance(l1.begin(), l1.end()), 0);

    verify_consistency(l1);
    verify_serialization(l1);
  }

  void test_string_erase_iter_iter() {

    const char* a1[] = {"1", "2", "3"};
    {
      gl_vector<gl_string> l1(a1, a1+3);
      gl_vector<gl_string>::iterator i = l1.erase(l1.cbegin(), l1.cbegin());
      TS_ASSERT_EQUALS(l1.size(), 3);
      TS_ASSERT(std::distance(l1.cbegin(), l1.cend()) == 3);
      TS_ASSERT(i == l1.begin());

      verify_consistency(l1);
      verify_serialization(l1);
    }
    {
      gl_vector<gl_string> l1(a1, a1+3);
      gl_vector<gl_string>::iterator i = l1.erase(l1.cbegin(), std::next(l1.cbegin()));
      TS_ASSERT_EQUALS(l1.size(), 2);
      TS_ASSERT_EQUALS(std::distance(l1.cbegin(), l1.cend()), 2);
      TS_ASSERT_EQUALS(i, l1.begin());
      TS_ASSERT(l1 == gl_vector<gl_string>(a1+1, a1+3));

      verify_consistency(l1);
      verify_serialization(l1);
    }
    {
      gl_vector<gl_string> l1(a1, a1+3);
      gl_vector<gl_string>::iterator i = l1.erase(l1.cbegin(), std::next(l1.cbegin(), 2));
      TS_ASSERT_EQUALS(l1.size(), 1);
      TS_ASSERT_EQUALS(std::distance(l1.cbegin(), l1.cend()), 1);
      TS_ASSERT(i == l1.begin());
      TS_ASSERT(l1 == gl_vector<gl_string>(a1+2, a1+3));
      verify_consistency(l1);
      verify_serialization(l1);
    }
    {
      gl_vector<gl_string> l1(a1, a1+3);
      gl_vector<gl_string>::iterator i = l1.erase(l1.cbegin(), std::next(l1.cbegin(), 3));
      TS_ASSERT_EQUALS(l1.size(), 0);
      TS_ASSERT_EQUALS(std::distance(l1.cbegin(), l1.cend()), 0);
      TS_ASSERT(i == l1.begin());
      verify_consistency(l1);
      verify_serialization(l1);
    }
    {
      gl_vector<gl_vector<gl_string> > outer(2, gl_vector<gl_string>(1));
      outer.erase(outer.begin(), outer.begin());
      TS_ASSERT_EQUALS(outer.size(), 2);
      TS_ASSERT_EQUALS(outer[0].size(), 1);
      TS_ASSERT_EQUALS(outer[1].size(), 1);
      verify_consistency(outer);
      verify_serialization(outer);
    }
  }

  void test_string_insert_initializer_list() {
    gl_vector<gl_string> d(10, "1");
    gl_vector<gl_string>::iterator i = d.insert(d.cbegin() + 2, {"3", "4", "5", "6"});
    TS_ASSERT(d.size() == 14);
    TS_ASSERT(i == d.begin() + 2);
    TS_ASSERT_EQUALS(d[0], "1");
    TS_ASSERT_EQUALS(d[1], "1");
    TS_ASSERT_EQUALS(d[2], "3");
    TS_ASSERT_EQUALS(d[3], "4");
    TS_ASSERT_EQUALS(d[4], "5");
    TS_ASSERT_EQUALS(d[5], "6");
    TS_ASSERT_EQUALS(d[6], "1");
    TS_ASSERT_EQUALS(d[7], "1");
    TS_ASSERT_EQUALS(d[8], "1");
    TS_ASSERT_EQUALS(d[9], "1");
    TS_ASSERT_EQUALS(d[10], "1");
    TS_ASSERT_EQUALS(d[11], "1");
    TS_ASSERT_EQUALS(d[12], "1");
    TS_ASSERT_EQUALS(d[13], "1");

    verify_consistency(d);
    verify_serialization(d);
  }

  void test_string_insert_by_value_1()
  {
    gl_vector<gl_string> v(100);
    int j;

    for (j = 0; j < 100; ++j)
      TS_ASSERT_EQUALS(v[j], "");

    gl_vector<gl_string>::iterator i = v.insert(v.cbegin() + 10, "1");

    TS_ASSERT_EQUALS(v.size(), 101);
    TS_ASSERT(i == v.begin() + 10);
    for (j = 0; j < 10; ++j)
      TS_ASSERT_EQUALS(v[j], "");
    for (; j < 11; ++j)
      TS_ASSERT_EQUALS(v[j], "1");
    for (++j; j < 101; ++j)
      TS_ASSERT_EQUALS(v[j], "");

    verify_consistency(v);
    verify_serialization(v);
  }

  void test_string_insert_by_value_2()
  {
    gl_vector<gl_string> v(100);
    gl_vector<gl_string>::iterator i = v.insert(v.cbegin() + 10, 5, "1");
    TS_ASSERT_EQUALS(v.size(), 105);
    TS_ASSERT(i == v.begin() + 10);
    int j;
    for (j = 0; j < 10; ++j)
      TS_ASSERT_EQUALS(v[j], "");
    for (; j < 15; ++j)
      TS_ASSERT_EQUALS(v[j], "1");
    for (++j; j < 105; ++j)
      TS_ASSERT_EQUALS(v[j], "");

    verify_consistency(v);
    verify_serialization(v);
  }

  void test_string_insert_by_iter()
  {
    gl_vector<gl_string> v(100);
    const char* a[] = {"1", "2", "3", "4", "5"};
    size_t N = sizeof(a)/sizeof(a[0]);
    gl_vector<gl_string>::iterator i = v.insert(v.cbegin() + 10, (const char**)a, (const char**)(a + N));

    TS_ASSERT_EQUALS(v.size(), 100 + N);
    TS_ASSERT(i == v.begin() + 10);
    int j;
    for (j = 0; j < 10; ++j)
      TS_ASSERT_EQUALS(v[j], "");
    for (int k = 0; k < truncate_check<int64_t>(N); ++j, ++k)
      TS_ASSERT_EQUALS(v[j], a[k]);
    for (; j < 105; ++j)
      TS_ASSERT_EQUALS(v[j], "");

    verify_consistency(v);
    verify_serialization(v);
  }

  void test_string_insert_by_iter_move()
  {
    gl_vector<gl_string> v(100);
    gl_vector<gl_string>::iterator i = v.insert(v.cbegin() + 10, "3");

    TS_ASSERT(v.size() == 101);
    TS_ASSERT(i == v.begin() + 10);

    int j;
    for (j = 0; j < 10; ++j)
      TS_ASSERT(v[j] == "");

    TS_ASSERT(v[j] == "3");

    for (++j; j < 101; ++j)
      TS_ASSERT(v[j] == "");
  }

  void test_string_iterators_1()
  {
    typedef gl_string T;
    typedef gl_vector<T> C;
    C c(1);
    C::iterator i = c.end();
    --i;
    TS_ASSERT(i == c.begin());
    TS_ASSERT(i == c.cbegin());

    verify_serialization(c);
    verify_consistency(c);
  }

  void test_string_iterators_1_const()
  {
    typedef gl_string T;
    typedef gl_vector<T> C;
    C c(1);
    auto i = c.cend();
    --i;
    TS_ASSERT(i == c.begin());
    TS_ASSERT(i == c.cbegin());

    verify_serialization(c);
    verify_consistency(c);
  }

  void test_string_swap_1()
  {
    gl_vector<gl_string> v1(100);
    gl_vector<gl_string> v2(200);

    gl_string* ptr_1 = v1.data();
    gl_string* ptr_2 = v2.data();

    v1.swap(v2);

    TS_ASSERT_EQUALS(v1.size(), 200);
    TS_ASSERT_EQUALS(v2.size(), 100);
    TS_ASSERT_EQUALS(v1.capacity(), 200);
    TS_ASSERT_EQUALS(v2.capacity(), 100);
    TS_ASSERT_EQUALS(v1.data(), ptr_2);
    TS_ASSERT_EQUALS(v2.data(), ptr_1);

    verify_serialization(v1);
    verify_consistency(v1);
    verify_serialization(v2);
    verify_consistency(v2);
  }

  void test_string_swap_2()
  {
    const char* a1[] = {"1", "3", "7", "9", "10"};
    const char* a2[] = {"0", "2", "4", "5", "6", "8", "11"};
    gl_vector<gl_string> c1(a1, a1+sizeof(a1)/sizeof(a1[0]));
    gl_vector<gl_string> c2(a2, a2+sizeof(a2)/sizeof(a2[0]));

    verify_serialization(c1);
    verify_consistency(c1);
    verify_serialization(c2);
    verify_consistency(c2);

    std::swap(c1, c2);

    TS_ASSERT(c1 == gl_vector<gl_string>(a2, a2+sizeof(a2)/sizeof(a2[0])));
    TS_ASSERT(c2 == gl_vector<gl_string>(a1, a1+sizeof(a1)/sizeof(a1[0])));

    verify_serialization(c1);
    verify_consistency(c1);
    verify_serialization(c2);
    verify_consistency(c2);
  }

  void test_string_shrink_to_fit_1()
  {
    gl_vector<gl_string> v(100);
    v.push_back("1");
    v.shrink_to_fit();
    TS_ASSERT_EQUALS(v.capacity(), alignment_round<gl_string>(101));
    TS_ASSERT_EQUALS(v.size(), 101);

    verify_serialization(v);
    verify_consistency(v);
  }

  void test_string_shrink_to_fit_2()
  {
    gl_vector<gl_string> v(100);
    v.reserve(200);
    v.shrink_to_fit();
    TS_ASSERT_EQUALS(v.capacity(), 100);
    TS_ASSERT_EQUALS(v.size(), 100);

    verify_serialization(v);
    verify_consistency(v);
  }

  void test_string_resize_1()
  {
    gl_vector<gl_string> v(100);
    v.resize(50, "1");
    TS_ASSERT(v.size() == 50);
    TS_ASSERT(v.capacity() == 100);
    TS_ASSERT(v == gl_vector<gl_string>(50));
    v.resize(200, "1");
    TS_ASSERT(v.size() == 200);
    TS_ASSERT(v.capacity() >= 200);
    for (unsigned i = 0; i < 50; ++i)
      TS_ASSERT(v[i] == "");
    for (unsigned i = 50; i < 200; ++i)
      TS_ASSERT(v[i] == "1");

    verify_serialization(v);
    verify_consistency(v);
  }

  void test_string_resize_2()
  {
    gl_vector<gl_string> v(100);
    v.resize(50);
    TS_ASSERT(v.size() == 50);
    TS_ASSERT(v.capacity() == 100);

    v.resize(200);
    TS_ASSERT(v.size() == 200);
    TS_ASSERT(v.capacity() >= 200);

    verify_serialization(v);
    verify_consistency(v);
  }

  void test_string_reserve_1() {
    gl_vector<gl_string> v;
    v.reserve(10);
    TS_ASSERT(v.capacity() >= 10);

    verify_serialization(v);
    verify_consistency(v);
  }

  void test_string_reserve_2() {
    gl_vector<gl_string> v(100);
    TS_ASSERT(v.capacity() == 100);
    v.reserve(50);
    TS_ASSERT(v.size() == 100);
    TS_ASSERT(v.capacity() == 100);
    v.reserve(150);
    TS_ASSERT(v.size() == 100);
    TS_ASSERT(v.capacity() == 150);

    verify_serialization(v);
    verify_consistency(v);
  }

  void test_string_assign_1() {
    gl_vector<gl_string> l(3, "2");
    gl_vector<gl_string> l2(2);
    l2 = l;

    TS_ASSERT(l2 == l);

    verify_serialization(l);
    verify_consistency(l);
    verify_serialization(l2);
    verify_consistency(l2);
  }

  void test_string_assign_2() {
    gl_vector<gl_string> l(3, "2");
    gl_vector<gl_string> l2(2, "1");
    l2 = l;

    TS_ASSERT(l2 == l);

    verify_serialization(l);
    verify_consistency(l);
    verify_serialization(l2);
    verify_consistency(l2);
  }

  void test_string_assign_3() {
    gl_vector<gl_string> l(3, "2");
    gl_vector<gl_string> l2(l.begin(), l.begin() + 2);
    l2 = l;

    TS_ASSERT(l2 == l);

    verify_serialization(l);
    verify_consistency(l);
    verify_serialization(l2);
    verify_consistency(l2);
  }

  void test_string_assign_initializers() {
    gl_vector<gl_string> d;
    d.assign({"3", "4", "5", "6"});
    TS_ASSERT(d.size() == 4);
    TS_ASSERT(d[0] == "3");
    TS_ASSERT(d[1] == "4");
    TS_ASSERT(d[2] == "5");
    TS_ASSERT(d[3] == "6");

    verify_serialization(d);
    verify_consistency(d);
  }

  void test_string_assign_move() {
    gl_vector<gl_string> l;
    gl_vector<gl_string> lo;

    for (int i = 1; i <= 3; ++i)
    {
      l.push_back(gl_string(std::to_string(i)));
      lo.push_back(gl_string(std::to_string(i)));
    }

    gl_vector<gl_string> l2;
    l2 = std::move(l);

    TS_ASSERT(l2 == lo);
  }

  void test_string_pop_back_1() {
    gl_vector<gl_string> c;
    c.push_back("1");
    TS_ASSERT(c.size() == 1);

    verify_serialization(c);
    verify_consistency(c);

    c.pop_back();
    TS_ASSERT(c.size() == 0);

    verify_serialization(c);
    verify_consistency(c);
  }

  void test_string_pop_back_2() {
    gl_vector<std::shared_ptr<gl_string> > c;

    std::shared_ptr<gl_string> i(new gl_string("blob"));

    TS_ASSERT(i.use_count() == 1);

    c.emplace_back(i);

    TS_ASSERT(i.use_count() == 2);
    TS_ASSERT(c.size() == 1);

    verify_consistency(c);

    c.pop_back();
    TS_ASSERT(c.size() == 0);
    TS_ASSERT(i.use_count() == 1);

    verify_consistency(c);
  }

  void test_string_string_serialization_1() {
    gl_vector<gl_string> v = {"hello"};

    verify_serialization(v);
    verify_consistency(v);
  }

  void test_string_string_serialization_2() {
    gl_vector<gl_string> v(1000);

    for(size_t i = 0; i < v.size(); ++i) {
      v[i] = gl_string(std::to_string(random_int()));
    }

    verify_serialization(v);
    verify_consistency(v);
  }
};

////////////////////////////////////////////////////////////////////////////////
// Stuff for the typing

template <class T> void _test_types()
{
  typedef gl_vector<T> C;

    static_assert((std::is_same<typename C::value_type, T>::value), "");

    static_assert((std::is_same<
        typename std::iterator_traits<typename C::iterator>::iterator_category,
        std::random_access_iterator_tag>::value), "");

    static_assert((std::is_same<
        typename std::iterator_traits<typename C::const_iterator>::iterator_category,
        std::random_access_iterator_tag>::value), "");

    static_assert((std::is_same<
        typename C::reverse_iterator,
        std::reverse_iterator<typename C::iterator> >::value), "");

    static_assert((std::is_same<
        typename C::const_reverse_iterator,
        std::reverse_iterator<typename C::const_iterator> >::value), "");
}

////////////////////////////////////////////////////////////////////////////////

struct gl_vector_types_test   {
 public:
  void test_int() {
    _test_types<int>();
  }

  void test_int_ptr() {
    _test_types<int*>();
  }

  void test_copyable() {
    _test_types<Copyable>();
  }

  void test_nested() {
    _test_types<gl_vector<int> >();
  }

};

template <typename T, typename GenFunction>
void stress_test(size_t n_tests, GenFunction&& gen_element) {

  gl_vector<T> v;
  std::vector<T> v_ref;

  std::vector<std::function<void()> > operations;

  // Push back
  operations.push_back([&]() {
      auto e = gen_element();
      v.push_back(e);
      v_ref.push_back(e);
    });

  // Emplace back
  operations.push_back([&]() {
      auto e = gen_element();
      v.emplace_back(e);
      v_ref.emplace_back(e);
    });

  // Insert, 1 element.
  operations.push_back([&]() {
      auto e = gen_element();
      v.insert(v.begin(), e);
      v_ref.insert(v_ref.begin(), e);
    });

  operations.push_back([&]() {
      auto e = gen_element();
      size_t idx = random::fast_uniform<size_t>(0, v.size());
      v.insert(v.begin() + idx, e);
      v_ref.insert(v_ref.begin() + idx, e);
    });

  operations.push_back([&]() {
      auto e = gen_element();
      v.insert(v.end(), e);
      v_ref.insert(v_ref.end(), e);
    });

  // Insert, multiple elements.
  operations.push_back([&]() {
      auto e = gen_element();
      v.insert(v.begin(), 3, e);
      v_ref.insert(v_ref.begin(), 3, e);
    });

  operations.push_back([&]() {
      auto e = gen_element();
      size_t idx = random::fast_uniform<size_t>(0, v.size());
      v.insert(v.begin() + idx, 3, e);
      v_ref.insert(v_ref.begin() + idx, 3, e);
    });

  operations.push_back([&]() {
      auto e = gen_element();
      v.insert(v.end(), 3, e);
      v_ref.insert(v_ref.end(), 3, e);
    });

  // Insert, move element
  operations.push_back([&]() {
      auto e = gen_element();
      auto e2 = e;
      v.insert(v.begin(), std::move(e));
      v_ref.insert(v_ref.begin(), std::move(e2));
    });

  operations.push_back([&]() {
      auto e = gen_element();
      auto e2 = e;
      size_t idx = random::fast_uniform<size_t>(0, v.size());
      v.insert(v.begin() + idx, std::move(e));
      v_ref.insert(v_ref.begin() + idx, std::move(e2));
    });

  operations.push_back([&]() {
      auto e = gen_element();
      auto e2 = e;
      v.insert(v.end(), std::move(e));
      v_ref.insert(v_ref.end(), std::move(e2));
    });

  // Insert, 3 elements.
  operations.push_back([&]() {
      std::vector<T> ev = {gen_element(), gen_element(), gen_element()};
      v.insert(v.begin(), ev.begin(), ev.end());
      v_ref.insert(v_ref.begin(), ev.begin(), ev.end());
    });

  operations.push_back([&]() {
      std::vector<T> ev = {gen_element(), gen_element(), gen_element()};
      size_t idx = random::fast_uniform<size_t>(0, v.size());
      v.insert(v.begin() + idx, ev.begin(), ev.end());
      v_ref.insert(v_ref.begin() + idx, ev.begin(), ev.end());
    });

  operations.push_back([&]() {
      std::vector<T> ev = {gen_element(), gen_element(), gen_element()};
      v.insert(v.end(), ev.begin(), ev.end());
      v_ref.insert(v_ref.end(), ev.begin(), ev.end());
    });

  // Erase, single element.
  operations.push_back([&]() {
      if(v.empty()) return;
      size_t idx = random::fast_uniform<size_t>(0, v.size() - 1);
      v.erase(v.begin() + idx);
      v_ref.erase(v_ref.begin() + idx);
    });

  // Erase, block
  operations.push_back([&]() {
      if(v.empty()) return;
      size_t idx_1 = random::fast_uniform<size_t>(0, v.size() - 1);
      size_t idx_2 = random::fast_uniform<size_t>(0, v.size() - 1);
      v.erase(v.begin() + std::min(idx_1, idx_2), v.begin() + std::max(idx_1, idx_2));
      v_ref.erase(v_ref.begin() + std::min(idx_1, idx_2), v_ref.begin() + std::max(idx_1, idx_2));
    });

  // Erase, to end
  operations.push_back([&]() {
      if(v.empty()) return;
      size_t idx = random::fast_uniform<size_t>(0, v.size() - 1);
      v.erase(v.begin() + idx, v.end());
      v_ref.erase(v_ref.begin() + idx, v_ref.end());
    });

  // Erase, from beginning
  operations.push_back([&]() {
      if(v.empty()) return;
      size_t idx = random::fast_uniform<size_t>(0, v.size() - 1);
      v.erase(v.begin(), v.begin() + idx);
      v_ref.erase(v_ref.begin(), v_ref.begin() + idx);
    });

  // Clear everything.
  operations.push_back([&]() {
      v.clear();
      v_ref.clear();
    });

  // Total clear.
  operations.push_back([&]() {
      gl_vector<T> v_empty;
      std::vector<T> vr_empty;
      v.swap(v_empty);
      v_ref.swap(vr_empty);
    });

  // Assignment to init list
  operations.push_back([&]() {
      std::vector<T> ev = {gen_element(), gen_element(), gen_element()};
      v = {ev[0], ev[1], ev[2]};
      v_ref = {ev[0], ev[1], ev[2]};
    });

  // Assignment by iterator
  operations.push_back([&]() {
      std::vector<T> ev = {gen_element(), gen_element(), gen_element()};
      v.assign(ev.begin(), ev.end());
      v_ref.assign(ev.begin(), ev.end());
    });

  // Assignment by move equality
  operations.push_back([&]() {
      std::vector<T> ev = {gen_element(), gen_element(), gen_element()};
      v = std::move(gl_vector<T>(ev.begin(), ev.end()));
      v_ref = std::move(std::vector<T>(ev.begin(), ev.end()));
    });

  // pop_back
  operations.push_back([&]() {
      if(v.empty()) return;
      v.pop_back();
      v_ref.pop_back();
    });

  // swap front and back
  operations.push_back([&]() {
      if(v.empty()) return;
      std::swap(v.back(), v.front());
      std::swap(v_ref.back(), v_ref.front());
    });

  // shuffle by index
  operations.push_back([&]() {
      for(size_t j = 0; j < v.size(); ++j) {
        size_t idx = random::fast_uniform<size_t>(0, v.size() - 1);
        std::swap(v[j], v[idx]);
        std::swap(v_ref[j], v_ref[idx]);
      }
    });

  // shuffle by iterator
  operations.push_back([&]() {
      for(size_t j = 0; j < v.size(); ++j) {
        size_t idx = random::fast_uniform<size_t>(0, v.size() - 1);
        std::swap(*(v.begin() + j), *(v.begin() + idx));
        std::swap(*(v_ref.begin() + j), *(v_ref.begin() + idx));
      }
    });

  // shuffle by reverse iterator
  operations.push_back([&]() {
      for(size_t j = 0; j < v.size(); ++j) {
        size_t idx = random::fast_uniform<size_t>(0, v.size() - 1);
        std::swap(*(v.rbegin() + j), *(v.rbegin() + idx));
        std::swap(*(v_ref.rbegin() + j), *(v_ref.rbegin() + idx));
      }
    });

  // swap and insert.
  operations.push_back([&]() {
      std::vector<T> ev = {gen_element(), gen_element(), gen_element()};
      gl_vector<T> v2 = {ev[0], ev[1], ev[2]};
      std::vector<T> v2_ref = {ev[0], ev[1], ev[2]};
      v.swap(v2);
      v_ref.swap(v2_ref);

      size_t idx = random::fast_uniform<size_t>(0, v.size());
      v.insert(v.begin() + idx, v2.begin(), v2.end());
      v_ref.insert(v_ref.begin() + idx, v2_ref.begin(), v2_ref.end());
    });

  // setting through an std::vector.
  operations.push_back([&]() {

      std::vector<T> v2 = v;
      v.assign(v2.begin(), v2.end());

      gl_vector<T> v2_ref(v_ref.begin(), v_ref.end());
      v_ref.assign(v2_ref.begin(), v2_ref.end());
    });

  // string deserialization
  operations.push_back([&]() {
      gl_string s = gl_string(serialize_to_string(v));
      v.clear();
      deserialize_from_string(s, v);
    });

  // string deserialization via vector
  operations.push_back([&]() {
      std::vector<T> v2 = v;
      gl_string s = gl_string(serialize_to_string(v2));
      deserialize_from_string(s, v);
    });

  // setting through an std::vector.
  operations.push_back([&]() {

      std::vector<T> v2 = v;
      v.assign(v2.begin(), v2.end());

      gl_vector<T> v2_ref(v_ref.begin(), v_ref.end());
      v_ref.assign(v2_ref.begin(), v2_ref.end());
    });

  for(size_t i = 0; i < n_tests; ++i) {
    size_t idx = random::fast_uniform<size_t>(0, operations.size() - 1);
    operations[idx]();

    ASSERT_EQ(v.size(), v_ref.size());

    for(size_t j = 0; j < v.size(); ++j) {
      ASSERT_TRUE(v[j] == v_ref[j]);
    }

    if((i + 1) % 1000 == 0) {
      verify_serialization(v);
      verify_consistency(v);
    }
  }
}

struct gl_vector_stress_test   {

 public:

  void test_int() {
    random::seed(0);
    stress_test<int>(100000, []() { return random_int(); });
  }

  void test_char() {
    random::seed(0);
    stress_test<int>(100000, []() { return random_int(); });
  }

  void test_string() {
    random::seed(1);
    stress_test<gl_string>(100000, []() { return gl_string(std::to_string(random_int())); });
  }

  void test_vector() {
    random::seed(2);
    stress_test<gl_vector<int> >(100000, []() {
        size_t len = random::fast_uniform<size_t>(0, 10);
        gl_vector<int> v;
        v.reserve(len);
        for(size_t i = 0; i < len; ++i) {
          v.push_back(random_int());
        }

        return v;
      });
  }

  void test_gl_vector() {
    random::seed(3);
    stress_test<gl_vector<int> >(100000, []() {
        size_t len = random::fast_uniform<size_t>(0, 10);
        gl_vector<int> v;
        v.reserve(len);
        for(size_t i = 0; i < len; ++i) {
          v.push_back(random_int());
        }

        return v;
      });
  }

};

BOOST_FIXTURE_TEST_SUITE(_gl_vector_datatype_test, gl_vector_datatype_test)
BOOST_AUTO_TEST_CASE(test_sanity) {
  gl_vector_datatype_test::test_sanity();
}
BOOST_AUTO_TEST_CASE(test_default_size_constructor) {
  gl_vector_datatype_test::test_default_size_constructor();
}
BOOST_AUTO_TEST_CASE(test_default_size_constructor_2) {
  gl_vector_datatype_test::test_default_size_constructor_2();
}
BOOST_AUTO_TEST_CASE(test_fill_from_iterator) {
  gl_vector_datatype_test::test_fill_from_iterator();
}
BOOST_AUTO_TEST_CASE(test_back) {
  gl_vector_datatype_test::test_back();
}
BOOST_AUTO_TEST_CASE(test_front) {
  gl_vector_datatype_test::test_front();
}
BOOST_AUTO_TEST_CASE(test_emplace) {
  gl_vector_datatype_test::test_emplace();
}
BOOST_AUTO_TEST_CASE(test_emplace_back) {
  gl_vector_datatype_test::test_emplace_back();
}
BOOST_AUTO_TEST_CASE(test_erase) {
  gl_vector_datatype_test::test_erase();
}
BOOST_AUTO_TEST_CASE(test_erase_iter_iter) {
  gl_vector_datatype_test::test_erase_iter_iter();
}
BOOST_AUTO_TEST_CASE(test_insert_initializer_list) {
  gl_vector_datatype_test::test_insert_initializer_list();
}
BOOST_AUTO_TEST_CASE(test_move) {
  gl_vector_datatype_test::test_move();
}
BOOST_AUTO_TEST_CASE(test_insert_by_value_1) {
  gl_vector_datatype_test::test_insert_by_value_1();
}
BOOST_AUTO_TEST_CASE(test_insert_by_value_2) {
  gl_vector_datatype_test::test_insert_by_value_2();
}
BOOST_AUTO_TEST_CASE(test_insert_by_iter) {
  gl_vector_datatype_test::test_insert_by_iter();
}
BOOST_AUTO_TEST_CASE(test_insert_by_iter_move) {
  gl_vector_datatype_test::test_insert_by_iter_move();
}
BOOST_AUTO_TEST_CASE(test_iterators_1) {
  gl_vector_datatype_test::test_iterators_1();
}
BOOST_AUTO_TEST_CASE(test_iterators_1_const) {
  gl_vector_datatype_test::test_iterators_1_const();
}
BOOST_AUTO_TEST_CASE(test_swap_1) {
  gl_vector_datatype_test::test_swap_1();
}
BOOST_AUTO_TEST_CASE(test_swap_2) {
  gl_vector_datatype_test::test_swap_2();
}
BOOST_AUTO_TEST_CASE(test_shrink_to_fit_1) {
  gl_vector_datatype_test::test_shrink_to_fit_1();
}
BOOST_AUTO_TEST_CASE(test_shrink_to_fit_2) {
  gl_vector_datatype_test::test_shrink_to_fit_2();
}
BOOST_AUTO_TEST_CASE(test_resize_1) {
  gl_vector_datatype_test::test_resize_1();
}
BOOST_AUTO_TEST_CASE(test_resize_2) {
  gl_vector_datatype_test::test_resize_2();
}
BOOST_AUTO_TEST_CASE(test_resize_2_move) {
  gl_vector_datatype_test::test_resize_2_move();
}
BOOST_AUTO_TEST_CASE(test_reserve_1) {
  gl_vector_datatype_test::test_reserve_1();
}
BOOST_AUTO_TEST_CASE(test_reserve_2) {
  gl_vector_datatype_test::test_reserve_2();
}
BOOST_AUTO_TEST_CASE(test_reserve_2_move) {
  gl_vector_datatype_test::test_reserve_2_move();
}
BOOST_AUTO_TEST_CASE(test_assign_1) {
  gl_vector_datatype_test::test_assign_1();
}
BOOST_AUTO_TEST_CASE(test_assign_initializers) {
  gl_vector_datatype_test::test_assign_initializers();
}
BOOST_AUTO_TEST_CASE(test_assign_move) {
  gl_vector_datatype_test::test_assign_move();
}
BOOST_AUTO_TEST_CASE(test_assign_constructors) {
  gl_vector_datatype_test::test_assign_constructors();
}
BOOST_AUTO_TEST_CASE(test_pop_back_1) {
  gl_vector_datatype_test::test_pop_back_1();
}
BOOST_AUTO_TEST_CASE(test_pop_back_2) {
  gl_vector_datatype_test::test_pop_back_2();
}
BOOST_AUTO_TEST_SUITE_END()
BOOST_FIXTURE_TEST_SUITE(_gl_vector_string_test, gl_vector_string_test)
BOOST_AUTO_TEST_CASE(test_string_sanity) {
  gl_vector_string_test::test_string_sanity();
}
BOOST_AUTO_TEST_CASE(test_string_default_size_constructor) {
  gl_vector_string_test::test_string_default_size_constructor();
}
BOOST_AUTO_TEST_CASE(test_string_default_size_constructor_2) {
  gl_vector_string_test::test_string_default_size_constructor_2();
}
BOOST_AUTO_TEST_CASE(test_string_fill_from_iterator) {
  gl_vector_string_test::test_string_fill_from_iterator();
}
BOOST_AUTO_TEST_CASE(test_string_back) {
  gl_vector_string_test::test_string_back();
}
BOOST_AUTO_TEST_CASE(test_string_front) {
  gl_vector_string_test::test_string_front();
}
BOOST_AUTO_TEST_CASE(test_string_erase) {
  gl_vector_string_test::test_string_erase();
}
BOOST_AUTO_TEST_CASE(test_string_erase_iter_iter) {
  gl_vector_string_test::test_string_erase_iter_iter();
}
BOOST_AUTO_TEST_CASE(test_string_insert_initializer_list) {
  gl_vector_string_test::test_string_insert_initializer_list();
}
BOOST_AUTO_TEST_CASE(test_string_insert_by_value_1) {
  gl_vector_string_test::test_string_insert_by_value_1();
}
BOOST_AUTO_TEST_CASE(test_string_insert_by_value_2) {
  gl_vector_string_test::test_string_insert_by_value_2();
}
BOOST_AUTO_TEST_CASE(test_string_insert_by_iter) {
  gl_vector_string_test::test_string_insert_by_iter();
}
BOOST_AUTO_TEST_CASE(test_string_insert_by_iter_move) {
  gl_vector_string_test::test_string_insert_by_iter_move();
}
BOOST_AUTO_TEST_CASE(test_string_iterators_1) {
  gl_vector_string_test::test_string_iterators_1();
}
BOOST_AUTO_TEST_CASE(test_string_iterators_1_const) {
  gl_vector_string_test::test_string_iterators_1_const();
}
BOOST_AUTO_TEST_CASE(test_string_swap_1) {
  gl_vector_string_test::test_string_swap_1();
}
BOOST_AUTO_TEST_CASE(test_string_swap_2) {
  gl_vector_string_test::test_string_swap_2();
}
BOOST_AUTO_TEST_CASE(test_string_shrink_to_fit_1) {
  gl_vector_string_test::test_string_shrink_to_fit_1();
}
BOOST_AUTO_TEST_CASE(test_string_shrink_to_fit_2) {
  gl_vector_string_test::test_string_shrink_to_fit_2();
}
BOOST_AUTO_TEST_CASE(test_string_resize_1) {
  gl_vector_string_test::test_string_resize_1();
}
BOOST_AUTO_TEST_CASE(test_string_resize_2) {
  gl_vector_string_test::test_string_resize_2();
}
BOOST_AUTO_TEST_CASE(test_string_reserve_1) {
  gl_vector_string_test::test_string_reserve_1();
}
BOOST_AUTO_TEST_CASE(test_string_reserve_2) {
  gl_vector_string_test::test_string_reserve_2();
}
BOOST_AUTO_TEST_CASE(test_string_assign_1) {
  gl_vector_string_test::test_string_assign_1();
}
BOOST_AUTO_TEST_CASE(test_string_assign_2) {
  gl_vector_string_test::test_string_assign_2();
}
BOOST_AUTO_TEST_CASE(test_string_assign_3) {
  gl_vector_string_test::test_string_assign_3();
}
BOOST_AUTO_TEST_CASE(test_string_assign_initializers) {
  gl_vector_string_test::test_string_assign_initializers();
}
BOOST_AUTO_TEST_CASE(test_string_assign_move) {
  gl_vector_string_test::test_string_assign_move();
}
BOOST_AUTO_TEST_CASE(test_string_pop_back_1) {
  gl_vector_string_test::test_string_pop_back_1();
}
BOOST_AUTO_TEST_CASE(test_string_pop_back_2) {
  gl_vector_string_test::test_string_pop_back_2();
}
BOOST_AUTO_TEST_CASE(test_string_string_serialization_1) {
  gl_vector_string_test::test_string_string_serialization_1();
}
BOOST_AUTO_TEST_CASE(test_string_string_serialization_2) {
  gl_vector_string_test::test_string_string_serialization_2();
}
BOOST_AUTO_TEST_SUITE_END()
BOOST_FIXTURE_TEST_SUITE(_gl_vector_types_test, gl_vector_types_test)
BOOST_AUTO_TEST_CASE(test_int) {
  gl_vector_types_test::test_int();
}
BOOST_AUTO_TEST_CASE(test_int_ptr) {
  gl_vector_types_test::test_int_ptr();
}
BOOST_AUTO_TEST_CASE(test_copyable) {
  gl_vector_types_test::test_copyable();
}
BOOST_AUTO_TEST_CASE(test_nested) {
  gl_vector_types_test::test_nested();
}
BOOST_AUTO_TEST_SUITE_END()
BOOST_FIXTURE_TEST_SUITE(_gl_vector_stress_test, gl_vector_stress_test)
BOOST_AUTO_TEST_CASE(test_int) {
  gl_vector_stress_test::test_int();
}
BOOST_AUTO_TEST_CASE(test_char) {
  gl_vector_stress_test::test_char();
}
BOOST_AUTO_TEST_CASE(test_string) {
  gl_vector_stress_test::test_string();
}
BOOST_AUTO_TEST_CASE(test_vector) {
  gl_vector_stress_test::test_vector();
}
BOOST_AUTO_TEST_CASE(test_gl_vector) {
  gl_vector_stress_test::test_gl_vector();
}
BOOST_AUTO_TEST_SUITE_END()

ext: cxx


text:
// This comes from the following Boost example:
// https://www.boost.org/doc/libs/1_72_0/doc/html/chrono/users_guide.html#chrono.users_guide.examples
#include <boost/chrono.hpp>
#include <iostream>
#include <cmath>

#if defined(BOOST_NAMESPACE)
namespace boost = BOOST_NAMESPACE;
#endif

int main()
{
    boost::chrono::system_clock::time_point start = boost::chrono::system_clock::now();

    for ( long i = 0; i < 10000000; ++i )
    std::sqrt( 123.456L ); // burn some time

    boost::chrono::duration<double> sec = boost::chrono::system_clock::now() - start;
    std::cout << "took " << sec.count() << " seconds\n";
    return 0;
}

ext: cpp

max_stars_repo_name: rockandsalt/conan-center-index

max_issues_repo_name: rockandsalt/conan-center-index

max_forks_repo_name: rockandsalt/conan-center-index


text:
#include <tiny_power2.h>

#define BOOST_AUTO_TEST_MAIN
#include <boost/test/auto_unit_test.hpp>
#include <boost/test/unit_test_suite.hpp>
#include <boost/test/floating_point_comparison.hpp>
#include <boost/test/test_tools.hpp>

BOOST_AUTO_TEST_SUITE(tiny_power2);

BOOST_AUTO_TEST_CASE(functional_test)
{
  BOOST_CHECK(  tiny::is_power2( 9 ) == false );
  BOOST_CHECK(  tiny::is_power2( 8 ) == true );

  BOOST_CHECK(  tiny::upper_power2( 8 ) == 8 );
  BOOST_CHECK(  tiny::lower_power2( 8 ) == 8 );

  BOOST_CHECK(  tiny::upper_power2( 9 ) == 16 );
  BOOST_CHECK(  tiny::lower_power2( 9 ) == 8 );
}

BOOST_AUTO_TEST_SUITE_END();

max_stars_repo_name: diku-dk/PROX

max_issues_repo_name: erleben/matchstick

max_forks_repo_name: erleben/matchstick


text:
/*******
edit_distance: STL and Boost compatible edit distance functions for C++

Copyright (c) 2013 Erik Erlandson

Author:  Erik Erlandson <erikerlandson@yahoo.com>

Distributed under the Boost Software License, Version 1.0.
See accompanying file LICENSE or copy at
http://www.boost.org/LICENSE_1_0.txt
*******/

#if !defined(BOOST_ALGORITHM_SEQUENCE_DETAIL_EDIT_DISTANCE_TYPES_HPP)
#define BOOST_ALGORITHM_SEQUENCE_DETAIL_EDIT_DISTANCE_TYPES_HPP

#include <cstddef>
#include <iterator>

#include <boost/tuple/tuple.hpp>
#include <boost/tuple/tuple_io.hpp>

#include <boost/exception/exception.hpp>

#include <boost/type_traits.hpp>
#include <boost/type_traits/is_arithmetic.hpp>

#include <boost/utility/enable_if.hpp>
#include <boost/typeof/std/utility.hpp>

#include <boost/function_types/result_type.hpp>
#include <boost/function_types/function_arity.hpp>
#include <boost/function_types/parameter_types.hpp>

#include <boost/tti/has_type.hpp>
#include <boost/tti/has_member_function.hpp>

#include <boost/range/metafunctions.hpp>
#include <boost/range/as_literal.hpp>

#include <boost/mpl/at.hpp>
#include <boost/mpl/assert.hpp>
#include <boost/mpl/vector.hpp>
#include <boost/mpl/logical.hpp>
#include <boost/mpl/equal_to.hpp>

#include <boost/concept/assert.hpp>
#include <boost/concept/usage.hpp>

#include <boost/unordered_set.hpp>
#include <boost/functional/hash.hpp>

#include <boost/parameter/name.hpp>
#include <boost/parameter/preprocessor.hpp>

namespace boost {
namespace algorithm {
namespace sequence {

struct unit_cost {
    typedef size_t cost_type;

    template <typename value_type> inline
    cost_type insertion(value_type const&) const {
        return cost_type(1);
    }

    template <typename value_type> inline
    cost_type deletion(value_type const&) const {
        return cost_type(1);
    }

    template <typename value_type_1, typename value_type_2> inline
    cost_type substitution(value_type_1 const&, value_type_2 const&) const {
        return cost_type(1);
    }
};

struct max_edit_cost_exception : public boost::exception {};

namespace parameter {
    BOOST_PARAMETER_NAME(sequence1)
    BOOST_PARAMETER_NAME(sequence2)
    BOOST_PARAMETER_NAME(cost)
    BOOST_PARAMETER_NAME(equal)
    BOOST_PARAMETER_NAME(script)
    BOOST_PARAMETER_NAME(substitution)
    BOOST_PARAMETER_NAME(max_cost)
    BOOST_PARAMETER_NAME(max_cost_exception)
}

namespace detail {

using boost::is_same;
using boost::is_member_function_pointer;
using boost::integral_constant;
using boost::false_type;
using boost::true_type;
using boost::function_types::result_type;
using boost::function_types::parameter_types;
using boost::function_types::function_arity;
using boost::mpl::at_c;
using boost::mpl::and_;
using boost::mpl::not_;
using boost::mpl::equal_to;
using boost::enable_if;

template <typename X> struct invoke : public true_type {};

struct none {};

template <typename T> inline T& nonconst_default() {
    static T r;
    return r;
}

template <typename Range1, typename Range2, typename Tag> struct range_category : public
    and_<is_same<typename std::iterator_traits<typename boost::range_iterator<Range1>::type>::iterator_category, Tag>,
         is_same<typename std::iterator_traits<typename boost::range_iterator<Range2>::type>::iterator_category, Tag> > {};

template <typename MaxCost, typename CostT, typename Node, typename Enable = void> struct max_cost_checker {};

template <typename MaxCost, typename CostT, typename Node>
struct max_cost_checker<MaxCost, CostT, Node, typename enable_if<is_same<MaxCost, none> >::type> {
    typedef typename Node::pos1_type pos1_type;
    typedef typename Node::pos2_type pos2_type;
    max_cost_checker(const MaxCost&, const pos1_type&, const pos2_type&) {}
    inline bool operator()(const CostT&) const { return false; }
    inline void update(const Node*) const {}
    inline void get(Node*&) const {}
};

template <typename MaxCost, typename CostT, typename Node>
struct max_cost_checker<MaxCost, CostT, Node, typename enable_if<is_arithmetic<MaxCost> >::type> {
    typedef typename Node::pos1_type pos1_type;
    typedef typename Node::pos2_type pos2_type;
    typedef typename pos1_type::difference_type diff_type;

    CostT max_cost;
    pos1_type beg1;
    pos2_type beg2;
    diff_type mcmin;
    diff_type mctec;
    Node* mcnode;

    max_cost_checker(const MaxCost& max_cost_, const pos1_type& pos1_, const pos2_type& pos2_) : max_cost(CostT(std::abs(max_cost_))), beg1(pos1_), beg2(pos2_), mcmin(-1), mctec(-1), mcnode(NULL) {}
    inline bool operator()(const CostT& c) const { return c > max_cost; }
    inline void update(Node* node) {
        // primary criteria:  position that consumes most sequence elements
        diff_type ttec = (node->pos1 - beg1) + (node->pos2 - beg2);
        if (ttec < mctec) return;

        // secondary criteria: favor positions closest to diagonal
        diff_type tmin = std::min(node->pos1 - beg1, node->pos2 - beg2);
        if (ttec > mctec  ||  tmin > mcmin) {
            mcnode = node;
            mctec = ttec;
            mcmin = tmin;
        }
    }
    inline void get(Node*& node) const {
        node = mcnode;
    }
};

struct remainder {
    enum kind { none, forward, reverse, bidirectional };
};

template <typename MaxCost, typename CostT, typename Pos, typename Enable = void> struct max_cost_checker_myers {};

template <typename MaxCost, typename CostT, typename Pos>
struct max_cost_checker_myers<MaxCost, CostT, Pos, typename enable_if<is_same<MaxCost, none> >::type> {
    max_cost_checker_myers(const MaxCost&) {}
    inline bool operator()(const CostT&) const { return false; }
    inline void update(const Pos&, const Pos&, const CostT&) const {}
    inline void get(Pos&, Pos&, CostT&) const {}
    template <typename Itr>
    inline void update(const Pos&, const Itr&, const Itr&, const Pos&, const Pos&, const Pos&, const Pos&) const {}
    inline void get(Pos&, remainder::kind&) const {}
};

template <typename MaxCost, typename CostT, typename Pos>
struct max_cost_checker_myers<MaxCost, CostT, Pos, typename enable_if<is_arithmetic<MaxCost> >::type> {
    CostT max_cost;
    Pos mcmin;
    Pos mctec;
    Pos mck;
    remainder::kind kind;

    max_cost_checker_myers(const MaxCost& max_cost_) : max_cost(CostT(std::abs(max_cost_))), mcmin(-1), mctec(-1), mck(0), kind(remainder::none) {}
    inline bool operator()(const CostT& c) const { return c > max_cost; }
    template <typename Itr>
    inline void update(const Pos& k, const Itr& Vf, const Itr& Vr, const Pos& delta, const Pos& L1, const Pos& L2, const Pos& D) {
        Pos j1f = Vf[k];
        Pos j2f = Vf[k]-k;
        Pos cf = j1f+j2f;

        // test bi-directional path
        if ((k-delta) >= -D  &&  (k-delta) <= D) {
            Pos j1r = Vr[k];
            Pos j2r = Vr[k]-k;
            Pos cr = (L1-j1r)+(L2-j2r);

            Pos ttec = cf+cr;
            if (ttec < mctec) return;

            Pos tmin = std::min(j1f, j2f);
            if (ttec > mctec  ||  tmin > mcmin) {
                mctec = ttec;
                mcmin = tmin;
                mck = k;
                kind = remainder::bidirectional;
            }

            // if a bidirectional path is available, that will be the best possible for this (k),
            // so we do not have to test forward/reverse individually:
            return;
        }

        // test forward path
        if (cf >= mctec) {
            Pos tmin = std::min(j1f, j2f);
            if (cf > mctec || tmin > mcmin) {
                mctec = cf;
                mcmin = tmin;
                mck = k;
                kind = remainder::forward;
            }
        }

        // test reverse path
        Pos j1r = Vr[k+delta];
        Pos j2r = Vr[k+delta]-(k+delta);
        Pos cr = (L1-j1r)+(L2-j2r);
        if (cr >= mctec) {
            Pos tmin = std::min((L1-j1r), (L2-j2r));
            if (cr > mctec  ||  tmin > mcmin) {
                mctec = cr;
                mcmin = tmin;
                mck = k+delta;
                kind = remainder::reverse;
            }
        }
    }

    inline void get(Pos& k_, remainder::kind& kind_) const {
        k_ = mck;
        kind_ = kind;
    }
};

struct default_equal {
    template <typename T1, typename T2>
    inline bool operator()(const T1& a, const T2& b) const { return a == b; }
};

template <typename AllowSub, typename Cost, typename CostT, typename Output, typename Enable=void>
struct sub_checker {
    // informative compile error here
};

template <typename AllowSub, typename Cost, typename CostT, typename Output>
struct sub_checker<AllowSub, Cost, CostT, Output, typename enable_if<is_same<AllowSub, bool> >::type> {
    bool allow;
    sub_checker(const bool& allow_) : allow(allow_) {}
    inline bool operator()() const { return allow; }
    template <typename V1, typename V2> inline CostT substitution(const Cost& cost, const V1& v1, const V2& v2) const { return cost.substitution(v1, v2); }
    template <typename V1, typename V2> inline void substitution(Output& out, const V1& v1, const V2& v2, const CostT& csub) const { out.substitution(v1, v2, csub); }
};

template <typename AllowSub, typename Cost, typename CostT, typename Output>
struct sub_checker<AllowSub, Cost, CostT, Output, typename enable_if<is_same<AllowSub, true_type> >::type> {
    sub_checker(const AllowSub&) {}
    inline bool operator()() const { return true; }
    template <typename V1, typename V2> inline CostT substitution(const Cost& cost, const V1& v1, const V2& v2) const { return cost.substitution(v1, v2); }
    template <typename V1, typename V2> inline void substitution(Output& out, const V1& v1, const V2& v2, const CostT& csub) const { out.substitution(v1, v2, csub); }
};

template <typename AllowSub, typename Cost, typename CostT, typename Output>
struct sub_checker<AllowSub, Cost, CostT, Output, typename enable_if<is_same<AllowSub, false_type> >::type> {
    sub_checker(const AllowSub&) {}
    inline bool operator()() const { return false; }
    template <typename V1, typename V2> inline CostT substitution(const Cost&, const V1&, const V2&) const { return 0; }
    template <typename V1, typename V2> inline void substitution(Output&, const V1&, const V2&, const CostT&) const {}
};

template <typename Itr, typename Enabled=void>
struct position {
    typedef Itr itr_type;
    typedef typename std::iterator_traits<Itr>::difference_type idx_type;
    typedef typename std::iterator_traits<Itr>::difference_type difference_type;
    typedef typename std::iterator_traits<Itr>::value_type value_type;
    typedef typename std::iterator_traits<Itr>::reference reference;

    itr_type j;
    idx_type idx;

    inline void beg(const itr_type& src) { j = src;  idx = 0; }

    inline reference operator*() { return *j; }
    inline bool operator==(const itr_type& rhs) const { return j == rhs; }
    inline bool operator!=(const itr_type& rhs) const { return j != rhs; }
    inline bool operator<(const position& rhs) const { return idx < rhs.idx; }
    inline position& operator++() { ++j; ++idx; return *this; }
    inline difference_type operator-(const position& rhs) const { return idx - rhs.idx; }
};

template <typename Itr>
struct position<Itr, typename enable_if<is_same<typename std::iterator_traits<Itr>::iterator_category, std::random_access_iterator_tag> >::type> {
    typedef Itr itr_type;
    typedef typename std::iterator_traits<Itr>::difference_type idx_type;
    typedef typename std::iterator_traits<Itr>::difference_type difference_type;
    typedef typename std::iterator_traits<Itr>::value_type value_type;
    typedef typename std::iterator_traits<Itr>::reference reference;

    itr_type j;

    inline void beg(const itr_type& src) { j = src; }

    inline reference operator*() { return *j; }
    inline bool operator==(const itr_type& rhs) const { return j == rhs; }
    inline bool operator!=(const itr_type& rhs) const { return j != rhs; }
    inline bool operator<(const position& rhs) const { return j < rhs.j; }
    inline position& operator++() { ++j; return *this; }
    inline difference_type operator-(const position& rhs) const { return j - rhs.j; }
};

template <typename Itr1, typename Itr2, typename Cost>
struct path_head {
    typedef position<Itr1> pos1_type;
    typedef position<Itr2> pos2_type;

    pos1_type pos1;
    pos2_type pos2;
    Cost cost;
};

template <typename Itr1, typename Itr2, typename Cost>
struct path_node : public path_head<Itr1, Itr2, Cost> {
    struct path_node* edge;
};

template <typename Pool, typename Visited, typename Pos1, typename Pos2, typename Cost>
inline
path_head<typename Pos1::itr_type, typename Pos2::itr_type, Cost>*
construct(Pool& pool, Visited& visited, const Pos1& pos1_, const Pos2& pos2_, const Cost& cost_) {
    typedef path_head<typename Pos1::itr_type, typename Pos2::itr_type, Cost> head_t;
    head_t w;
    w.pos1 = pos1_;
    w.pos2 = pos2_;
    typename Visited::iterator f(visited.find(&w));
    if (visited.end() != f   &&   cost_ >= (*f)->cost) return static_cast<head_t*>(NULL);
    head_t* r = pool.construct();
    r->pos1 = pos1_;
    r->pos2 = pos2_;
    r->cost = cost_;
    if (visited.end() != f) visited.erase(f);
    visited.insert(r);
    return r;
}

template <typename Pool, typename Visited, typename Pos1, typename Pos2, typename Cost>
inline
path_node<typename Pos1::itr_type, typename Pos2::itr_type, Cost>*
construct(Pool& pool, Visited& visited, const Pos1& pos1_, const Pos2& pos2_, const Cost& cost_, path_node<typename Pos1::itr_type, typename Pos2::itr_type, Cost>* const& edge_) {
    typedef path_node<typename Pos1::itr_type, typename Pos2::itr_type, Cost> head_t;
    head_t w;
    w.pos1 = pos1_;
    w.pos2 = pos2_;
    typename Visited::iterator f(visited.find(&w));
    if (visited.end() != f   &&   cost_ >= (*f)->cost) return static_cast<head_t*>(NULL);
    head_t* r = pool.construct();
    r->pos1 = pos1_;
    r->pos2 = pos2_;
    r->cost = cost_;
    r->edge = edge_;
    if (visited.end() != f) visited.erase(f);
    visited.insert(r);
    return r;
}

template <typename Pos1, typename Pos2>
struct heap_lessthan {
    Pos1 beg1;
    Pos2 beg2;
    heap_lessthan(const Pos1& pos1_, const Pos2& pos2_) : beg1(pos1_), beg2(pos2_) {}
    template <typename T> inline bool operator()(T const* a, T const* b) const {
        return a->cost > b->cost;
    }
};

template <typename Pos1, typename Pos2>
struct visited_hash {
    Pos1 beg1;
    Pos2 beg2;
    visited_hash(const Pos1& pos1_, const Pos2& pos2_) : beg1(pos1_), beg2(pos2_) {}
    template<typename T> inline
    size_t operator()(T const* e) const {
        size_t h = 0;
        boost::hash_combine(h, e->pos1-beg1);
        boost::hash_combine(h, e->pos2-beg2);
        return h;
    }
};

struct visited_equal {
    template<typename T> inline
    bool operator()(T const* a, T const* b) const {
        return (a->pos1.j == b->pos1.j) && (a->pos2.j == b->pos2.j);
    }
};

template <typename X>
struct ForwardRangeConvertible {
    BOOST_CONCEPT_USAGE(ForwardRangeConvertible) {
        // all I really want to capture here is that any sequence argument to edit_distance()
        // and friends can be treated as a ForwardRange -- currently I'm doing this by
        // applying as_literal() to all incoming arguments, which seems to allow me to send in
        // null-terminated strings, ranges, sequence containers, etc, which is what I want.
        boost::as_literal(x);
    }
    X x;
};

// I'm a little surprised this doesn't exist already
template <typename X>
struct Arithmetic {
    BOOST_CONCEPT_USAGE(Arithmetic) {
        BOOST_STATIC_ASSERT(boost::is_arithmetic<X>::value);
    }
    X x;
};

BOOST_TTI_HAS_TYPE(cost_type)

template <typename X, typename V, typename Enable=void>
struct cost_type {
    static X x;
    static V v;
    // by default, we infer cost_type from the return value of cost functions
    typedef BOOST_TYPEOF(x.insertion(v)) type;
};

template <typename X, typename V>
struct cost_type<X, V, typename enable_if<has_type_cost_type<X> >::type> {
    // if the class explicitly defines a cost_type, then that is what we use
    typedef typename X::cost_type type;
};

template <typename X, typename Sequence, typename Enabled=void> struct TestCostSub {};

template <typename X, typename Sequence>
struct TestCostSub<X, Sequence, typename enable_if<invoke<BOOST_TYPEOF_TPL(&X::substitution)> >::type> {
    typedef typename boost::range_value<Sequence>::type value_type;
    typedef typename cost_type<X, value_type>::type cost_type;
    BOOST_CONCEPT_USAGE(TestCostSub) {
        c = x.substitution(v,v);
    }

    X x;
    cost_type c;
    value_type v;
};

template <typename X, typename Sequence> struct SequenceAlignmentCost {
    BOOST_CONCEPT_ASSERT((ForwardRangeConvertible<Sequence>));

    typedef typename boost::range_value<Sequence>::type value_type;
    typedef typename cost_type<X, value_type>::type cost_type;
    BOOST_CONCEPT_ASSERT((Arithmetic<cost_type>));

    BOOST_CONCEPT_USAGE(SequenceAlignmentCost) {
        c = x.insertion(v);
        c = x.deletion(v);
    }

    // test x.substitution() method, if it is defined
    BOOST_CONCEPT_ASSERT((TestCostSub<X, Sequence>));

    X x;
    cost_type c;
    value_type v;
};

}}}}

#endif

ext: hpp


text:
/*

Copyright (c) 2006-2012, Arvid Norberg
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:

    * Redistributions of source code must retain the above copyright
      notice, this list of conditions and the following disclaimer.
    * Redistributions in binary form must reproduce the above copyright
      notice, this list of conditions and the following disclaimer in
      the documentation and/or other materials provided with the distribution.
    * Neither the name of the author nor the names of its
      contributors may be used to endorse or promote products derived
      from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
POSSIBILITY OF SUCH DAMAGE.

*/

#include "libtorrent/pch.hpp"

#ifdef TORRENT_DHT_VERBOSE_LOGGING
#include <fstream>
#endif

#include <set>
#include <numeric>
#include <boost/bind.hpp>
#include <boost/ref.hpp>

#include "libtorrent/kademlia/node.hpp"
#include "libtorrent/kademlia/node_id.hpp"
#include "libtorrent/kademlia/traversal_algorithm.hpp"
#include "libtorrent/kademlia/dht_tracker.hpp"
#include "libtorrent/kademlia/msg.hpp"

#include "libtorrent/aux_/session_impl.hpp"
#include "libtorrent/socket.hpp"
#include "libtorrent/socket_io.hpp"
#include "libtorrent/bencode.hpp"
#include "libtorrent/io.hpp"
#include "libtorrent/version.hpp"
#include "libtorrent/escape_string.hpp"

#include "../../../src/util.h"

using boost::ref;
using libtorrent::dht::node_impl;
using libtorrent::dht::node_id;
using libtorrent::dht::packet_t;
using libtorrent::dht::msg;
using namespace libtorrent::detail;

enum
{
	key_refresh = 5 // generate a new write token key every 5 minutes
};

namespace
{
	const int tick_period = 1; // minutes

	template <class EndpointType>
	void read_endpoint_list(libtorrent::entry const* n, std::vector<EndpointType>& epl)
	{
		using namespace libtorrent;
		if (n->type() != entry::list_t) return;
		entry::list_type const& contacts = n->list();
		for (entry::list_type::const_iterator i = contacts.begin()
			, end(contacts.end()); i != end; ++i)
		{
			if (i->type() != entry::string_t) return;
			std::string const& p = i->string();
			if (p.size() < 6) continue;
			std::string::const_iterator in = p.begin();
			if (p.size() == 6)
				epl.push_back(read_v4_endpoint<EndpointType>(in));
#if TORRENT_USE_IPV6
			else if (p.size() == 18)
				epl.push_back(read_v6_endpoint<EndpointType>(in));
#endif
		}
	}

}

namespace libtorrent { namespace dht
{

	void incoming_error(entry& e, char const* msg);

#ifdef TORRENT_DHT_VERBOSE_LOGGING
	int g_az_message_input = 0;
	int g_ut_message_input = 0;
	int g_lt_message_input = 0;
	int g_mp_message_input = 0;
	int g_gr_message_input = 0;
	int g_mo_message_input = 0;
	int g_unknown_message_input = 0;

	int g_announces = 0;
	int g_failed_announces = 0;
#endif

	void intrusive_ptr_add_ref(dht_tracker const* c)
	{
		TORRENT_ASSERT(c != 0);
		TORRENT_ASSERT(c->m_refs >= 0);
		++c->m_refs;
	}

	void intrusive_ptr_release(dht_tracker const* c)
	{
		TORRENT_ASSERT(c != 0);
		TORRENT_ASSERT(c->m_refs > 0);
		if (--c->m_refs == 0)
			delete c;
	}

#ifdef TORRENT_DHT_VERBOSE_LOGGING
	std::string parse_dht_client(lazy_entry const& e)
	{
		lazy_entry const* ver = e.dict_find_string("v");
		if (!ver) return "generic";
		std::string const& client = ver->string_value();
		if (client.size() < 2)
		{
			++g_unknown_message_input;
			return client;
		}
		else if (std::equal(client.begin(), client.begin() + 2, "Az"))
		{
			++g_az_message_input;
			return "Azureus";
		}
		else if (std::equal(client.begin(), client.begin() + 2, "UT"))
		{
			++g_ut_message_input;
			return "uTorrent";
		}
		else if (std::equal(client.begin(), client.begin() + 2, "LT"))
		{
			++g_lt_message_input;
			return "libtorrent";
		}
		else if (std::equal(client.begin(), client.begin() + 2, "MP"))
		{
			++g_mp_message_input;
			return "MooPolice";
		}
		else if (std::equal(client.begin(), client.begin() + 2, "GR"))
		{
			++g_gr_message_input;
			return "GetRight";
		}
		else if (std::equal(client.begin(), client.begin() + 2, "MO"))
		{
			++g_mo_message_input;
			return "Mono Torrent";
		}
		else
		{
			++g_unknown_message_input;
			return client;
		}
	}
#endif

#ifdef TORRENT_DHT_VERBOSE_LOGGING
	TORRENT_DEFINE_LOG(dht_tracker)
#endif

	node_id extract_node_id(lazy_entry const* e)
	{
		if (e == 0 || e->type() != lazy_entry::dict_t) return (node_id::min)();
		lazy_entry const* nid = e->dict_find_string("node-id");
		if (nid == 0 || nid->string_length() != 20) return (node_id::min)();
		return node_id(node_id(nid->string_ptr()));
	}

	node_id extract_node_id(entry const* e)
	{
		if (e == 0 || e->type() != entry::dictionary_t) return (node_id::min)();
		entry const* nid = e->find_key("node-id");
		if (nid == 0 || nid->type() != entry::string_t || nid->string().length() != 20)
			return (node_id::min)();
		return node_id(node_id(nid->string().c_str()));
	}

	// class that puts the networking and the kademlia node in a single
	// unit and connecting them together.
	dht_tracker::dht_tracker(libtorrent::aux::session_impl& ses, rate_limited_udp_socket& sock
		, dht_settings const& settings, entry const* state)
		: m_dht(&ses, this, settings, extract_node_id(state)
			, ses.external_address().external_address(address_v4()), &ses)
		, m_sock(sock)
		, m_last_new_key(time_now() - minutes(key_refresh))
		, m_timer(sock.get_io_service())
		, m_connection_timer(sock.get_io_service())
		, m_refresh_timer(sock.get_io_service())
		, m_settings(settings)
		, m_refresh_bucket(160)
		, m_abort(false)
		, m_host_resolver(sock.get_io_service())
		, m_sent_bytes(0)
		, m_received_bytes(0)
		, m_refs(0)
	{
#ifdef TORRENT_DHT_VERBOSE_LOGGING
		m_counter = 0;
		std::fill_n(m_replies_bytes_sent, 5, 0);
		std::fill_n(m_queries_bytes_received, 5, 0);
		std::fill_n(m_replies_sent, 5, 0);
		std::fill_n(m_queries_received, 5, 0);
		g_announces = 0;
		g_failed_announces = 0;
		m_total_message_input = 0;
		m_total_in_bytes = 0;
		m_total_out_bytes = 0;
		m_queries_out_bytes = 0;

		// turns on and off individual components' logging

		rpc_log().enable(false);
		node_log().enable(false);
//		traversal_log().enable(false);
//		dht_tracker_log.enable(false);

		TORRENT_LOG(dht_tracker) << "starting DHT tracker with node id: " << m_dht.nid();
#endif
		if (state && state->type() == entry::dictionary_t) {
			m_dht.load_storage(state->find_key("storage_table"));
		}
	}

	dht_tracker::~dht_tracker() {}

	// defined in node.cpp
	extern void nop();

	void dht_tracker::start(entry const& bootstrap)
	{
		std::vector<udp::endpoint> initial_nodes;

		if (bootstrap.type() == entry::dictionary_t)
		{
			TORRENT_TRY {
				if (entry const* nodes = bootstrap.find_key("nodes"))
					read_endpoint_list<udp::endpoint>(nodes, initial_nodes);
			} TORRENT_CATCH(std::exception&) {}
		}

		error_code ec;
		m_timer.expires_from_now(seconds(1), ec);
		m_timer.async_wait(boost::bind(&dht_tracker::tick, self(), _1));

		m_connection_timer.expires_from_now(seconds(1), ec);
		m_connection_timer.async_wait(
			boost::bind(&dht_tracker::connection_timeout, self(), _1));

		m_refresh_timer.expires_from_now(seconds(5), ec);
		m_refresh_timer.async_wait(boost::bind(&dht_tracker::refresh_timeout, self(), _1));
		m_dht.bootstrap(initial_nodes, boost::bind(&libtorrent::dht::nop));
	}

	void dht_tracker::stop()
	{
		m_abort = true;
		error_code ec;
		m_timer.cancel(ec);
		m_connection_timer.cancel(ec);
		m_refresh_timer.cancel(ec);
		m_host_resolver.cancel();
	}

    bool dht_tracker::refresh_storage()
    {
        return m_dht.refresh_storage();
    }

	void dht_tracker::dht_status(session_status& s)
	{
		m_dht.status(s);
	}

	void dht_tracker::network_stats(int& sent, int& received)
	{
		sent = m_sent_bytes;
		received = m_received_bytes;
		m_sent_bytes = 0;
		m_received_bytes = 0;
	}

	void dht_tracker::connection_timeout(error_code const& e)
	{
		if (e || m_abort) return;

		time_duration d = m_dht.connection_timeout();
		error_code ec;
		m_connection_timer.expires_from_now(d, ec);
		m_connection_timer.async_wait(boost::bind(&dht_tracker::connection_timeout, self(), _1));
	}

	void dht_tracker::refresh_timeout(error_code const& e)
	{
		if (e || m_abort) return;

		m_dht.tick();
		error_code ec;
		m_refresh_timer.expires_from_now(seconds(5), ec);
		m_refresh_timer.async_wait(
			boost::bind(&dht_tracker::refresh_timeout, self(), _1));
	}

	void dht_tracker::tick(error_code const& e)
	{
		if (e || m_abort) return;

		error_code ec;
		m_timer.expires_from_now(minutes(tick_period), ec);
		m_timer.async_wait(boost::bind(&dht_tracker::tick, self(), _1));

		ptime now = time_now();
		if (now - m_last_new_key > minutes(key_refresh))
		{
			m_last_new_key = now;
			m_dht.new_write_key();
#ifdef TORRENT_DHT_VERBOSE_LOGGING
			TORRENT_LOG(dht_tracker) << " *** new write key";
#endif
		}

#ifdef TORRENT_DHT_VERBOSE_LOGGING
		static bool first = true;

		std::ofstream st("dht_routing_table_state.txt", std::ios_base::trunc);
		m_dht.print_state(st);

		// count torrents
		int torrents = m_dht.num_torrents();

		// count peers
		int peers = m_dht.num_peers();

		std::ofstream pc("dht_stats.log", first ? std::ios_base::trunc : std::ios_base::app);
		if (first)
		{
			first = false;
			pc << "\n\n *****   starting log at " << time_now_string() << "   *****\n\n"
				<< "minute:active nodes:passive nodes"
				":ping replies sent:ping queries recvd"
				":ping replies bytes sent:ping queries bytes recvd"
				":find_node replies sent:find_node queries recv"
				":find_node replies bytes sent:find_node queries bytes recv"
				":get_peers replies sent:get_peers queries recvd"
				":get_peers replies bytes sent:get_peers queries bytes recv"
				":announce_peer replies sent:announce_peer queries recvd"
				":announce_peer replies bytes sent:announce_peer queries bytes recv"
				":error replies sent:error queries recvd"
				":error replies bytes sent:error queries bytes recv"
				":num torrents:num peers:announces per min"
				":failed announces per min:total msgs per min"
				":az msgs per min:ut msgs per min:lt msgs per min:mp msgs per min"
				":gr msgs per min:mo msgs per min:bytes in per sec:bytes out per sec"
				":queries out bytes per sec\n\n";
		}

		int active;
		int passive;
		boost::tie(active, passive) = m_dht.size();
		pc << (m_counter * tick_period)
			<< "\t" << active
			<< "\t" << passive;
		for (int i = 0; i < 5; ++i)
			pc << "\t" << (m_replies_sent[i] / float(tick_period))
				<< "\t" << (m_queries_received[i] / float(tick_period))
				<< "\t" << (m_replies_bytes_sent[i] / float(tick_period*60))
				<< "\t" << (m_queries_bytes_received[i] / float(tick_period*60));

		pc << "\t" << torrents
			<< "\t" << peers
			<< "\t" << g_announces / float(tick_period)
			<< "\t" << g_failed_announces / float(tick_period)
			<< "\t" << (m_total_message_input / float(tick_period))
			<< "\t" << (g_az_message_input / float(tick_period))
			<< "\t" << (g_ut_message_input / float(tick_period))
			<< "\t" << (g_lt_message_input / float(tick_period))
			<< "\t" << (g_mp_message_input / float(tick_period))
			<< "\t" << (g_gr_message_input / float(tick_period))
			<< "\t" << (g_mo_message_input / float(tick_period))
			<< "\t" << (m_total_in_bytes / float(tick_period*60))
			<< "\t" << (m_total_out_bytes / float(tick_period*60))
			<< "\t" << (m_queries_out_bytes / float(tick_period*60))
			<< std::endl;
		++m_counter;
		std::fill_n(m_replies_bytes_sent, 5, 0);
		std::fill_n(m_queries_bytes_received, 5, 0);
		std::fill_n(m_replies_sent, 5, 0);
		std::fill_n(m_queries_received, 5, 0);
		g_announces = 0;
		g_failed_announces = 0;
		m_total_message_input = 0;
		g_az_message_input = 0;
		g_ut_message_input = 0;
		g_lt_message_input = 0;
		g_mp_message_input = 0;
		g_gr_message_input = 0;
		g_mo_message_input = 0;
		g_unknown_message_input = 0;
		m_total_in_bytes = 0;
		m_total_out_bytes = 0;
		m_queries_out_bytes = 0;
#endif
	}

	void dht_tracker::announce(std::string const& trackerName, sha1_hash const& ih
		, address addr, int listen_port, bool seed, bool myself, int list_peers
		, boost::function<void(std::vector<tcp::endpoint> const&)> f)
	{
		m_dht.announce(trackerName, ih, addr, listen_port, seed, myself, list_peers, f);
	}

	void dht_tracker::putData(std::string const &username, std::string const &resource, bool multi,
		     entry const &value, std::string const &sig_user,
             boost::int64_t timeutc, int seq)
	{
		m_dht.putData(username,resource, multi, value, sig_user, timeutc, seq);
	}

	void dht_tracker::getData(std::string const &username, std::string const &resource, bool multi,
				  boost::function<void(entry::list_type const&)> fdata,
				  boost::function<void(bool, bool)> fdone)
	{
		m_dht.getData(username, resource, multi, fdata, fdone);
	}

	// translate bittorrent kademlia message into the generice kademlia message
	// used by the library
	bool dht_tracker::incoming_packet(error_code const& ec
		, udp::endpoint const& ep, char const* buf, int size)
	{
		if (ec)
		{
			if (ec == asio::error::connection_refused
				|| ec == asio::error::connection_reset
				|| ec == asio::error::connection_aborted
#ifdef WIN32
				|| ec == error_code(ERROR_HOST_UNREACHABLE, get_system_category())
				|| ec == error_code(ERROR_PORT_UNREACHABLE, get_system_category())
				|| ec == error_code(ERROR_CONNECTION_REFUSED, get_system_category())
				|| ec == error_code(ERROR_CONNECTION_ABORTED, get_system_category())
#endif
				)
			{
				m_dht.unreachable(ep);
			}
			return false;
		}

		if (size <= 20 || *buf != 'd' || buf[size-1] != 'e') return false;

		// account for IP and UDP overhead
		m_received_bytes += size + (ep.address().is_v6() ? 48 : 28);

		node_ban_entry* match = 0;
		node_ban_entry* min = m_ban_nodes;
		ptime now = time_now();
		for (node_ban_entry* i = m_ban_nodes; i < m_ban_nodes + num_ban_nodes; ++i)
		{
			if (i->src == ep.address())
			{
				match = i;
				break;
			}
			if (i->count < min->count) min = i;
		}

		if (match)
		{
			++match->count;
			if (match->count >= 1000)
			{
				if (now < match->limit)
				{
#ifdef TORRENT_DHT_VERBOSE_LOGGING
					if (match->count == 20)
					{
						TORRENT_LOG(dht_tracker) << " BANNING PEER [ ip: "
							<< ep << " time: " << total_milliseconds((now - match->limit) + seconds(5)) / 1000.f
							<< " count: " << match->count << " ]";
					}
#endif
                    if (match->count == 1000)
                    {
                        printf(" BANNING PEER [ ip: %s:%d ] time: %.3f ]\n",
                               ep.address().to_string().c_str(), ep.port(),
                               total_milliseconds((now - match->limit) + seconds(5)) / 1000.f);
                    }

					// we've received 20 messages in less than 5 seconds from
					// this node. Ignore it until it's silent for 5 minutes
					match->limit = now + minutes(5);
					return true;
				}

				// we got 50 messages from this peer, but it was in
				// more than 5 seconds. Reset the counter and the timer
				match->count = 0;
				match->limit = now + seconds(5);
			}
		}
		else
		{
			min->count = 1;
			min->limit = now + seconds(5);
			min->src = ep.address();
		}

#ifdef TORRENT_DHT_VERBOSE_LOGGING
		++m_total_message_input;
		m_total_in_bytes += size;
#endif

		using libtorrent::entry;
		using libtorrent::bdecode;

		TORRENT_ASSERT(size > 0);

		lazy_entry e;
		int pos;
		error_code err;
		int ret = lazy_bdecode(buf, buf + size, e, err, &pos, 10, 500);
		if (ret != 0)
		{
#ifdef TORRENT_DHT_VERBOSE_LOGGING
			TORRENT_LOG(dht_tracker) << "<== " << ep << " ERROR: "
				<< err.message() << " pos: " << pos;
#endif
			return false;
		}

		libtorrent::dht::msg m(e, ep);

		if (e.type() != lazy_entry::dict_t)
		{
#ifdef TORRENT_DHT_VERBOSE_LOGGING
			TORRENT_LOG(dht_tracker) << "<== " << ep << " ERROR: not a dictionary: "
				<< print_entry(e, true);
#endif
			// it's not a good idea to send invalid messages
			// especially not in response to an invalid message
//			entry r;
//			libtorrent::dht::incoming_error(r, "message is not a dictionary");
//			send_packet(r, ep, 0);
			return false;
		}

#ifdef TORRENT_DHT_VERBOSE_LOGGING
		parse_dht_client(e);
		TORRENT_LOG(dht_tracker) << "<== " << ep << " " << print_entry(e, true);
#endif

		m_dht.incoming(m);
		return true;
	}

	void add_node_fun(void* userdata, node_entry const& e)
	{
		entry* n = (entry*)userdata;
		std::string node;
		std::back_insert_iterator<std::string> out(node);
		write_endpoint(e.ep(), out);
		n->list().push_back(entry(node));
	}

	entry dht_tracker::state() const
	{
		entry ret(entry::dictionary_t);
		{
			entry nodes(entry::list_t);
			m_dht.m_table.for_each_node(&add_node_fun, &add_node_fun, &nodes);
			bucket_t cache;
			m_dht.replacement_cache(cache);
			for (bucket_t::iterator i(cache.begin())
				, end(cache.end()); i != end; ++i)
			{
				std::string node;
				std::back_insert_iterator<std::string> out(node);
				write_endpoint(i->ep(), out);
				nodes.list().push_back(entry(node));
			}
			if (!nodes.list().empty())
				ret["nodes"] = nodes;

			// [MF] save stored keys
			entry storate_entry(entry::dictionary_t);
			if( m_dht.save_storage(storate_entry) ) {
				ret["storage_table"] = storate_entry;
			}
		}

		ret["node-id"] = m_dht.nid().to_string();
		return ret;
	}

	void dht_tracker::add_node(udp::endpoint node)
	{
		m_dht.add_node(node);
	}

	void dht_tracker::add_node(std::pair<std::string, int> const& node)
	{
		char port[7];
		snprintf(port, sizeof(port), "%d", node.second);
		udp::resolver::query q(node.first, port);
		m_host_resolver.async_resolve(q,
			boost::bind(&dht_tracker::on_name_lookup, self(), _1, _2));
	}

	void dht_tracker::on_name_lookup(error_code const& e
		, udp::resolver::iterator host)
	{
		if (e || host == udp::resolver::iterator()) return;
		add_node(host->endpoint());
	}

	void dht_tracker::add_router_node(udp::endpoint const& node)
	{
		m_dht.add_router_node(node);
	}

	bool dht_tracker::send_packet(libtorrent::entry& e, udp::endpoint const& addr, int send_flags)
	{
		using libtorrent::bencode;
		using libtorrent::entry;

		static char const version_str[] = {'L', 'T'
			, LIBTORRENT_VERSION_MAJOR, LIBTORRENT_VERSION_MINOR};
		e["v"] = std::string(version_str, version_str + 4);

		m_send_buf.clear();
		bencode(std::back_inserter(m_send_buf), e);
		error_code ec;

#ifdef TORRENT_DHT_VERBOSE_LOGGING
		std::stringstream log_line;
		lazy_entry print;
		int ret = lazy_bdecode(&m_send_buf[0], &m_send_buf[0] + m_send_buf.size(), print, ec);
		TORRENT_ASSERT(ret == 0);
		log_line << print_entry(print, true);
#endif

		if (m_sock.send(addr, &m_send_buf[0], (int)m_send_buf.size(), ec, send_flags))
		{
			if (ec) return false;

			// account for IP and UDP overhead
			m_sent_bytes += m_send_buf.size() + (addr.address().is_v6() ? 48 : 28);

#ifdef TORRENT_DHT_VERBOSE_LOGGING
			m_total_out_bytes += m_send_buf.size();

			if (e["z"].string() == "r")
			{
				// TODO: 2 fix this stats logging. For instance,
				// the stats counters could be factored out into its own
				// class, and dht_tracker could take an optional reference to it
//				++m_replies_sent[e["r"]];
//				m_replies_bytes_sent[e["r"]] += int(m_send_buf.size());
			}
			else if (e["z"].string() == "q")
			{
				m_queries_out_bytes += m_send_buf.size();
			}
			TORRENT_LOG(dht_tracker) << "==> " << addr << " " << log_line.str();
#endif
			return true;
		}
		else
		{
#ifdef TORRENT_DHT_VERBOSE_LOGGING
			TORRENT_LOG(dht_tracker) << "==> " << addr << " DROPPED " << log_line.str();
#endif
			return false;
		}
	}

}}

max_stars_repo_name: Erkan-Yilmaz/twister-core

max_issues_repo_name: Erkan-Yilmaz/twister-core

max_forks_repo_name: Erkan-Yilmaz/twister-core