HashFunction.h

Go to the documentation of this file.

/*
Copyright 2007-2025. Algoryx Simulation AB.
 
All AGX source code, intellectual property, documentation, sample code,
tutorials, scene files and technical white papers, are copyrighted, proprietary
and confidential material of Algoryx Simulation AB. You may not download, read,
store, distribute, publish, copy or otherwise disseminate, use or expose this
material unless having a written signed agreement with Algoryx Simulation AB, or having been
advised so by Algoryx Simulation AB for a time limited evaluation, or having purchased a
valid commercial license from Algoryx Simulation AB.
 
Algoryx Simulation AB disclaims all responsibilities for loss or damage caused
from using this software, unless otherwise stated in written agreements with
Algoryx Simulation AB.
*/
 
#ifndef AGX_HASHFUNCTIONS_H
#define AGX_HASHFUNCTIONS_H
 
#include <stddef.h>
#include <cstring>
#include <ratio>
 
#include <agx/agx.h>
#include <agx/Integer.h>
#include <agx/String.h>
#include <agx/hash.h>
 
namespace agx
{
 
  // See hash function declarations in agx/hash.h
 
 
 
 
  // Implementation of basic hash functions
 
 
  inline UInt64 buildHashKey(UInt32 id1, UInt32 id2)
  {
    return (id1 < id2) ? (((UInt64)id1 << 32) | (UInt64)id2) : (((UInt64)id2 << 32) | (UInt64)id1);
  }
 
  inline bool hashKeyContains(UInt64 key, UInt32 id)
  {
    return (UInt32)key == id || (UInt32)(key >> 32) == id;
  }
 
  inline void splitHashKey(UInt64 key, UInt32& id1, UInt32& id2)
  {
    id1 = (UInt32)key;
    id2 = (UInt32)(key >> 32);
  }
 
  inline UInt64 splitMix64( UInt64 x )
  {
    x += 0x9e3779b97f4a7c15ULL;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
    x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
    x =  x ^ (x >> 31);
    return x;
  }
 
  inline UInt64 hash64( UInt64 x, UInt64 y, UInt64 z )
  {
    UInt64 h = 0x9e3779b97f4a7c15ULL; // Large odd prime (golden ratio)
    h = ( h ^ splitMix64( x ) ) * 0xbf58476d1ce4e5b9ULL;
    h = ( h ^ splitMix64( y ) ) * 0x94d049bb133111ebULL;
    h = ( h ^ splitMix64( z ) );
    return h;
  }
 
  inline UInt32 hash( UInt64 x, UInt64 y, UInt64 z )
  {
    const auto h = hash64( x, y, z );
    return static_cast<UInt32>( h ^ ( h >> 32 ) );
  }
 
  inline UInt64 spatialHash( double x, double eps )
  {
    static constexpr double dInt64Max = (double)std::numeric_limits<Int64>::max();
    static constexpr double dInt64Min = (double)std::numeric_limits<Int64>::min();
 
    if ( eps < 1.0E-14 ) {
      UInt64 result{};
      std::memcpy( &result, &x, sizeof( UInt64 ) );
      return result;
    }
 
    const double t = x / eps;
    if ( t > dInt64Max )
      return static_cast<UInt64>( std::numeric_limits<Int64>::max() );
    else if ( t < dInt64Min )
      return static_cast<UInt64>( std::numeric_limits<Int64>::min() );
 
    return static_cast<UInt64>( static_cast<Int64>( std::floor( t ) ) );
  }
 
  inline UInt64 spatialHash64( double x, double y, double z, double eps )
  {
    return hash64( spatialHash( x, eps ),
                   spatialHash( y, eps ),
                   spatialHash( z, eps ) );
  }
 
  inline UInt32 spatialHash( double x, double y, double z, double eps )
  {
    return hash( spatialHash( x, eps ),
                 spatialHash( y, eps ),
                 spatialHash( z, eps ) );
  }
 
  template<typename Vec3Type, class Epsilon = std::ratio<1, 1'000'000>>
  struct SpatialHasher3D
  {
    static constexpr double CellSize = (double)Epsilon::num / Epsilon::den;
 
    inline UInt32 operator()( const Vec3Type& v ) const
    {
      return spatialHash( (double)v[ 0 ],
                          (double)v[ 1 ],
                          (double)v[ 2 ],
                          CellSize );
    }
  };
 
  inline UInt32 hash( UInt32 x, UInt32 y, UInt32 z )
  {
    const UInt32 p1 = 73856093UL;
    const UInt32 p2 = 19349663UL;
    const UInt32 p3 = 83492791UL;
 
    return (p1 * x) ^ (p2 * y) ^ (p3 * z);
  }
 
  template<typename T>
  UInt32 HashFn<T>::operator()(const T& key) const
  {
    return key.hash();
  }
 
  template<typename T>
  inline UInt32 hash(const T& key)
  {
    HashFn<T> hashFn;
    return hashFn(key);
  }
 
  inline UInt32 hash( UInt32 h1, UInt32 h2 )
  {
    return h1 ^ (h2 + 0x9e3779b9 + (h1<<6) + (h1>>2));
  }
 
  template<typename T1, typename T2>
  inline bool hashKeyEqual(const T1& key1, const T2& key2)
  {
    return key1 == key2;
  }
 
  // Pair hashing
  template<typename T1, typename T2>
  struct HashFn< std::pair<T1, T2> >
  {
    inline UInt32 operator()(const std::pair<T1,T2>& key) const
    {
      return hash(hash(key.first), hash(key.second));
    }
  };
 
  // Integer hash functions
  template<>
  struct HashFn<UInt32>
  {
    inline UInt32 operator()(UInt32 key) const
    {
      /* http://www.concentric.net/~Ttwang/tech/inthash.htm */
      key = ~key + (key << 15); // key = (key << 15) - key - 1;
      key = key ^ (key >> 12);
      key = key + (key << 2);
      key = key ^ (key >> 4);
      key = key * 2057; // key = (key + (key << 3)) + (key << 11);
      key = key ^ (key >> 16);
      return key;
    }
  };
 
  template<>
  struct HashFn<Int32>
  {
    inline UInt32 operator()(Int32 key) const
    {
      return hash((UInt32)key);
    }
  };
 
  template<>
  struct HashFn<UInt64>
  {
    inline UInt32 operator()(UInt64 key) const
    {
      /* http://www.concentric.net/~Ttwang/tech/inthash.htm */
      key = (~key) + (key << 18); // key = (key << 18) - key - 1;
      key = key ^ (key >> 31);
      key = key * 21; // key = (key + (key << 2)) + (key << 4);
      key = key ^ (key >> 11);
      key = key + (key << 6);
      key = key ^ (key >> 22);
      return (UInt32)key;
    }
  };
 
  template<>
  struct HashFn<Int64>
  {
    inline UInt32 operator()(Int64 key) const
    {
      return hash((UInt64)key);
    }
 
  };
 
#ifdef __APPLE__
  template<>
  struct HashFn<size_t>
  {
    inline UInt32 operator()(size_t key) const
    {
      return hash((UInt64)(key));
    }
 
  };
#endif
 
  // Pointer hashing
 
  template<typename T>
  struct HashFn<T*>
  {
    typedef const T* PtrT;
 
    inline UInt32 operator()(const PtrT key) const
    {
      return hash((UInt64)(key));
    }
  };
 
  // String hashing
 
  // Hash functions
 
  template<typename T>
  inline UInt32 stringHash(const T& key, UInt32 startValue = 0)
  {
    UInt32 hashValue = startValue;
 
    for (UInt32 i = 0; i < key.length(); i++)
      hashValue = 37 * hashValue + (UInt32)key[i];
 
    return hashValue;
  }
 
  template<>
  struct HashFn<std::string>
  {
    inline UInt32 operator()(const std::string& key) const
    {
      return agx::stringHash(key);
    }
  };
 
  template<>
  struct HashFn<String>
  {
    inline UInt32 operator()(const String& key) const
    {
      return agx::stringHash(key);
    }
  };
 
  template<>
  struct HashFn<const char *>
  {
    inline UInt32 operator()(const char *key) const
    {
      UInt32 hashValue = 0;
 
      while (*key)
        hashValue = 37 * hashValue + (UInt32)(*key++);
 
      return hashValue;
    }
  };
 
  inline bool hashKeyEqual(char *key1, char *key2)
  {
    return strcmp(key1, key2) == 0;
  }
 
  inline bool hashKeyEqual(const char *key1, const char *key2)
  {
    return strcmp(key1, key2) == 0;
  }
}
 
#endif /* _AGX_HASHFUNCTIONS_H_ */