1
import type { OrderedPackSnapshotEntry } from "@/worker/git/operations/fetch/types";
2
 
3
import { BinaryHeap, bytesToHex } from "@/worker/common";
4
 
5
type CompactionHeapEntry = {
6
  packSlot: number;
7
  objectIndex: number;
8
};
9
 
10
function compareRawOid(
11
  leftView: OrderedPackSnapshotEntry["idx"],
12
  leftIndex: number,
13
  rightView: OrderedPackSnapshotEntry["idx"],
14
  rightIndex: number
15
): number {
16
  const leftStart = leftIndex * 20;
17
  const rightStart = rightIndex * 20;
18
  for (let byteIndex = 0; byteIndex < 20; byteIndex++) {
19
    const diff =
20
      leftView.rawNames[leftStart + byteIndex] - rightView.rawNames[rightStart + byteIndex];
21
    if (diff !== 0) return diff;
22
  }
23
  return 0;
24
}
25
 
26
function compareRawOidToBuffer(
27
  view: OrderedPackSnapshotEntry["idx"],
28
  objectIndex: number,
29
  other: Uint8Array
30
): number {
31
  const start = objectIndex * 20;
32
  for (let byteIndex = 0; byteIndex < 20; byteIndex++) {
33
    const diff = view.rawNames[start + byteIndex] - other[byteIndex];
34
    if (diff !== 0) return diff;
35
  }
36
  return 0;
37
}
38
 
39
function copyRawOid(view: OrderedPackSnapshotEntry["idx"], objectIndex: number): Uint8Array {
40
  const start = objectIndex * 20;
41
  return view.rawNames.slice(start, start + 20);
42
}
43
 
44
export function buildCompactionNeededOids(sourcePacks: OrderedPackSnapshotEntry[]): string[] {
45
  const heap = new BinaryHeap<CompactionHeapEntry>((left, right) => {
46
    const leftView = sourcePacks[left.packSlot]!.idx;
47
    const rightView = sourcePacks[right.packSlot]!.idx;
48
    const cmp = compareRawOid(leftView, left.objectIndex, rightView, right.objectIndex);
49
    if (cmp !== 0) return cmp;
50
    if (left.packSlot !== right.packSlot) return left.packSlot - right.packSlot;
51
    return left.objectIndex - right.objectIndex;
52
  });
53
 
54
  for (let packSlot = 0; packSlot < sourcePacks.length; packSlot++) {
55
    if (sourcePacks[packSlot]!.idx.count > 0) {
56
      heap.push({ packSlot, objectIndex: 0 });
57
    }
58
  }
59
 
60
  const neededOids: string[] = [];
61
  let previousOid: Uint8Array | undefined;
62
 
63
  while (!heap.isEmpty()) {
64
    const current = heap.pop()!;
65
    const currentPack = sourcePacks[current.packSlot]!;
66
    if (
67
      !previousOid ||
68
      compareRawOidToBuffer(currentPack.idx, current.objectIndex, previousOid) !== 0
69
    ) {
70
      const oidBytes = copyRawOid(currentPack.idx, current.objectIndex);
71
      neededOids.push(bytesToHex(oidBytes));
72
      previousOid = oidBytes;
73
    }
74
 
75
    const nextObjectIndex = current.objectIndex + 1;
76
    if (nextObjectIndex < currentPack.idx.count) {
77
      heap.push({
78
        packSlot: current.packSlot,
79
        objectIndex: nextObjectIndex,
80
      });
81
    }
82
  }
83
 
84
  return neededOids;
85
}