Detailed Description

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

Functions
SCIP_EXPORT int	SCIPcalcMultihashSize (int minsize)

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

SCIP_EXPORT void	SCIPmultihashFree (SCIP_MULTIHASH **multihash)

SCIP_EXPORT SCIP_RETCODE	SCIPmultihashInsert (SCIP_MULTIHASH multihash, void element)

SCIP_EXPORT SCIP_RETCODE	SCIPmultihashSafeInsert (SCIP_MULTIHASH multihash, void element)

SCIP_EXPORT void *	SCIPmultihashRetrieve (SCIP_MULTIHASH multihash, void key)

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

SCIP_EXPORT SCIP_Bool	SCIPmultihashExists (SCIP_MULTIHASH multihash, void element)

SCIP_EXPORT SCIP_RETCODE	SCIPmultihashRemove (SCIP_MULTIHASH multihash, void element)

SCIP_EXPORT void	SCIPmultihashRemoveAll (SCIP_MULTIHASH *multihash)

SCIP_EXPORT SCIP_Longint	SCIPmultihashGetNElements (SCIP_MULTIHASH *multihash)

SCIP_EXPORT SCIP_Real	SCIPmultihashGetLoad (SCIP_MULTIHASH *multihash)

SCIP_EXPORT void	SCIPmultihashPrintStatistics (SCIP_MULTIHASH multihash, SCIP_MESSAGEHDLR messagehdlr)

SCIP_EXPORT	SCIP_DECL_HASHKEYEQ (SCIPhashKeyEqString)

SCIP_EXPORT	SCIP_DECL_HASHKEYVAL (SCIPhashKeyValString)

SCIP_EXPORT	SCIP_DECL_HASHGETKEY (SCIPhashGetKeyStandard)

SCIP_EXPORT	SCIP_DECL_HASHKEYEQ (SCIPhashKeyEqPtr)

SCIP_EXPORT	SCIP_DECL_HASHKEYVAL (SCIPhashKeyValPtr)

Function Documentation

◆ SCIPcalcMultihashSize()

SCIP_EXPORT int SCIPcalcMultihashSize ( int minsize )

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

Parameters

minsize minimal size of the hash table

Definition at line 1577 of file misc.c.

References SCIPsortedvecFindInt().

Referenced by presolveFindDuplicates(), and SCIPrealHashCode().

◆ SCIPmultihashCreate()

SCIP_EXPORT 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

multihash	pointer to store the created multihash table
blkmem	block memory used to store multihash table entries
tablesize	size of the hash table
userptr	user pointer

Definition at line 1900 of file misc.c.

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

Referenced by presolveFindDuplicates(), and SCIPrealHashCode().

◆ SCIPmultihashFree()

SCIP_EXPORT void SCIPmultihashFree ( SCIP_MULTIHASH ** multihash )

frees the multihash table

Parameters

multihash pointer to the multihash table

Definition at line 1933 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_EXPORT 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

multihash	multihash table
element	element to insert into the table

Definition at line 1964 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_EXPORT 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

multihash	multihash table
element	element to insert into the table

Definition at line 2005 of file misc.c.

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

Referenced by SCIPrealHashCode().

◆ SCIPmultihashRetrieve()

SCIP_EXPORT void* SCIPmultihashRetrieve	(	SCIP_MULTIHASH *	multihash,
		void *	key
	)

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

Parameters

multihash	multihash table
key	key to retrieve

Definition at line 2024 of file misc.c.

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

Referenced by SCIPmultihashSafeInsert(), and SCIPrealHashCode().

◆ SCIPmultihashRetrieveNext()

SCIP_EXPORT 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

multihash	multihash table
multihashlist	input: 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
key	key to retrieve

Definition at line 2053 of file misc.c.

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

Referenced by presolveFindDuplicates(), and SCIPrealHashCode().

◆ SCIPmultihashExists()

SCIP_EXPORT SCIP_Bool SCIPmultihashExists	(	SCIP_MULTIHASH *	multihash,
		void *	element
	)

returns whether the given element exists in the multihash table

Parameters

multihash	multihash table
element	element to search in the table

Definition at line 2089 of file misc.c.

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

Referenced by SCIPrealHashCode().

◆ SCIPmultihashRemove()

SCIP_EXPORT SCIP_RETCODE SCIPmultihashRemove	(	SCIP_MULTIHASH *	multihash,
		void *	element
	)

removes element from the multihash table, if it exists

Parameters

multihash	multihash table
element	element to remove from the table

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

SCIP_EXPORT 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

multihash multihash table

Definition at line 2150 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_EXPORT SCIP_Longint SCIPmultihashGetNElements ( SCIP_MULTIHASH * multihash )

returns number of multihash table elements

Parameters

multihash multihash table

Definition at line 2171 of file misc.c.

References SCIP_MultiHash::nelements, and NULL.

Referenced by SCIPrealHashCode().

◆ SCIPmultihashGetLoad()

SCIP_EXPORT SCIP_Real SCIPmultihashGetLoad ( SCIP_MULTIHASH * multihash )

returns the load of the given multihash table in percentage

Parameters

multihash multihash table

Definition at line 2181 of file misc.c.

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

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

◆ SCIPmultihashPrintStatistics()

SCIP_EXPORT void SCIPmultihashPrintStatistics	(	SCIP_MULTIHASH *	multihash,
		SCIP_MESSAGEHDLR *	messagehdlr
	)

prints statistics about multihash table usage

Parameters

multihash	multihash table
messagehdlr	message handler

Definition at line 2191 of file misc.c.

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

Referenced by SCIPrealHashCode().

◆ SCIP_DECL_HASHKEYEQ() [1/2]

SCIP_EXPORT SCIP_DECL_HASHKEYEQ ( SCIPhashKeyEqString )

standard hash key comparator for string keys

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

Definition at line 2781 of file misc.c.

Referenced by SCIPrealHashCode().

◆ SCIP_DECL_HASHKEYVAL() [1/2]

SCIP_EXPORT SCIP_DECL_HASHKEYVAL ( SCIPhashKeyValString )

standard hashing function for string keys

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

Definition at line 2790 of file misc.c.

Referenced by SCIPrealHashCode().

◆ SCIP_DECL_HASHGETKEY()

SCIP_EXPORT SCIP_DECL_HASHGETKEY ( SCIPhashGetKeyStandard )

gets the element as the key

Definition at line 2809 of file misc.c.

Referenced by SCIPrealHashCode().

◆ SCIP_DECL_HASHKEYEQ() [2/2]

SCIP_EXPORT SCIP_DECL_HASHKEYEQ ( SCIPhashKeyEqPtr )

returns TRUE iff both keys(pointer) are equal

Definition at line 2816 of file misc.c.

◆ SCIP_DECL_HASHKEYVAL() [2/2]

SCIP_EXPORT SCIP_DECL_HASHKEYVAL ( SCIPhashKeyValPtr )

returns the hash value of the key

Definition at line 2822 of file misc.c.

SCIP

Detailed Description

Functions

Function Documentation

◆ SCIPcalcMultihashSize()

◆ SCIPmultihashCreate()

◆ SCIPmultihashFree()

◆ SCIPmultihashInsert()

◆ SCIPmultihashSafeInsert()

◆ SCIPmultihashRetrieve()

◆ SCIPmultihashRetrieveNext()

◆ SCIPmultihashExists()

◆ SCIPmultihashRemove()

◆ SCIPmultihashRemoveAll()

◆ SCIPmultihashGetNElements()

◆ SCIPmultihashGetLoad()

◆ SCIPmultihashPrintStatistics()

◆ SCIP_DECL_HASHKEYEQ() [1/2]

◆ SCIP_DECL_HASHKEYVAL() [1/2]

◆ SCIP_DECL_HASHGETKEY()

◆ SCIP_DECL_HASHKEYEQ() [2/2]

◆ SCIP_DECL_HASHKEYVAL() [2/2]