Functions for local caches. More...

#include "util.h"
#include "cuddInt.h"

Include dependency graph for cuddLCache.c:

Macros
#define	DD_MAX_HASHTABLE_DENSITY 2 /* tells when to resize a table */

#define	ddLCHash1(f, shift) (((unsigned)(ptruint)(f) * DD_P1) >> (shift))
	Computes hash function for keys of one operand. More...

#define	ddLCHash2(f, g, shift)
	Computes hash function for keys of two operands. More...

#define	ddLCHash3(f, g, h, shift) ddCHash2(f,g,h,shift)
	Computes hash function for keys of three operands. More...

Functions
DdLocalCache *	cuddLocalCacheInit (DdManager *manager, unsigned int keySize, unsigned int cacheSize, unsigned int maxCacheSize)
	Initializes a local computed table. More...

void	cuddLocalCacheQuit (DdLocalCache *cache)
	Shuts down a local computed table. More...

void	cuddLocalCacheInsert (DdLocalCache cache, DdNodePtr key, DdNode *value)
	Inserts a result in a local cache. More...

DdNode *	cuddLocalCacheLookup (DdLocalCache cache, DdNodePtr key)
	Looks up in a local cache. More...

void	cuddLocalCacheClearDead (DdManager *manager)
	Clears the dead entries of the local caches of a manager. More...

void	cuddLocalCacheClearAll (DdManager *manager)
	Clears the local caches of a manager. More...

DdHashTable *	cuddHashTableInit (DdManager *manager, unsigned int keySize, unsigned int initSize)
	Initializes a hash table. More...

void	cuddHashTableQuit (DdHashTable *hash)
	Shuts down a hash table. More...

void	cuddHashTableGenericQuit (DdHashTable *hash)
	Shuts down a hash table. More...

int	cuddHashTableInsert (DdHashTable hash, DdNodePtr key, DdNode *value, ptrint count)
	Inserts an item in a hash table. More...

DdNode *	cuddHashTableLookup (DdHashTable hash, DdNodePtr key)
	Looks up a key in a hash table. More...

int	cuddHashTableInsert1 (DdHashTable hash, DdNode f, DdNode *value, ptrint count)
	Inserts an item in a hash table. More...

DdNode *	cuddHashTableLookup1 (DdHashTable hash, DdNode f)
	Looks up a key consisting of one pointer in a hash table. More...

int	cuddHashTableGenericInsert (DdHashTable hash, DdNode f, void *value)
	Inserts a generic item in a hash table. More...

void *	cuddHashTableGenericLookup (DdHashTable hash, DdNode f)
	Looks up a key consisting of one pointer in a hash table. More...

int	cuddHashTableInsert2 (DdHashTable hash, DdNode f, DdNode g, DdNode value, ptrint count)
	Inserts an item in a hash table. More...

DdNode *	cuddHashTableLookup2 (DdHashTable hash, DdNode f, DdNode *g)
	Looks up a key consisting of two pointers in a hash table. More...

int	cuddHashTableInsert3 (DdHashTable hash, DdNode f, DdNode g, DdNode h, DdNode *value, ptrint count)
	Inserts an item in a hash table. More...

DdNode *	cuddHashTableLookup3 (DdHashTable hash, DdNode f, DdNode g, DdNode h)
	Looks up a key consisting of three pointers in a hash table. More...

static void	cuddLocalCacheResize (DdLocalCache *cache)
	Resizes a local cache. More...

static unsigned int	ddLCHash (DdNodePtr *key, unsigned int keysize, int shift)
	Computes the hash value for a local cache. More...

static void	cuddLocalCacheAddToList (DdLocalCache *cache)
	Inserts a local cache in the manager list. More...

static void	cuddLocalCacheRemoveFromList (DdLocalCache *cache)
	Removes a local cache from the manager list. More...

static int	cuddHashTableResize (DdHashTable *hash)
	Resizes a hash table. More...

static DdHashItem *	cuddHashTableAlloc (DdHashTable *hash)
	Fast storage allocation for items in a hash table. More...

Detailed Description

Functions for local caches.

Author: Fabio Somenzi

Copyright

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

Neither the name of the University of Colorado nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Macro Definition Documentation

◆ ddLCHash1

#define ddLCHash1	(	f,
		shift
	)	(((unsigned)(ptruint)(f) * DD_P1) >> (shift))

Computes hash function for keys of one operand.

Side effects None

See also: ddLCHash3 ddLCHash

◆ ddLCHash2

#define ddLCHash2	(	f,
		g,
		shift
	)

Value:

((((unsigned)(ptruint)(f) * DD_P1 + \

(unsigned)(ptruint)(g)) * DD_P2) >> (shift))

ptruint

uintptr_t ptruint

Unsigned integer that is the size of a pointer.

Definition: cuddInt.h:231

Computes hash function for keys of two operands.

Side effects None

See also: ddLCHash3 ddLCHash

◆ ddLCHash3

#define ddLCHash3	(	f,
		g,
		h,
		shift
	)	ddCHash2(f,g,h,shift)

Computes hash function for keys of three operands.

Side effects None

See also: ddLCHash2 ddLCHash

Function Documentation

◆ cuddHashTableAlloc()

static DdHashItem* cuddHashTableAlloc ( DdHashTable * hash )

static

Fast storage allocation for items in a hash table.

The first sizeof(void *) bytes of a chunk contain a pointer to the next block; the rest contains DD_MEM_CHUNK spaces for hash items.

Returns: a pointer to a new item if successful; NULL is memory is full.

Side effects None

See also: cuddAllocNode cuddDynamicAllocNode

◆ cuddHashTableGenericInsert()

int cuddHashTableGenericInsert	(	DdHashTable *	hash,
		DdNode *	f,
		void *	value
	)

Inserts a generic item in a hash table.

Inserts an item in a hash table when the key is one pointer and the value is not a DdNode pointer. The main difference w.r.t. cuddHashTableInsert1 is that the reference count of the value is not incremented.

Returns: 1 if successful; 0 otherwise.

Side effects None

See also: cuddHashTableInsert1 cuddHashTableGenericLookup

◆ cuddHashTableGenericLookup()

void* cuddHashTableGenericLookup	(	DdHashTable *	hash,
		DdNode *	f
	)

Looks up a key consisting of one pointer in a hash table.

Looks up a key consisting of one pointer in a hash table when the value is not a DdNode pointer.

Returns: the value associated to the key if there is an entry for the given key in the table; NULL otherwise.

Side effects None

See also: cuddHashTableLookup1 cuddHashTableGenericInsert

◆ cuddHashTableGenericQuit()

void cuddHashTableGenericQuit ( DdHashTable * hash )

Shuts down a hash table.

Shuts down a hash table, when the values are not DdNode pointers.

Side effects None

See also: cuddHashTableInit

◆ cuddHashTableInit()

DdHashTable* cuddHashTableInit	(	DdManager *	manager,
		unsigned int	keySize,
		unsigned int	initSize
	)

Initializes a hash table.

The table associates tuples of DdNode pointers to one DdNode pointer. This type of table is used for functions that cannot (or prefer not to) use the main computed table. The package also provides functions that allow the caller to store arbitrary pointers in the table.

Returns: a pointer to the new table if successful; NULL otherwise.

Side effects None

See also: cuddHashTableQuit cuddHashTableGenericQuit

Parameters

manager	DD manager
keySize	number of pointers in the key
initSize	initial size of the table

◆ cuddHashTableInsert()

int cuddHashTableInsert	(	DdHashTable *	hash,
		DdNodePtr *	key,
		DdNode *	value,
		ptrint	count
	)

Inserts an item in a hash table.

Inserts an item in a hash table when the key has more than three pointers.

Returns: 1 if successful; 0 otherwise.

Side effects None

See also: [cuddHashTableInsert1 cuddHashTableInsert2 cuddHashTableInsert3 cuddHashTableLookup

◆ cuddHashTableInsert1()

int cuddHashTableInsert1	(	DdHashTable *	hash,
		DdNode *	f,
		DdNode *	value,
		ptrint	count
	)

Inserts an item in a hash table.

Inserts an item in a hash table when the key is one pointer.

Returns: 1 if successful; 0 otherwise.

Side effects None

See also: cuddHashTableInsert cuddHashTableInsert2 cuddHashTableInsert3 cuddHashTableLookup1

◆ cuddHashTableInsert2()

int cuddHashTableInsert2	(	DdHashTable *	hash,
		DdNode *	f,
		DdNode *	g,
		DdNode *	value,
		ptrint	count
	)

Inserts an item in a hash table.

Inserts an item in a hash table when the key is composed of two pointers.

Returns: 1 if successful; 0 otherwise.

Side effects None

See also: cuddHashTableInsert cuddHashTableInsert1 cuddHashTableInsert3 cuddHashTableLookup2

◆ cuddHashTableInsert3()

int cuddHashTableInsert3	(	DdHashTable *	hash,
		DdNode *	f,
		DdNode *	g,
		DdNode *	h,
		DdNode *	value,
		ptrint	count
	)

Inserts an item in a hash table.

Inserts an item in a hash table when the key is composed of three pointers.

Returns: 1 if successful; 0 otherwise.

Side effects None

See also: cuddHashTableInsert cuddHashTableInsert1 cuddHashTableInsert2 cuddHashTableLookup3

◆ cuddHashTableLookup()

DdNode* cuddHashTableLookup	(	DdHashTable *	hash,
		DdNodePtr *	key
	)

Looks up a key in a hash table.

Looks up a key consisting of more than three pointers in a hash table. If the entry is present, its reference counter is decremented if not saturated. If the counter reaches 0, the value of the entry is dereferenced, and the entry is returned to the free list.

Returns: the value associated to the key if there is an entry for the given key in the table; NULL otherwise.

Side effects None

See also: cuddHashTableLookup1 cuddHashTableLookup2 cuddHashTableLookup3 cuddHashTableInsert

◆ cuddHashTableLookup1()

DdNode* cuddHashTableLookup1	(	DdHashTable *	hash,
		DdNode *	f
	)

Looks up a key consisting of one pointer in a hash table.

If the entry is present, its reference count is decremented if not saturated. If the counter reaches 0, the value of the entry is dereferenced, and the entry is returned to the free list.

Returns: the value associated to the key if there is an entry for the given key in the table; NULL otherwise.

Side effects None

See also: cuddHashTableLookup cuddHashTableLookup2 cuddHashTableLookup3 cuddHashTableInsert1

◆ cuddHashTableLookup2()

DdNode* cuddHashTableLookup2	(	DdHashTable *	hash,
		DdNode *	f,
		DdNode *	g
	)

Looks up a key consisting of two pointers in a hash table.

If the entry is present, its reference counter is decremented if not saturated. If the counter reaches 0, the value of the entry is dereferenced, and the entry is returned to the free list.

Returns: the value associated to the key if there is an entry for the given key in the table; NULL otherwise.

Side effects None

See also: cuddHashTableLookup cuddHashTableLookup1 cuddHashTableLookup3 cuddHashTableInsert2

◆ cuddHashTableLookup3()

DdNode* cuddHashTableLookup3	(	DdHashTable *	hash,
		DdNode *	f,
		DdNode *	g,
		DdNode *	h
	)

Looks up a key consisting of three pointers in a hash table.

If the entry is present, its reference counter is decremented if not saturated. If the counter reaches 0, the value of the entry is dereferenced, and the entry is returned to the free list.

Returns: the value associated to the key if there is an entry for the given key in the table; NULL otherwise.

Side effects None

See also: cuddHashTableLookup cuddHashTableLookup1 cuddHashTableLookup2 cuddHashTableInsert3

◆ cuddHashTableQuit()

void cuddHashTableQuit ( DdHashTable * hash )

Shuts down a hash table.

Dereferences all the values.

Side effects None

See also: cuddHashTableInit

◆ cuddHashTableResize()

static int cuddHashTableResize ( DdHashTable * hash )

static

Resizes a hash table.

Returns: 1 if successful; 0 otherwise.

Side effects None

See also: cuddHashTableInsert

◆ cuddLocalCacheAddToList()

static void cuddLocalCacheAddToList ( DdLocalCache * cache )

static

Inserts a local cache in the manager list.

Side effects None

◆ cuddLocalCacheClearAll()

void cuddLocalCacheClearAll ( DdManager * manager )

Clears the local caches of a manager.

Used before reordering.

Side effects None

◆ cuddLocalCacheClearDead()

void cuddLocalCacheClearDead ( DdManager * manager )

Clears the dead entries of the local caches of a manager.

Used during garbage collection.

Side effects None

◆ cuddLocalCacheInit()

DdLocalCache* cuddLocalCacheInit	(	DdManager *	manager,
		unsigned int	keySize,
		unsigned int	cacheSize,
		unsigned int	maxCacheSize
	)

Initializes a local computed table.

Returns: a pointer the the new local cache in case of success; NULL otherwise.

Side effects None

See also: cuddInitCache

Parameters

manager	manager
keySize	size of the key (number of operands)
cacheSize	Initial size of the cache
maxCacheSize	Size of the cache beyond which no resizing occurs

◆ cuddLocalCacheInsert()

void cuddLocalCacheInsert	(	DdLocalCache *	cache,
		DdNodePtr *	key,
		DdNode *	value
	)

Inserts a result in a local cache.

Side effects None

◆ cuddLocalCacheLookup()

DdNode* cuddLocalCacheLookup	(	DdLocalCache *	cache,
		DdNodePtr *	key
	)

Looks up in a local cache.

Returns: the result if found; it returns NULL if no result is found.

Side effects None

◆ cuddLocalCacheQuit()

void cuddLocalCacheQuit ( DdLocalCache * cache )

Shuts down a local computed table.

Side effects None

See also: cuddLocalCacheInit

Parameters

cache cache to be shut down

◆ cuddLocalCacheRemoveFromList()

static void cuddLocalCacheRemoveFromList ( DdLocalCache * cache )

static

Removes a local cache from the manager list.

Side effects None

◆ cuddLocalCacheResize()

static void cuddLocalCacheResize ( DdLocalCache * cache )

static

Resizes a local cache.

Side effects None

◆ ddLCHash()

static unsigned int ddLCHash	(	DdNodePtr *	key,
		unsigned int	keysize,
		int	shift
	)

static

Computes the hash value for a local cache.

Returns: the bucket index.

Side effects None

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ ddLCHash1

◆ ddLCHash2

◆ ddLCHash3

Function Documentation

◆ cuddHashTableAlloc()

◆ cuddHashTableGenericInsert()

◆ cuddHashTableGenericLookup()

◆ cuddHashTableGenericQuit()

◆ cuddHashTableInit()

◆ cuddHashTableInsert()

◆ cuddHashTableInsert1()

◆ cuddHashTableInsert2()

◆ cuddHashTableInsert3()

◆ cuddHashTableLookup()

◆ cuddHashTableLookup1()

◆ cuddHashTableLookup2()

◆ cuddHashTableLookup3()

◆ cuddHashTableQuit()

◆ cuddHashTableResize()

◆ cuddLocalCacheAddToList()

◆ cuddLocalCacheClearAll()

◆ cuddLocalCacheClearDead()

◆ cuddLocalCacheInit()

◆ cuddLocalCacheInsert()

◆ cuddLocalCacheLookup()

◆ cuddLocalCacheQuit()

◆ cuddLocalCacheRemoveFromList()

◆ cuddLocalCacheResize()

◆ ddLCHash()