A game about forced loneliness, made by TACStudios
tacstudios.tngl.sh
1using System;
2using System.Threading;
3using Unity.Collections.LowLevel.Unsafe;
4using Unity.Mathematics;
5
6#pragma warning disable 0649
7
8namespace Unity.Collections
9{
10 internal struct Long8
11 {
12 internal long f0,f1,f2,f3,f4,f5,f6,f7;
13 }
14
15 internal struct Long64
16 {
17 internal Long8 f0,f1,f2,f3,f4,f5,f6,f7;
18 }
19
20 internal struct Long512
21 {
22 internal Long64 f0,f1,f2,f3,f4,f5,f6,f7;
23 }
24
25 internal struct Long1024 : IIndexable<long>
26 {
27 internal Long512 f0,f1;
28 public int Length { get { return 1024;} set {} }
29 public ref long ElementAt(int index)
30 {
31 unsafe { fixed(Long512* p = &f0) {
32 return ref UnsafeUtility.AsRef<long>((long*)p + index);
33 } }
34 }
35 }
36
37 internal class ConcurrentMask
38 {
39 internal static long AtomicOr(ref long destination, long source)
40 {
41 var readValue = Interlocked.Read(ref destination);
42 long oldReadValue, writtenValue;
43 do
44 {
45 writtenValue = readValue | source;
46 oldReadValue = readValue;
47 readValue = Interlocked.CompareExchange(ref destination, writtenValue, oldReadValue);
48 } while(readValue != oldReadValue);
49 return writtenValue;
50 }
51
52 internal static long AtomicAnd(ref long destination, long source)
53 {
54 var readValue = Interlocked.Read(ref destination);
55 long oldReadValue, writtenValue;
56 do
57 {
58 writtenValue = readValue & source;
59 oldReadValue = readValue;
60 readValue = Interlocked.CompareExchange(ref destination, writtenValue, oldReadValue);
61 } while(readValue != oldReadValue);
62 return writtenValue;
63 }
64
65 internal static void longestConsecutiveOnes(long value, out int offset, out int count)
66 {
67 count = 0;
68 var newvalue = value;
69 while(newvalue != 0)
70 {
71 value = newvalue;
72 newvalue = value & (long)((ulong)value >> 1);
73 ++count;
74 }
75 offset = math.tzcnt(value);
76 }
77
78 internal static bool foundAtLeastThisManyConsecutiveOnes(long value, int minimum, out int offset, out int count)
79 {
80 if(minimum == 1)
81 {
82 offset = math.tzcnt(value); // find offset of first 1 bit
83 count = 1;
84 return offset != 64;
85 }
86 longestConsecutiveOnes(value, out offset, out count);
87 return count >= minimum;
88 }
89
90 internal static bool foundAtLeastThisManyConsecutiveZeroes(long value, int minimum, out int offset, out int count)
91 {
92 return foundAtLeastThisManyConsecutiveOnes(~value, minimum, out offset, out count);
93 }
94
95 internal const int ErrorFailedToFree = -1;
96 internal const int ErrorFailedToAllocate = -2;
97 internal const int ErrorAllocationCrossesWordBoundary = -3;
98 internal const int EmptyBeforeAllocation = 0;
99 internal const int EmptyAfterFree = 0;
100
101 internal static bool Succeeded(int error)
102 {
103 return error >= 0;
104 }
105
106 internal static long MakeMask(int offset, int bits)
107 {
108 return (long)(~0UL >> (64-bits)) << offset;
109 }
110
111 internal static int TryAllocate(ref long l, int offset, int bits)
112 {
113 var mask = MakeMask(offset, bits);
114 var readValue = Interlocked.Read(ref l);
115 long oldReadValue, writtenValue;
116 do
117 {
118 if((readValue & mask) != 0)
119 return ErrorFailedToAllocate;
120 writtenValue = readValue | mask;
121 oldReadValue = readValue;
122 readValue = Interlocked.CompareExchange(ref l, writtenValue, oldReadValue);
123 } while(readValue != oldReadValue);
124 return math.countbits(readValue); // how many bits were set, before i allocated? sometimes if 0, do something special (allocate chunk?)
125 }
126
127 internal static int TryFree(ref long l, int offset, int bits)
128 {
129 var mask = MakeMask(offset, bits);
130 var readValue = Interlocked.Read(ref l);
131 long oldReadValue, writtenValue;
132 do
133 {
134 if((readValue & mask) != mask)
135 return ErrorFailedToFree;
136 writtenValue = readValue & ~mask;
137 oldReadValue = readValue;
138 readValue = Interlocked.CompareExchange(ref l, writtenValue, oldReadValue);
139 } while(readValue != oldReadValue);
140 return math.countbits(writtenValue); // how many bits are set, after i freed? sometimes if 0, do something special (free chunk?)
141 }
142
143 internal static int TryAllocate(ref long l, out int offset, int bits)
144 {
145 var readValue = Interlocked.Read(ref l);
146 long oldReadValue, writtenValue;
147 do
148 {
149 if(!foundAtLeastThisManyConsecutiveZeroes(readValue, bits, out offset, out int _))
150 return ErrorFailedToAllocate;
151 var mask = MakeMask(offset, bits);
152 writtenValue = readValue | mask;
153 oldReadValue = readValue;
154 readValue = Interlocked.CompareExchange(ref l, writtenValue, oldReadValue);
155 } while(readValue != oldReadValue);
156 return math.countbits(readValue); // how many bits were set, before i allocated? sometimes if 0, do something special (allocate chunk?)
157 }
158
159 internal static int TryAllocate<T>(ref T t, int offset, int bits) where T : IIndexable<long>
160 {
161 var wordOffset = offset >> 6;
162 var bitOffset = offset & 63;
163 if(bitOffset + bits > 64)
164 return ErrorAllocationCrossesWordBoundary;
165 return TryAllocate(ref t.ElementAt(wordOffset), bitOffset, bits);
166 }
167
168 internal static int TryFree<T>(ref T t, int offset, int bits) where T : IIndexable<long>
169 {
170 var wordOffset = offset >> 6;
171 var bitOffset = offset & 63;
172 return TryFree(ref t.ElementAt(wordOffset), bitOffset, bits);
173 }
174
175 internal static int TryAllocate<T>(ref T t, out int offset, int begin, int end, int bits) where T : IIndexable<long>
176 {
177 var wordOffset = begin;
178 for(; wordOffset < end; ++wordOffset)
179 if(t.ElementAt(wordOffset) != ~0L)
180 break;
181 for(; wordOffset < end; ++wordOffset)
182 {
183 int error, bitOffset;
184 error = TryAllocate(ref t.ElementAt(wordOffset), out bitOffset, bits);
185 if(Succeeded(error))
186 {
187 offset = wordOffset * 64 + bitOffset;
188 return error;
189 }
190 }
191 offset = -1;
192 return ErrorFailedToAllocate;
193 }
194
195 internal static int TryAllocate<T>(ref T t, out int offset, int begin, int bits) where T : IIndexable<long>
196 {
197 var error = TryAllocate(ref t, out offset, begin, t.Length, bits);
198 if(Succeeded(error))
199 return error;
200 return TryAllocate(ref t, out offset, 0, begin, bits);
201 }
202
203 internal static int TryAllocate<T>(ref T t, out int offset, int bits) where T : IIndexable<long>
204 {
205 return TryAllocate(ref t, out offset, 0, t.Length, bits);
206 }
207
208 }
209}