#include "niml_private.h"
/******************************************************************************/
/*********** Hash table functions (string/pointer pair) [26 Aug 2002] *********/
/******************************************************************************/
#undef UINT
#define UINT unsigned int
#undef INLINE
#ifdef __GNUC__
# define INLINE inline
#else
# define INLINE /*nada*/
#endif
static int vtkill=0 ;
void Htable_set_vtkill( int vt ){ vtkill = vt ; }
/*---------------------------------------------------------*/
/*! Compute a non-negative integer key from a string.
-----------------------------------------------------------*/
static INLINE UINT hashkey( char *str )
{
char *p ;
unsigned int h=32003 ;
for( p=str ; *p != '\0' ; p++ )
h = ( h << 5 ) - h + *p ;
#if 0
h = ((h & 0xf0f0f0f0) >> 4) /* swap nibbles */
| ((h & 0x0f0f0f0f) << 4) ; /* just for fun */
#endif
return h;
}
/*-------------------------------------------------------*/
/*! Create a new Htable, with len slots.
---------------------------------------------------------*/
Htable * new_Htable( int len )
{
Htable *ht ;
if( len <= 7 ) len = 7 ; /* smallest allowed */
else if( len%2 == 0 ) len++ ; /* mustn't be even */
ht = (Htable *) calloc( 1 , sizeof(Htable) ) ;
ht->len = len ;
ht->vtab = (void ***) calloc( len , sizeof(void **) ) ;
ht->ctab = (char ***) calloc( len , sizeof(char **) ) ;
ht->ntab = (int *) calloc( len , sizeof(int) ) ;
return ht ;
}
/*---------------------------------------------------------*/
/*! Delete a Htable forever.
-----------------------------------------------------------*/
void destroy_Htable( Htable *ht )
{
int jj , kk ;
if( ht == NULL ) return ;
for( jj=0 ; jj < ht->len ; jj++ ){
if( ht->vtab[jj] != NULL ){
if( vtkill ){
for( kk=0 ; kk < ht->ntab[jj] ; kk++ )
if( ht->vtab[jj][kk] != NULL ) free(ht->vtab[jj][kk]) ;
}
free(ht->vtab[jj]) ;
}
if( ht->ctab[jj] != NULL ){
for( kk=0 ; kk < ht->ntab[jj] ; kk++ )
if( ht->ctab[jj][kk] != NULL ) free(ht->ctab[jj][kk]) ;
free(ht->ctab[jj]) ;
}
}
free(ht->vtab) ; free(ht->ctab) ; free(ht->ntab) ; free(ht) ;
return ;
}
/*-------------------------------------------------------*/
/* Find a string in the hash table;
- Returns the pointer it was deposited with, or NULL.
- Also returns NULL if inputs are illegal.
---------------------------------------------------------*/
void * findin_Htable( char *str , Htable *ht )
{
UINT jj ;
int kk , ntab ;
char *key , **ctab ;
void ***vtab ;
if( str == NULL || ht == NULL || ht->ntot == 0 ) return NULL ;
jj = hashkey(str) % ht->len ; /* hash table row */
vtab = ht->vtab ;
if( vtab[jj] == NULL ) return NULL ; /* nothing there */
key = str ;
ctab = ht->ctab[jj] ; ntab = ht->ntab[jj] ;
for( kk=0 ; kk < ntab ; kk++ ) /* scan for match of key to ctab */
if( ctab[kk] != NULL && strcmp(key,ctab[kk]) == 0 )
return vtab[jj][kk];
return NULL ; /* no match found */
}
/*--------------------------------------------------------*/
/*! Add a string/pointer pair to a hash table.
- If the ptr is NULL, this will remove the string/ptr
pair from the table.
- If you insert with the same string twice, then the
second time will overwrite the 1st time.
----------------------------------------------------------*/
void addto_Htable( char *str , void *vpt , Htable *ht )
{
UINT jj ;
int kk , ll=-1 ;
char *key ;
/* check for bad inputs */
if( str == NULL || ht == NULL ) return ;
if( vpt == NULL ){ removefrom_Htable( str , ht ) ; return ; }
jj = hashkey(str) % ht->len ; /* hash table row */
key = strdup(str) ; /* internal key string */
if( ht->vtab[jj] == NULL ){ /* create this row in table */
ht->vtab[jj] = (void **) calloc(3,sizeof(void *)) ;
ht->ctab[jj] = (char **) calloc(3,sizeof(char *)) ;
ht->ntab[jj] = 3 ; /* made 2 extra entries */
ht->vtab[jj][0] = vpt ; /* save pointer */
ht->ctab[jj][0] = key ; /* save key string */
ht->ntot ++ ; /* 1 more in table */
} else { /* search this row */
for( kk=0 ; kk < ht->ntab[jj] ; kk++ ){
if( ht->ctab[jj][kk] == NULL ){ if(ll < 0) ll=kk; } /* add here? */
else if( strcmp(key,ht->ctab[jj][kk]) == 0 ) break ; /* found it? */
}
if( kk == ht->ntab[jj] ){ /* didn't find str in row already */
if( ll >= 0 ){ /* have a NULL slot from scan above */
ht->vtab[jj][ll] = vpt ; /* save ptr */
ht->ctab[jj][ll] = key ; /* save key string */
ht->ntot ++ ; /* 1 more in table */
} else { /* must make row longer */
ht->vtab[jj] = (void **) realloc( ht->vtab[jj] , (kk+3)*sizeof(void *)) ;
ht->ctab[jj] = (char **) realloc( ht->ctab[jj] , (kk+3)*sizeof(char *)) ;
ht->ntab[jj] = kk+3 ;
ht->vtab[jj][kk] = vpt ; /* save ptr */
ht->ctab[jj][kk] = key ; /* save key string */
ht->ntot ++ ; /* 1 more in table */
ht->vtab[jj][kk+1] = ht->vtab[jj][kk+2] = NULL ; /* created 2 extra */
ht->ctab[jj][kk+1] = ht->ctab[jj][kk+2] = NULL ; /* elements above */
}
} else { /* found str in row at index kk */
if( vtkill && ht->vtab[jj][kk] != NULL ) free(ht->vtab[jj][kk]) ;
ht->vtab[jj][kk] = vpt ; /* replace old ptr with new */
free(key) ; /* don't need this */
}
}
}
/*--------------------------------------------------------*/
/*! Remove an entry from a Htable.
----------------------------------------------------------*/
void removefrom_Htable( char *str , Htable *ht )
{
UINT jj ;
int kk ;
char *key ;
void ***vtab ;
char **ctab ;
int ntab ;
if( str == NULL || ht == NULL || ht->ntot == 0 ) return ;
jj = hashkey(str) % ht->len ; /* hash table row */
vtab = ht->vtab ;
if( vtab[jj] == NULL ) return ; /* nothing there */
key = str ;
ctab = ht->ctab[jj] ; ntab = ht->ntab[jj] ;
for( kk=0 ; kk < ntab ; kk++ ) /* scan for match of key to ctab */
if( ctab[kk] != NULL && strcmp(key,ctab[kk]) == 0 ){
free(ctab[kk]); ctab[kk] = NULL;
if( vtkill && vtab[jj][kk] != NULL ) free(vtab[jj][kk]) ;
vtab[jj][kk] = NULL; ht->ntot--; break;
}
return ;
}
/*-----------------------------------------------------------------*/
/*! Profile a Htable to stdout.
-------------------------------------------------------------------*/
void profile_Htable( char *str, Htable *ht )
{
int jj, kk , nn ;
printf("\n----- Htable profile: %s\n",(str != NULL) ? str : "" ) ;
if( ht == NULL ){
printf("++ EMPTY ++\n") ; return ;
}
printf("Rows=%d Ntot=%d\n",ht->len,ht->ntot) ;
for( jj=0 ; jj < ht->len ; jj++ ){
printf(" #%05d: ",jj) ;
if( ht->vtab[jj] == NULL ){
printf("++ EMPTY ++\n") ;
} else {
for( nn=kk=0 ; kk < ht->ntab[jj] ; kk++ ){
if( ht->ctab[jj][kk] != NULL ){ printf("*") ; nn++ ; }
else { printf(".") ; }
}
printf(" [ntab=%d nn=%d]\n",ht->ntab[jj],nn) ;
}
}
fflush(stdout) ;
}
/*-----------------------------------------------------------------*/
/*! Put contents of htold into htnew.
-------------------------------------------------------------------*/
void subsume_Htable( Htable *htold , Htable *htnew )
{
int kk,jj ;
/* check inputs for sanity */
if( htold == NULL || htold->ntot == 0 || htnew == NULL ) return ;
for( jj=0 ; jj < htold->len ; jj++ ){
if( htold->vtab[jj] != NULL ){
for( kk=0 ; kk < htold->ntab[jj] ; kk++ )
if( htold->ctab[jj][kk] != NULL )
addto_Htable( htold->ctab[jj][kk] , htold->vtab[jj][kk] , htnew ) ;
}
}
}
/*-----------------------------------------------------------------*/
/*! Resize the guts of a Htable [28 Feb 2005]
-------------------------------------------------------------------*/
void resize_Htable( int newlen , Htable *ht )
{
Htable *htnew ;
int jj , kk ;
if( ht == NULL ) return ;
/* auto-resize? */
if( newlen == 0 ){
if( ht->ntot <= 131 * ht->len ) return ;
newlen = ht->ntot / 37 ;
}
/* create new Htable, copy contents of this one into it */
htnew = new_Htable( newlen ) ;
if( htnew == NULL ) return ;
subsume_Htable( ht , htnew ) ;
/* erase contents of this one now */
for( jj=0 ; jj < ht->len ; jj++ ){
if( ht->vtab[jj] != NULL ) free(ht->vtab[jj]) ;
if( ht->ctab[jj] != NULL ){
for( kk=0 ; kk < ht->ntab[jj] ; kk++ )
if( ht->ctab[jj][kk] != NULL ) free(ht->ctab[jj][kk]) ;
free(ht->ctab[jj]) ;
}
}
free(ht->vtab) ; free(ht->ctab) ; free(ht->ntab) ;
/* copy guts of new Htable over the guts of this one */
*ht = *htnew ;
/* free the shell of the new Htable and exit */
free((void *)htnew) ; return ;
}
syntax highlighted by Code2HTML, v. 0.9.1