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 : authash2.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
52 # include "authash2.h"
53 # include "auterror.h"
54
55 /*------------------------------------------------------------\
56 | |
57 | Constants |
58 | |
59 \------------------------------------------------------------*/
60 /*------------------------------------------------------------\
61 | |
62 | Types |
63 | |
64 \------------------------------------------------------------*/
65 /*------------------------------------------------------------\
66 | |
67 | Variables |
68 | |
69 \------------------------------------------------------------*/
70
71 long AUT_HASH2_STRETCH_FACTOR = HASH2_STRETCH_FACTOR;
72 long AUT_HASH2_MAX_SCAN = HASH2_MAX_SCAN;
73
74 /*------------------------------------------------------------\
75 | |
76 | Functions |
77 | |
78 \------------------------------------------------------------*/
79 /*------------------------------------------------------------\
80 | |
81 | Aut Set Hash Size Function |
82 | |
83 \------------------------------------------------------------*/
84
setauth2func(HashTable,FuncSize,FuncKey,FuncIndex)85 void setauth2func( HashTable, FuncSize, FuncKey, FuncIndex )
86
87 auth2table *HashTable;
88 long (*FuncSize)();
89 long (*FuncKey)();
90 long (*FuncIndex)();
91 {
92 if ( FuncSize != 0 ) HashTable->FUNC_SIZE = FuncSize;
93 if ( FuncKey != 0 ) HashTable->FUNC_KEY = FuncKey;
94 if ( FuncIndex != 0 ) HashTable->FUNC_INDEX = FuncIndex;
95 }
96
97 /*------------------------------------------------------------\
98 | |
99 | Aut Get Hash Size |
100 | |
101 \------------------------------------------------------------*/
102
getauth2size(Size)103 long getauth2size( Size )
104
105 long Size;
106 {
107 int Index;
108
109 for ( Index = 0; Index < AUT_MAX_PRIME_NUMBER; Index++ )
110 {
111 if ( AUT_HASH_PRIME_NUMBER[ Index ] > Size )
112 {
113 return( AUT_HASH_PRIME_NUMBER[ Index ] );
114 }
115 }
116
117 if ( ( Size & 1 ) == 0 )
118 {
119 Size++;
120 }
121
122 return( Size );
123 }
124
125 /*------------------------------------------------------------\
126 | |
127 | Aut Get Hash Key |
128 | |
129 \------------------------------------------------------------*/
130
getauth2key(Table,Key1,Key2)131 long getauth2key( Table, Key1, Key2 )
132
133 auth2table *Table;
134 char *Key1;
135 char *Key2;
136 {
137 return( ( ((unsigned long)Key1 >> 2 ) +
138 ((unsigned long)Key2 << 1 ) ) % Table->TABLE_SIZE );
139 }
140
141 /*------------------------------------------------------------\
142 | |
143 | Aut Get Hash Index |
144 | |
145 \------------------------------------------------------------*/
146
getauth2index(Table,Key1,Key2,Index)147 long getauth2index( Table, Key1, Key2, Index )
148
149 auth2table *Table;
150 char *Key1;
151 char *Key2;
152 long Index;
153 {
154 return( ( ((unsigned long)Index ) +
155 ((unsigned long)Index << 2 ) +
156 ((unsigned long)Key2 ) +
157 ((unsigned long)Key1 << 1 ) ) % Table->TABLE_SIZE );
158 }
159
160 /*------------------------------------------------------------\
161 | |
162 | Aut Check Hash Key |
163 | |
164 \------------------------------------------------------------*/
165
checkauth2key(Key1,Key2,Severity)166 int checkauth2key( Key1, Key2, Severity )
167
168 char *Key1;
169 char *Key2;
170 int Severity;
171 {
172 if ( ( Key1 == AUT_HASH_KEY_EMPTY ) ||
173 ( Key1 == AUT_HASH_KEY_DELETED ) )
174 {
175 if ( Severity )
176 {
177 auterror( AUT_HASH_KEY_ERROR, Key1 );
178 }
179
180 return( 0 );
181 }
182
183 if ( ( Key2 == AUT_HASH_KEY_EMPTY ) ||
184 ( Key2 == AUT_HASH_KEY_DELETED ) )
185 {
186 if ( Severity )
187 {
188 auterror( AUT_HASH_KEY_ERROR, Key2 );
189 }
190
191 return( 0 );
192 }
193
194 return( 1 );
195 }
196
197 /*------------------------------------------------------------\
198 | |
199 | Aut Create Hash Table |
200 | |
201 \------------------------------------------------------------*/
202
createauth2table(Length)203 auth2table *createauth2table( Length )
204
205 long Length;
206 {
207 auth2table *HashTable;
208 auth2elem *Table;
209
210 if ( Length < 0 )
211 {
212 auterror( AUT_HASH_SIZE_ERROR, Length );
213 }
214
215 Length = getauth2size( Length );
216
217 HashTable = allocauth2table();
218 Table = allocauth2elem( Length );
219
220 HashTable->TABLE = Table;
221 HashTable->TABLE_SIZE = Length;
222 HashTable->FUNC_SIZE = getauth2size;
223 HashTable->FUNC_INDEX = getauth2index;
224 HashTable->FUNC_KEY = getauth2key;
225
226 return( HashTable );
227 }
228
229 /*------------------------------------------------------------\
230 | |
231 | Aut Destroy Hash Table |
232 | |
233 \------------------------------------------------------------*/
234
destroyauth2table(HashTable)235 void destroyauth2table( HashTable )
236
237 auth2table *HashTable;
238 {
239 freeauth2elem( HashTable->TABLE );
240 freeauth2table( HashTable );
241 }
242
243 /*------------------------------------------------------------\
244 | |
245 | Aut Reset Hash Table |
246 | |
247 \------------------------------------------------------------*/
248
resetauth2table(HashTable)249 void resetauth2table( HashTable )
250
251 auth2table *HashTable;
252 {
253 if ( HashTable->NUMBER_ELEM > 0 )
254 {
255 memset( (void *)HashTable->TABLE, 0,
256 (size_t)HashTable->TABLE_SIZE * sizeof( auth2elem ) );
257 }
258
259 HashTable->NUMBER_ELEM = 0;
260 HashTable->NUMBER_ADD = 0;
261 HashTable->NUMBER_SCAN = 0;
262 HashTable->NUMBER_DEL = 0;
263 HashTable->NUMBER_STRETCH = 0;
264 }
265
266 /*------------------------------------------------------------\
267 | |
268 | Aut Stretch Hash Table |
269 | |
270 \------------------------------------------------------------*/
271
stretchauth2table(HashTable)272 void stretchauth2table( HashTable )
273
274 auth2table *HashTable;
275 {
276 auth2elem *NewTable;
277 auth2elem *Table;
278 auth2elem *Element;
279 long NewLength;
280 long Length;
281
282 Length = HashTable->TABLE_SIZE;
283 Table = HashTable->TABLE;
284 NewLength = (*HashTable->FUNC_SIZE)( Length * AUT_HASH2_STRETCH_FACTOR / 100 );
285 NewTable = allocauth2elem( NewLength );
286
287 HashTable->TABLE = NewTable;
288 HashTable->TABLE_SIZE = NewLength;
289 HashTable->NUMBER_ELEM = 0;
290 HashTable->NUMBER_STRETCH += 1;
291
292 while ( Length > 0 )
293 {
294 Length = Length - 1;
295 Element = &Table[ Length ];
296
297 if ( ( Element->KEY1 != AUT_HASH_KEY_EMPTY ) &&
298 ( Element->KEY1 != AUT_HASH_KEY_DELETED ) )
299 {
300 addauth2elem( HashTable,
301 Element->KEY1,
302 Element->KEY2,
303 Element->VALUE );
304 }
305 }
306
307 freeauth2elem( Table );
308 }
309
310 /*------------------------------------------------------------\
311 | |
312 | Aut Add Hash Element |
313 | |
314 \------------------------------------------------------------*/
315
addauth2elem(HashTable,Key1,Key2,Value)316 auth2elem *addauth2elem( HashTable, Key1, Key2, Value )
317
318 auth2table *HashTable;
319 char *Key1;
320 char *Key2;
321 long Value;
322 {
323 auth2elem *Element;
324 long HashIndex;
325 long Deleted;
326 int NumberScan;
327 char Stop;
328
329 check_auth2key( Key1, Key2 );
330
331 HashIndex = (*HashTable->FUNC_KEY)( HashTable, Key1, Key2 );
332 Deleted = -1;
333 NumberScan = 0;
334 Stop = 0;
335
336 HashTable->NUMBER_ADD++;
337
338 do
339 {
340 Element = &HashTable->TABLE[ HashIndex ];
341
342 if ( Element->KEY1 == AUT_HASH_KEY_DELETED )
343 {
344 if ( Deleted == -1 ) Deleted = HashIndex;
345 }
346 else
347 if ( ( Element->KEY1 == AUT_HASH_KEY_EMPTY ) ||
348 ( ( Element->KEY1 == Key1 ) &&
349 ( Element->KEY2 == Key2 ) ) )
350 {
351 if ( Element->KEY1 == AUT_HASH_KEY_EMPTY )
352 {
353 HashTable->NUMBER_ELEM++;
354
355 if ( Deleted != -1 )
356 {
357 Element = &HashTable->TABLE[ Deleted ];
358 }
359 }
360 else
361 if ( Deleted != -1 )
362 {
363 Element->KEY1 = AUT_HASH_KEY_DELETED;
364 Element = &HashTable->TABLE[ Deleted ];
365 }
366
367 Element->VALUE = Value;
368 Element->KEY1 = Key1;
369 Element->KEY2 = Key2;
370
371 Stop = 1;
372 }
373
374 NumberScan += 1;
375
376 if ( Stop == 0 )
377 {
378 if ( NumberScan > AUT_HASH2_MAX_SCAN )
379 {
380 if ( Deleted != -1 )
381 {
382 HashTable->TABLE[ Deleted ].KEY1 = AUT_HASH_KEY_EMPTY;
383 HashIndex = Deleted;
384 Deleted = -1;
385 }
386 else
387 {
388 stretchauth2table( HashTable );
389
390 HashIndex = (*HashTable->FUNC_KEY)( HashTable, Key1, Key2 );
391 NumberScan = 0;
392 }
393 }
394 else
395 {
396 HashIndex = (*HashTable->FUNC_INDEX)( HashTable, Key1, Key2, HashIndex );
397 }
398 }
399 }
400 while ( Stop == 0 );
401
402 HashTable->NUMBER_SCAN += NumberScan + 1;
403
404 return( Element );
405 }
406
407 /*------------------------------------------------------------\
408 | |
409 | Aut Del Hash Element |
410 | |
411 \------------------------------------------------------------*/
412
delauth2elem(HashTable,Key1,Key2)413 int delauth2elem( HashTable, Key1, Key2 )
414
415 auth2table *HashTable;
416 char *Key1;
417 char *Key2;
418 {
419 auth2elem *Element;
420 long HashIndex;
421 int NumberScan;
422
423 check_auth2key( Key1, Key2 );
424
425 HashIndex = (*HashTable->FUNC_KEY)( HashTable, Key1, Key2 );
426 NumberScan = 0;
427
428 HashTable->NUMBER_DEL++;
429
430 do
431 {
432 Element = &HashTable->TABLE[ HashIndex ];
433
434 if ( ( Element->KEY1 == Key1 ) &&
435 ( Element->KEY2 == Key2 ) )
436 {
437 HashTable->NUMBER_ELEM--;
438
439 Element->KEY1 = AUT_HASH_KEY_DELETED;
440
441 HashTable->NUMBER_SCAN += NumberScan + 1;
442
443 return( 1 );
444 }
445
446 if ( Element->KEY1 == AUT_HASH_KEY_EMPTY )
447 {
448 return( 0 );
449 }
450
451 NumberScan += 1;
452 HashIndex = (*HashTable->FUNC_INDEX)( HashTable, Key1, Key2, HashIndex );
453 }
454 while ( NumberScan <= AUT_HASH2_MAX_SCAN );
455
456 return( 0 );
457 }
458
459 /*------------------------------------------------------------\
460 | |
461 | Aut Search Hash Element |
462 | |
463 \------------------------------------------------------------*/
464
searchauth2elem(HashTable,Key1,Key2)465 auth2elem *searchauth2elem( HashTable, Key1, Key2 )
466
467 auth2table *HashTable;
468 char *Key1;
469 char *Key2;
470 {
471 auth2elem *Element;
472 long HashIndex;
473 int NumberScan;
474
475 check_auth2key( Key1, Key2 );
476
477 HashIndex = (*HashTable->FUNC_KEY)( HashTable, Key1, Key2 );
478 NumberScan = 0;
479
480 do
481 {
482 Element = &HashTable->TABLE[ HashIndex ];
483
484 if ( ( Element->KEY1 == Key1 ) &&
485 ( Element->KEY2 == Key2 ) )
486 {
487 return( Element );
488 }
489
490 if ( Element->KEY1 == AUT_HASH_KEY_EMPTY )
491 {
492 return( (auth2elem *)0 );
493 }
494
495 NumberScan += 1;
496 HashIndex = (*HashTable->FUNC_INDEX)( HashTable, Key1, Key2, HashIndex );
497 }
498 while ( NumberScan <= AUT_HASH2_MAX_SCAN );
499
500 return( (auth2elem *)0 );
501 }
502
503 /*------------------------------------------------------------\
504 | |
505 | Aut View Hash Element |
506 | |
507 \------------------------------------------------------------*/
508
viewauth2elem(Element)509 void viewauth2elem( Element )
510
511 auth2elem *Element;
512 {
513 fprintf( stdout, "VALUE: %10ld KEY1: %s KEY2: %s\n",
514 Element->VALUE, Element->KEY1, Element->KEY2 );
515 }
516
517 /*------------------------------------------------------------\
518 | |
519 | Aut View Hash Table |
520 | |
521 \------------------------------------------------------------*/
522
viewauth2table(HashTable,FuncView)523 void viewauth2table( HashTable, FuncView )
524
525 auth2table *HashTable;
526 void (*FuncView)();
527 {
528 auth2elem *Element;
529 long HashIndex;
530
531 fprintf( stdout, "--> HashTable\n" );
532 fprintf( stdout, " SIZE : %ld\n", HashTable->TABLE_SIZE );
533 fprintf( stdout, " ELEMENT : %ld\n", HashTable->NUMBER_ELEM );
534 fprintf( stdout, " STRETCH : %ld\n", HashTable->NUMBER_STRETCH );
535 fprintf( stdout, " SCAN : %ld\n", HashTable->NUMBER_SCAN );
536 fprintf( stdout, " ADD : %ld\n", HashTable->NUMBER_ADD );
537 fprintf( stdout, " DEL : %ld\n", HashTable->NUMBER_DEL );
538
539 if ( FuncView )
540 {
541 for ( HashIndex = 0; HashIndex < HashTable->TABLE_SIZE; HashIndex++ )
542 {
543 Element = &HashTable->TABLE[ HashIndex ];
544
545 if ( checkauth2key( Element->KEY1, Element->KEY2, 0 ) )
546 {
547 fprintf( stdout, " INDEX : %-4ld ", HashIndex );
548
549 (*FuncView)( Element );
550 }
551 }
552 }
553
554 fprintf( stdout, "<-- HashTable\n" );
555 }
556