Hash Table

Detailed Description

Functions
int	SCIPcalcHashtableSize (int minsize)
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)
void *	SCIPhashtableRetrieveNext (SCIP_HASHTABLE *hashtable, SCIP_HASHTABLELIST **hashtablelist, 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)
SCIP_Real	SCIPhashtableGetLoad (SCIP_HASHTABLE *hashtable)
void	SCIPhashtablePrintStatistics (SCIP_HASHTABLE *hashtable, SCIP_MESSAGEHDLR *messagehdlr)
	SCIP_DECL_HASHKEYEQ (SCIPhashKeyEqString)
	SCIP_DECL_HASHKEYVAL (SCIPhashKeyValString)
	SCIP_DECL_HASHGETKEY (SCIPhashGetKeyStandard)
	SCIP_DECL_HASHKEYEQ (SCIPhashKeyEqPtr)
	SCIP_DECL_HASHKEYVAL (SCIPhashKeyValPtr)

Function Documentation

int SCIPcalcHashtableSize

(

int

minsize

)

returns a reasonable hash table size (a prime number) that is at least as large as the specified value

Parameters

minsize

minimal size of the hash table

Definition at line 1157 of file misc.c.

References SCIPsortedvecFindInt().

Referenced by applyOfins(), applyVbounds(), checkCurvature(), checkSystemGF2(), checkVarnames(), collectBranchingCands(), copyProb(), copyVars(), createCoveringProblem(), createStartingData(), createSubSCIP(), createTcliqueGraph(), detectRedundantConstraints(), findCumulativeConss(), initAlternativeLP(), initData(), inithashmapandtable(), initPropdata(), nlrowSetupQuadVarsHash(), nodepairqueueCreate(), preprocessCliques(), presolveDisaggregate(), presolveFindDuplicates(), readPolynomial(), removeDoubleAndSingletonsAndPerformDualpresolve(), removeRedundantConssAndNonzeros(), SCIP_DECL_CONSINITPRE(), SCIP_DECL_CONSINITSOL(), SCIP_DECL_CONSTRANS(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PARAMCHGD(), SCIP_DECL_READERWRITE(), SCIPapplyProximity(), SCIPapplyRens(), SCIPapplyZeroobj(), SCIPcliquetableCreate(), SCIPcopy(), SCIPcopyConss(), SCIPcopyOrig(), SCIPcopyOrigConss(), SCIPcreateConsQuadratic(), SCIPcreateFiniteSolCopy(), SCIPcreateWorstCaseProfile(), SCIPexprgraphCreate(), SCIPexprtreeRemoveFixedVars(), SCIPgetConsCopy(), SCIPgetVarCopy(), SCIPnlpCreate(), SCIPvisualizeConsCumulative(), SCIPwriteCliqueGraph(), SCIPwriteLp(), searchEcAggrWithCliques(), setUpEvents(), solveSubMIP(), solveSubproblem(), and writeOpbConstraints().

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 1480 of file misc.c.

References BMSallocClearMemoryArray, BMSallocMemory, NULL, SCIP_ALLOC, and SCIP_OKAY.

Referenced by collectBranchingCands(), detectRedundantConstraints(), findCumulativeConss(), inithashmapandtable(), nodepairqueueCreate(), presoldataInitHashtables(), presolveFindDuplicates(), SCIP_DECL_HEURINIT(), SCIP_DECL_READERREAD(), SCIP_DECL_READERWRITE(), SCIPcliquetableCreate(), SCIPcutpoolCreate(), SCIPexprParse(), SCIPparamsetCreate(), SCIPprobCreate(), SCIPvisualizeConsCumulative(), SCIPwriteLp(), and SCIPwritePip().

void SCIPhashtableFree

(

SCIP_HASHTABLE **

hashtable

)

frees the hash table

Parameters

hashtable

pointer to the hash table

Definition at line 1510 of file misc.c.

References SCIP_HashTable::blkmem, BMSfreeMemory, BMSfreeMemoryArray, hashtablelistFree(), SCIP_HashTable::lists, SCIP_HashTable::nlists, and NULL.

Referenced by collectBranchingCands(), conshdlrdataFree(), detectRedundantConstraints(), findCumulativeConss(), nodepairqueueCreate(), presolveFindDuplicates(), SCIP_DECL_HEUREXIT(), SCIP_DECL_READERREAD(), SCIP_DECL_READERWRITE(), SCIPcliquetableFree(), SCIPcutpoolFree(), SCIPexprParse(), SCIPparamsetFree(), SCIPprobFree(), SCIPvisualizeConsCumulative(), SCIPwriteLp(), and SCIPwritePip().

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 1542 of file misc.c.

References SCIP_HashTable::blkmem, hashtablelistFree(), SCIP_HashTable::lists, SCIP_HashTable::nelements, SCIP_HashTable::nlists, and NULL.

SCIP_RETCODE SCIPhashtableInsert	(	SCIP_HASHTABLE *	hashtable,
		void *	element
	)

inserts element in hash table (multiple inserts of same element possible)

Note

A pointer to a hashtablelist returned by SCIPhashtableRetrieveNext() might get invalid when adding an element to the hash table, due to dynamic resizing.

Parameters

hashtable	hash table
element	element to insert into the table

Definition at line 1567 of file misc.c.

References SCIP_HashTable::blkmem, hashtablelistAppend(), hashtableResize(), SCIP_HashTable::lists, SCIP_HashTable::nelements, SCIP_HashTable::nlists, NULL, SCIP_CALL, SCIP_HASHTABLE_RESIZE_PERCENTAGE, SCIP_OKAY, SCIPhashtableGetLoad(), and SCIP_HashTable::userptr.

Referenced by addConflictBinvar(), cleanupHashDatas(), collectAggregatedVars(), collectBranchingCands(), collectMinactImplicVars(), correctPresoldata(), createAndAddAndCons(), createConstantAssignment(), createPresoldata(), createVariable(), detectRedundantConstraints(), exprparseReadVariable(), findCumulativeConss(), getConflictImplics(), nodepairqueueCreate(), presolveFindDuplicates(), SCIP_DECL_HEUREXEC(), SCIP_DECL_READERWRITE(), SCIPcliquetableAdd(), SCIPcliquetableCleanup(), SCIPcreateConsPseudobooleanWithConss(), SCIPcutpoolAddNewRow(), SCIPhashtableSafeInsert(), SCIPprobAddConsName(), SCIPprobAddVarName(), SCIPvisualizeConsCumulative(), selectSolsRandomized(), and setupSubproblem().

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)

Note

A pointer to a hashtablelist returned by SCIPhashtableRetrieveNext() might get invalid when adding a new element to the hash table, due to dynamic resizing.

Parameters

hashtable	hash table
element	element to insert into the table

Definition at line 1608 of file misc.c.

References NULL, SCIP_CALL, SCIP_KEYALREADYEXISTING, SCIP_OKAY, SCIPhashtableInsert(), SCIPhashtableRetrieve(), and SCIP_HashTable::userptr.

Referenced by paramsetAdd().

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 1627 of file misc.c.

References hashtablelistRetrieve(), SCIP_HashTable::lists, SCIP_HashTable::nlists, NULL, and SCIP_HashTable::userptr.

Referenced by applyVariableAssignment(), consdataFree(), CREATE_CONSTRAINT(), createAndAddAndCons(), createConstantAssignment(), createLinking(), createVariable(), detectRedundantConstraints(), exprparseReadVariable(), extractGates(), nodepairqueueCreate(), paramSetBool(), paramSetChar(), paramSetInt(), paramSetLongint(), paramsetParse(), paramSetReal(), paramsetSetHeuristicsAggressive(), paramsetSetHeuristicsFast(), paramsetSetPresolvingAggressive(), paramsetSetPresolvingFast(), paramsetSetSeparatingAggressive(), paramsetSetSeparatingDefault(), parseAggregation(), parseArrayIndex(), parseConstraint(), parseQuadratic(), parseSolveItem(), parseValue(), parseVariableArrayAssignment(), SCIPcliquetableAdd(), SCIPcliquetableCleanup(), SCIPcreateConsPseudobooleanWithConss(), SCIPcutpoolAddRow(), SCIPcutpoolDelRow(), SCIPhashtableSafeInsert(), SCIPparamsetCopyParams(), SCIPparamsetFix(), SCIPparamsetGetBool(), SCIPparamsetGetChar(), SCIPparamsetGetInt(), SCIPparamsetGetLongint(), SCIPparamsetGetParam(), SCIPparamsetGetReal(), SCIPparamsetGetString(), SCIPparamsetIsFixed(), SCIPparamsetSet(), SCIPparamsetSetBool(), SCIPparamsetSetChar(), SCIPparamsetSetDefaultBool(), SCIPparamsetSetDefaultInt(), SCIPparamsetSetInt(), SCIPparamsetSetLongint(), SCIPparamsetSetReal(), SCIPparamsetSetString(), SCIPparamsetSetToDefault(), SCIPprobFindCons(), SCIPprobFindVar(), and transformToOrig().

void* SCIPhashtableRetrieveNext	(	SCIP_HASHTABLE *	hashtable,
		SCIP_HASHTABLELIST **	hashtablelist,
		void *	key
	)

retrieve element with key from hash table, returns NULL if not existing can be used to retrieve all entries with the same key (one-by-one)

Note

The returned hashtablelist pointer might get invalid when adding a new element to the hash table.

Parameters

hashtable	hash table
hashtablelist	input: entry in hash table list from which to start searching, or NULL output: entry in hash table list corresponding to element after retrieved one, or NULL
key	key to retrieve

Definition at line 1656 of file misc.c.

References hashtablelistRetrieveNext(), SCIP_HashTable::lists, SCIP_HashTable::nlists, NULL, and SCIP_HashTable::userptr.

Referenced by presolveFindDuplicates().

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 1692 of file misc.c.

References hashtablelistFind(), SCIP_HashTable::lists, SCIP_HashTable::nlists, NULL, and SCIP_HashTable::userptr.

Referenced by addConflictBinvar(), cleanupHashDatas(), collectAggregatedVars(), collectBranchingCands(), collectMinactImplicVars(), consdataFree(), correctConshdlrdata(), correctPresoldata(), cutpoolDelCut(), findCumulativeConss(), getConflictImplics(), printBoundSection(), printColumnSection(), resolvePropagation(), SCIP_DECL_READERWRITE(), SCIPprobRemoveConsName(), SCIPprobRemoveVarName(), SCIPvisualizeConsCumulative(), selectSolsRandomized(), setupSubproblem(), transformToOrig(), and updateConsanddataUses().

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 1719 of file misc.c.

References SCIP_HashTable::blkmem, hashtablelistRemove(), SCIP_HashTable::lists, SCIP_HashTable::nelements, SCIP_HashTable::nlists, NULL, SCIP_OKAY, and SCIP_HashTable::userptr.

Referenced by cleanupHashDatas(), consdataFree(), correctConshdlrdata(), correctPresoldata(), cutpoolDelCut(), detectRedundantConstraints(), extractGates(), presolveFindDuplicates(), SCIPcliquetableCleanup(), SCIPprobRemoveConsName(), SCIPprobRemoveVarName(), and updateConsanddataUses().

void SCIPhashtableRemoveAll

(

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.

Parameters

hashtable

hash table

Definition at line 1753 of file misc.c.

References SCIP_HashTable::blkmem, hashtablelistFree(), SCIP_HashTable::lists, SCIP_HashTable::nelements, SCIP_HashTable::nlists, and NULL.

Referenced by correctPresoldata(), hashtableResize(), and resolvePropagation().

SCIP_Longint SCIPhashtableGetNElements

(

SCIP_HASHTABLE *

hashtable

)

returns number of hash table elements

Parameters

hashtable

hash table

Definition at line 1774 of file misc.c.

References SCIP_HashTable::nelements, and NULL.

SCIP_Real SCIPhashtableGetLoad

(

SCIP_HASHTABLE *

hashtable

)

returns the load of the given hash table in percentage

Parameters

hashtable

hash table

Definition at line 1784 of file misc.c.

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

Referenced by hashtableResize(), and SCIPhashtableInsert().

void SCIPhashtablePrintStatistics	(	SCIP_HASHTABLE *	hashtable,
		SCIP_MESSAGEHDLR *	messagehdlr
	)

prints statistics about hash table usage

Parameters

hashtable	hash table
messagehdlr	message handler

Definition at line 1794 of file misc.c.

References SCIP_HashTable::lists, MAX, SCIP_HashTable::nelements, SCIP_HashTableList::next, SCIP_HashTable::nlists, NULL, SCIP_Real, and SCIPmessagePrintInfo().

SCIP_DECL_HASHKEYEQ

(

SCIPhashKeyEqString

)

standard hash key comparator for string keys

returns TRUE iff both keys (i.e. strings) are equal

Definition at line 1839 of file misc.c.

SCIP_DECL_HASHKEYVAL

(

SCIPhashKeyValString

)

standard hashing function for string keys

returns the hash value of the key (i.e. string)

Definition at line 1848 of file misc.c.

SCIP_DECL_HASHGETKEY

(

SCIPhashGetKeyStandard

)

gets the element as the key

Definition at line 1867 of file misc.c.

SCIP_DECL_HASHKEYEQ

(

SCIPhashKeyEqPtr

)

returns TRUE iff both keys(pointer) are equal

Definition at line 1874 of file misc.c.

SCIP_DECL_HASHKEYVAL

(

SCIPhashKeyValPtr

)

returns the hash value of the key

Definition at line 1880 of file misc.c.