|
#include "probing_hash_table.hh" |
|
|
|
#include "murmur_hash.hh" |
|
#include "scoped.hh" |
|
|
|
#define BOOST_TEST_MODULE ProbingHashTableTest |
|
#include <boost/test/unit_test.hpp> |
|
#include <boost/scoped_array.hpp> |
|
#include <boost/functional/hash.hpp> |
|
#include <cstdio> |
|
#include <cstdlib> |
|
#include <cstring> |
|
#include <stdint.h> |
|
|
|
namespace util { |
|
namespace { |
|
|
|
struct Entry { |
|
unsigned char key; |
|
typedef unsigned char Key; |
|
|
|
unsigned char GetKey() const { |
|
return key; |
|
} |
|
|
|
void SetKey(unsigned char to) { |
|
key = to; |
|
} |
|
|
|
uint64_t GetValue() const { |
|
return value; |
|
} |
|
|
|
uint64_t value; |
|
}; |
|
|
|
typedef ProbingHashTable<Entry, boost::hash<unsigned char> > Table; |
|
|
|
BOOST_AUTO_TEST_CASE(simple) { |
|
size_t size = Table::Size(10, 1.2); |
|
boost::scoped_array<char> mem(new char[size]); |
|
memset(mem.get(), 0, size); |
|
|
|
Table table(mem.get(), size); |
|
const Entry *i = NULL; |
|
BOOST_CHECK(!table.Find(2, i)); |
|
Entry to_ins; |
|
to_ins.key = 3; |
|
to_ins.value = 328920; |
|
table.Insert(to_ins); |
|
BOOST_REQUIRE(table.Find(3, i)); |
|
BOOST_CHECK_EQUAL(3, i->GetKey()); |
|
BOOST_CHECK_EQUAL(static_cast<uint64_t>(328920), i->GetValue()); |
|
BOOST_CHECK(!table.Find(2, i)); |
|
} |
|
|
|
struct Entry64 { |
|
uint64_t key; |
|
typedef uint64_t Key; |
|
|
|
Entry64() {} |
|
|
|
explicit Entry64(uint64_t key_in) { |
|
key = key_in; |
|
} |
|
|
|
Key GetKey() const { return key; } |
|
void SetKey(uint64_t to) { key = to; } |
|
}; |
|
|
|
struct MurmurHashEntry64 { |
|
std::size_t operator()(uint64_t value) const { |
|
return util::MurmurHash64A(&value, 8); |
|
} |
|
}; |
|
|
|
typedef ProbingHashTable<Entry64, MurmurHashEntry64> Table64; |
|
|
|
BOOST_AUTO_TEST_CASE(Double) { |
|
for (std::size_t initial = 19; initial < 30; ++initial) { |
|
size_t size = Table64::Size(initial, 1.2); |
|
scoped_malloc mem(MallocOrThrow(size)); |
|
Table64 table(mem.get(), size, std::numeric_limits<uint64_t>::max()); |
|
table.Clear(); |
|
for (uint64_t i = 0; i < 19; ++i) { |
|
table.Insert(Entry64(i)); |
|
} |
|
table.CheckConsistency(); |
|
mem.call_realloc(table.DoubleTo()); |
|
table.Double(mem.get()); |
|
table.CheckConsistency(); |
|
for (uint64_t i = 20; i < 40 ; ++i) { |
|
table.Insert(Entry64(i)); |
|
} |
|
mem.call_realloc(table.DoubleTo()); |
|
table.Double(mem.get()); |
|
table.CheckConsistency(); |
|
} |
|
} |
|
|
|
} |
|
} |
|
|
