A game about forced loneliness, made by TACStudios
tacstudios.tngl.sh
1using System;
2using System.Diagnostics;
3using System.Threading;
4using AOT;
5using Unity.Burst;
6using Unity.Collections.LowLevel.Unsafe;
7using Unity.Mathematics;
8
9namespace Unity.Collections
10{
11 unsafe internal struct ArrayOfArrays<T> : IDisposable where T : unmanaged
12 {
13 AllocatorManager.AllocatorHandle m_backingAllocatorHandle;
14 int m_lengthInElements;
15 int m_capacityInElements;
16 int m_log2BlockSizeInElements;
17 int m_blocks;
18 IntPtr* m_block;
19
20 int BlockSizeInElements => 1 << m_log2BlockSizeInElements;
21 int BlockSizeInBytes => BlockSizeInElements * sizeof(T);
22 int BlockMask => BlockSizeInElements - 1;
23
24 public int Length => m_lengthInElements;
25 public int Capacity => m_capacityInElements;
26
27 public ArrayOfArrays(int capacityInElements, AllocatorManager.AllocatorHandle backingAllocatorHandle, int log2BlockSizeInElements = 12)
28 {
29 this = default;
30 m_backingAllocatorHandle = backingAllocatorHandle;
31 m_lengthInElements = 0;
32 m_capacityInElements = capacityInElements;
33 m_log2BlockSizeInElements = log2BlockSizeInElements;
34 m_blocks = (capacityInElements + BlockMask) >> m_log2BlockSizeInElements;
35 m_block = (IntPtr*)Memory.Unmanaged.Allocate(sizeof(IntPtr) * m_blocks, 16, m_backingAllocatorHandle);
36 UnsafeUtility.MemSet(m_block, 0, sizeof(IntPtr) * m_blocks);
37 }
38
39 public void LockfreeAdd(T t)
40 {
41 var elementIndex = Interlocked.Increment(ref m_lengthInElements) - 1;
42 var blockIndex = BlockIndexOfElement(elementIndex);
43 CheckBlockIndex(blockIndex);
44 if(m_block[blockIndex] == IntPtr.Zero)
45 {
46 void* pointer = Memory.Unmanaged.Allocate(BlockSizeInBytes, 16, m_backingAllocatorHandle); // $$$!
47 var lastBlock = math.min(m_blocks, blockIndex + 4); // don't overgrow too fast, simply to avoid a $$$ free
48 for(; blockIndex < lastBlock; ++blockIndex)
49 if(IntPtr.Zero == Interlocked.CompareExchange(ref m_block[blockIndex], (IntPtr)pointer, IntPtr.Zero))
50 break; // install the new block, into *any* empty slot available, to avoid wasting the time we spent on malloc
51 if(blockIndex == lastBlock)
52 Memory.Unmanaged.Free(pointer, m_backingAllocatorHandle); // $$$, only if absolutely necessary
53 }
54 this[elementIndex] = t;
55 }
56
57 public ref T this[int elementIndex]
58 {
59 get
60 {
61 CheckElementIndex(elementIndex);
62 var blockIndex = BlockIndexOfElement(elementIndex);
63 CheckBlockIndex(blockIndex);
64 CheckBlockIsNotNull(blockIndex);
65 IntPtr blockIntPtr = m_block[blockIndex];
66 var elementIndexInBlock = elementIndex & BlockMask;
67 T* blockPointer = (T*)blockIntPtr;
68 return ref blockPointer[elementIndexInBlock];
69 }
70 }
71
72 public void Rewind()
73 {
74 m_lengthInElements = 0;
75 }
76
77 public void Clear()
78 {
79 Rewind();
80 for(var i = 0; i < m_blocks; ++i)
81 if(m_block[i] != IntPtr.Zero)
82 {
83 Memory.Unmanaged.Free((void*)m_block[i], m_backingAllocatorHandle);
84 m_block[i] = IntPtr.Zero;
85 }
86 }
87
88 public void Dispose()
89 {
90 Clear();
91 Memory.Unmanaged.Free(m_block, m_backingAllocatorHandle);
92 }
93
94 [Conditional("ENABLE_UNITY_COLLECTIONS_CHECKS"), Conditional("UNITY_DOTS_DEBUG")]
95 void CheckElementIndex(int elementIndex)
96 {
97 if (elementIndex >= m_lengthInElements)
98 throw new ArgumentException($"Element index {elementIndex} must be less than length in elements {m_lengthInElements}.");
99 }
100
101 [Conditional("ENABLE_UNITY_COLLECTIONS_CHECKS"), Conditional("UNITY_DOTS_DEBUG")]
102 void CheckBlockIndex(int blockIndex)
103 {
104 if (blockIndex >= m_blocks)
105 throw new ArgumentException($"Block index {blockIndex} must be less than number of blocks {m_blocks}.");
106 }
107
108 [Conditional("ENABLE_UNITY_COLLECTIONS_CHECKS"), Conditional("UNITY_DOTS_DEBUG")]
109 void CheckBlockIsNotNull(int blockIndex)
110 {
111 if(m_block[blockIndex] == IntPtr.Zero)
112 throw new ArgumentException($"Block index {blockIndex} is a null pointer.");
113 }
114
115 public void RemoveAtSwapBack(int elementIndex)
116 {
117 this[elementIndex] = this[Length-1];
118 --m_lengthInElements;
119 }
120
121 int BlockIndexOfElement(int elementIndex)
122 {
123 return elementIndex >> m_log2BlockSizeInElements;
124 }
125
126 public void TrimExcess()
127 {
128 for(var blockIndex = BlockIndexOfElement(m_lengthInElements + BlockMask); blockIndex < m_blocks; ++blockIndex)
129 {
130 CheckBlockIndex(blockIndex);
131 if(m_block[blockIndex] != IntPtr.Zero)
132 {
133 var blockIntPtr = m_block[blockIndex];
134 void* blockPointer = (void*)blockIntPtr;
135 Memory.Unmanaged.Free(blockPointer, m_backingAllocatorHandle);
136 m_block[blockIndex] = IntPtr.Zero;
137 }
138 }
139 }
140 }
141
142 [BurstCompile]
143 internal struct AutoFreeAllocator : AllocatorManager.IAllocator
144 {
145 ArrayOfArrays<IntPtr> m_allocated;
146 ArrayOfArrays<IntPtr> m_tofree;
147 AllocatorManager.AllocatorHandle m_handle;
148 AllocatorManager.AllocatorHandle m_backingAllocatorHandle;
149
150 unsafe public void Update()
151 {
152 for(var i = m_tofree.Length; i --> 0;)
153 for(var j = m_allocated.Length; j --> 0;)
154 if(m_allocated[j] == m_tofree[i])
155 {
156 Memory.Unmanaged.Free((void*)m_tofree[i], m_backingAllocatorHandle);
157 m_allocated.RemoveAtSwapBack(j);
158 break;
159 }
160 m_tofree.Rewind();
161 m_allocated.TrimExcess();
162 }
163
164 unsafe public void Initialize(AllocatorManager.AllocatorHandle backingAllocatorHandle)
165 {
166 m_allocated = new ArrayOfArrays<IntPtr>(1024 * 1024, backingAllocatorHandle);
167 m_tofree = new ArrayOfArrays<IntPtr>(128 * 1024, backingAllocatorHandle);
168 m_backingAllocatorHandle = backingAllocatorHandle;
169 }
170
171 unsafe public void FreeAll()
172 {
173 Update();
174 m_handle.Rewind();
175 for(var i = 0; i < m_allocated.Length; ++i)
176 Memory.Unmanaged.Free((void*) m_allocated[i], m_backingAllocatorHandle);
177 m_allocated.Rewind();
178 }
179
180 /// <summary>
181 /// Dispose the allocator. This must be called to free the memory blocks that were allocated from the system.
182 /// </summary>
183 public void Dispose()
184 {
185 FreeAll();
186 m_tofree.Dispose();
187 m_allocated.Dispose();
188 }
189
190 /// <summary>
191 /// The allocator function. It can allocate, deallocate, or reallocate.
192 /// </summary>
193 public AllocatorManager.TryFunction Function => Try;
194
195 /// <summary>
196 /// Invoke the allocator function.
197 /// </summary>
198 /// <param name="block">The block to allocate, deallocate, or reallocate. See <see cref="AllocatorManager.Try"/></param>
199 /// <returns>0 if successful. Otherwise, returns the error code from the allocator function.</returns>
200 public int Try(ref AllocatorManager.Block block)
201 {
202 unsafe
203 {
204 if (block.Range.Pointer == IntPtr.Zero)
205 {
206 if (block.Bytes == 0)
207 {
208 return 0;
209 }
210
211 var ptr = (byte*)Memory.Unmanaged.Allocate(block.Bytes, block.Alignment, m_backingAllocatorHandle);
212 block.Range.Pointer = (IntPtr)ptr;
213 block.AllocatedItems = block.Range.Items;
214
215 m_allocated.LockfreeAdd(block.Range.Pointer);
216
217 return 0;
218 }
219
220 if (block.Range.Items == 0)
221 {
222 m_tofree.LockfreeAdd(block.Range.Pointer);
223
224 block.Range.Pointer = IntPtr.Zero;
225 block.AllocatedItems = 0;
226
227 return 0;
228 }
229
230 return -1;
231 }
232 }
233
234 [BurstCompile]
235 [MonoPInvokeCallback(typeof(AllocatorManager.TryFunction))]
236 internal static int Try(IntPtr state, ref AllocatorManager.Block block)
237 {
238 unsafe { return ((AutoFreeAllocator*)state)->Try(ref block); }
239 }
240
241 /// <summary>
242 /// This allocator.
243 /// </summary>
244 /// <value>This allocator.</value>
245 public AllocatorManager.AllocatorHandle Handle { get { return m_handle; } set { m_handle = value; } }
246
247 /// <summary>
248 /// Cast the Allocator index into Allocator
249 /// </summary>
250 public Allocator ToAllocator { get { return m_handle.ToAllocator; } }
251
252 /// <summary>
253 /// Check whether an allocator is a custom allocator
254 /// </summary>
255 public bool IsCustomAllocator { get { return m_handle.IsCustomAllocator; } }
256
257 /// <summary>
258 /// Check whether this allocator will automatically dispose allocations.
259 /// </summary>
260 /// <remarks>Allocations made by Auto free allocator are automatically disposed.</remarks>
261 /// <value>Always true</value>
262 public bool IsAutoDispose { get { return true; } }
263 }
264}