mirror of
https://github.com/intel/intel-graphics-compiler.git
synced 2025-10-30 08:18:26 +08:00
608 lines
16 KiB
C++
608 lines
16 KiB
C++
/*========================== begin_copyright_notice ============================
|
|
|
|
Copyright (C) 2017-2021 Intel Corporation
|
|
|
|
SPDX-License-Identifier: MIT
|
|
|
|
============================= end_copyright_notice ===========================*/
|
|
|
|
#pragma once
|
|
|
|
#include "Object.h"
|
|
|
|
#ifndef ASSERT
|
|
#include "..\..\d3d\ibdw\d3ddebug.h"
|
|
#endif
|
|
|
|
namespace iSTD
|
|
{
|
|
|
|
/*****************************************************************************\
|
|
Template Parameters
|
|
\*****************************************************************************/
|
|
#define FastMaskTemplateList bool OrderedList
|
|
#define CFastMaskSetType CFastMask<OrderedList>
|
|
|
|
/*****************************************************************************\
|
|
|
|
Class:
|
|
FastMask
|
|
|
|
Description:
|
|
Simple ordered mask with minimal set list traversal
|
|
|
|
\*****************************************************************************/
|
|
template<FastMaskTemplateList>
|
|
class CFastMask
|
|
{
|
|
public:
|
|
CFastMask( unsigned int inSize );
|
|
virtual ~CFastMask();
|
|
|
|
inline bool IsValid( void ) const;
|
|
inline bool IsSet( unsigned int index ) const;
|
|
inline bool IsDirty ( void );
|
|
inline const unsigned int* GetMask(unsigned int &ioSetKey);
|
|
inline unsigned int GetSize();
|
|
inline unsigned int GetSetListSize();
|
|
inline void GetUnsortedSetList( unsigned int const** ioList, unsigned int &ioSize );
|
|
inline void GetSetList( unsigned int const** ioList, unsigned int &ioSize );
|
|
inline void SetBits( unsigned int index, unsigned int count );
|
|
inline void SetBit( unsigned int index );
|
|
inline void ClearBits( void );
|
|
inline void UnSetBit( unsigned int index );
|
|
inline void Resize ( unsigned int in_NewSize );
|
|
|
|
protected:
|
|
inline void SortSetList( void );
|
|
inline void CollapseSetList( void );
|
|
|
|
unsigned int* m_Mask;
|
|
unsigned int* m_SetList;
|
|
unsigned int m_Key;
|
|
unsigned int m_SortIdx;
|
|
unsigned int m_CollapseIdx;
|
|
unsigned int m_SetListSize;
|
|
unsigned int m_Capacity;
|
|
bool m_SortOnGet;
|
|
bool m_CollapseUnsorted;
|
|
};
|
|
|
|
/*****************************************************************************\
|
|
|
|
Function:
|
|
Constructor
|
|
|
|
Description:
|
|
Constructs a mask with the incoming size
|
|
|
|
\*****************************************************************************/
|
|
template<FastMaskTemplateList>
|
|
CFastMaskSetType::CFastMask( unsigned int inSize )
|
|
: m_Mask(0)
|
|
, m_SetList(0)
|
|
, m_Key(1)
|
|
, m_SortIdx(0)
|
|
, m_CollapseIdx(0)
|
|
, m_SetListSize(0)
|
|
, m_Capacity(inSize)
|
|
, m_SortOnGet(false)
|
|
, m_CollapseUnsorted(false)
|
|
{
|
|
ASSERT(inSize > 0);
|
|
|
|
if( inSize > 0 )
|
|
{
|
|
m_Mask = new unsigned int[m_Capacity];
|
|
m_SetList = new unsigned int[m_Capacity];
|
|
|
|
ASSERT(0 != m_Mask);
|
|
ASSERT(0 != m_SetList);
|
|
|
|
if( m_Mask && m_SetList )
|
|
{
|
|
// quick run up to next power of 2
|
|
while( (unsigned int)m_Key <= m_Capacity )
|
|
{
|
|
m_Key = m_Key << 1;
|
|
}
|
|
|
|
// clear mask
|
|
for( unsigned int i = 0; i < m_Capacity; i++ )
|
|
{
|
|
m_Mask[i] = m_Key;
|
|
}
|
|
}
|
|
else
|
|
{
|
|
SafeDeleteArray( m_Mask );
|
|
SafeDeleteArray( m_SetList );
|
|
}
|
|
}
|
|
}
|
|
|
|
/*****************************************************************************\
|
|
|
|
Function:
|
|
Destructor
|
|
|
|
Description:
|
|
Cleanup memory
|
|
|
|
\*****************************************************************************/
|
|
template<FastMaskTemplateList>
|
|
CFastMaskSetType::~CFastMask( void )
|
|
{
|
|
SafeDeleteArray(m_Mask);
|
|
SafeDeleteArray(m_SetList);
|
|
}
|
|
|
|
/*****************************************************************************\
|
|
|
|
Function:
|
|
IsValid
|
|
|
|
Description:
|
|
Returns whether the object has been constructed properly.
|
|
|
|
\*****************************************************************************/
|
|
template<FastMaskTemplateList>
|
|
bool CFastMaskSetType::IsValid( void ) const
|
|
{
|
|
return ( ( m_Mask != NULL ) && ( m_SetList != NULL ) );
|
|
}
|
|
|
|
/*****************************************************************************\
|
|
|
|
Function:
|
|
IsSet
|
|
|
|
Description:
|
|
Returns whether or not a bit has been set in the mask.
|
|
|
|
\*****************************************************************************/
|
|
template<FastMaskTemplateList>
|
|
bool CFastMaskSetType::IsSet( unsigned int index ) const
|
|
{
|
|
ASSERT( index < m_Capacity );
|
|
return ( m_Key != m_Mask[index] );
|
|
}
|
|
|
|
/*****************************************************************************\
|
|
|
|
Function:
|
|
IsDirty
|
|
|
|
Description:
|
|
Returns whether or not the mask is dirty
|
|
|
|
\*****************************************************************************/
|
|
template<FastMaskTemplateList>
|
|
bool CFastMaskSetType::IsDirty( void )
|
|
{
|
|
if( true == m_CollapseUnsorted )
|
|
{
|
|
CollapseSetList();
|
|
}
|
|
|
|
return (m_SetListSize > 0);
|
|
}
|
|
|
|
/*****************************************************************************\
|
|
|
|
Function:
|
|
GetMask
|
|
|
|
Description:
|
|
Get the current mask with the set key for use in optimal comparisons for
|
|
multiple bits.
|
|
|
|
\*****************************************************************************/
|
|
template<FastMaskTemplateList>
|
|
const unsigned int* CFastMaskSetType::GetMask( unsigned int &ioSetKey )
|
|
{
|
|
ioSetKey = m_Key;
|
|
|
|
return m_Mask;
|
|
}
|
|
|
|
/*****************************************************************************\
|
|
|
|
Function:
|
|
GetSize
|
|
|
|
Description:
|
|
Returns the number of possible indices.
|
|
|
|
\*****************************************************************************/
|
|
template<FastMaskTemplateList>
|
|
unsigned int CFastMaskSetType::GetSize( void )
|
|
{
|
|
return m_Capacity;
|
|
}
|
|
|
|
/*****************************************************************************\
|
|
|
|
Function:
|
|
GetSetListSize
|
|
|
|
Description:
|
|
Returns the number set indices
|
|
|
|
\*****************************************************************************/
|
|
template<FastMaskTemplateList>
|
|
unsigned int CFastMaskSetType::GetSetListSize( void )
|
|
{
|
|
if( true == m_CollapseUnsorted )
|
|
{
|
|
CollapseSetList();
|
|
}
|
|
|
|
return m_SetListSize;
|
|
}
|
|
|
|
/*****************************************************************************\
|
|
|
|
Function:
|
|
SetBits
|
|
|
|
Description:
|
|
Sets mask bits from index to count.
|
|
|
|
\*****************************************************************************/
|
|
template<FastMaskTemplateList>
|
|
void CFastMaskSetType::SetBits( unsigned int index, unsigned int count )
|
|
{
|
|
ASSERT( (index + count) <= m_Capacity );
|
|
for( unsigned int i = index; i < index + count; i++ )
|
|
{
|
|
if( m_Key == m_Mask[i] )
|
|
{
|
|
// when the user sets/un-sets bits often without a Get* then there
|
|
// exists a possibility of overrunning the setlist.
|
|
if( m_SetListSize >= m_Capacity )
|
|
{
|
|
CollapseSetList();
|
|
}
|
|
|
|
ASSERT(m_SetListSize < m_Capacity);
|
|
m_Mask[i] = m_SetListSize;
|
|
m_SetList[m_SetListSize++] = i;
|
|
|
|
if( OrderedList )
|
|
{
|
|
m_SortOnGet = true;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
/*****************************************************************************\
|
|
|
|
Function:
|
|
SetBit
|
|
|
|
Description:
|
|
Sets mask bit for index
|
|
|
|
\*****************************************************************************/
|
|
template<FastMaskTemplateList>
|
|
void CFastMaskSetType::SetBit( unsigned int index )
|
|
{
|
|
ASSERT( index < m_Capacity );
|
|
if( m_Key == m_Mask[index] )
|
|
{
|
|
if( m_SetListSize >= m_Capacity )
|
|
{
|
|
CollapseSetList();
|
|
}
|
|
|
|
ASSERT(m_SetListSize < m_Capacity);
|
|
m_Mask[index] = m_SetListSize;
|
|
m_SetList[m_SetListSize++] = index;
|
|
|
|
if( OrderedList )
|
|
{
|
|
m_SortOnGet = true;
|
|
}
|
|
}
|
|
}
|
|
|
|
/*****************************************************************************\
|
|
|
|
Function:
|
|
GetUnsortedSetList
|
|
|
|
Description:
|
|
Gets an unsorted set list as an override if the list is sorted but you don't
|
|
require sorting at this point.
|
|
|
|
\*****************************************************************************/
|
|
template<FastMaskTemplateList>
|
|
void CFastMaskSetType::GetUnsortedSetList( unsigned int const** ioList, unsigned int &ioSize )
|
|
{
|
|
if( true == m_CollapseUnsorted )
|
|
{
|
|
CollapseSetList();
|
|
}
|
|
|
|
*ioList = m_SetList;
|
|
ioSize = m_SetListSize;
|
|
}
|
|
|
|
/*****************************************************************************\
|
|
|
|
Function:
|
|
GetSetList
|
|
|
|
Description:
|
|
Gets the set list for traversal
|
|
|
|
\*****************************************************************************/
|
|
template<FastMaskTemplateList>
|
|
void CFastMaskSetType::GetSetList( unsigned int const** ioList, unsigned int &ioSize )
|
|
{
|
|
if( OrderedList && ( true == m_SortOnGet ) )
|
|
{
|
|
SortSetList();
|
|
}
|
|
else if( true == m_CollapseUnsorted )
|
|
{
|
|
CollapseSetList();
|
|
}
|
|
|
|
*ioList = m_SetList;
|
|
ioSize = m_SetListSize;
|
|
}
|
|
|
|
/*****************************************************************************\
|
|
|
|
Function:
|
|
ClearBits
|
|
|
|
Description:
|
|
Remove the bit from the list and mask if necessary
|
|
|
|
\*****************************************************************************/
|
|
template<FastMaskTemplateList>
|
|
void CFastMaskSetType::ClearBits( void )
|
|
{
|
|
unsigned int index = 0;
|
|
|
|
// walk the set list and remove set elements
|
|
for( unsigned int i = 0; i < m_SetListSize; i++ )
|
|
{
|
|
index = m_SetList[i];
|
|
|
|
// the user can un-set bits prior to calling clear and we need to ensure
|
|
// that we dont try to change those entries as they dont matter and could
|
|
// corrupt the heap
|
|
if( index != m_Key )
|
|
{
|
|
m_Mask[index] = m_Key;
|
|
}
|
|
}
|
|
|
|
m_SetListSize = 0;
|
|
m_SortIdx = 0;
|
|
m_CollapseIdx = 0;
|
|
m_SortOnGet = false;
|
|
m_CollapseUnsorted = false;
|
|
}
|
|
|
|
/*****************************************************************************\
|
|
|
|
Function:
|
|
UnSetBit
|
|
|
|
Description:
|
|
Remove the bit from the list and mask if necessary
|
|
|
|
\*****************************************************************************/
|
|
template<FastMaskTemplateList>
|
|
void CFastMaskSetType::UnSetBit( unsigned int index )
|
|
{
|
|
ASSERT( index < m_Capacity );
|
|
|
|
// we do not change the setlist size because we will rely
|
|
// upon the sort to remove those key elements
|
|
if( m_Key != m_Mask[index] )
|
|
{
|
|
// set that we need to collapse this list, required if we query an
|
|
// unsorted set from a sorted set list
|
|
m_CollapseUnsorted = true;
|
|
|
|
unsigned int setListPos = m_Mask[index];
|
|
if( setListPos < m_CollapseIdx )
|
|
{
|
|
m_CollapseIdx = setListPos; // we need to start our collapse at this index
|
|
}
|
|
|
|
// handle ordered list
|
|
if( OrderedList )
|
|
{
|
|
// if we are an ordered list we need to compare the index position
|
|
// with the current sort index and modify that index if necessary
|
|
if( setListPos < m_SortIdx )
|
|
{
|
|
m_SortIdx = setListPos; // move index down to allow for collapse
|
|
}
|
|
|
|
m_SortOnGet = true;
|
|
}
|
|
|
|
m_SetList[m_Mask[index]] = m_Key;
|
|
m_Mask[index] = m_Key;
|
|
}
|
|
}
|
|
|
|
/*****************************************************************************\
|
|
|
|
Function:
|
|
Resize
|
|
|
|
Description:
|
|
Resizes the FastMask.
|
|
|
|
\*****************************************************************************/
|
|
template<FastMaskTemplateList>
|
|
void CFastMaskSetType::Resize( unsigned int in_NewSize )
|
|
{
|
|
ASSERT(in_NewSize != 0);
|
|
|
|
if( in_NewSize == m_Capacity )
|
|
return;
|
|
|
|
unsigned int* old_m_SetList = m_SetList;
|
|
unsigned int old_m_SetListSize = m_SetListSize;
|
|
|
|
m_SetListSize = 0; //will be using SetBits() which will correct this value
|
|
m_CollapseIdx = 0;
|
|
m_SortIdx = 0;
|
|
m_Capacity = in_NewSize;
|
|
m_CollapseUnsorted = false;
|
|
m_SortOnGet = false;
|
|
|
|
SafeDeleteArray(m_Mask);
|
|
m_Mask = new unsigned int[m_Capacity];
|
|
m_SetList = new unsigned int[m_Capacity];
|
|
|
|
ASSERT(0 != m_Mask);
|
|
ASSERT(0 != m_SetList);
|
|
|
|
// save off old key
|
|
unsigned int old_m_Key = m_Key;
|
|
m_Key = 1;
|
|
|
|
// quick run up to next power of 2
|
|
while( (unsigned int)m_Key <= m_Capacity )
|
|
{
|
|
m_Key = m_Key << 1;
|
|
}
|
|
|
|
for( unsigned int i = 0; i < m_Capacity; i++)
|
|
{
|
|
m_Mask[i] = m_Key;
|
|
}
|
|
|
|
for( unsigned int i = 0; i < old_m_SetListSize; i++)
|
|
{
|
|
if(old_m_SetList[i] != old_m_Key)
|
|
{
|
|
SetBit(old_m_SetList[i]);
|
|
}
|
|
}
|
|
|
|
SafeDeleteArray(old_m_SetList);
|
|
}
|
|
|
|
/*****************************************************************************\
|
|
|
|
Function:
|
|
SortSetList
|
|
|
|
Description:
|
|
Sorts the set list, a modified insertion sort algorithm
|
|
http://en.wikipedia.org/wiki/Insertion_sort
|
|
|
|
\*****************************************************************************/
|
|
template<FastMaskTemplateList>
|
|
void CFastMaskSetType::SortSetList( )
|
|
{
|
|
// perform an insertion sort in place
|
|
unsigned int count = 0;
|
|
unsigned int keyVal = 0;
|
|
int idx;
|
|
|
|
for( unsigned int i = m_SortIdx; i < m_SetListSize; i++ )
|
|
{
|
|
keyVal = m_SetList[i];
|
|
|
|
// handle un-set bit
|
|
if( keyVal == m_Key )
|
|
{
|
|
count++; // increment number of un-set keys seen, these will
|
|
// automatically be sorted to the RHS of the list
|
|
}
|
|
|
|
idx = i - 1;
|
|
|
|
// find the sort position for this keyVal
|
|
while( idx >= 0 && m_SetList[idx] > keyVal )
|
|
{
|
|
m_SetList[idx+1] = m_SetList[idx];
|
|
idx--;
|
|
}
|
|
|
|
m_SetList[idx+1] = keyVal;
|
|
}
|
|
|
|
m_SetListSize -= count; // subtract off the number of un-set bits on the RHS
|
|
m_SortOnGet = false;
|
|
m_CollapseUnsorted = false;
|
|
m_SortIdx = ( m_SetListSize > 0 ) ? m_SetListSize - 1 : 0;
|
|
m_CollapseIdx = m_SortIdx;
|
|
|
|
// update the mask with the new positions
|
|
for( unsigned int i = 0; i < m_SetListSize; i++ )
|
|
{
|
|
m_Mask[m_SetList[i]] = i; // new index
|
|
}
|
|
}
|
|
|
|
/*****************************************************************************\
|
|
|
|
Function:
|
|
CollapseSetList
|
|
|
|
Description:
|
|
Removes any un-set bits from the set list
|
|
|
|
\*****************************************************************************/
|
|
|
|
template<FastMaskTemplateList>
|
|
void CFastMaskSetType::CollapseSetList( )
|
|
{
|
|
// walk the set list and collapse by skipping over un-set elements
|
|
unsigned int count = m_CollapseIdx;
|
|
|
|
for( unsigned int i = m_CollapseIdx; i < m_SetListSize; i++ )
|
|
{
|
|
if( m_Key != m_SetList[i] )
|
|
{
|
|
m_Mask[m_SetList[i]] = count; // update mask with new position
|
|
m_SetList[count++] = m_SetList[i];
|
|
}
|
|
}
|
|
|
|
m_CollapseUnsorted = false;
|
|
m_SetListSize = count;
|
|
|
|
if( 0 == m_SetListSize )
|
|
{
|
|
m_SortIdx = 0;
|
|
m_CollapseIdx = 0;
|
|
|
|
if( OrderedList )
|
|
{
|
|
m_SortOnGet = false; // no need to sort if empty
|
|
}
|
|
}
|
|
else
|
|
{
|
|
if( m_CollapseIdx < m_SortIdx )
|
|
{
|
|
m_SortIdx = m_CollapseIdx;
|
|
|
|
if( OrderedList )
|
|
{
|
|
m_SortOnGet = true;
|
|
}
|
|
}
|
|
|
|
m_CollapseIdx = m_SetListSize - 1;
|
|
}
|
|
}
|
|
|
|
} // iSTD
|