1  using System;
  2  using System.Collections.Generic;
  3  using System.Diagnostics;
  4  
  5  namespace Ryujinx.Graphics.Gpu.Shader.HashTable
  6  {
  7      /// <summary>
  8      /// Partitioned hash table.
  9      /// </summary>
 10      /// <typeparam name="T"></typeparam>
 11      public class PartitionedHashTable<T>
 12      {
 13          /// <summary>
 14          /// Entry for a given data size.
 15          /// </summary>
 16          private readonly struct SizeEntry
 17          {
 18              /// <summary>
 19              /// Size for the data that will be stored on the hash table on this entry.
 20              /// </summary>
 21              public int Size { get; }
 22  
 23              /// <summary>
 24              /// Number of entries on the hash table.
 25              /// </summary>
 26              public int TableCount => _table.Count;
 27  
 28              private readonly PartitionHashTable<T> _table;
 29  
 30              /// <summary>
 31              /// Creates an entry for a given size.
 32              /// </summary>
 33              /// <param name="size">Size of the data to be stored on this entry</param>
 34              public SizeEntry(int size)
 35              {
 36                  Size = size;
 37                  _table = new PartitionHashTable<T>();
 38              }
 39  
 40              /// <summary>
 41              /// Gets an item for existing data, or adds a new one.
 42              /// </summary>
 43              /// <param name="data">Data associated with the item</param>
 44              /// <param name="dataHash">Hash of <paramref name="data"/></param>
 45              /// <param name="item">Item to be added</param>
 46              /// <returns>Existing item, or <paramref name="item"/> if not present</returns>
 47              public T GetOrAdd(byte[] data, uint dataHash, T item)
 48              {
 49                  Debug.Assert(data.Length == Size);
 50                  return _table.GetOrAdd(data, dataHash, item);
 51              }
 52  
 53              /// <summary>
 54              /// Adds a new item.
 55              /// </summary>
 56              /// <param name="data">Data associated with the item</param>
 57              /// <param name="dataHash">Hash of <paramref name="data"/></param>
 58              /// <param name="item">Item to be added</param>
 59              /// <returns>True if added, false otherwise</returns>
 60              public bool Add(byte[] data, uint dataHash, T item)
 61              {
 62                  Debug.Assert(data.Length == Size);
 63                  return _table.Add(data, dataHash, item);
 64              }
 65  
 66              /// <summary>
 67              /// Adds a partial entry.
 68              /// </summary>
 69              /// <param name="ownerData">Full entry data</param>
 70              /// <param name="dataHash">Hash of the sub-region of the data that belongs to this entry</param>
 71              /// <returns>True if added, false otherwise</returns>
 72              public bool AddPartial(byte[] ownerData, uint dataHash)
 73              {
 74                  return _table.AddPartial(ownerData, dataHash, Size);
 75              }
 76  
 77              /// <summary>
 78              /// Fills a new hash table with "partials" of existing full entries of higher size.
 79              /// </summary>
 80              /// <param name="newEntry">Entry with the new hash table</param>
 81              public void FillPartials(SizeEntry newEntry)
 82              {
 83                  Debug.Assert(newEntry.Size < Size);
 84                  _table.FillPartials(newEntry._table, newEntry.Size);
 85              }
 86  
 87              /// <summary>
 88              /// Tries to find an item on the hash table.
 89              /// </summary>
 90              /// <param name="dataAccessor">Data accessor</param>
 91              /// <param name="item">The item on the table, if found, otherwise unmodified</param>
 92              /// <param name="data">The data on the table, if found, otherwise unmodified</param>
 93              /// <returns>Table lookup result</returns>
 94              public PartitionHashTable<T>.SearchResult TryFindItem(scoped ref SmartDataAccessor dataAccessor, scoped ref T item, scoped ref byte[] data)
 95              {
 96                  return _table.TryFindItem(ref dataAccessor, Size, ref item, ref data);
 97              }
 98          }
 99  
100          private readonly List<SizeEntry> _sizeTable;
101  
102          /// <summary>
103          /// Creates a new partitioned hash table.
104          /// </summary>
105          public PartitionedHashTable()
106          {
107              _sizeTable = new List<SizeEntry>();
108          }
109  
110          /// <summary>
111          /// Adds a new item to the table.
112          /// </summary>
113          /// <param name="data">Data</param>
114          /// <param name="item">Item associated with the data</param>
115          public void Add(byte[] data, T item)
116          {
117              GetOrAdd(data, item);
118          }
119  
120          /// <summary>
121          /// Gets an existing item from the table, or adds a new one if not present.
122          /// </summary>
123          /// <param name="data">Data</param>
124          /// <param name="item">Item associated with the data</param>
125          /// <returns>Existing item, or <paramref name="item"/> if not present</returns>
126          public T GetOrAdd(byte[] data, T item)
127          {
128              SizeEntry sizeEntry;
129  
130              int index = BinarySearch(_sizeTable, data.Length);
131              if (index < _sizeTable.Count && _sizeTable[index].Size == data.Length)
132              {
133                  sizeEntry = _sizeTable[index];
134              }
135              else
136              {
137                  if (index < _sizeTable.Count && _sizeTable[index].Size < data.Length)
138                  {
139                      index++;
140                  }
141  
142                  sizeEntry = new SizeEntry(data.Length);
143  
144                  _sizeTable.Insert(index, sizeEntry);
145  
146                  for (int i = index + 1; i < _sizeTable.Count; i++)
147                  {
148                      _sizeTable[i].FillPartials(sizeEntry);
149                  }
150              }
151  
152              HashState hashState = new();
153              hashState.Initialize();
154  
155              for (int i = 0; i < index; i++)
156              {
157                  ReadOnlySpan<byte> dataSlice = new ReadOnlySpan<byte>(data)[.._sizeTable[i].Size];
158                  hashState.Continue(dataSlice);
159                  _sizeTable[i].AddPartial(data, hashState.Finalize(dataSlice));
160              }
161  
162              hashState.Continue(data);
163              return sizeEntry.GetOrAdd(data, hashState.Finalize(data), item);
164          }
165  
166          /// <summary>
167          /// Performs binary search on a list of hash tables, each one with a fixed data size.
168          /// </summary>
169          /// <param name="entries">List of hash tables</param>
170          /// <param name="size">Size to search for</param>
171          /// <returns>Index of the hash table with the given size, or nearest one otherwise</returns>
172          private static int BinarySearch(List<SizeEntry> entries, int size)
173          {
174              int left = 0;
175              int middle = 0;
176              int right = entries.Count - 1;
177  
178              while (left <= right)
179              {
180                  middle = left + ((right - left) >> 1);
181  
182                  SizeEntry entry = entries[middle];
183  
184                  if (size == entry.Size)
185                  {
186                      break;
187                  }
188  
189                  if (size < entry.Size)
190                  {
191                      right = middle - 1;
192                  }
193                  else
194                  {
195                      left = middle + 1;
196                  }
197              }
198  
199              return middle;
200          }
201  
202          /// <summary>
203          /// Tries to find an item on the table.
204          /// </summary>
205          /// <param name="dataAccessor">Data accessor</param>
206          /// <param name="item">Item, if found</param>
207          /// <param name="data">Data, if found</param>
208          /// <returns>True if the item was found on the table, false otherwise</returns>
209          public bool TryFindItem(IDataAccessor dataAccessor, out T item, out byte[] data)
210          {
211              SmartDataAccessor sda = new(dataAccessor);
212  
213              item = default;
214              data = null;
215  
216              int left = 0;
217              int right = _sizeTable.Count;
218  
219              while (left != right)
220              {
221                  int index = left + ((right - left) >> 1);
222  
223                  PartitionHashTable<T>.SearchResult result = _sizeTable[index].TryFindItem(ref sda, ref item, ref data);
224  
225                  if (result == PartitionHashTable<T>.SearchResult.FoundFull)
226                  {
227                      return true;
228                  }
229  
230                  if (result == PartitionHashTable<T>.SearchResult.NotFound)
231                  {
232                      right = index;
233                  }
234                  else /* if (result == PartitionHashTable<T>.SearchResult.FoundPartial) */
235                  {
236                      left = index + 1;
237                  }
238              }
239  
240              data = null;
241              return false;
242          }
243      }
244  }