cudd/cuddLCache.c File Reference

Functions for local caches. More...

#include "util.h"
#include "cuddInt.h"
Include dependency graph for cuddLCache.c:

Defines

#define DD_MAX_HASHTABLE_DENSITY   2
#define ddLCHash1(f, shift)   (((unsigned)(f) * DD_P1) >> (shift))
 Computes hash function for keys of one operand.
#define ddLCHash2(f, g, shift)   ((((unsigned)(f) * DD_P1 + (unsigned)(g)) * DD_P2) >> (shift))
 Computes hash function for keys of two operands.
#define ddLCHash3(f, g, h, shift)   ddCHash2(f,g,h,shift)
 Computes hash function for keys of three operands.

Functions

DdLocalCachecuddLocalCacheInit (DdManager *manager, unsigned int keySize, unsigned int cacheSize, unsigned int maxCacheSize)
 Initializes a local computed table.
void cuddLocalCacheQuit (DdLocalCache *cache)
 Shuts down a local computed table.
void cuddLocalCacheInsert (DdLocalCache *cache, DdNodePtr *key, DdNode *value)
 Inserts a result in a local cache.
DdNodecuddLocalCacheLookup (DdLocalCache *cache, DdNodePtr *key)
 Looks up in a local cache.
void cuddLocalCacheClearDead (DdManager *manager)
 Clears the dead entries of the local caches of a manager.
void cuddLocalCacheClearAll (DdManager *manager)
 Clears the local caches of a manager.
DdHashTablecuddHashTableInit (DdManager *manager, unsigned int keySize, unsigned int initSize)
 Initializes a hash table.
void cuddHashTableQuit (DdHashTable *hash)
 Shuts down a hash table.
void cuddHashTableGenericQuit (DdHashTable *hash)
 Shuts down a hash table.
int cuddHashTableInsert (DdHashTable *hash, DdNodePtr *key, DdNode *value, ptrint count)
 Inserts an item in a hash table.
DdNodecuddHashTableLookup (DdHashTable *hash, DdNodePtr *key)
 Looks up a key in a hash table.
int cuddHashTableInsert1 (DdHashTable *hash, DdNode *f, DdNode *value, ptrint count)
 Inserts an item in a hash table.
DdNodecuddHashTableLookup1 (DdHashTable *hash, DdNode *f)
 Looks up a key consisting of one pointer in a hash table.
int cuddHashTableGenericInsert (DdHashTable *hash, DdNode *f, void *value)
 Inserts a generic item in a hash table.
void * cuddHashTableGenericLookup (DdHashTable *hash, DdNode *f)
 Looks up a key consisting of one pointer in a hash table.
int cuddHashTableInsert2 (DdHashTable *hash, DdNode *f, DdNode *g, DdNode *value, ptrint count)
 Inserts an item in a hash table.
DdNodecuddHashTableLookup2 (DdHashTable *hash, DdNode *f, DdNode *g)
 Looks up a key consisting of two pointers in a hash table.
int cuddHashTableInsert3 (DdHashTable *hash, DdNode *f, DdNode *g, DdNode *h, DdNode *value, ptrint count)
 Inserts an item in a hash table.
DdNodecuddHashTableLookup3 (DdHashTable *hash, DdNode *f, DdNode *g, DdNode *h)
 Looks up a key consisting of three pointers in a hash table.
static void cuddLocalCacheResize (DdLocalCache *cache)
 Resizes a local cache.
static unsigned int ddLCHash (DdNodePtr *key, unsigned int keysize, int shift)
 Computes the hash value for a local cache.
static void cuddLocalCacheAddToList (DdLocalCache *cache)
 Inserts a local cache in the manager list.
static void cuddLocalCacheRemoveFromList (DdLocalCache *cache)
 Removes a local cache from the manager list.
static int cuddHashTableResize (DdHashTable *hash)
 Resizes a hash table.
static DdHashItemcuddHashTableAlloc (DdHashTable *hash)
 Fast storage allocation for items in a hash table.

Detailed Description

Functions for local caches.

Author:
Fabio Somenzi

Copyright (c) 1995-2015, Regents of the University of Colorado

All rights reserved.

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.


Define Documentation

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

Computes hash function for keys of one operand.

Side effects
None
See also:
ddLCHash3 ddLCHash
#define ddLCHash2 ( f,
g,
shift   )     ((((unsigned)(f) * DD_P1 + (unsigned)(g)) * DD_P2) >> (shift))

Computes hash function for keys of two operands.

Side effects
None
See also:
ddLCHash3 ddLCHash
#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

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
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
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
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
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
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
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
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
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
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
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
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
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
void cuddHashTableQuit ( DdHashTable hash  ) 

Shuts down a hash table.

Dereferences all the values.

Side effects
None
See also:
cuddHashTableInit
static int cuddHashTableResize ( DdHashTable hash  )  [static]

Resizes a hash table.

Returns:
1 if successful; 0 otherwise.
Side effects
None
See also:
cuddHashTableInsert
static void cuddLocalCacheAddToList ( DdLocalCache cache  )  [static]

Inserts a local cache in the manager list.

Side effects
None
void cuddLocalCacheClearAll ( DdManager manager  ) 

Clears the local caches of a manager.

Used before reordering.

Side effects
None
void cuddLocalCacheClearDead ( DdManager manager  ) 

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

Used during garbage collection.

Side effects
None
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
void cuddLocalCacheInsert ( DdLocalCache cache,
DdNodePtr key,
DdNode value 
)

Inserts a result in a local cache.

Side effects
None
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
void cuddLocalCacheQuit ( DdLocalCache cache  ) 

Shuts down a local computed table.

Side effects
None
See also:
cuddLocalCacheInit
Parameters:
cache cache to be shut down
static void cuddLocalCacheRemoveFromList ( DdLocalCache cache  )  [static]

Removes a local cache from the manager list.

Side effects
None
static void cuddLocalCacheResize ( DdLocalCache cache  )  [static]

Resizes a local cache.

Side effects
None
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
 All Data Structures Files Functions Variables Typedefs Enumerations Defines

Generated on 31 Dec 2015 for cudd by  doxygen 1.6.1