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) |
Macro Definition Documentation
◆ SCIPhashSignature64
#define SCIPhashSignature64 | ( | a | ) | (UINT64_C(0x8000000000000000)>>((UINT32_C(0x9e3779b9) * ((uint32_t)(a)))>>26)) |
Definition at line 517 of file pub_misc.h.
Referenced by calcSignature(), consdataGetFeasibility(), and SCIP_DECL_HASHKEYVAL().
◆ SCIPhashTwo
#define SCIPhashTwo | ( | a, | |
b | |||
) | ((uint32_t)((((uint32_t)(a) + 0xd37e9a1ce2148403ULL) * ((uint32_t)(b) + 0xe5fcc163aef32782ULL) )>>32)) |
Definition at line 519 of file pub_misc.h.
Referenced by hashIndexPair(), SCIP_DECL_HASHKEYVAL(), and SCIPrandomSetSeed().
◆ SCIPhashThree
Definition at line 521 of file pub_misc.h.
Referenced by SCIP_DECL_HASHKEYVAL().
◆ SCIPhashFour
Definition at line 524 of file pub_misc.h.
Referenced by SCIP_DECL_HASHKEYVAL().
◆ SCIPhashFive
Definition at line 527 of file pub_misc.h.
◆ SCIPhashSix
Definition at line 531 of file pub_misc.h.
◆ SCIPhashSeven
Definition at line 535 of file pub_misc.h.
Function Documentation
◆ SCIPrealHashCode()
|
static |
computes a hashcode for double precision floating point values containing 15 significant bits, the sign and the exponent
Definition at line 544 of file pub_misc.h.
References eps, nnodes, SCIP_Bool, SCIP_DECL_HASHGETKEY(), SCIP_DECL_HASHKEYEQ(), SCIP_DECL_HASHKEYVAL(), SCIP_DECL_NEWTONEVAL, SCIP_Longint, SCIP_Real, SCIPactivityCreate(), SCIPactivityFree(), SCIPactivityGetDemand(), SCIPactivityGetDuration(), SCIPactivityGetEnergy(), SCIPactivityGetVar(), SCIPbtCreate(), SCIPbtFree(), SCIPbtGetRoot(), SCIPbtIsEmpty(), SCIPbtnodeCreate(), SCIPbtnodeFree(), SCIPbtnodeGetData(), SCIPbtnodeGetLeftchild(), SCIPbtnodeGetParent(), SCIPbtnodeGetRightchild(), SCIPbtnodeGetSibling(), SCIPbtnodeIsLeaf(), SCIPbtnodeIsLeftchild(), SCIPbtnodeIsRightchild(), SCIPbtnodeIsRoot(), SCIPbtnodeSetData(), SCIPbtnodeSetLeftchild(), SCIPbtnodeSetParent(), SCIPbtnodeSetRightchild(), SCIPbtPrintGml(), SCIPbtSetRoot(), SCIPcalcBinomCoef(), SCIPcalcFibHash(), SCIPcalcGreComDiv(), SCIPcalcIntegralScalar(), SCIPcalcMachineEpsilon(), SCIPcalcMultihashSize(), SCIPcalcRootNewton(), SCIPcalcSmaComMul(), SCIPdigraphAddArc(), SCIPdigraphAddArcSafe(), SCIPdigraphComputeDirectedComponents(), SCIPdigraphComputeUndirectedComponents(), SCIPdigraphFree(), SCIPdigraphFreeComponents(), SCIPdigraphGetArticulationPoints(), SCIPdigraphGetComponent(), SCIPdigraphGetNArcs(), SCIPdigraphGetNComponents(), SCIPdigraphGetNNodes(), SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPdigraphPrint(), SCIPdigraphPrintComponents(), SCIPdigraphPrintGml(), SCIPdigraphResize(), SCIPdigraphSetNodeData(), SCIPdigraphSetNSuccessors(), SCIPdigraphSetSizes(), SCIPdigraphTopoSortComponents(), SCIPdisjointsetClear(), SCIPdisjointsetFind(), SCIPdisjointsetGetComponentCount(), SCIPdisjointsetGetSize(), SCIPdisjointsetUnion(), SCIPfindSimpleRational(), SCIPhashmapCreate(), SCIPhashmapEntryGetImage(), SCIPhashmapEntryGetImageInt(), SCIPhashmapEntryGetImageReal(), SCIPhashmapEntryGetOrigin(), SCIPhashmapEntrySetImage(), SCIPhashmapEntrySetImageInt(), SCIPhashmapEntrySetImageReal(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapGetEntry(), SCIPhashmapGetImage(), SCIPhashmapGetImageInt(), SCIPhashmapGetImageReal(), SCIPhashmapGetNElements(), SCIPhashmapGetNEntries(), SCIPhashmapInsert(), SCIPhashmapInsertInt(), SCIPhashmapInsertReal(), SCIPhashmapIsEmpty(), SCIPhashmapPrintStatistics(), SCIPhashmapRemove(), SCIPhashmapRemoveAll(), SCIPhashmapSetImage(), SCIPhashmapSetImageInt(), SCIPhashmapSetImageReal(), SCIPhashsetCreate(), SCIPhashsetExists(), SCIPhashsetFree(), SCIPhashsetGetNElements(), SCIPhashsetGetNSlots(), SCIPhashsetGetSlots(), SCIPhashsetInsert(), SCIPhashsetIsEmpty(), SCIPhashsetPrintStatistics(), SCIPhashsetRemove(), SCIPhashsetRemoveAll(), SCIPhashtableClear(), SCIPhashtableCreate(), SCIPhashtableExists(), SCIPhashtableFree(), SCIPhashtableGetEntry(), SCIPhashtableGetLoad(), SCIPhashtableGetNElements(), SCIPhashtableGetNEntries(), SCIPhashtableInsert(), SCIPhashtablePrintStatistics(), SCIPhashtableRemove(), SCIPhashtableRemoveAll(), SCIPhashtableRetrieve(), SCIPhashtableSafeInsert(), SCIPmultihashCreate(), SCIPmultihashExists(), SCIPmultihashFree(), SCIPmultihashGetLoad(), SCIPmultihashGetNElements(), SCIPmultihashInsert(), SCIPmultihashPrintStatistics(), SCIPmultihashRemove(), SCIPmultihashRemoveAll(), SCIPmultihashRetrieve(), SCIPmultihashRetrieveNext(), SCIPmultihashSafeInsert(), SCIPnextafter(), SCIPprofileCreate(), SCIPprofileDeleteCore(), SCIPprofileFindLeft(), SCIPprofileFree(), SCIPprofileGetCapacity(), SCIPprofileGetEarliestFeasibleStart(), SCIPprofileGetLatestFeasibleStart(), SCIPprofileGetLoad(), SCIPprofileGetLoads(), SCIPprofileGetNTimepoints(), SCIPprofileGetTime(), SCIPprofileGetTimepoints(), SCIPprofileInsertCore(), SCIPprofilePrint(), SCIPrealToRational(), SCIPselectSimpleValue(), and 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 2246 of file misc.c.
References BMSallocBlockMemory, BMSallocBlockMemoryArray, BMSallocClearBlockMemoryArray, MAX, NULL, SCIP_ALLOC, and SCIP_OKAY.
Referenced by bilinearTermsInsertEntry(), checkConsnames(), collectBranchingCands(), computeSymmetryGroup(), copyConsPseudoboolean(), detectHiddenProducts(), detectRedundantConstraints(), fillGraphByConss(), fillGraphByNonlinearConss(), findCumulativeConss(), inithashmapandtable(), mod2matrixPreprocessColumns(), mod2matrixPreprocessRows(), nodepairqueueCreate(), presoldataInitHashtables(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEURINIT(), SCIP_DECL_PRESOLEXEC(), SCIP_DECL_READERREAD(), SCIP_DECL_READERWRITE(), SCIPcliquetableCreate(), SCIPcutpoolCreate(), SCIPparamsetCreate(), SCIPprobCreate(), SCIPrealHashCode(), 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 2296 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(), computeSymmetryGroup(), conshdlrdataFree(), copyConsPseudoboolean(), detectHiddenProducts(), detectRedundantConstraints(), fillGraphByConss(), fillGraphByNonlinearConss(), findCumulativeConss(), mod2matrixPreprocessColumns(), mod2matrixPreprocessRows(), nodepairqueueCreate(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEUREXIT(), SCIP_DECL_PRESOLEXEC(), SCIP_DECL_READERREAD(), SCIP_DECL_READERWRITE(), SCIPcliquetableFree(), SCIPcutpoolFree(), SCIPparamsetFree(), SCIPprobFree(), SCIPrealHashCode(), 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 2348 of file misc.c.
References SCIPhashtableRemoveAll().
Referenced by SCIPrealHashCode().
◆ 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 2497 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(), computeSymmetryGroup(), copyConsPseudoboolean(), correctPresoldata(), createAndAddAndCons(), createConstantAssignment(), createPresoldata(), createVariable(), detectRedundantConstraints(), determineVariableFixings(), fillGraphByConss(), fillGraphByNonlinearConss(), fillRelationTables(), findCumulativeConss(), getConflictImplics(), mod2matrixPreprocessColumns(), mod2matrixPreprocessRows(), nodepairqueueCreate(), retrieveParallelConstraints(), SCIP_DECL_PRESOLEXEC(), SCIP_DECL_READERWRITE(), SCIPcliquetableAdd(), SCIPcliquetableCleanup(), SCIPcreateConsPseudobooleanWithConss(), SCIPcutpoolAddNewRow(), SCIPprobAddConsName(), SCIPprobAddVarName(), SCIPrealHashCode(), 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 2529 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_HEUREXEC(), and SCIPrealHashCode().
◆ 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 2558 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(), computeSymmetryGroup(), consdataFree(), CREATE_CONSTRAINT(), createAndAddAndCons(), createConstantAssignment(), createLinking(), createVariable(), detectProductsUnconditional(), detectRedundantConstraints(), extractGates(), fillGraphByConss(), fillGraphByNonlinearConss(), fillRelationTables(), getParallelConsKey(), mod2matrixPreprocessColumns(), mod2matrixPreprocessRows(), nodepairqueueCreate(), paramSetBool(), paramSetChar(), paramSetInt(), paramSetLongint(), paramsetParse(), paramSetReal(), paramsetSetHeuristicsAggressive(), paramsetSetHeuristicsFast(), paramsetSetPresolvingAggressive(), paramsetSetPresolvingFast(), paramsetSetSeparatingAggressive(), paramsetSetSeparatingDefault(), parseAggregation(), parseArrayIndex(), parseConstraint(), parseQuadratic(), parseSolveItem(), parseValue(), parseVariableArrayAssignment(), 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(), SCIPparamsetSetBool(), SCIPparamsetSetChar(), SCIPparamsetSetDefaultBool(), SCIPparamsetSetDefaultChar(), SCIPparamsetSetDefaultInt(), SCIPparamsetSetDefaultLongint(), SCIPparamsetSetDefaultReal(), SCIPparamsetSetDefaultString(), SCIPparamsetSetEmphasis(), SCIPparamsetSetInt(), SCIPparamsetSetLongint(), SCIPparamsetSetReal(), SCIPparamsetSetString(), SCIPparamsetSetToDefault(), SCIPprobFindCons(), SCIPprobFindVar(), SCIPprobRemoveConsName(), SCIPrealHashCode(), 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 2609 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(), computeSymmetryGroup(), consdataFree(), copyConsPseudoboolean(), correctConshdlrdata(), correctPresoldata(), cutpoolDelCut(), determineVariableFixings(), fillGraphByConss(), fillGraphByNonlinearConss(), findCumulativeConss(), getConflictImplics(), mod2matrixPreprocessRows(), printBoundSection(), printColumnSection(), resolvePropagation(), SCIP_DECL_READERWRITE(), SCIPcutpoolAddNewRow(), SCIPprobRemoveVarName(), SCIPrealHashCode(), 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 2627 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_PRESOLEXEC(), SCIPcliquetableCleanup(), SCIPprobRemoveConsName(), SCIPprobRemoveVarName(), SCIPrealHashCode(), and updateConsanddataUses().
◆ SCIPhashtableRemoveAll()
void SCIPhashtableRemoveAll | ( | SCIP_HASHTABLE * | hashtable | ) |
removes all elements of the hash table
- Parameters
-
hashtable hash table
Definition at line 2705 of file misc.c.
References BMSclearMemoryArray, SCIP_HashTable::hashes, SCIP_HashTable::mask, SCIP_HashTable::nelements, and NULL.
Referenced by correctPresoldata(), resolvePropagation(), SCIP_DECL_PRESOLEXEC(), SCIPcutpoolClear(), SCIPhashtableClear(), SCIPrealHashCode(), and SCIPvariablegraphBreadthFirst().
◆ SCIPhashtableGetNElements()
SCIP_Longint SCIPhashtableGetNElements | ( | SCIP_HASHTABLE * | hashtable | ) |
returns number of hash table elements
- Parameters
-
hashtable hash table
Definition at line 2717 of file misc.c.
References SCIP_HashTable::nelements, and NULL.
Referenced by SCIP_DECL_HEUREXEC(), and SCIPrealHashCode().
◆ 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 2727 of file misc.c.
References SCIP_HashTable::mask.
Referenced by detectHiddenProducts(), SCIP_DECL_PRESOLEXEC(), and SCIPrealHashCode().
◆ 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 2735 of file misc.c.
References SCIP_HashTable::hashes, NULL, and SCIP_HashTable::slots.
Referenced by detectHiddenProducts(), and SCIPrealHashCode().
◆ SCIPhashtableGetLoad()
SCIP_Real SCIPhashtableGetLoad | ( | SCIP_HASHTABLE * | hashtable | ) |
returns the load of the given hash table in percentage
- Parameters
-
hashtable hash table
Definition at line 2744 of file misc.c.
References SCIP_HashTable::mask, SCIP_HashTable::nelements, NULL, and SCIP_Real.
Referenced by SCIPrealHashCode().
◆ 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 2754 of file misc.c.
References ELEM_DISTANCE, SCIP_HashTable::hashes, SCIP_HashTable::mask, MAX, SCIP_HashTable::nelements, NULL, SCIP_Real, and SCIPmessagePrintInfo().
Referenced by SCIPrealHashCode().