# SCIP

Solving Constraint Integer Programs

Hash Table

## Detailed Description

hash table that resolves conflicts by probing

## Macros

#define SCIPhashSignature64(a)   ((uint64_t)(UINT64_C(1) << ((a) % 64)))

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

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

#define SCIPcombineTwoInt(a, b)   (((uint64_t) (a) << 32) | (uint64_t) (b) )

#define SCIPcombineThreeInt(a, b, c)   (((uint64_t) (a) << 43) + ((uint64_t) (b) << 21) + ((uint64_t) (c)) )

#define SCIPcombineFourInt(a, b, c, d)   (((uint64_t) (a) << 48) + ((uint64_t) (b) << 32) + ((uint64_t) (c) << 16) + ((uint64_t) (d)) )

#define SCIPrealHashCode(x, n)   ( (x)*(1<<n) >= INT64_MAX ? INT64_MAX : ((x)*(1<<n) <= INT64_MIN ? INT64_MIN : (int64_t)((x)*(1<<n))) )

#define SCIPpositiveRealHashCode(x, n)   ( (x)*(1<<n) >= UINT64_MAX ? UINT64_MAX : (uint64_t)((x)*(1<<n)) )

## Functions

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)

void SCIPhashtablePrintStatistics (SCIP_HASHTABLE *hashtable, SCIP_MESSAGEHDLR *messagehdlr)

## ◆ SCIPhashSignature64

 #define SCIPhashSignature64 ( a ) ((uint64_t)(UINT64_C(1) << ((a) % 64)))

Definition at line 470 of file pub_misc.h.

Referenced by consdataGetFeasibility().

## ◆ SCIPhashTwo

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

Definition at line 471 of file pub_misc.h.

Referenced by randomInitialize(), and SCIP_DECL_HASHKEYVAL().

## ◆ SCIPhashFour

 #define SCIPhashFour ( a, b, c, d )
Value:
((uint32_t)((((uint64_t)(a) + 0xbd5c89185f082658ULL) * ((uint64_t)(b) + 0xe5fcc163aef32782ULL) + \
((uint64_t)(c) + 0xd37e9a1ce2148403ULL) * ((uint64_t)(d) + 0x926f2d4dc4a67218ULL))>>32 ))

Definition at line 473 of file pub_misc.h.

Referenced by SCIP_DECL_HASHKEYVAL().

## ◆ SCIPcombineTwoInt

 #define SCIPcombineTwoInt ( a, b ) (((uint64_t) (a) << 32) | (uint64_t) (b) )

Definition at line 477 of file pub_misc.h.

Referenced by SCIP_DECL_HASHKEYVAL().

## ◆ SCIPcombineThreeInt

 #define SCIPcombineThreeInt ( a, b, c ) (((uint64_t) (a) << 43) + ((uint64_t) (b) << 21) + ((uint64_t) (c)) )

Definition at line 479 of file pub_misc.h.

Referenced by SCIP_DECL_HASHKEYVAL().

## ◆ SCIPcombineFourInt

 #define SCIPcombineFourInt ( a, b, c, d ) (((uint64_t) (a) << 48) + ((uint64_t) (b) << 32) + ((uint64_t) (c) << 16) + ((uint64_t) (d)) )

Definition at line 481 of file pub_misc.h.

## ◆ SCIPrealHashCode

 #define SCIPrealHashCode ( x, n ) ( (x)*(1<= INT64_MAX ? INT64_MAX : ((x)*(1<

Definition at line 484 of file pub_misc.h.

## ◆ SCIPpositiveRealHashCode

 #define SCIPpositiveRealHashCode ( x, n ) ( (x)*(1<= UINT64_MAX ? UINT64_MAX : (uint64_t)((x)*(1<

Definition at line 486 of file pub_misc.h.

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

## ◆ SCIPhashtableFree()

 void SCIPhashtableFree ( SCIP_HASHTABLE ** hashtable )

frees the hash table

Parameters
 hashtable pointer to the hash table

Definition at line 2065 of file misc.c.

## ◆ 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:

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:
Parameters
 hashtable hash table

Definition at line 2117 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 2254 of file misc.c.

## ◆ 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 2286 of file misc.c.

## ◆ SCIPhashtableRetrieve()

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

## ◆ 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 2366 of file misc.c.

## ◆ 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 2384 of file misc.c.

## ◆ SCIPhashtableRemoveAll()

 void SCIPhashtableRemoveAll ( SCIP_HASHTABLE * hashtable )

removes all elements of the hash table

Parameters
 hashtable hash table

Definition at line 2462 of file misc.c.

## ◆ SCIPhashtableGetNElements()

 SCIP_Longint SCIPhashtableGetNElements ( SCIP_HASHTABLE * hashtable )

returns number of hash table elements

Parameters
 hashtable hash table

Definition at line 2474 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 2484 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 2494 of file misc.c.