Detailed Description

header only, simple implementation of a bitset

Author: Daniel Rehfeldt

Implements a simple bitset. Should be set to NULL if undefined. NOTE: for efficiency reasons the bitset type is based on an STP_Vector and thus uses a non-SCIP-standard allocation method. In this way we avoid indirections, because we directly access the raw array. todo if too slow use extra fixed-size vector that uses standard memory allocs, or even cache-aligned mallocs

Definition in file stpbitset.h.

#include "scip/scip.h"
#include "stpvector.h"

Go to the source code of this file.

Macros
#define	STP_Bitset STP_Vectype(uint64_t)

Functions
static int	bitsetinternalPopcount (uint64_t number)

static STP_Bitset	stpbitset_new (SCIP *scip, int maxnbits)

static void	stpbitset_free (SCIP scip, STP_Bitset bitset)

static int	stpbitset_getCapacity (STP_Bitset bitset)

static void	stpbitset_setBitTrue (STP_Bitset bitset, int index)

static void	stpbitset_setBitFalse (STP_Bitset bitset, int index)

static SCIP_Bool	stpbitset_setsAreCompatible (STP_Bitset bitset1, STP_Bitset bitset2)

static SCIP_Bool	stpbitset_haveIntersection (STP_Bitset bitset1, STP_Bitset bitset2)

static SCIP_Bool	stpbitset_areEqual (STP_Bitset bitset1, STP_Bitset bitset2)

static SCIP_Bool	stpbitset_bitIsTrue (STP_Bitset bitset, int index)

static int	stpbitset_getPopcount (STP_Bitset bitset)

static STP_Bitset	stpbitset_newCopy (SCIP *scip, STP_Bitset bitsetOrg)

static void	stpbitset_and (SCIP *scip, STP_Bitset bitset1, STP_Bitset bitset2, STP_Bitset bitsetAnd)

static void	stpbitset_or (SCIP *scip, STP_Bitset bitset1, STP_Bitset bitset2, STP_Bitset bitsetOr)

static STP_Bitset	stpbitset_newAnd (SCIP *scip, STP_Bitset bitset1, STP_Bitset bitset2)

static STP_Bitset	stpbitset_newOr (SCIP *scip, STP_Bitset bitset1, STP_Bitset bitset2)

static STP_Bitset	stpbitset_newXor (SCIP *scip, STP_Bitset bitset1, STP_Bitset bitset2)

static STP_Bitset	stpbitset_newNot (SCIP *scip, STP_Bitset bitset1, int size)

static STP_Bitset	stpbitset_newAllTrue (SCIP *scip, int maxnbits)

static void	stpbitset_print (STP_Bitset bitset)

static SCIP_Bool	stpbitset_GT (STP_Bitset bitset1, STP_Bitset bitset2)

static SCIP_Bool	stpbitset_LT (STP_Bitset bitset1, STP_Bitset bitset2)

Macro Definition Documentation

◆ STP_Bitset

#define STP_Bitset STP_Vectype(uint64_t)

Definition at line 44 of file stpbitset.h.

Referenced by stpbitset_new(), stpbitset_newAllTrue(), stpbitset_newAnd(), stpbitset_newCopy(), stpbitset_newNot(), stpbitset_newOr(), and stpbitset_newXor().

Function Documentation

◆ bitsetinternalPopcount()

static int bitsetinternalPopcount ( uint64_t number )

inlinestatic

todo: do that more efficiently; currently just a text-book implementation. probably want to have case distinction for compilers and use intrinsics at least for gcc, clang, and intel

Parameters

number to get popcount for

Definition at line 51 of file stpbitset.h.

References number.

Referenced by stpbitset_getPopcount().

◆ stpbitset_new()

static STP_Bitset stpbitset_new	(	SCIP *	scip,
		int	maxnbits
	)

inlinestatic

initializes clean (all-0) bitset and returns it

Parameters

scip	SCIP data structure
maxnbits	size of bitset

Definition at line 75 of file stpbitset.h.

References NULL, STP_Bitset, StpVecPushBack, and StpVecReserve.

Referenced by dpiterAddNewPrepare(), dpsolverInitData(), stpbitset_newAllTrue(), stpbitset_newAnd(), stpbitset_newCopy(), stpbitset_newNot(), stpbitset_newOr(), and stpbitset_newXor().

◆ stpbitset_free()

static void stpbitset_free	(	SCIP *	scip,
		STP_Bitset *	bitset
	)

inlinestatic

frees

Parameters

scip	SCIP data structure
bitset	bitset pointer

Definition at line 100 of file stpbitset.h.

References NULL, and StpVecFree.

Referenced by combineWithIntersecting(), dpiterAddNewPrepare(), dpiterFinalizeSol(), dpiterPopSol(), dpmiscFree(), dpterms_dpsubsolFree(), dpterms_streeFree(), subtreesAddNewFinalize(), and updateIncumbent().

◆ stpbitset_getCapacity()

static int stpbitset_getCapacity ( STP_Bitset bitset )

inlinestatic

gets number of bits that can be stored

Parameters

bitset bitset

Definition at line 116 of file stpbitset.h.

References StpVecGetcapacity, and StpVecGetSize.

Referenced by bitsetsizesAreValid(), stpbitset_bitIsTrue(), stpbitset_newAllTrue(), stpbitset_newAnd(), stpbitset_newCopy(), stpbitset_newNot(), stpbitset_newOr(), stpbitset_newXor(), stpbitset_print(), stpbitset_setBitFalse(), stpbitset_setBitTrue(), and stpbitset_setsAreCompatible().

◆ stpbitset_setBitTrue()

static void stpbitset_setBitTrue	(	STP_Bitset	bitset,
		int	index
	)

inlinestatic

sets bit to TRUE (1)

Parameters

bitset	bitset
index	bit index

Definition at line 129 of file stpbitset.h.

References stpbitset_getCapacity().

Referenced by dpiterAddNewPrepare(), dpsolverInitData(), and stpbitset_newAllTrue().

◆ stpbitset_setBitFalse()

static void stpbitset_setBitFalse	(	STP_Bitset	bitset,
		int	index
	)

inlinestatic

sets bit to FALSE (0)

Parameters

bitset	bitset
index	bit index

Definition at line 143 of file stpbitset.h.

References stpbitset_getCapacity().

◆ stpbitset_setsAreCompatible()

static SCIP_Bool stpbitset_setsAreCompatible	(	STP_Bitset	bitset1,
		STP_Bitset	bitset2
	)

inlinestatic

are given bitsets compatible?

Parameters

bitset1	bitset
bitset2	bitset

Definition at line 157 of file stpbitset.h.

References FALSE, stpbitset_getCapacity(), StpVecGetSize, and TRUE.

Referenced by STP_Vectype(), stpbitset_and(), stpbitset_areEqual(), stpbitset_GT(), stpbitset_haveIntersection(), stpbitset_LT(), stpbitset_newAnd(), stpbitset_newCopy(), stpbitset_newOr(), stpbitset_newXor(), and stpbitset_or().

◆ stpbitset_haveIntersection()

static SCIP_Bool stpbitset_haveIntersection	(	STP_Bitset	bitset1,
		STP_Bitset	bitset2
	)

inlinestatic

do bitsets (of same size) intersect?

Parameters

bitset1	bitset
bitset2	bitset

Definition at line 177 of file stpbitset.h.

References FALSE, stpbitset_setsAreCompatible(), StpVecGetSize, and TRUE.

Referenced by STP_Vectype(), and streeCollectIntersects().

◆ stpbitset_areEqual()

static SCIP_Bool stpbitset_areEqual	(	STP_Bitset	bitset1,
		STP_Bitset	bitset2
	)

inlinestatic

are bitsets the same?

Parameters

bitset1	bitset
bitset2	bitset

Definition at line 200 of file stpbitset.h.

References FALSE, stpbitset_setsAreCompatible(), StpVecGetSize, and TRUE.

Referenced by dpiterPopSol().

◆ stpbitset_bitIsTrue()

static SCIP_Bool stpbitset_bitIsTrue	(	STP_Bitset	bitset,
		int	index
	)

inlinestatic

is bit at given index set?

Parameters

bitset	bitset
index	bit index

Definition at line 223 of file stpbitset.h.

References FALSE, stpbitset_getCapacity(), and TRUE.

Referenced by allExtensionsAreInvalid(), dpiterGetNextSol(), insertData(), nodeIsNonSolTerm(), STP_Vectype(), stpbitset_newAllTrue(), stpbitset_newNot(), stpbitset_print(), and streeCollectIntersects().

◆ stpbitset_getPopcount()

static int stpbitset_getPopcount ( STP_Bitset bitset )

inlinestatic

gets number of 1-bits

Parameters

bitset bitset

Definition at line 247 of file stpbitset.h.

References bitsetinternalPopcount(), and StpVecGetSize.

Referenced by combineWithIntersecting(), dpiterPopSol(), dpterms_streeInsert(), insertData(), and subtreesAddNew().

◆ stpbitset_newCopy()

static STP_Bitset stpbitset_newCopy	(	SCIP *	scip,
		STP_Bitset	bitsetOrg
	)

inlinestatic

gets copy

Parameters

scip	SCIP data structure
bitsetOrg	bitset

Definition at line 267 of file stpbitset.h.

References BMScopyMemoryArray, STP_Bitset, stpbitset_getCapacity(), stpbitset_new(), stpbitset_setsAreCompatible(), and StpVecGetSize.

Referenced by combineWithIntersecting(), dpsolverInitData(), insertData(), and subtreesAddNewFinalize().

◆ stpbitset_and()

static void stpbitset_and	(	SCIP *	scip,
		STP_Bitset	bitset1,
		STP_Bitset	bitset2,
		STP_Bitset	bitsetAnd
	)

inlinestatic

sets AND bitset

Parameters

scip	SCIP data structure
bitset1	bitset
bitset2	bitset
bitsetAnd	bitset to set

Definition at line 286 of file stpbitset.h.

References stpbitset_setsAreCompatible(), and StpVecGetSize.

Referenced by insertData(), and stpbitset_newAnd().

◆ stpbitset_or()

static void stpbitset_or	(	SCIP *	scip,
		STP_Bitset	bitset1,
		STP_Bitset	bitset2,
		STP_Bitset	bitsetOr
	)

inlinestatic

sets OR bitset

Parameters

scip	SCIP data structure
bitset1	bitset
bitset2	bitset
bitsetOr	bitset to set

Definition at line 308 of file stpbitset.h.

References stpbitset_setsAreCompatible(), and StpVecGetSize.

Referenced by insertData(), and stpbitset_newOr().

◆ stpbitset_newAnd()

static STP_Bitset stpbitset_newAnd	(	SCIP *	scip,
		STP_Bitset	bitset1,
		STP_Bitset	bitset2
	)

inlinestatic

gets new AND bitset

Parameters

scip	SCIP data structure
bitset1	bitset
bitset2	bitset

Definition at line 330 of file stpbitset.h.

References STP_Bitset, stpbitset_and(), stpbitset_getCapacity(), stpbitset_new(), and stpbitset_setsAreCompatible().

◆ stpbitset_newOr()

static STP_Bitset stpbitset_newOr	(	SCIP *	scip,
		STP_Bitset	bitset1,
		STP_Bitset	bitset2
	)

inlinestatic

gets new OR bitset

Parameters

scip	SCIP data structure
bitset1	bitset
bitset2	bitset

Definition at line 348 of file stpbitset.h.

References STP_Bitset, stpbitset_getCapacity(), stpbitset_new(), stpbitset_or(), and stpbitset_setsAreCompatible().

Referenced by combineWithIntersecting().

◆ stpbitset_newXor()

static STP_Bitset stpbitset_newXor	(	SCIP *	scip,
		STP_Bitset	bitset1,
		STP_Bitset	bitset2
	)

inlinestatic

gets new XOR bitset

Parameters

scip	SCIP data structure
bitset1	bitset
bitset2	bitset

Definition at line 366 of file stpbitset.h.

References STP_Bitset, stpbitset_getCapacity(), stpbitset_new(), stpbitset_setsAreCompatible(), and StpVecGetSize.

◆ stpbitset_newNot()

static STP_Bitset stpbitset_newNot	(	SCIP *	scip,
		STP_Bitset	bitset1,
		int	size
	)

inlinestatic

gets new Not bitset

Parameters

scip	SCIP data structure
bitset1	bitset for not
size	size to apply not operation to

Definition at line 390 of file stpbitset.h.

References STP_Bitset, stpbitset_bitIsTrue(), stpbitset_getCapacity(), stpbitset_new(), and StpVecGetSize.

Referenced by updateIncumbent().

◆ stpbitset_newAllTrue()

static STP_Bitset stpbitset_newAllTrue	(	SCIP *	scip,
		int	maxnbits
	)

inlinestatic

initializes all TRUE bitset and returns it todo more efficiently

Parameters

scip	SCIP data structure
maxnbits	size of bitset

Definition at line 430 of file stpbitset.h.

References STP_Bitset, stpbitset_bitIsTrue(), stpbitset_getCapacity(), stpbitset_new(), and stpbitset_setBitTrue().

◆ stpbitset_print()

static void stpbitset_print ( STP_Bitset bitset )

inlinestatic

prints bitset (0,1) ... for debugging

Parameters

bitset bitset to print

Definition at line 452 of file stpbitset.h.

References stpbitset_bitIsTrue(), and stpbitset_getCapacity().

Referenced by dpiterGetNextSol(), dpterms_streeInsert(), printNodeDebugInfo(), subtreesAddNew(), and updateIncumbent().

◆ stpbitset_GT()

static SCIP_Bool stpbitset_GT	(	STP_Bitset	bitset1,
		STP_Bitset	bitset2
	)

inlinestatic

bitset1 > bitset2?

Parameters

bitset1	bitset
bitset2	bitset

Definition at line 473 of file stpbitset.h.

References stpbitset_setsAreCompatible(), and StpVecGetSize.

◆ stpbitset_LT()

static SCIP_Bool stpbitset_LT	(	STP_Bitset	bitset1,
		STP_Bitset	bitset2
	)

inlinestatic

bitset1 < bitset2?

Parameters

bitset1	bitset
bitset2	bitset

Definition at line 492 of file stpbitset.h.

References stpbitset_setsAreCompatible(), and StpVecGetSize.

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ STP_Bitset

Function Documentation

◆ bitsetinternalPopcount()

◆ stpbitset_new()

◆ stpbitset_free()

◆ stpbitset_getCapacity()

◆ stpbitset_setBitTrue()

◆ stpbitset_setBitFalse()

◆ stpbitset_setsAreCompatible()

◆ stpbitset_haveIntersection()

◆ stpbitset_areEqual()

◆ stpbitset_bitIsTrue()

◆ stpbitset_getPopcount()

◆ stpbitset_newCopy()

◆ stpbitset_and()

◆ stpbitset_or()

◆ stpbitset_newAnd()

◆ stpbitset_newOr()

◆ stpbitset_newXor()

◆ stpbitset_newNot()

◆ stpbitset_newAllTrue()

◆ stpbitset_print()

◆ stpbitset_GT()

◆ stpbitset_LT()