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
|
using System;
using System.Collections.Generic;
using System.Numerics;
namespace ARMeilleure.Common
{
/// <summary>
/// Represents an expandable table of the type <typeparamref name="TEntry"/>, whose entries will remain at the same
/// address through out the table's lifetime.
/// </summary>
/// <typeparam name="TEntry">Type of the entry in the table</typeparam>
class EntryTable<TEntry> : IDisposable where TEntry : unmanaged
{
private bool _disposed;
private int _freeHint;
private readonly int _pageCapacity; // Number of entries per page.
private readonly int _pageLogCapacity;
private readonly Dictionary<int, IntPtr> _pages;
private readonly BitMap _allocated;
/// <summary>
/// Initializes a new instance of the <see cref="EntryTable{TEntry}"/> class with the desired page size in
/// bytes.
/// </summary>
/// <param name="pageSize">Desired page size in bytes</param>
/// <exception cref="ArgumentOutOfRangeException"><paramref name="pageSize"/> is less than 0</exception>
/// <exception cref="ArgumentException"><typeparamref name="TEntry"/>'s size is zero</exception>
/// <remarks>
/// The actual page size may be smaller or larger depending on the size of <typeparamref name="TEntry"/>.
/// </remarks>
public unsafe EntryTable(int pageSize = 4096)
{
if (pageSize < 0)
{
throw new ArgumentOutOfRangeException(nameof(pageSize), "Page size cannot be negative.");
}
if (sizeof(TEntry) == 0)
{
throw new ArgumentException("Size of TEntry cannot be zero.");
}
_allocated = new BitMap(NativeAllocator.Instance);
_pages = new Dictionary<int, IntPtr>();
_pageLogCapacity = BitOperations.Log2((uint)(pageSize / sizeof(TEntry)));
_pageCapacity = 1 << _pageLogCapacity;
}
/// <summary>
/// Allocates an entry in the <see cref="EntryTable{TEntry}"/>.
/// </summary>
/// <returns>Index of entry allocated in the table</returns>
/// <exception cref="ObjectDisposedException"><see cref="EntryTable{TEntry}"/> instance was disposed</exception>
public int Allocate()
{
ObjectDisposedException.ThrowIf(_disposed, this);
lock (_allocated)
{
if (_allocated.IsSet(_freeHint))
{
_freeHint = _allocated.FindFirstUnset();
}
int index = _freeHint++;
var page = GetPage(index);
_allocated.Set(index);
GetValue(page, index) = default;
return index;
}
}
/// <summary>
/// Frees the entry at the specified <paramref name="index"/>.
/// </summary>
/// <param name="index">Index of entry to free</param>
/// <exception cref="ObjectDisposedException"><see cref="EntryTable{TEntry}"/> instance was disposed</exception>
public void Free(int index)
{
ObjectDisposedException.ThrowIf(_disposed, this);
lock (_allocated)
{
if (_allocated.IsSet(index))
{
_allocated.Clear(index);
_freeHint = index;
}
}
}
/// <summary>
/// Gets a reference to the entry at the specified allocated <paramref name="index"/>.
/// </summary>
/// <param name="index">Index of the entry</param>
/// <returns>Reference to the entry at the specified <paramref name="index"/></returns>
/// <exception cref="ObjectDisposedException"><see cref="EntryTable{TEntry}"/> instance was disposed</exception>
/// <exception cref="ArgumentException">Entry at <paramref name="index"/> is not allocated</exception>
public ref TEntry GetValue(int index)
{
ObjectDisposedException.ThrowIf(_disposed, this);
lock (_allocated)
{
if (!_allocated.IsSet(index))
{
throw new ArgumentException("Entry at the specified index was not allocated", nameof(index));
}
var page = GetPage(index);
return ref GetValue(page, index);
}
}
/// <summary>
/// Gets a reference to the entry at using the specified <paramref name="index"/> from the specified
/// <paramref name="page"/>.
/// </summary>
/// <param name="page">Page to use</param>
/// <param name="index">Index to use</param>
/// <returns>Reference to the entry</returns>
private ref TEntry GetValue(Span<TEntry> page, int index)
{
return ref page[index & (_pageCapacity - 1)];
}
/// <summary>
/// Gets the page for the specified <see cref="index"/>.
/// </summary>
/// <param name="index">Index to use</param>
/// <returns>Page for the specified <see cref="index"/></returns>
private unsafe Span<TEntry> GetPage(int index)
{
var pageIndex = (int)((uint)(index & ~(_pageCapacity - 1)) >> _pageLogCapacity);
if (!_pages.TryGetValue(pageIndex, out IntPtr page))
{
page = (IntPtr)NativeAllocator.Instance.Allocate((uint)sizeof(TEntry) * (uint)_pageCapacity);
_pages.Add(pageIndex, page);
}
return new Span<TEntry>((void*)page, _pageCapacity);
}
/// <summary>
/// Releases all resources used by the <see cref="EntryTable{TEntry}"/> instance.
/// </summary>
public void Dispose()
{
Dispose(true);
GC.SuppressFinalize(this);
}
/// <summary>
/// Releases all unmanaged and optionally managed resources used by the <see cref="EntryTable{TEntry}"/>
/// instance.
/// </summary>
/// <param name="disposing"><see langword="true"/> to dispose managed resources also; otherwise just unmanaged resouces</param>
protected unsafe virtual void Dispose(bool disposing)
{
if (!_disposed)
{
_allocated.Dispose();
foreach (var page in _pages.Values)
{
NativeAllocator.Instance.Free((void*)page);
}
_disposed = true;
}
}
/// <summary>
/// Frees resources used by the <see cref="EntryTable{TEntry}"/> instance.
/// </summary>
~EntryTable()
{
Dispose(false);
}
}
}
|
