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