Scippy

SCIP

Solving Constraint Integer Programs

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_EXPORT 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)
 
SCIP_EXPORT void SCIPhashtableFree (SCIP_HASHTABLE **hashtable)
 
SCIP_EXPORT void SCIPhashtableClear (SCIP_HASHTABLE *hashtable)
 
SCIP_EXPORT SCIP_RETCODE SCIPhashtableInsert (SCIP_HASHTABLE *hashtable, void *element)
 
SCIP_EXPORT SCIP_RETCODE SCIPhashtableSafeInsert (SCIP_HASHTABLE *hashtable, void *element)
 
SCIP_EXPORT void * SCIPhashtableRetrieve (SCIP_HASHTABLE *hashtable, void *key)
 
SCIP_EXPORT SCIP_Bool SCIPhashtableExists (SCIP_HASHTABLE *hashtable, void *element)
 
SCIP_EXPORT SCIP_RETCODE SCIPhashtableRemove (SCIP_HASHTABLE *hashtable, void *element)
 
SCIP_EXPORT void SCIPhashtableRemoveAll (SCIP_HASHTABLE *hashtable)
 
SCIP_EXPORT SCIP_Longint SCIPhashtableGetNElements (SCIP_HASHTABLE *hashtable)
 
SCIP_EXPORT int SCIPhashtableGetNEntries (SCIP_HASHTABLE *hashtable)
 
SCIP_EXPORT void * SCIPhashtableGetEntry (SCIP_HASHTABLE *hashtable, int entryidx)
 
SCIP_EXPORT SCIP_Real SCIPhashtableGetLoad (SCIP_HASHTABLE *hashtable)
 
SCIP_EXPORT 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 507 of file pub_misc.h.

Referenced by consdataGetFeasibility(), and SCIP_DECL_HASHKEYVAL().

◆ SCIPhashTwo

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

Definition at line 509 of file pub_misc.h.

Referenced by hashIndexPair(), SCIP_DECL_HASHKEYVAL(), and SCIPrandomSetSeed().

◆ SCIPhashThree

#define SCIPhashThree (   a,
  b,
 
)
Value:
((uint32_t)((((uint32_t)(a) + 0xbd5c89185f082658ULL) * ((uint32_t)(b) + 0xe5fcc163aef32782ULL) + \
(uint32_t)(c) * 0xd37e9a1ce2148403ULL)>>32 ))
SCIP_VAR ** b
Definition: circlepacking.c:56
SCIP_VAR * a
Definition: circlepacking.c:57

Definition at line 511 of file pub_misc.h.

Referenced by SCIP_DECL_HASHKEYVAL().

◆ SCIPhashFour

#define SCIPhashFour (   a,
  b,
  c,
 
)
Value:
((uint32_t)((((uint32_t)(a) + 0xbd5c89185f082658ULL) * ((uint32_t)(b) + 0xe5fcc163aef32782ULL) + \
((uint32_t)(c) + 0xd37e9a1ce2148403ULL) * ((uint32_t)(d) + 0x926f2d4dc4a67218ULL))>>32 ))
SCIP_VAR ** b
Definition: circlepacking.c:56
SCIP_VAR * a
Definition: circlepacking.c:57

Definition at line 514 of file pub_misc.h.

Referenced by SCIP_DECL_HASHKEYVAL().

◆ SCIPhashFive

#define SCIPhashFive (   a,
  b,
  c,
  d,
 
)
Value:
((uint32_t)((((uint32_t)(a) + 0xbd5c89185f082658ULL) * ((uint32_t)(b) + 0xe5fcc163aef32782ULL) + \
((uint32_t)(c) + 0xd37e9a1ce2148403ULL) * ((uint32_t)(d) + 0x926f2d4dc4a67218ULL) + \
(uint32_t)(e) * 0xf48d4cd331e14327ULL)>>32 ))
SCIP_VAR ** b
Definition: circlepacking.c:56
SCIP_VAR * a
Definition: circlepacking.c:57

Definition at line 517 of file pub_misc.h.

◆ SCIPhashSix

#define SCIPhashSix (   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) * ((uint32_t)(f) + 0x80791a4edfc44c75ULL))>>32 ))
SCIP_VAR ** b
Definition: circlepacking.c:56
SCIP_VAR * a
Definition: circlepacking.c:57

Definition at line 521 of file pub_misc.h.

◆ SCIPhashSeven

#define SCIPhashSeven (   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) + \
(uint32_t)(g) * 0x7f497d9ba3bd83c0ULL)>>32 ))
SCIP_VAR ** b
Definition: circlepacking.c:56
SCIP_VAR * a
Definition: circlepacking.c:57

Definition at line 525 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 534 of file pub_misc.h.

References nnodes, SCIP_Bool, SCIP_DECL_HASHGETKEY(), SCIP_DECL_HASHKEYEQ(), SCIP_DECL_HASHKEYVAL(), SCIP_EXPORT, 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(), SCIPcalcGreComDiv(), SCIPcalcIntegralScalar(), SCIPcalcMachineEpsilon(), SCIPcalcMultihashSize(), 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(), and SCIPselectSimpleValue().

Referenced by SCIP_DECL_HASHKEYVAL().

◆ SCIPhashtableCreate()

◆ SCIPhashtableFree()

◆ SCIPhashtableClear()

SCIP_EXPORT 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
hashtablehash table

Definition at line 2337 of file misc.c.

References SCIPhashtableRemoveAll().

Referenced by SCIPrealHashCode().

◆ SCIPhashtableInsert()

SCIP_EXPORT SCIP_RETCODE SCIPhashtableInsert ( SCIP_HASHTABLE hashtable,
void *  element 
)

◆ SCIPhashtableSafeInsert()

SCIP_EXPORT 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
hashtablehash table
elementelement to insert into the table

Definition at line 2518 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(), SCIP_DECL_HEUREXEC(), and SCIPrealHashCode().

◆ SCIPhashtableRetrieve()

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

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

Parameters
hashtablehash table
keykey to retrieve

Definition at line 2547 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(), detectRedundantConstraints(), exprparseReadVariable(), extractGates(), 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(), SCIPhashtableExists(), SCIPparamsetCopyParams(), SCIPparamsetFix(), SCIPparamsetGetBool(), SCIPparamsetGetChar(), SCIPparamsetGetInt(), SCIPparamsetGetLongint(), SCIPparamsetGetParam(), SCIPparamsetGetReal(), SCIPparamsetGetString(), SCIPparamsetIsFixed(), SCIPparamsetSet(), SCIPparamsetSetBool(), SCIPparamsetSetChar(), SCIPparamsetSetDefaultBool(), SCIPparamsetSetDefaultInt(), SCIPparamsetSetEmphasis(), SCIPparamsetSetInt(), SCIPparamsetSetLongint(), SCIPparamsetSetReal(), SCIPparamsetSetString(), SCIPparamsetSetToDefault(), SCIPprobFindCons(), SCIPprobFindVar(), SCIPprobRemoveConsName(), SCIPrealHashCode(), and transformToOrig().

◆ SCIPhashtableExists()

◆ SCIPhashtableRemove()

◆ SCIPhashtableRemoveAll()

SCIP_EXPORT void SCIPhashtableRemoveAll ( SCIP_HASHTABLE hashtable)

removes all elements of the hash table

Parameters
hashtablehash table

Definition at line 2694 of file misc.c.

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

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

◆ SCIPhashtableGetNElements()

SCIP_EXPORT SCIP_Longint SCIPhashtableGetNElements ( SCIP_HASHTABLE hashtable)

returns number of hash table elements

Parameters
hashtablehash table

Definition at line 2706 of file misc.c.

References SCIP_HashTable::nelements, and NULL.

Referenced by SCIP_DECL_HEUREXEC(), and SCIPrealHashCode().

◆ SCIPhashtableGetNEntries()

SCIP_EXPORT int SCIPhashtableGetNEntries ( SCIP_HASHTABLE hashtable)

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

Parameters
hashtablehash table

Definition at line 2716 of file misc.c.

References SCIP_HashTable::mask.

Referenced by SCIPrealHashCode().

◆ SCIPhashtableGetEntry()

SCIP_EXPORT 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
hashtablehash table
entryidxindex of hash table entry

Definition at line 2724 of file misc.c.

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

Referenced by SCIPrealHashCode().

◆ SCIPhashtableGetLoad()

SCIP_EXPORT SCIP_Real SCIPhashtableGetLoad ( SCIP_HASHTABLE hashtable)

returns the load of the given hash table in percentage

Parameters
hashtablehash table

Definition at line 2733 of file misc.c.

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

Referenced by SCIPrealHashCode().

◆ SCIPhashtablePrintStatistics()

SCIP_EXPORT void SCIPhashtablePrintStatistics ( SCIP_HASHTABLE hashtable,
SCIP_MESSAGEHDLR messagehdlr 
)

prints statistics about hash table usage

Parameters
hashtablehash table
messagehdlrmessage handler

Definition at line 2743 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().