Scippy

    SCIP

    Solving Constraint Integer Programs

    Macros | Functions
    Hash Table
    Public API of SCIP » Core API » Data Structures

    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)
     
    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 566 of file pub_misc.h.

    ◆ SCIPhashTwo

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

    Definition at line 568 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 ))
    a
    SCIP_VAR * a
    Definition: circlepacking.c:66
    b
    SCIP_VAR ** b
    Definition: circlepacking.c:65

    Definition at line 570 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 573 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 576 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 580 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 584 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 593 of file pub_misc.h.

    References ABS, SCIPisFinite, 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
    hashtablepointer to store the created hash table
    blkmemblock memory used to store hash table entries
    tablesizesize of the hash table
    userptruser pointer

    Definition at line 2298 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_CONSINIT(), SCIP_DECL_EVENTINITSOL(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEURINIT(), SCIP_DECL_PRESOLEXEC(), SCIP_DECL_READERREAD(), SCIP_DECL_READERWRITE(), SCIPcliquetableCreate(), SCIPcutpoolCreate(), SCIPhypergraphComputeOverlaps(), SCIPparamsetCreate(), SCIPprobCreate(), SCIPvariableGraphCreate(), SCIPvisualizeConsCumulative(), SCIPwriteLp(), SCIPwriteMps(), SCIPwritePip(), and writeOpb().

    ◆ SCIPhashtableFree()

    void SCIPhashtableFree ( SCIP_HASHTABLE **  hashtable)

    frees the hash table

    Parameters
    hashtablepointer to the hash table

    Definition at line 2348 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_CONSEXIT(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEUREXIT(), SCIP_DECL_PRESOLEXEC(), SCIP_DECL_PRESOLFREE(), SCIP_DECL_READERREAD(), SCIP_DECL_READERWRITE(), SCIPcliquetableFree(), SCIPcutpoolFree(), SCIPhypergraphClear(), SCIPhypergraphFree(), SCIPparamsetFree(), SCIPprobFree(), SCIPvariableGraphFree(), SCIPvisualizeConsCumulative(), SCIPwriteLp(), SCIPwriteMps(), SCIPwritePip(), and writeOpb().

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

    Definition at line 2535 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(), findOverlap(), getConflictImplics(), mod2matrixPreprocessColumns(), mod2matrixPreprocessRows(), nodepairqueueCreate(), retrieveParallelConstraints(), SCIP_DECL_CONSCHECK(), 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
    hashtablehash table
    elementelement to insert into the table

    Definition at line 2567 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
    hashtablehash table
    keykey to retrieve

    Definition at line 2596 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(), findOverlap(), 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
    hashtablehash table
    elementelement to search in the table

    Definition at line 2647 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(), resolvePropagation(), SCIP_DECL_CONSCHECK(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_PRESOLEXIT(), SCIP_DECL_READERWRITE(), SCIP_DECL_SORTPTRCOMP(), 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
    hashtablehash table
    elementelement to remove from the table

    Definition at line 2665 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
    hashtablehash table

    Definition at line 2743 of file misc.c.

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

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

    ◆ SCIPhashtableGetNElements()

    SCIP_Longint SCIPhashtableGetNElements ( SCIP_HASHTABLE *  hashtable)

    returns number of hash table elements

    Parameters
    hashtablehash table

    Definition at line 2755 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
    hashtablehash table

    Definition at line 2765 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
    hashtablehash table
    entryidxindex of hash table entry

    Definition at line 2773 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
    hashtablehash table

    Definition at line 2782 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
    hashtablehash table
    messagehdlrmessage handler

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