1 /*========================== begin_copyright_notice ============================
2
3 Copyright (C) 2017-2021 Intel Corporation
4
5 SPDX-License-Identifier: MIT
6
7 ============================= end_copyright_notice ===========================*/
8
9 #pragma once
10
11 #include "Object.h"
12
13 #ifndef ASSERT
14 #include "..\..\d3d\ibdw\d3ddebug.h"
15 #endif
16
17 namespace iSTD
18 {
19
20 /*****************************************************************************\
21 Template Parameters
22 \*****************************************************************************/
23 #define FastMaskTemplateList bool OrderedList
24 #define CFastMaskSetType CFastMask<OrderedList>
25
26 /*****************************************************************************\
27
28 Class:
29 FastMask
30
31 Description:
32 Simple ordered mask with minimal set list traversal
33
34 \*****************************************************************************/
35 template<FastMaskTemplateList>
36 class CFastMask
37 {
38 public:
39 CFastMask( unsigned int inSize );
40 virtual ~CFastMask();
41
42 inline bool IsValid( void ) const;
43 inline bool IsSet( unsigned int index ) const;
44 inline bool IsDirty ( void );
45 inline const unsigned int* GetMask(unsigned int &ioSetKey);
46 inline unsigned int GetSize();
47 inline unsigned int GetSetListSize();
48 inline void GetUnsortedSetList( unsigned int const** ioList, unsigned int &ioSize );
49 inline void GetSetList( unsigned int const** ioList, unsigned int &ioSize );
50 inline void SetBits( unsigned int index, unsigned int count );
51 inline void SetBit( unsigned int index );
52 inline void ClearBits( void );
53 inline void UnSetBit( unsigned int index );
54 inline void Resize ( unsigned int in_NewSize );
55
56 protected:
57 inline void SortSetList( void );
58 inline void CollapseSetList( void );
59
60 unsigned int* m_Mask;
61 unsigned int* m_SetList;
62 unsigned int m_Key;
63 unsigned int m_SortIdx;
64 unsigned int m_CollapseIdx;
65 unsigned int m_SetListSize;
66 unsigned int m_Capacity;
67 bool m_SortOnGet;
68 bool m_CollapseUnsorted;
69 };
70
71 /*****************************************************************************\
72
73 Function:
74 Constructor
75
76 Description:
77 Constructs a mask with the incoming size
78
79 \*****************************************************************************/
80 template<FastMaskTemplateList>
CFastMask(unsigned int inSize)81 CFastMaskSetType::CFastMask( unsigned int inSize )
82 : m_Mask(0)
83 , m_SetList(0)
84 , m_Key(1)
85 , m_SortIdx(0)
86 , m_CollapseIdx(0)
87 , m_SetListSize(0)
88 , m_Capacity(inSize)
89 , m_SortOnGet(false)
90 , m_CollapseUnsorted(false)
91 {
92 ASSERT(inSize > 0);
93
94 if( inSize > 0 )
95 {
96 m_Mask = new unsigned int[m_Capacity];
97 m_SetList = new unsigned int[m_Capacity];
98
99 ASSERT(0 != m_Mask);
100 ASSERT(0 != m_SetList);
101
102 if( m_Mask && m_SetList )
103 {
104 // quick run up to next power of 2
105 while( (unsigned int)m_Key <= m_Capacity )
106 {
107 m_Key = m_Key << 1;
108 }
109
110 // clear mask
111 for( unsigned int i = 0; i < m_Capacity; i++ )
112 {
113 m_Mask[i] = m_Key;
114 }
115 }
116 else
117 {
118 SafeDeleteArray( m_Mask );
119 SafeDeleteArray( m_SetList );
120 }
121 }
122 }
123
124 /*****************************************************************************\
125
126 Function:
127 Destructor
128
129 Description:
130 Cleanup memory
131
132 \*****************************************************************************/
133 template<FastMaskTemplateList>
~CFastMask(void)134 CFastMaskSetType::~CFastMask( void )
135 {
136 SafeDeleteArray(m_Mask);
137 SafeDeleteArray(m_SetList);
138 }
139
140 /*****************************************************************************\
141
142 Function:
143 IsValid
144
145 Description:
146 Returns whether the object has been constructed properly.
147
148 \*****************************************************************************/
149 template<FastMaskTemplateList>
IsValid(void)150 bool CFastMaskSetType::IsValid( void ) const
151 {
152 return ( ( m_Mask != NULL ) && ( m_SetList != NULL ) );
153 }
154
155 /*****************************************************************************\
156
157 Function:
158 IsSet
159
160 Description:
161 Returns whether or not a bit has been set in the mask.
162
163 \*****************************************************************************/
164 template<FastMaskTemplateList>
IsSet(unsigned int index)165 bool CFastMaskSetType::IsSet( unsigned int index ) const
166 {
167 ASSERT( index < m_Capacity );
168 return ( m_Key != m_Mask[index] );
169 }
170
171 /*****************************************************************************\
172
173 Function:
174 IsDirty
175
176 Description:
177 Returns whether or not the mask is dirty
178
179 \*****************************************************************************/
180 template<FastMaskTemplateList>
IsDirty(void)181 bool CFastMaskSetType::IsDirty( void )
182 {
183 if( true == m_CollapseUnsorted )
184 {
185 CollapseSetList();
186 }
187
188 return (m_SetListSize > 0);
189 }
190
191 /*****************************************************************************\
192
193 Function:
194 GetMask
195
196 Description:
197 Get the current mask with the set key for use in optimal comparisons for
198 multiple bits.
199
200 \*****************************************************************************/
201 template<FastMaskTemplateList>
GetMask(unsigned int & ioSetKey)202 const unsigned int* CFastMaskSetType::GetMask( unsigned int &ioSetKey )
203 {
204 ioSetKey = m_Key;
205
206 return m_Mask;
207 }
208
209 /*****************************************************************************\
210
211 Function:
212 GetSize
213
214 Description:
215 Returns the number of possible indices.
216
217 \*****************************************************************************/
218 template<FastMaskTemplateList>
GetSize(void)219 unsigned int CFastMaskSetType::GetSize( void )
220 {
221 return m_Capacity;
222 }
223
224 /*****************************************************************************\
225
226 Function:
227 GetSetListSize
228
229 Description:
230 Returns the number set indices
231
232 \*****************************************************************************/
233 template<FastMaskTemplateList>
GetSetListSize(void)234 unsigned int CFastMaskSetType::GetSetListSize( void )
235 {
236 if( true == m_CollapseUnsorted )
237 {
238 CollapseSetList();
239 }
240
241 return m_SetListSize;
242 }
243
244 /*****************************************************************************\
245
246 Function:
247 SetBits
248
249 Description:
250 Sets mask bits from index to count.
251
252 \*****************************************************************************/
253 template<FastMaskTemplateList>
SetBits(unsigned int index,unsigned int count)254 void CFastMaskSetType::SetBits( unsigned int index, unsigned int count )
255 {
256 ASSERT( (index + count) <= m_Capacity );
257 for( unsigned int i = index; i < index + count; i++ )
258 {
259 if( m_Key == m_Mask[i] )
260 {
261 // when the user sets/un-sets bits often without a Get* then there
262 // exists a possibility of overrunning the setlist.
263 if( m_SetListSize >= m_Capacity )
264 {
265 CollapseSetList();
266 }
267
268 ASSERT(m_SetListSize < m_Capacity);
269 m_Mask[i] = m_SetListSize;
270 m_SetList[m_SetListSize++] = i;
271
272 if( OrderedList )
273 {
274 m_SortOnGet = true;
275 }
276 }
277 }
278 }
279
280 /*****************************************************************************\
281
282 Function:
283 SetBit
284
285 Description:
286 Sets mask bit for index
287
288 \*****************************************************************************/
289 template<FastMaskTemplateList>
SetBit(unsigned int index)290 void CFastMaskSetType::SetBit( unsigned int index )
291 {
292 ASSERT( index < m_Capacity );
293 if( m_Key == m_Mask[index] )
294 {
295 if( m_SetListSize >= m_Capacity )
296 {
297 CollapseSetList();
298 }
299
300 ASSERT(m_SetListSize < m_Capacity);
301 m_Mask[index] = m_SetListSize;
302 m_SetList[m_SetListSize++] = index;
303
304 if( OrderedList )
305 {
306 m_SortOnGet = true;
307 }
308 }
309 }
310
311 /*****************************************************************************\
312
313 Function:
314 GetUnsortedSetList
315
316 Description:
317 Gets an unsorted set list as an override if the list is sorted but you don't
318 require sorting at this point.
319
320 \*****************************************************************************/
321 template<FastMaskTemplateList>
GetUnsortedSetList(unsigned int const ** ioList,unsigned int & ioSize)322 void CFastMaskSetType::GetUnsortedSetList( unsigned int const** ioList, unsigned int &ioSize )
323 {
324 if( true == m_CollapseUnsorted )
325 {
326 CollapseSetList();
327 }
328
329 *ioList = m_SetList;
330 ioSize = m_SetListSize;
331 }
332
333 /*****************************************************************************\
334
335 Function:
336 GetSetList
337
338 Description:
339 Gets the set list for traversal
340
341 \*****************************************************************************/
342 template<FastMaskTemplateList>
GetSetList(unsigned int const ** ioList,unsigned int & ioSize)343 void CFastMaskSetType::GetSetList( unsigned int const** ioList, unsigned int &ioSize )
344 {
345 if( OrderedList && ( true == m_SortOnGet ) )
346 {
347 SortSetList();
348 }
349 else if( true == m_CollapseUnsorted )
350 {
351 CollapseSetList();
352 }
353
354 *ioList = m_SetList;
355 ioSize = m_SetListSize;
356 }
357
358 /*****************************************************************************\
359
360 Function:
361 ClearBits
362
363 Description:
364 Remove the bit from the list and mask if necessary
365
366 \*****************************************************************************/
367 template<FastMaskTemplateList>
ClearBits(void)368 void CFastMaskSetType::ClearBits( void )
369 {
370 unsigned int index = 0;
371
372 // walk the set list and remove set elements
373 for( unsigned int i = 0; i < m_SetListSize; i++ )
374 {
375 index = m_SetList[i];
376
377 // the user can un-set bits prior to calling clear and we need to ensure
378 // that we dont try to change those entries as they dont matter and could
379 // corrupt the heap
380 if( index != m_Key )
381 {
382 m_Mask[index] = m_Key;
383 }
384 }
385
386 m_SetListSize = 0;
387 m_SortIdx = 0;
388 m_CollapseIdx = 0;
389 m_SortOnGet = false;
390 m_CollapseUnsorted = false;
391 }
392
393 /*****************************************************************************\
394
395 Function:
396 UnSetBit
397
398 Description:
399 Remove the bit from the list and mask if necessary
400
401 \*****************************************************************************/
402 template<FastMaskTemplateList>
UnSetBit(unsigned int index)403 void CFastMaskSetType::UnSetBit( unsigned int index )
404 {
405 ASSERT( index < m_Capacity );
406
407 // we do not change the setlist size because we will rely
408 // upon the sort to remove those key elements
409 if( m_Key != m_Mask[index] )
410 {
411 // set that we need to collapse this list, required if we query an
412 // unsorted set from a sorted set list
413 m_CollapseUnsorted = true;
414
415 unsigned int setListPos = m_Mask[index];
416 if( setListPos < m_CollapseIdx )
417 {
418 m_CollapseIdx = setListPos; // we need to start our collapse at this index
419 }
420
421 // handle ordered list
422 if( OrderedList )
423 {
424 // if we are an ordered list we need to compare the index position
425 // with the current sort index and modify that index if necessary
426 if( setListPos < m_SortIdx )
427 {
428 m_SortIdx = setListPos; // move index down to allow for collapse
429 }
430
431 m_SortOnGet = true;
432 }
433
434 m_SetList[m_Mask[index]] = m_Key;
435 m_Mask[index] = m_Key;
436 }
437 }
438
439 /*****************************************************************************\
440
441 Function:
442 Resize
443
444 Description:
445 Resizes the FastMask.
446
447 \*****************************************************************************/
448 template<FastMaskTemplateList>
Resize(unsigned int in_NewSize)449 void CFastMaskSetType::Resize( unsigned int in_NewSize )
450 {
451 ASSERT(in_NewSize != 0);
452
453 if( in_NewSize == m_Capacity )
454 return;
455
456 unsigned int* old_m_SetList = m_SetList;
457 unsigned int old_m_SetListSize = m_SetListSize;
458
459 m_SetListSize = 0; //will be using SetBits() which will correct this value
460 m_CollapseIdx = 0;
461 m_SortIdx = 0;
462 m_Capacity = in_NewSize;
463 m_CollapseUnsorted = false;
464 m_SortOnGet = false;
465
466 SafeDeleteArray(m_Mask);
467 m_Mask = new unsigned int[m_Capacity];
468 m_SetList = new unsigned int[m_Capacity];
469
470 ASSERT(0 != m_Mask);
471 ASSERT(0 != m_SetList);
472
473 // save off old key
474 unsigned int old_m_Key = m_Key;
475 m_Key = 1;
476
477 // quick run up to next power of 2
478 while( (unsigned int)m_Key <= m_Capacity )
479 {
480 m_Key = m_Key << 1;
481 }
482
483 for( unsigned int i = 0; i < m_Capacity; i++)
484 {
485 m_Mask[i] = m_Key;
486 }
487
488 for( unsigned int i = 0; i < old_m_SetListSize; i++)
489 {
490 if(old_m_SetList[i] != old_m_Key)
491 {
492 SetBit(old_m_SetList[i]);
493 }
494 }
495
496 SafeDeleteArray(old_m_SetList);
497 }
498
499 /*****************************************************************************\
500
501 Function:
502 SortSetList
503
504 Description:
505 Sorts the set list, a modified insertion sort algorithm
506 http://en.wikipedia.org/wiki/Insertion_sort
507
508 \*****************************************************************************/
509 template<FastMaskTemplateList>
SortSetList()510 void CFastMaskSetType::SortSetList( )
511 {
512 // perform an insertion sort in place
513 unsigned int count = 0;
514 unsigned int keyVal = 0;
515 int idx;
516
517 for( unsigned int i = m_SortIdx; i < m_SetListSize; i++ )
518 {
519 keyVal = m_SetList[i];
520
521 // handle un-set bit
522 if( keyVal == m_Key )
523 {
524 count++; // increment number of un-set keys seen, these will
525 // automatically be sorted to the RHS of the list
526 }
527
528 idx = i - 1;
529
530 // find the sort position for this keyVal
531 while( idx >= 0 && m_SetList[idx] > keyVal )
532 {
533 m_SetList[idx+1] = m_SetList[idx];
534 idx--;
535 }
536
537 m_SetList[idx+1] = keyVal;
538 }
539
540 m_SetListSize -= count; // subtract off the number of un-set bits on the RHS
541 m_SortOnGet = false;
542 m_CollapseUnsorted = false;
543 m_SortIdx = ( m_SetListSize > 0 ) ? m_SetListSize - 1 : 0;
544 m_CollapseIdx = m_SortIdx;
545
546 // update the mask with the new positions
547 for( unsigned int i = 0; i < m_SetListSize; i++ )
548 {
549 m_Mask[m_SetList[i]] = i; // new index
550 }
551 }
552
553 /*****************************************************************************\
554
555 Function:
556 CollapseSetList
557
558 Description:
559 Removes any un-set bits from the set list
560
561 \*****************************************************************************/
562
563 template<FastMaskTemplateList>
CollapseSetList()564 void CFastMaskSetType::CollapseSetList( )
565 {
566 // walk the set list and collapse by skipping over un-set elements
567 unsigned int count = m_CollapseIdx;
568
569 for( unsigned int i = m_CollapseIdx; i < m_SetListSize; i++ )
570 {
571 if( m_Key != m_SetList[i] )
572 {
573 m_Mask[m_SetList[i]] = count; // update mask with new position
574 m_SetList[count++] = m_SetList[i];
575 }
576 }
577
578 m_CollapseUnsorted = false;
579 m_SetListSize = count;
580
581 if( 0 == m_SetListSize )
582 {
583 m_SortIdx = 0;
584 m_CollapseIdx = 0;
585
586 if( OrderedList )
587 {
588 m_SortOnGet = false; // no need to sort if empty
589 }
590 }
591 else
592 {
593 if( m_CollapseIdx < m_SortIdx )
594 {
595 m_SortIdx = m_CollapseIdx;
596
597 if( OrderedList )
598 {
599 m_SortOnGet = true;
600 }
601 }
602
603 m_CollapseIdx = m_SetListSize - 1;
604 }
605 }
606
607 } // iSTD
608