joaat_hash Function

public function joaat_hash(key) result(hash_index)

generates the hash of a string and the index in the table

Arguments

TypeIntentOptionalAttributesName
integer, intent(in), DIMENSION(:):: key

Return Value integer


Contents

Source Code


Source Code

   FUNCTION joaat_hash(key) RESULT(hash_index)
      !! generates the hash of a string and the index in the table
      !! @note
      !! http://en.wikipedia.org/wiki/Hash_table
      !! http://www.burtleburtle.net/bob/hash/doobs.html
      !! However, since fortran doesn't have an unsigned 4 byte int
      !! we compute it using an integer with the appropriate range
      !! we return already the index in the table as a final result

      ! LIBXSMM: at least v1.9.0-6 is required
#if defined(__LIBXSMM) && TO_VERSION(1, 10) <= TO_VERSION(LIBXSMM_CONFIG_VERSION_MAJOR, LIBXSMM_CONFIG_VERSION_MINOR)
      USE libxsmm, ONLY: libxsmm_hash
      INTEGER, PARAMETER                                 :: seed = 0
      INTEGER, DIMENSION(:), INTENT(IN)                  :: key
         !! a string of any length
      INTEGER                                            :: hash_index
      hash_index = libxsmm_hash(key, seed)
#else
      INTEGER, DIMENSION(:), INTENT(IN)                  :: key
      INTEGER                                            :: hash_index

      INTEGER(KIND=int_8), PARAMETER                     :: b32 = 2_int_8**32 - 1_int_8

      INTEGER                                            :: i, j
      INTEGER(KIND=int_8)                                :: byte, hash

      hash = 0_int_8
      DO i = 1, SIZE(key)
         DO j = 0, 3
            byte = IAND(ISHFT(key(i), -j*8), 255)
            hash = IAND(hash + byte, b32)
            hash = IAND(hash + IAND(ISHFT(hash, 10), b32), b32)
            hash = IAND(IEOR(hash, IAND(ISHFT(hash, -6), b32)), b32)
         END DO
      END DO
      hash = IAND(hash + IAND(ISHFT(hash, 3), b32), b32)
      hash = IAND(IEOR(hash, IAND(ISHFT(hash, -11), b32)), b32)
      hash = IAND(hash + IAND(ISHFT(hash, 15), b32), b32)
      ! In fortran 4-byte-integers have only 31 bits because they are signed
      ! In fortran the rightmost (least significant) bit is in position 0
      hash_index = INT(IBCLR(hash, 31))
#endif
   END FUNCTION joaat_hash