source: trip-planner-front/node_modules/hdr-histogram-js/assembly/packedarray/PackedArrayContext.ts

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

initial commit

  • Property mode set to 100644
File size: 23.3 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 { bitCount } from "./bitcount";
10
11/**
12 * A packed-value, sparse array context used for storing 64 bit signed values.
13 *
14 * An array context is optimised for tracking sparsely set (as in mostly zeros) values that tend to not make
15 * use pof the full 64 bit value range even when they are non-zero. The array context's internal representation
16 * is such that the packed value at each virtual array index may be represented by 0-8 bytes of actual storage.
17 *
18 * An array context encodes the packed values in 8 "set trees" with each set tree representing one byte of the
19 * packed value at the virtual index in question. The {@link #getPackedIndex(int, int, boolean)} method is used
20 * to look up the byte-index corresponding to the given (set tree) value byte of the given virtual index, and can
21 * be used to add entries to represent that byte as needed. As a succesful {@link #getPackedIndex(int, int, boolean)}
22 * may require a resizing of the array, it can throw a {@link ResizeError} to indicate that the requested
23 * packed index cannot be found or added without a resize of the physical storage.
24 *
25 */
26export const MINIMUM_INITIAL_PACKED_ARRAY_CAPACITY = 16;
27const MAX_SUPPORTED_PACKED_COUNTS_ARRAY_LENGTH = Math.pow(2, 13) - 1; //(Short.MAX_VALUE / 4); TODO ALEX why ???
28const SET_0_START_INDEX = 0;
29const NUMBER_OF_SETS = 8;
30const LEAF_LEVEL_SHIFT = 3;
31const NON_LEAF_ENTRY_SLOT_INDICATORS_OFFSET = 0;
32const NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS = <u16>1;
33const PACKED_ARRAY_GROWTH_INCREMENT = 16;
34const PACKED_ARRAY_GROWTH_FRACTION_POW2 = 4;
35
36export class PackedArrayContext {
37 public readonly isPacked: boolean;
38 physicalLength: i32;
39
40 private array: ArrayBuffer;
41 private byteArray: Uint8Array;
42 private shortArray: Uint16Array;
43 private longArray: Uint64Array;
44 private populatedShortLength: i32 = 0;
45 private virtualLength: i32;
46 private topLevelShift: i32 = i32.MAX_VALUE; // Make it non-sensical until properly initialized.
47
48 constructor(virtualLength: i32, initialPhysicalLength: i32) {
49 this.physicalLength = <i32>(
50 Math.max(initialPhysicalLength, MINIMUM_INITIAL_PACKED_ARRAY_CAPACITY)
51 );
52 this.isPacked =
53 this.physicalLength <= MAX_SUPPORTED_PACKED_COUNTS_ARRAY_LENGTH;
54 if (!this.isPacked) {
55 this.physicalLength = virtualLength;
56 }
57 this.array = new ArrayBuffer(this.physicalLength * 8);
58 this.initArrayViews(this.array);
59 this.init(virtualLength);
60 }
61
62 private initArrayViews(array: ArrayBuffer): void {
63 this.byteArray = Uint8Array.wrap(array);
64 this.shortArray = Uint16Array.wrap(array);
65 this.longArray = Uint64Array.wrap(array);
66 }
67
68 private init(virtualLength: i32): void {
69 if (!this.isPacked) {
70 // Deal with non-packed context init:
71 this.virtualLength = virtualLength;
72 return;
73 }
74
75 this.populatedShortLength = SET_0_START_INDEX + 8;
76
77 // Populate empty root entries, and point to them from the root indexes:
78 for (let i = 0; i < NUMBER_OF_SETS; i++) {
79 this.setAtShortIndex(SET_0_START_INDEX + i, 0);
80 }
81
82 this.setVirtualLength(virtualLength);
83 }
84
85 public clear(): void {
86 this.byteArray.fill(0);
87 this.init(this.virtualLength);
88 }
89
90 public copyAndIncreaseSize(
91 newPhysicalArrayLength: i32,
92 newVirtualArrayLength: i32
93 ): PackedArrayContext {
94 const ctx = new PackedArrayContext(
95 newVirtualArrayLength,
96 newPhysicalArrayLength
97 );
98 if (this.isPacked) {
99 ctx.populateEquivalentEntriesWithEntriesFromOther(this);
100 }
101 return ctx;
102 }
103
104 public getPopulatedShortLength(): i32 {
105 return this.populatedShortLength;
106 }
107
108 public getPopulatedLongLength(): i32 {
109 return (this.getPopulatedShortLength() + 3) >> 2; // round up
110 }
111
112 public setAtByteIndex(byteIndex: i32, value: u8): void {
113 this.byteArray[byteIndex] = value;
114 }
115
116 public getAtByteIndex(byteIndex: i32): u8 {
117 return this.byteArray[byteIndex];
118 }
119
120 /**
121 * add a byte value to a current byte value in the array
122 * @param byteIndex index of byte value to add to
123 * @param valueToAdd byte value to add
124 * @return the afterAddValue. ((afterAddValue & 0x100) != 0) indicates a carry.
125 */
126 public addAtByteIndex(byteIndex: i32, valueToAdd: u8): u8 {
127 const newValue = this.byteArray[byteIndex] + valueToAdd;
128 this.byteArray[byteIndex] = newValue;
129 return newValue;
130 }
131
132 setPopulatedLongLength(newPopulatedLongLength: i32): void {
133 this.populatedShortLength = newPopulatedLongLength << 2;
134 }
135
136 public getVirtualLength(): i32 {
137 return this.virtualLength;
138 }
139 public length(): i32 {
140 return this.physicalLength;
141 }
142
143 setAtShortIndex(shortIndex: i32, value: u16): void {
144 this.shortArray[shortIndex] = value;
145 }
146
147 setAtLongIndex(longIndex: i32, value: u64): void {
148 this.longArray[longIndex] = value;
149 }
150
151 getAtShortIndex(shortIndex: i32): u16 {
152 return this.shortArray[shortIndex];
153 }
154
155 getIndexAtShortIndex(shortIndex: i32): u16 {
156 return this.shortArray[shortIndex];
157 }
158
159 setPackedSlotIndicators(entryIndex: i32, newPackedSlotIndicators: u16): void {
160 this.setAtShortIndex(
161 entryIndex + NON_LEAF_ENTRY_SLOT_INDICATORS_OFFSET,
162 newPackedSlotIndicators
163 );
164 }
165
166 getPackedSlotIndicators(entryIndex: i32): u16 {
167 return (
168 this.shortArray[entryIndex + NON_LEAF_ENTRY_SLOT_INDICATORS_OFFSET] &
169 0xffff
170 );
171 }
172
173 private getIndexAtEntrySlot(entryIndex: i32, slot: i32): u16 {
174 return this.getAtShortIndex(
175 entryIndex + NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS + slot
176 );
177 }
178
179 setIndexAtEntrySlot(entryIndex: i32, slot: i32, newIndexValue: u16): void {
180 this.setAtShortIndex(
181 entryIndex + NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS + slot,
182 newIndexValue
183 );
184 }
185
186 private expandArrayIfNeeded(entryLengthInLongs: i32): void {
187 const currentLength = this.length();
188 if (currentLength < this.getPopulatedLongLength() + entryLengthInLongs) {
189 const growthIncrement = <i32>(
190 max(
191 max(entryLengthInLongs, PACKED_ARRAY_GROWTH_INCREMENT),
192 this.getPopulatedLongLength() >> PACKED_ARRAY_GROWTH_FRACTION_POW2
193 )
194 );
195 this.resizeArray(currentLength + growthIncrement);
196 }
197 }
198
199 private newEntry(entryLengthInShorts: i32): i32 {
200 // Add entry at the end of the array:
201
202 const newEntryIndex = this.populatedShortLength;
203 this.expandArrayIfNeeded((entryLengthInShorts >> 2) + 1);
204 this.populatedShortLength = newEntryIndex + entryLengthInShorts;
205
206 for (let i = 0; i < entryLengthInShorts; i++) {
207 this.setAtShortIndex(newEntryIndex + i, <u16>-1); // Poison value -1. Must be overriden before reads
208 }
209 return newEntryIndex;
210 }
211
212 private newLeafEntry(): i32 {
213 // Add entry at the end of the array:
214 let newEntryIndex = this.getPopulatedLongLength();
215 this.expandArrayIfNeeded(1);
216
217 this.setPopulatedLongLength(newEntryIndex + 1);
218
219 this.setAtLongIndex(newEntryIndex, 0);
220
221 return newEntryIndex;
222 }
223
224 /**
225 * Consolidate entry with previous entry version if one exists
226 *
227 * @param entryIndex The shortIndex of the entry to be consolidated
228 * @param previousVersionIndex the index of the previous version of the entry
229 */
230 private consolidateEntry(entryIndex: i32, previousVersionIndex: i32): void {
231 const previousVersionPackedSlotsIndicators = this.getPackedSlotIndicators(
232 previousVersionIndex
233 );
234 // Previous version exists, needs consolidation
235
236 const packedSlotsIndicators = this.getPackedSlotIndicators(entryIndex);
237
238 const insertedSlotMask =
239 packedSlotsIndicators ^ previousVersionPackedSlotsIndicators; // the only bit that differs
240 const slotsBelowBitNumber = packedSlotsIndicators & (insertedSlotMask - 1);
241 const insertedSlotIndex = bitCount(slotsBelowBitNumber);
242 const numberOfSlotsInEntry = bitCount(packedSlotsIndicators);
243
244 // Copy the entry slots from previous version, skipping the newly inserted slot in the target:
245 let sourceSlot = 0;
246 for (
247 let targetSlot: u8 = 0;
248 targetSlot < numberOfSlotsInEntry;
249 targetSlot++
250 ) {
251 if (targetSlot !== insertedSlotIndex) {
252 const indexAtSlot = this.getIndexAtEntrySlot(
253 previousVersionIndex,
254 sourceSlot
255 );
256 if (indexAtSlot !== 0) {
257 this.setIndexAtEntrySlot(entryIndex, targetSlot, indexAtSlot);
258 }
259 sourceSlot++;
260 }
261 }
262 }
263
264 /**
265 * Expand entry as indicated.
266 *
267 * @param existingEntryIndex the index of the entry
268 * @param entryPointerIndex index to the slot pointing to the entry (needs to be fixed up)
269 * @param insertedSlotIndex realtive [packed] index of slot being inserted into entry
270 * @param insertedSlotMask mask value fo slot being inserted
271 * @param nextLevelIsLeaf the level below this one is a leaf level
272 * @return the updated index of the entry (-1 if epansion failed due to conflict)
273 * @throws RetryException if expansion fails due to concurrent conflict, and caller should try again.
274 */
275 expandEntry(
276 existingEntryIndex: i32,
277 entryPointerIndex: i32,
278 insertedSlotIndex: i32,
279 insertedSlotMask: i32,
280 nextLevelIsLeaf: boolean
281 ): i32 {
282 let packedSlotIndicators =
283 (<i32>this.getAtShortIndex(existingEntryIndex)) & 0xffff;
284 packedSlotIndicators |= insertedSlotMask;
285 const numberOfslotsInExpandedEntry = bitCount(packedSlotIndicators);
286
287 if (insertedSlotIndex >= <i32>numberOfslotsInExpandedEntry) {
288 throw new Error(
289 "inserted slot index is out of range given provided masks"
290 );
291 }
292
293 const expandedEntryLength =
294 numberOfslotsInExpandedEntry + NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS;
295
296 // Create new next-level entry to refer to from slot at this level:
297 let indexOfNewNextLevelEntry = 0;
298 if (nextLevelIsLeaf) {
299 indexOfNewNextLevelEntry = this.newLeafEntry(); // Establish long-index to new leaf entry
300 } else {
301 // TODO: Optimize this by creating the whole sub-tree here, rather than a step that will immediaterly expand
302
303 // Create a new 1 word (empty, no slots set) entry for the next level:
304 indexOfNewNextLevelEntry = this.newEntry(
305 NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS
306 ); // Establish short-index to new leaf entry
307
308 this.setPackedSlotIndicators(indexOfNewNextLevelEntry, 0);
309 }
310
311 const insertedSlotValue = indexOfNewNextLevelEntry;
312
313 const expandedEntryIndex = this.newEntry(expandedEntryLength);
314
315 // populate the packed indicators word:
316 this.setPackedSlotIndicators(expandedEntryIndex, <u16>packedSlotIndicators);
317
318 // Populate the inserted slot with the index of the new next level entry:
319 this.setIndexAtEntrySlot(
320 expandedEntryIndex,
321 insertedSlotIndex,
322 <u16>insertedSlotValue
323 );
324
325 this.setAtShortIndex(entryPointerIndex, <u16>expandedEntryIndex);
326 this.consolidateEntry(expandedEntryIndex, existingEntryIndex);
327
328 return expandedEntryIndex;
329 }
330
331 //
332 // ###### ######## ######## ## ## ### ## ## #### ## ## ######## ######## ## ##
333 // ## ## ## ## ## ## ## ## ## ## ## ### ## ## ## ## ## ##
334 // ## ## ## ## ## ## ## ## ## ## #### ## ## ## ## ## ##
335 // ## #### ###### ## ## ## ## ## ## ## ## ## ## ## ## ## ###### ###
336 // ## ## ## ## ## ## ######### ## ## ## ## #### ## ## ## ## ##
337 // ## ## ## ## ## ## ## ## ## ## ## ## ### ## ## ## ## ##
338 // ###### ######## ## ### ## ## ######## ## #### ## ## ######## ######## ## ##
339 //
340
341 getRootEntry(setNumber: i32, insertAsNeeded: boolean = false): i32 {
342 const entryPointerIndex = SET_0_START_INDEX + setNumber;
343 let entryIndex = <i32>this.getIndexAtShortIndex(entryPointerIndex);
344
345 if (entryIndex == 0) {
346 if (!insertAsNeeded) {
347 return 0; // Index does not currently exist in packed array;
348 }
349
350 entryIndex = this.newEntry(NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS);
351 // Create a new empty (no slots set) entry for the next level:
352 this.setPackedSlotIndicators(entryIndex, 0);
353
354 this.setAtShortIndex(entryPointerIndex, <u16>entryIndex);
355 }
356 return entryIndex;
357 }
358
359 /**
360 * Get the byte-index (into the packed array) corresponding to a given (set tree) value byte of given virtual index.
361 * Inserts new set tree nodes as needed if indicated.
362 *
363 * @param setNumber The set tree number (0-7, 0 corresponding with the LSByte set tree)
364 * @param virtualIndex The virtual index into the PackedArray
365 * @param insertAsNeeded If true, will insert new set tree nodes as needed if they do not already exist
366 * @return the byte-index corresponding to the given (set tree) value byte of the given virtual index
367 */
368 getPackedIndex(
369 setNumber: i32,
370 virtualIndex: i32,
371 insertAsNeeded: boolean
372 ): i32 {
373 if (virtualIndex >= this.virtualLength) {
374 throw new Error(
375 `Attempting access at index ${virtualIndex}, beyond virtualLength ${this.virtualLength}`
376 );
377 }
378
379 let entryPointerIndex = SET_0_START_INDEX + setNumber; // TODO init needed ?
380 let entryIndex = this.getRootEntry(setNumber, insertAsNeeded);
381 if (entryIndex == 0) {
382 return -1; // Index does not currently exist in packed array;
383 }
384
385 // Work down the levels of non-leaf entries:
386 for (
387 let indexShift = this.topLevelShift;
388 indexShift >= LEAF_LEVEL_SHIFT;
389 indexShift -= 4
390 ) {
391 const nextLevelIsLeaf = indexShift === LEAF_LEVEL_SHIFT;
392 // Target is a packedSlotIndicators entry
393 const packedSlotIndicators = this.getPackedSlotIndicators(entryIndex);
394 const slotBitNumber = (virtualIndex >>> indexShift) & 0xf;
395 const slotMask = 1 << slotBitNumber;
396 const slotsBelowBitNumber = packedSlotIndicators & (slotMask - 1);
397 const slotNumber = bitCount(slotsBelowBitNumber);
398
399 if ((packedSlotIndicators & slotMask) === 0) {
400 // The entryIndex slot does not have the contents we want
401 if (!insertAsNeeded) {
402 return -1; // Index does not currently exist in packed array;
403 }
404
405 // Expand the entry, adding the index to new entry at the proper slot:
406 entryIndex = this.expandEntry(
407 entryIndex,
408 entryPointerIndex,
409 slotNumber,
410 slotMask,
411 nextLevelIsLeaf
412 );
413 }
414
415 // Next level's entry pointer index is in the appropriate slot in in the entries array in this entry:
416 entryPointerIndex =
417 entryIndex + NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS + slotNumber;
418
419 entryIndex = this.getIndexAtShortIndex(entryPointerIndex);
420 }
421
422 // entryIndex is the long-index of a leaf entry that contains the value byte for the given set
423
424 const byteIndex = (entryIndex << 3) + (virtualIndex & 0x7); // Determine byte index offset within leaf entry
425 return byteIndex;
426 }
427
428 determineTopLevelShiftForVirtualLength(virtualLength: i32): i32 {
429 const sizeMagnitude = <i32>ceil(Math.log2(virtualLength));
430 const eightsSizeMagnitude = sizeMagnitude - 3;
431 let multipleOfFourSizeMagnitude =
432 <i32>ceil(<f64>eightsSizeMagnitude / 4.0) * 4;
433 multipleOfFourSizeMagnitude = max(multipleOfFourSizeMagnitude, 8);
434 const topLevelShiftNeeded = multipleOfFourSizeMagnitude - 4 + 3;
435 return topLevelShiftNeeded;
436 }
437
438 setVirtualLength(virtualLength: i32): void {
439 if (!this.isPacked) {
440 throw new Error(
441 "Should never be adjusting the virtual size of a non-packed context"
442 );
443 }
444 this.topLevelShift = this.determineTopLevelShiftForVirtualLength(
445 virtualLength
446 );
447 this.virtualLength = virtualLength;
448 }
449
450 getTopLevelShift(): i32 {
451 return this.topLevelShift;
452 }
453
454 //
455 // ## ## ######## ####### ######## ## ## ## ### ######## ########
456 // ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
457 // ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
458 // ### ####### ######## ## ## ######## ## ## ## ## ## ## ######
459 // ## ## ## ## ## ## ## ## ## ######### ## ##
460 // ## ## ## ## ## ## ## ## ## ## ## ## ##
461 // ## ## ## ####### ## ####### ######## ## ## ## ########
462 //
463
464 public resizeArray(newLength: i32): void {
465 const tmp = new Uint8Array(newLength * 8);
466 tmp.set(this.byteArray);
467 this.array = tmp.buffer;
468 this.initArrayViews(this.array);
469 this.physicalLength = newLength;
470 }
471
472 private populateEquivalentEntriesWithEntriesFromOther(
473 other: PackedArrayContext
474 ): void {
475 if (this.virtualLength < other.getVirtualLength()) {
476 throw new Error("Cannot populate array of smaller virtual length");
477 }
478
479 for (let i = 0; i < NUMBER_OF_SETS; i++) {
480 const otherEntryIndex = other.getAtShortIndex(SET_0_START_INDEX + i);
481 if (otherEntryIndex == 0) continue; // No tree to duplicate
482 let entryIndexPointer = SET_0_START_INDEX + i;
483 for (let i = this.topLevelShift; i > other.topLevelShift; i -= 4) {
484 // for each inserted level:
485 // Allocate entry in other:
486 const sizeOfEntry = NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS + 1;
487 const newEntryIndex = this.newEntry(sizeOfEntry);
488
489 // Link new level in.
490 this.setAtShortIndex(entryIndexPointer, <u16>newEntryIndex);
491 // Populate new level entry, use pointer to slot 0 as place to populate under:
492 this.setPackedSlotIndicators(newEntryIndex, 0x1); // Slot 0 populated
493 entryIndexPointer =
494 newEntryIndex + NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS; // Where the slot 0 index goes.
495 }
496 this.copyEntriesAtLevelFromOther(
497 other,
498 otherEntryIndex,
499 entryIndexPointer,
500 other.topLevelShift
501 );
502 }
503 }
504
505 private copyEntriesAtLevelFromOther(
506 other: PackedArrayContext,
507 otherLevelEntryIndex: i32,
508 levelEntryIndexPointer: i32,
509 otherIndexShift: i32
510 ): void {
511 const nextLevelIsLeaf = otherIndexShift == LEAF_LEVEL_SHIFT;
512 const packedSlotIndicators = other.getPackedSlotIndicators(
513 otherLevelEntryIndex
514 );
515 const numberOfSlots = bitCount(packedSlotIndicators);
516 const sizeOfEntry = NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS + numberOfSlots;
517 const entryIndex = this.newEntry(sizeOfEntry);
518
519 this.setAtShortIndex(levelEntryIndexPointer, <u16>entryIndex);
520 this.setAtShortIndex(
521 entryIndex + NON_LEAF_ENTRY_SLOT_INDICATORS_OFFSET,
522 packedSlotIndicators
523 );
524
525 for (let i: u8 = 0; i < numberOfSlots; i++) {
526 if (nextLevelIsLeaf) {
527 // Make leaf in other:
528 const leafEntryIndex = this.newLeafEntry();
529
530 this.setIndexAtEntrySlot(entryIndex, i, <u16>leafEntryIndex);
531
532 // OPTIM
533 // avoid iteration on all the values of the source ctx
534 const otherNextLevelEntryIndex = other.getIndexAtEntrySlot(
535 otherLevelEntryIndex,
536 i
537 );
538 this.longArray[leafEntryIndex] =
539 other.longArray[otherNextLevelEntryIndex];
540 } else {
541 const otherNextLevelEntryIndex = other.getIndexAtEntrySlot(
542 otherLevelEntryIndex,
543 i
544 );
545 this.copyEntriesAtLevelFromOther(
546 other,
547 otherNextLevelEntryIndex,
548 entryIndex + NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS + i,
549 otherIndexShift - 4
550 );
551 }
552 }
553 }
554
555 getAtUnpackedIndex(index: i32): u64 {
556 return this.longArray[index];
557 }
558
559 setAtUnpackedIndex(index: i32, newValue: u64): void {
560 this.longArray[index] = newValue;
561 }
562
563 lazysetAtUnpackedIndex(index: i32, newValue: u64): void {
564 this.longArray[index] = newValue;
565 }
566
567 incrementAndGetAtUnpackedIndex(index: i32): u64 {
568 this.longArray[index]++;
569 return this.longArray[index];
570 }
571
572 addAndGetAtUnpackedIndex(index: i32, valueToAdd: u64): u64 {
573 this.longArray[index] += valueToAdd;
574 return this.longArray[index];
575 }
576
577 //
578 // ######## ####### ###### ######## ######## #### ## ## ######
579 // ## ## ## ## ## ## ## ## ## ### ## ## ##
580 // ## ## ## ## ## ## ## ## #### ## ##
581 // ## ## ## ####### ###### ## ######## ## ## ## ## ## ####
582 // ## ## ## ## ## ## ## ## ## #### ## ##
583 // ## ## ## ## ## ## ## ## ## ## ### ## ##
584 // ## ####### ###### ## ## ## #### ## ## ######
585 //
586
587 private nonLeafEntryToString(
588 entryIndex: i32,
589 indexShift: i32,
590 indentLevel: i32
591 ): string {
592 let output = "";
593 for (let i = 0; i < indentLevel; i++) {
594 output += " ";
595 }
596 const packedSlotIndicators = this.getPackedSlotIndicators(entryIndex);
597 output +=
598 "slotIndiators: 0x" +
599 toHex(packedSlotIndicators) +
600 ", prevVersionIndex: 0: [ ";
601
602 const numberOfslotsInEntry = bitCount(packedSlotIndicators);
603 for (let i: u8 = 0; i < numberOfslotsInEntry; i++) {
604 output += this.getIndexAtEntrySlot(entryIndex, i).toString();
605 if (i < numberOfslotsInEntry - 1) {
606 output += ", ";
607 }
608 }
609 output += " ] (indexShift = " + indexShift.toString() + ")\n";
610 const nextLevelIsLeaf = indexShift == LEAF_LEVEL_SHIFT;
611 for (let i: u8 = 0; i < numberOfslotsInEntry; i++) {
612 const nextLevelEntryIndex = this.getIndexAtEntrySlot(entryIndex, i);
613 if (nextLevelIsLeaf) {
614 output += this.leafEntryToString(nextLevelEntryIndex, indentLevel + 4);
615 } else {
616 output += this.nonLeafEntryToString(
617 nextLevelEntryIndex,
618 indexShift - 4,
619 indentLevel + 4
620 );
621 }
622 }
623
624 return output;
625 }
626
627 private leafEntryToString(entryIndex: i32, indentLevel: i32): string {
628 let output = "";
629 for (let i = 0; i < indentLevel; i++) {
630 output += " ";
631 }
632
633 output += "Leaf bytes : ";
634 for (let i = 0; i < 8; i++) {
635 output += "0x" + toHex(this.byteArray[entryIndex * 8 + i]) + " ";
636 }
637 output += "\n";
638
639 return output;
640 }
641
642 public toString(): string {
643 let output = "PackedArrayContext:\n";
644 if (!this.isPacked) {
645 return output + "Context is unpacked:\n"; // unpackedToString();
646 }
647 for (let setNumber = 0; setNumber < NUMBER_OF_SETS; setNumber++) {
648 const entryPointerIndex = SET_0_START_INDEX + setNumber;
649 const entryIndex = this.getIndexAtShortIndex(entryPointerIndex);
650 output +=
651 "Set " +
652 setNumber.toString() +
653 ": root = " +
654 entryIndex.toString() +
655 " \n";
656 if (entryIndex == 0) continue;
657 output += this.nonLeafEntryToString(entryIndex, this.topLevelShift, 4);
658 }
659 //output += recordedValuesToString();
660 return output;
661 }
662}
663
664const hexaCode = [
665 "0",
666 "1",
667 "2",
668 "3",
669 "4",
670 "5",
671 "6",
672 "7",
673 "8",
674 "9",
675 "a",
676 "b",
677 "c",
678 "d",
679 "e",
680 "f",
681];
682
683export function toHex(n: u64): string {
684 let i = n;
685 let result = "";
686 do {
687 const current = <i32>(i & 0xf);
688 result = hexaCode[current] + result;
689 i = i >> 4;
690 } while (i > 0);
691
692 return result.padStart(2, "0");
693}
Note: See TracBrowser for help on using the repository browser.