greenplumn CBitSet 源码

greenplumn CBitSet 代码

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

//---------------------------------------------------------------------------
//	Greenplum Database
//	Copyright (C) 2009 Greenplum, Inc.
//
//	@filename:
//		CBitSet.cpp
//
//	@doc:
//		Implementation of bit sets
//
//		Underlying assumption: a set contains only a few links of bitvectors
//		hence, keeping them in a linked list is efficient;
//---------------------------------------------------------------------------

#include "gpos/common/CBitSet.h"

#include "gpos/base.h"
#include "gpos/common/CAutoRef.h"
#include "gpos/common/CBitSetIter.h"

#ifdef GPOS_DEBUG
#include "gpos/error/CAutoTrace.h"
#endif	// GPOS_DEBUG

using namespace gpos;

FORCE_GENERATE_DBGSTR(CBitSet);

//---------------------------------------------------------------------------
//	@function:
//		CBitSetLink
//
//	@doc:
//		ctor
//
//---------------------------------------------------------------------------
CBitSet::CBitSetLink::CBitSetLink(CMemoryPool *mp, ULONG offset,
								  ULONG vector_size)
	: m_offset(offset)
{
	m_vec = GPOS_NEW(mp) CBitVector(mp, vector_size);
}


//---------------------------------------------------------------------------
//	@function:
//		CBitSetLink
//
//	@doc:
//		copy ctor
//
//---------------------------------------------------------------------------
CBitSet::CBitSetLink::CBitSetLink(CMemoryPool *mp, const CBitSetLink &bsl)
	: m_offset(bsl.m_offset)
{
	m_vec = GPOS_NEW(mp) CBitVector(mp, *bsl.GetVec());
}


//---------------------------------------------------------------------------
//	@function:
//		~CBitSetLink
//
//	@doc:
//		ctor
//
//---------------------------------------------------------------------------
CBitSet::CBitSetLink::~CBitSetLink()
{
	GPOS_DELETE(m_vec);
}


//---------------------------------------------------------------------------
//	@function:
//		CBitSet::FindLinkByOffset
//
//	@doc:
//		Find bit set link for a given offset; if non-existent return previous
//		link (may be NULL);
//		By providing a starting link we can implement a number of operations
//		in one sweep, ie O(N)
//
//---------------------------------------------------------------------------
CBitSet::CBitSetLink *
CBitSet::FindLinkByOffset(ULONG offset, CBitSetLink *bsl) const
{
	CBitSetLink *found = nullptr;
	CBitSetLink *cursor = bsl;

	if (nullptr == bsl)
	{
		// if no cursor provided start with first element
		cursor = m_bsllist.First();
	}
	else
	{
		GPOS_ASSERT(bsl->GetOffset() <= offset && "invalid start cursor");
		found = bsl;
	}

	GPOS_ASSERT_IMP(nullptr != cursor,
					GPOS_OK == m_bsllist.Find(cursor) && "cursor not in list");

	while (true)
	{
		// no more links or we've overshot the target
		if (nullptr == cursor || cursor->GetOffset() > offset)
		{
			break;
		}

		found = cursor;
		cursor = m_bsllist.Next(cursor);
	}

	GPOS_ASSERT_IMP(found, found->GetOffset() <= offset);
	return found;
}


//---------------------------------------------------------------------------
//	@function:
//		CBitSet::RecomputeSize
//
//	@doc:
//		Compute size of set by adding up sizes of links
//
//---------------------------------------------------------------------------
void
CBitSet::RecomputeSize()
{
	m_size = 0;
	CBitSetLink *bsl = nullptr;

	for (bsl = m_bsllist.First(); bsl != nullptr; bsl = m_bsllist.Next(bsl))
	{
		m_size += bsl->GetVec()->CountSetBits();
	}
}


//---------------------------------------------------------------------------
//	@function:
//		CBitSet::Clear
//
//	@doc:
//		release all links
//
//---------------------------------------------------------------------------
void
CBitSet::Clear()
{
	CBitSetLink *bsl = nullptr;

	while (nullptr != (bsl = m_bsllist.First()))
	{
		CBitSetLink *bsl_to_remove = bsl;
		bsl = m_bsllist.Next(bsl);

		m_bsllist.Remove(bsl_to_remove);
		GPOS_DELETE(bsl_to_remove);
	}

	RecomputeSize();
}


//---------------------------------------------------------------------------
//	@function:
//		CBitSet::GetOffset
//
//	@doc:
//		Compute offset
//
//---------------------------------------------------------------------------
ULONG
CBitSet::ComputeOffset(ULONG ul) const
{
	return (ul / m_vector_size) * m_vector_size;
}



//---------------------------------------------------------------------------
//	@function:
//		CBitSet::CBitSet
//
//	@doc:
//		ctor
//
//---------------------------------------------------------------------------
CBitSet::CBitSet(CMemoryPool *mp, ULONG vector_size)
	: m_mp(mp), m_vector_size(vector_size), m_size(0)
{
	m_bsllist.Init(GPOS_OFFSET(CBitSetLink, m_link));
}


//---------------------------------------------------------------------------
//	@function:
//		CBitSet::CBitSet
//
//	@doc:
//		copy ctor;
//
//---------------------------------------------------------------------------
CBitSet::CBitSet(CMemoryPool *mp, const CBitSet &bs)
	: m_mp(mp), m_vector_size(bs.m_vector_size), m_size(0)
{
	m_bsllist.Init(GPOS_OFFSET(CBitSetLink, m_link));
	Union(&bs);
}


//---------------------------------------------------------------------------
//	@function:
//		CBitSet::~CBitSet
//
//	@doc:
//		dtor
//
//---------------------------------------------------------------------------
CBitSet::~CBitSet()
{
	Clear();
}


//---------------------------------------------------------------------------
//	@function:
//		CBitSet::Get
//
//	@doc:
//		Check if given bit is set
//
//---------------------------------------------------------------------------
BOOL
CBitSet::Get(ULONG pos) const
{
	ULONG offset = ComputeOffset(pos);

	CBitSetLink *bsl = FindLinkByOffset(offset);
	if (nullptr != bsl && bsl->GetOffset() == offset)
	{
		return bsl->GetVec()->Get(pos - offset);
	}

	return false;
}


//---------------------------------------------------------------------------
//	@function:
//		CBitSet::ExchangeSet
//
//	@doc:
//		Set given bit; return previous value; allocate new link if necessary
//
//---------------------------------------------------------------------------
BOOL
CBitSet::ExchangeSet(ULONG pos)
{
	ULONG offset = ComputeOffset(pos);

	CBitSetLink *bsl = FindLinkByOffset(offset);
	if (nullptr == bsl || bsl->GetOffset() != offset)
	{
		CBitSetLink *pbsl_new =
			GPOS_NEW(m_mp) CBitSetLink(m_mp, offset, m_vector_size);
		if (nullptr == bsl)
		{
			m_bsllist.Prepend(pbsl_new);
		}
		else
		{
			// insert after found link
			m_bsllist.Append(pbsl_new, bsl);
		}

		bsl = pbsl_new;
	}

	GPOS_ASSERT(bsl->GetOffset() == offset);

	BOOL bit = bsl->GetVec()->ExchangeSet(pos - offset);
	if (!bit)
	{
		m_size++;
	}

	return bit;
}


//---------------------------------------------------------------------------
//	@function:
//		CBitSet::ExchangeClear
//
//	@doc:
//		Clear given bit; return previous value
//
//---------------------------------------------------------------------------
BOOL
CBitSet::ExchangeClear(ULONG pos)
{
	ULONG offset = ComputeOffset(pos);

	CBitSetLink *bsl = FindLinkByOffset(offset);
	if (nullptr != bsl && bsl->GetOffset() == offset)
	{
		BOOL bit = bsl->GetVec()->ExchangeClear(pos - offset);

		// remove empty link
		if (bsl->GetVec()->IsEmpty())
		{
			m_bsllist.Remove(bsl);
			GPOS_DELETE(bsl);
		}

		if (bit)
		{
			m_size--;
		}

		return bit;
	}

	return false;
}


//---------------------------------------------------------------------------
//	@function:
//		CBitSet::Union
//
//	@doc:
//		Union with given other set;
//		(1) determine which links need to be allocated before(!) modifying
//			the set allocate and copy missing links aside
//		(2) insert the new links into the list
//		(3) union all links, old and new, on a per-bitvector basis
//
//		For clarity step (2) and (3) are separated;
//
//---------------------------------------------------------------------------
void
CBitSet::Union(const CBitSet *pbsOther)
{
	CBitSetLink *bsl = nullptr;
	CBitSetLink *bsl_other = nullptr;

	// dynamic array of CBitSetLink
	using CBitSetLinkArray = CDynamicPtrArray<CBitSetLink, CleanupNULL>;

	CAutoRef<CBitSetLinkArray> a_drgpbsl;
	a_drgpbsl = GPOS_NEW(m_mp) CBitSetLinkArray(m_mp);

	// iterate through other's links and copy missing links to array
	for (bsl_other = pbsOther->m_bsllist.First(); bsl_other != nullptr;
		 bsl_other = pbsOther->m_bsllist.Next(bsl_other))
	{
		bsl = FindLinkByOffset(bsl_other->GetOffset(), bsl);
		if (nullptr == bsl || bsl->GetOffset() != bsl_other->GetOffset())
		{
			// need to copy this link
			CAutoP<CBitSetLink> a_pbsl;
			a_pbsl = GPOS_NEW(m_mp) CBitSetLink(m_mp, *bsl_other);
			a_drgpbsl->Append(a_pbsl.Value());

			a_pbsl.Reset();
		}
	}

	// insert all new links
	bsl = nullptr;
	for (ULONG i = 0; i < a_drgpbsl->Size(); i++)
	{
		CBitSetLink *pbslInsert = (*a_drgpbsl)[i];
		bsl = FindLinkByOffset(pbslInsert->GetOffset(), bsl);

		GPOS_ASSERT_IMP(nullptr != bsl,
						bsl->GetOffset() < pbslInsert->GetOffset());
		if (nullptr == bsl)
		{
			m_bsllist.Prepend(pbslInsert);
		}
		else
		{
			m_bsllist.Append(pbslInsert, bsl);
		}
	}

	// iterate through all links and union them up
	bsl_other = nullptr;
	bsl = m_bsllist.First();
	while (nullptr != bsl)
	{
		bsl_other = pbsOther->FindLinkByOffset(bsl->GetOffset(), bsl_other);
		if (nullptr != bsl_other && bsl_other->GetOffset() == bsl->GetOffset())
		{
			bsl->GetVec()->Or(bsl_other->GetVec());
		}

		bsl = m_bsllist.Next(bsl);
	}

	RecomputeSize();
}


//---------------------------------------------------------------------------
//	@function:
//		CBitSet::Intersection
//
//	@doc:
//		Iterate through all links and intersect them; release unused links
//
//---------------------------------------------------------------------------
void
CBitSet::Intersection(const CBitSet *pbsOther)
{
	if (nullptr == pbsOther)
	{
		return;
	}

	CBitSetLink *bsl_other = nullptr;
	CBitSetLink *bsl = m_bsllist.First();

	while (nullptr != bsl)
	{
		CBitSetLink *bsl_to_remove = nullptr;

		bsl_other = pbsOther->FindLinkByOffset(bsl->GetOffset(), bsl_other);
		if (nullptr != bsl_other && bsl_other->GetOffset() == bsl->GetOffset())
		{
			bsl->GetVec()->And(bsl_other->GetVec());
			bsl = m_bsllist.Next(bsl);
		}
		else
		{
			bsl_to_remove = bsl;
			bsl = m_bsllist.Next(bsl);

			m_bsllist.Remove(bsl_to_remove);
			GPOS_DELETE(bsl_to_remove);
		}
	}

	RecomputeSize();
}


//---------------------------------------------------------------------------
//	@function:
//		CBitSet::Difference
//
//	@doc:
//		Substract other set from this by iterating through other set and
//		explicit removal of elements;
//
//---------------------------------------------------------------------------
void
CBitSet::Difference(const CBitSet *pbs)
{
	if (IsDisjoint(pbs))
	{
		return;
	}

	CBitSetIter bsiter(*pbs);
	while (bsiter.Advance())
	{
		(void) ExchangeClear(bsiter.Bit());
	}
}


//---------------------------------------------------------------------------
//	@function:
//		CBitSet::FSubset
//
//	@doc:
//		Determine if given vector is subset
//
//---------------------------------------------------------------------------
BOOL
CBitSet::ContainsAll(const CBitSet *bs) const
{
	// skip iterating if we can already tell by the sizes
	if (Size() < bs->Size())
	{
		return false;
	}

	CBitSetLink *bsl = nullptr;
	CBitSetLink *bsl_other = nullptr;

	// iterate through other's links and check for subsets
	for (bsl_other = bs->m_bsllist.First(); bsl_other != nullptr;
		 bsl_other = bs->m_bsllist.Next(bsl_other))
	{
		bsl = FindLinkByOffset(bsl_other->GetOffset(), bsl);

		if (nullptr == bsl || bsl->GetOffset() != bsl_other->GetOffset() ||
			!bsl->GetVec()->ContainsAll(bsl_other->GetVec()))
		{
			return false;
		}
	}

	return true;
}


//---------------------------------------------------------------------------
//	@function:
//		CBitSet::Equals
//
//	@doc:
//		Determine if equal
//
//---------------------------------------------------------------------------
BOOL
CBitSet::Equals(const CBitSet *bs) const
{
	// check pointer equality first
	if (this == bs)
	{
		return true;
	}

	// skip iterating if we can already tell by the sizes
	if (Size() != bs->Size())
	{
		return false;
	}

	CBitSetLink *bsl = m_bsllist.First();
	CBitSetLink *bsl_other = bs->m_bsllist.First();

	while (nullptr != bsl)
	{
		if (nullptr == bsl_other ||
			bsl->GetOffset() != bsl_other->GetOffset() ||
			!bsl->GetVec()->Equals(bsl_other->GetVec()))
		{
			return false;
		}

		bsl = m_bsllist.Next(bsl);
		bsl_other = bs->m_bsllist.Next(bsl_other);
	}

	// same length implies bsl_other must have reached end as well
	return bsl_other == nullptr;
}



//---------------------------------------------------------------------------
//	@function:
//		CBitSet::FDisjoint
//
//	@doc:
//		Determine if disjoint
//
//---------------------------------------------------------------------------
BOOL
CBitSet::IsDisjoint(const CBitSet *bs) const
{
	CBitSetLink *bsl = nullptr;
	CBitSetLink *bsl_other = nullptr;

	// iterate through other's links an check if disjoint
	for (bsl_other = bs->m_bsllist.First(); bsl_other != nullptr;
		 bsl_other = bs->m_bsllist.Next(bsl_other))
	{
		bsl = FindLinkByOffset(bsl_other->GetOffset(), bsl);

		if (nullptr != bsl && bsl->GetOffset() == bsl_other->GetOffset() &&
			!bsl->GetVec()->IsDisjoint(bsl_other->GetVec()))
		{
			return false;
		}
	}

	return true;
}


//---------------------------------------------------------------------------
//	@function:
//		CBitSet::HashValue
//
//	@doc:
//		Compute hash value for set
//
//---------------------------------------------------------------------------
ULONG
CBitSet::HashValue() const
{
	ULONG ulHash = 0;

	CBitSetLink *bsl = m_bsllist.First();
	while (nullptr != bsl)
	{
		ulHash = gpos::CombineHashes(ulHash, bsl->GetVec()->HashValue());
		bsl = m_bsllist.Next(bsl);
	}

	return ulHash;
}


//---------------------------------------------------------------------------
//	@function:
//		CBitSet::OsPrint
//
//	@doc:
//		Debug print function
//
//---------------------------------------------------------------------------
IOstream &
CBitSet::OsPrint(IOstream &os) const
{
	os << "{";

	ULONG ulElems = Size();
	CBitSetIter bsiter(*this);

	for (ULONG ul = 0; ul < ulElems; ul++)
	{
		(void) bsiter.Advance();
		os << bsiter.Bit();

		if (ul < ulElems - 1)
		{
			os << ", ";
		}
	}

	os << "}";

	return os;
}

// EOF

相关信息

greenplumn 源码目录

相关文章

greenplumn CAutoTimer 源码

greenplumn CBitSetIter 源码

greenplumn CBitVector 源码

greenplumn CDebugCounter 源码

greenplumn CHeapObject 源码

greenplumn CMainArgs 源码

greenplumn CRandom 源码

greenplumn CRefCount 源码

greenplumn CStackDescriptor 源码

greenplumn CStackObject 源码