Practical Template Programming - Learn C++ for Game Development - page 202

Calculating SDBM Hash Values Using a Template
Metaprogram
The SDBM hash algorithm is used to turn a stream of bytes into an integer representation. The
algorithm has a very low chance of producing the same value for two different sets of data, which
makes it ideal for our purposes. It's also really easy to implement in C++, as you can see in
Listing 21-17.
Listing 21-17. The SDBM Hash Function
inline unsigned int SDBMHash(const std::string& key)
{
unsigned int result = 0;
for (unsigned int i = 0; i < key.length(); ++i)
{
int c = key[i];
result = c + (result << 6) + (result << 16) - result;
}
return result;
}
The algorithm iterates over the data, in this case a string, and uses the value of each character in an
additive algorithm that manipulates the current result using bit shifts and subtractions. The problem
with this function as implemented is that it will execute at runtime. This might be desired for some of
our data; however, for any constexpr values that we know of at compile time it would be much better
to preprocess the hashes. This makes the function a perfect target for template metaprogramming.
Listing 21-18 shows the code that achieves this.
Listing 21-18. The SDBMCalculator Template Metaprogram
template <int stringLength>
struct SDBMCalculator
{
static inline int Calculate(const char* const stringToHash, int& value)
{
int character =
SDBMCalculator<stringLength - 1>::Calculate(stringToHash, value);
value = character + (value << 6) + (value << 16) - value;
return stringToHash[stringLength - 1];
}
static inline int CalculateValue(const char* const stringToHash)
{
int value = 0;
int character = SDBMCalculator<stringLength>::Calculate(stringToHash, value);
value = character + (value << 6) + (value << 16) - value;
return value;
}
};