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 21 /** 22 * Code from com.carrotsearch.hppc.LongScatterSet copy pasted, inlined and converted to Kotlin. 23 * 24 * See https://github.com/carrotsearch/hppc . 25 */ 26 internal class LongScatterSet(expectedElements: Int = 4) { 27 /** The hash array holding keys. */ 28 private var keys: LongArray = longArrayOf() 29 30 /** 31 * The number of stored keys (assigned key slots), excluding the special 32 * "empty" key, if any. 33 * 34 * @see .size 35 * @see .hasEmptyKey 36 */ 37 private var assigned = 0 38 39 /** 40 * Mask for slot scans in [.keys]. 41 */ 42 private var mask = 0 43 44 /** 45 * Expand (rehash) [.keys] when [.assigned] hits this value. 46 */ 47 private var resizeAt = 0 48 49 /** 50 * Special treatment for the "empty slot" key marker. 51 */ 52 private var hasEmptyKey = false 53 54 /** 55 * The load factor for [.keys]. 56 */ 57 private val loadFactor = 0.75 58 59 init { 60 ensureCapacity(expectedElements) 61 } 62 elementSequencenull63 fun elementSequence(): Sequence<Long> { 64 val max = mask + 1 65 var slot = -1 66 return generateSequence { 67 if (slot < max) { 68 var existing: Long 69 slot++ 70 while (slot < max) { 71 existing = keys[slot] 72 if (existing != 0L) { 73 return@generateSequence existing 74 } 75 slot++ 76 } 77 } 78 if (slot == max && hasEmptyKey) { 79 slot++ 80 return@generateSequence 0L 81 } 82 return@generateSequence null 83 } 84 } 85 hashKeynull86 private fun hashKey(key: Long): Int { 87 return HPPC.mixPhi(key) 88 } 89 plusAssignnull90 operator fun plusAssign(key: Long) { 91 add(key) 92 } 93 addnull94 fun add(key: Long): Boolean { 95 if (key == 0L) { 96 val added = !hasEmptyKey 97 hasEmptyKey = true 98 return added 99 } else { 100 val keys = this.keys 101 val mask = this.mask 102 var slot = hashKey(key) and mask 103 104 var existing = keys[slot] 105 while (existing != 0L) { 106 if (existing == key) { 107 return false 108 } 109 slot = slot + 1 and mask 110 existing = keys[slot] 111 } 112 113 if (assigned == resizeAt) { 114 allocateThenInsertThenRehash(slot, key) 115 } else { 116 keys[slot] = key 117 } 118 119 assigned++ 120 return true 121 } 122 } 123 containsnull124 operator fun contains(key: Long): Boolean { 125 if (key == 0L) { 126 return hasEmptyKey 127 } else { 128 val keys = this.keys 129 val mask = this.mask 130 var slot = hashKey(key) and mask 131 var existing = keys[slot] 132 while (existing != 0L) { 133 if (existing == key) { 134 return true 135 } 136 slot = slot + 1 and mask 137 existing = keys[slot] 138 } 139 return false 140 } 141 } 142 removenull143 fun remove(key: Long): Boolean { 144 return if (key == 0L) { 145 val hadEmptyKey = hasEmptyKey 146 hasEmptyKey = false 147 hadEmptyKey 148 } else { 149 val keys = this.keys 150 val mask = this.mask 151 var slot = hashKey(key) and mask 152 var existing: Long = keys[slot] 153 while (existing != 0L) { 154 if (existing == key) { 155 shiftConflictingKeys(slot) 156 return true 157 } 158 slot = slot + 1 and mask 159 existing = keys[slot] 160 } 161 false 162 } 163 } 164 165 /** 166 * Shift all the slot-conflicting keys allocated to (and including) `slot`. 167 */ shiftConflictingKeysnull168 private fun shiftConflictingKeys(inputGapSlot: Int) { 169 var gapSlot = inputGapSlot 170 val keys = keys 171 val mask = mask 172 // Perform shifts of conflicting keys to fill in the gap. 173 var distance = 0 174 while (true) { 175 val slot = (gapSlot + (++distance)) and mask 176 val existing = keys[slot] 177 if (existing == 0L) { 178 break 179 } 180 val idealSlot = hashKey(existing) 181 val shift = (slot - idealSlot) and mask 182 if (shift >= distance) { 183 // Entry at this position was originally at or before the gap slot. 184 // Move the conflict-shifted entry to the gap's position and repeat the procedure 185 // for any entries to the right of the current position, treating it 186 // as the new gap. 187 keys[gapSlot] = existing 188 gapSlot = slot 189 distance = 0 190 } 191 } 192 // Mark the last found gap slot without a conflict as empty. 193 keys[gapSlot] = 0L 194 assigned-- 195 } 196 releasenull197 fun release() { 198 assigned = 0 199 hasEmptyKey = false 200 allocateBuffers(HPPC.minBufferSize(4, loadFactor)) 201 } 202 ensureCapacitynull203 fun ensureCapacity(expectedElements: Int) { 204 if (expectedElements > resizeAt) { 205 val prevKeys = this.keys 206 allocateBuffers(HPPC.minBufferSize(expectedElements, loadFactor)) 207 if (size() != 0) { 208 rehash(prevKeys) 209 } 210 } 211 } 212 sizenull213 fun size(): Int { 214 return assigned + if (hasEmptyKey) 1 else 0 215 } 216 rehashnull217 private fun rehash(fromKeys: LongArray) { 218 // Rehash all stored keys into the new buffers. 219 val keys = this.keys 220 val mask = this.mask 221 var existing: Long 222 var i = fromKeys.size - 1 223 while (--i >= 0) { 224 existing = fromKeys[i] 225 if (existing != 0L) { 226 var slot = hashKey(existing) and mask 227 while (keys[slot] != 0L) { 228 slot = slot + 1 and mask 229 } 230 keys[slot] = existing 231 } 232 } 233 } 234 235 /** 236 * Allocate new internal buffers. This method attempts to allocate 237 * and assign internal buffers atomically (either allocations succeed or not). 238 */ allocateBuffersnull239 private fun allocateBuffers(arraySize: Int) { 240 // Ensure no change is done if we hit an OOM. 241 val prevKeys = this.keys 242 try { 243 val emptyElementSlot = 1 244 this.keys = LongArray(arraySize + emptyElementSlot) 245 } catch (e: OutOfMemoryError) { 246 this.keys = prevKeys 247 throw RuntimeException( 248 String.format( 249 Locale.ROOT, 250 "Not enough memory to allocate buffers for rehashing: %d -> %d", 251 size(), 252 arraySize 253 ), e 254 ) 255 } 256 257 this.resizeAt = HPPC.expandAtCount(arraySize, loadFactor) 258 this.mask = arraySize - 1 259 } 260 allocateThenInsertThenRehashnull261 private fun allocateThenInsertThenRehash( 262 slot: Int, 263 pendingKey: Long 264 ) { 265 // Try to allocate new buffers first. If we OOM, we leave in a consistent state. 266 val prevKeys = this.keys 267 allocateBuffers(HPPC.nextBufferSize(mask + 1, size(), loadFactor)) 268 269 // We have succeeded at allocating new data so insert the pending key/value at 270 // the free slot in the old arrays before rehashing. 271 prevKeys[slot] = pendingKey 272 273 // Rehash old keys, including the pending key. 274 rehash(prevKeys) 275 } 276 } 277