source: trip-planner-front/node_modules/hdr-histogram-js/assembly/packedarray/PackedArray.ts@ 6c1585f

Last change on this file since 6c1585f was 6a3a178, checked in by Ema <ema_spirova@…>, 3 years ago

initial commit

  • Property mode set to 100644
File size: 7.2 KB
Line 
1/*
2 * This is a AssemblyScript port of the original Java version, which was written by
3 * Gil Tene as described in
4 * https://github.com/HdrHistogram/HdrHistogram
5 * and released to the public domain, as explained at
6 * http://creativecommons.org/publicdomain/zero/1.0/
7 */
8
9import {
10 PackedArrayContext,
11 MINIMUM_INITIAL_PACKED_ARRAY_CAPACITY,
12} from "./PackedArrayContext";
13
14const NUMBER_OF_SETS: u8 = 8;
15
16/**
17 * A Packed array of signed 64 bit values, and supports {@link #get get()}, {@link #set set()},
18 * {@link #add add()} and {@link #increment increment()} operations on the logical contents of the array.
19 *
20 * An {@link PackedLongArray} Uses {@link PackedArrayContext} to track
21 * the array's logical contents. Contexts may be switched when a context requires resizing
22 * to complete logical array operations (get, set, add, increment). Contexts are
23 * established and used within critical sections in order to facilitate concurrent
24 * implementors.
25 *
26 */
27export class PackedArray {
28 [key: number]: number;
29
30 private arrayContext: PackedArrayContext;
31
32 constructor(
33 virtualLength: i32,
34 initialPhysicalLength: i32 = MINIMUM_INITIAL_PACKED_ARRAY_CAPACITY
35 ) {
36 this.arrayContext = new PackedArrayContext(
37 virtualLength,
38 initialPhysicalLength
39 );
40 }
41
42 public resize(newVirtualArrayLength: i32): PackedArray {
43 this.setVirtualLength(newVirtualArrayLength);
44 return this;
45 }
46
47 public setVirtualLength(newVirtualArrayLength: i32): void {
48 if (newVirtualArrayLength < this.length()) {
49 throw new Error(
50 "Cannot set virtual length, as requested length " +
51 newVirtualArrayLength.toString() +
52 " is smaller than the current virtual length " +
53 this.length().toString()
54 );
55 }
56 const currentArrayContext = this.arrayContext;
57 if (
58 currentArrayContext.isPacked &&
59 currentArrayContext.determineTopLevelShiftForVirtualLength(
60 newVirtualArrayLength
61 ) == currentArrayContext.getTopLevelShift()
62 ) {
63 // No changes to the array context contents is needed. Just change the virtual length.
64 currentArrayContext.setVirtualLength(newVirtualArrayLength);
65 return;
66 }
67 this.arrayContext = currentArrayContext.copyAndIncreaseSize(
68 this.getPhysicalLength(),
69 newVirtualArrayLength
70 );
71 }
72
73 @operator("[]") private __get(index: i32): u64 {
74 return this.get(index);
75 }
76
77 @operator("[]=") private __set(index: i32, value: u64): void {
78 this.set(index, value);
79 }
80
81 /**
82 * Get value at virtual index in the array
83 * @param index the virtual array index
84 * @return the array value at the virtual index given
85 */
86 get(index: i32): u64 {
87 let value: u64 = 0;
88 for (let byteNum: u8 = 0; byteNum < NUMBER_OF_SETS; byteNum++) {
89 let byteValueAtPackedIndex: u64 = 0;
90
91 // Deal with unpacked context:
92 if (!this.arrayContext.isPacked) {
93 return this.arrayContext.getAtUnpackedIndex(index);
94 }
95 // Context is packed:
96 const packedIndex = this.arrayContext.getPackedIndex(
97 byteNum,
98 index,
99 false
100 );
101 if (packedIndex < 0) {
102 return value;
103 }
104 byteValueAtPackedIndex =
105 (<u64>this.arrayContext.getAtByteIndex(packedIndex)) << (byteNum << 3);
106 value += byteValueAtPackedIndex;
107 }
108 return value;
109 }
110
111 /**
112 * Increment value at a virrual index in the array
113 * @param index virtual index of value to increment
114 */
115 public increment(index: i32): void {
116 this.add(index, 1);
117 }
118
119 private safeGetPackedIndexgetPackedIndex(
120 setNumber: i32,
121 virtualIndex: i32
122 ): i32 {
123 return this.arrayContext.getPackedIndex(setNumber, virtualIndex, true);
124 }
125
126 /**
127 * Add to a value at a virtual index in the array
128 * @param index the virtual index of the value to be added to
129 * @param value the value to add
130 */
131 public add(index: i32, value: u64): void {
132 let remainingValueToAdd = value;
133
134 for (
135 let byteNum = 0, byteShift = 0;
136 byteNum < NUMBER_OF_SETS;
137 byteNum++, byteShift += 8
138 ) {
139 // Deal with unpacked context:
140 if (!this.arrayContext.isPacked) {
141 this.arrayContext.addAndGetAtUnpackedIndex(index, value);
142 return;
143 }
144 // Context is packed:
145 const packedIndex = this.safeGetPackedIndexgetPackedIndex(byteNum, index);
146
147 const byteToAdd = remainingValueToAdd & 0xff;
148
149 const afterAddByteValue = this.arrayContext.addAtByteIndex(
150 packedIndex,
151 byteToAdd
152 );
153
154 // Reduce remaining value to add by amount just added:
155 remainingValueToAdd -= byteToAdd;
156
157 remainingValueToAdd = remainingValueToAdd >> 8;
158 // Account for carry:
159 remainingValueToAdd += afterAddByteValue >> 8;
160
161 if (remainingValueToAdd == 0) {
162 return; // nothing to add to higher magnitudes
163 }
164 }
165 }
166
167 /**
168 * Set the value at a virtual index in the array
169 * @param index the virtual index of the value to set
170 * @param value the value to set
171 */
172 set(index: i32, value: u64): void {
173 let bytesAlreadySet: u8 = 0;
174 let valueForNextLevels = value;
175 for (let byteNum: u8 = 0; byteNum < NUMBER_OF_SETS; byteNum++) {
176 // Establish context within: critical section
177
178 // Deal with unpacked context:
179 if (!this.arrayContext.isPacked) {
180 this.arrayContext.setAtUnpackedIndex(index, value);
181 return;
182 }
183 // Context is packed:
184 if (valueForNextLevels == 0) {
185 // Special-case zeros to avoid inflating packed array for no reason
186 const packedIndex = this.arrayContext.getPackedIndex(
187 byteNum,
188 index,
189 false
190 );
191 if (packedIndex < 0) {
192 return; // no need to create entries for zero values if they don't already exist
193 }
194 }
195 // Make sure byte is populated:
196 const packedIndex = this.arrayContext.getPackedIndex(
197 byteNum,
198 index,
199 true
200 );
201
202 // Determine value to write, and prepare for next levels
203 const byteToWrite: u8 = <u8>(valueForNextLevels & 0xff);
204 valueForNextLevels = valueForNextLevels >> 8;
205
206 if (byteNum < bytesAlreadySet) {
207 // We want to avoid writing to the same byte twice when not doing so for the
208 // entire 64 bit value atomically, as doing so opens a race with e.g. concurrent
209 // adders. So dobn't actually write the byte if has been written before.
210 continue;
211 }
212 this.arrayContext.setAtByteIndex(packedIndex, byteToWrite);
213 bytesAlreadySet++;
214 }
215 }
216
217 /**
218 * Get the current physical length (in longs) of the array's backing storage
219 * @return the current physical length (in longs) of the array's current backing storage
220 */
221 getPhysicalLength(): i32 {
222 return this.arrayContext.physicalLength;
223 }
224
225 public get estimatedFootprintInBytes(): i32 {
226 // @ts-ignore
227 return offsetof<PackedArray>() + this.getPhysicalLength();
228 }
229
230 /**
231 * Get the (virtual) length of the array
232 * @return the (virtual) length of the array
233 */
234 length(): i32 {
235 return this.arrayContext.getVirtualLength();
236 }
237
238 /**
239 * Clear the array contents
240 */
241 public clear(): void {
242 this.arrayContext.clear();
243 }
244
245 public toString(): string {
246 let output = "PackedArray:\n";
247 output += this.arrayContext.toString();
248 return output;
249 }
250}
Note: See TracBrowser for help on using the repository browser.