distrib/sources/mbkspice/spi_hash.c

   1 /*
   2  * This file is part of the Alliance CAD System
   3  * Copyright (C) Laboratoire LIP6 - Département ASIM
   4  * Universite Pierre et Marie Curie
   5  *
   6  * Home page          : http://www-asim.lip6.fr/alliance/
   7  * E-mail support     : mailto:alliance-support@asim.lip6.fr
   8  *
   9  * This library is free software; you  can redistribute it and/or modify it
  10  * under the terms  of the GNU Library General Public  License as published
  11  * by the Free Software Foundation; either version 2 of the License, or (at
  12  * your option) any later version.
  13  *
  14  * Alliance VLSI  CAD System  is distributed  in the hope  that it  will be
  15  * useful, but WITHOUT  ANY WARRANTY; without even the  implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General
  17  * Public License for more details.
  18  *
  19  * You should have received a copy  of the GNU General Public License along
  20  * with the GNU C Library; see the  file COPYING. If not, write to the Free
  21  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  22  */
  23
  24
  25 /*******************************************************************************
  26 *                                                                              *
  27 *  Tool        : Spice parser / driver v 7.00                                  *
  28 *  Author(s)   : Gregoire AVOT                                                 *
  29 *  Updates     : March, 18th 1998                                              *
  30 *                                                                              *
  31 *******************************************************************************/
  32
  33 #include <stdio.h>
  34 #include <string.h>
  35 #include <stdlib.h>
  36 #include <ctype.h>
  37 #include MUT_H
  38 #include "spi_hash.h"
  39
  40 extern char SPI_CASE_SENSITIVE;
  41
  42 /* 2^n elements dans la table de hash */
  43 #define HASH_MINI       4
  44 #define HASH_MAXI       15
  45
  46 /* 2^n Seuil d'augmentation */
  47 #define HASH_DELTA      1
  48
  49 thash*          creatthash( )
  50 {
  51   thash         *new;
  52   int            i;
  53   int            n;
  54
  55   new           = ( thash* )mbkalloc( sizeof( thash ) );
  56   new->entree   = HASH_MINI ;
  57   n             = 1 << new->entree;
  58   new->table    = ( hashelem** )mbkalloc( sizeof( hashelem* ) * n );
  59   new->nbelem   = 0;
  60   new->tete     = NULL;
  61   new->libere   = NULL;
  62
  63   for( i = 0 ; i < n ; i++ )
  64     new->table[i]  = NULL;
  65
  66   return( new );
  67 }
  68
  69 void            freethash( pt )
  70 thash           *pt;
  71 {
  72   chain_list    *scanchain;
  73
  74   mbkfree( pt->table );
  75   /*
  76   if( pt->tete )
  77     mbkfree( pt->tete );
  78   */
  79
  80   for( scanchain = pt->libere ; scanchain ; scanchain = scanchain->NEXT )
  81     mbkfree( scanchain->DATA );
  82   freechain( pt->libere );
  83
  84   mbkfree( pt );
  85 }
  86
  87 hashelem*       nouvhashelem( table )
  88 thash           *table;
  89 {
  90   int           i;
  91   hashelem      *elem;
  92
  93   if( ! table->tete )
  94   {
  95     table->tete   = ( hashelem* ) mbkalloc ( sizeof( hashelem ) * 64 );
  96     table->libere = addchain( table->libere, table->tete );
  97     elem          = table->tete;
  98
  99     for( i = 1 ; i < 64 ; i++ )
 100     {
 101       elem->suivant = elem + 1;
 102       elem++;
 103     }
 104     elem->suivant = NULL;
 105   }
 106
 107   elem              = table->tete;
 108   table->tete       = table->tete->suivant;
 109
 110   return( elem );
 111 }
 112
 113 void            liberehashelem( table, elem )
 114 thash           *table;
 115 hashelem        *elem;
 116 {
 117   elem->suivant = table->tete;
 118   table->tete   = elem;
 119 }
 120
 121 void            addthashelem( nouveau, ptr, table )
 122 char            *nouveau;
 123 void            *ptr;
 124 thash           *table;
 125 {
 126   int           s;
 127   hashelem      *elm;
 128
 129
 130   if( table->nbelem == 1 << ( table->entree + HASH_DELTA ) &&
 131       table->entree < HASH_MAXI                               )
 132     resizetable( table, table->entree + 1 );
 133
 134   s   = thashsignature( nouveau, table->entree );
 135   elm = nouvhashelem( table );
 136
 137   elm->suivant      = table->table[ s ];
 138   table->table[ s ] = elm;
 139
 140   elm->mot          = nouveau;
 141   elm->ptr          = ptr;
 142
 143   table->nbelem++;
 144 }
 145
 146 void*           getthashelem( elem, table, status )
 147 char            *elem;
 148 thash           *table;
 149 int             *status;
 150 {
 151   int            s;
 152   hashelem      *scan;
 153
 154   s = thashsignature( elem, table->entree );
 155
 156   for( scan = table->table[ s ] ; scan ; scan = scan->suivant )
 157   {
 158     if( /*scan->mot == elem ||*/ strcasecmp( scan->mot, elem ) == 0 )
 159     {
 160       if( status != NULL )
 161         *status = 1;
 162       return( scan->ptr );
 163     }
 164   }
 165
 166   if( status != NULL )
 167     *status = 0;
 168
 169   return( NULL );
 170 }
 171
 172 int             thashsignature( c, l )
 173 char            *c;
 174 int             l;
 175 {
 176   int bit;
 177   int b;
 178   int dec;
 179
 180   dec = 0;
 181   bit = 0;
 182
 183   while( *c )
 184   {
 185     for( bit = 0; bit < 8 ; bit ++ )
 186     {
 187       if (CASE_SENSITIVE != 'P') b = ( *c >> bit ) & 0x1;
 188       else b = ( tolower((int)*c) >> bit ) & 0x1;
 189
 190       /* Polynome générateur : X^15 + X + 1 */
 191       dec = ( ( dec & 0x3FFE ) << 1 )                               |
 192             ( ( ( dec & 0x4000 ) >> 13 ) ^ ( ( dec & 0x1 ) << 1 ) ) |
 193             ( ( ( dec & 0x4000 ) >> 14 ) ^ b ) ;
 194     }
 195     c++;
 196   }
 197
 198   return( dec % ( 1 << l ) );
 199 }
 200
 201 void resizetable( table, elem )
 202 thash           *table;
 203 int             elem;
 204 {
 205   hashelem      **new;
 206   hashelem       *nouv;
 207   hashelem       *scan;
 208   hashelem       *suiv;
 209   int             n;
 210   int             i;
 211   int             s;
 212
 213   n = 1 << elem;
 214
 215   new = ( hashelem** )mbkalloc( sizeof( hashelem* ) * n );
 216   for( i = 0 ; i < n ; i++ )
 217     new[ i ] = NULL;
 218
 219   n = 1 << table->entree;
 220
 221   for( i = 0 ; i < n ; i++ )
 222   {
 223     for( scan = table->table[i] ; scan ; scan = scan->suivant )
 224     {
 225       nouv = nouvhashelem( table );
 226       s = thashsignature( scan->mot, elem );
 227
 228       nouv->suivant = new[ s ];
 229       new[s]        = nouv;
 230       nouv->mot     = scan->mot;
 231       nouv->ptr     = scan->ptr;
 232     }
 233
 234     for( scan = table->table[i] ; scan ; scan = suiv )
 235     {
 236       suiv = scan->suivant;
 237       liberehashelem( table, scan );
 238     }
 239   }
 240
 241   mbkfree( table->table );
 242   table->table  = new;
 243   table->entree = elem;
 244 }