xref: /AOO41X/main/sfx2/source/bastyp/bitset.cxx (revision cdf0e10c4e3984b49a9502b011690b615761d4a3)

/*************************************************************************
 *
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * Copyright 2000, 2010 Oracle and/or its affiliates.
 *
 * OpenOffice.org - a multi-platform office productivity suite
 *
 * This file is part of OpenOffice.org.
 *
 * OpenOffice.org is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License version 3
 * only, as published by the Free Software Foundation.
 *
 * OpenOffice.org is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License version 3 for more details
 * (a copy is included in the LICENSE file that accompanied this code).
 *
 * You should have received a copy of the GNU Lesser General Public License
 * version 3 along with OpenOffice.org.  If not, see
 * <http://www.openoffice.org/license.html>
 * for a copy of the LGPLv3 License.
 *
 ************************************************************************/

// MARKER(update_precomp.py): autogen include statement, do not remove
#include "precompiled_sfx2.hxx"
#include <tools/debug.hxx>
#ifndef GCC
#endif

#include "bitset.hxx"

#include <string.h>		// memset(), memcpy()
#include <limits.h>		// USHRT_MAX

//====================================================================
// add nOffset to each bit-value in the set

BitSet BitSet::operator<<( sal_uInt16 nOffset ) const
{
	DBG_MEMTEST();
	// create a work-copy, return it if nothing to shift
	BitSet aSet(*this);
	if ( nOffset == 0 )
		return aSet;

	// compute the shiftment in long-words and bits
	sal_uInt16 nBlockDiff = nOffset / 32;
	sal_uIntPtr nBitValDiff = nOffset % 32;

	// compute the new number of bits
	for ( sal_uInt16 nBlock = 0; nBlock < nBlockDiff; ++nBlock )
		aSet.nCount = aSet.nCount - CountBits( *(aSet.pBitmap+nBlock) );
	aSet.nCount = aSet.nCount -
        CountBits( *(aSet.pBitmap+nBlockDiff) >> (32-nBitValDiff) );

	// shift complete long-words
	sal_uInt16 nTarget, nSource;
	for ( nTarget = 0, nSource = nBlockDiff;
		  (nSource+1) < aSet.nBlocks;
		  ++nTarget, ++nSource )
		*(aSet.pBitmap+nTarget) =
			( *(aSet.pBitmap+nSource) << nBitValDiff ) |
			( *(aSet.pBitmap+nSource+1) >> (32-nBitValDiff) );

	// shift the remainder (if in total minor 32 bits, only this)
	*(aSet.pBitmap+nTarget) = *(aSet.pBitmap+nSource) << nBitValDiff;

	// determine the last used block
	while ( *(aSet.pBitmap+nTarget) == 0 )
		--nTarget;

	// shorten the block-array
	if ( nTarget < aSet.nBlocks )
	{
		sal_uIntPtr* pNewMap = new sal_uIntPtr[nTarget];
		memcpy( pNewMap, aSet.pBitmap, 4 * nTarget );
        delete [] aSet.pBitmap;
		aSet.pBitmap = pNewMap;
		aSet.nBlocks = nTarget;
	}

	return aSet;
}

//--------------------------------------------------------------------

// substracts nOffset from each bit-value in the set

BitSet BitSet::operator>>( sal_uInt16 ) const
{
	DBG_MEMTEST();
	return BitSet();
}

//--------------------------------------------------------------------

// internal code for operator= and copy-ctor

void BitSet::CopyFrom( const BitSet& rSet )
{
	DBG_MEMTEST();
	nCount = rSet.nCount;
	nBlocks = rSet.nBlocks;
	if ( rSet.nBlocks )
	{
		DBG_MEMTEST();
		pBitmap = new sal_uIntPtr[nBlocks];
		memcpy( pBitmap, rSet.pBitmap, 4 * nBlocks );
	}
	else
		pBitmap = 0;
}

//--------------------------------------------------------------------

// creates an empty bitset

BitSet::BitSet()
{
	DBG_MEMTEST();
	nCount = 0;
	nBlocks = 0;
	pBitmap = 0;
}

//--------------------------------------------------------------------

// creates a copy of bitset rOrig

BitSet::BitSet( const BitSet& rOrig )
{
	DBG_MEMTEST();
	CopyFrom(rOrig);
}

//--------------------------------------------------------------------

// creates a bitset from an array

BitSet::BitSet( sal_uInt16* pArray, sal_uInt16 nSize ):
	nCount(nSize)
{
	DBG_MEMTEST();
	// find the highest bit to set
	sal_uInt16 nMax = 0;
	for ( sal_uInt16 n = 0; n < nCount; ++n )
		if ( pArray[n] > nMax )
			nMax = pArray[n];

	// if there are bits at all
	if ( nMax > 0 )
	{
		// allocate memory for all blocks needed
		nBlocks = nMax / 32 + 1;
		pBitmap = new sal_uIntPtr[nBlocks];
		memset( pBitmap, 0, 4 * nBlocks );

		// set all the bits
		for ( sal_uInt16 n = 0; n < nCount; ++n )
		{
			// compute the block no. and bitvalue
			sal_uInt16 nBlock = n / 32;
			sal_uIntPtr nBitVal = 1L << (n % 32);

			// set a single bit
			if ( ( *(pBitmap+nBlock) & nBitVal ) == 0 )
			{
				*(pBitmap+nBlock) |= nBitVal;
				++nCount;
			}
		}
	}
	else
	{
		// initalize emtpy set
		nBlocks = 0;
		pBitmap = 0;
	}
}

//--------------------------------------------------------------------

// frees the storage

BitSet::~BitSet()
{
	DBG_MEMTEST();
    delete [] pBitmap;
}

//--------------------------------------------------------------------

// creates a bitmap with all bits in rRange set

BitSet::BitSet( const Range& )
{
	DBG_MEMTEST();
}

//--------------------------------------------------------------------

// assignment from another bitset

BitSet& BitSet::operator=( const BitSet& rOrig )
{
	DBG_MEMTEST();
	if ( this != &rOrig )
	{
        delete [] pBitmap;
		CopyFrom(rOrig);
	}
	return *this;
}

//--------------------------------------------------------------------

// assignment from a single bit

BitSet& BitSet::operator=( sal_uInt16 nBit )
{
	DBG_MEMTEST();
    delete [] pBitmap;

	nBlocks = nBit / 32;
	sal_uIntPtr nBitVal = 1L << (nBit % 32);
	nCount = 1;

	pBitmap = new sal_uIntPtr[nBlocks];
	memset( pBitmap + nBlocks, 0, 4 * nBlocks );

	*(pBitmap+nBlocks) = nBitVal;

	return *this;
}

//--------------------------------------------------------------------

// creates the asymetric difference with another bitset

BitSet& BitSet::operator-=(sal_uInt16 nBit)
{
	DBG_MEMTEST();
	sal_uInt16 nBlock = nBit / 32;
	sal_uIntPtr nBitVal = 1L << (nBit % 32);

	if ( nBlock >= nBlocks )
	  return *this;

	if ( (*(pBitmap+nBlock) & nBitVal) )
	{
		*(pBitmap+nBlock) &= ~nBitVal;
		--nCount;
	}

	return *this;
}

//--------------------------------------------------------------------

// unites with the bits of rSet

BitSet& BitSet::operator|=( const BitSet& rSet )
{
	DBG_MEMTEST();
	sal_uInt16 nMax = Min(nBlocks, rSet.nBlocks);

	// expand the bitmap
	if ( nBlocks < rSet.nBlocks )
	{
		sal_uIntPtr *pNewMap = new sal_uIntPtr[rSet.nBlocks];
		memset( pNewMap + nBlocks, 0, 4 * (rSet.nBlocks - nBlocks) );

		if ( pBitmap )
		{
			memcpy( pNewMap, pBitmap, 4 * nBlocks );
            delete [] pBitmap;
		}
		pBitmap = pNewMap;
		nBlocks = rSet.nBlocks;
	}

	// add the bits blocks by block
	for ( sal_uInt16 nBlock = 0; nBlock < nMax; ++nBlock )
	{
		// compute numberof additional bits
		sal_uIntPtr nDiff = ~*(pBitmap+nBlock) & *(rSet.pBitmap+nBlock);
		nCount = nCount + CountBits(nDiff);

		*(pBitmap+nBlock) |= *(rSet.pBitmap+nBlock);
	}

	return *this;
}

//--------------------------------------------------------------------

// unites with a single bit

BitSet& BitSet::operator|=( sal_uInt16 nBit )
{
	DBG_MEMTEST();
	sal_uInt16 nBlock = nBit / 32;
	sal_uIntPtr nBitVal = 1L << (nBit % 32);

	if ( nBlock >= nBlocks )
	{
		sal_uIntPtr *pNewMap = new sal_uIntPtr[nBlock+1];
		memset( pNewMap + nBlocks, 0, 4 * (nBlock - nBlocks + 1) );

		if ( pBitmap )
		{
			memcpy( pNewMap, pBitmap, 4 * nBlocks );
            delete [] pBitmap;
		}
		pBitmap = pNewMap;
		nBlocks = nBlock+1;
	}

	if ( (*(pBitmap+nBlock) & nBitVal) == 0 )
	{
		*(pBitmap+nBlock) |= nBitVal;
		++nCount;
	}

	return *this;
}

//--------------------------------------------------------------------

// determines if the bit is set (may be the only one)

sal_Bool BitSet::Contains( sal_uInt16 nBit ) const
{
	DBG_MEMTEST();
	sal_uInt16 nBlock = nBit / 32;
	sal_uIntPtr nBitVal = 1L << (nBit % 32);

	if ( nBlock >= nBlocks )
		return sal_False;
	return ( nBitVal & *(pBitmap+nBlock) ) == nBitVal;
}

//--------------------------------------------------------------------

// determines if the bitsets are equal

sal_Bool BitSet::operator==( const BitSet& rSet ) const
{
	DBG_MEMTEST();
	if ( nBlocks != rSet.nBlocks )
		return sal_False;

	sal_uInt16 nBlock = nBlocks;
	while ( nBlock-- > 0 )
		if ( *(pBitmap+nBlock) != *(rSet.pBitmap+nBlock) )
			return sal_False;

	return sal_True;
}

//--------------------------------------------------------------------

// counts the number of 1-bits in the parameter

sal_uInt16 BitSet::CountBits( sal_uIntPtr nBits )
{
	sal_uInt16 nCount = 0;
	int nBit = 32;
	while ( nBit-- && nBits )
	{   if ( ( (long)nBits ) < 0 )
			++nCount;
		nBits = nBits << 1;
	}
	return nCount;
}

//--------------------------------------------------------------------

sal_uInt16 IndexBitSet::GetFreeIndex()
{
  for(sal_uInt16 i=0;i<USHRT_MAX;i++)
	if(!Contains(i))
	  {
		*this|=i;
		return i;
	  }
  DBG_ASSERT(sal_False, "IndexBitSet enthaelt mehr als USHRT_MAX Eintraege");
  return 0;
}