Hash Table

Detailed Description

hash table that resolves conflicts by probing

Macros
#define	SCIPhashSignature64(a)   (UINT64_C(0x8000000000000000)>>((UINT32_C(0x9e3779b9) * ((uint32_t)(a)))>>26))
#define	SCIPhashTwo(a, b)   ((uint32_t)((((uint32_t)(a) + 0xd37e9a1ce2148403ULL) * ((uint32_t)(b) + 0xe5fcc163aef32782ULL) )>>32))
#define	SCIPhashThree(a, b, c)
#define	SCIPhashFour(a, b, c, d)
#define	SCIPhashFive(a, b, c, d, e)
#define	SCIPhashSix(a, b, c, d, e, f)
#define	SCIPhashSeven(a, b, c, d, e, f, g)

Functions
static INLINE uint32_t	SCIPrealHashCode (double x)
SCIP_RETCODE	SCIPhashtableCreate (SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
void	SCIPhashtableFree (SCIP_HASHTABLE **hashtable)
void	SCIPhashtableClear (SCIP_HASHTABLE *hashtable)
SCIP_RETCODE	SCIPhashtableInsert (SCIP_HASHTABLE *hashtable, void *element)
SCIP_RETCODE	SCIPhashtableSafeInsert (SCIP_HASHTABLE *hashtable, void *element)
void *	SCIPhashtableRetrieve (SCIP_HASHTABLE *hashtable, void *key)
SCIP_Bool	SCIPhashtableExists (SCIP_HASHTABLE *hashtable, void *element)
SCIP_RETCODE	SCIPhashtableRemove (SCIP_HASHTABLE *hashtable, void *element)
void	SCIPhashtableRemoveAll (SCIP_HASHTABLE *hashtable)
SCIP_Longint	SCIPhashtableGetNElements (SCIP_HASHTABLE *hashtable)
int	SCIPhashtableGetNEntries (SCIP_HASHTABLE *hashtable)
void *	SCIPhashtableGetEntry (SCIP_HASHTABLE *hashtable, int entryidx)
SCIP_Real	SCIPhashtableGetLoad (SCIP_HASHTABLE *hashtable)
void	SCIPhashtablePrintStatistics (SCIP_HASHTABLE *hashtable, SCIP_MESSAGEHDLR *messagehdlr)

Macro Definition Documentation

SCIPhashSignature64

#define SCIPhashSignature64

(

a

)

(UINT64_C(0x8000000000000000)>>((UINT32_C(0x9e3779b9) * ((uint32_t)(a)))>>26))

Definition at line 549 of file pub_misc.h.

SCIPhashTwo

#define SCIPhashTwo	(		a,
			b
	)		((uint32_t)((((uint32_t)(a) + 0xd37e9a1ce2148403ULL) * ((uint32_t)(b) + 0xe5fcc163aef32782ULL) )>>32))

Definition at line 551 of file pub_misc.h.

SCIPhashThree

#define SCIPhashThree	(		a,
			b,
			c
	)

Value:

                                                        ((uint32_t)((((uint32_t)(a) + 0xbd5c89185f082658ULL) * ((uint32_t)(b) + 0xe5fcc163aef32782ULL) + \
                                                        (uint32_t)(c) * 0xd37e9a1ce2148403ULL)>>32 ))

Definition at line 553 of file pub_misc.h.

SCIPhashFour

#define SCIPhashFour	(		a,
			b,
			c,
			d
	)

Value:

                                                         ((uint32_t)((((uint32_t)(a) + 0xbd5c89185f082658ULL) * ((uint32_t)(b) + 0xe5fcc163aef32782ULL) + \
                                                         ((uint32_t)(c) + 0xd37e9a1ce2148403ULL) * ((uint32_t)(d) + 0x926f2d4dc4a67218ULL))>>32 ))

Definition at line 556 of file pub_misc.h.

SCIPhashFive

#define SCIPhashFive	(		a,
			b,
			c,
			d,
			e
	)

Value:

                                                         ((uint32_t)((((uint32_t)(a) + 0xbd5c89185f082658ULL) * ((uint32_t)(b) + 0xe5fcc163aef32782ULL) + \
                                                         ((uint32_t)(c) + 0xd37e9a1ce2148403ULL) * ((uint32_t)(d) + 0x926f2d4dc4a67218ULL) + \
                                                           (uint32_t)(e) * 0xf48d4cd331e14327ULL)>>32 ))

Definition at line 559 of file pub_misc.h.

SCIPhashSix

#define SCIPhashSix	(		a,
			b,
			c,
			d,
			e,
			f
	)

Value:

                                                         ((uint32_t)((((uint32_t)(a) + 0xbd5c89185f082658ULL) * ((uint32_t)(b) + 0xe5fcc163aef32782ULL) + \
                                                         ((uint32_t)(c) + 0xd37e9a1ce2148403ULL) * ((uint32_t)(d) + 0x926f2d4dc4a67218ULL) + \
                                                         ((uint32_t)(e) + 0xf48d4cd331e14327ULL) * ((uint32_t)(f) + 0x80791a4edfc44c75ULL))>>32 ))

Definition at line 563 of file pub_misc.h.

SCIPhashSeven

#define SCIPhashSeven	(		a,
			b,
			c,
			d,
			e,
			f,
			g
	)

Value:

                                                         ((uint32_t)((((uint32_t)(a) + 0xbd5c89185f082658ULL) * ((uint32_t)(b) + 0xe5fcc163aef32782ULL) + \
                                                         ((uint32_t)(c) + 0xd37e9a1ce2148403ULL) * ((uint32_t)(d) + 0x926f2d4dc4a67218ULL) + \
                                                         ((uint32_t)(e) + 0xf48d4cd331e14327ULL) * ((uint32_t)(f) + 0x80791a4edfc44c75ULL) + \
                                                         (uint32_t)(g) * 0x7f497d9ba3bd83c0ULL)>>32 ))

Definition at line 567 of file pub_misc.h.

Function Documentation

SCIPrealHashCode()

static INLINE uint32_t SCIPrealHashCode ( double  x )

static

computes a hashcode for double precision floating point values containing 15 significant bits, the sign and the exponent

Definition at line 576 of file pub_misc.h.

References x.

Referenced by SCIP_DECL_HASHKEYVAL().

SCIPhashtableCreate()

SCIP_RETCODE SCIPhashtableCreate	(	SCIP_HASHTABLE **	hashtable,
		BMS_BLKMEM *	blkmem,
		int	tablesize,
		SCIP_DECL_HASHGETKEY((*hashgetkey))	,
		SCIP_DECL_HASHKEYEQ((*hashkeyeq))	,
		SCIP_DECL_HASHKEYVAL((*hashkeyval))	,
		void *	userptr
	)

creates a hash table

Parameters

hashtable	pointer to store the created hash table
blkmem	block memory used to store hash table entries
tablesize	size of the hash table
userptr	user pointer

Definition at line 2299 of file misc.c.

References BMSallocBlockMemory, BMSallocBlockMemoryArray, BMSallocClearBlockMemoryArray, LOG2, MAX, NULL, SCIP_ALLOC, and SCIP_OKAY.

Referenced by addOrbitope(), bilinearTermsInsertEntry(), checkConsnames(), collectBranchingCands(), copyConsPseudoboolean(), detectHiddenProducts(), detectRedundantConstraints(), findCumulativeConss(), inithashmapandtable(), mod2matrixPreprocessColumns(), mod2matrixPreprocessRows(), nodepairqueueCreate(), presoldataInitHashtables(), propdataInit(), SCIP_DECL_EVENTINITSOL(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEURINIT(), SCIP_DECL_PRESOLEXEC(), SCIP_DECL_READERREAD(), SCIP_DECL_READERWRITE(), SCIPcliquetableCreate(), SCIPcutpoolCreate(), SCIPparamsetCreate(), SCIPprobCreate(), SCIPvariableGraphCreate(), SCIPvisualizeConsCumulative(), SCIPwriteLp(), SCIPwriteMps(), SCIPwritePip(), and writeOpb().

SCIPhashtableFree()

void SCIPhashtableFree

(

SCIP_HASHTABLE **

hashtable

)

frees the hash table

Parameters

hashtable

pointer to the hash table

Definition at line 2349 of file misc.c.

References BMSfreeBlockMemory, BMSfreeBlockMemoryArray, SCIP_HashTable::hashes, SCIP_HashTable::mask, MAX, SCIP_HashTable::nelements, NULL, SCIP_Real, SCIPdebugMessage, SCIP_HashTable::shift, and SCIP_HashTable::slots.

Referenced by bilinearTermsFree(), checkConsnames(), collectBranchingCands(), conshdlrdataFree(), copyConsPseudoboolean(), detectHiddenProducts(), detectRedundantConstraints(), findCumulativeConss(), freeOrbitope(), freeShadowTree(), mod2matrixPreprocessColumns(), mod2matrixPreprocessRows(), nodepairqueueCreate(), propdataExit(), propdataInit(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEUREXIT(), SCIP_DECL_PRESOLEXEC(), SCIP_DECL_PRESOLFREE(), SCIP_DECL_READERREAD(), SCIP_DECL_READERWRITE(), SCIPcliquetableFree(), SCIPcutpoolFree(), SCIPparamsetFree(), SCIPprobFree(), SCIPvariableGraphFree(), SCIPvisualizeConsCumulative(), SCIPwriteLp(), SCIPwriteMps(), SCIPwritePip(), and writeOpb().

SCIPhashtableClear()

void SCIPhashtableClear

(

SCIP_HASHTABLE *

hashtable

)

removes all elements of the hash table

Note

From a performance point of view you should not fill and clear a hash table too often since the clearing can be expensive. Clearing is done by looping over all buckets and removing the hash table lists one-by-one.

Deprecated:

Please use SCIPhashtableRemoveAll()

removes all elements of the hash table

Note

From a performance point of view you should not fill and clear a hash table too often since the clearing can be expensive. Clearing is done by looping over all buckets and removing the hash table lists one-by-one.

Deprecated:

Please use SCIPhashtableRemoveAll()

Parameters

hashtable

hash table

Definition at line 2401 of file misc.c.

References SCIPhashtableRemoveAll().

SCIPhashtableInsert()

SCIP_RETCODE SCIPhashtableInsert	(	SCIP_HASHTABLE *	hashtable,
		void *	element
	)

inserts element in hash table (multiple inserts of same element override the previous entry)

inserts element in hash table

Note

multiple inserts of same element overrides previous one

Parameters

hashtable	hash table
element	element to insert into the table

Definition at line 2550 of file misc.c.

References SCIP_HashTable::hashes, hashtableCheckLoad(), hashtableInsert(), hashvalue(), SCIP_HashTable::mask, NULL, SCIP_CALL, SCIP_HashTable::slots, TRUE, and SCIP_HashTable::userptr.

Referenced by addConflictBinvar(), bilinearTermsInsertEntry(), checkConsnames(), cleanupHashDatas(), collectAggregatedVars(), collectBranchingCands(), collectMinactImplicVars(), copyConsPseudoboolean(), correctPresoldata(), createAndAddAndCons(), createConstantAssignment(), createPresoldata(), createVariable(), detectRedundantConstraints(), determineVariableFixings(), fillRelationTables(), findCumulativeConss(), getConflictImplics(), mod2matrixPreprocessColumns(), mod2matrixPreprocessRows(), nodepairqueueCreate(), retrieveParallelConstraints(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTINITSOL(), SCIP_DECL_PRESOLEXEC(), SCIP_DECL_READERWRITE(), SCIPcliquetableAdd(), SCIPcliquetableCleanup(), SCIPcreateConsPseudobooleanWithConss(), SCIPcutpoolAddNewRow(), SCIPprobAddConsName(), SCIPprobAddVarName(), SCIPvariablegraphBreadthFirst(), SCIPvisualizeConsCumulative(), SCIPwriteMps(), selectSolsRandomized(), setupAndSolveSubscipCrossover(), writeOpbFixedVars(), and writeOpbRelevantAnds().

SCIPhashtableSafeInsert()

SCIP_RETCODE SCIPhashtableSafeInsert	(	SCIP_HASHTABLE *	hashtable,
		void *	element
	)

inserts element in hash table (multiple insertion of same element is checked and results in an error)

inserts element in hash table

Note

multiple insertion of same element is checked and results in an error

Parameters

hashtable	hash table
element	element to insert into the table

Definition at line 2582 of file misc.c.

References FALSE, SCIP_HashTable::hashes, hashtableCheckLoad(), hashtableInsert(), hashvalue(), SCIP_HashTable::mask, NULL, SCIP_CALL, SCIP_HashTable::slots, and SCIP_HashTable::userptr.

Referenced by paramsetAdd(), retrieveParallelConstraints(), SCIP_DECL_EVENTEXEC(), and SCIP_DECL_HEUREXEC().

SCIPhashtableRetrieve()

void * SCIPhashtableRetrieve	(	SCIP_HASHTABLE *	hashtable,
		void *	key
	)

retrieve element with key from hash table, returns NULL if not existing

Parameters

hashtable	hash table
key	key to retrieve

Definition at line 2611 of file misc.c.

References ELEM_DISTANCE, SCIP_HashTable::hashes, hashvalue(), SCIP_HashTable::mask, NULL, SCIP_HashTable::shift, SCIP_HashTable::slots, TRUE, and SCIP_HashTable::userptr.

Referenced by applyVariableAssignment(), cancelCol(), cancelRow(), checkConsnames(), consdataFree(), CREATE_CONSTRAINT(), createAndAddAndCons(), createConstantAssignment(), createLinking(), createVariable(), detectProductsUnconditional(), detectRedundantConstraints(), extractGates(), fillRelationTables(), getRowOrder(), mod2matrixPreprocessColumns(), mod2matrixPreprocessRows(), nodepairqueueCreate(), paramSetBool(), paramSetChar(), paramSetInt(), paramSetLongint(), paramSetReal(), paramsetSetHeuristicsAggressive(), paramsetSetHeuristicsFast(), paramsetSetPresolvingAggressive(), paramsetSetPresolvingFast(), paramsetSetSeparatingAggressive(), paramsetSetSeparatingDefault(), parseAggregation(), parseArrayIndex(), parseConstraint(), parseQuadratic(), parseSolveItem(), parseValue(), parseVariableArrayAssignment(), populateRootedPathColumnOrder(), retrieveParallelConstraints(), scalePenalties(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PRESOLEXEC(), SCIPcliquetableAdd(), SCIPcliquetableCleanup(), SCIPcreateConsPseudobooleanWithConss(), SCIPcutpoolAddRow(), SCIPcutpoolDelRow(), SCIPcutpoolIsCutNew(), SCIPgetBilinTermIdxNonlinear(), SCIPhashtableExists(), SCIPparamsetCopyParams(), SCIPparamsetFix(), SCIPparamsetGetBool(), SCIPparamsetGetChar(), SCIPparamsetGetInt(), SCIPparamsetGetLongint(), SCIPparamsetGetParam(), SCIPparamsetGetReal(), SCIPparamsetGetString(), SCIPparamsetIsFixed(), SCIPparamsetSet(), SCIPparamsetSetBool(), SCIPparamsetSetChar(), SCIPparamsetSetDefaultBool(), SCIPparamsetSetDefaultChar(), SCIPparamsetSetDefaultInt(), SCIPparamsetSetDefaultLongint(), SCIPparamsetSetDefaultReal(), SCIPparamsetSetDefaultString(), SCIPparamsetSetEmphasis(), SCIPparamsetSetInt(), SCIPparamsetSetLongint(), SCIPparamsetSetReal(), SCIPparamsetSetString(), SCIPparamsetSetToDefault(), SCIPprobFindCons(), SCIPprobFindVar(), SCIPprobRemoveConsName(), SCIPshadowTreeGetShadowNodeFromNodeNumber(), and transformToOrig().

SCIPhashtableExists()

SCIP_Bool SCIPhashtableExists	(	SCIP_HASHTABLE *	hashtable,
		void *	element
	)

returns whether the given element exists in the table

Parameters

hashtable	hash table
element	element to search in the table

Definition at line 2662 of file misc.c.

References SCIP_HashTable::hashes, SCIP_HashTable::mask, NULL, SCIPhashtableRetrieve(), SCIP_HashTable::slots, and SCIP_HashTable::userptr.

Referenced by addConflictBinvar(), cleanupHashDatas(), collectAggregatedVars(), collectBranchingCands(), collectMinactImplicVars(), consdataFree(), copyConsPseudoboolean(), correctConshdlrdata(), correctPresoldata(), cutpoolDelCut(), determineVariableFixings(), findCumulativeConss(), getConflictImplics(), mod2matrixPreprocessRows(), printBoundSection(), printColumnSection(), resolvePropagation(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_PRESOLEXIT(), SCIP_DECL_READERWRITE(), SCIPcutpoolAddNewRow(), SCIPprobRemoveVarName(), SCIPvariablegraphBreadthFirst(), SCIPvisualizeConsCumulative(), SCIPwriteMps(), selectSolsRandomized(), transformToOrig(), updateConsanddataUses(), and writeOpbFixedVars().

SCIPhashtableRemove()

SCIP_RETCODE SCIPhashtableRemove	(	SCIP_HASHTABLE *	hashtable,
		void *	element
	)

removes element from the hash table, if it exists

Parameters

hashtable	hash table
element	element to remove from the table

Definition at line 2680 of file misc.c.

References ELEM_DISTANCE, SCIP_HashTable::hashes, hashvalue(), SCIP_HashTable::mask, SCIP_HashTable::nelements, NULL, SCIP_OKAY, SCIP_HashTable::shift, SCIP_HashTable::slots, TRUE, and SCIP_HashTable::userptr.

Referenced by cleanupHashDatas(), consdataFree(), correctConshdlrdata(), correctPresoldata(), cutpoolDelCut(), detectRedundantConstraints(), extractGates(), mod2matrixPreprocessRows(), retrieveParallelConstraints(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_PRESOLEXEC(), SCIP_DECL_PRESOLEXIT(), SCIPcliquetableCleanup(), SCIPprobRemoveConsName(), SCIPprobRemoveVarName(), and updateConsanddataUses().

SCIPhashtableRemoveAll()

void SCIPhashtableRemoveAll

(

SCIP_HASHTABLE *

hashtable

)

removes all elements of the hash table

Parameters

hashtable

hash table

Definition at line 2758 of file misc.c.

References BMSclearMemoryArray, SCIP_HashTable::hashes, SCIP_HashTable::mask, SCIP_HashTable::nelements, and NULL.

Referenced by correctPresoldata(), resolvePropagation(), SCIP_DECL_PRESOLEXEC(), SCIP_DECL_PRESOLEXIT(), SCIPcutpoolClear(), SCIPhashtableClear(), and SCIPvariablegraphBreadthFirst().

SCIPhashtableGetNElements()

SCIP_Longint SCIPhashtableGetNElements

(

SCIP_HASHTABLE *

hashtable

)

returns number of hash table elements

Parameters

hashtable

hash table

Definition at line 2770 of file misc.c.

References SCIP_HashTable::nelements, and NULL.

Referenced by SCIP_DECL_HEUREXEC().

SCIPhashtableGetNEntries()

int SCIPhashtableGetNEntries

(

SCIP_HASHTABLE *

hashtable

)

gives the number of entries in the internal arrays of a hash table

Parameters

hashtable

hash table

Definition at line 2780 of file misc.c.

References SCIP_HashTable::mask.

Referenced by detectHiddenProducts(), freeOrbitope(), freeShadowTree(), and SCIP_DECL_PRESOLEXEC().

SCIPhashtableGetEntry()

void * SCIPhashtableGetEntry	(	SCIP_HASHTABLE *	hashtable,
		int	entryidx
	)

gives the element at the given index or NULL if entry at that index has no element

Parameters

hashtable	hash table
entryidx	index of hash table entry

Definition at line 2788 of file misc.c.

References SCIP_HashTable::hashes, NULL, and SCIP_HashTable::slots.

Referenced by detectHiddenProducts(), freeOrbitope(), and freeShadowTree().

SCIPhashtableGetLoad()

SCIP_Real SCIPhashtableGetLoad

(

SCIP_HASHTABLE *

hashtable

)

returns the load of the given hash table in percentage

Parameters

hashtable

hash table

Definition at line 2797 of file misc.c.

References SCIP_HashTable::mask, SCIP_HashTable::nelements, NULL, and SCIP_Real.

SCIPhashtablePrintStatistics()

void SCIPhashtablePrintStatistics	(	SCIP_HASHTABLE *	hashtable,
		SCIP_MESSAGEHDLR *	messagehdlr
	)

prints statistics about hash table usage

Parameters

hashtable	hash table
messagehdlr	message handler

Definition at line 2807 of file misc.c.

References ELEM_DISTANCE, SCIP_HashTable::hashes, SCIP_HashTable::mask, MAX, SCIP_HashTable::nelements, NULL, SCIP_Real, and SCIPmessagePrintInfo().

Referenced by detectRedundantConstraints().