1
import type { PackEntryTable, ScanResult } from "../types";
2
import { getRefBaseOidAt } from "../types";
3
 
4
import { enqueueReadyDeferred, extendDeadlineChain } from "./dependencies";
5
 
6
export interface RefBaseLookup {
7
  mask: number;
8
  used: Uint8Array;
9
  keys: Uint8Array;
10
  resolvedEntries: Int32Array;
11
  waitHeadBySlot: Int32Array;
12
  nextWait: Int32Array;
13
  entrySlots: Int32Array;
14
}
15
 
16
function nextPowerOfTwo(value: number): number {
17
  let out = 1;
18
  while (out < value) out <<= 1;
19
  return out;
20
}
21
 
22
function hashOid(oid: Uint8Array): number {
23
  let hash = 2166136261;
24
  for (let i = 0; i < 20; i++) {
25
    hash ^= oid[i];
26
    hash = Math.imul(hash, 16777619);
27
  }
28
  return hash >>> 0;
29
}
30
 
31
function slotKeyEquals(keys: Uint8Array, slot: number, oid: Uint8Array): boolean {
32
  const start = slot * 20;
33
  for (let i = 0; i < 20; i++) {
34
    if (keys[start + i] !== oid[i]) return false;
35
  }
36
  return true;
37
}
38
 
39
function findOrCreateSlot(lookup: RefBaseLookup, oid: Uint8Array): number {
40
  let slot = hashOid(oid) & lookup.mask;
41
  while (lookup.used[slot]) {
42
    if (slotKeyEquals(lookup.keys, slot, oid)) return slot;
43
    slot = (slot + 1) & lookup.mask;
44
  }
45
  lookup.used[slot] = 1;
46
  lookup.keys.set(oid, slot * 20);
47
  return slot;
48
}
49
 
50
function findExistingSlot(lookup: RefBaseLookup, oid: Uint8Array): number {
51
  let slot = hashOid(oid) & lookup.mask;
52
  while (lookup.used[slot]) {
53
    if (slotKeyEquals(lookup.keys, slot, oid)) return slot;
54
    slot = (slot + 1) & lookup.mask;
55
  }
56
  return -1;
57
}
58
 
59
export function createRefBaseLookup(scanResult: ScanResult): RefBaseLookup | null {
60
  if (scanResult.refDeltaCount === 0) return null;
61
 
62
  const slotCount = nextPowerOfTwo(Math.max(4, scanResult.refDeltaCount * 2));
63
  const lookup: RefBaseLookup = {
64
    mask: slotCount - 1,
65
    used: new Uint8Array(slotCount),
66
    keys: new Uint8Array(slotCount * 20),
67
    resolvedEntries: new Int32Array(slotCount).fill(-1),
68
    waitHeadBySlot: new Int32Array(slotCount).fill(-1),
69
    nextWait: new Int32Array(scanResult.objectCount).fill(-1),
70
    entrySlots: new Int32Array(scanResult.objectCount).fill(-1),
71
  };
72
 
73
  for (let i = 0; i < scanResult.objectCount; i++) {
74
    if (scanResult.table.types[i] !== 7) continue;
75
    lookup.entrySlots[i] = findOrCreateSlot(lookup, getRefBaseOidAt(scanResult.refBaseOids, i));
76
  }
77
 
78
  return lookup;
79
}
80
 
81
export function noteResolvedEntry(
82
  lookup: RefBaseLookup,
83
  oidBuffer: Uint8Array,
84
  entryIndex: number
85
): void {
86
  const start = entryIndex * 20;
87
  const slot = findExistingSlot(lookup, oidBuffer.subarray(start, start + 20));
88
  if (slot >= 0) lookup.resolvedEntries[slot] = entryIndex;
89
}
90
 
91
export function getResolvedBaseEntry(lookup: RefBaseLookup, entryIndex: number): number {
92
  const slot = lookup.entrySlots[entryIndex];
93
  return slot < 0 ? -1 : lookup.resolvedEntries[slot];
94
}
95
 
96
export function enqueueWaitingRefDelta(lookup: RefBaseLookup, entryIndex: number): void {
97
  const slot = lookup.entrySlots[entryIndex];
98
  if (slot < 0) return;
99
  lookup.nextWait[entryIndex] = lookup.waitHeadBySlot[slot];
100
  lookup.waitHeadBySlot[slot] = entryIndex;
101
}
102
 
103
export function promoteWaitingRefDeltas(
104
  lookup: RefBaseLookup,
105
  resolvedIndex: number,
106
  table: PackEntryTable,
107
  baseIndexArr: Int32Array,
108
  isBaseArr: Uint8Array,
109
  deadlines: Uint32Array,
110
  readyDeferred?: number[],
111
  deferredQueued?: Uint8Array
112
): void {
113
  const slot = findExistingSlot(
114
    lookup,
115
    table.oids.subarray(resolvedIndex * 20, resolvedIndex * 20 + 20)
116
  );
117
  if (slot < 0) return;
118
 
119
  lookup.resolvedEntries[slot] = resolvedIndex;
120
  let waiter = lookup.waitHeadBySlot[slot];
121
  if (waiter < 0) return;
122
 
123
  lookup.waitHeadBySlot[slot] = -1;
124
  isBaseArr[resolvedIndex] = 1;
125
  while (waiter >= 0) {
126
    const next = lookup.nextWait[waiter];
127
    lookup.nextWait[waiter] = -1;
128
    if (baseIndexArr[waiter] < 0) {
129
      baseIndexArr[waiter] = resolvedIndex;
130
      extendDeadlineChain(
131
        deadlines,
132
        baseIndexArr,
133
        resolvedIndex,
134
        Math.max(table.offsets[waiter], deadlines[waiter])
135
      );
136
      if (readyDeferred && deferredQueued) {
137
        enqueueReadyDeferred(readyDeferred, deferredQueued, table, baseIndexArr, waiter);
138
      }
139
    }
140
    waiter = next;
141
  }
142
}