1 /* 2 * Copyright 2010-2013, Carrot Search s.c., Boznicza 11/56, Poznan, Poland 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package shark.internal.hppc 18 19 import java.util.Locale 20 import kotlin.math.ceil 21 import kotlin.math.max 22 import kotlin.math.min 23 24 /** 25 * Code from https://github.com/carrotsearch/hppc copy pasted, inlined and converted to Kotlin. 26 */ 27 internal object HPPC { 28 29 private const val PHI_C64 = -0x61c8864680b583ebL 30 mixPhinull31 fun mixPhi(k: Long): Int { 32 val h = k * PHI_C64 33 return (h xor h.ushr(32)).toInt() 34 } 35 36 private const val MIN_HASH_ARRAY_LENGTH = 4 37 private const val MAX_HASH_ARRAY_LENGTH = (-0x80000000).ushr(1) 38 minBufferSizenull39 fun minBufferSize( 40 elements: Int, 41 loadFactor: Double 42 ): Int { 43 var length = ceil(elements / loadFactor) 44 .toLong() 45 if (length == elements.toLong()) { 46 length++ 47 } 48 length = max(MIN_HASH_ARRAY_LENGTH.toLong(), nextHighestPowerOfTwo(length)) 49 50 if (length > MAX_HASH_ARRAY_LENGTH) { 51 throw RuntimeException( 52 String.format( 53 Locale.ROOT, 54 "Maximum array size exceeded for this load factor (elements: %d, load factor: %f)", 55 elements, 56 loadFactor 57 ) 58 ) 59 } 60 61 return length.toInt() 62 } 63 nextHighestPowerOfTwonull64 fun nextHighestPowerOfTwo(input: Long): Long { 65 var v = input 66 v-- 67 v = v or (v shr 1) 68 v = v or (v shr 2) 69 v = v or (v shr 4) 70 v = v or (v shr 8) 71 v = v or (v shr 16) 72 v = v or (v shr 32) 73 v++ 74 return v 75 } 76 expandAtCountnull77 fun expandAtCount( 78 arraySize: Int, 79 loadFactor: Double 80 ): Int { 81 return min(arraySize - 1, ceil(arraySize * loadFactor).toInt()) 82 } 83 nextBufferSizenull84 fun nextBufferSize( 85 arraySize: Int, 86 elements: Int, 87 loadFactor: Double 88 ): Int { 89 if (arraySize == MAX_HASH_ARRAY_LENGTH) { 90 throw RuntimeException( 91 String.format( 92 Locale.ROOT, 93 "Maximum array size exceeded for this load factor (elements: %d, load factor: %f)", 94 elements, 95 loadFactor 96 ) 97 ) 98 } 99 100 return arraySize shl 1 101 } 102 } 103