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 : mailto:alliance-users@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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 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 <mut.h>
36 #include "spi_hash.h"
37
38 /* 2^n elements dans la table de hash */
39 #define HASH_MINI 4
40 #define HASH_MAXI 15
41
42 /* 2^n Seuil d'augmentation */
43 #define HASH_DELTA 1
44
creatthash()45 thash* creatthash( )
46 {
47 thash *new;
48 int i;
49 int n;
50
51 new = ( thash* )mbkalloc( sizeof( thash ) );
52 new->entree = HASH_MINI ;
53 n = 1 << new->entree;
54 new->table = ( hashelem** )mbkalloc( sizeof( hashelem* ) * n );
55 new->nbelem = 0;
56 new->tete = NULL;
57 new->libere = NULL;
58
59 for( i = 0 ; i < n ; i++ )
60 new->table[i] = NULL;
61
62 return( new );
63 }
64
freethash(pt)65 void freethash( pt )
66 thash *pt;
67 {
68 chain_list *scanchain;
69
70 mbkfree( pt->table );
71 /*
72 if( pt->tete )
73 mbkfree( pt->tete );
74 */
75
76 for( scanchain = pt->libere ; scanchain ; scanchain = scanchain->NEXT )
77 mbkfree( scanchain->DATA );
78 freechain( pt->libere );
79
80 mbkfree( pt );
81 }
82
nouvhashelem(table)83 hashelem* nouvhashelem( table )
84 thash *table;
85 {
86 int i;
87 hashelem *elem;
88
89 if( ! table->tete )
90 {
91 table->tete = ( hashelem* ) mbkalloc ( sizeof( hashelem ) * 64 );
92 table->libere = addchain( table->libere, table->tete );
93 elem = table->tete;
94
95 for( i = 1 ; i < 64 ; i++ )
96 {
97 elem->suivant = elem + 1;
98 elem++;
99 }
100 elem->suivant = NULL;
101 }
102
103 elem = table->tete;
104 table->tete = table->tete->suivant;
105
106 return( elem );
107 }
108
liberehashelem(table,elem)109 void liberehashelem( table, elem )
110 thash *table;
111 hashelem *elem;
112 {
113 elem->suivant = table->tete;
114 table->tete = elem;
115 }
116
addthashelem(nouveau,ptr,table)117 void addthashelem( nouveau, ptr, table )
118 char *nouveau;
119 void *ptr;
120 thash *table;
121 {
122 int s;
123 hashelem *elm;
124
125
126 if( table->nbelem == 1 << ( table->entree + HASH_DELTA ) &&
127 table->entree < HASH_MAXI )
128 resizetable( table, table->entree + 1 );
129
130 s = thashsignature( nouveau, table->entree );
131 elm = nouvhashelem( table );
132
133 elm->suivant = table->table[ s ];
134 table->table[ s ] = elm;
135
136 elm->mot = nouveau;
137 elm->ptr = ptr;
138
139 table->nbelem++;
140 }
141
getthashelem(elem,table,status)142 void* getthashelem( elem, table, status )
143 char *elem;
144 thash *table;
145 int *status;
146 {
147 int s;
148 hashelem *scan;
149
150 s = thashsignature( elem, table->entree );
151
152 for( scan = table->table[ s ] ; scan ; scan = scan->suivant )
153 {
154 if( scan->mot == elem || strcmp( scan->mot, elem ) == 0 )
155 {
156 if( status != NULL )
157 *status = 1;
158 return( scan->ptr );
159 }
160 }
161
162 if( status != NULL )
163 *status = 0;
164
165 return( NULL );
166 }
167
thashsignature(c,l)168 int thashsignature( c, l )
169 char *c;
170 int l;
171 {
172 int bit;
173 int b;
174 int dec;
175
176 dec = 0;
177 bit = 0;
178
179 while( *c )
180 {
181 for( bit = 0; bit < 8 ; bit ++ )
182 {
183 b = ( *c >> bit ) & 0x1;
184
185 /* Polynome g�n�rateur : X^15 + X + 1 */
186 dec = ( ( dec & 0x3FFE ) << 1 ) |
187 ( ( ( dec & 0x4000 ) >> 13 ) ^ ( ( dec & 0x1 ) << 1 ) ) |
188 ( ( ( dec & 0x4000 ) >> 14 ) ^ b ) ;
189 }
190 c++;
191 }
192
193 return( dec % ( 1 << l ) );
194 }
195
resizetable(table,elem)196 void resizetable( table, elem )
197 thash *table;
198 int elem;
199 {
200 hashelem **new;
201 hashelem *nouv;
202 hashelem *scan;
203 hashelem *suiv;
204 int n;
205 int i;
206 int s;
207
208 n = 1 << elem;
209
210 new = ( hashelem** )mbkalloc( sizeof( hashelem* ) * n );
211 for( i = 0 ; i < n ; i++ )
212 new[ i ] = NULL;
213
214 n = 1 << table->entree;
215
216 for( i = 0 ; i < n ; i++ )
217 {
218 for( scan = table->table[i] ; scan ; scan = scan->suivant )
219 {
220 nouv = nouvhashelem( table );
221 s = thashsignature( scan->mot, elem );
222
223 nouv->suivant = new[ s ];
224 new[s] = nouv;
225 nouv->mot = scan->mot;
226 nouv->ptr = scan->ptr;
227 }
228
229 for( scan = table->table[i] ; scan ; scan = suiv )
230 {
231 suiv = scan->suivant;
232 liberehashelem( table, scan );
233 }
234 }
235
236 mbkfree( table->table );
237 table->table = new;
238 table->entree = elem;
239 }
240