Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

hash table that resolves conflicts by queueing, thereby allowing for duplicate entries

Functions

int SCIPcalcMultihashSize (int minsize)
 
SCIP_RETCODE SCIPmultihashCreate (SCIP_MULTIHASH **multihash, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
 
void SCIPmultihashFree (SCIP_MULTIHASH **multihash)
 
SCIP_RETCODE SCIPmultihashInsert (SCIP_MULTIHASH *multihash, void *element)
 
SCIP_RETCODE SCIPmultihashSafeInsert (SCIP_MULTIHASH *multihash, void *element)
 
void * SCIPmultihashRetrieve (SCIP_MULTIHASH *multihash, void *key)
 
void * SCIPmultihashRetrieveNext (SCIP_MULTIHASH *multihash, SCIP_MULTIHASHLIST **multihashlist, void *key)
 
SCIP_Bool SCIPmultihashExists (SCIP_MULTIHASH *multihash, void *element)
 
SCIP_RETCODE SCIPmultihashRemove (SCIP_MULTIHASH *multihash, void *element)
 
void SCIPmultihashRemoveAll (SCIP_MULTIHASH *multihash)
 
SCIP_Longint SCIPmultihashGetNElements (SCIP_MULTIHASH *multihash)
 
SCIP_Real SCIPmultihashGetLoad (SCIP_MULTIHASH *multihash)
 
void SCIPmultihashPrintStatistics (SCIP_MULTIHASH *multihash, SCIP_MESSAGEHDLR *messagehdlr)
 
 SCIP_DECL_HASHKEYEQ (SCIPhashKeyEqString)
 
 SCIP_DECL_HASHKEYVAL (SCIPhashKeyValString)
 
 SCIP_DECL_HASHGETKEY (SCIPhashGetKeyStandard)
 
 SCIP_DECL_HASHKEYEQ (SCIPhashKeyEqPtr)
 
 SCIP_DECL_HASHKEYVAL (SCIPhashKeyValPtr)
 

Function Documentation

◆ SCIPcalcMultihashSize()

int SCIPcalcMultihashSize ( int  minsize)

returns a reasonable hash table size (a prime number) that is at least as large as the specified value

Parameters
minsizeminimal size of the hash table

Definition at line 1455 of file misc.c.

References SCIPsortedvecFindInt().

Referenced by presolveFindDuplicates(), and SCIPrealHashCode().

◆ SCIPmultihashCreate()

SCIP_RETCODE SCIPmultihashCreate ( SCIP_MULTIHASH **  multihash,
BMS_BLKMEM blkmem,
int  tablesize,
SCIP_DECL_HASHGETKEY((*hashgetkey))  ,
SCIP_DECL_HASHKEYEQ((*hashkeyeq))  ,
SCIP_DECL_HASHKEYVAL((*hashkeyval))  ,
void *  userptr 
)

creates a multihash table

Parameters
multihashpointer to store the created multihash table
blkmemblock memory used to store multihash table entries
tablesizesize of the hash table
userptruser pointer

Definition at line 1778 of file misc.c.

References BMSallocBlockMemory, BMSallocClearBlockMemoryArray, NULL, SCIP_ALLOC, and SCIP_OKAY.

Referenced by presolveFindDuplicates(), and SCIPrealHashCode().

◆ SCIPmultihashFree()

void SCIPmultihashFree ( SCIP_MULTIHASH **  multihash)

frees the multihash table

Parameters
multihashpointer to the multihash table

Definition at line 1811 of file misc.c.

References SCIP_MultiHash::blkmem, BMSfreeBlockMemory, BMSfreeBlockMemoryArray, SCIP_MultiHash::lists, multihashlistFree(), SCIP_MultiHash::nlists, and NULL.

Referenced by presolveFindDuplicates(), and SCIPrealHashCode().

◆ SCIPmultihashInsert()

SCIP_RETCODE SCIPmultihashInsert ( SCIP_MULTIHASH multihash,
void *  element 
)

inserts element in multihash table (multiple inserts of same element possible)

Note
A pointer to a multihashlist returned by SCIPmultihashRetrieveNext() might get invalid when adding an element to the hash table, due to dynamic resizing.
Parameters
multihashmultihash table
elementelement to insert into the table

Definition at line 1842 of file misc.c.

References SCIP_MultiHash::blkmem, SCIP_MultiHash::lists, multihashlistAppend(), multihashResize(), SCIP_MultiHash::nelements, SCIP_MultiHash::nlists, NULL, SCIP_CALL, SCIP_MULTIHASH_RESIZE_PERCENTAGE, SCIP_OKAY, SCIPmultihashGetLoad(), and SCIP_MultiHash::userptr.

Referenced by presolveFindDuplicates(), SCIPmultihashSafeInsert(), and SCIPrealHashCode().

◆ SCIPmultihashSafeInsert()

SCIP_RETCODE SCIPmultihashSafeInsert ( SCIP_MULTIHASH multihash,
void *  element 
)

inserts element in multihash table (multiple insertion of same element is checked and results in an error)

Note
A pointer to a multihashlist returned by SCIPmultihashRetrieveNext() might get invalid when adding a new element to the multihash table, due to dynamic resizing.
Parameters
multihashmultihash table
elementelement to insert into the table

Definition at line 1883 of file misc.c.

References NULL, SCIP_CALL, SCIP_KEYALREADYEXISTING, SCIP_OKAY, SCIPmultihashInsert(), SCIPmultihashRetrieve(), and SCIP_MultiHash::userptr.

Referenced by SCIPrealHashCode().

◆ SCIPmultihashRetrieve()

void* SCIPmultihashRetrieve ( SCIP_MULTIHASH multihash,
void *  key 
)

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

Parameters
multihashmultihash table
keykey to retrieve

Definition at line 1902 of file misc.c.

References SCIP_MultiHash::lists, multihashlistRetrieve(), SCIP_MultiHash::nlists, NULL, and SCIP_MultiHash::userptr.

Referenced by SCIPmultihashSafeInsert(), and SCIPrealHashCode().

◆ SCIPmultihashRetrieveNext()

void* SCIPmultihashRetrieveNext ( SCIP_MULTIHASH multihash,
SCIP_MULTIHASHLIST **  multihashlist,
void *  key 
)

retrieve element with key from multihash table, returns NULL if not existing can be used to retrieve all entries with the same key (one-by-one)

Note
The returned multimultihashlist pointer might get invalid when adding a new element to the multihash table.
Parameters
multihashmultihash table
multihashlistinput: entry in hash table list from which to start searching, or NULL output: entry in hash table list corresponding to element after retrieved one, or NULL
keykey to retrieve

Definition at line 1931 of file misc.c.

References SCIP_MultiHash::lists, multihashlistRetrieveNext(), SCIP_MultiHash::nlists, NULL, and SCIP_MultiHash::userptr.

Referenced by presolveFindDuplicates(), and SCIPrealHashCode().

◆ SCIPmultihashExists()

SCIP_Bool SCIPmultihashExists ( SCIP_MULTIHASH multihash,
void *  element 
)

returns whether the given element exists in the multihash table

Parameters
multihashmultihash table
elementelement to search in the table

Definition at line 1967 of file misc.c.

References SCIP_MultiHash::lists, multihashlistFind(), SCIP_MultiHash::nlists, NULL, and SCIP_MultiHash::userptr.

Referenced by SCIPrealHashCode().

◆ SCIPmultihashRemove()

SCIP_RETCODE SCIPmultihashRemove ( SCIP_MULTIHASH multihash,
void *  element 
)

removes element from the multihash table, if it exists

Parameters
multihashmultihash table
elementelement to remove from the table

Definition at line 1994 of file misc.c.

References SCIP_MultiHash::blkmem, SCIP_MultiHash::lists, multihashlistRemove(), SCIP_MultiHash::nelements, SCIP_MultiHash::nlists, NULL, SCIP_OKAY, and SCIP_MultiHash::userptr.

Referenced by presolveFindDuplicates(), and SCIPrealHashCode().

◆ SCIPmultihashRemoveAll()

void SCIPmultihashRemoveAll ( SCIP_MULTIHASH multihash)

removes all elements of the multihash 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.
Parameters
multihashmultihash table

Definition at line 2028 of file misc.c.

References SCIP_MultiHash::blkmem, SCIP_MultiHash::lists, multihashlistFree(), SCIP_MultiHash::nelements, SCIP_MultiHash::nlists, and NULL.

Referenced by multihashResize(), and SCIPrealHashCode().

◆ SCIPmultihashGetNElements()

SCIP_Longint SCIPmultihashGetNElements ( SCIP_MULTIHASH multihash)

returns number of multihash table elements

Parameters
multihashmultihash table

Definition at line 2049 of file misc.c.

References SCIP_MultiHash::nelements, and NULL.

Referenced by SCIPrealHashCode().

◆ SCIPmultihashGetLoad()

SCIP_Real SCIPmultihashGetLoad ( SCIP_MULTIHASH multihash)

returns the load of the given multihash table in percentage

Parameters
multihashmultihash table

Definition at line 2059 of file misc.c.

References SCIP_MultiHash::nelements, SCIP_MultiHash::nlists, NULL, and SCIP_Real.

Referenced by multihashResize(), SCIPmultihashInsert(), and SCIPrealHashCode().

◆ SCIPmultihashPrintStatistics()

void SCIPmultihashPrintStatistics ( SCIP_MULTIHASH multihash,
SCIP_MESSAGEHDLR messagehdlr 
)

prints statistics about multihash table usage

Parameters
multihashmultihash table
messagehdlrmessage handler

Definition at line 2069 of file misc.c.

References SCIP_MultiHash::lists, MAX, SCIP_MultiHash::nelements, SCIP_MultiHashList::next, SCIP_MultiHash::nlists, NULL, SCIP_LONGINT_FORMAT, SCIP_Real, and SCIPmessagePrintInfo().

Referenced by SCIPrealHashCode().

◆ SCIP_DECL_HASHKEYEQ() [1/2]

SCIP_DECL_HASHKEYEQ ( SCIPhashKeyEqString  )

standard hash key comparator for string keys

returns TRUE iff both keys (i.e. strings) are equal

Definition at line 2659 of file misc.c.

Referenced by SCIPrealHashCode().

◆ SCIP_DECL_HASHKEYVAL() [1/2]

SCIP_DECL_HASHKEYVAL ( SCIPhashKeyValString  )

standard hashing function for string keys

returns the hash value of the key (i.e. string)

Definition at line 2668 of file misc.c.

Referenced by SCIPrealHashCode().

◆ SCIP_DECL_HASHGETKEY()

SCIP_DECL_HASHGETKEY ( SCIPhashGetKeyStandard  )

gets the element as the key

Definition at line 2687 of file misc.c.

Referenced by SCIPrealHashCode().

◆ SCIP_DECL_HASHKEYEQ() [2/2]

SCIP_DECL_HASHKEYEQ ( SCIPhashKeyEqPtr  )

returns TRUE iff both keys(pointer) are equal

Definition at line 2694 of file misc.c.

◆ SCIP_DECL_HASHKEYVAL() [2/2]

SCIP_DECL_HASHKEYVAL ( SCIPhashKeyValPtr  )

returns the hash value of the key

Definition at line 2700 of file misc.c.