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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
|
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
using System.Reflection.Metadata;
using Debug = System.Diagnostics.Debug;
using Internal.NativeFormat;
namespace Internal.TypeSystem.Ecma
{
/// <summary>
/// MetadataReader string decoder that caches and reuses strings rather than allocating
/// on each call to MetadataReader.GetString(handle).
/// Safe to use from multiple threads and lock free.
/// </summary>
public sealed class CachingMetadataStringDecoder : MetadataStringDecoder
{
private struct Entry
{
// hash code of the entry
public int HashCode;
// full text of the item
public string Text;
}
// TODO: Tune the bucket size
private const int BucketSize = 4;
// The table of cached entries. The size of the table has to be power of 2.
private Entry[] _table;
// The next candidate in the bucket range for eviction
private int _evictionHint;
public CachingMetadataStringDecoder(int size)
: base(System.Text.Encoding.UTF8)
{
Debug.Assert((size & (size - 1)) == 0, "The cache size must be power of 2");
_table = new Entry[size];
}
private string Find(int hashCode, string s)
{
var arr = _table;
int mask = _table.Length - 1;
int idx = hashCode & mask;
// we use quadratic probing here
// bucket positions are (n^2 + n)/2 relative to the masked hashcode
for (int i = 1; i < BucketSize + 1; i++)
{
string e = arr[idx].Text;
int hash = arr[idx].HashCode;
if (e == null)
{
// once we see unfilled entry, the rest of the bucket will be empty
break;
}
if (hash == hashCode && s == e)
{
return e;
}
idx = (idx + i) & mask;
}
return null;
}
private unsafe string FindASCII(int hashCode, byte* bytes, int byteCount)
{
var arr = _table;
int mask = _table.Length - 1;
int idx = hashCode & mask;
// we use quadratic probing here
// bucket positions are (n^2 + n)/2 relative to the masked hashcode
for (int i = 1; i < BucketSize + 1; i++)
{
string e = arr[idx].Text;
int hash = arr[idx].HashCode;
if (e == null)
{
// once we see unfilled entry, the rest of the bucket will be empty
break;
}
if (hash == hashCode && TextEqualsASCII(e, bytes, byteCount))
{
return e;
}
idx = (idx + i) & mask;
}
return null;
}
private static unsafe bool TextEqualsASCII(string text, byte* ascii, int length)
{
#if DEBUG
for (var i = 0; i < length; i++)
{
Debug.Assert((ascii[i] & 0x80) == 0, "The byte* input to this method must be valid ASCII.");
}
#endif
if (length != text.Length)
{
return false;
}
for (var i = 0; i < length; i++)
{
if (ascii[i] != text[i])
{
return false;
}
}
return true;
}
private string Add(int hashCode, string s)
{
var arr = _table;
int mask = _table.Length - 1;
int idx = hashCode & mask;
// try finding an empty spot in the bucket
// we use quadratic probing here
// bucket positions are (n^2 + n)/2 relative to the masked hashcode
int curIdx = idx;
for (int i = 1; i < BucketSize + 1; i++)
{
if (arr[curIdx].Text == null)
{
idx = curIdx;
goto foundIdx;
}
curIdx = (curIdx + i) & BucketSize;
}
// or pick a victim within the bucket range
// and replace with new entry
var i1 = _evictionHint++ & (BucketSize - 1);
idx = (idx + ((i1 * i1 + i1) / 2)) & mask;
foundIdx:
arr[idx].HashCode = hashCode;
arr[idx].Text = s;
return s;
}
public string Lookup(string s)
{
int hashCode = TypeHashingAlgorithms.ComputeNameHashCode(s);
string existing = Find(hashCode, s);
if (existing != null)
return existing;
return Add(hashCode, s);
}
public override unsafe string GetString(byte* bytes, int byteCount)
{
bool isAscii;
int hashCode = TypeHashingAlgorithms.ComputeASCIINameHashCode(bytes, byteCount, out isAscii);
if (isAscii)
{
string existing = FindASCII(hashCode, bytes, byteCount);
if (existing != null)
return existing;
return Add(hashCode, Encoding.GetString(bytes, byteCount));
}
else
{
return Lookup(Encoding.GetString(bytes, byteCount));
}
}
}
}
|
