<lambda>null1 package shark.internal
2
3 import shark.internal.aosp.ByteArrayTimSort
4
5 /**
6 * Wraps a byte array of entries where each entry is an id followed by bytes for the value.
7 * `id` is a long if [longIdentifiers] is true and an int otherwise. Each entry has [bytesPerValue]
8 * value bytes. Entries are appended into the array via [append]. Once done, the backing array
9 * is sorted and turned into a [SortedBytesMap] by calling [moveToSortedMap].
10 */
11 internal class UnsortedByteEntries(
12 private val bytesPerValue: Int,
13 private val longIdentifiers: Boolean,
14 private val initialCapacity: Int = 4,
15 private val growthFactor: Double = 2.0
16 ) {
17
18 private val bytesPerEntry = bytesPerValue + if (longIdentifiers) 8 else 4
19
20 private var entries: ByteArray? = null
21 private val subArray = MutableByteSubArray()
22 private var subArrayIndex = 0
23
24 private var assigned: Int = 0
25 private var currentCapacity = 0
26
27 fun append(
28 key: Long
29 ): MutableByteSubArray {
30 if (entries == null) {
31 currentCapacity = initialCapacity
32 entries = ByteArray(currentCapacity * bytesPerEntry)
33 } else {
34 if (currentCapacity == assigned) {
35 val newCapacity = (currentCapacity * growthFactor).toInt()
36 growEntries(newCapacity)
37 currentCapacity = newCapacity
38 }
39 }
40 assigned++
41 subArrayIndex = 0
42 subArray.writeId(key)
43 return subArray
44 }
45
46 fun moveToSortedMap(): SortedBytesMap {
47 if (assigned == 0) {
48 return SortedBytesMap(longIdentifiers, bytesPerValue, ByteArray(0))
49 }
50 val entries = entries!!
51 // Sort entries by keys, which are ids of 4 or 8 bytes.
52 ByteArrayTimSort.sort(entries, 0, assigned, bytesPerEntry) {
53 entrySize, o1Array, o1Index, o2Array, o2Index ->
54 if (longIdentifiers) {
55 readLong(o1Array, o1Index * entrySize)
56 .compareTo(
57 readLong(o2Array, o2Index * entrySize)
58 )
59 } else {
60 readInt(o1Array, o1Index * entrySize)
61 .compareTo(
62 readInt(o2Array, o2Index * entrySize)
63 )
64 }
65 }
66 val sortedEntries = if (entries.size > assigned * bytesPerEntry) {
67 entries.copyOf(assigned * bytesPerEntry)
68 } else entries
69 this.entries = null
70 assigned = 0
71 return SortedBytesMap(
72 longIdentifiers, bytesPerValue, sortedEntries
73 )
74 }
75
76 private fun readInt(
77 array: ByteArray,
78 index: Int
79 ): Int {
80 var pos = index
81 return (array[pos++] and 0xff shl 24
82 or (array[pos++] and 0xff shl 16)
83 or (array[pos++] and 0xff shl 8)
84 or (array[pos] and 0xff))
85 }
86
87 @Suppress("NOTHING_TO_INLINE") // Syntactic sugar.
88 private inline infix fun Byte.and(other: Long): Long = toLong() and other
89
90 @Suppress("NOTHING_TO_INLINE") // Syntactic sugar.
91 private inline infix fun Byte.and(other: Int): Int = toInt() and other
92
93 private fun readLong(
94 array: ByteArray,
95 index: Int
96 ): Long {
97 var pos = index
98 return (array[pos++] and 0xffL shl 56
99 or (array[pos++] and 0xffL shl 48)
100 or (array[pos++] and 0xffL shl 40)
101 or (array[pos++] and 0xffL shl 32)
102 or (array[pos++] and 0xffL shl 24)
103 or (array[pos++] and 0xffL shl 16)
104 or (array[pos++] and 0xffL shl 8)
105 or (array[pos] and 0xffL))
106 }
107
108 private fun growEntries(newCapacity: Int) {
109 val newEntries = ByteArray(newCapacity * bytesPerEntry)
110 System.arraycopy(entries, 0, newEntries, 0, assigned * bytesPerEntry)
111 entries = newEntries
112 }
113
114 internal inner class MutableByteSubArray {
115 fun writeByte(value: Byte) {
116 val index = subArrayIndex
117 subArrayIndex++
118 require(index in 0..bytesPerEntry) {
119 "Index $index should be between 0 and $bytesPerEntry"
120 }
121 val valuesIndex = ((assigned - 1) * bytesPerEntry) + index
122 entries!![valuesIndex] = value
123 }
124
125 fun writeId(value: Long) {
126 if (longIdentifiers) {
127 writeLong(value)
128 } else {
129 writeInt(value.toInt())
130 }
131 }
132
133 fun writeInt(value: Int) {
134 val index = subArrayIndex
135 subArrayIndex += 4
136 require(index >= 0 && index <= bytesPerEntry - 4) {
137 "Index $index should be between 0 and ${bytesPerEntry - 4}"
138 }
139 var pos = ((assigned - 1) * bytesPerEntry) + index
140 val values = entries!!
141 values[pos++] = (value ushr 24 and 0xff).toByte()
142 values[pos++] = (value ushr 16 and 0xff).toByte()
143 values[pos++] = (value ushr 8 and 0xff).toByte()
144 values[pos] = (value and 0xff).toByte()
145 }
146
147 fun writeTruncatedLong(
148 value: Long,
149 byteCount: Int
150 ) {
151 val index = subArrayIndex
152 subArrayIndex += byteCount
153 require(index >= 0 && index <= bytesPerEntry - byteCount) {
154 "Index $index should be between 0 and ${bytesPerEntry - byteCount}"
155 }
156 var pos = ((assigned - 1) * bytesPerEntry) + index
157 val values = entries!!
158
159 var shift = (byteCount - 1) * 8
160 while (shift >= 8) {
161 values[pos++] = (value ushr shift and 0xffL).toByte()
162 shift -= 8
163 }
164 values[pos] = (value and 0xffL).toByte()
165 }
166
167 fun writeLong(value: Long) {
168 val index = subArrayIndex
169 subArrayIndex += 8
170 require(index >= 0 && index <= bytesPerEntry - 8) {
171 "Index $index should be between 0 and ${bytesPerEntry - 8}"
172 }
173 var pos = ((assigned - 1) * bytesPerEntry) + index
174 val values = entries!!
175 values[pos++] = (value ushr 56 and 0xffL).toByte()
176 values[pos++] = (value ushr 48 and 0xffL).toByte()
177 values[pos++] = (value ushr 40 and 0xffL).toByte()
178 values[pos++] = (value ushr 32 and 0xffL).toByte()
179 values[pos++] = (value ushr 24 and 0xffL).toByte()
180 values[pos++] = (value ushr 16 and 0xffL).toByte()
181 values[pos++] = (value ushr 8 and 0xffL).toByte()
182 values[pos] = (value and 0xffL).toByte()
183 }
184 }
185 }
186
187