1  using System;
  2  using System.Collections.Generic;
  3  using System.Runtime.CompilerServices;
  4  
  5  namespace Ryujinx.Graphics.Vulkan
  6  {
  7      interface IRefEquatable<T>
  8      {
  9          bool Equals(ref T other);
 10      }
 11  
 12      class HashTableSlim<TKey, TValue> where TKey : IRefEquatable<TKey>
 13      {
 14          private const int TotalBuckets = 16; // Must be power of 2
 15          private const int TotalBucketsMask = TotalBuckets - 1;
 16  
 17          private struct Entry
 18          {
 19              public int Hash;
 20              public TKey Key;
 21              public TValue Value;
 22          }
 23  
 24          private struct Bucket
 25          {
 26              public int Length;
 27              public Entry[] Entries;
 28  
 29              [MethodImpl(MethodImplOptions.AggressiveInlining)]
 30              public readonly Span<Entry> AsSpan()
 31              {
 32                  return Entries == null ? Span<Entry>.Empty : Entries.AsSpan(0, Length);
 33              }
 34          }
 35  
 36          private readonly Bucket[] _hashTable = new Bucket[TotalBuckets];
 37  
 38          public IEnumerable<TKey> Keys
 39          {
 40              get
 41              {
 42                  foreach (Bucket bucket in _hashTable)
 43                  {
 44                      for (int i = 0; i < bucket.Length; i++)
 45                      {
 46                          yield return bucket.Entries[i].Key;
 47                      }
 48                  }
 49              }
 50          }
 51  
 52          public IEnumerable<TValue> Values
 53          {
 54              get
 55              {
 56                  foreach (Bucket bucket in _hashTable)
 57                  {
 58                      for (int i = 0; i < bucket.Length; i++)
 59                      {
 60                          yield return bucket.Entries[i].Value;
 61                      }
 62                  }
 63              }
 64          }
 65  
 66          public void Add(ref TKey key, TValue value)
 67          {
 68              var entry = new Entry
 69              {
 70                  Hash = key.GetHashCode(),
 71                  Key = key,
 72                  Value = value,
 73              };
 74  
 75              int hashCode = key.GetHashCode();
 76              int bucketIndex = hashCode & TotalBucketsMask;
 77  
 78              ref var bucket = ref _hashTable[bucketIndex];
 79              if (bucket.Entries != null)
 80              {
 81                  int index = bucket.Length;
 82  
 83                  if (index >= bucket.Entries.Length)
 84                  {
 85                      Array.Resize(ref bucket.Entries, index + 1);
 86                  }
 87  
 88                  bucket.Entries[index] = entry;
 89              }
 90              else
 91              {
 92                  bucket.Entries = new[]
 93                  {
 94                      entry,
 95                  };
 96              }
 97  
 98              bucket.Length++;
 99          }
100  
101          public bool Remove(ref TKey key)
102          {
103              int hashCode = key.GetHashCode();
104  
105              ref var bucket = ref _hashTable[hashCode & TotalBucketsMask];
106              var entries = bucket.AsSpan();
107              for (int i = 0; i < entries.Length; i++)
108              {
109                  ref var entry = ref entries[i];
110  
111                  if (entry.Hash == hashCode && entry.Key.Equals(ref key))
112                  {
113                      entries[(i + 1)..].CopyTo(entries[i..]);
114                      bucket.Length--;
115  
116                      return true;
117                  }
118              }
119  
120              return false;
121          }
122  
123          public bool TryGetValue(ref TKey key, out TValue value)
124          {
125              int hashCode = key.GetHashCode();
126  
127              var entries = _hashTable[hashCode & TotalBucketsMask].AsSpan();
128              for (int i = 0; i < entries.Length; i++)
129              {
130                  ref var entry = ref entries[i];
131  
132                  if (entry.Hash == hashCode && entry.Key.Equals(ref key))
133                  {
134                      value = entry.Value;
135                      return true;
136                  }
137              }
138  
139              value = default;
140              return false;
141          }
142      }
143  }