# Copyright (C) 2012 Aldo Cortesi
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program. If not, see <http://www.gnu.org/licenses/>.
import copy, re
import urwid
import common
from .. import utils, filt
def _mkhelp():
text = []
keys = [
("A", "insert row before cursor"),
("a", "add row after cursor"),
("d", "delete row"),
("e", "spawn external editor on current field"),
("q", "return to flow view"),
("esc", "return to flow view/exit field edit mode"),
("tab", "nex/**CFile****************************************************************
FileName [utilNam.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [Manager for character strings.]
Synopsis [Manager for character strings.]
Author [Alan Mishchenko]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - June 20, 2005.]
Revision [$Id: utilNam.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
***********************************************************************/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include "abc_global.h"
#include "misc/vec/vec.h"
#include "utilNam.h"
ABC_NAMESPACE_IMPL_START
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
// this package maps non-empty character strings into natural numbers and back
// name manager
struct Abc_Nam_t_
{
// info storage for names
int nStore; // the size of allocated storage
int iHandle; // the current free handle
char * pStore; // storage for name objects
// internal number mappings
Vec_Int_t vInt2Handle; // mapping integers into handles
Vec_Int_t vInt2Next; // mapping integers into nexts
// hash table for names
int * pBins; // the hash table bins
int nBins; // the number of bins
// manager recycling
int nRefs; // reference counter for the manager
// internal buffer
Vec_Str_t vBuffer;
};
static inline char * Abc_NamHandleToStr( Abc_Nam_t * p, int h ) { return (char *)(p->pStore + h); }
static inline int Abc_NamIntToHandle( Abc_Nam_t * p, int i ) { return Vec_IntEntry(&p->vInt2Handle, i); }
static inline char * Abc_NamIntToStr( Abc_Nam_t * p, int i ) { return Abc_NamHandleToStr(p, Abc_NamIntToHandle(p,i)); }
static inline int Abc_NamIntToNext( Abc_Nam_t * p, int i ) { return Vec_IntEntry(&p->vInt2Next, i); }
static inline int * Abc_NamIntToNextP( Abc_Nam_t * p, int i ) { return Vec_IntEntryP(&p->vInt2Next, i); }
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis [Creates manager.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Abc_Nam_t * Abc_NamStart( int nObjs, int nAveSize )
{
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
Vec_IntGrow( &p->vInt2Handle, nObjs ); Vec_IntPush( &p->vInt2Handle, -1 );
Vec_IntGrow( &p->vInt2Next, 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;
}
/**Function*************************************************************
Synopsis [Deletes manager.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_NamStop( Abc_Nam_t * p )
{
//Abc_Print( 1, "Starting nam with %d bins.\n", p->nBins );
Vec_StrErase( &p->vBuffer );
Vec_IntErase( &p->vInt2Handle );
Vec_IntErase( &p->vInt2Next );
ABC_FREE( p->pStore );
ABC_FREE( p->pBins );
ABC_FREE( p );
}
/**Function*************************************************************
Synopsis [Prints manager.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_NamPrint( Abc_Nam_t * p )
{
int h, i;
Vec_IntForEachEntryStart( &p->vInt2Handle, h, i, 1 )
Abc_Print( 1, "%d=\n%s\n", i, Abc_NamHandleToStr(p, h) );
}
/**Function*************************************************************
Synopsis [References the manager.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Abc_Nam_t * Abc_NamRef( Abc_Nam_t * p )
{
p->nRefs++;
return p;
}
/**Function*************************************************************
Synopsis [Dereferences the manager.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_NamDeref( Abc_Nam_t * p )
{
if ( p == NULL )
return;
if ( --p->nRefs == 0 )
Abc_NamStop( p );
}
/**Function*************************************************************
Synopsis [Returns the number of used entries.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NamObjNumMax( Abc_Nam_t * p )
{
return Vec_IntSize(&p->vInt2Handle);
}
/**Function*************************************************************
Synopsis [Reports memory usage of the manager.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NamMemUsed( Abc_Nam_t * p )
{
if ( p == NULL )
return 0;
return sizeof(Abc_Nam_t) + p->iHandle + sizeof(int) * p->nBins +
sizeof(int) * (p->vInt2Handle.nSize + p->vInt2Next.nSize);
}
/**Function*************************************************************
Synopsis [Reports memory usage of the manager.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NamMemAlloc( Abc_Nam_t * p )
{
if ( p == NULL )
return 0;
return sizeof(Abc_Nam_t) + p->nStore + sizeof(int) * p->nBins +
sizeof(int) * (p->vInt2Handle.nCap + p->vInt2Next.nCap);
}
/**Function*************************************************************
Synopsis [Computes hash value of the C-string.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NamStrHash( const char * pStr, const char * pLim, int nTableSize )
{
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;
}
/**Function*************************************************************
Synopsis [Returns place where this string is, or should be.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
static inline int Abc_NamStrcmp( char * pStr, char * pLim, char * pThis )
{
if ( pLim )
{
while ( pStr < pLim )
if ( *pStr++ != *pThis++ )
return 1;
return *pThis != '\0';
}
else
{
while ( *pStr )
if ( *pStr++ != *pThis++ )
return 1;
return *pThis != '\0';
}
}
static inline int * Abc_NamStrHashFind( Abc_Nam_t * p, const char * pStr, const char * pLim )
{
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;
}
/**Function*************************************************************
Synopsis [Resizes the hash table.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_NamStrHashResize( Abc_Nam_t * p )
{
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;
Vec_IntZero( &p->vInt2Handle );
Vec_IntGrow( &p->vInt2Handle, 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_IntErase( &vInt2HandleOld );
ABC_FREE( pBinsOld );
// Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
}
/**Function*************************************************************
Synopsis [Returns the index of the string in the table.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NamStrFind( Abc_Nam_t * p, char * pStr )
{
return *Abc_NamStrHashFind( p, pStr, NULL );
}
int Abc_NamStrFindLim( Abc_Nam_t * p, char * pStr, char * pLim )
{
return *Abc_NamStrHashFind( p, pStr, pLim );
}
/**Function*************************************************************
Synopsis [Finds or adds the given name to storage.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NamStrFindOrAdd( Abc_Nam_t * p, char * pStr, int * pfFound )
{
int i, iHandleNew;
int *piPlace;
if ( !(pStr[0