# SCIP

Solving Constraint Integer Programs

Hash Table

## 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)((((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)) )

## 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)

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)

int SCIPhashtableGetNEntries (SCIP_HASHTABLE *hashtable)

void * SCIPhashtableGetEntry (SCIP_HASHTABLE *hashtable, int entryidx)

void SCIPhashtablePrintStatistics (SCIP_HASHTABLE *hashtable, SCIP_MESSAGEHDLR *messagehdlr)

## ◆ SCIPhashSignature64

 #define SCIPhashSignature64 ( a ) (UINT64_C(0x8000000000000000)>>((UINT32_C(0x9e3779b9) * ((uint32_t)(a)))>>26))

Definition at line 473 of file pub_misc.h.

Referenced by consdataGetFeasibility(), and SCIP_DECL_HASHKEYVAL().

## ◆ SCIPhashTwo

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

Definition at line 474 of file pub_misc.h.

Referenced by SCIP_DECL_HASHKEYVAL(), and SCIPrandomSetSeed().

## ◆ 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 ))
SCIP_VAR ** b
Definition: circlepacking.c:56
SCIP_VAR * a
Definition: circlepacking.c:57

Definition at line 476 of file pub_misc.h.

## ◆ SCIPcombineTwoInt

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

Definition at line 480 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 482 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 484 of file pub_misc.h.

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

## ◆ SCIPhashtableFree()

 void SCIPhashtableFree ( SCIP_HASHTABLE ** hashtable )

frees the hash table

Parameters
 hashtable pointer to the hash table

Definition at line 2064 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 2116 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 2265 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 2297 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 2377 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 2395 of file misc.c.

## ◆ SCIPhashtableRemoveAll()

 void SCIPhashtableRemoveAll ( SCIP_HASHTABLE * hashtable )

removes all elements of the hash table

Parameters
 hashtable hash table

Definition at line 2473 of file misc.c.

## ◆ SCIPhashtableGetNElements()

 SCIP_Longint SCIPhashtableGetNElements ( SCIP_HASHTABLE * hashtable )

returns number of hash table elements

Parameters
 hashtable hash table

Definition at line 2485 of file misc.c.

References SCIP_HashTable::nelements, and NULL.

Referenced by 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 2495 of file misc.c.

Referenced by 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 2503 of file misc.c.

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

Referenced by SCIPrealHashCode().

 SCIP_Real SCIPhashtableGetLoad ( SCIP_HASHTABLE * hashtable )

returns the load of the given hash table in percentage

Parameters
 hashtable hash table

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

Referenced by SCIPrealHashCode().