1 /*------------------------------------------------------------\
2 | |
3 | This file is part of the Alliance CAD System Copyright |
4 | (C) Laboratoire LIP6 - D�partement ASIM Universite P&M Curie|
5 | |
6 | Home page : http://www-asim.lip6.fr/alliance/ |
7 | E-mail : mailto:alliance-users@asim.lip6.fr |
8 | |
9 | This progam is free software; you can redistribute it |
10 | and/or modify it under the terms of the GNU Library General|
11 | Public License as published by the Free Software Foundation |
12 | either version 2 of the License, or (at your option) any |
13 | later version. |
14 | |
15 | Alliance VLSI CAD System is distributed in the hope that |
16 | it will be useful, but WITHOUT ANY WARRANTY; |
17 | without even the implied warranty of MERCHANTABILITY or |
18 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General |
19 | Public License for more details. |
20 | |
21 | You should have received a copy of the GNU General Public |
22 | License along with the GNU C Library; see the file COPYING. |
23 | If not, write to the Free Software Foundation, Inc., |
24 | 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. |
25 | |
26 \------------------------------------------------------------*/
27 /*------------------------------------------------------------\
28 | |
29 | Tool : Aut |
30 | |
31 | File : authash.c |
32 | |
33 | Date : 03.12.96 |
34 | |
35 | Author : Jacomme Ludovic |
36 | |
37 \------------------------------------------------------------*/
38 /*------------------------------------------------------------\
39 | |
40 | Include Files |
41 | |
42 \------------------------------------------------------------*/
43
44 # include <stdio.h>
45 # include <string.h>
46 # include <memory.h>
47
48 # include <mut.h>
49 # include "aut.h"
50
51 # include "authash.h"
52 # include "auterror.h"
53
54 /*------------------------------------------------------------\
55 | |
56 | Constants |
57 | |
58 \------------------------------------------------------------*/
59 /*------------------------------------------------------------\
60 | |
61 | Types |
62 | |
63 \------------------------------------------------------------*/
64 /*------------------------------------------------------------\
65 | |
66 | Variables |
67 | |
68 \------------------------------------------------------------*/
69
70 long AUT_HASH_PRIME_NUMBER[ AUT_MAX_PRIME_NUMBER ] =
71 {
72 1,
73 3,
74 5,
75 7,
76 13,
77 23,
78 59,
79 101,
80 503,
81 1009,
82 2003,
83 3001,
84 4001,
85 5003,
86 6007,
87 7001,
88 8009,
89 9001,
90 10007,
91 12007,
92 14009,
93 16001,
94 18013,
95 20011,
96 25013,
97 30011,
98 35023,
99 40009,
100 50021,
101 60013,
102 80021,
103 100003,
104 150001,
105 200003,
106 250007,
107 300007,
108 400009,
109 600011,
110 800011,
111 1000003,
112 1500007,
113 2000003,
114 2642201,
115 3328979,
116 4194287,
117 5284393,
118 6657919,
119 8388593,
120 10568797,
121 13315831,
122 16777199,
123 33554393,
124 67108859,
125 134217689,
126 268435399,
127 536870879,
128 1073741789,
129 2147483629
130 };
131
132 long AUT_HASH_STRETCH_FACTOR = HASH_STRETCH_FACTOR;
133 long AUT_HASH_MAX_SCAN = HASH_MAX_SCAN;
134
135 /*------------------------------------------------------------\
136 | |
137 | Functions |
138 | |
139 \------------------------------------------------------------*/
140 /*------------------------------------------------------------\
141 | |
142 | Aut Set Hash Size Function |
143 | |
144 \------------------------------------------------------------*/
145
setauthfunc(HashTable,FuncSize,FuncKey,FuncIndex)146 void setauthfunc( HashTable, FuncSize, FuncKey, FuncIndex )
147
148 authtable *HashTable;
149 long (*FuncSize)();
150 long (*FuncKey)();
151 long (*FuncIndex)();
152 {
153 if ( FuncSize != 0 ) HashTable->FUNC_SIZE = FuncSize;
154 if ( FuncKey != 0 ) HashTable->FUNC_KEY = FuncKey;
155 if ( FuncIndex != 0 ) HashTable->FUNC_INDEX = FuncIndex;
156 }
157
158 /*------------------------------------------------------------\
159 | |
160 | Aut Get Hash Size |
161 | |
162 \------------------------------------------------------------*/
163
getauthsize(Size)164 long getauthsize( Size )
165
166 long Size;
167 {
168 int Index;
169
170 for ( Index = 0; Index < AUT_MAX_PRIME_NUMBER; Index++ )
171 {
172 if ( AUT_HASH_PRIME_NUMBER[ Index ] > Size )
173 {
174 return( AUT_HASH_PRIME_NUMBER[ Index ] );
175 }
176 }
177
178 if ( ( Size & 1 ) == 0 )
179 {
180 Size++;
181 }
182
183 return( Size );
184 }
185
186 /*------------------------------------------------------------\
187 | |
188 | Aut Get Hash Key |
189 | |
190 \------------------------------------------------------------*/
191
getauthkey(Table,Key)192 long getauthkey( Table, Key )
193
194 authtable *Table;
195 char *Key;
196 {
197 return( ( (unsigned long)Key >> 2 ) % Table->TABLE_SIZE );
198 }
199
200 /*------------------------------------------------------------\
201 | |
202 | Aut Get Hash Index |
203 | |
204 \------------------------------------------------------------*/
205
getauthindex(Table,Key,Index)206 long getauthindex( Table, Key, Index )
207
208 authtable *Table;
209 char *Key;
210 long Index;
211 {
212 Index = Index + 1;
213
214 if ( Index >= Table->TABLE_SIZE ) Index = 0;
215
216 return( Index );
217 }
218
219 /*------------------------------------------------------------\
220 | |
221 | Aut Check Hash Key |
222 | |
223 \------------------------------------------------------------*/
224
checkauthkey(Key,Severity)225 int checkauthkey( Key, Severity )
226
227 char *Key;
228 int Severity;
229 {
230 if ( ( Key == AUT_HASH_KEY_EMPTY ) ||
231 ( Key == AUT_HASH_KEY_DELETED ) )
232 {
233 if ( Severity )
234 {
235 auterror( AUT_HASH_KEY_ERROR, Key );
236 }
237
238 return( 0 );
239 }
240
241 return( 1 );
242 }
243
244 /*------------------------------------------------------------\
245 | |
246 | Aut Create Hash Table |
247 | |
248 \------------------------------------------------------------*/
249
createauthtable(Length)250 authtable *createauthtable( Length )
251
252 long Length;
253 {
254 authtable *HashTable;
255 authelem *Table;
256
257 if ( Length < 0 )
258 {
259 auterror( AUT_HASH_SIZE_ERROR, Length );
260 }
261
262 Length = getauthsize( Length );
263
264 HashTable = allocauthtable();
265 Table = allocauthelem( Length );
266
267 HashTable->TABLE = Table;
268 HashTable->TABLE_SIZE = Length;
269 HashTable->FUNC_SIZE = getauthsize;
270 HashTable->FUNC_INDEX = getauthindex;
271 HashTable->FUNC_KEY = getauthkey;
272
273 return( HashTable );
274 }
275
276 /*------------------------------------------------------------\
277 | |
278 | Aut Destroy Hash Table |
279 | |
280 \------------------------------------------------------------*/
281
destroyauthtable(HashTable)282 void destroyauthtable( HashTable )
283
284 authtable *HashTable;
285 {
286 freeauthelem( HashTable->TABLE );
287 freeauthtable( HashTable );
288 }
289
290 /*------------------------------------------------------------\
291 | |
292 | Aut Reset Hash Table |
293 | |
294 \------------------------------------------------------------*/
295
resetauthtable(HashTable)296 void resetauthtable( HashTable )
297
298 authtable *HashTable;
299 {
300 if ( HashTable->NUMBER_ELEM > 0 )
301 {
302 memset( (void *)HashTable->TABLE, 0,
303 (size_t)HashTable->TABLE_SIZE * sizeof( authelem ) );
304 }
305
306 HashTable->NUMBER_ELEM = 0;
307 HashTable->NUMBER_ADD = 0;
308 HashTable->NUMBER_SCAN = 0;
309 HashTable->NUMBER_DEL = 0;
310 HashTable->NUMBER_STRETCH = 0;
311 }
312
313 /*------------------------------------------------------------\
314 | |
315 | Aut Stretch Hash Table |
316 | |
317 \------------------------------------------------------------*/
318
stretchauthtable(HashTable)319 void stretchauthtable( HashTable )
320
321 authtable *HashTable;
322 {
323 authelem *NewTable;
324 authelem *Table;
325 authelem *Element;
326 long NewLength;
327 long Length;
328
329 Length = HashTable->TABLE_SIZE;
330 Table = HashTable->TABLE;
331 NewLength = (*HashTable->FUNC_SIZE)( Length * AUT_HASH_STRETCH_FACTOR / 100 );
332 NewTable = allocauthelem( NewLength );
333
334 HashTable->TABLE = NewTable;
335 HashTable->TABLE_SIZE = NewLength;
336 HashTable->NUMBER_ELEM = 0;
337 HashTable->NUMBER_STRETCH += 1;
338
339 while ( Length > 0 )
340 {
341 Length = Length - 1;
342 Element = &Table[ Length ];
343
344 if ( ( Element->KEY != AUT_HASH_KEY_EMPTY ) &&
345 ( Element->KEY != AUT_HASH_KEY_DELETED ) )
346 {
347 addauthelem( HashTable,
348 Element->KEY,
349 Element->VALUE );
350 }
351 }
352
353 freeauthelem( Table );
354 }
355
356 /*------------------------------------------------------------\
357 | |
358 | Aut Add Hash Element |
359 | |
360 \------------------------------------------------------------*/
361
addauthelem(HashTable,Key,Value)362 authelem *addauthelem( HashTable, Key, Value )
363
364 authtable *HashTable;
365 char *Key;
366 long Value;
367 {
368 authelem *Element;
369 long HashIndex;
370 long Deleted;
371 int NumberScan;
372 char Stop;
373
374 check_authkey( Key );
375
376 HashIndex = (*HashTable->FUNC_KEY)( HashTable, Key );
377 Deleted = -1;
378 NumberScan = 0;
379 Stop = 0;
380
381 HashTable->NUMBER_ADD++;
382
383 do
384 {
385 Element = &HashTable->TABLE[ HashIndex ];
386
387 if ( Element->KEY == AUT_HASH_KEY_DELETED )
388 {
389 if ( Deleted == -1 ) Deleted = HashIndex;
390 }
391 else
392 if ( ( Element->KEY == AUT_HASH_KEY_EMPTY ) ||
393 ( Element->KEY == Key ) )
394 {
395 if ( Element->KEY == AUT_HASH_KEY_EMPTY )
396 {
397 HashTable->NUMBER_ELEM++;
398
399 if ( Deleted != -1 )
400 {
401 Element = &HashTable->TABLE[ Deleted ];
402 }
403 }
404 else
405 if ( Deleted != -1 )
406 {
407 Element->KEY = AUT_HASH_KEY_DELETED;
408 Element = &HashTable->TABLE[ Deleted ];
409 }
410
411 Element->VALUE = Value;
412 Element->KEY = Key;
413
414 Stop = 1;
415 }
416
417 NumberScan += 1;
418
419 if ( Stop == 0 )
420 {
421 if ( NumberScan > AUT_HASH_MAX_SCAN )
422 {
423 if ( Deleted != -1 )
424 {
425 HashTable->TABLE[ Deleted ].KEY = AUT_HASH_KEY_EMPTY;
426 HashIndex = Deleted;
427 Deleted = -1;
428 }
429 else
430 {
431 stretchauthtable( HashTable );
432
433 HashIndex = (*HashTable->FUNC_KEY)( HashTable, Key );
434 NumberScan = 0;
435 }
436 }
437 else
438 {
439 HashIndex = (*HashTable->FUNC_INDEX)( HashTable, Key, HashIndex );
440 }
441 }
442 }
443 while ( Stop == 0 );
444
445 HashTable->NUMBER_SCAN += NumberScan + 1;
446
447 return( Element );
448 }
449
450 /*------------------------------------------------------------\
451 | |
452 | Aut Del Hash Element |
453 | |
454 \------------------------------------------------------------*/
455
delauthelem(HashTable,Key)456 int delauthelem( HashTable, Key )
457
458 authtable *HashTable;
459 char *Key;
460 {
461 authelem *Element;
462 long HashIndex;
463 int NumberScan;
464
465 check_authkey( Key );
466
467 HashIndex = (*HashTable->FUNC_KEY)( HashTable, Key );
468 NumberScan = 0;
469
470 HashTable->NUMBER_DEL++;
471
472 do
473 {
474 Element = &HashTable->TABLE[ HashIndex ];
475
476 if ( Element->KEY == Key )
477 {
478 HashTable->NUMBER_ELEM--;
479
480 Element->KEY = AUT_HASH_KEY_DELETED;
481
482 HashTable->NUMBER_SCAN += NumberScan + 1;
483
484 return( 1 );
485 }
486
487 if ( Element->KEY == AUT_HASH_KEY_EMPTY )
488 {
489 return( 0 );
490 }
491
492 NumberScan += 1;
493 HashIndex = (*HashTable->FUNC_INDEX)( HashTable, Key, HashIndex );
494 }
495 while ( NumberScan <= AUT_HASH_MAX_SCAN );
496
497 return( 0 );
498 }
499
500 /*------------------------------------------------------------\
501 | |
502 | Aut Search Hash Element |
503 | |
504 \------------------------------------------------------------*/
505
searchauthelem(HashTable,Key)506 authelem *searchauthelem( HashTable, Key )
507
508 authtable *HashTable;
509 char *Key;
510 {
511 authelem *Element;
512 long HashIndex;
513 int NumberScan;
514
515 check_authkey( Key );
516
517 HashIndex = (*HashTable->FUNC_KEY)( HashTable, Key );
518 NumberScan = 0;
519
520 do
521 {
522 Element = &HashTable->TABLE[ HashIndex ];
523
524 if ( Element->KEY == Key )
525 {
526 return( Element );
527 }
528
529 if ( Element->KEY == AUT_HASH_KEY_EMPTY )
530 {
531 return( (authelem *)0 );
532 }
533
534 NumberScan += 1;
535 HashIndex = (*HashTable->FUNC_INDEX)( HashTable, Key, HashIndex );
536 }
537 while ( NumberScan <= AUT_HASH_MAX_SCAN );
538
539 return( (authelem *)0 );
540 }
541
542 /*------------------------------------------------------------\
543 | |
544 | Aut View Hash Element |
545 | |
546 \------------------------------------------------------------*/
547
viewauthelem(Element)548 void viewauthelem( Element )
549
550 authelem *Element;
551 {
552 fprintf( stdout, "VALUE: %10ld KEY: %s\n",
553 Element->VALUE, Element->KEY );
554 }
555
556 /*------------------------------------------------------------\
557 | |
558 | Aut View Hash Table |
559 | |
560 \------------------------------------------------------------*/
561
viewauthtable(HashTable,FuncView)562 void viewauthtable( HashTable, FuncView )
563
564 authtable *HashTable;
565 void (*FuncView)();
566 {
567 authelem *Element;
568 long HashIndex;
569
570 fprintf( stdout, "--> HashTable\n" );
571 fprintf( stdout, " SIZE : %ld\n", HashTable->TABLE_SIZE );
572 fprintf( stdout, " ELEMENT : %ld\n", HashTable->NUMBER_ELEM );
573 fprintf( stdout, " STRETCH : %ld\n", HashTable->NUMBER_STRETCH );
574 fprintf( stdout, " SCAN : %ld\n", HashTable->NUMBER_SCAN );
575 fprintf( stdout, " ADD : %ld\n", HashTable->NUMBER_ADD );
576 fprintf( stdout, " DEL : %ld\n", HashTable->NUMBER_DEL );
577
578 if ( FuncView )
579 {
580 for ( HashIndex = 0; HashIndex < HashTable->TABLE_SIZE; HashIndex++ )
581 {
582 Element = &HashTable->TABLE[ HashIndex ];
583
584 if ( checkauthkey( Element->KEY, 0 ) )
585 {
586 fprintf( stdout, " INDEX : %-4ld ", HashIndex );
587
588 (*FuncView)( Element );
589 }
590 }
591 }
592
593 fprintf( stdout, "<-- HashTable\n" );
594 }
595