OpenBarnyard
 
Loading...
Searching...
No Matches
TBitArray.cpp
Go to the documentation of this file.
1#include "ToshiPCH.h"
2#include "TBitArray.h"
3
4//-----------------------------------------------------------------------------
5// Enables memory debugging.
6// Note: Should be the last include!
7//-----------------------------------------------------------------------------
8#include "Core/TMemoryDebugOn.h"
9
10TOSHI_NAMESPACE_START
11
12#define MIN_NUM_BITS ( 8 * sizeof( TUINT32 ) )
13#define BIT_SUBNUM_MASK ( MIN_NUM_BITS - 1 )
14
15TBitArray::TBitArray( TINT a_iNumBits, TINT a_iInitialiseWith )
16{
17 Create( a_iNumBits, a_iInitialiseWith );
18}
19
24
25TINT TBitArray::GetNumAllocatedBytes() const
26{
27 return sizeof( TUINT32 ) * ( ( m_iSize + BIT_SUBNUM_MASK ) / MIN_NUM_BITS );
28}
29
30TINT TBitArray::FindFirstClearBit()
31{
32 TUINT uiNumElements = GetNumAllocatedBytes() / sizeof( TUINT32 );
33
34 // This is... um... amazing... in some way
35 // I know I could do this with a for cycle or even macro but I just had some great time meditating while writing this
36 // And yep, there's no for cycle in the original code too
37 for ( TUINT i = 0; i < uiNumElements; i++ )
38 {
39 if ( ( m_pBuffer[ i ] & ( 1U << 0U ) ) == 0 )
40 return MIN_NUM_BITS * i + 0;
41 if ( ( m_pBuffer[ i ] & ( 1U << 1U ) ) == 0 )
42 return MIN_NUM_BITS * i + 1;
43 if ( ( m_pBuffer[ i ] & ( 1U << 2U ) ) == 0 )
44 return MIN_NUM_BITS * i + 2;
45 if ( ( m_pBuffer[ i ] & ( 1U << 3U ) ) == 0 )
46 return MIN_NUM_BITS * i + 3;
47 if ( ( m_pBuffer[ i ] & ( 1U << 4U ) ) == 0 )
48 return MIN_NUM_BITS * i + 4;
49 if ( ( m_pBuffer[ i ] & ( 1U << 5U ) ) == 0 )
50 return MIN_NUM_BITS * i + 5;
51 if ( ( m_pBuffer[ i ] & ( 1U << 6U ) ) == 0 )
52 return MIN_NUM_BITS * i + 6;
53 if ( ( m_pBuffer[ i ] & ( 1U << 7U ) ) == 0 )
54 return MIN_NUM_BITS * i + 7;
55 if ( ( m_pBuffer[ i ] & ( 1U << 8U ) ) == 0 )
56 return MIN_NUM_BITS * i + 8;
57 if ( ( m_pBuffer[ i ] & ( 1U << 9U ) ) == 0 )
58 return MIN_NUM_BITS * i + 9;
59 if ( ( m_pBuffer[ i ] & ( 1U << 10U ) ) == 0 )
60 return MIN_NUM_BITS * i + 10;
61 if ( ( m_pBuffer[ i ] & ( 1U << 11U ) ) == 0 )
62 return MIN_NUM_BITS * i + 11;
63 if ( ( m_pBuffer[ i ] & ( 1U << 12U ) ) == 0 )
64 return MIN_NUM_BITS * i + 12;
65 if ( ( m_pBuffer[ i ] & ( 1U << 13U ) ) == 0 )
66 return MIN_NUM_BITS * i + 13;
67 if ( ( m_pBuffer[ i ] & ( 1U << 14U ) ) == 0 )
68 return MIN_NUM_BITS * i + 14;
69 if ( ( m_pBuffer[ i ] & ( 1U << 15U ) ) == 0 )
70 return MIN_NUM_BITS * i + 15;
71 if ( ( m_pBuffer[ i ] & ( 1U << 16U ) ) == 0 )
72 return MIN_NUM_BITS * i + 16;
73 if ( ( m_pBuffer[ i ] & ( 1U << 17U ) ) == 0 )
74 return MIN_NUM_BITS * i + 17;
75 if ( ( m_pBuffer[ i ] & ( 1U << 18U ) ) == 0 )
76 return MIN_NUM_BITS * i + 18;
77 if ( ( m_pBuffer[ i ] & ( 1U << 19U ) ) == 0 )
78 return MIN_NUM_BITS * i + 19;
79 if ( ( m_pBuffer[ i ] & ( 1U << 20U ) ) == 0 )
80 return MIN_NUM_BITS * i + 20;
81 if ( ( m_pBuffer[ i ] & ( 1U << 21U ) ) == 0 )
82 return MIN_NUM_BITS * i + 21;
83 if ( ( m_pBuffer[ i ] & ( 1U << 22U ) ) == 0 )
84 return MIN_NUM_BITS * i + 22;
85 if ( ( m_pBuffer[ i ] & ( 1U << 23U ) ) == 0 )
86 return MIN_NUM_BITS * i + 23;
87 if ( ( m_pBuffer[ i ] & ( 1U << 24U ) ) == 0 )
88 return MIN_NUM_BITS * i + 24;
89 if ( ( m_pBuffer[ i ] & ( 1U << 25U ) ) == 0 )
90 return MIN_NUM_BITS * i + 25;
91 if ( ( m_pBuffer[ i ] & ( 1U << 26U ) ) == 0 )
92 return MIN_NUM_BITS * i + 26;
93 if ( ( m_pBuffer[ i ] & ( 1U << 27U ) ) == 0 )
94 return MIN_NUM_BITS * i + 27;
95 if ( ( m_pBuffer[ i ] & ( 1U << 28U ) ) == 0 )
96 return MIN_NUM_BITS * i + 28;
97 if ( ( m_pBuffer[ i ] & ( 1U << 29U ) ) == 0 )
98 return MIN_NUM_BITS * i + 29;
99 if ( ( m_pBuffer[ i ] & ( 1U << 30U ) ) == 0 )
100 return MIN_NUM_BITS * i + 30;
101 if ( ( m_pBuffer[ i ] & ( 1U << 31U ) ) == 0 )
102 return MIN_NUM_BITS * i + 31;
103 }
104
105 return -1;
106}
107
108TINT TBitArray::FindFirstSetBit()
109{
110 TUINT uiNumElements = GetNumAllocatedBytes() / sizeof( TUINT32 );
111
112 // This is... um... amazing... in some way
113 // I know I could do this with a for cycle or even macro but I just had some great time meditating while writing this
114 // And yep, there's no for cycle in the original code too
115 for ( TUINT i = 0; i < uiNumElements; i++ )
116 {
117 if ( ( m_pBuffer[ i ] & ( 1U << 0U ) ) != 0 )
118 return MIN_NUM_BITS * i + 0;
119 if ( ( m_pBuffer[ i ] & ( 1U << 1U ) ) != 0 )
120 return MIN_NUM_BITS * i + 1;
121 if ( ( m_pBuffer[ i ] & ( 1U << 2U ) ) != 0 )
122 return MIN_NUM_BITS * i + 2;
123 if ( ( m_pBuffer[ i ] & ( 1U << 3U ) ) != 0 )
124 return MIN_NUM_BITS * i + 3;
125 if ( ( m_pBuffer[ i ] & ( 1U << 4U ) ) != 0 )
126 return MIN_NUM_BITS * i + 4;
127 if ( ( m_pBuffer[ i ] & ( 1U << 5U ) ) != 0 )
128 return MIN_NUM_BITS * i + 5;
129 if ( ( m_pBuffer[ i ] & ( 1U << 6U ) ) != 0 )
130 return MIN_NUM_BITS * i + 6;
131 if ( ( m_pBuffer[ i ] & ( 1U << 7U ) ) != 0 )
132 return MIN_NUM_BITS * i + 7;
133 if ( ( m_pBuffer[ i ] & ( 1U << 8U ) ) != 0 )
134 return MIN_NUM_BITS * i + 8;
135 if ( ( m_pBuffer[ i ] & ( 1U << 9U ) ) != 0 )
136 return MIN_NUM_BITS * i + 9;
137 if ( ( m_pBuffer[ i ] & ( 1U << 10U ) ) != 0 )
138 return MIN_NUM_BITS * i + 10;
139 if ( ( m_pBuffer[ i ] & ( 1U << 11U ) ) != 0 )
140 return MIN_NUM_BITS * i + 11;
141 if ( ( m_pBuffer[ i ] & ( 1U << 12U ) ) != 0 )
142 return MIN_NUM_BITS * i + 12;
143 if ( ( m_pBuffer[ i ] & ( 1U << 13U ) ) != 0 )
144 return MIN_NUM_BITS * i + 13;
145 if ( ( m_pBuffer[ i ] & ( 1U << 14U ) ) != 0 )
146 return MIN_NUM_BITS * i + 14;
147 if ( ( m_pBuffer[ i ] & ( 1U << 15U ) ) != 0 )
148 return MIN_NUM_BITS * i + 15;
149 if ( ( m_pBuffer[ i ] & ( 1U << 16U ) ) != 0 )
150 return MIN_NUM_BITS * i + 16;
151 if ( ( m_pBuffer[ i ] & ( 1U << 17U ) ) != 0 )
152 return MIN_NUM_BITS * i + 17;
153 if ( ( m_pBuffer[ i ] & ( 1U << 18U ) ) != 0 )
154 return MIN_NUM_BITS * i + 18;
155 if ( ( m_pBuffer[ i ] & ( 1U << 19U ) ) != 0 )
156 return MIN_NUM_BITS * i + 19;
157 if ( ( m_pBuffer[ i ] & ( 1U << 20U ) ) != 0 )
158 return MIN_NUM_BITS * i + 20;
159 if ( ( m_pBuffer[ i ] & ( 1U << 21U ) ) != 0 )
160 return MIN_NUM_BITS * i + 21;
161 if ( ( m_pBuffer[ i ] & ( 1U << 22U ) ) != 0 )
162 return MIN_NUM_BITS * i + 22;
163 if ( ( m_pBuffer[ i ] & ( 1U << 23U ) ) != 0 )
164 return MIN_NUM_BITS * i + 23;
165 if ( ( m_pBuffer[ i ] & ( 1U << 24U ) ) != 0 )
166 return MIN_NUM_BITS * i + 24;
167 if ( ( m_pBuffer[ i ] & ( 1U << 25U ) ) != 0 )
168 return MIN_NUM_BITS * i + 25;
169 if ( ( m_pBuffer[ i ] & ( 1U << 26U ) ) != 0 )
170 return MIN_NUM_BITS * i + 26;
171 if ( ( m_pBuffer[ i ] & ( 1U << 27U ) ) != 0 )
172 return MIN_NUM_BITS * i + 27;
173 if ( ( m_pBuffer[ i ] & ( 1U << 28U ) ) != 0 )
174 return MIN_NUM_BITS * i + 28;
175 if ( ( m_pBuffer[ i ] & ( 1U << 29U ) ) != 0 )
176 return MIN_NUM_BITS * i + 29;
177 if ( ( m_pBuffer[ i ] & ( 1U << 30U ) ) != 0 )
178 return MIN_NUM_BITS * i + 30;
179 if ( ( m_pBuffer[ i ] & ( 1U << 31U ) ) != 0 )
180 return MIN_NUM_BITS * i + 31;
181 }
182
183 return -1;
184}
185
186TINT TBitArray::GetBit( TINT a_iIndex ) const
187{
188 TASSERT( a_iIndex < m_iSize );
189
190 return ( m_pBuffer[ a_iIndex / MIN_NUM_BITS ] & ( 1 << ( a_iIndex % m_iSize ) ) );
191}
192
193void TBitArray::ClearBit( TINT a_iIndex )
194{
195 TASSERT( a_iIndex < m_iSize );
196
197 TUINT uiBit = 1 << ( a_iIndex % m_iSize );
198 m_pBuffer[ a_iIndex / MIN_NUM_BITS ] &= ~uiBit;
199}
200
201void TBitArray::ToggleBit( TINT a_iIndex )
202{
203 TASSERT( a_iIndex < m_iSize );
204
205 TUINT uiBit = 1 << ( a_iIndex % m_iSize );
206 m_pBuffer[ a_iIndex / MIN_NUM_BITS ] ^= uiBit;
207}
208
209void TBitArray::SetBit( TINT a_iIndex )
210{
211 TASSERT( a_iIndex < m_iSize );
212
213 TUINT uiBit = 1 << ( a_iIndex % m_iSize );
214 m_pBuffer[ a_iIndex / MIN_NUM_BITS ] |= uiBit;
215}
216
217void TBitArray::SetBit( TINT a_iIndex, TINT a_iValue )
218{
219 TASSERT( a_iIndex < m_iSize );
220
221 TUINT uiBit = 1 << ( a_iIndex % m_iSize );
222
223 if ( a_iValue == 0 ) m_pBuffer[ a_iIndex / MIN_NUM_BITS ] &= ~uiBit;
224 else
225 m_pBuffer[ a_iIndex / MIN_NUM_BITS ] |= uiBit;
226}
227
228void TBitArray::Reset()
229{
230 TUINT uiNumElements = GetNumAllocatedBytes() / sizeof( TUINT32 );
231
232 for ( TUINT i = 0; i < uiNumElements; i++ )
233 {
234 m_pBuffer[ i ] = m_uiInitialisedWith;
235 }
236}
237
238void TBitArray::Destroy()
239{
240 if ( m_pBuffer )
241 delete m_pBuffer;
242
243 m_pBuffer = TNULL;
244}
245
246void TBitArray::Create( TINT a_iNumBits, TINT a_iInitialiseWith )
247{
248 m_iSize = a_iNumBits;
249 m_uiInitialisedWith = ( a_iInitialiseWith == 0 ) ? 0 : 0xFFFFFFFF;
250
251 m_pBuffer = new TUINT32[ GetNumAllocatedBytes() / sizeof( TUINT32 ) ];
252 TVALIDPTR( m_pBuffer );
253
254 Reset();
255}
256
257TOSHI_NAMESPACE_END
TASSERT
#define TASSERT(X,...)
Definition Defines.h:138
TOSHI_NAMESPACE_START
#define TOSHI_NAMESPACE_START
Definition Defines.h:47
TOSHI_NAMESPACE_END
#define TOSHI_NAMESPACE_END
Definition Defines.h:50
TVALIDPTR
#define TVALIDPTR(PTR)
Definition Defines.h:139
BIT_SUBNUM_MASK
#define BIT_SUBNUM_MASK
Definition TBitArray.cpp:13
MIN_NUM_BITS
#define MIN_NUM_BITS
Definition TBitArray.cpp:12
TUINT
unsigned int TUINT
Definition Typedefs.h:8
TNULL
#define TNULL
Definition Typedefs.h:23
TUINT32
uint32_t TUINT32
Definition Typedefs.h:13
TINT
int TINT
Definition Typedefs.h:7
TBitArray::FindFirstSetBit
TINT FindFirstSetBit()
Definition TBitArray.cpp:108
TBitArray::Destroy
void Destroy()
Definition TBitArray.cpp:238
TBitArray::SetBit
void SetBit(TINT a_iIndex, TINT a_iValue)
Definition TBitArray.cpp:217
TBitArray::ClearBit
void ClearBit(TINT a_iIndex)
Definition TBitArray.cpp:193
TBitArray::GetNumAllocatedBytes
TINT GetNumAllocatedBytes() const
Definition TBitArray.cpp:25
TBitArray::FindFirstClearBit
TINT FindFirstClearBit()
Definition TBitArray.cpp:30
TBitArray::Reset
void Reset()
Definition TBitArray.cpp:228
TBitArray::GetBit
TINT GetBit(TINT a_iIndex) const
Definition TBitArray.cpp:186
TBitArray::Create
void Create(TINT a_iNumBits, TINT a_iInitialiseWith)
Definition TBitArray.cpp:246
TBitArray::TBitArray
constexpr TBitArray()
Definition TBitArray.h:9
TBitArray::ToggleBit
void ToggleBit(TINT a_iIndex)
Definition TBitArray.cpp:201