531 lines
16 KiB
C++
531 lines
16 KiB
C++
/***
|
|
Copyright (C) 2022 J Reece Wilson (a/k/a "Reece"). All rights reserved.
|
|
|
|
File: auHashUtils.hpp
|
|
Date: 2022-3-23
|
|
Author: Reece
|
|
***/
|
|
#pragma once
|
|
|
|
#include "auFNV1Utils.hpp"
|
|
#include "auMemoryModel.hpp"
|
|
#include "auString.hpp"
|
|
#include "auUTF8StringView.hpp"
|
|
|
|
#define _AU_HASH_UTILS_HAS_STD
|
|
|
|
#if 1 || defined(AURORA_COMPILER_CLANG) && !defined(AURORA_BUG_DOES_CLANG_SUPPORT_64_BIT_CONSTEXPR_YET)
|
|
#define _AU_HASH_RETARD_COMPILER
|
|
#define _AH_HAS_RETARD_CONSTEXPR
|
|
#else
|
|
#define _AH_HAS_RETARD_CONSTEXPR constexpr
|
|
#endif
|
|
|
|
template <class T>
|
|
struct AuHasHashCode
|
|
{
|
|
template <class C> static constexpr AuTrueType Test(decltype(&C::HashCode));
|
|
template <class C> static constexpr AuFalseType Test(...);
|
|
using type = decltype(Test<T>(0));
|
|
};
|
|
|
|
template <class T>
|
|
constexpr inline bool AuHasHashCode_v = AuHasHashCode<T>::type::value;
|
|
|
|
namespace AuHash
|
|
{
|
|
template <class Key>
|
|
struct hash
|
|
{
|
|
#if defined(_AU_HASH_UTILS_HAS_STD)
|
|
AuConditional_t<AuHasHashCode_v<Key>, AuUInt8, std::hash<Key>> trashHasher;
|
|
#endif
|
|
|
|
AuUInt operator()(const Key &ref) const
|
|
{
|
|
if constexpr (AuHasHashCode_v<Key>)
|
|
{
|
|
return ref.HashCode();
|
|
}
|
|
#if defined(_AU_HASH_UTILS_HAS_STD)
|
|
else
|
|
{
|
|
return trashHasher(ref);
|
|
}
|
|
#endif
|
|
}
|
|
};
|
|
|
|
#if defined(_AU_WANT_GOOGLE_HASHES)
|
|
// Thomas Wang, Integer Hash Functions: https://web.archive.org/web/20061201032901/http://www.concentric.net/%7ETtwang/tech/inthash.htm
|
|
// Updated version under V8: V8/v9-11/src/utils/utils.h
|
|
//
|
|
// I'm sure Google's tweaks and subsequence implementations have justification grounded in reality more so than the initial publishing of a 1999ish article by some dude at HP
|
|
// Real world experience > 1999 HP guy > whatever the fuck the stl is doing (i think ms just uses fnv1s for everything)
|
|
//
|
|
// Preserving original function names for ease of xref. unseeded vs implied seeded doesnt mean anything. see: ComputeLongHash comment.
|
|
inline _AH_HAS_RETARD_CONSTEXPR AuUInt32 ComputeUnseededHash(AuUInt32 key)
|
|
{
|
|
AuUInt32 hash = key;
|
|
hash = ~hash + (hash << 15); // hash = (hash << 15) - hash - 1;
|
|
hash = hash ^ (hash >> 12);
|
|
hash = hash + (hash << 2);
|
|
hash = hash ^ (hash >> 4);
|
|
hash = hash * 2057; // hash = (hash + (hash << 3)) + (hash << 11);
|
|
hash = hash ^ (hash >> 16);
|
|
return hash;
|
|
}
|
|
|
|
// ComputeLongHash(base::double_to_uint64(AsNumber())); ( pre-maglev V8 wasn't u64 optimizated. )
|
|
// ComputeLongHash(static_cast<uint64_t>(digit(0))); ( most js wont touch >31bit ints. )
|
|
inline _AH_HAS_RETARD_CONSTEXPR AuUInt64 ComputeLongHash(AuUInt64 key)// ( i'm sure this function's fine for all ranges. )
|
|
{
|
|
AuUInt64 hash = key;
|
|
hash = ~hash + (hash << 18); // hash = (hash << 18) - hash - 1;
|
|
hash = hash ^ (hash >> 31);
|
|
hash = hash * 21; // hash = (hash + (hash << 2)) + (hash << 4);
|
|
hash = hash ^ (hash >> 11); // key = key ^ (key >>> 28); ?
|
|
hash = hash + (hash << 6); // key = key + (key << 31); ?
|
|
hash = hash ^ (hash >> 22); // ???????????
|
|
return hash;
|
|
}
|
|
#else
|
|
// nvm lost respect for google
|
|
// maybe the above hashing algorithms could squeeze out a few more cycles on some architectures, but i doubt it.
|
|
|
|
inline _AH_HAS_RETARD_CONSTEXPR AuUInt32 ComputeUnseededHash(AuUInt32 key)
|
|
{
|
|
#if defined(_AU_HASH_RETARD_COMPILER)
|
|
return AuFnv1aRuntime(&key, sizeof(key));
|
|
#else
|
|
return AuFnv1a64Runtime<sizeof(AuUInt32)>(&key);
|
|
#endif
|
|
}
|
|
|
|
inline _AH_HAS_RETARD_CONSTEXPR AuUInt64 ComputeLongHash(AuUInt64 key)
|
|
{
|
|
#if defined(_AU_HASH_RETARD_COMPILER)
|
|
return AuFnv1aRuntime(&key, sizeof(key));
|
|
#else
|
|
return AuFnv1a64Runtime<sizeof(AuUInt64)>(&key);
|
|
#endif
|
|
}
|
|
#endif
|
|
|
|
#if defined(_AU_HASH_RETARD_COMPILER)
|
|
#define _HASH_INT(type) \
|
|
template <> \
|
|
struct hash<type> \
|
|
{ \
|
|
_AH_HAS_RETARD_CONSTEXPR AuUInt operator ()(const type b) const \
|
|
{ \
|
|
return AuFnv1aRuntime<sizeof(b)>(&b); \
|
|
} \
|
|
};
|
|
#else
|
|
#define _HASH_INT(type) \
|
|
template <> \
|
|
struct hash<type> \
|
|
{ \
|
|
_AH_HAS_RETARD_CONSTEXPR AuUInt operator ()(const type b) const \
|
|
{ \
|
|
return AuFnv1aRuntime<sizeof(b)>(&b); \
|
|
} \
|
|
};
|
|
#endif
|
|
|
|
#if defined(AURORA_IS_32BIT)
|
|
|
|
#define _HASH_INT32BIT(type) \
|
|
template <> \
|
|
struct hash<type> \
|
|
{ \
|
|
_AH_HAS_RETARD_CONSTEXPR AuUInt operator ()(const type intValue) const \
|
|
{ \
|
|
return ComputeUnseededHash(AuUInt32(intValue)); \
|
|
} \
|
|
};
|
|
|
|
#else
|
|
|
|
#define _HASH_INT32BIT(type) \
|
|
template <> \
|
|
struct hash<type> \
|
|
{ \
|
|
_AH_HAS_RETARD_CONSTEXPR AuUInt operator ()(const type intValue) const \
|
|
{ \
|
|
return ComputeLongHash(AuUInt64(intValue)); \
|
|
} \
|
|
};
|
|
|
|
#endif
|
|
|
|
#if defined(AURORA_IS_32BIT)
|
|
|
|
#define _HASH_INT64BIT(type) \
|
|
template <> \
|
|
struct hash<type> \
|
|
{ \
|
|
_AH_HAS_RETARD_CONSTEXPR AuUInt operator ()(const type intValue) const \
|
|
{ \
|
|
return AuUInt32(ComputeLongHash(AuUInt64(intValue)) & 0xFFFFFFFF); \
|
|
} \
|
|
};
|
|
|
|
#else
|
|
|
|
#define _HASH_INT64BIT(type) \
|
|
template <> \
|
|
struct hash<type> \
|
|
{ \
|
|
_AH_HAS_RETARD_CONSTEXPR AuUInt operator ()(const type intValue) const \
|
|
{ \
|
|
return ComputeLongHash(AuUInt64(intValue)); \
|
|
} \
|
|
};
|
|
|
|
#endif
|
|
|
|
#if 0
|
|
_HASH_INT32BIT(bool);
|
|
_HASH_INT32BIT(char);
|
|
_HASH_INT32BIT(signed char);
|
|
_HASH_INT32BIT(unsigned char);
|
|
_HASH_INT32BIT(char8_t);
|
|
_HASH_INT32BIT(char16_t);
|
|
_HASH_INT32BIT(char32_t);
|
|
_HASH_INT32BIT(wchar_t);
|
|
_HASH_INT32BIT(short);
|
|
_HASH_INT32BIT(unsigned short);
|
|
_HASH_INT32BIT(int);
|
|
_HASH_INT32BIT(unsigned int);
|
|
_HASH_INT64BIT(long); // I know, I don't care.
|
|
_HASH_INT64BIT(long long);
|
|
_HASH_INT64BIT(unsigned long);
|
|
_HASH_INT64BIT(unsigned long long);
|
|
#else
|
|
_HASH_INT(bool);
|
|
_HASH_INT(char);
|
|
_HASH_INT(signed char);
|
|
_HASH_INT(unsigned char);
|
|
_HASH_INT(char8_t);
|
|
_HASH_INT(char16_t);
|
|
_HASH_INT(char32_t);
|
|
_HASH_INT(wchar_t);
|
|
_HASH_INT(short);
|
|
_HASH_INT(unsigned short);
|
|
_HASH_INT(int);
|
|
_HASH_INT(unsigned int);
|
|
_HASH_INT(long); // I know, I don't care.
|
|
_HASH_INT(long long);
|
|
_HASH_INT(unsigned long);
|
|
_HASH_INT(unsigned long long);
|
|
#endif
|
|
_HASH_INT(float);
|
|
_HASH_INT(double);
|
|
_HASH_INT(long double);
|
|
_HASH_INT(std::nullptr_t);
|
|
|
|
#undef _HASH_INT
|
|
#undef _HASH_INT32BIT
|
|
#undef _HASH_INT64BIT
|
|
|
|
template <class T>
|
|
struct hash<T *>
|
|
{
|
|
_AH_HAS_RETARD_CONSTEXPR AuUInt operator ()(T *ptr) const
|
|
{
|
|
#if defined(AURORA_IS_32BIT)
|
|
return ComputeUnseededHash(AuUInt(ptr));
|
|
#else
|
|
return ComputeLongHash(AuUInt(ptr));
|
|
#endif
|
|
}
|
|
};
|
|
|
|
template <class T>
|
|
struct less
|
|
{
|
|
bool operator()(const T &lhs, const T &rhs) const
|
|
{
|
|
if constexpr (AuHasHashCode_v<T>)
|
|
{
|
|
return lhs.HashCode() < rhs.HashCode();
|
|
}
|
|
else
|
|
{
|
|
return lhs < rhs;
|
|
}
|
|
}
|
|
};
|
|
|
|
template <class T>
|
|
struct equal
|
|
{
|
|
bool operator()(const T &lhs, const T &rhs) const
|
|
{
|
|
return lhs == rhs;
|
|
}
|
|
};
|
|
|
|
template <>
|
|
struct equal<std::string>
|
|
{
|
|
using is_transparent = void;
|
|
|
|
bool operator()(std::string_view lhs, std::string_view rhs) const
|
|
{
|
|
return lhs == rhs;
|
|
}
|
|
};
|
|
|
|
template <>
|
|
struct equal<AuRONString>
|
|
{
|
|
using is_transparent = void;
|
|
|
|
bool operator()(std::string_view lhs, std::string_view rhs) const
|
|
{
|
|
return lhs == rhs;
|
|
}
|
|
};
|
|
|
|
template <>
|
|
struct equal<AuROString>
|
|
{
|
|
using is_transparent = void;
|
|
|
|
bool operator()(std::string_view lhs, std::string_view rhs) const
|
|
{
|
|
return lhs == rhs;
|
|
}
|
|
};
|
|
|
|
template <>
|
|
struct equal<std::basic_string<char, std::char_traits<char>, Aurora::Memory::StringAllocator<char>>>
|
|
{
|
|
using is_transparent = void;
|
|
|
|
bool operator()(std::string_view lhs, std::string_view rhs) const
|
|
{
|
|
return lhs == rhs;
|
|
}
|
|
};
|
|
}
|
|
|
|
template <class T, AU_TEMPLATE_ENABLE_WHEN(AuHasHashCode_v<T>)>
|
|
inline AuUInt AuHashCode(const T &ref)
|
|
{
|
|
return ref.HashCode();
|
|
}
|
|
|
|
template <class T, AU_TEMPLATE_ENABLE_WHEN(!AuHasHashCode_v<T>)>
|
|
inline AuUInt AuHashCode(const T &ref)
|
|
{
|
|
return AuHash::hash<T>()(ref);
|
|
}
|
|
|
|
#include <auROXTL/auTuple.hpp>
|
|
|
|
namespace AuHash
|
|
{
|
|
template <typename T, typename Z>
|
|
struct hash<AuPair<T, Z>>
|
|
{
|
|
AuUInt operator ()(const AuPair<T, Z> &pair) const
|
|
{
|
|
return AuHashCode(pair.first) ^
|
|
AuHashCode(pair.second);
|
|
}
|
|
};
|
|
|
|
template <class ...Ts>
|
|
struct hash<AuTuple<Ts...>>
|
|
{
|
|
AuUInt operator ()(const AuTuple<Ts...> &tuple) const
|
|
{
|
|
AuUInt uHashCode {};
|
|
AuTupleForEach(tuple, [&](auto & a /*c++14 poggurs*/)
|
|
{
|
|
uHashCode ^= AuHashCode(a);
|
|
});
|
|
return uHashCode;
|
|
}
|
|
};
|
|
|
|
// container bug in msvc?
|
|
#if 0
|
|
template <>
|
|
struct hash<std::string_view>
|
|
{
|
|
size_t operator()(std::string_view txt) const
|
|
{
|
|
return AuFnv1aRuntime(txt.data(), txt.size());
|
|
}
|
|
};
|
|
#endif
|
|
|
|
template <>
|
|
struct hash<std::string>
|
|
{
|
|
using is_transparent = void;
|
|
using transparent_key_equal = equal<std::string>;
|
|
|
|
size_t operator()(std::string_view txt) const
|
|
{
|
|
return hash<std::string_view>{}(txt);
|
|
}
|
|
};
|
|
|
|
template <>
|
|
struct hash<AuROString>
|
|
{
|
|
using is_transparent = void;
|
|
using transparent_key_equal = equal<std::string>;
|
|
|
|
size_t operator()(AuROString txt) const
|
|
{
|
|
return hash<std::string_view>{}(txt);
|
|
}
|
|
};
|
|
|
|
template <>
|
|
struct hash<AuRONString>
|
|
{
|
|
using is_transparent = void;
|
|
using transparent_key_equal = equal<std::string>;
|
|
|
|
size_t operator()(AuROString txt) const
|
|
{
|
|
return hash<std::string_view>{}(txt);
|
|
}
|
|
};
|
|
|
|
template <>
|
|
struct hash<std::basic_string<char, std::char_traits<char>, Aurora::Memory::StringAllocator<char>>>
|
|
{
|
|
using is_transparent = void;
|
|
using transparent_key_equal = equal<std::basic_string<char, std::char_traits<char>, Aurora::Memory::StringAllocator<char>>>;
|
|
|
|
size_t operator()(std::string_view txt) const
|
|
{
|
|
return hash<std::string_view>{}(txt);
|
|
}
|
|
};
|
|
|
|
template <>
|
|
struct less<std::string>
|
|
{
|
|
using is_transparent = void;
|
|
|
|
bool operator()(std::string_view lhs, std::string_view rhs) const
|
|
{
|
|
#if 0
|
|
return AuFnv1aRuntime(lhs.data(), lhs.size()) < AuFnv1aRuntime(rhs.data(), rhs.size());
|
|
#else
|
|
return hash<std::string_view>{}(lhs) < hash<std::string_view>{}(rhs);
|
|
#endif
|
|
}
|
|
};
|
|
|
|
template <>
|
|
struct less<std::basic_string<char, std::char_traits<char>, Aurora::Memory::StringAllocator<char>>>
|
|
{
|
|
using is_transparent = void;
|
|
|
|
bool operator()(std::string_view lhs, std::string_view rhs) const
|
|
{
|
|
#if 0
|
|
return AuFnv1aRuntime(lhs.data(), lhs.size()) < AuFnv1aRuntime(rhs.data(), rhs.size());
|
|
#else
|
|
return hash<std::string_view>{}(lhs) < hash<std::string_view>{}(rhs);
|
|
#endif
|
|
}
|
|
};
|
|
|
|
template <>
|
|
struct less<std::string_view>
|
|
{
|
|
bool operator()(std::string_view lhs, std::string_view rhs) const
|
|
{
|
|
#if 0
|
|
return AuFnv1aRuntime(lhs.data(), lhs.size()) < AuFnv1aRuntime(rhs.data(), rhs.size());
|
|
#else
|
|
return hash<std::string_view>{}(lhs) < hash<std::string_view>{}(rhs);
|
|
#endif
|
|
}
|
|
};
|
|
|
|
template <>
|
|
struct less<AuRONString>
|
|
{
|
|
bool operator()(AuRONString lhs, AuRONString rhs) const
|
|
{
|
|
#if 0
|
|
return AuFnv1aRuntime(lhs.data(), lhs.size()) < AuFnv1aRuntime(rhs.data(), rhs.size());
|
|
#else
|
|
return hash<std::string_view>{}(AuROString(lhs)) < hash<std::string_view>{}(AuROString(lhs));
|
|
#endif
|
|
}
|
|
};
|
|
|
|
template <>
|
|
struct less<AuROString>
|
|
{
|
|
bool operator()(AuROString lhs, AuROString rhs) const
|
|
{
|
|
#if 0
|
|
return AuFnv1aRuntime(lhs.data(), lhs.size()) < AuFnv1aRuntime(rhs.data(), rhs.size());
|
|
#else
|
|
return hash<std::string_view>{}(lhs) < hash<std::string_view>{}(rhs);
|
|
#endif
|
|
}
|
|
};
|
|
|
|
template <>
|
|
struct less<const char *>
|
|
{
|
|
bool operator()(const char *lhs, const char *rhs) const
|
|
{
|
|
#if 0
|
|
return AuFnv1aRuntime(lhs, strlen(lhs)) < AuFnv1aRuntime(rhs, strlen(rhs));
|
|
#else
|
|
return hash<std::string_view>{}(lhs) < hash<std::string_view>{}(rhs);
|
|
#endif
|
|
}
|
|
};
|
|
}
|
|
|
|
template <class T>
|
|
struct AuEnableHashCodeOnData
|
|
{
|
|
AuUInt HashCode() const
|
|
{
|
|
#if defined(AURORA_IS_32BIT)
|
|
return AuFnv1a64Runtime<sizeof(T)>(AuStaticCast<AuAddConst_t<T>>(this));
|
|
#else
|
|
return AuFnv1a64Runtime<sizeof(T)>(AuStaticCast<AuAddConst_t<T>>(this));
|
|
#endif
|
|
}
|
|
};
|
|
|
|
#if defined(_AU_HASH_RETARD_COMPILER)
|
|
#undef _AU_HASH_RETARD_COMPILER
|
|
#undef _AH_HAS_RETARD_CONSTEXPR
|
|
#endif
|
|
|
|
namespace AuHash
|
|
{
|
|
template <class T>
|
|
struct hash<AuSPtr<T>>
|
|
{
|
|
AuUInt operator ()(const AuSPtr<T> &ptr) const
|
|
{
|
|
#if defined(AURORA_IS_32BIT)
|
|
return ComputeUnseededHash(AuUInt(ptr.get()));
|
|
#else
|
|
return ComputeLongHash(AuUInt(ptr.get()));
|
|
#endif
|
|
}
|
|
};
|
|
} |