1566 lines
65 KiB
C#
1566 lines
65 KiB
C#
using System.Buffers.Binary;
|
||
using System.Collections.Concurrent;
|
||
using System.Runtime.InteropServices;
|
||
using System.Text;
|
||
using Microsoft.Win32.SafeHandles;
|
||
|
||
namespace FluidExplorer.Services.Search.Usn;
|
||
|
||
/// <summary>增量监听实际生效的通道。</summary>
|
||
public enum IndexWatchMode
|
||
{
|
||
/// <summary>未监听。</summary>
|
||
None,
|
||
|
||
/// <summary>FSCTL_READ_USN_JOURNAL（首选，能拿到 FRN、改名、删除等完整信息）。</summary>
|
||
UsnJournal,
|
||
|
||
/// <summary>ReadDirectoryChangesW 回退（日志不可用/无权限时；靠路径 → FileIndex 反查 FRN）。</summary>
|
||
DirectoryChanges
|
||
}
|
||
|
||
/// <summary>
|
||
/// Everything 式的单卷 NTFS 索引。
|
||
///
|
||
/// 构建：FSCTL_ENUM_USN_DATA 一次性枚举整个 MFT 拿到“全部文件名/父目录/属性”，
|
||
/// 再（若权限允许）直接读原始 $MFT 补齐真实文件大小与精确时间戳。
|
||
/// 监听：FSCTL_READ_USN_JOURNAL 阻塞式循环消费 USN 变更，墓碑标记删除、就地更新改名/大小。
|
||
/// 查询：在 Struct-of-Arrays + 大字符池上做并行扫描，候选零 string 分配，毫秒级返回 Top-N。
|
||
///
|
||
/// 线程模型：
|
||
/// * <see cref="IndexStore"/> 快照通过 <see cref="Volatile"/> 发布；结构只增不减，读侧无需持锁。
|
||
/// * 追加/扩容走 <c>_gate</c> 串行化（写极少），因此读查询永远不会被写长期阻塞。
|
||
/// </summary>
|
||
public sealed class UsnVolumeIndex : IFileIndex, IDisposable
|
||
{
|
||
private const int DefaultMaxResults = 2000;
|
||
|
||
/// <summary>
|
||
/// FSCTL_ENUM_USN_DATA 的输出缓冲。参考实现用 0x3900，但更大的缓冲能显著减少往返次数；
|
||
/// 有些驱动对超大缓冲不友好，1MB 是实践中安全的上限。
|
||
/// </summary>
|
||
private const int EnumBufferSize = 1024 * 1024;
|
||
private const int WatchBufferSize = 1024 * 1024;
|
||
private const long WatchBytesToWaitFor = 64 * 1024;
|
||
private const int MaxPathDepth = 256;
|
||
private const int MaxPathCacheEntries = 262144;
|
||
private const long FileTimeToTicksOffset = 504911232000000000L; // 1601-01-01 → 0001-01-01
|
||
private const int MaxTrackedRecords = 64 * 1024 * 1024;
|
||
|
||
private readonly string _devicePath; // \\.\C:
|
||
private readonly string _volumeRoot; // C:\
|
||
private readonly ConcurrentDictionary<ulong, string> _dirPathCache = new();
|
||
private readonly object _gate = new();
|
||
|
||
private IndexStore _store = new(1024);
|
||
private FrnMap _frnMap = new(16);
|
||
|
||
private SafeFileHandle? _volumeHandle;
|
||
private MftReader? _mftReader;
|
||
private Thread? _watchThread;
|
||
private IntPtr _watchThreadHandle;
|
||
private SafeFileHandle? _watchHandle;
|
||
|
||
private int _state = (int)IndexState.NotStarted;
|
||
private long _liveCount;
|
||
private long _changeCount;
|
||
private volatile bool _watchRequested;
|
||
private volatile bool _stopRequested;
|
||
private DirectoryChangeWatcher? _directoryWatcher;
|
||
private bool _disposed;
|
||
|
||
public UsnVolumeIndex(string volumeRoot)
|
||
{
|
||
(_volumeRoot, _devicePath) = NormalizeVolumeRoot(volumeRoot);
|
||
}
|
||
|
||
// ================================================================ IFileIndex
|
||
|
||
public string VolumeRoot => _volumeRoot;
|
||
|
||
public IndexState State => (IndexState)Volatile.Read(ref _state);
|
||
|
||
/// <summary>存活条目数（不含已打墓碑的删除项）。</summary>
|
||
public long EntryCount => Volatile.Read(ref _liveCount);
|
||
|
||
/// <summary>为 true 表示大小/时间来自原始 MFT 解析；false 表示 USN 降级（<see cref="IndexedEntry.Size"/> 多为 -1）。</summary>
|
||
public bool UsesRawMft { get; private set; }
|
||
|
||
/// <summary>降级或失败的具体原因（中文），便于 UI 直接展示。</summary>
|
||
public string? DegradationReason { get; private set; }
|
||
|
||
/// <summary>监听期间累计处理的 USN 变更条数。</summary>
|
||
public long WatchedChangeCount => Volatile.Read(ref _changeCount);
|
||
|
||
/// <summary>
|
||
/// 当前实际生效的增量监听通道：优先 USN 变更日志；日志不可用（无权限/不存在且建不了）时回退为
|
||
/// <see cref="IndexWatchMode.DirectoryChanges"/>（ReadDirectoryChangesW，不需要日志权限）。
|
||
/// </summary>
|
||
public IndexWatchMode WatchMode { get; private set; } = IndexWatchMode.None;
|
||
|
||
/// <summary>
|
||
/// 卷上没有 USN 日志时是否允许自动创建（FSCTL_CREATE_USN_JOURNAL，系统默认大小）。
|
||
/// 默认 true（Everything 的行为）；创建属于对卷的持久改动，调用方若不愿改动系统可置 false。
|
||
/// 无论此值如何，本类<b>从不删除</b>日志。
|
||
/// </summary>
|
||
public bool CreateJournalIfMissing { get; set; } = true;
|
||
|
||
/// <summary>索引构建是否因为找不到 $MFT 而完全没有建立（此时只有回退监听可用）。</summary>
|
||
public bool HasIndex => Volatile.Read(ref _liveCount) > 0 || Volatile.Read(ref _store).Count > 0;
|
||
|
||
public event EventHandler<IndexStateChangedEventArgs>? StateChanged;
|
||
|
||
/// <summary>
|
||
/// 建立索引。本方法内部使用线程池，绝不阻塞调用线程，也绝不向外抛异常：
|
||
/// 权限不足 → <see cref="IndexState.RequiresElevation"/>；非 NTFS → <see cref="IndexState.Failed"/>；
|
||
/// 取消 → <see cref="IndexState.Stopped"/>。调用方一律通过 <see cref="State"/> / <see cref="StateChanged"/> 判断结果。
|
||
/// </summary>
|
||
public Task BuildAsync(IProgress<double>? progress, CancellationToken cancellationToken)
|
||
{
|
||
// 注意：这里传 CancellationToken.None —— 取消由内部协作式处理，避免调用方拿到 Canceled 状态的 Task。
|
||
return Task.Run(() => BuildCore(progress, cancellationToken), CancellationToken.None);
|
||
}
|
||
|
||
public void StartWatching()
|
||
{
|
||
_watchRequested = true;
|
||
var state = State;
|
||
// 构建还没结束的话，构建完成后会自动开始监听（见 BuildCore 末尾）
|
||
if (state is not (IndexState.Ready or IndexState.Watching)) return;
|
||
StartWatchThread();
|
||
}
|
||
|
||
public void Stop()
|
||
{
|
||
// 显式 Stop 之后不再自动开始监听，直到调用方再次 StartWatching()
|
||
_watchRequested = false;
|
||
StopWatchingInternal();
|
||
SetState(IndexState.Stopped, $"{_volumeRoot} 的索引已停止。");
|
||
}
|
||
|
||
public void Dispose()
|
||
{
|
||
if (_disposed) return;
|
||
_disposed = true;
|
||
StopWatchingInternal();
|
||
try { _volumeHandle?.Dispose(); } catch (ObjectDisposedException) { }
|
||
_volumeHandle = null;
|
||
_mftReader = null;
|
||
}
|
||
|
||
// ================================================================ 构建
|
||
|
||
private void BuildCore(IProgress<double>? progress, CancellationToken cancellationToken)
|
||
{
|
||
try
|
||
{
|
||
StopWatchingInternal();
|
||
SetState(IndexState.Building, $"正在建立 {_volumeRoot} 的文件索引…");
|
||
progress?.Report(0d);
|
||
|
||
// ---- 1) 打开卷句柄：首选 GENERIC_READ|GENERIC_WRITE，失败后逐级降权 ----
|
||
var (handle, access, openError) = OpenVolumeWithBestAccess();
|
||
if (handle is null)
|
||
{
|
||
DegradationReason = UsnNative.DescribeError(openError, $"无法打开卷 {_devicePath}");
|
||
if (openError == UsnNative.ERROR_ACCESS_DENIED)
|
||
{
|
||
SetState(IndexState.RequiresElevation,
|
||
"读取 NTFS 主文件表需要管理员权限，可点击以管理员身份重启索引服务。");
|
||
}
|
||
else
|
||
{
|
||
// 其它错误（卷未就绪 / 盘符不存在 / 设备被占用…）不是权限问题，别误导用户去提权
|
||
SetState(IndexState.Failed, $"{_volumeRoot} 索引不可用：{DegradationReason}");
|
||
}
|
||
return;
|
||
}
|
||
|
||
SafeFileHandle? old;
|
||
lock (_gate)
|
||
{
|
||
old = _volumeHandle;
|
||
_volumeHandle = handle;
|
||
}
|
||
old?.Dispose();
|
||
|
||
bool canReadData = (access & (UsnNative.GENERIC_READ | UsnNative.FILE_READ_DATA)) != 0;
|
||
|
||
// ---- 2) 卷信息：同时用来判断是不是 NTFS ----
|
||
var volumeData = default(UsnNative.NtfsVolumeDataBuffer);
|
||
bool hasVolumeData = QueryNtfsVolumeData(handle, out volumeData, out var volumeDataError);
|
||
if (!hasVolumeData)
|
||
{
|
||
var fileSystem = TryGetFileSystemName();
|
||
if (fileSystem is not null && !fileSystem.Equals("NTFS", StringComparison.OrdinalIgnoreCase))
|
||
{
|
||
DegradationReason = $"卷 {_volumeRoot} 的文件系统是 {fileSystem}，不是 NTFS";
|
||
SetState(IndexState.Failed, $"{_volumeRoot} 不是 NTFS 卷（检测到 {fileSystem}），Everything 式 USN 索引仅支持 NTFS。");
|
||
return;
|
||
}
|
||
|
||
// 确实是 NTFS（或无法判定）却拿不到 NTFS 卷结构 —— 实测在非管理员下
|
||
// FSCTL_GET_NTFS_VOLUME_DATA 会返回 ERROR_INVALID_FUNCTION(1) 而不是 ERROR_ACCESS_DENIED(5)，
|
||
// 所以这里必须按“权限不足”处理，否则会把正常的 NTFS 卷误判成“不是 NTFS”。
|
||
DegradationReason = UsnNative.DescribeError(volumeDataError, "FSCTL_GET_NTFS_VOLUME_DATA 失败");
|
||
SetState(IndexState.RequiresElevation,
|
||
"读取 NTFS 主文件表需要管理员权限，可点击以管理员身份重启索引服务。");
|
||
return;
|
||
}
|
||
|
||
// ---- 3) USN 变更日志：不存在就尝试创建（创建后绝不自动删除）----
|
||
bool hasJournal = EnsureUsnJournal(handle, out var journal, out var journalError, out bool journalCreated);
|
||
if (hasJournal && journalCreated)
|
||
{
|
||
SetState(IndexState.Building, "本卷原先没有 USN 变更日志，已按系统默认大小创建以便做增量监听。");
|
||
}
|
||
else if (!hasJournal)
|
||
{
|
||
DegradationReason ??= UsnNative.DescribeError(journalError, "FSCTL_QUERY_USN_JOURNAL / FSCTL_CREATE_USN_JOURNAL 失败");
|
||
}
|
||
|
||
// ---- 4) 原始 MFT 读取器（需要管理员，成功则大小/时间用真实值）----
|
||
MftReader? mft = null;
|
||
string? mftError = null;
|
||
if (canReadData && hasVolumeData)
|
||
{
|
||
mft = MftReader.TryCreate(handle, in volumeData, out mftError);
|
||
}
|
||
else if (!canReadData)
|
||
{
|
||
mftError = "卷句柄不含 FILE_READ_DATA 权限（非管理员），无法直接读取 $MFT";
|
||
}
|
||
else
|
||
{
|
||
mftError = "无法获取 NTFS 卷结构信息";
|
||
}
|
||
|
||
UsesRawMft = mft is not null;
|
||
if (mft is null)
|
||
{
|
||
DegradationReason = mftError;
|
||
}
|
||
|
||
// ---- 5) 枚举 MFT ----
|
||
int estimated = 65536;
|
||
int bytesPerRecord = 1024;
|
||
if (hasVolumeData && volumeData.BytesPerFileRecordSegment > 0)
|
||
{
|
||
bytesPerRecord = (int)volumeData.BytesPerFileRecordSegment;
|
||
if (volumeData.MftValidDataLength > 0)
|
||
{
|
||
long total = volumeData.MftValidDataLength / bytesPerRecord;
|
||
if (total > 0 && total <= MaxTrackedRecords) estimated = (int)total;
|
||
else if (total > MaxTrackedRecords) estimated = MaxTrackedRecords;
|
||
}
|
||
}
|
||
|
||
var store = new IndexStore(estimated);
|
||
var map = new FrnMap(Math.Min(estimated, 1 << 20));
|
||
int live = 0;
|
||
string? degradedNote = null;
|
||
|
||
// 枚举阶段占总进度的 65%，原始 MFT 补齐阶段占 35%
|
||
double enumWeight = mft is null ? 1.0 : 0.65;
|
||
long reportTicks = Environment.TickCount64;
|
||
|
||
// 输入按参考实现取 [FirstUsn, NextUsn]；若一条都没枚举到（日志刚建好、区间过窄等），
|
||
// 再退一次 [0, MAXLONGLONG] 全量范围 —— 那条路径必然能拿到整个 MFT。
|
||
long lowUsn = hasJournal ? journal.FirstUsn : 0;
|
||
long highUsn = hasJournal ? journal.NextUsn : long.MaxValue;
|
||
|
||
long visited = EnumMft(handle, lowUsn, highUsn, estimated, cancellationToken, progress, enumWeight, ref reportTicks,
|
||
(ReadOnlySpan<char> name, ulong frn, ulong parent, uint attributes, long timeStamp) =>
|
||
{
|
||
bool isDir = (attributes & UsnNative.FILE_ATTRIBUTE_DIRECTORY) != 0;
|
||
int idx = AppendEntry(ref store, frn, parent, name, isDir,
|
||
isDir ? 0 : -1, FileTimeToTicks(timeStamp), attributes);
|
||
map.AddBuild(frn, idx);
|
||
live++;
|
||
});
|
||
|
||
if (visited == 0 && (lowUsn != 0 || highUsn != long.MaxValue))
|
||
{
|
||
degradedNote = "USN 区间 [FirstUsn, NextUsn] 未枚举到记录，已改用 [0, MAXLONGLONG] 全量枚举";
|
||
visited = EnumMft(handle, 0, long.MaxValue, estimated, cancellationToken, progress, enumWeight, ref reportTicks,
|
||
(ReadOnlySpan<char> name, ulong frn, ulong parent, uint attributes, long timeStamp) =>
|
||
{
|
||
bool isDir = (attributes & UsnNative.FILE_ATTRIBUTE_DIRECTORY) != 0;
|
||
int idx = AppendEntry(ref store, frn, parent, name, isDir,
|
||
isDir ? 0 : -1, FileTimeToTicks(timeStamp), attributes);
|
||
map.AddBuild(frn, idx);
|
||
live++;
|
||
});
|
||
}
|
||
|
||
progress?.Report(enumWeight);
|
||
|
||
// ---- 6) 用原始 MFT 给每条记录补齐真实大小/时间/属性 ----
|
||
if (mft is not null)
|
||
{
|
||
long totalBytes = mft.MftValidDataLength;
|
||
mft.Enumerate(
|
||
(ulong recordNumber, Span<byte> record) =>
|
||
{
|
||
if (!MftReader.TryParseRecord(record, mft.BytesPerSector, out var info)) return;
|
||
if (!info.InUse) return;
|
||
if (!map.TryGet(recordNumber, out int idx)) return;
|
||
if ((uint)idx >= (uint)store.Count) return;
|
||
|
||
store.ModifiedTicks[idx] = FileTimeToTicks(info.ModifiedFileTime);
|
||
store.Attributes[idx] = info.Attributes;
|
||
if (info.IsDirectory) store.Size[idx] = 0;
|
||
else if (info.Size >= 0) store.Size[idx] = info.Size;
|
||
},
|
||
totalBytes,
|
||
bytesRead =>
|
||
{
|
||
long now = Environment.TickCount64;
|
||
if (now - reportTicks < 60) return;
|
||
reportTicks = now;
|
||
double ratio = totalBytes > 0 ? Math.Min(1d, (double)bytesRead / totalBytes) : 0d;
|
||
progress?.Report(enumWeight + (1d - enumWeight) * ratio);
|
||
},
|
||
cancellationToken);
|
||
}
|
||
|
||
// ---- 7) 发布新快照 ----
|
||
// 注意发布顺序：先写 _frnMap（release），最后才用 volatile 写 _store 作为整批数据的发布点。
|
||
map.Optimize();
|
||
lock (_gate)
|
||
{
|
||
Volatile.Write(ref _frnMap, map);
|
||
Volatile.Write(ref _liveCount, live);
|
||
_mftReader = mft;
|
||
_changeCount = 0;
|
||
Volatile.Write(ref _store, store);
|
||
}
|
||
_dirPathCache.Clear();
|
||
|
||
if (degradedNote is not null)
|
||
{
|
||
DegradationReason = DegradationReason is null ? degradedNote : $"{DegradationReason}；{degradedNote}";
|
||
}
|
||
|
||
progress?.Report(1d);
|
||
|
||
string summary = mft is null
|
||
? $"索引完成：{live:N0} 项（USN 降级模式，文件大小未知）。"
|
||
: $"索引完成：{live:N0} 项（已解析原始 MFT，大小/时间精确）。";
|
||
SetState(IndexState.Ready, summary);
|
||
|
||
// ---- 8) 构建前就调用过 StartWatching() 的话，这里补上 ----
|
||
// 注意：无论日志是否可用都要起监听线程 —— 线程内部会在日志不可用时回退到 ReadDirectoryChangesW。
|
||
if (_watchRequested) StartWatchThread();
|
||
}
|
||
catch (OperationCanceledException)
|
||
{
|
||
SetState(IndexState.Stopped, "索引构建已取消。");
|
||
}
|
||
catch (VolumeAccessException ex)
|
||
{
|
||
// 卷句柄能打开、但 FSCTL 被拒：同样是权限问题（非管理员下内核返回 INVALID_FUNCTION）
|
||
DegradationReason = ex.Message;
|
||
SetState(IndexState.RequiresElevation,
|
||
"读取 NTFS 主文件表需要管理员权限，可点击以管理员身份重启索引服务。");
|
||
}
|
||
catch (Exception ex)
|
||
{
|
||
DegradationReason = ex.Message;
|
||
SetState(IndexState.Failed, $"{_volumeRoot} 索引构建失败：{ex.Message}");
|
||
}
|
||
}
|
||
|
||
/// <summary>FSCTL_ENUM_USN_DATA 主循环：按 StartFileReferenceNumber 递增游标直到 ERROR_HANDLE_EOF。</summary>
|
||
private long EnumMft(
|
||
SafeFileHandle handle,
|
||
long lowUsn,
|
||
long highUsn,
|
||
int estimatedRecords,
|
||
CancellationToken cancellationToken,
|
||
IProgress<double>? progress,
|
||
double weight,
|
||
ref long reportTicks,
|
||
EnumSink sink)
|
||
{
|
||
// MFT_ENUM_DATA_V0{ StartFileReferenceNumber = 0, LowUsn = ujd.FirstUsn, HighUsn = ujd.NextUsn }
|
||
var input = new UsnNative.MftEnumDataV0
|
||
{
|
||
StartFileReferenceNumber = 0,
|
||
LowUsn = lowUsn,
|
||
HighUsn = highUsn
|
||
};
|
||
var inBuffer = new byte[Marshal.SizeOf<UsnNative.MftEnumDataV0>()];
|
||
var outBuffer = new byte[EnumBufferSize];
|
||
long visited = 0;
|
||
|
||
while (true)
|
||
{
|
||
cancellationToken.ThrowIfCancellationRequested();
|
||
|
||
WriteStruct(inBuffer, in input);
|
||
if (!UsnNative.Ioctl(handle, UsnNative.FSCTL_ENUM_USN_DATA, inBuffer, outBuffer, out int bytesReturned))
|
||
{
|
||
int error = Marshal.GetLastWin32Error();
|
||
// 枚举到尾时内核返回 ERROR_HANDLE_EOF，属于正常结束，不是错误
|
||
if (error == UsnNative.ERROR_HANDLE_EOF) break;
|
||
throw new VolumeAccessException(error, UsnNative.DescribeError(error, "FSCTL_ENUM_USN_DATA 枚举 MFT 失败"));
|
||
}
|
||
|
||
// 输出缓冲最开头的 8 字节就是下一页游标（ulong），记录数据从 +8 处开始
|
||
if (bytesReturned <= 8) break;
|
||
ulong nextStart = BinaryPrimitives.ReadUInt64LittleEndian(outBuffer);
|
||
ParseEnumBuffer(outBuffer.AsSpan(8, bytesReturned - 8), sink, ref visited);
|
||
|
||
if (nextStart == 0 || nextStart == input.StartFileReferenceNumber) break;
|
||
input.StartFileReferenceNumber = nextStart;
|
||
|
||
long now = Environment.TickCount64;
|
||
if (now - reportTicks >= 60)
|
||
{
|
||
reportTicks = now;
|
||
double ratio = estimatedRecords > 0 ? Math.Min(1d, (double)visited / estimatedRecords) : 0d;
|
||
progress?.Report(weight * ratio);
|
||
}
|
||
}
|
||
|
||
progress?.Report(weight);
|
||
return visited;
|
||
}
|
||
|
||
/// <summary>FSCTL_ENUM_USN_DATA 输出缓冲解析回调（internal 以便被合成数据集测试直接驱动）。</summary>
|
||
internal delegate void EnumSink(ReadOnlySpan<char> name, ulong frn, ulong parent, uint attributes, long timeStamp);
|
||
|
||
internal static void ParseEnumBuffer(ReadOnlySpan<byte> records, EnumSink sink, ref long visited)
|
||
{
|
||
int offset = 0;
|
||
while (offset + UsnNative.UsnRecordV2.Size <= records.Length)
|
||
{
|
||
var header = MemoryMarshal.Read<UsnNative.UsnRecordV2>(records[offset..]);
|
||
int recordLength = (int)header.RecordLength;
|
||
if (recordLength < UsnNative.UsnRecordV2.Size || offset + recordLength > records.Length) break;
|
||
|
||
visited++;
|
||
// USN_RECORD_V2 之外（V3/V4）在 NTFS 卷上不会出现；这里只处理 V2
|
||
if (header.MajorVersion == 2
|
||
&& header.FileNameLength > 0
|
||
&& header.FileNameOffset + header.FileNameLength <= recordLength)
|
||
{
|
||
var name = MemoryMarshal.Cast<byte, char>(
|
||
records.Slice(offset + header.FileNameOffset, header.FileNameLength));
|
||
// 卷根目录的名字是 "."，父目录自指，入索引没有意义
|
||
if (!(name.Length == 1 && name[0] == '.'))
|
||
{
|
||
sink(name,
|
||
UsnNative.NormalizeFrn(header.FileReferenceNumber),
|
||
UsnNative.NormalizeFrn(header.ParentFileReferenceNumber),
|
||
header.FileAttributes,
|
||
header.TimeStamp);
|
||
}
|
||
}
|
||
|
||
offset += recordLength;
|
||
}
|
||
}
|
||
|
||
// ================================================================ 增量监听
|
||
|
||
private void StartWatchThread()
|
||
{
|
||
lock (_gate)
|
||
{
|
||
if (_disposed) return;
|
||
if (_watchThread is { IsAlive: true }) return;
|
||
_stopRequested = false;
|
||
var thread = new Thread(WatchLoop)
|
||
{
|
||
IsBackground = true,
|
||
Name = $"UsnWatch[{_volumeRoot}]",
|
||
Priority = ThreadPriority.BelowNormal
|
||
};
|
||
_watchThread = thread;
|
||
thread.Start();
|
||
}
|
||
}
|
||
|
||
/// <summary>
|
||
/// FSCTL_READ_USN_JOURNAL 阻塞式循环。BytesToWaitFor=64KB 让内核攒够一批再唤醒，
|
||
/// 每次唤醒只处理一个批次，改完一次性触发 StateChanged(Watching)。
|
||
/// </summary>
|
||
private void WatchLoop()
|
||
{
|
||
SafeFileHandle? handle = null;
|
||
try
|
||
{
|
||
_watchThreadHandle = UsnNative.OpenThread(UsnNative.THREAD_TERMINATE, false, UsnNative.GetCurrentThreadId());
|
||
|
||
var (opened, _, openError) = OpenVolumeWithBestAccess();
|
||
handle = opened;
|
||
bool needFallback;
|
||
if (handle is null)
|
||
{
|
||
ReportWatchIssue($"无法打开卷句柄用于增量监听（{UsnNative.DescribeError(openError)}），改用 ReadDirectoryChangesW 回退监听。");
|
||
needFallback = true;
|
||
}
|
||
else
|
||
{
|
||
Volatile.Write(ref _watchHandle, handle);
|
||
// 日志不存在就尝试创建（需要管理员）；拿不到就回退
|
||
if (EnsureUsnJournal(handle, out var journal, out int journalError, out bool created))
|
||
{
|
||
if (created)
|
||
{
|
||
ReportWatchIssue("本卷原先没有 USN 变更日志，已按系统默认大小创建（不会自动删除）以便做增量监听。");
|
||
}
|
||
needFallback = RunUsnJournalLoop(handle, in journal);
|
||
}
|
||
else
|
||
{
|
||
ReportWatchIssue($"USN 变更日志不可用（{UsnNative.DescribeError(journalError)}），改用 ReadDirectoryChangesW 回退监听。");
|
||
needFallback = true;
|
||
}
|
||
}
|
||
|
||
if (needFallback && !_stopRequested) RunDirectoryChangesLoop();
|
||
}
|
||
catch (Exception ex)
|
||
{
|
||
if (!_stopRequested) SetState(IndexState.Ready, $"实时监听异常退出：{ex.Message}");
|
||
}
|
||
finally
|
||
{
|
||
var watchHandle = Interlocked.Exchange(ref _watchHandle, null);
|
||
watchHandle?.Dispose();
|
||
handle?.Dispose();
|
||
var threadHandle = Interlocked.Exchange(ref _watchThreadHandle, IntPtr.Zero);
|
||
if (threadHandle != IntPtr.Zero) UsnNative.CloseHandle(threadHandle);
|
||
}
|
||
}
|
||
|
||
/// <summary>
|
||
/// FSCTL_READ_USN_JOURNAL 阻塞循环。返回 true 表示「USN 通道不可用，请回退到 RDCW」；
|
||
/// false 表示正常收到停止信号退出。
|
||
/// </summary>
|
||
private bool RunUsnJournalLoop(SafeFileHandle handle, in UsnNative.UsnJournalDataV0 journal)
|
||
{
|
||
var read = new UsnNative.ReadUsnJournalDataV0
|
||
{
|
||
StartUsn = journal.NextUsn,
|
||
ReasonMask = UsnNative.USN_REASON_ANY,
|
||
ReturnOnlyOnClose = 0,
|
||
Timeout = 0, // 0 = 无数据时无限等待，靠 CancelSynchronousIo 打断
|
||
BytesToWaitFor = WatchBytesToWaitFor,
|
||
UsnJournalID = journal.UsnJournalID
|
||
};
|
||
|
||
var inBuffer = new byte[Marshal.SizeOf<UsnNative.ReadUsnJournalDataV0>()];
|
||
var outBuffer = new byte[WatchBufferSize];
|
||
WatchMode = IndexWatchMode.UsnJournal;
|
||
SetState(IndexState.Watching, $"{_volumeRoot} 索引已就绪，正在通过 USN 日志实时监听文件变更。");
|
||
|
||
while (!_stopRequested)
|
||
{
|
||
WriteStruct(inBuffer, in read);
|
||
bool ok = UsnNative.Ioctl(handle, UsnNative.FSCTL_READ_USN_JOURNAL, inBuffer, outBuffer, out int bytesReturned);
|
||
if (!ok)
|
||
{
|
||
int error = Marshal.GetLastWin32Error();
|
||
if (_stopRequested
|
||
|| error is UsnNative.ERROR_OPERATION_ABORTED or UsnNative.ERROR_CANCELLED or UsnNative.ERROR_INVALID_HANDLE)
|
||
{
|
||
return false;
|
||
}
|
||
// 日志被删除/重建：重新确保日志可用后继续（期间可能漏掉少量变更，重建索引可修正）
|
||
if (error is UsnNative.ERROR_JOURNAL_DELETE_IN_PROGRESS
|
||
or UsnNative.ERROR_JOURNAL_NOT_ACTIVE
|
||
or UsnNative.ERROR_JOURNAL_ENTRY_DELETED)
|
||
{
|
||
if (!EnsureUsnJournal(handle, out var refreshed, out _, out _))
|
||
{
|
||
ReportWatchIssue("USN 日志已被删除且无法重新获取，改用 ReadDirectoryChangesW 回退监听。");
|
||
return true;
|
||
}
|
||
read.StartUsn = refreshed.FirstUsn;
|
||
read.UsnJournalID = refreshed.UsnJournalID;
|
||
continue;
|
||
}
|
||
ReportWatchIssue($"USN 实时监听中断（{UsnNative.DescribeError(error)}），改用 ReadDirectoryChangesW 回退监听。");
|
||
return true;
|
||
}
|
||
|
||
if (bytesReturned <= 8) continue;
|
||
read.StartUsn = BinaryPrimitives.ReadInt64LittleEndian(outBuffer);
|
||
int applied = ApplyChanges(outBuffer.AsSpan(8, bytesReturned - 8));
|
||
if (applied > 0)
|
||
{
|
||
Interlocked.Add(ref _changeCount, applied);
|
||
SetState(IndexState.Watching, $"{_volumeRoot} 索引已更新（{applied} 条变更）。");
|
||
}
|
||
}
|
||
|
||
return false;
|
||
}
|
||
|
||
/// <summary>ReadDirectoryChangesW 回退监听（不需要 USN 日志权限）。</summary>
|
||
private void RunDirectoryChangesLoop()
|
||
{
|
||
var watcher = new DirectoryChangeWatcher(this);
|
||
if (!watcher.TryOpen(out var error))
|
||
{
|
||
WatchMode = IndexWatchMode.None;
|
||
SetState(IndexState.Ready, $"实时监听不可用：{error}");
|
||
return;
|
||
}
|
||
|
||
_directoryWatcher = watcher;
|
||
WatchMode = IndexWatchMode.DirectoryChanges;
|
||
SetState(IndexState.Watching,
|
||
$"{_volumeRoot} 索引已就绪（USN 日志不可用，回退为 ReadDirectoryChangesW 实时监听）。");
|
||
try
|
||
{
|
||
watcher.Run();
|
||
}
|
||
finally
|
||
{
|
||
_directoryWatcher = null;
|
||
}
|
||
|
||
if (!_stopRequested)
|
||
{
|
||
WatchMode = IndexWatchMode.None;
|
||
SetState(IndexState.Ready, "实时监听已停止。");
|
||
}
|
||
}
|
||
|
||
/// <summary>应用一批 USN 变更记录，返回处理条数（internal 以便被合成数据集测试直接驱动）。</summary>
|
||
internal int ApplyChanges(ReadOnlySpan<byte> records)
|
||
{
|
||
int offset = 0;
|
||
int applied = 0;
|
||
while (offset + UsnNative.UsnRecordV2.Size <= records.Length)
|
||
{
|
||
var header = MemoryMarshal.Read<UsnNative.UsnRecordV2>(records[offset..]);
|
||
int recordLength = (int)header.RecordLength;
|
||
if (recordLength < UsnNative.UsnRecordV2.Size || offset + recordLength > records.Length) break;
|
||
|
||
if (header.MajorVersion == 2)
|
||
{
|
||
ReadOnlySpan<char> name = default;
|
||
if (header.FileNameLength > 0 && header.FileNameOffset + header.FileNameLength <= recordLength)
|
||
{
|
||
name = MemoryMarshal.Cast<byte, char>(
|
||
records.Slice(offset + header.FileNameOffset, header.FileNameLength));
|
||
}
|
||
ApplyOne(in header, name);
|
||
applied++;
|
||
}
|
||
offset += recordLength;
|
||
}
|
||
return applied;
|
||
}
|
||
|
||
private void ApplyOne(in UsnNative.UsnRecordV2 header, ReadOnlySpan<char> name)
|
||
{
|
||
ulong frn = UsnNative.NormalizeFrn(header.FileReferenceNumber);
|
||
ulong parent = UsnNative.NormalizeFrn(header.ParentFileReferenceNumber);
|
||
uint reason = header.Reason;
|
||
var store = Volatile.Read(ref _store);
|
||
bool exists = _frnMap.TryGet(frn, out int index) && (uint)index < (uint)store.Count;
|
||
|
||
// ---- 删除：打墓碑，不搬移数组 ----
|
||
if ((reason & UsnNative.USN_REASON_FILE_DELETE) != 0)
|
||
{
|
||
if (exists && (store.Flags[index] & IndexStore.FlagDeleted) == 0)
|
||
{
|
||
store.Flags[index] |= IndexStore.FlagDeleted;
|
||
Interlocked.Decrement(ref _liveCount);
|
||
}
|
||
return;
|
||
}
|
||
|
||
bool isDir = (header.FileAttributes & UsnNative.FILE_ATTRIBUTE_DIRECTORY) != 0;
|
||
|
||
if (!exists)
|
||
{
|
||
if (name.Length == 0) return;
|
||
index = AppendEntryThreadSafe(frn, parent, name, isDir,
|
||
isDir ? 0 : -1, FileTimeToTicks(header.TimeStamp), header.FileAttributes);
|
||
Interlocked.Increment(ref _liveCount);
|
||
RefreshFromDisk(frn, index);
|
||
return;
|
||
}
|
||
|
||
// ---- 改名 / 移动：就地改名字引用与父目录（NameRef 单次 8 字节原子写，读侧不会看到半新半旧）----
|
||
if (name.Length > 0)
|
||
{
|
||
var current = store.GetName(index);
|
||
if (!current.SequenceEqual(name))
|
||
{
|
||
if (name.Length > NamePool.MaxNameLength) name = name[..NamePool.MaxNameLength];
|
||
int nameOffset = store.Names.Add(name);
|
||
Volatile.Write(ref store.NameRef[index], NamePool.Pack(nameOffset, name.Length));
|
||
store.ParentFrn[index] = parent;
|
||
}
|
||
else if (store.ParentFrn[index] != parent)
|
||
{
|
||
store.ParentFrn[index] = parent;
|
||
}
|
||
}
|
||
|
||
// 复活：之前被标记删除的记录号又被新文件复用了
|
||
if ((store.Flags[index] & IndexStore.FlagDeleted) != 0 && (reason & UsnNative.USN_REASON_FILE_CREATE) != 0)
|
||
{
|
||
store.Flags[index] &= unchecked((byte)~IndexStore.FlagDeleted);
|
||
Interlocked.Increment(ref _liveCount);
|
||
}
|
||
|
||
RefreshFromDisk(frn, index);
|
||
}
|
||
|
||
/// <summary>用原始 MFT 刷新单个条目的大小/时间/属性；没有 MFT 时退化为用 USN 的变更时间。</summary>
|
||
private void RefreshFromDisk(ulong frn, int index)
|
||
{
|
||
var store = Volatile.Read(ref _store);
|
||
if ((uint)index >= (uint)store.Count) return;
|
||
|
||
var mft = _mftReader;
|
||
if (mft is null) return; // USN 降级模式：大小保持 -1（未知），时间已在创建/改名时写入
|
||
|
||
Span<byte> buffer = mft.BytesPerRecord <= 4096 ? stackalloc byte[4096] : new byte[mft.BytesPerRecord];
|
||
if (!mft.TryReadRecord(frn, buffer)) return;
|
||
if (!MftReader.TryParseRecord(buffer, mft.BytesPerSector, out var info)) return;
|
||
|
||
if (info.IsDirectory) store.Size[index] = 0;
|
||
else if (info.Size >= 0) store.Size[index] = info.Size;
|
||
if (info.ModifiedFileTime > 0) store.ModifiedTicks[index] = FileTimeToTicks(info.ModifiedFileTime);
|
||
if (info.Attributes != 0) store.Attributes[index] = info.Attributes;
|
||
}
|
||
|
||
// ================================================================ RDCW 回退通道的落地接口
|
||
|
||
/// <summary>
|
||
/// 由 <see cref="DirectoryChangeWatcher"/> 调用：按 FRN 写入/更新一条记录（RDCW 只有路径，FRN 来自句柄）。
|
||
/// </summary>
|
||
internal void UpsertFromFileSystem(ulong frn, ulong parentFrn, ReadOnlySpan<char> name,
|
||
bool isDirectory, long size, long modifiedTicks, uint attributes)
|
||
{
|
||
frn = UsnNative.NormalizeFrn(frn);
|
||
parentFrn = UsnNative.NormalizeFrn(parentFrn);
|
||
|
||
var store = Volatile.Read(ref _store);
|
||
if (_frnMap.TryGet(frn, out int index) && (uint)index < (uint)store.Count)
|
||
{
|
||
if (name.Length > 0)
|
||
{
|
||
var current = store.GetName(index);
|
||
if (!current.SequenceEqual(name))
|
||
{
|
||
if (name.Length > NamePool.MaxNameLength) name = name[..NamePool.MaxNameLength];
|
||
int nameOffset = store.Names.Add(name);
|
||
Volatile.Write(ref store.NameRef[index], NamePool.Pack(nameOffset, name.Length));
|
||
}
|
||
if (parentFrn != 0) store.ParentFrn[index] = parentFrn;
|
||
}
|
||
store.Size[index] = isDirectory ? 0 : size;
|
||
if (modifiedTicks > 0) store.ModifiedTicks[index] = modifiedTicks;
|
||
if (attributes != 0) store.Attributes[index] = attributes;
|
||
store.Flags[index] = (byte)((store.Flags[index] & IndexStore.FlagDeleted)
|
||
| (isDirectory ? IndexStore.FlagDirectory : 0));
|
||
|
||
// 记录号被复用：之前打的墓碑要撤掉
|
||
if ((store.Flags[index] & IndexStore.FlagDeleted) != 0)
|
||
{
|
||
store.Flags[index] &= unchecked((byte)~IndexStore.FlagDeleted);
|
||
Interlocked.Increment(ref _liveCount);
|
||
}
|
||
Interlocked.Increment(ref _changeCount);
|
||
return;
|
||
}
|
||
|
||
if (name.Length == 0) return;
|
||
AppendEntryThreadSafe(frn, parentFrn, name, isDirectory, isDirectory ? 0 : size, modifiedTicks, attributes);
|
||
Interlocked.Increment(ref _liveCount);
|
||
Interlocked.Increment(ref _changeCount);
|
||
}
|
||
|
||
/// <summary>
|
||
/// 由 <see cref="DirectoryChangeWatcher"/> 调用：对某个目录做「磁盘现状 vs 索引」对账，
|
||
/// 把索引里存在、磁盘上已消失的孩子打上墓碑。返回打墓碑的条数。
|
||
/// RDCW 的删除事件只给路径、无法反查 FRN，所以删除统一走这条对账路径。
|
||
/// </summary>
|
||
internal int ResyncDirectoryFromDisk(string directoryPath)
|
||
{
|
||
if (!UsnNative.TryStatPath(directoryPath, out var directoryInfo)) return 0;
|
||
ulong directoryFrn = UsnNative.NormalizeFrn(directoryInfo.FileIndex);
|
||
if (directoryFrn == 0) return 0;
|
||
|
||
HashSet<string> liveNames;
|
||
try
|
||
{
|
||
liveNames = new HashSet<string>(StringComparer.OrdinalIgnoreCase);
|
||
foreach (var entry in Directory.EnumerateFileSystemEntries(directoryPath))
|
||
{
|
||
var leaf = Path.GetFileName(entry);
|
||
if (leaf.Length > 0) liveNames.Add(leaf);
|
||
}
|
||
}
|
||
catch (IOException)
|
||
{
|
||
return 0;
|
||
}
|
||
catch (UnauthorizedAccessException)
|
||
{
|
||
return 0;
|
||
}
|
||
|
||
var store = Volatile.Read(ref _store);
|
||
int tombstoned = 0;
|
||
for (int i = 0; i < store.Count; i++)
|
||
{
|
||
if ((store.Flags[i] & IndexStore.FlagDeleted) != 0) continue;
|
||
if (store.ParentFrn[i] != directoryFrn) continue;
|
||
|
||
var name = store.GetName(i);
|
||
if (name.Length == 0) continue;
|
||
if (liveNames.Contains(name.ToString())) continue;
|
||
|
||
store.Flags[i] |= IndexStore.FlagDeleted;
|
||
Interlocked.Decrement(ref _liveCount);
|
||
Interlocked.Increment(ref _changeCount);
|
||
tombstoned++;
|
||
}
|
||
return tombstoned;
|
||
}
|
||
|
||
/// <summary>把监听通道的异常/进展以 StateChanged(Watching) 的形式抛给 UI。</summary>
|
||
internal void ReportWatchIssue(string? message, int tombstoned = 0)
|
||
{
|
||
if (message is null && tombstoned <= 0) return;
|
||
var text = message is null
|
||
? $"{_volumeRoot} 索引已更新（{tombstoned} 项删除）。"
|
||
: tombstoned > 0
|
||
? $"{message}（{tombstoned} 项删除）"
|
||
: message;
|
||
SetState(WatchMode == IndexWatchMode.None ? IndexState.Ready : IndexState.Watching, text);
|
||
}
|
||
|
||
private void StopWatchingInternal() {
|
||
_stopRequested = true;
|
||
Thread? thread;
|
||
lock (_gate)
|
||
{
|
||
thread = _watchThread;
|
||
_watchThread = null;
|
||
}
|
||
|
||
var threadHandle = _watchThreadHandle;
|
||
if (threadHandle != IntPtr.Zero) UsnNative.CancelSynchronousIo(threadHandle);
|
||
// 回退通道用的是目录句柄上的 ReadDirectoryChangesW，同样用 CancelSynchronousIo 打断，外加关句柄兜底
|
||
_directoryWatcher?.RequestStop();
|
||
|
||
if (thread is { IsAlive: true })
|
||
{
|
||
if (!thread.Join(1500))
|
||
{
|
||
// 兜底：CancelSynchronousIo 没生效时直接关掉卷句柄，让阻塞中的 DeviceIoControl 立刻失败返回
|
||
var watchHandle = Interlocked.Exchange(ref _watchHandle, null);
|
||
watchHandle?.Dispose();
|
||
UsnNative.CancelSynchronousIo(threadHandle);
|
||
thread.Join(1500);
|
||
}
|
||
}
|
||
}
|
||
|
||
// ================================================================ 查询
|
||
|
||
public IEnumerable<IndexedEntry> Query(SearchQuery query, int maxResults, CancellationToken cancellationToken)
|
||
{
|
||
ArgumentNullException.ThrowIfNull(query);
|
||
|
||
var store = Volatile.Read(ref _store);
|
||
int count = store.Count;
|
||
int k = maxResults > 0 ? maxResults : DefaultMaxResults;
|
||
|
||
if (count == 0) return [];
|
||
|
||
var spec = new QuerySpec(query);
|
||
|
||
// 并行分片：分片数按 CPU 核数放大，同时限制每片 Top-K 堆的总内存
|
||
int partitions = Math.Min(count, Math.Max(1, Environment.ProcessorCount * 4));
|
||
if (partitions > 1 && (long)k * partitions > 4_000_000L)
|
||
{
|
||
partitions = (int)Math.Max(1, 4_000_000L / k);
|
||
}
|
||
int chunk = (count + partitions - 1) / partitions;
|
||
|
||
var partials = new TopK?[partitions];
|
||
var options = new ParallelOptions
|
||
{
|
||
CancellationToken = cancellationToken,
|
||
MaxDegreeOfParallelism = Environment.ProcessorCount
|
||
};
|
||
|
||
Parallel.For(0, partitions, options, p =>
|
||
{
|
||
int start = p * chunk;
|
||
int end = Math.Min(count, start + chunk);
|
||
if (start >= end) return;
|
||
var top = new TopK(k);
|
||
for (int i = start; i < end; i++)
|
||
{
|
||
long key = Probe(store, i, in spec);
|
||
if (key >= 0) top.Add(key, i);
|
||
}
|
||
partials[p] = top;
|
||
});
|
||
|
||
var merged = new TopK(k);
|
||
foreach (var partial in partials)
|
||
{
|
||
partial?.DrainInto(merged);
|
||
}
|
||
|
||
var hits = merged.ToSortedArray();
|
||
var results = new List<IndexedEntry>(hits.Length);
|
||
foreach (var (key, index) in hits)
|
||
{
|
||
cancellationToken.ThrowIfCancellationRequested();
|
||
var entry = Materialize(store, index);
|
||
if (entry is not null) results.Add(entry.Value);
|
||
}
|
||
return results;
|
||
}
|
||
|
||
/// <summary>
|
||
/// 单条候选的过滤 + 打分。返回 >=0 的排序键（越小越好），-1 表示被过滤掉。
|
||
/// 过滤顺序刻意从最便宜的条件到最贵的：先看标志位/大小/时间，再做名字匹配，最后才解析路径。
|
||
/// </summary>
|
||
private long Probe(IndexStore store, int i, in QuerySpec spec)
|
||
{
|
||
byte flags = store.Flags[i];
|
||
if ((flags & IndexStore.FlagDeleted) != 0) return -1;
|
||
|
||
bool isDir = (flags & IndexStore.FlagDirectory) != 0;
|
||
if (spec.DirectoriesOnly && !isDir) return -1;
|
||
if (spec.FilesOnly && isDir) return -1;
|
||
|
||
long size = store.Size[i];
|
||
if (size >= 0)
|
||
{
|
||
// 注意：Size < 0 表示“未知”（USN 降级），必须放行，绝不能当成 0 字节
|
||
if (spec.MinSize != long.MinValue && size < spec.MinSize) return -1;
|
||
if (spec.MaxSize != long.MaxValue && size > spec.MaxSize) return -1;
|
||
}
|
||
|
||
long ticks = store.ModifiedTicks[i];
|
||
if (ticks > 0)
|
||
{
|
||
if (spec.ModifiedAfterTicks > 0 && ticks < spec.ModifiedAfterTicks) return -1;
|
||
if (spec.ModifiedBeforeTicks > 0 && ticks > spec.ModifiedBeforeTicks) return -1;
|
||
}
|
||
|
||
var name = store.GetName(i);
|
||
|
||
if (spec.Extensions.Length > 0 && !MatchExtension(name, spec.Extensions)) return -1;
|
||
if (spec.ExcludeExtensions.Length > 0 && MatchExtension(name, spec.ExcludeExtensions)) return -1;
|
||
|
||
string? path = null;
|
||
if (!MatchNameAll(name, in spec, out int rank))
|
||
{
|
||
// 名字没全中：只有允许整路径匹配时才付出解析路径的代价
|
||
if (!spec.MatchWholePath) return -1;
|
||
path = ResolveFullPath(i);
|
||
if (path is null || !MatchNameAll(path.AsSpan(), in spec, out rank)) return -1;
|
||
}
|
||
|
||
if (spec.PathFilter is not null)
|
||
{
|
||
path ??= ResolveFullPath(i);
|
||
if (path is null) return -1;
|
||
if (path.IndexOf(spec.PathFilter, StringComparison.OrdinalIgnoreCase) < 0) return -1;
|
||
}
|
||
|
||
return PackKey(rank, name.Length, i);
|
||
}
|
||
|
||
private static long PackKey(int rank, int nameLength, int index)
|
||
=> ((long)rank << 56) | ((long)Math.Min(nameLength, 0xFFFFFF) << 32) | (uint)index;
|
||
|
||
/// <summary>IncludeTerms / IncludeRegexLike 全部命中才算通过；rank 取最差的一档。</summary>
|
||
private static bool MatchNameAll(ReadOnlySpan<char> name, in QuerySpec spec, out int rank)
|
||
{
|
||
rank = 0;
|
||
var terms = spec.IncludeTerms;
|
||
for (int t = 0; t < terms.Length; t++)
|
||
{
|
||
int r = MatchLiteral(name, terms[t]);
|
||
if (r < 0) return false;
|
||
if (r > rank) rank = r;
|
||
}
|
||
|
||
var patterns = spec.Wildcards;
|
||
for (int t = 0; t < patterns.Length; t++)
|
||
{
|
||
var pattern = patterns[t];
|
||
if (!WildcardMatcher.IsMatch(name, pattern)) return false;
|
||
int r = WildcardRank(name, pattern);
|
||
if (r > rank) rank = r;
|
||
}
|
||
|
||
var excludes = spec.ExcludeTerms;
|
||
for (int t = 0; t < excludes.Length; t++)
|
||
{
|
||
if (name.IndexOf(excludes[t], StringComparison.OrdinalIgnoreCase) >= 0) return false;
|
||
}
|
||
|
||
return true;
|
||
}
|
||
|
||
/// <summary>字面量子串匹配并给出优先级：完全相等(0) > 前缀(1) > 词边界(2) > 普通子串(3)。</summary>
|
||
private static int MatchLiteral(ReadOnlySpan<char> name, string term)
|
||
{
|
||
int idx = name.IndexOf(term, StringComparison.OrdinalIgnoreCase);
|
||
if (idx < 0) return -1;
|
||
if (idx != 0) return !char.IsLetterOrDigit(name[idx - 1]) ? 2 : 3;
|
||
return name.Length == term.Length ? 0 : 1;
|
||
}
|
||
|
||
private static int WildcardRank(ReadOnlySpan<char> name, ReadOnlySpan<char> pattern)
|
||
{
|
||
var prefix = WildcardMatcher.LiteralPrefix(pattern);
|
||
if (prefix.Length == 0) return 3;
|
||
if (!name.StartsWith(prefix, StringComparison.OrdinalIgnoreCase)) return 3;
|
||
return name.Length == prefix.Length ? 0 : 1;
|
||
}
|
||
|
||
/// <summary>扩展名比较：忽略大小写，且允许查询侧不带点（"log" 与 ".LOG" 都算命中）。</summary>
|
||
private static bool MatchExtension(ReadOnlySpan<char> name, string[] extensions)
|
||
{
|
||
int dot = name.LastIndexOf('.');
|
||
if (dot <= 0 || dot == name.Length - 1) return false;
|
||
var extension = name[(dot + 1)..];
|
||
foreach (var candidate in extensions)
|
||
{
|
||
if (extension.Equals(candidate, StringComparison.OrdinalIgnoreCase)) return true;
|
||
}
|
||
return false;
|
||
}
|
||
|
||
private IndexedEntry? Materialize(IndexStore store, int index)
|
||
{
|
||
if ((uint)index >= (uint)store.Count) return null;
|
||
long nameRef = Volatile.Read(ref store.NameRef[index]);
|
||
var nameSpan = store.Names.Get(NamePool.UnpackOffset(nameRef), NamePool.UnpackLength(nameRef));
|
||
if (nameSpan.Length == 0) return null;
|
||
|
||
bool isDir = (store.Flags[index] & IndexStore.FlagDirectory) != 0;
|
||
long ticks = store.ModifiedTicks[index];
|
||
var modified = ticks > 0 ? new DateTime(ticks, DateTimeKind.Utc) : default;
|
||
|
||
return new IndexedEntry(
|
||
store.Frn[index],
|
||
store.ParentFrn[index],
|
||
nameSpan.ToString(),
|
||
isDir,
|
||
store.Size[index],
|
||
modified,
|
||
store.Attributes[index])
|
||
{
|
||
FullPath = ResolveFullPath(index)
|
||
};
|
||
}
|
||
|
||
// ================================================================ 路径解析
|
||
|
||
public bool TryResolvePath(ulong frn, out string fullPath)
|
||
{
|
||
fullPath = string.Empty;
|
||
if (!_frnMap.TryGet(frn, out int index)) return false;
|
||
var store = Volatile.Read(ref _store);
|
||
if ((uint)index >= (uint)store.Count) return false;
|
||
var path = ResolveFullPath(index);
|
||
if (path is null) return false;
|
||
fullPath = path;
|
||
return true;
|
||
}
|
||
|
||
/// <summary>条目 → 完整路径。父链缺失或 FRN==0 时以 <see cref="VolumeRoot"/> 终止；彻底失败返回 null。</summary>
|
||
private string? ResolveFullPath(int index)
|
||
{
|
||
var store = Volatile.Read(ref _store);
|
||
if ((uint)index >= (uint)store.Count) return null;
|
||
|
||
bool isDir = (store.Flags[index] & IndexStore.FlagDirectory) != 0;
|
||
if (isDir) return ResolveDirectoryPath(index);
|
||
|
||
var name = store.GetName(index);
|
||
if (name.Length == 0) return null;
|
||
|
||
ulong frn = store.Frn[index];
|
||
ulong parent = store.ParentFrn[index];
|
||
if (parent == 0 || parent == frn) return string.Concat(VolumeRoot, name);
|
||
if (!_frnMap.TryGet(parent, out int parentIndex) || (uint)parentIndex >= (uint)store.Count)
|
||
{
|
||
return string.Concat(VolumeRoot, name);
|
||
}
|
||
|
||
var directory = ResolveDirectoryPath(parentIndex);
|
||
return directory is null ? null : string.Concat(directory, name);
|
||
}
|
||
|
||
/// <summary>
|
||
/// 目录条目 → 以 '\' 结尾的完整路径。父链结果整体缓存（键是目录 FRN），
|
||
/// 上层目录一旦算过，子目录拼一次字符串即可 —— 这是路径过滤能保持毫秒级的关键。
|
||
/// </summary>
|
||
private string? ResolveDirectoryPath(int index)
|
||
{
|
||
var store = Volatile.Read(ref _store);
|
||
if ((uint)index >= (uint)store.Count) return null;
|
||
|
||
ulong startFrn = store.Frn[index];
|
||
if (_dirPathCache.TryGetValue(startFrn, out var cached))
|
||
{
|
||
return cached.Length == 0 ? null : cached;
|
||
}
|
||
|
||
List<int>? chain = null;
|
||
string? prefix = null;
|
||
int current = index;
|
||
|
||
for (int depth = 0; depth < MaxPathDepth; depth++)
|
||
{
|
||
ulong frn = store.Frn[current];
|
||
ulong parent = store.ParentFrn[current];
|
||
|
||
// 终止条件（三条，都不硬编码根 FRN）：
|
||
// (a) 父指向自身 —— NTFS 卷根（MFT 记录 5）的特征；
|
||
// (b) parent == 0（没有父）；
|
||
// (c) 父不在映射里（父已被删/记录号已复用）。
|
||
// 命中任一条就以卷符为前缀结束，并且当前这一层（卷根自己）不写进路径。
|
||
if (parent == 0 || parent == frn)
|
||
{
|
||
prefix = VolumeRoot;
|
||
break;
|
||
}
|
||
(chain ??= new List<int>(8)).Add(current);
|
||
|
||
if (_dirPathCache.TryGetValue(parent, out var parentPath))
|
||
{
|
||
if (parentPath.Length == 0)
|
||
{
|
||
CacheDirectoryPath(startFrn, string.Empty);
|
||
return null;
|
||
}
|
||
prefix = parentPath;
|
||
break;
|
||
}
|
||
if (!_frnMap.TryGet(parent, out int parentIndex) || (uint)parentIndex >= (uint)store.Count)
|
||
{
|
||
prefix = VolumeRoot; // 父项缺失 → 以卷根终止
|
||
break;
|
||
}
|
||
current = parentIndex;
|
||
}
|
||
|
||
if (prefix is null)
|
||
{
|
||
// 超过深度上限：父链成环或数据损坏
|
||
CacheDirectoryPath(startFrn, string.Empty);
|
||
return null;
|
||
}
|
||
|
||
var builder = new StringBuilder(prefix, prefix.Length + chain!.Count * 16);
|
||
for (int i = chain.Count - 1; i >= 0; i--)
|
||
{
|
||
var segment = store.GetName(chain[i]);
|
||
if (segment.Length == 0) continue;
|
||
// 卷根目录在枚举里可能叫 "."（也可能是卷标），两种都不应该出现在路径里
|
||
if (segment.Length == 1 && segment[0] == '.') continue;
|
||
if (segment.Length == 2 && segment[0] == '.' && segment[1] == '.') continue;
|
||
builder.Append(segment).Append('\\');
|
||
}
|
||
|
||
var path = builder.ToString();
|
||
CacheDirectoryPath(startFrn, path);
|
||
return path;
|
||
}
|
||
|
||
private void CacheDirectoryPath(ulong frn, string path)
|
||
{
|
||
if (_dirPathCache.Count >= MaxPathCacheEntries) _dirPathCache.Clear();
|
||
_dirPathCache[frn] = path;
|
||
}
|
||
|
||
// ================================================================ 卷 / 日志
|
||
|
||
/// <summary>
|
||
/// 打开卷句柄。
|
||
///
|
||
/// 首选参数严格按参考实现（Everything）来：
|
||
/// CreateFileW(@"\\.\C:", GENERIC_READ|GENERIC_WRITE,
|
||
/// FILE_SHARE_READ|FILE_SHARE_WRITE, null, OPEN_EXISTING, FILE_ATTRIBUTE_READONLY, null)
|
||
/// —— 共享模式必须带 FILE_SHARE_WRITE；dwFlagsAndAttributes 用 FILE_ATTRIBUTE_READONLY（NORMAL 反而可能开不了）。
|
||
///
|
||
/// 之后逐级降权重试是为了「非管理员也能跑」：普通用户开不了读写卷句柄，
|
||
/// 但常常仍能拿到 FILE_READ_ATTRIBUTES 的句柄，从而完成 MFT 枚举（只是读不了原始数据 → 大小未知）。
|
||
/// </summary>
|
||
private (SafeFileHandle? Handle, uint Access, int Error) OpenVolumeWithBestAccess()
|
||
{
|
||
ReadOnlySpan<uint> accesses =
|
||
[
|
||
UsnNative.GENERIC_READ | UsnNative.GENERIC_WRITE,
|
||
UsnNative.GENERIC_READ,
|
||
UsnNative.FILE_READ_DATA | UsnNative.FILE_READ_ATTRIBUTES,
|
||
UsnNative.FILE_READ_ATTRIBUTES,
|
||
0
|
||
];
|
||
|
||
const uint share = UsnNative.FILE_SHARE_READ | UsnNative.FILE_SHARE_WRITE | UsnNative.FILE_SHARE_DELETE;
|
||
const uint flags = UsnNative.FILE_ATTRIBUTE_READONLY;
|
||
|
||
int lastError = 0;
|
||
foreach (var access in accesses)
|
||
{
|
||
var handle = UsnNative.CreateFileW(
|
||
_devicePath, access, share, IntPtr.Zero, UsnNative.OPEN_EXISTING, flags, IntPtr.Zero);
|
||
|
||
if (!handle.IsInvalid) return (handle, access, 0);
|
||
lastError = Marshal.GetLastWin32Error();
|
||
handle.Dispose();
|
||
}
|
||
|
||
return (null, 0, lastError);
|
||
}
|
||
|
||
private static bool QueryNtfsVolumeData(SafeFileHandle handle, out UsnNative.NtfsVolumeDataBuffer data, out int error)
|
||
{
|
||
data = default;
|
||
var buffer = new byte[Marshal.SizeOf<UsnNative.NtfsVolumeDataBuffer>()];
|
||
if (UsnNative.Ioctl(handle, UsnNative.FSCTL_GET_NTFS_VOLUME_DATA, [], buffer, out int bytes) && bytes >= buffer.Length)
|
||
{
|
||
data = MemoryMarshal.Read<UsnNative.NtfsVolumeDataBuffer>(buffer);
|
||
error = 0;
|
||
return true;
|
||
}
|
||
error = Marshal.GetLastWin32Error();
|
||
return false;
|
||
}
|
||
|
||
private static bool QueryUsnJournal(SafeFileHandle handle, out UsnNative.UsnJournalDataV0 journal, out int error)
|
||
{
|
||
journal = default;
|
||
var buffer = new byte[Marshal.SizeOf<UsnNative.UsnJournalDataV0>()];
|
||
if (UsnNative.Ioctl(handle, UsnNative.FSCTL_QUERY_USN_JOURNAL, [], buffer, out int bytes) && bytes >= buffer.Length)
|
||
{
|
||
journal = MemoryMarshal.Read<UsnNative.UsnJournalDataV0>(buffer);
|
||
error = 0;
|
||
return journal.UsnJournalID != 0;
|
||
}
|
||
error = Marshal.GetLastWin32Error();
|
||
return false;
|
||
}
|
||
|
||
/// <summary>
|
||
/// 确保卷上有 USN 变更日志可用：先 QUERY，拿不到（ERROR_JOURNAL_NOT_ACTIVE / ERROR_INVALID_FUNCTION 等）
|
||
/// 就尝试 FSCTL_CREATE_USN_JOURNAL 创建（MaximumSize/AllocationDelta 传 0 = 用系统默认值）。
|
||
///
|
||
/// 重要约定：**创建后绝不自动删除**（删掉就再也没法做增量监听了）。
|
||
/// 只有调用方显式调用 <see cref="DeleteUsnJournal"/> 才会删，且 DeleteFlags 用 USN_DELETE_FLAG_DELETE。
|
||
/// </summary>
|
||
private bool EnsureUsnJournal(SafeFileHandle handle, out UsnNative.UsnJournalDataV0 journal, out int error, out bool created)
|
||
{
|
||
created = false;
|
||
if (QueryUsnJournal(handle, out journal, out error)) return true;
|
||
if (!CreateJournalIfMissing) return false;
|
||
|
||
// 创建日志是需要管理员权限的操作；失败时把错误码原样带回给调用方分类
|
||
var input = new byte[Marshal.SizeOf<UsnNative.CreateUsnJournalData>()];
|
||
WriteStruct(input, new UsnNative.CreateUsnJournalData { MaximumSize = 0, AllocationDelta = 0 });
|
||
var output = new byte[16]; // 该 FSCTL 无输出，给个非空缓冲更保守
|
||
if (!UsnNative.Ioctl(handle, UsnNative.FSCTL_CREATE_USN_JOURNAL, input, output, out _))
|
||
{
|
||
error = Marshal.GetLastWin32Error();
|
||
return false;
|
||
}
|
||
|
||
created = true;
|
||
return QueryUsnJournal(handle, out journal, out error);
|
||
}
|
||
|
||
/// <summary>
|
||
/// 显式删除本卷的 USN 变更日志（DeleteFlags = USN_DELETE_FLAG_DELETE）。
|
||
/// 只有「用户主动关闭本卷索引并愿意放弃增量能力」时才调用；内部任何流程都不会自动调用它。
|
||
/// </summary>
|
||
public bool DeleteUsnJournal()
|
||
{
|
||
var (handle, _, _) = OpenVolumeWithBestAccess();
|
||
if (handle is null) return false;
|
||
try
|
||
{
|
||
if (!QueryUsnJournal(handle, out var journal, out _)) return false;
|
||
var input = new byte[Marshal.SizeOf<UsnNative.DeleteUsnJournalData>()];
|
||
WriteStruct(input, new UsnNative.DeleteUsnJournalData
|
||
{
|
||
UsnJournalID = journal.UsnJournalID,
|
||
DeleteFlags = UsnNative.USN_DELETE_FLAG_DELETE
|
||
});
|
||
var output = new byte[16];
|
||
return UsnNative.Ioctl(handle, UsnNative.FSCTL_DELETE_USN_JOURNAL, input, output, out _);
|
||
}
|
||
finally
|
||
{
|
||
handle.Dispose();
|
||
}
|
||
}
|
||
|
||
/// <summary>通过 FSCTL_GET_NTFS_FILE_RECORD 直接取一条 MFT 记录（备用通道，不依赖 ReadFile 权限）。</summary>
|
||
internal static bool TryGetNtfsFileRecord(SafeFileHandle handle, ulong recordNumber, byte[] buffer, out int recordLength)
|
||
{
|
||
recordLength = 0;
|
||
var input = new byte[Marshal.SizeOf<UsnNative.NtfsFileRecordInputBuffer>()];
|
||
WriteStruct(input, new UsnNative.NtfsFileRecordInputBuffer
|
||
{
|
||
FileReferenceNumber = UsnNative.NormalizeFrn(recordNumber)
|
||
});
|
||
if (!UsnNative.Ioctl(handle, UsnNative.FSCTL_GET_NTFS_FILE_RECORD, input, buffer, out int bytes)) return false;
|
||
if (bytes < Marshal.SizeOf<UsnNative.NtfsFileRecordOutputBuffer>()) return false;
|
||
recordLength = (int)BinaryPrimitives.ReadUInt32LittleEndian(buffer.AsSpan(8));
|
||
return recordLength > 0;
|
||
}
|
||
|
||
// ================================================================ 工具
|
||
|
||
private static unsafe void WriteStruct<T>(byte[] buffer, in T value) where T : unmanaged
|
||
{
|
||
fixed (byte* p = buffer)
|
||
{
|
||
*(T*)p = value;
|
||
}
|
||
}
|
||
|
||
/// <summary>
|
||
/// 追加一条记录；容量不足时 copy-on-write 扩容。返回新下标（扩容后 store 引用可能被替换，故用 ref）。
|
||
/// 名字池始终取自 store.Names —— 绝不能让“写名字的池”和“快照的池”变成两个对象。
|
||
/// </summary>
|
||
private static int AppendEntry(ref IndexStore store, ulong frn, ulong parent,
|
||
ReadOnlySpan<char> name, bool isDirectory, long size, long modifiedTicks, uint attributes)
|
||
{
|
||
if (store.Count >= store.Capacity) store = IndexStore.Grow(store, store.Count + 1);
|
||
if (name.Length > NamePool.MaxNameLength) name = name[..NamePool.MaxNameLength];
|
||
|
||
int index = store.Count;
|
||
int nameOffset = store.Names.Add(name);
|
||
|
||
store.Frn[index] = frn;
|
||
store.ParentFrn[index] = parent;
|
||
store.NameRef[index] = NamePool.Pack(nameOffset, name.Length);
|
||
store.Size[index] = size;
|
||
store.ModifiedTicks[index] = modifiedTicks;
|
||
store.Attributes[index] = attributes;
|
||
store.Flags[index] = isDirectory ? IndexStore.FlagDirectory : (byte)0;
|
||
|
||
// 最后才发布条数：保证读侧看到的下标一定已经写满字段
|
||
store.Count = index + 1;
|
||
return index;
|
||
}
|
||
|
||
private int AppendEntryThreadSafe(ulong frn, ulong parent, ReadOnlySpan<char> name,
|
||
bool isDirectory, long size, long modifiedTicks, uint attributes)
|
||
{
|
||
lock (_gate)
|
||
{
|
||
var store = Volatile.Read(ref _store);
|
||
int index = AppendEntry(ref store, frn, parent, name, isDirectory, size, modifiedTicks, attributes);
|
||
Volatile.Write(ref _store, store);
|
||
_frnMap.Set(frn, index);
|
||
return index;
|
||
}
|
||
}
|
||
|
||
private void SetState(IndexState state, string? message = null)
|
||
{
|
||
Volatile.Write(ref _state, (int)state);
|
||
var handler = StateChanged;
|
||
if (handler is null) return;
|
||
try
|
||
{
|
||
handler(this, new IndexStateChangedEventArgs(state, message));
|
||
}
|
||
catch
|
||
{
|
||
// UI 回调里的异常绝不能影响索引线程
|
||
}
|
||
}
|
||
|
||
/// <summary>FILETIME(1601-01-01 起) → .NET ticks(0001-01-01 起)；非法值一律变成 0（= 未知）。</summary>
|
||
internal static long FileTimeToTicks(long fileTime)
|
||
{
|
||
if (fileTime <= 0) return 0;
|
||
long ticks = fileTime + FileTimeToTicksOffset;
|
||
if (ticks < 0 || ticks > DateTime.MaxValue.Ticks) return 0;
|
||
return ticks;
|
||
}
|
||
|
||
/// <summary>查询侧时间边界 → UTC ticks（SearchQuery 里的日期都是本地时间语义）。</summary>
|
||
private static long ToUtcTicks(DateTime? value)
|
||
{
|
||
if (value is not { } date) return 0;
|
||
return date.Kind == DateTimeKind.Utc ? date.Ticks : date.ToUniversalTime().Ticks;
|
||
}
|
||
|
||
/// <summary>
|
||
/// 不带任何权限地用 DriveInfo 读出文件系统名（"NTFS"/"FAT32"/"exFAT"…）。
|
||
/// 关键作用：把“不是 NTFS”和“没有权限”这两种都会返回 ERROR_INVALID_FUNCTION 的情况区分开。
|
||
/// </summary>
|
||
private string? TryGetFileSystemName()
|
||
{
|
||
try
|
||
{
|
||
if (_volumeRoot.Length >= 2 && _volumeRoot[1] == ':') return new DriveInfo(_volumeRoot).DriveFormat;
|
||
}
|
||
catch (IOException)
|
||
{
|
||
return null;
|
||
}
|
||
catch (UnauthorizedAccessException)
|
||
{
|
||
return null;
|
||
}
|
||
return null;
|
||
}
|
||
|
||
private static (string Root, string Device) NormalizeVolumeRoot(string volumeRoot) {
|
||
ArgumentException.ThrowIfNullOrWhiteSpace(volumeRoot);
|
||
var text = volumeRoot.Trim();
|
||
|
||
// \\?\Volume{GUID}\ 形式：直接用它当设备路径
|
||
if (text.StartsWith(@"\\?\", StringComparison.Ordinal) || text.StartsWith(@"\\.\", StringComparison.Ordinal))
|
||
{
|
||
var device = text.TrimEnd('\\');
|
||
return (device + "\\", device);
|
||
}
|
||
|
||
var letter = char.ToUpperInvariant(text[0]);
|
||
if (letter is < 'A' or > 'Z')
|
||
{
|
||
throw new ArgumentException($"卷根必须是盘符形式（如 \"C:\\\"）或 \\\\?\\Volume{{GUID}}\\，收到：{volumeRoot}", nameof(volumeRoot));
|
||
}
|
||
return ($"{letter}:\\", $@"\\.\{letter}:");
|
||
}
|
||
|
||
// ================================================================ 查询预处理 / Top-K
|
||
|
||
/// <summary>把 SearchQuery 里每轮循环都要读的字段摊平，避免热路径上反复做属性/接口调用。</summary>
|
||
private readonly struct QuerySpec
|
||
{
|
||
internal readonly string[] IncludeTerms;
|
||
internal readonly string[] ExcludeTerms;
|
||
internal readonly string[] Wildcards;
|
||
internal readonly string[] Extensions;
|
||
internal readonly string[] ExcludeExtensions;
|
||
internal readonly string? PathFilter;
|
||
internal readonly bool MatchWholePath;
|
||
internal readonly bool DirectoriesOnly;
|
||
internal readonly bool FilesOnly;
|
||
internal readonly long MinSize;
|
||
internal readonly long MaxSize;
|
||
internal readonly long ModifiedAfterTicks;
|
||
internal readonly long ModifiedBeforeTicks;
|
||
|
||
internal QuerySpec(SearchQuery query)
|
||
{
|
||
IncludeTerms = [.. query.IncludeTerms];
|
||
ExcludeTerms = [.. query.ExcludeTerms];
|
||
Wildcards = [.. query.IncludeRegexLike];
|
||
Extensions = [.. query.Extensions];
|
||
ExcludeExtensions = [.. query.ExcludeExtensions];
|
||
PathFilter = string.IsNullOrEmpty(query.PathFilter) ? null : query.PathFilter;
|
||
MatchWholePath = query.MatchWholePath || PathFilter is not null;
|
||
DirectoriesOnly = query.DirectoriesOnly;
|
||
FilesOnly = query.FilesOnly;
|
||
MinSize = query.MinSize ?? long.MinValue;
|
||
MaxSize = query.MaxSize ?? long.MaxValue;
|
||
ModifiedAfterTicks = ToUtcTicks(query.ModifiedAfter);
|
||
ModifiedBeforeTicks = ToUtcTicks(query.ModifiedBefore);
|
||
// 说明：SearchQuery.CreatedAfter 无法参与过滤 —— IndexedEntry 没有创建时间字段
|
||
//（$STANDARD_INFORMATION 的创建时间只在原始 MFT 解析里拿得到），需要接口扩展才能支持。
|
||
}
|
||
}
|
||
|
||
/// <summary>卷句柄可用但 FSCTL 被内核拒绝（权限/非 NTFS），携带原始 Win32 错误码供上层分类。</summary>
|
||
private sealed class VolumeAccessException(int error, string message) : Exception(message)
|
||
{
|
||
internal int Error { get; } = error;
|
||
}
|
||
|
||
/// <summary>容量受限的最大堆：始终只保留“最好的” K 条。键越小越好，堆顶是当前最差的一条。</summary>
|
||
private sealed class TopK(int capacity)
|
||
{
|
||
private readonly long[] _keys = new long[Math.Max(1, capacity)];
|
||
private readonly int[] _indexes = new int[Math.Max(1, capacity)];
|
||
private int _count;
|
||
|
||
internal void Add(long key, int index)
|
||
{
|
||
if (_count < _keys.Length)
|
||
{
|
||
int i = _count++;
|
||
_keys[i] = key;
|
||
_indexes[i] = index;
|
||
SiftUp(i);
|
||
}
|
||
else if (key < _keys[0])
|
||
{
|
||
_keys[0] = key;
|
||
_indexes[0] = index;
|
||
SiftDown(0);
|
||
}
|
||
}
|
||
|
||
internal void DrainInto(TopK other)
|
||
{
|
||
for (int i = 0; i < _count; i++) other.Add(_keys[i], _indexes[i]);
|
||
}
|
||
|
||
internal (long Key, int Index)[] ToSortedArray()
|
||
{
|
||
var result = new (long, int)[_count];
|
||
for (int i = 0; i < _count; i++) result[i] = (_keys[i], _indexes[i]);
|
||
Array.Sort(result, static (a, b) => a.Item1.CompareTo(b.Item1));
|
||
return result;
|
||
}
|
||
|
||
private void SiftUp(int i)
|
||
{
|
||
while (i > 0)
|
||
{
|
||
int parent = (i - 1) >> 1;
|
||
if (_keys[parent] >= _keys[i]) break;
|
||
Swap(parent, i);
|
||
i = parent;
|
||
}
|
||
}
|
||
|
||
private void SiftDown(int i)
|
||
{
|
||
while (true)
|
||
{
|
||
int left = (i << 1) + 1;
|
||
if (left >= _count) return;
|
||
int largest = left;
|
||
int right = left + 1;
|
||
if (right < _count && _keys[right] > _keys[left]) largest = right;
|
||
if (_keys[i] >= _keys[largest]) return;
|
||
Swap(i, largest);
|
||
i = largest;
|
||
}
|
||
}
|
||
|
||
private void Swap(int a, int b)
|
||
{
|
||
(_keys[a], _keys[b]) = (_keys[b], _keys[a]);
|
||
(_indexes[a], _indexes[b]) = (_indexes[b], _indexes[a]);
|
||
}
|
||
}
|
||
}
|