PartitionHashTable.cs
1 using System; 2 using System.Collections.Generic; 3 using System.Numerics; 4 5 namespace Ryujinx.Graphics.Gpu.Shader.HashTable 6 { 7 /// <summary> 8 /// Partitioned hash table. 9 /// </summary> 10 /// <typeparam name="T">Hash table entry type</typeparam> 11 class PartitionHashTable<T> 12 { 13 /// <summary> 14 /// Hash table entry. 15 /// </summary> 16 private struct Entry 17 { 18 /// <summary> 19 /// Hash <see cref="OwnSize"/> bytes of <see cref="Data"/>. 20 /// </summary> 21 public readonly uint Hash; 22 23 /// <summary> 24 /// If this entry is only a sub-region of <see cref="Data"/>, this indicates the size in bytes 25 /// of that region. Otherwise, it should be zero. 26 /// </summary> 27 public readonly int OwnSize; 28 29 /// <summary> 30 /// Data used to compute the hash for this entry. 31 /// </summary> 32 /// <remarks> 33 /// To avoid additional allocations, this might be a instance of the full entry data, 34 /// and only a sub-region of it might be actually used by this entry. Such sub-region 35 /// has its size indicated by <see cref="OwnSize"/> in this case. 36 /// </remarks> 37 public readonly byte[] Data; 38 39 /// <summary> 40 /// Item associated with this entry. 41 /// </summary> 42 public T Item; 43 44 /// <summary> 45 /// Indicates if the entry is partial, which means that this entry is only for a sub-region of the data. 46 /// </summary> 47 /// <remarks> 48 /// Partial entries have no items associated with them. They just indicates that the data might be present on 49 /// the table, and one must keep looking for the full entry on other tables of larger data size. 50 /// </remarks> 51 public readonly bool IsPartial => OwnSize != 0; 52 53 /// <summary> 54 /// Creates a new partial hash table entry. 55 /// </summary> 56 /// <param name="hash">Hash of the data</param> 57 /// <param name="ownerData">Full data</param> 58 /// <param name="ownSize">Size of the sub-region of data that belongs to this entry</param> 59 public Entry(uint hash, byte[] ownerData, int ownSize) 60 { 61 Hash = hash; 62 OwnSize = ownSize; 63 Data = ownerData; 64 Item = default; 65 } 66 67 /// <summary> 68 /// Creates a new full hash table entry. 69 /// </summary> 70 /// <param name="hash">Hash of the data</param> 71 /// <param name="data">Data</param> 72 /// <param name="item">Item associated with this entry</param> 73 public Entry(uint hash, byte[] data, T item) 74 { 75 Hash = hash; 76 OwnSize = 0; 77 Data = data; 78 Item = item; 79 } 80 81 /// <summary> 82 /// Gets the data for this entry, either full or partial. 83 /// </summary> 84 /// <returns>Data sub-region</returns> 85 public readonly ReadOnlySpan<byte> GetData() 86 { 87 if (OwnSize != 0) 88 { 89 return new ReadOnlySpan<byte>(Data)[..OwnSize]; 90 } 91 92 return Data; 93 } 94 } 95 96 /// <summary> 97 /// Hash table bucket. 98 /// </summary> 99 private struct Bucket 100 { 101 /// <summary> 102 /// Inline entry, to avoid allocations for the common single entry case. 103 /// </summary> 104 public Entry InlineEntry; 105 106 /// <summary> 107 /// List of additional entries for the not-so-common multiple entries case. 108 /// </summary> 109 public List<Entry> MoreEntries; 110 } 111 112 private Bucket[] _buckets; 113 private int _count; 114 115 /// <summary> 116 /// Total amount of entries on the hash table. 117 /// </summary> 118 public int Count => _count; 119 120 /// <summary> 121 /// Creates a new instance of the partitioned hash table. 122 /// </summary> 123 public PartitionHashTable() 124 { 125 _buckets = Array.Empty<Bucket>(); 126 } 127 128 /// <summary> 129 /// Gets an item on the table, or adds a new one if not present. 130 /// </summary> 131 /// <param name="data">Data</param> 132 /// <param name="dataHash">Hash of the data</param> 133 /// <param name="item">Item to be added if not found</param> 134 /// <returns>Existing item if found, or <paramref name="item"/> if not found</returns> 135 public T GetOrAdd(byte[] data, uint dataHash, T item) 136 { 137 if (TryFindItem(dataHash, data, out T existingItem)) 138 { 139 return existingItem; 140 } 141 142 Entry entry = new(dataHash, data, item); 143 144 AddToBucket(dataHash, ref entry); 145 146 return item; 147 } 148 149 /// <summary> 150 /// Adds an item to the hash table. 151 /// </summary> 152 /// <param name="data">Data</param> 153 /// <param name="dataHash">Hash of the data</param> 154 /// <param name="item">Item to be added</param> 155 /// <returns>True if the item was added, false due to an item associated with the data already being on the table</returns> 156 public bool Add(byte[] data, uint dataHash, T item) 157 { 158 if (TryFindItem(dataHash, data, out _)) 159 { 160 return false; 161 } 162 163 Entry entry = new(dataHash, data, item); 164 165 AddToBucket(dataHash, ref entry); 166 167 return true; 168 } 169 170 /// <summary> 171 /// Adds a partial entry to the hash table. 172 /// </summary> 173 /// <param name="ownerData">Full data</param> 174 /// <param name="ownSize">Size of the sub-region of <paramref name="ownerData"/> used by the partial entry</param> 175 /// <returns>True if added, false otherwise</returns> 176 public bool AddPartial(byte[] ownerData, int ownSize) 177 { 178 ReadOnlySpan<byte> data = new ReadOnlySpan<byte>(ownerData)[..ownSize]; 179 180 return AddPartial(ownerData, HashState.CalcHash(data), ownSize); 181 } 182 183 /// <summary> 184 /// Adds a partial entry to the hash table. 185 /// </summary> 186 /// <param name="ownerData">Full data</param> 187 /// <param name="dataHash">Hash of the data sub-region</param> 188 /// <param name="ownSize">Size of the sub-region of <paramref name="ownerData"/> used by the partial entry</param> 189 /// <returns>True if added, false otherwise</returns> 190 public bool AddPartial(byte[] ownerData, uint dataHash, int ownSize) 191 { 192 ReadOnlySpan<byte> data = new ReadOnlySpan<byte>(ownerData)[..ownSize]; 193 194 if (TryFindItem(dataHash, data, out _)) 195 { 196 return false; 197 } 198 199 Entry entry = new(dataHash, ownerData, ownSize); 200 201 AddToBucket(dataHash, ref entry); 202 203 return true; 204 } 205 206 /// <summary> 207 /// Adds entry with a given hash to the table. 208 /// </summary> 209 /// <param name="dataHash">Hash of the entry</param> 210 /// <param name="entry">Entry</param> 211 private void AddToBucket(uint dataHash, ref Entry entry) 212 { 213 int pow2Count = GetPow2Count(++_count); 214 if (pow2Count != _buckets.Length) 215 { 216 Rebuild(pow2Count); 217 } 218 219 ref Bucket bucket = ref GetBucketForHash(dataHash); 220 221 AddToBucket(ref bucket, ref entry); 222 } 223 224 /// <summary> 225 /// Adds an entry to a bucket. 226 /// </summary> 227 /// <param name="bucket">Bucket to add the entry into</param> 228 /// <param name="entry">Entry to be added</param> 229 private static void AddToBucket(ref Bucket bucket, ref Entry entry) 230 { 231 if (bucket.InlineEntry.Data == null) 232 { 233 bucket.InlineEntry = entry; 234 } 235 else 236 { 237 (bucket.MoreEntries ??= new List<Entry>()).Add(entry); 238 } 239 } 240 241 /// <summary> 242 /// Creates partial entries on a new hash table for all existing full entries. 243 /// </summary> 244 /// <remarks> 245 /// This should be called every time a new hash table is created, and there are hash 246 /// tables with data sizes that are higher than that of the new table. 247 /// This will then fill the new hash table with "partial" entries of full entries 248 /// on the hash tables with higher size. 249 /// </remarks> 250 /// <param name="newTable">New hash table</param> 251 /// <param name="newEntrySize">Size of the data on the new hash table</param> 252 public void FillPartials(PartitionHashTable<T> newTable, int newEntrySize) 253 { 254 for (int i = 0; i < _buckets.Length; i++) 255 { 256 ref Bucket bucket = ref _buckets[i]; 257 ref Entry inlineEntry = ref bucket.InlineEntry; 258 259 if (inlineEntry.Data != null) 260 { 261 if (!inlineEntry.IsPartial) 262 { 263 newTable.AddPartial(inlineEntry.Data, newEntrySize); 264 } 265 266 if (bucket.MoreEntries != null) 267 { 268 foreach (Entry entry in bucket.MoreEntries) 269 { 270 if (entry.IsPartial) 271 { 272 continue; 273 } 274 275 newTable.AddPartial(entry.Data, newEntrySize); 276 } 277 } 278 } 279 } 280 } 281 282 /// <summary> 283 /// Tries to find an item on the table. 284 /// </summary> 285 /// <param name="dataHash">Hash of <paramref name="data"/></param> 286 /// <param name="data">Data to find</param> 287 /// <param name="item">Item associated with the data</param> 288 /// <returns>True if an item was found, false otherwise</returns> 289 private bool TryFindItem(uint dataHash, ReadOnlySpan<byte> data, out T item) 290 { 291 if (_count == 0) 292 { 293 item = default; 294 return false; 295 } 296 297 ref Bucket bucket = ref GetBucketForHash(dataHash); 298 299 if (bucket.InlineEntry.Data != null) 300 { 301 if (bucket.InlineEntry.Hash == dataHash && bucket.InlineEntry.GetData().SequenceEqual(data)) 302 { 303 item = bucket.InlineEntry.Item; 304 return true; 305 } 306 307 if (bucket.MoreEntries != null) 308 { 309 foreach (Entry entry in bucket.MoreEntries) 310 { 311 if (entry.Hash == dataHash && entry.GetData().SequenceEqual(data)) 312 { 313 item = entry.Item; 314 return true; 315 } 316 } 317 } 318 } 319 320 item = default; 321 return false; 322 } 323 324 /// <summary> 325 /// Indicates the result of a hash table lookup. 326 /// </summary> 327 public enum SearchResult 328 { 329 /// <summary> 330 /// No entry was found, the search must continue on hash tables of lower size. 331 /// </summary> 332 NotFound, 333 334 /// <summary> 335 /// A partial entry was found, the search must continue on hash tables of higher size. 336 /// </summary> 337 FoundPartial, 338 339 /// <summary> 340 /// A full entry was found, the search was concluded and the item can be retrieved. 341 /// </summary> 342 FoundFull, 343 } 344 345 /// <summary> 346 /// Tries to find an item on the table. 347 /// </summary> 348 /// <param name="dataAccessor">Data accessor</param> 349 /// <param name="size">Size of the hash table data</param> 350 /// <param name="item">The item on the table, if found, otherwise unmodified</param> 351 /// <param name="data">The data on the table, if found, otherwise unmodified</param> 352 /// <returns>Table lookup result</returns> 353 public SearchResult TryFindItem(scoped ref SmartDataAccessor dataAccessor, int size, scoped ref T item, scoped ref byte[] data) 354 { 355 if (_count == 0) 356 { 357 return SearchResult.NotFound; 358 } 359 360 ReadOnlySpan<byte> dataSpan = dataAccessor.GetSpanAndHash(size, out uint dataHash); 361 362 if (dataSpan.Length != size) 363 { 364 return SearchResult.NotFound; 365 } 366 367 ref Bucket bucket = ref GetBucketForHash(dataHash); 368 369 if (bucket.InlineEntry.Data != null) 370 { 371 if (bucket.InlineEntry.Hash == dataHash && bucket.InlineEntry.GetData().SequenceEqual(dataSpan)) 372 { 373 item = bucket.InlineEntry.Item; 374 data = bucket.InlineEntry.Data; 375 return bucket.InlineEntry.IsPartial ? SearchResult.FoundPartial : SearchResult.FoundFull; 376 } 377 378 if (bucket.MoreEntries != null) 379 { 380 foreach (Entry entry in bucket.MoreEntries) 381 { 382 if (entry.Hash == dataHash && entry.GetData().SequenceEqual(dataSpan)) 383 { 384 item = entry.Item; 385 data = entry.Data; 386 return entry.IsPartial ? SearchResult.FoundPartial : SearchResult.FoundFull; 387 } 388 } 389 } 390 } 391 392 return SearchResult.NotFound; 393 } 394 395 /// <summary> 396 /// Rebuilds the table for a new count. 397 /// </summary> 398 /// <param name="newPow2Count">New power of two count of the table</param> 399 private void Rebuild(int newPow2Count) 400 { 401 Bucket[] newBuckets = new Bucket[newPow2Count]; 402 403 uint mask = (uint)newPow2Count - 1; 404 405 for (int i = 0; i < _buckets.Length; i++) 406 { 407 ref Bucket bucket = ref _buckets[i]; 408 409 if (bucket.InlineEntry.Data != null) 410 { 411 AddToBucket(ref newBuckets[(int)(bucket.InlineEntry.Hash & mask)], ref bucket.InlineEntry); 412 413 if (bucket.MoreEntries != null) 414 { 415 foreach (Entry entry in bucket.MoreEntries) 416 { 417 Entry entryCopy = entry; 418 AddToBucket(ref newBuckets[(int)(entry.Hash & mask)], ref entryCopy); 419 } 420 } 421 } 422 } 423 424 _buckets = newBuckets; 425 } 426 427 /// <summary> 428 /// Gets the bucket for a given hash. 429 /// </summary> 430 /// <param name="hash">Data hash</param> 431 /// <returns>Bucket for the hash</returns> 432 private ref Bucket GetBucketForHash(uint hash) 433 { 434 int index = (int)(hash & (_buckets.Length - 1)); 435 436 return ref _buckets[index]; 437 } 438 439 /// <summary> 440 /// Gets a power of two count from a regular count. 441 /// </summary> 442 /// <param name="count">Count</param> 443 /// <returns>Power of two count</returns> 444 private static int GetPow2Count(int count) 445 { 446 // This returns the nearest power of two that is lower than count. 447 // This was done to optimize memory usage rather than performance. 448 return 1 << BitOperations.Log2((uint)count); 449 } 450 } 451 }