00001 #include "niml_private.h"
00002 
00003 /******************************************************************************/
00004 /*********** Hash table functions (string/pointer pair) [26 Aug 2002] *********/
00005 /******************************************************************************/
00006 
00007 #undef  UINT
00008 #define UINT unsigned int
00009 
00010 #undef INLINE
00011 #ifdef __GNUC__
00012 # define INLINE inline
00013 #else
00014 # define INLINE /*nada*/
00015 #endif
00016 
00017 static int vtkill=0 ;
00018 void Htable_set_vtkill( int vt ){ vtkill = vt ; }
00019 
00020 /*---------------------------------------------------------*/
00021 /*! Compute a non-negative integer key from a string.
00022 -----------------------------------------------------------*/
00023 
00024 static INLINE UINT hashkey( char *str )
00025 {
00026   char *p ;
00027   unsigned int h=32003 ;
00028 
00029   for( p=str ; *p != '\0' ; p++ )
00030     h = ( h << 5 ) - h + *p ;
00031 
00032 #if 0
00033   h =   ((h & 0xf0f0f0f0) >> 4)   /* swap nibbles */
00034       | ((h & 0x0f0f0f0f) << 4) ; /* just for fun */
00035 #endif
00036 
00037   return h;
00038 }
00039 
00040 /*-------------------------------------------------------*/
00041 /*! Create a new Htable, with len slots.
00042 ---------------------------------------------------------*/
00043 
00044 Htable * new_Htable( int len )
00045 {
00046    Htable *ht ;
00047 
00048         if( len   <= 7 ) len = 7 ;  /* smallest allowed */
00049    else if( len%2 == 0 ) len++   ;  /* mustn't be even */
00050 
00051    ht = (Htable *) calloc( 1 , sizeof(Htable) ) ;
00052 
00053    ht->len  = len ;
00054    ht->vtab = (void ***) calloc( len , sizeof(void **) ) ;
00055    ht->ctab = (char ***) calloc( len , sizeof(char **) ) ;
00056    ht->ntab = (int *)    calloc( len , sizeof(int)     ) ;
00057 
00058    return ht ;
00059 }
00060 
00061 /*---------------------------------------------------------*/
00062 /*! Delete a Htable forever.
00063 -----------------------------------------------------------*/
00064 
00065 void destroy_Htable( Htable *ht )
00066 {
00067    int jj , kk ;
00068 
00069    if( ht == NULL ) return ;
00070 
00071    for( jj=0 ; jj < ht->len ; jj++ ){
00072      if( ht->vtab[jj] != NULL ){
00073        if( vtkill ){
00074          for( kk=0 ; kk < ht->ntab[jj] ; kk++ )
00075            if( ht->vtab[jj][kk] != NULL ) free(ht->vtab[jj][kk]) ;
00076        }
00077        free(ht->vtab[jj]) ;
00078      }
00079      if( ht->ctab[jj] != NULL ){
00080        for( kk=0 ; kk < ht->ntab[jj] ; kk++ )
00081          if( ht->ctab[jj][kk] != NULL ) free(ht->ctab[jj][kk]) ;
00082        free(ht->ctab[jj]) ;
00083      }
00084    }
00085    free(ht->vtab) ; free(ht->ctab) ; free(ht->ntab) ; free(ht) ;
00086    return ;
00087 }
00088 
00089 /*-------------------------------------------------------*/
00090 /* Find a string in the hash table;
00091    - Returns the pointer it was deposited with, or NULL.
00092    - Also returns NULL if inputs are illegal.
00093 ---------------------------------------------------------*/
00094 
00095 void * findin_Htable( char *str , Htable *ht )
00096 {
00097    UINT jj ;
00098    int kk , ntab ;
00099    char *key , **ctab ;
00100    void ***vtab ;
00101 
00102    if( str == NULL || ht == NULL || ht->ntot == 0 ) return NULL ;
00103 
00104    jj = hashkey(str) % ht->len ;      /* hash table row */
00105 
00106    vtab = ht->vtab ;
00107 
00108    if( vtab[jj] == NULL ) return NULL ;  /* nothing there */
00109 
00110    key = str ;
00111 
00112    ctab = ht->ctab[jj] ; ntab = ht->ntab[jj] ;
00113 
00114    for( kk=0 ; kk < ntab ; kk++ )   /* scan for match of key to ctab */
00115      if( ctab[kk] != NULL && strcmp(key,ctab[kk]) == 0 )
00116        return vtab[jj][kk];
00117 
00118    return NULL ; /* no match found */
00119 }
00120 
00121 /*--------------------------------------------------------*/
00122 /*! Add a string/pointer pair to a hash table.
00123     - If the ptr is NULL, this will remove the string/ptr
00124       pair from the table.
00125     - If you insert with the same string twice, then the
00126       second time will overwrite the 1st time.
00127 ----------------------------------------------------------*/
00128 
00129 void addto_Htable( char *str , void *vpt , Htable *ht )
00130 {
00131    UINT jj ;
00132    int kk , ll=-1 ;
00133    char *key ;
00134 
00135    /* check for bad inputs */
00136 
00137    if( str == NULL || ht == NULL ) return ;
00138 
00139    if( vpt == NULL ){ removefrom_Htable( str , ht ) ; return ; }
00140 
00141    jj = hashkey(str) % ht->len ;      /* hash table row */
00142 
00143    key = strdup(str) ;                /* internal key string */
00144 
00145    if( ht->vtab[jj] == NULL ){        /* create this row in table */
00146 
00147      ht->vtab[jj] = (void **) calloc(3,sizeof(void *)) ;
00148      ht->ctab[jj] = (char **) calloc(3,sizeof(char *)) ;
00149      ht->ntab[jj] = 3 ;    /* made 2 extra entries */
00150 
00151      ht->vtab[jj][0] = vpt ;   /* save pointer */
00152      ht->ctab[jj][0] = key ;   /* save key string */
00153      ht->ntot ++ ;             /* 1 more in table */
00154 
00155    } else {                           /* search this row */
00156 
00157      for( kk=0 ; kk < ht->ntab[jj] ; kk++ ){
00158             if( ht->ctab[jj][kk] == NULL         ){ if(ll < 0) ll=kk; } /* add here? */
00159        else if( strcmp(key,ht->ctab[jj][kk]) == 0 ) break ;             /* found it? */
00160      }
00161 
00162      if( kk == ht->ntab[jj] ){   /* didn't find str in row already */
00163 
00164        if( ll >= 0 ){         /* have a NULL slot from scan above */
00165 
00166          ht->vtab[jj][ll] = vpt ;  /* save ptr */
00167          ht->ctab[jj][ll] = key ;  /* save key string */
00168          ht->ntot ++ ;             /* 1 more in table */
00169 
00170        } else {               /* must make row longer */
00171 
00172          ht->vtab[jj] = (void **) realloc( ht->vtab[jj] , (kk+3)*sizeof(void *)) ;
00173          ht->ctab[jj] = (char **) realloc( ht->ctab[jj] , (kk+3)*sizeof(char *)) ;
00174          ht->ntab[jj] = kk+3 ;
00175 
00176          ht->vtab[jj][kk] = vpt ;  /* save ptr */
00177          ht->ctab[jj][kk] = key ;  /* save key string */
00178          ht->ntot ++ ;             /* 1 more in table */
00179 
00180          ht->vtab[jj][kk+1] = ht->vtab[jj][kk+2] = NULL ;  /* created 2 extra */
00181          ht->ctab[jj][kk+1] = ht->ctab[jj][kk+2] = NULL ;  /* elements above */
00182 
00183        }
00184 
00185      } else {                    /* found str in row at index kk */
00186 
00187        if( vtkill && ht->vtab[jj][kk] != NULL ) free(ht->vtab[jj][kk]) ;
00188 
00189        ht->vtab[jj][kk] = vpt ;  /* replace old ptr with new */
00190        free(key) ;               /* don't need this */
00191      }
00192    }
00193 }
00194 
00195 /*--------------------------------------------------------*/
00196 /*! Remove an entry from a Htable.
00197 ----------------------------------------------------------*/
00198 
00199 void removefrom_Htable( char *str , Htable *ht )
00200 {
00201    UINT jj ;
00202    int kk ;
00203    char *key ;
00204    void ***vtab ;
00205    char **ctab ;
00206    int  ntab ;
00207 
00208    if( str == NULL || ht == NULL || ht->ntot == 0 ) return ;
00209 
00210    jj = hashkey(str) % ht->len ;      /* hash table row */
00211 
00212    vtab = ht->vtab ;
00213 
00214    if( vtab[jj] == NULL ) return ;    /* nothing there */
00215 
00216    key = str ;
00217 
00218    ctab = ht->ctab[jj] ; ntab = ht->ntab[jj] ;
00219 
00220    for( kk=0 ; kk < ntab ; kk++ )   /* scan for match of key to ctab */
00221      if( ctab[kk] != NULL && strcmp(key,ctab[kk]) == 0 ){
00222        free(ctab[kk]); ctab[kk] = NULL;
00223        if( vtkill && vtab[jj][kk] != NULL ) free(vtab[jj][kk]) ;
00224        vtab[jj][kk] = NULL; ht->ntot--; break;
00225      }
00226 
00227    return ;
00228 }
00229 
00230 /*-----------------------------------------------------------------*/
00231 /*! Profile a Htable to stdout.
00232 -------------------------------------------------------------------*/
00233 
00234 void profile_Htable( char *str, Htable *ht )
00235 {
00236    int jj, kk , nn ;
00237 
00238    printf("\n----- Htable profile: %s\n",(str != NULL) ? str : "" ) ;
00239    if( ht == NULL ){
00240      printf("++ EMPTY ++\n") ; return ;
00241    }
00242 
00243    printf("Rows=%d  Ntot=%d\n",ht->len,ht->ntot) ;
00244 
00245    for( jj=0 ; jj < ht->len ; jj++ ){
00246      printf(" #%05d: ",jj) ;
00247      if( ht->vtab[jj] == NULL ){
00248        printf("++ EMPTY ++\n") ;
00249      } else {
00250        for( nn=kk=0 ; kk < ht->ntab[jj] ; kk++ ){
00251          if( ht->ctab[jj][kk] != NULL ){ printf("*") ; nn++ ; }
00252          else                          { printf(".") ;        }
00253        }
00254        printf(" [ntab=%d nn=%d]\n",ht->ntab[jj],nn) ;
00255      }
00256    }
00257    fflush(stdout) ;
00258 }
00259 
00260 /*-----------------------------------------------------------------*/
00261 /*! Put contents of htold into htnew.
00262 -------------------------------------------------------------------*/
00263 
00264 void subsume_Htable( Htable *htold , Htable *htnew )
00265 {
00266    int kk,jj ;
00267 
00268    /* check inputs for sanity */
00269 
00270    if( htold == NULL || htold->ntot == 0 || htnew == NULL ) return ;
00271 
00272    for( jj=0 ; jj < htold->len ; jj++ ){
00273      if( htold->vtab[jj] != NULL ){
00274        for( kk=0 ; kk < htold->ntab[jj] ; kk++ )
00275          if( htold->ctab[jj][kk] != NULL )
00276            addto_Htable( htold->ctab[jj][kk] , htold->vtab[jj][kk] , htnew ) ;
00277      }
00278    }
00279 }
00280 
00281 /*-----------------------------------------------------------------*/
00282 /*! Resize the guts of a Htable [28 Feb 2005]
00283 -------------------------------------------------------------------*/
00284 
00285 void resize_Htable( int newlen , Htable *ht )
00286 {
00287    Htable *htnew ;
00288    int jj , kk ;
00289 
00290    if( ht == NULL ) return ;
00291 
00292    /* auto-resize? */
00293 
00294    if( newlen == 0 ){
00295      if( ht->ntot <= 131 * ht->len ) return ;
00296      newlen = ht->ntot / 37 ;
00297    }
00298 
00299    /* create new Htable, copy contents of this one into it */
00300 
00301    htnew = new_Htable( newlen ) ;
00302    if( htnew == NULL ) return ;
00303 
00304    subsume_Htable( ht , htnew ) ;
00305 
00306    /* erase contents of this one now */
00307 
00308    for( jj=0 ; jj < ht->len ; jj++ ){
00309      if( ht->vtab[jj] != NULL ) free(ht->vtab[jj]) ;
00310 
00311      if( ht->ctab[jj] != NULL ){
00312        for( kk=0 ; kk < ht->ntab[jj] ; kk++ )
00313          if( ht->ctab[jj][kk] != NULL ) free(ht->ctab[jj][kk]) ;
00314        free(ht->ctab[jj]) ;
00315      }
00316    }
00317    free(ht->vtab) ; free(ht->ctab) ; free(ht->ntab) ;
00318 
00319    /* copy guts of new Htable over the guts of this one */
00320 
00321    *ht = *htnew ;
00322 
00323    /* free the shell of the new Htable and exit */
00324 
00325    free((void *)htnew) ; return ;
00326 }