using System;
using System.Collections.Generic;
using System.Diagnostics;
namespace Ryujinx.Graphics.Gpu.Shader.HashTable
{
///
/// Partitioned hash table.
///
///
public class PartitionedHashTable
{
///
/// Entry for a given data size.
///
private readonly struct SizeEntry
{
///
/// Size for the data that will be stored on the hash table on this entry.
///
public int Size { get; }
///
/// Number of entries on the hash table.
///
public int TableCount => _table.Count;
private readonly PartitionHashTable _table;
///
/// Creates an entry for a given size.
///
/// Size of the data to be stored on this entry
public SizeEntry(int size)
{
Size = size;
_table = new PartitionHashTable();
}
///
/// Gets an item for existing data, or adds a new one.
///
/// Data associated with the item
/// Hash of
/// Item to be added
/// Existing item, or if not present
public T GetOrAdd(byte[] data, uint dataHash, T item)
{
Debug.Assert(data.Length == Size);
return _table.GetOrAdd(data, dataHash, item);
}
///
/// Adds a new item.
///
/// Data associated with the item
/// Hash of
/// Item to be added
/// True if added, false otherwise
public bool Add(byte[] data, uint dataHash, T item)
{
Debug.Assert(data.Length == Size);
return _table.Add(data, dataHash, item);
}
///
/// Adds a partial entry.
///
/// Full entry data
/// Hash of the sub-region of the data that belongs to this entry
/// True if added, false otherwise
public bool AddPartial(byte[] ownerData, uint dataHash)
{
return _table.AddPartial(ownerData, dataHash, Size);
}
///
/// Fills a new hash table with "partials" of existing full entries of higher size.
///
/// Entry with the new hash table
public void FillPartials(SizeEntry newEntry)
{
Debug.Assert(newEntry.Size < Size);
_table.FillPartials(newEntry._table, newEntry.Size);
}
///
/// Tries to find an item on the hash table.
///
/// Data accessor
/// The item on the table, if found, otherwise unmodified
/// The data on the table, if found, otherwise unmodified
/// Table lookup result
public PartitionHashTable.SearchResult TryFindItem(scoped ref SmartDataAccessor dataAccessor, scoped ref T item, scoped ref byte[] data)
{
return _table.TryFindItem(ref dataAccessor, Size, ref item, ref data);
}
}
private readonly List _sizeTable;
///
/// Creates a new partitioned hash table.
///
public PartitionedHashTable()
{
_sizeTable = new List();
}
///
/// Adds a new item to the table.
///
/// Data
/// Item associated with the data
public void Add(byte[] data, T item)
{
GetOrAdd(data, item);
}
///
/// Gets an existing item from the table, or adds a new one if not present.
///
/// Data
/// Item associated with the data
/// Existing item, or if not present
public T GetOrAdd(byte[] data, T item)
{
SizeEntry sizeEntry;
int index = BinarySearch(_sizeTable, data.Length);
if (index < _sizeTable.Count && _sizeTable[index].Size == data.Length)
{
sizeEntry = _sizeTable[index];
}
else
{
if (index < _sizeTable.Count && _sizeTable[index].Size < data.Length)
{
index++;
}
sizeEntry = new SizeEntry(data.Length);
_sizeTable.Insert(index, sizeEntry);
for (int i = index + 1; i < _sizeTable.Count; i++)
{
_sizeTable[i].FillPartials(sizeEntry);
}
}
HashState hashState = new();
hashState.Initialize();
for (int i = 0; i < index; i++)
{
ReadOnlySpan dataSlice = new ReadOnlySpan(data)[.._sizeTable[i].Size];
hashState.Continue(dataSlice);
_sizeTable[i].AddPartial(data, hashState.Finalize(dataSlice));
}
hashState.Continue(data);
return sizeEntry.GetOrAdd(data, hashState.Finalize(data), item);
}
///
/// Performs binary search on a list of hash tables, each one with a fixed data size.
///
/// List of hash tables
/// Size to search for
/// Index of the hash table with the given size, or nearest one otherwise
private static int BinarySearch(List entries, int size)
{
int left = 0;
int middle = 0;
int right = entries.Count - 1;
while (left <= right)
{
middle = left + ((right - left) >> 1);
SizeEntry entry = entries[middle];
if (size == entry.Size)
{
break;
}
if (size < entry.Size)
{
right = middle - 1;
}
else
{
left = middle + 1;
}
}
return middle;
}
///
/// Tries to find an item on the table.
///
/// Data accessor
/// Item, if found
/// Data, if found
/// True if the item was found on the table, false otherwise
public bool TryFindItem(IDataAccessor dataAccessor, out T item, out byte[] data)
{
SmartDataAccessor sda = new(dataAccessor);
item = default;
data = null;
int left = 0;
int right = _sizeTable.Count;
while (left != right)
{
int index = left + ((right - left) >> 1);
PartitionHashTable.SearchResult result = _sizeTable[index].TryFindItem(ref sda, ref item, ref data);
if (result == PartitionHashTable.SearchResult.FoundFull)
{
return true;
}
if (result == PartitionHashTable.SearchResult.NotFound)
{
right = index;
}
else /* if (result == PartitionHashTable.SearchResult.FoundPartial) */
{
left = index + 1;
}
}
data = null;
return false;
}
}
}