util_hash.go raw

   1  package xsync
   2  
   3  import (
   4  	"reflect"
   5  	"unsafe"
   6  )
   7  
   8  // makeSeed creates a random seed.
   9  func makeSeed() uint64 {
  10  	var s1 uint32
  11  	for {
  12  		s1 = runtime_fastrand()
  13  		// We use seed 0 to indicate an uninitialized seed/hash,
  14  		// so keep trying until we get a non-zero seed.
  15  		if s1 != 0 {
  16  			break
  17  		}
  18  	}
  19  	s2 := runtime_fastrand()
  20  	return uint64(s1)<<32 | uint64(s2)
  21  }
  22  
  23  // hashString calculates a hash of s with the given seed.
  24  func hashString(s string, seed uint64) uint64 {
  25  	if s == "" {
  26  		return seed
  27  	}
  28  	strh := (*reflect.StringHeader)(unsafe.Pointer(&s))
  29  	return uint64(runtime_memhash(unsafe.Pointer(strh.Data), uintptr(seed), uintptr(strh.Len)))
  30  }
  31  
  32  //go:noescape
  33  //go:linkname runtime_memhash runtime.memhash
  34  func runtime_memhash(p unsafe.Pointer, h, s uintptr) uintptr
  35  
  36  // defaultHasher creates a fast hash function for the given comparable type.
  37  // The only limitation is that the type should not contain interfaces inside
  38  // based on runtime.typehash.
  39  func defaultHasher[T comparable]() func(T, uint64) uint64 {
  40  	var zero T
  41  
  42  	if reflect.TypeOf(&zero).Elem().Kind() == reflect.Interface {
  43  		return func(value T, seed uint64) uint64 {
  44  			iValue := any(value)
  45  			i := (*iface)(unsafe.Pointer(&iValue))
  46  			return runtime_typehash64(i.typ, i.word, seed)
  47  		}
  48  	} else {
  49  		var iZero any = zero
  50  		i := (*iface)(unsafe.Pointer(&iZero))
  51  		return func(value T, seed uint64) uint64 {
  52  			return runtime_typehash64(i.typ, unsafe.Pointer(&value), seed)
  53  		}
  54  	}
  55  }
  56  
  57  // how interface is represented in memory
  58  type iface struct {
  59  	typ  uintptr
  60  	word unsafe.Pointer
  61  }
  62  
  63  // same as runtime_typehash, but always returns a uint64
  64  // see: maphash.rthash function for details
  65  func runtime_typehash64(t uintptr, p unsafe.Pointer, seed uint64) uint64 {
  66  	if unsafe.Sizeof(uintptr(0)) == 8 {
  67  		return uint64(runtime_typehash(t, p, uintptr(seed)))
  68  	}
  69  
  70  	lo := runtime_typehash(t, p, uintptr(seed))
  71  	hi := runtime_typehash(t, p, uintptr(seed>>32))
  72  	return uint64(hi)<<32 | uint64(lo)
  73  }
  74  
  75  //go:noescape
  76  //go:linkname runtime_typehash runtime.typehash
  77  func runtime_typehash(t uintptr, p unsafe.Pointer, h uintptr) uintptr
  78