utilNam.c File Reference

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include "abc_global.h"
#include "misc/vec/vec.h"
#include "utilNam.h"

Go to the source code of this file.

Data Structures
struct	Abc_Nam_t_
	DECLARATIONS ///. More...

Functions
static char *	Abc_NamHandleToStr (Abc_Nam_t *p, int h)
static int	Abc_NamIntToHandle (Abc_Nam_t *p, int i)
static char *	Abc_NamIntToStr (Abc_Nam_t *p, int i)
static int	Abc_NamIntToNext (Abc_Nam_t *p, int i)
static int *	Abc_NamIntToNextP (Abc_Nam_t *p, int i)
Abc_Nam_t *	Abc_NamStart (int nObjs, int nAveSize)
	FUNCTION DEFINITIONS ///. More...
void	Abc_NamStop (Abc_Nam_t *p)
void	Abc_NamPrint (Abc_Nam_t *p)
Abc_Nam_t *	Abc_NamRef (Abc_Nam_t *p)
void	Abc_NamDeref (Abc_Nam_t *p)
int	Abc_NamObjNumMax (Abc_Nam_t *p)
int	Abc_NamMemUsed (Abc_Nam_t *p)
int	Abc_NamMemAlloc (Abc_Nam_t *p)
int	Abc_NamStrHash (const char *pStr, const char *pLim, int nTableSize)
static int	Abc_NamStrcmp (char *pStr, char *pLim, char *pThis)
static int *	Abc_NamStrHashFind (Abc_Nam_t *p, const char *pStr, const char *pLim)
void	Abc_NamStrHashResize (Abc_Nam_t *p)
int	Abc_NamStrFind (Abc_Nam_t *p, char *pStr)
int	Abc_NamStrFindLim (Abc_Nam_t *p, char *pStr, char *pLim)
int	Abc_NamStrFindOrAdd (Abc_Nam_t *p, char *pStr, int *pfFound)
int	Abc_NamStrFindOrAddLim (Abc_Nam_t *p, char *pStr, char *pLim, int *pfFound)
char *	Abc_NamStr (Abc_Nam_t *p, int NameId)
Vec_Int_t *	Abc_NamComputeIdMap (Abc_Nam_t *p1, Abc_Nam_t *p2)
int	Abc_NamReportCommon (Vec_Int_t *vNameIds1, Abc_Nam_t *p1, Abc_Nam_t *p2)
char *	Abc_NamReportUnique (Vec_Int_t *vNameIds1, Abc_Nam_t *p1, Abc_Nam_t *p2)

Function Documentation

Vec_Int_t* Abc_NamComputeIdMap	(	Abc_Nam_t *	p1,
		Abc_Nam_t *	p2
	)

Function*************************************************************

Synopsis [For each ID of the first manager, gives ID of the second one.]

Description []

SideEffects []

SeeAlso []

Definition at line 495 of file utilNam.c.

{
    Vec_Int_t * vMap;
    char * pThis;
    int * piPlace, iHandle1, i;
    if ( p1 == p2 )
        return Vec_IntStartNatural( Abc_NamObjNumMax(p1) );
    vMap = Vec_IntStart( Abc_NamObjNumMax(p1) );
    Vec_IntForEachEntryStart( p1->vInt2Handle, iHandle1, i, 1 )
    {
        pThis = Abc_NamHandleToStr( p1, iHandle1 );
        piPlace = Abc_NamStrHashFind( p2, pThis, NULL );
        Vec_IntWriteEntry( vMap, i, *piPlace );
//        Abc_Print( 1, "%d->%d  ", i, *piPlace );
    }
    return vMap;
}

void Abc_NamDeref

(

Abc_Nam_t *

p

)

Function*************************************************************

Synopsis [Dereferences the manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 167 of file utilNam.c.

{
    if ( p == NULL )
        return;
    if ( --p->nRefs == 0 )
        Abc_NamStop( p );
}

static char* Abc_NamHandleToStr ( Abc_Nam_t *  p, int  h  )

inlinestatic

Definition at line 57 of file utilNam.c.

{ return (char *)(p->pStore + h);                         }

static int Abc_NamIntToHandle ( Abc_Nam_t *  p, int  i  )

inlinestatic

Definition at line 58 of file utilNam.c.

{ return Vec_IntEntry(p->vInt2Handle, i);                 }

static int Abc_NamIntToNext ( Abc_Nam_t *  p, int  i  )

inlinestatic

Definition at line 60 of file utilNam.c.

{ return Vec_IntEntry(p->vInt2Next, i);                   }

static int* Abc_NamIntToNextP ( Abc_Nam_t *  p, int  i  )

inlinestatic

Definition at line 61 of file utilNam.c.

{ return Vec_IntEntryP(p->vInt2Next, i);                  }

static char* Abc_NamIntToStr ( Abc_Nam_t *  p, int  i  )

inlinestatic

Definition at line 59 of file utilNam.c.

{ return Abc_NamHandleToStr(p, Abc_NamIntToHandle(p,i));  }

int Abc_NamMemAlloc

(

Abc_Nam_t *

p

)

Function*************************************************************

Synopsis [Reports memory usage of the manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 221 of file utilNam.c.

{
    if ( p == NULL )
        return 0;
    return sizeof(Abc_Nam_t) + p->nStore + sizeof(int) * p->nBins + 
        sizeof(int) * (p->vInt2Handle->nCap + p->vInt2Next->nCap);
}

int Abc_NamMemUsed

(

Abc_Nam_t *

p

)

Function*************************************************************

Synopsis [Reports memory usage of the manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 202 of file utilNam.c.

{
    if ( p == NULL )
        return 0;
    return sizeof(Abc_Nam_t) + p->iHandle + sizeof(int) * p->nBins + 
        sizeof(int) * (p->vInt2Handle->nSize + p->vInt2Next->nSize);
}

int Abc_NamObjNumMax

(

Abc_Nam_t *

p

)

Function*************************************************************

Synopsis [Returns the number of used entries.]

Description []

SideEffects []

SeeAlso []

Definition at line 186 of file utilNam.c.

{
    return Vec_IntSize(p->vInt2Handle);
}

void Abc_NamPrint

(

Abc_Nam_t *

p

)

Function*************************************************************

Synopsis [Prints manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 131 of file utilNam.c.

{
    int h, i;
    Vec_IntForEachEntryStart( p->vInt2Handle, h, i, 1 )
        Abc_Print( 1, "%d=\n%s\n", i, Abc_NamHandleToStr(p, h) );
//    Abc_Print( 1, "\n" );
}

Abc_Nam_t* Abc_NamRef

(

Abc_Nam_t *

p

)

Function*************************************************************

Synopsis [References the manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 150 of file utilNam.c.

{
    p->nRefs++;
    return p;
}

int Abc_NamReportCommon	(	Vec_Int_t *	vNameIds1,
		Abc_Nam_t *	p1,
		Abc_Nam_t *	p2
	)

Function*************************************************************

Synopsis [Returns the number of common names in the array.]

Description [The array contains name IDs in the first manager. The procedure returns the number of entries that correspond to names in the first manager that appear in the second manager.]

SideEffects []

SeeAlso []

Definition at line 526 of file utilNam.c.

{
    int i, Entry, Counter = 0;
    Vec_IntForEachEntry( vNameIds1, Entry, i )
    {
        assert( Entry > 0 && Entry < Abc_NamObjNumMax(p1) );
        Counter += (Abc_NamStrFind(p2, Abc_NamStr(p1, Entry)) > 0);
//        if ( Abc_NamStrFind(p2, Abc_NamStr(p1, Entry)) == 0 )
//            Abc_Print( 1, "unique name <%s>\n", Abc_NamStr(p1, Entry) );
    }
    return Counter;
}

char* Abc_NamReportUnique	(	Vec_Int_t *	vNameIds1,
		Abc_Nam_t *	p1,
		Abc_Nam_t *	p2
	)

Function*************************************************************

Synopsis [Returns the name that appears in p1 does not appear in p2.]

Description []

SideEffects []

SeeAlso []

Definition at line 550 of file utilNam.c.

{
    int i, Entry;
    Vec_IntForEachEntry( vNameIds1, Entry, i )
    {
        assert( Entry > 0 && Entry < Abc_NamObjNumMax(p1) );
        if ( Abc_NamStrFind(p2, Abc_NamStr(p1, Entry)) == 0 )
            return Abc_NamStr(p1, Entry);
    }
    return NULL;
}

Abc_Nam_t* Abc_NamStart	(	int	nObjs,
		int	nAveSize
	)

FUNCTION DEFINITIONS ///.

FUNCTION DECLARATIONS ///.

Function*************************************************************

Synopsis [Creates manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 78 of file utilNam.c.

{
    Abc_Nam_t * p;
    if ( nObjs == 0 )
        nObjs = 16;
    p = ABC_CALLOC( Abc_Nam_t, 1 );
    p->nStore      = ((nObjs * (nAveSize + 1) + 16) / 4) * 4;
    p->pStore      = ABC_ALLOC( char, p->nStore );
    p->nBins       = Abc_PrimeCudd( nObjs );
    p->pBins       = ABC_CALLOC( int, p->nBins );
    // 0th object is unused
    p->vInt2Handle = Vec_IntAlloc( nObjs );  Vec_IntPush( p->vInt2Handle, -1 );
    p->vInt2Next   = Vec_IntAlloc( nObjs );  Vec_IntPush( p->vInt2Next,   -1 );
    p->iHandle     = 4;
    memset( p->pStore, 0, 4 );
//Abc_Print( 1, "Starting nam with %d bins.\n", p->nBins );
    // start reference counting
    p->nRefs       = 1;
    return p;
}

void Abc_NamStop

(

Abc_Nam_t *

p

)

Function*************************************************************

Synopsis [Deletes manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 110 of file utilNam.c.

{
//Abc_Print( 1, "Starting nam with %d bins.\n", p->nBins );
    Vec_IntFree( p->vInt2Handle );
    Vec_IntFree( p->vInt2Next );
    ABC_FREE( p->pStore );
    ABC_FREE( p->pBins );
    ABC_FREE( p );
}

char* Abc_NamStr	(	Abc_Nam_t *	p,
		int	NameId
	)

Function*************************************************************

Synopsis [Returns name from name ID.]

Description []

SideEffects []

SeeAlso []

Definition at line 479 of file utilNam.c.

{
    return NameId? Abc_NamIntToStr(p, NameId) : NULL;
}

static int Abc_NamStrcmp ( char *  pStr, char *  pLim, char *  pThis  )

inlinestatic

Function*************************************************************

Synopsis [Returns place where this string is, or should be.]

Description []

SideEffects []

SeeAlso []

Definition at line 288 of file utilNam.c.

{
    if ( pLim )
    {
        while ( pStr < pLim )
            if ( *pStr++ != *pThis++ )
                return 1;
        return *pThis != '\0';
    }
    else
    {
        while ( *pStr )
            if ( *pStr++ != *pThis++ )
                return 1;
        return *pThis != '\0';
    }
}

int Abc_NamStrFind	(	Abc_Nam_t *	p,
		char *	pStr
	)

Function*************************************************************

Synopsis [Returns the index of the string in the table.]

Description []

SideEffects []

SeeAlso []

Definition at line 372 of file utilNam.c.

{
    return *Abc_NamStrHashFind( p, pStr, NULL );
}

int Abc_NamStrFindLim	(	Abc_Nam_t *	p,
		char *	pStr,
		char *	pLim
	)

Definition at line 376 of file utilNam.c.

{
    return *Abc_NamStrHashFind( p, pStr, pLim );
}

int Abc_NamStrFindOrAdd	(	Abc_Nam_t *	p,
		char *	pStr,
		int *	pfFound
	)

Function*************************************************************

Synopsis [Finds or adds the given name to storage.]

Description []

SideEffects []

SeeAlso []

Definition at line 392 of file utilNam.c.

{
    int i, iHandleNew;
    int *piPlace;
    if ( !(pStr[0] != '\\' || pStr[strlen(pStr)-1] == ' ') )
    {
        for ( i = strlen(pStr) - 1; i >= 0; i-- )
            if ( *pStr == ' ' )
                break;
        assert( i < (int)strlen(pStr) );
    }
    piPlace = Abc_NamStrHashFind( p, pStr, NULL );
    if ( *piPlace )
    {
        if ( pfFound )
            *pfFound = 1;
        return *piPlace;
    }
    if ( pfFound )
        *pfFound = 0;
    iHandleNew = p->iHandle + strlen(pStr) + 1;
    while ( p->nStore < iHandleNew )
    {
        p->nStore *= 3;
        p->nStore /= 2;
        p->pStore  = ABC_REALLOC( char, p->pStore, p->nStore );
    }
    assert( p->nStore >= iHandleNew );
    // create new handle
    *piPlace = Vec_IntSize( p->vInt2Handle );
    strcpy( Abc_NamHandleToStr( p, p->iHandle ), pStr );
    Vec_IntPush( p->vInt2Handle, p->iHandle );
    Vec_IntPush( p->vInt2Next, 0 );
    p->iHandle = iHandleNew;
    // extend the hash table
    if ( Vec_IntSize(p->vInt2Handle) > 2 * p->nBins )
        Abc_NamStrHashResize( p );
    return Vec_IntSize(p->vInt2Handle) - 1;
}

int Abc_NamStrFindOrAddLim	(	Abc_Nam_t *	p,
		char *	pStr,
		char *	pLim,
		int *	pfFound
	)

Definition at line 431 of file utilNam.c.

{
    int iHandleNew;
    int *piPlace;
    char * pStore;
    assert( pStr < pLim );
    piPlace = Abc_NamStrHashFind( p, pStr, pLim );
    if ( *piPlace )
    {
        if ( pfFound )
            *pfFound = 1;
        return *piPlace;
    }
    if ( pfFound )
        *pfFound = 0;
    iHandleNew = p->iHandle + (pLim - pStr) + 1;
    while ( p->nStore < iHandleNew )
    {
        p->nStore *= 3;
        p->nStore /= 2;
        p->pStore  = ABC_REALLOC( char, p->pStore, p->nStore );
    }
    assert( p->nStore >= iHandleNew );
    // create new handle
    *piPlace = Vec_IntSize( p->vInt2Handle );
    pStore = Abc_NamHandleToStr( p, p->iHandle );
    strncpy( pStore, pStr, pLim - pStr );
    pStore[pLim - pStr] = 0;
    Vec_IntPush( p->vInt2Handle, p->iHandle );
    Vec_IntPush( p->vInt2Next, 0 );
    p->iHandle = iHandleNew;
    // extend the hash table
    if ( Vec_IntSize(p->vInt2Handle) > 2 * p->nBins )
        Abc_NamStrHashResize( p );
    return Vec_IntSize(p->vInt2Handle) - 1;
}

int Abc_NamStrHash	(	const char *	pStr,
		const char *	pLim,
		int	nTableSize
	)

Function*************************************************************

Synopsis [Computes hash value of the C-string.]

Description []

SideEffects []

SeeAlso []

Definition at line 240 of file utilNam.c.

{
    static int s_FPrimes[128] = { 
        1009, 1049, 1093, 1151, 1201, 1249, 1297, 1361, 1427, 1459, 
        1499, 1559, 1607, 1657, 1709, 1759, 1823, 1877, 1933, 1997, 
        2039, 2089, 2141, 2213, 2269, 2311, 2371, 2411, 2467, 2543, 
        2609, 2663, 2699, 2741, 2797, 2851, 2909, 2969, 3037, 3089, 
        3169, 3221, 3299, 3331, 3389, 3461, 3517, 3557, 3613, 3671, 
        3719, 3779, 3847, 3907, 3943, 4013, 4073, 4129, 4201, 4243, 
        4289, 4363, 4441, 4493, 4549, 4621, 4663, 4729, 4793, 4871, 
        4933, 4973, 5021, 5087, 5153, 5227, 5281, 5351, 5417, 5471, 
        5519, 5573, 5651, 5693, 5749, 5821, 5861, 5923, 6011, 6073, 
        6131, 6199, 6257, 6301, 6353, 6397, 6481, 6563, 6619, 6689, 
        6737, 6803, 6863, 6917, 6977, 7027, 7109, 7187, 7237, 7309, 
        7393, 7477, 7523, 7561, 7607, 7681, 7727, 7817, 7877, 7933, 
        8011, 8039, 8059, 8081, 8093, 8111, 8123, 8147
    };
    unsigned i, uHash;
    if ( pLim )
    {
        for ( uHash = 0, i = 0; pStr+i < pLim; i++ )
            if ( i & 1 ) 
                uHash *= pStr[i] * s_FPrimes[i & 0x7F];
            else
                uHash ^= pStr[i] * s_FPrimes[i & 0x7F];
    }
    else
    {
        for ( uHash = 0, i = 0; pStr[i]; i++ )
            if ( i & 1 ) 
                uHash *= pStr[i] * s_FPrimes[i & 0x7F];
            else
                uHash ^= pStr[i] * s_FPrimes[i & 0x7F];
    }
    return uHash % nTableSize;
}

static int* Abc_NamStrHashFind ( Abc_Nam_t *  p, const char *  pStr, const char *  pLim  )

inlinestatic

Definition at line 305 of file utilNam.c.

{
    char * pThis;
    int * pPlace = (int *)(p->pBins + Abc_NamStrHash( pStr, pLim, p->nBins ));
    assert( *pStr );
    for ( pThis = (*pPlace)? Abc_NamIntToStr(p, *pPlace) : NULL; 
          pThis;    pPlace = Abc_NamIntToNextP(p, *pPlace), 
          pThis = (*pPlace)? Abc_NamIntToStr(p, *pPlace) : NULL )
              if ( !Abc_NamStrcmp( (char *)pStr, (char *)pLim, pThis ) )
                  break;
    return pPlace;
}

void Abc_NamStrHashResize

(

Abc_Nam_t *

p

)

Function*************************************************************

Synopsis [Resizes the hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 329 of file utilNam.c.

{
    Vec_Int_t * vInt2HandleOld;
    char * pThis;
    int * piPlace, * pBinsOld, iHandleOld, i;//, clk = Abc_Clock();
    assert( p->pBins != NULL );
//    Abc_Print( 1, "Resizing names manager hash table from %6d to %6d. ", p->nBins, Abc_PrimeCudd( 3 * p->nBins ) );
    // replace the table
    pBinsOld = p->pBins;
    p->nBins = Abc_PrimeCudd( 3 * p->nBins ); 
    p->pBins = ABC_CALLOC( int, p->nBins );
    // replace the handles array
    vInt2HandleOld = p->vInt2Handle;
    p->vInt2Handle = Vec_IntAlloc( 2 * Vec_IntSize(vInt2HandleOld) ); 
    Vec_IntPush( p->vInt2Handle, -1 );
    Vec_IntClear( p->vInt2Next );    Vec_IntPush( p->vInt2Next, -1 );
    // rehash the entries from the old table
    Vec_IntForEachEntryStart( vInt2HandleOld, iHandleOld, i, 1 )
    {
        pThis   = Abc_NamHandleToStr( p, iHandleOld );
        piPlace = Abc_NamStrHashFind( p, pThis, NULL );
        assert( *piPlace == 0 );
        *piPlace = Vec_IntSize( p->vInt2Handle );
        assert( Vec_IntSize( p->vInt2Handle ) == i );
        Vec_IntPush( p->vInt2Handle, iHandleOld );
        Vec_IntPush( p->vInt2Next,   0 );
    }
    Vec_IntFree( vInt2HandleOld );
    ABC_FREE( pBinsOld );
//    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
}