00001 #include "util/probing_hash_table.hh"
00002
00003 #include "util/murmur_hash.hh"
00004 #include "util/scoped.hh"
00005
00006 #define BOOST_TEST_MODULE ProbingHashTableTest
00007 #include <boost/test/unit_test.hpp>
00008 #include <boost/scoped_array.hpp>
00009 #include <boost/functional/hash.hpp>
00010 #include <cstdio>
00011 #include <cstdlib>
00012 #include <cstring>
00013 #include <stdint.h>
00014
00015 namespace util {
00016 namespace {
00017
00018 struct Entry {
00019 unsigned char key;
00020 typedef unsigned char Key;
00021
00022 unsigned char GetKey() const {
00023 return key;
00024 }
00025
00026 void SetKey(unsigned char to) {
00027 key = to;
00028 }
00029
00030 uint64_t GetValue() const {
00031 return value;
00032 }
00033
00034 uint64_t value;
00035 };
00036
00037 typedef ProbingHashTable<Entry, boost::hash<unsigned char> > Table;
00038
00039 BOOST_AUTO_TEST_CASE(simple) {
00040 size_t size = Table::Size(10, 1.2);
00041 boost::scoped_array<char> mem(new char[size]);
00042 memset(mem.get(), 0, size);
00043
00044 Table table(mem.get(), size);
00045 const Entry *i = NULL;
00046 BOOST_CHECK(!table.Find(2, i));
00047 Entry to_ins;
00048 to_ins.key = 3;
00049 to_ins.value = 328920;
00050 table.Insert(to_ins);
00051 BOOST_REQUIRE(table.Find(3, i));
00052 BOOST_CHECK_EQUAL(3, i->GetKey());
00053 BOOST_CHECK_EQUAL(static_cast<uint64_t>(328920), i->GetValue());
00054 BOOST_CHECK(!table.Find(2, i));
00055 }
00056
00057 struct Entry64 {
00058 uint64_t key;
00059 typedef uint64_t Key;
00060
00061 Entry64() {}
00062
00063 explicit Entry64(uint64_t key_in) {
00064 key = key_in;
00065 }
00066
00067 Key GetKey() const { return key; }
00068 void SetKey(uint64_t to) { key = to; }
00069 };
00070
00071 struct MurmurHashEntry64 {
00072 std::size_t operator()(uint64_t value) const {
00073 return util::MurmurHash64A(&value, 8);
00074 }
00075 };
00076
00077 typedef ProbingHashTable<Entry64, MurmurHashEntry64> Table64;
00078
00079 BOOST_AUTO_TEST_CASE(Double) {
00080 for (std::size_t initial = 19; initial < 30; ++initial) {
00081 size_t size = Table64::Size(initial, 1.2);
00082 scoped_malloc mem(MallocOrThrow(size));
00083 Table64 table(mem.get(), size, std::numeric_limits<uint64_t>::max());
00084 table.Clear();
00085 for (uint64_t i = 0; i < 19; ++i) {
00086 table.Insert(Entry64(i));
00087 }
00088 table.CheckConsistency();
00089 mem.call_realloc(table.DoubleTo());
00090 table.Double(mem.get());
00091 table.CheckConsistency();
00092 for (uint64_t i = 20; i < 40 ; ++i) {
00093 table.Insert(Entry64(i));
00094 }
00095 mem.call_realloc(table.DoubleTo());
00096 table.Double(mem.get());
00097 table.CheckConsistency();
00098 }
00099 }
00100
00101 }
00102 }