summaryrefslogtreecommitdiffstats
path: root/src/aig/mem
diff options
context:
space:
mode:
Diffstat (limited to 'src/aig/mem')
-rw-r--r--src/aig/mem/mem.c604
-rw-r--r--src/aig/mem/mem.h72
-rw-r--r--src/aig/mem/module.make1
3 files changed, 677 insertions, 0 deletions
diff --git a/src/aig/mem/mem.c b/src/aig/mem/mem.c
new file mode 100644
index 00000000..f5bfbfd8
--- /dev/null
+++ b/src/aig/mem/mem.c
@@ -0,0 +1,604 @@
+/**CFile****************************************************************
+
+ FileName [esopMem.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [Cover manipulation package.]
+
+ Synopsis [Memory managers.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - June 20, 2005.]
+
+ Revision [$Id: esopMem.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+#include "mem.h"
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+struct Mem_Fixed_t_
+{
+ // information about individual entries
+ int nEntrySize; // the size of one entry
+ int nEntriesAlloc; // the total number of entries allocated
+ int nEntriesUsed; // the number of entries in use
+ int nEntriesMax; // the max number of entries in use
+ char * pEntriesFree; // the linked list of free entries
+
+ // this is where the memory is stored
+ int nChunkSize; // the size of one chunk
+ int nChunksAlloc; // the maximum number of memory chunks
+ int nChunks; // the current number of memory chunks
+ char ** pChunks; // the allocated memory
+
+ // statistics
+ int nMemoryUsed; // memory used in the allocated entries
+ int nMemoryAlloc; // memory allocated
+};
+
+struct Mem_Flex_t_
+{
+ // information about individual entries
+ int nEntriesUsed; // the number of entries allocated
+ char * pCurrent; // the current pointer to free memory
+ char * pEnd; // the first entry outside the free memory
+
+ // this is where the memory is stored
+ int nChunkSize; // the size of one chunk
+ int nChunksAlloc; // the maximum number of memory chunks
+ int nChunks; // the current number of memory chunks
+ char ** pChunks; // the allocated memory
+
+ // statistics
+ int nMemoryUsed; // memory used in the allocated entries
+ int nMemoryAlloc; // memory allocated
+};
+
+struct Mem_Step_t_
+{
+ int nMems; // the number of fixed memory managers employed
+ Mem_Fixed_t ** pMems; // memory managers: 2^1 words, 2^2 words, etc
+ int nMapSize; // the size of the memory array
+ Mem_Fixed_t ** pMap; // maps the number of bytes into its memory manager
+};
+
+#define ALLOC(type, num) ((type *) malloc(sizeof(type) * (num)))
+#define FREE(obj) ((obj) ? (free((char *) (obj)), (obj) = 0) : 0)
+#define REALLOC(type, obj, num) \
+ ((obj) ? ((type *) realloc((char *)(obj), sizeof(type) * (num))) : \
+ ((type *) malloc(sizeof(type) * (num))))
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Allocates memory pieces of fixed size.]
+
+ Description [The size of the chunk is computed as the minimum of
+ 1024 entries and 64K. Can only work with entry size at least 4 byte long.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Mem_Fixed_t * Mem_FixedStart( int nEntrySize )
+{
+ Mem_Fixed_t * p;
+
+ p = ALLOC( Mem_Fixed_t, 1 );
+ memset( p, 0, sizeof(Mem_Fixed_t) );
+
+ p->nEntrySize = nEntrySize;
+ p->nEntriesAlloc = 0;
+ p->nEntriesUsed = 0;
+ p->pEntriesFree = NULL;
+
+ if ( nEntrySize * (1 << 10) < (1<<16) )
+ p->nChunkSize = (1 << 10);
+ else
+ p->nChunkSize = (1<<16) / nEntrySize;
+ if ( p->nChunkSize < 8 )
+ p->nChunkSize = 8;
+
+ p->nChunksAlloc = 64;
+ p->nChunks = 0;
+ p->pChunks = ALLOC( char *, p->nChunksAlloc );
+
+ p->nMemoryUsed = 0;
+ p->nMemoryAlloc = 0;
+ return p;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Mem_FixedStop( Mem_Fixed_t * p, int fVerbose )
+{
+ int i;
+ if ( p == NULL )
+ return;
+ if ( fVerbose )
+ {
+ printf( "Fixed memory manager: Entry = %5d. Chunk = %5d. Chunks used = %5d.\n",
+ p->nEntrySize, p->nChunkSize, p->nChunks );
+ printf( " Entries used = %8d. Entries peak = %8d. Memory used = %8d. Memory alloc = %8d.\n",
+ p->nEntriesUsed, p->nEntriesMax, p->nEntrySize * p->nEntriesUsed, p->nMemoryAlloc );
+ }
+ for ( i = 0; i < p->nChunks; i++ )
+ free( p->pChunks[i] );
+ free( p->pChunks );
+ free( p );
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+char * Mem_FixedEntryFetch( Mem_Fixed_t * p )
+{
+ char * pTemp;
+ int i;
+
+ // check if there are still free entries
+ if ( p->nEntriesUsed == p->nEntriesAlloc )
+ { // need to allocate more entries
+ assert( p->pEntriesFree == NULL );
+ if ( p->nChunks == p->nChunksAlloc )
+ {
+ p->nChunksAlloc *= 2;
+ p->pChunks = REALLOC( char *, p->pChunks, p->nChunksAlloc );
+ }
+ p->pEntriesFree = ALLOC( char, p->nEntrySize * p->nChunkSize );
+ p->nMemoryAlloc += p->nEntrySize * p->nChunkSize;
+ // transform these entries into a linked list
+ pTemp = p->pEntriesFree;
+ for ( i = 1; i < p->nChunkSize; i++ )
+ {
+ *((char **)pTemp) = pTemp + p->nEntrySize;
+ pTemp += p->nEntrySize;
+ }
+ // set the last link
+ *((char **)pTemp) = NULL;
+ // add the chunk to the chunk storage
+ p->pChunks[ p->nChunks++ ] = p->pEntriesFree;
+ // add to the number of entries allocated
+ p->nEntriesAlloc += p->nChunkSize;
+ }
+ // incrememt the counter of used entries
+ p->nEntriesUsed++;
+ if ( p->nEntriesMax < p->nEntriesUsed )
+ p->nEntriesMax = p->nEntriesUsed;
+ // return the first entry in the free entry list
+ pTemp = p->pEntriesFree;
+ p->pEntriesFree = *((char **)pTemp);
+ return pTemp;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Mem_FixedEntryRecycle( Mem_Fixed_t * p, char * pEntry )
+{
+ // decrement the counter of used entries
+ p->nEntriesUsed--;
+ // add the entry to the linked list of free entries
+ *((char **)pEntry) = p->pEntriesFree;
+ p->pEntriesFree = pEntry;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description [Relocates all the memory except the first chunk.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Mem_FixedRestart( Mem_Fixed_t * p )
+{
+ int i;
+ char * pTemp;
+
+ // deallocate all chunks except the first one
+ for ( i = 1; i < p->nChunks; i++ )
+ free( p->pChunks[i] );
+ p->nChunks = 1;
+ // transform these entries into a linked list
+ pTemp = p->pChunks[0];
+ for ( i = 1; i < p->nChunkSize; i++ )
+ {
+ *((char **)pTemp) = pTemp + p->nEntrySize;
+ pTemp += p->nEntrySize;
+ }
+ // set the last link
+ *((char **)pTemp) = NULL;
+ // set the free entry list
+ p->pEntriesFree = p->pChunks[0];
+ // set the correct statistics
+ p->nMemoryAlloc = p->nEntrySize * p->nChunkSize;
+ p->nMemoryUsed = 0;
+ p->nEntriesAlloc = p->nChunkSize;
+ p->nEntriesUsed = 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Mem_FixedReadMemUsage( Mem_Fixed_t * p )
+{
+ return p->nMemoryAlloc;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Mem_FixedReadMaxEntriesUsed( Mem_Fixed_t * p )
+{
+ return p->nEntriesMax;
+}
+
+
+
+/**Function*************************************************************
+
+ Synopsis [Allocates entries of flexible size.]
+
+ Description [Can only work with entry size at least 4 byte long.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Mem_Flex_t * Mem_FlexStart()
+{
+ Mem_Flex_t * p;
+
+ p = ALLOC( Mem_Flex_t, 1 );
+ memset( p, 0, sizeof(Mem_Flex_t) );
+
+ p->nEntriesUsed = 0;
+ p->pCurrent = NULL;
+ p->pEnd = NULL;
+
+ p->nChunkSize = (1 << 14);
+ p->nChunksAlloc = 64;
+ p->nChunks = 0;
+ p->pChunks = ALLOC( char *, p->nChunksAlloc );
+
+ p->nMemoryUsed = 0;
+ p->nMemoryAlloc = 0;
+ return p;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Mem_FlexStop( Mem_Flex_t * p, int fVerbose )
+{
+ int i;
+ if ( p == NULL )
+ return;
+ if ( fVerbose )
+ {
+ printf( "Flexible memory manager: Chunk size = %d. Chunks used = %d.\n",
+ p->nChunkSize, p->nChunks );
+ printf( " Entries used = %d. Memory used = %d. Memory alloc = %d.\n",
+ p->nEntriesUsed, p->nMemoryUsed, p->nMemoryAlloc );
+ }
+ for ( i = 0; i < p->nChunks; i++ )
+ free( p->pChunks[i] );
+ free( p->pChunks );
+ free( p );
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+char * Mem_FlexEntryFetch( Mem_Flex_t * p, int nBytes )
+{
+ char * pTemp;
+ // check if there are still free entries
+ if ( p->pCurrent == NULL || p->pCurrent + nBytes > p->pEnd )
+ { // need to allocate more entries
+ if ( p->nChunks == p->nChunksAlloc )
+ {
+ p->nChunksAlloc *= 2;
+ p->pChunks = REALLOC( char *, p->pChunks, p->nChunksAlloc );
+ }
+ if ( nBytes > p->nChunkSize )
+ {
+ // resize the chunk size if more memory is requested than it can give
+ // (ideally, this should never happen)
+ p->nChunkSize = 2 * nBytes;
+ }
+ p->pCurrent = ALLOC( char, p->nChunkSize );
+ p->pEnd = p->pCurrent + p->nChunkSize;
+ p->nMemoryAlloc += p->nChunkSize;
+ // add the chunk to the chunk storage
+ p->pChunks[ p->nChunks++ ] = p->pCurrent;
+ }
+ assert( p->pCurrent + nBytes <= p->pEnd );
+ // increment the counter of used entries
+ p->nEntriesUsed++;
+ // keep track of the memory used
+ p->nMemoryUsed += nBytes;
+ // return the next entry
+ pTemp = p->pCurrent;
+ p->pCurrent += nBytes;
+ return pTemp;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description [Relocates all the memory except the first chunk.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Mem_FlexRestart( Mem_Flex_t * p )
+{
+ int i;
+ if ( p->nChunks == 0 )
+ return;
+ // deallocate all chunks except the first one
+ for ( i = 1; i < p->nChunks; i++ )
+ free( p->pChunks[i] );
+ p->nChunks = 1;
+ p->nMemoryAlloc = p->nChunkSize;
+ // transform these entries into a linked list
+ p->pCurrent = p->pChunks[0];
+ p->pEnd = p->pCurrent + p->nChunkSize;
+ p->nEntriesUsed = 0;
+ p->nMemoryUsed = 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Mem_FlexReadMemUsage( Mem_Flex_t * p )
+{
+ return p->nMemoryUsed;
+}
+
+
+
+
+
+/**Function*************************************************************
+
+ Synopsis [Starts the hierarchical memory manager.]
+
+ Description [This manager can allocate entries of any size.
+ Iternally they are mapped into the entries with the number of bytes
+ equal to the power of 2. The smallest entry size is 8 bytes. The
+ next one is 16 bytes etc. So, if the user requests 6 bytes, he gets
+ 8 byte entry. If we asks for 25 bytes, he gets 32 byte entry etc.
+ The input parameters "nSteps" says how many fixed memory managers
+ are employed internally. Calling this procedure with nSteps equal
+ to 10 results in 10 hierarchically arranged internal memory managers,
+ which can allocate up to 4096 (1Kb) entries. Requests for larger
+ entries are handed over to malloc() and then free()ed.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Mem_Step_t * Mem_StepStart( int nSteps )
+{
+ Mem_Step_t * p;
+ int i, k;
+ p = ALLOC( Mem_Step_t, 1 );
+ memset( p, 0, sizeof(Mem_Step_t) );
+ p->nMems = nSteps;
+ // start the fixed memory managers
+ p->pMems = ALLOC( Mem_Fixed_t *, p->nMems );
+ for ( i = 0; i < p->nMems; i++ )
+ p->pMems[i] = Mem_FixedStart( (8<<i) );
+ // set up the mapping of the required memory size into the corresponding manager
+ p->nMapSize = (4<<p->nMems);
+ p->pMap = ALLOC( Mem_Fixed_t *, p->nMapSize+1 );
+ p->pMap[0] = NULL;
+ for ( k = 1; k <= 4; k++ )
+ p->pMap[k] = p->pMems[0];
+ for ( i = 0; i < p->nMems; i++ )
+ for ( k = (4<<i)+1; k <= (8<<i); k++ )
+ p->pMap[k] = p->pMems[i];
+//for ( i = 1; i < 100; i ++ )
+//printf( "%10d: size = %10d\n", i, p->pMap[i]->nEntrySize );
+ return p;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Stops the memory manager.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Mem_StepStop( Mem_Step_t * p, int fVerbose )
+{
+ int i;
+ for ( i = 0; i < p->nMems; i++ )
+ Mem_FixedStop( p->pMems[i], fVerbose );
+// if ( p->pLargeChunks )
+// {
+// for ( i = 0; i < p->nLargeChunks; i++ )
+// free( p->pLargeChunks[i] );
+// free( p->pLargeChunks );
+// }
+ free( p->pMems );
+ free( p->pMap );
+ free( p );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Creates the entry.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+char * Mem_StepEntryFetch( Mem_Step_t * p, int nBytes )
+{
+ if ( nBytes == 0 )
+ return NULL;
+ if ( nBytes > p->nMapSize )
+ {
+// printf( "Allocating %d bytes.\n", nBytes );
+/*
+ if ( p->nLargeChunks == p->nLargeChunksAlloc )
+ {
+ if ( p->nLargeChunksAlloc == 0 )
+ p->nLargeChunksAlloc = 5;
+ p->nLargeChunksAlloc *= 2;
+ p->pLargeChunks = REALLOC( char *, p->pLargeChunks, p->nLargeChunksAlloc );
+ }
+ p->pLargeChunks[ p->nLargeChunks++ ] = ALLOC( char, nBytes );
+ return p->pLargeChunks[ p->nLargeChunks - 1 ];
+*/
+ return ALLOC( char, nBytes );
+ }
+ return Mem_FixedEntryFetch( p->pMap[nBytes] );
+}
+
+
+/**Function*************************************************************
+
+ Synopsis [Recycles the entry.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Mem_StepEntryRecycle( Mem_Step_t * p, char * pEntry, int nBytes )
+{
+ if ( nBytes == 0 )
+ return;
+ if ( nBytes > p->nMapSize )
+ {
+ free( pEntry );
+ return;
+ }
+ Mem_FixedEntryRecycle( p->pMap[nBytes], pEntry );
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Mem_StepReadMemUsage( Mem_Step_t * p )
+{
+ int i, nMemTotal = 0;
+ for ( i = 0; i < p->nMems; i++ )
+ nMemTotal += p->pMems[i]->nMemoryAlloc;
+ return nMemTotal;
+}
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
diff --git a/src/aig/mem/mem.h b/src/aig/mem/mem.h
new file mode 100644
index 00000000..d43e5fc3
--- /dev/null
+++ b/src/aig/mem/mem.h
@@ -0,0 +1,72 @@
+/**CFile****************************************************************
+
+ FileName [mem.h]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [Memory management.]
+
+ Synopsis [External declarations.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - June 20, 2005.]
+
+ Revision [$Id: mem.h,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#ifndef __MEM_H__
+#define __MEM_H__
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+typedef struct Mem_Fixed_t_ Mem_Fixed_t;
+typedef struct Mem_Flex_t_ Mem_Flex_t;
+typedef struct Mem_Step_t_ Mem_Step_t;
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/*=== mem.c ===========================================================*/
+// fixed-size-block memory manager
+extern Mem_Fixed_t * Mem_FixedStart( int nEntrySize );
+extern void Mem_FixedStop( Mem_Fixed_t * p, int fVerbose );
+extern char * Mem_FixedEntryFetch( Mem_Fixed_t * p );
+extern void Mem_FixedEntryRecycle( Mem_Fixed_t * p, char * pEntry );
+extern void Mem_FixedRestart( Mem_Fixed_t * p );
+extern int Mem_FixedReadMemUsage( Mem_Fixed_t * p );
+extern int Mem_FixedReadMaxEntriesUsed( Mem_Fixed_t * p );
+// flexible-size-block memory manager
+extern Mem_Flex_t * Mem_FlexStart();
+extern void Mem_FlexStop( Mem_Flex_t * p, int fVerbose );
+extern char * Mem_FlexEntryFetch( Mem_Flex_t * p, int nBytes );
+extern void Mem_FlexRestart( Mem_Flex_t * p );
+extern int Mem_FlexReadMemUsage( Mem_Flex_t * p );
+// hierarchical memory manager
+extern Mem_Step_t * Mem_StepStart( int nSteps );
+extern void Mem_StepStop( Mem_Step_t * p, int fVerbose );
+extern char * Mem_StepEntryFetch( Mem_Step_t * p, int nBytes );
+extern void Mem_StepEntryRecycle( Mem_Step_t * p, char * pEntry, int nBytes );
+extern int Mem_StepReadMemUsage( Mem_Step_t * p );
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
diff --git a/src/aig/mem/module.make b/src/aig/mem/module.make
new file mode 100644
index 00000000..ae6fcbe4
--- /dev/null
+++ b/src/aig/mem/module.make
@@ -0,0 +1 @@
+SRC += src/aig/mem/mem.c