greenplumn CBitVector 源码

2022-08-18
浏览 (281)

greenplumn CBitVector 代码

文件路径：/src/backend/gporca/libgpos/src/common/CBitVector.cpp

//---------------------------------------------------------------------------
//	Greenplum Database
//	Copyright (C) 2008 Greenplum, Inc.
//
//	@filename:
//		CBitVector.cpp
//
//	@doc:
//		Implementation of simple, static bit vector class
//---------------------------------------------------------------------------


#include "gpos/common/CBitVector.h"

#include "gpos/base.h"
#include "gpos/common/CAutoRg.h"
#include "gpos/common/clibwrapper.h"
#include "gpos/utils.h"

using namespace gpos;

#define BYTES_PER_UNIT GPOS_SIZEOF(ULLONG)
#define BITS_PER_UNIT (8 * BYTES_PER_UNIT)

//---------------------------------------------------------------------------
//	@function:
//		CBitVector::Clear
//
//	@doc:
//		wipe all units
//
//---------------------------------------------------------------------------
void
CBitVector::Clear()
{
	GPOS_ASSERT(nullptr != m_vec);
	clib::Memset(m_vec, 0, m_len * BYTES_PER_UNIT);
}


//---------------------------------------------------------------------------
//	@function:
//		CBitVector::CBitVector
//
//	@doc:
//		ctor -- allocates actual vector, clears it
//
//---------------------------------------------------------------------------
CBitVector::CBitVector(CMemoryPool *mp, ULONG nbits)
	: m_nbits(nbits), m_len(0), m_vec(nullptr)
{
	// determine units needed to represent the number
	m_len = m_nbits / BITS_PER_UNIT;
	if (m_len * BITS_PER_UNIT < m_nbits)
	{
		m_len++;
	}

	GPOS_ASSERT(m_len * BITS_PER_UNIT >= m_nbits &&
				"Bit vector sized incorrectly");

	// allocate and clear
	m_vec = GPOS_NEW_ARRAY(mp, ULLONG, m_len);

	CAutoRg<ULLONG> argull;
	argull = m_vec;

	Clear();

	// unhook from protector
	argull.RgtReset();
}


//---------------------------------------------------------------------------
//	@function:
//		CBitVector::~CBitVector
//
//	@doc:
//		dtor
//
//---------------------------------------------------------------------------
CBitVector::~CBitVector()
{
	GPOS_DELETE_ARRAY(m_vec);
}


//---------------------------------------------------------------------------
//	@function:
//		CBitVector::CBitVector
//
//	@doc:
//		copy ctor;
//
//---------------------------------------------------------------------------
CBitVector::CBitVector(CMemoryPool *mp, const CBitVector &bv)
	: m_nbits(bv.m_nbits), m_len(bv.m_len), m_vec(nullptr)
{
	// deep copy
	m_vec = GPOS_NEW_ARRAY(mp, ULLONG, m_len);

	// Using auto range for cleanliness only;
	// NOTE: 03/25/2008; strictly speaking not necessary since there is
	//		no operation that could fail and it's the only allocation in the
	//		ctor;
	CAutoRg<ULLONG> argull;
	argull = m_vec;

	clib::Memcpy(m_vec, bv.m_vec, BYTES_PER_UNIT * m_len);

	// unhook from protector
	argull.RgtReset();
}


//---------------------------------------------------------------------------
//	@function:
//		CBitVector::Get
//
//	@doc:
//		Check if given bit is set
//
//---------------------------------------------------------------------------
BOOL
CBitVector::Get(ULONG pos) const
{
	GPOS_ASSERT(pos < m_nbits && "Bit index out of bounds.");

	ULONG idx = pos / BITS_PER_UNIT;
	ULLONG mask = ((ULLONG) 1) << (pos % BITS_PER_UNIT);

	return m_vec[idx] & mask;
}


//---------------------------------------------------------------------------
//	@function:
//		CBitVector::ExchangeSet
//
//	@doc:
//		Set given bit; return previous value
//
//---------------------------------------------------------------------------
BOOL
CBitVector::ExchangeSet(ULONG pos)
{
	GPOS_ASSERT(pos < m_nbits && "Bit index out of bounds.");

	// CONSIDER: 03/25/2008; make testing for the bit part of this routine and
	// avoid function call
	BOOL fSet = Get(pos);

	ULONG idx = pos / BITS_PER_UNIT;
	ULLONG mask = ((ULLONG) 1) << (pos % BITS_PER_UNIT);

	// OR the target unit with the mask
	m_vec[idx] |= mask;

	return fSet;
}


//---------------------------------------------------------------------------
//	@function:
//		CBitVector::ExchangeClear
//
//	@doc:
//		Clear given bit; return previous value
//
//---------------------------------------------------------------------------
BOOL
CBitVector::ExchangeClear(ULONG ulBit)
{
	GPOS_ASSERT(ulBit < m_nbits && "Bit index out of bounds.");

	// CONSIDER: 03/25/2008; make testing for the bit part of this routine and
	// avoid function call
	BOOL fSet = Get(ulBit);

	ULONG idx = ulBit / BITS_PER_UNIT;
	ULLONG mask = ((ULLONG) 1) << (ulBit % BITS_PER_UNIT);

	// AND the target unit with the inverted mask
	m_vec[idx] &= ~mask;

	return fSet;
}


//---------------------------------------------------------------------------
//	@function:
//		CBitVector::Union
//
//	@doc:
//		Union with given other vector
//
//---------------------------------------------------------------------------
void
CBitVector::Or(const CBitVector *vec)
{
	GPOS_ASSERT(m_nbits == vec->m_nbits && m_len == vec->m_len &&
				"vectors must be of same size");

	// OR all components
	for (ULONG i = 0; i < m_len; i++)
	{
		m_vec[i] |= vec->m_vec[i];
	}
}


//---------------------------------------------------------------------------
//	@function:
//		CBitVector::Intersection
//
//	@doc:
//		Intersect with given other vector
//
//---------------------------------------------------------------------------
void
CBitVector::And(const CBitVector *vec)
{
	GPOS_ASSERT(m_nbits == vec->m_nbits && m_len == vec->m_len &&
				"vectors must be of same size");

	// AND all components
	for (ULONG i = 0; i < m_len; i++)
	{
		m_vec[i] &= vec->m_vec[i];
	}
}


//---------------------------------------------------------------------------
//	@function:
//		CBitVector::FSubset
//
//	@doc:
//		Determine if given vector is subset
//
//---------------------------------------------------------------------------
BOOL
CBitVector::ContainsAll(const CBitVector *vec) const
{
	GPOS_ASSERT(m_nbits == vec->m_nbits && m_len == vec->m_len &&
				"vectors must be of same size");

	// OR all components
	for (ULONG i = 0; i < m_len; i++)
	{
		ULLONG ull = m_vec[i] & vec->m_vec[i];
		if (ull != vec->m_vec[i])
		{
			return false;
		}
	}

	return true;
}


//---------------------------------------------------------------------------
//	@function:
//		CBitVector::FDisjoint
//
//	@doc:
//		Determine if given vector is disjoint
//
//---------------------------------------------------------------------------
BOOL
CBitVector::IsDisjoint(const CBitVector *vec) const
{
	GPOS_ASSERT(m_nbits == vec->m_nbits && m_len == vec->m_len &&
				"vectors must be of same size");

	for (ULONG i = 0; i < m_len; i++)
	{
		if (0 != (m_vec[i] & vec->m_vec[i]))
		{
			return false;
		}
	}

	return true;
}


//---------------------------------------------------------------------------
//	@function:
//		CBitVector::Equals
//
//	@doc:
//		Determine if equal
//
//---------------------------------------------------------------------------
BOOL
CBitVector::Equals(const CBitVector *vec) const
{
	GPOS_ASSERT(m_nbits == vec->m_nbits && m_len == vec->m_len &&
				"vectors must be of same size");

	// compare all components
	if (0 == clib::Memcmp(m_vec, vec->m_vec, m_len * BYTES_PER_UNIT))
	{
		GPOS_ASSERT(this->ContainsAll(vec) && vec->ContainsAll(this));
		return true;
	}

	return false;
}



//---------------------------------------------------------------------------
//	@function:
//		CBitVector::IsEmpty
//
//	@doc:
//		Determine if vector is empty
//
//---------------------------------------------------------------------------
BOOL
CBitVector::IsEmpty() const
{
	for (ULONG i = 0; i < m_len; i++)
	{
		if (0 != m_vec[i])
		{
			return false;
		}
	}

	return true;
}


//---------------------------------------------------------------------------
//	@function:
//		CBitVector::GetNextBit
//
//	@doc:
//		Determine the next bit set greater or equal than the provided position
//
//---------------------------------------------------------------------------
BOOL
CBitVector::GetNextSetBit(ULONG start_pos, ULONG &next_pos) const
{
	ULONG offset = start_pos % BITS_PER_UNIT;
	for (ULONG idx = start_pos / BITS_PER_UNIT; idx < m_len; idx++)
	{
		ULLONG ull = m_vec[idx] >> offset;

		ULONG bit = offset;
		while (0 != ull && 0 == (ull & (ULLONG) 1))
		{
			ull >>= 1;
			bit++;
		}

		// if any bits left we found the next set position
		if (0 != ull)
		{
			next_pos = bit + (idx * BITS_PER_UNIT);
			return true;
		}

		// the initial offset applies only to the first chunk
		offset = 0;
	}

	return false;
}


//---------------------------------------------------------------------------
//	@function:
//		CBitVector::CElements
//
//	@doc:
//		Count bits in vector
//
//---------------------------------------------------------------------------
ULONG
CBitVector::CountSetBits() const
{
	ULONG nbits = 0;
	for (ULONG i = 0; i < m_len; i++)
	{
		ULLONG ull = m_vec[i];
		ULONG j = 0;

		for (j = 0; ull != 0; j++)
		{
			ull &= (ull - 1);
		}

		nbits += j;
	}

	return nbits;
}


//---------------------------------------------------------------------------
//	@function:
//		CBitVector::HashValue
//
//	@doc:
//		Compute hash value for bit vector
//
//---------------------------------------------------------------------------
ULONG
CBitVector::HashValue() const
{
	return gpos::HashByteArray((BYTE *) &m_vec[0],
							   GPOS_SIZEOF(m_vec[0]) * m_len);
}


// EOF

相关信息

greenplumn 源码目录

相关文章

greenplumn CAutoTimer 源码

greenplumn CBitSet 源码

greenplumn CBitSetIter 源码

greenplumn CDebugCounter 源码

greenplumn CHeapObject 源码

greenplumn CMainArgs 源码

greenplumn CRandom 源码

greenplumn CRefCount 源码

greenplumn CStackDescriptor 源码

greenplumn CStackObject 源码

0 赞

所属分类： 大数据
本文标签： greenplum
版权声明： 原创文章如转载，请注明本文链接: https://www.seaxiang.com/blog/cb94581ee3a048f5b74d70ccdb9e2ad4

热门推荐

1、直接访问google.com
2、 - 优质文章
3、 gate.io
4、 harmony 鸿蒙hdc使用指导
5、 harmony 鸿蒙初识ArkTS语言
6、 flink kafka connector scan.startup.mode 的几个选项
7、 harmony 鸿蒙ArkUI组件（ArkTS）开发常见问题
8、 golang
9、 openharmony
10、 Vue中input框自动聚焦

Loading...