Code:
#include <list>
#include <vector>
#include <utility>
#include <fstream>
#include <string>
#include <iostream>
#include "spooky.h"
#include <ctime>
#include <cassert>
#include <exception>
#define BASIC_TYPE(type2) \
template<typename T> struct BasicType<type2 T> { typedef typename BasicType<T>::type type; }
template<typename T> struct BasicType { typedef T type; };
template<typename T> struct BasicType<T*> { typedef typename BasicType<T>::type type; };
BASIC_TYPE(const);
BASIC_TYPE(volatile);
#define IIS_PRIMITIVE_FLOAT(type) \
template<> struct IIsPrimitive<type> { static const bool value = true; }
#define IIS_PRIMITIVE(type) \
template<> struct IIsPrimitive<unsigned type> { static const bool value = true; }; \
template<> struct IIsPrimitive<signed type> { static const bool value = true; }
template<typename Key_t> struct IIsPrimitive { static const bool value = false; };
IIS_PRIMITIVE(char);
IIS_PRIMITIVE(short);
IIS_PRIMITIVE(int);
IIS_PRIMITIVE(long);
IIS_PRIMITIVE(long long);
IIS_PRIMITIVE_FLOAT(float);
IIS_PRIMITIVE_FLOAT(double);
IIS_PRIMITIVE_FLOAT(long double);
IIS_PRIMITIVE_FLOAT(void);
template<typename Key_t> struct IsPrimitive { static const bool value = IIsPrimitive<typename BasicType<Key_t>::type>::value; };
template<bool IsPrimitive, typename Key_t> class XHashTableImpl { };
template<typename Key_t, typename Type_t> class XHashTable;
template<typename Key_t>
class XHashTableImpl<true, Key_t>
{
template<typename Key_t_, typename Value_t_> friend class XHashTable;
static unsigned int GetHash(const Key_t& Key, std::size_t Modulus)
{
return SpookyHash::Hash64(&Key, sizeof(Key), 0) % Modulus;
}
};
template<typename Key_t>
class XHashTableImpl<false, Key_t>
{
template<typename Key_t_, typename Value_t_> friend class XHashTable;
static unsigned int GetHash(const Key_t& Key, std::size_t Modulus)
{
return SpookyHash::Hash64(&Key[0], Key.size(), 0) % Modulus;
}
};
template<typename Key_t, typename Type_t, bool Const> class XHashTableImpl3;
template<typename Key_t, typename Type_t, bool Const> class XHashTableImpl2 {};
template<typename Key_t, typename Type_t>
class XHashTableImpl2<Key_t, Type_t, false>
{
template<typename Key_t_, typename Value_t_> friend class XHashTable;
template<typename Key_t_, typename Value_t_, bool Const> friend class XHashTableImpl3;
typedef XHashTable<Key_t, Type_t> HashTable_t;
typedef typename XHashTable<Key_t, Type_t>::List_t List_t;
typedef typename List_t::iterator It_t;
};
template<typename Key_t, typename Type_t>
class XHashTableImpl2<Key_t, Type_t, true>
{
template<typename Key_t_, typename Value_t_> friend class XHashTable;
template<typename Key_t_, typename Value_t_, bool Const> friend class XHashTableImpl3;
typedef const XHashTable<Key_t, Type_t> HashTable_t;
typedef const typename XHashTable<Key_t, Type_t>::List_t List_t;
typedef typename List_t::const_iterator It_t;
};
template<typename Key_t, typename Type_t, bool Const>
class XHashTableImpl3
{
template<typename Key_t_, typename Value_t_> friend class XHashTable;
static bool IFind(typename XHashTableImpl2<Key_t, Type_t, Const>::HashTable_t& Table,
const Key_t& Key,
typename XHashTableImpl2<Key_t, Type_t, Const>::List_t*& List_out,
typename XHashTableImpl2<Key_t, Type_t, Const>::It_t& it_out)
{
auto Hash = Table.GetHash<IsPrimitive<Key_t>::value>(Key);
auto & list = Table.m_Values.at(Hash);
auto list_end = list.end();
for (auto it = list.begin(); it != list_end; ++it)
{
if (it->first == Key)
{
it_out = it;
List_out = &list;
return true;
}
}
return false;
}
static bool IFind(typename XHashTableImpl2<Key_t, Type_t, Const>::HashTable_t& Table, const Key_t& Key)
{
typename XHashTableImpl2<Key_t, Type_t, Const>::List_t* List;
typename XHashTableImpl2<Key_t, Type_t, Const>::It_t it;
return IFind(Table, Key, List, it);
}
static bool IFind(typename XHashTableImpl2<Key_t, Type_t, Const>::HashTable_t& Table, const Key_t& Key, typename XHashTableImpl2<Key_t, Type_t, Const>::It_t& it)
{
typename XHashTableImpl2<Key_t, Type_t, Const>::List_t* List;
return IFind(Table, Key, List, it);
}
};
template<typename Key_t, typename Type_t>
class XHashTable
{
protected:
template<bool IsPrimitive, typename Key_t_> friend class XHashTableImpl;
template<typename Key_t_, typename Type_t_, bool Const> friend class XHashTableImpl2;
template<typename Key_t_, typename Type_t_, bool Const> friend class XHashTableImpl3;
#define XHASH_TABLE_IMPL_1(IsPrimitive) XHashTableImpl<IsPrimitive, Key_t>
#define XHASH_TABLE_IMPL_2(Const) XHashTableImpl2<Key_t, Type_t, Const>
#define XHASH_TABLE_IMPL_3(Const) XHashTableImpl3<Key_t, Type_t, Const>
typedef std::pair<Key_t, Type_t> Pair_t;
typedef std::list<Pair_t> List_t;
typedef std::vector<List_t> Vector_t;
public:
XHashTable(float LoadFactor = 0.9): m_Items(0), m_Collisions(0), m_Values(100), m_LoadFactor(LoadFactor)
{
assert(LoadFactor > 0);
}
void Add(const Key_t& Key, const Type_t& Value)
{
assert(m_Items > 0);
if ((float)m_Items / m_Values.size() > m_LoadFactor)
{
m_Values.resize(m_Values.size() * 2);
Rehash();
}
if (XHASH_TABLE_IMPL_3(true)::IFind(*this, Key))
return;
m_Items++;
auto Hash = GetHash<IsPrimitive<Key_t>::value>(Key);
auto pair = std::make_pair(Key, Value);
auto & list = m_Values.at(Hash);
if (list.size() > 0)
m_Collisions++;
assert(m_Collisions >= 0);
list.push_back(pair);
}
Type_t& Find(const Key_t& Key)
{
return const_cast<Type_t&>(Find2(Key));
}
const Type_t& Find(const Key_t& Key) const
{
return Find2(Key);
}
bool Delete(const Key_t& key)
{
List_t* List;
typename List_t::iterator it;
if (!XHASH_TABLE_IMPL_3(false)::IFind(*this, key, List, it))
return false;
List->erase(it);
m_Items--;
return true;
}
unsigned int GetCollisions() const { return m_Collisions; }
std::size_t GetStorageSize() const { return m_Values.size(); }
unsigned int GetMapSize() const { return m_Items; }
unsigned int GetLongestChainLength() const
{
unsigned int MaxChainLength = 0;
for (auto it = m_Values.begin(); it != m_Values.end(); ++it)
MaxChainLength = std::max(it->size(), MaxChainLength);
return MaxChainLength;
}
double GetAverageChainLength() const
{
long long ChainLength = 0;
long long DivideBy = 0;
for (auto it = m_Values.begin(); it != m_Values.end(); ++it)
{
auto size = it->size();
if (size > 0)
{
ChainLength += size;
DivideBy++;
}
assert(ChainLength > 0);
}
double ret = (double)ChainLength / DivideBy;
return ret;
}
protected:
template<bool IsPrimitive>
unsigned int GetHash(const Key_t& Key) const
{
return XHashTableImpl<IsPrimitive, Key_t>::GetHash(Key, m_Values.size());
}
const Type_t& Find2(const Key_t& Key) const
{
typename XHashTableImpl2<Key_t, Type_t, true>::It_t it;
if (!XHASH_TABLE_IMPL_3(true)::IFind(*this, Key, it))
throw std::runtime_error("Key not found!");
return it->second;
}
void Rehash()
{
for (std::size_t it = 0; it < m_Values.size(); ++it)
{
auto & list = m_Values.at(it);
for (auto list_it = list.begin(); list_it != list.end();)
{
const auto & key = list_it->first;
const auto & value = list_it->second;
auto NewHash = GetHash<IsPrimitive<Key_t>::value>(key);
if (NewHash != it)
{
m_Values.at(NewHash).push_back(std::make_pair(key, value));
auto old_it = list_it++;
list.erase(old_it);
}
else
++list_it;
}
}
}
Vector_t m_Values;
int m_Items;
int m_Collisions;
float m_LoadFactor;
};
template class XHashTable<std::string, int>;
int main()
{
int lines = 0;
XHashTable<std::vector<char>, int> HashTable;
std::vector<char> buf(1024);
const int NumLines = 2000000;
{
std::ifstream testfile("C:/Server/Video/Walkthrough and let's plays/Agarest/Record of Agarest War Zero - Digest Mode Fifth Generation [HD] Part 1.mp4", std::ios_base::binary);
while (testfile.read(&buf[0], buf.size()) && lines < NumLines)
{
lines++;
HashTable.Add(buf, lines);
}
}
lines = 0;
{
std::ifstream testfile("C:/Server/Video/Walkthrough and let's plays/Agarest/Record of Agarest War Zero - Digest Mode Fifth Generation [HD] Part 1.mp4", std::ios_base::binary);
while (testfile.read(&buf[0], buf.size()) && lines < NumLines)
{
lines++;
if (HashTable.Find(buf) != lines)
std::cout << "MISMATCH AT ROW " << lines << ".\n";
}
}
std::cout << "Collisions: " << HashTable.GetCollisions() << " (" << (float)HashTable.GetCollisions() / HashTable.GetMapSize() * 100 << "%)\n";
std::cout << "Number of items in map: " << HashTable.GetMapSize() << "\nSize of internal vector: " << HashTable.GetStorageSize() << "\n";
std::cout << "Max chain length: " << HashTable.GetLongestChainLength() << "\nAverage chain length: " << HashTable.GetAverageChainLength() << "\n";
return 0;
}
This seems to take care of the const issues. Is there anything else I'm missing?