1  using System;
  2  using System.Collections.Generic;
  3  using System.Numerics;
  4  
  5  namespace ARMeilleure.Common
  6  {
  7      /// <summary>
  8      /// Represents an expandable table of the type <typeparamref name="TEntry"/>, whose entries will remain at the same
  9      /// address through out the table's lifetime.
 10      /// </summary>
 11      /// <typeparam name="TEntry">Type of the entry in the table</typeparam>
 12      class EntryTable<TEntry> : IDisposable where TEntry : unmanaged
 13      {
 14          private bool _disposed;
 15          private int _freeHint;
 16          private readonly int _pageCapacity; // Number of entries per page.
 17          private readonly int _pageLogCapacity;
 18          private readonly Dictionary<int, IntPtr> _pages;
 19          private readonly BitMap _allocated;
 20  
 21          /// <summary>
 22          /// Initializes a new instance of the <see cref="EntryTable{TEntry}"/> class with the desired page size in
 23          /// bytes.
 24          /// </summary>
 25          /// <param name="pageSize">Desired page size in bytes</param>
 26          /// <exception cref="ArgumentOutOfRangeException"><paramref name="pageSize"/> is less than 0</exception>
 27          /// <exception cref="ArgumentException"><typeparamref name="TEntry"/>'s size is zero</exception>
 28          /// <remarks>
 29          /// The actual page size may be smaller or larger depending on the size of <typeparamref name="TEntry"/>.
 30          /// </remarks>
 31          public unsafe EntryTable(int pageSize = 4096)
 32          {
 33              if (pageSize < 0)
 34              {
 35                  throw new ArgumentOutOfRangeException(nameof(pageSize), "Page size cannot be negative.");
 36              }
 37  
 38              if (sizeof(TEntry) == 0)
 39              {
 40                  throw new ArgumentException("Size of TEntry cannot be zero.");
 41              }
 42  
 43              _allocated = new BitMap(NativeAllocator.Instance);
 44              _pages = new Dictionary<int, IntPtr>();
 45              _pageLogCapacity = BitOperations.Log2((uint)(pageSize / sizeof(TEntry)));
 46              _pageCapacity = 1 << _pageLogCapacity;
 47          }
 48  
 49          /// <summary>
 50          /// Allocates an entry in the <see cref="EntryTable{TEntry}"/>.
 51          /// </summary>
 52          /// <returns>Index of entry allocated in the table</returns>
 53          /// <exception cref="ObjectDisposedException"><see cref="EntryTable{TEntry}"/> instance was disposed</exception>
 54          public int Allocate()
 55          {
 56              ObjectDisposedException.ThrowIf(_disposed, this);
 57  
 58              lock (_allocated)
 59              {
 60                  if (_allocated.IsSet(_freeHint))
 61                  {
 62                      _freeHint = _allocated.FindFirstUnset();
 63                  }
 64  
 65                  int index = _freeHint++;
 66                  var page = GetPage(index);
 67  
 68                  _allocated.Set(index);
 69  
 70                  GetValue(page, index) = default;
 71  
 72                  return index;
 73              }
 74          }
 75  
 76          /// <summary>
 77          /// Frees the entry at the specified <paramref name="index"/>.
 78          /// </summary>
 79          /// <param name="index">Index of entry to free</param>
 80          /// <exception cref="ObjectDisposedException"><see cref="EntryTable{TEntry}"/> instance was disposed</exception>
 81          public void Free(int index)
 82          {
 83              ObjectDisposedException.ThrowIf(_disposed, this);
 84  
 85              lock (_allocated)
 86              {
 87                  if (_allocated.IsSet(index))
 88                  {
 89                      _allocated.Clear(index);
 90  
 91                      _freeHint = index;
 92                  }
 93              }
 94          }
 95  
 96          /// <summary>
 97          /// Gets a reference to the entry at the specified allocated <paramref name="index"/>.
 98          /// </summary>
 99          /// <param name="index">Index of the entry</param>
100          /// <returns>Reference to the entry at the specified <paramref name="index"/></returns>
101          /// <exception cref="ObjectDisposedException"><see cref="EntryTable{TEntry}"/> instance was disposed</exception>
102          /// <exception cref="ArgumentException">Entry at <paramref name="index"/> is not allocated</exception>
103          public ref TEntry GetValue(int index)
104          {
105              ObjectDisposedException.ThrowIf(_disposed, this);
106  
107              lock (_allocated)
108              {
109                  if (!_allocated.IsSet(index))
110                  {
111                      throw new ArgumentException("Entry at the specified index was not allocated", nameof(index));
112                  }
113  
114                  var page = GetPage(index);
115  
116                  return ref GetValue(page, index);
117              }
118          }
119  
120          /// <summary>
121          /// Gets a reference to the entry at using the specified <paramref name="index"/> from the specified
122          /// <paramref name="page"/>.
123          /// </summary>
124          /// <param name="page">Page to use</param>
125          /// <param name="index">Index to use</param>
126          /// <returns>Reference to the entry</returns>
127          private ref TEntry GetValue(Span<TEntry> page, int index)
128          {
129              return ref page[index & (_pageCapacity - 1)];
130          }
131  
132          /// <summary>
133          /// Gets the page for the specified <see cref="index"/>.
134          /// </summary>
135          /// <param name="index">Index to use</param>
136          /// <returns>Page for the specified <see cref="index"/></returns>
137          private unsafe Span<TEntry> GetPage(int index)
138          {
139              var pageIndex = (int)((uint)(index & ~(_pageCapacity - 1)) >> _pageLogCapacity);
140  
141              if (!_pages.TryGetValue(pageIndex, out IntPtr page))
142              {
143                  page = (IntPtr)NativeAllocator.Instance.Allocate((uint)sizeof(TEntry) * (uint)_pageCapacity);
144  
145                  _pages.Add(pageIndex, page);
146              }
147  
148              return new Span<TEntry>((void*)page, _pageCapacity);
149          }
150  
151          /// <summary>
152          /// Releases all resources used by the <see cref="EntryTable{TEntry}"/> instance.
153          /// </summary>
154          public void Dispose()
155          {
156              Dispose(true);
157              GC.SuppressFinalize(this);
158          }
159  
160          /// <summary>
161          /// Releases all unmanaged and optionally managed resources used by the <see cref="EntryTable{TEntry}"/>
162          /// instance.
163          /// </summary>
164          /// <param name="disposing"><see langword="true"/> to dispose managed resources also; otherwise just unmanaged resouces</param>
165          protected unsafe virtual void Dispose(bool disposing)
166          {
167              if (!_disposed)
168              {
169                  _allocated.Dispose();
170  
171                  foreach (var page in _pages.Values)
172                  {
173                      NativeAllocator.Instance.Free((void*)page);
174                  }
175  
176                  _disposed = true;
177              }
178          }
179  
180          /// <summary>
181          /// Frees resources used by the <see cref="EntryTable{TEntry}"/> instance.
182          /// </summary>
183          ~EntryTable()
184          {
185              Dispose(false);
186          }
187      }
188  }