1 /**CFile****************************************************************
2
3 FileName [utilNam.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Manager for character strings.]
8
9 Synopsis [Manager for character strings.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - June 20, 2005.]
16
17 Revision [$Id: utilNam.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21
22 #include <stdio.h>
23 #include <string.h>
24 #include <stdlib.h>
25 #include <assert.h>
26
27 #include "abc_global.h"
28 #include "misc/vec/vec.h"
29 #include "utilNam.h"
30
31 ABC_NAMESPACE_IMPL_START
32
33
34 ////////////////////////////////////////////////////////////////////////
35 /// DECLARATIONS ///
36 ////////////////////////////////////////////////////////////////////////
37
38 // this package maps non-empty character strings into natural numbers and back
39
40 // name manager
41 struct Abc_Nam_t_
42 {
43 // info storage for names
44 int nStore; // the size of allocated storage
45 int iHandle; // the current free handle
46 char * pStore; // storage for name objects
47 // internal number mappings
48 Vec_Int_t vInt2Handle; // mapping integers into handles
49 Vec_Int_t vInt2Next; // mapping integers into nexts
50 // hash table for names
51 int * pBins; // the hash table bins
52 int nBins; // the number of bins
53 // manager recycling
54 int nRefs; // reference counter for the manager
55 // internal buffer
56 Vec_Str_t vBuffer;
57 };
58
Abc_NamHandleToStr(Abc_Nam_t * p,int h)59 static inline char * Abc_NamHandleToStr( Abc_Nam_t * p, int h ) { return (char *)(p->pStore + h); }
Abc_NamIntToHandle(Abc_Nam_t * p,int i)60 static inline int Abc_NamIntToHandle( Abc_Nam_t * p, int i ) { return Vec_IntEntry(&p->vInt2Handle, i); }
Abc_NamIntToStr(Abc_Nam_t * p,int i)61 static inline char * Abc_NamIntToStr( Abc_Nam_t * p, int i ) { return Abc_NamHandleToStr(p, Abc_NamIntToHandle(p,i)); }
Abc_NamIntToNext(Abc_Nam_t * p,int i)62 static inline int Abc_NamIntToNext( Abc_Nam_t * p, int i ) { return Vec_IntEntry(&p->vInt2Next, i); }
Abc_NamIntToNextP(Abc_Nam_t * p,int i)63 static inline int * Abc_NamIntToNextP( Abc_Nam_t * p, int i ) { return Vec_IntEntryP(&p->vInt2Next, i); }
64
65 ////////////////////////////////////////////////////////////////////////
66 /// FUNCTION DEFINITIONS ///
67 ////////////////////////////////////////////////////////////////////////
68
69 /**Function*************************************************************
70
71 Synopsis [Creates manager.]
72
73 Description []
74
75 SideEffects []
76
77 SeeAlso []
78
79 ***********************************************************************/
Abc_NamStart(int nObjs,int nAveSize)80 Abc_Nam_t * Abc_NamStart( int nObjs, int nAveSize )
81 {
82 Abc_Nam_t * p;
83 if ( nObjs == 0 )
84 nObjs = 16;
85 p = ABC_CALLOC( Abc_Nam_t, 1 );
86 p->nStore = ((nObjs * (nAveSize + 1) + 16) / 4) * 4;
87 p->pStore = ABC_ALLOC( char, p->nStore );
88 p->nBins = Abc_PrimeCudd( nObjs );
89 p->pBins = ABC_CALLOC( int, p->nBins );
90 // 0th object is unused
91 Vec_IntGrow( &p->vInt2Handle, nObjs ); Vec_IntPush( &p->vInt2Handle, -1 );
92 Vec_IntGrow( &p->vInt2Next, nObjs ); Vec_IntPush( &p->vInt2Next, -1 );
93 p->iHandle = 4;
94 memset( p->pStore, 0, 4 );
95 //Abc_Print( 1, "Starting nam with %d bins.\n", p->nBins );
96 // start reference counting
97 p->nRefs = 1;
98 return p;
99 }
100
101 /**Function*************************************************************
102
103 Synopsis [Deletes manager.]
104
105 Description []
106
107 SideEffects []
108
109 SeeAlso []
110
111 ***********************************************************************/
Abc_NamStop(Abc_Nam_t * p)112 void Abc_NamStop( Abc_Nam_t * p )
113 {
114 //Abc_Print( 1, "Starting nam with %d bins.\n", p->nBins );
115 Vec_StrErase( &p->vBuffer );
116 Vec_IntErase( &p->vInt2Handle );
117 Vec_IntErase( &p->vInt2Next );
118 ABC_FREE( p->pStore );
119 ABC_FREE( p->pBins );
120 ABC_FREE( p );
121 }
122
123 /**Function*************************************************************
124
125 Synopsis [Prints manager.]
126
127 Description []
128
129 SideEffects []
130
131 SeeAlso []
132
133 ***********************************************************************/
Abc_NamPrint(Abc_Nam_t * p,char * pFileName)134 void Abc_NamPrint( Abc_Nam_t * p, char * pFileName )
135 {
136 FILE * pFile = pFileName ? fopen( pFileName, "wb" ) : stdout;
137 int h, i;
138 if ( pFile == NULL ) { printf( "Count node open file %s\n", pFileName ); return; }
139 Vec_IntForEachEntryStart( &p->vInt2Handle, h, i, 1 )
140 fprintf( pFile, "%8d = %s\n", i, Abc_NamHandleToStr(p, h) );
141 if ( pFile != stdout )
142 fclose(pFile);
143 }
144
145 /**Function*************************************************************
146
147 Synopsis [References the manager.]
148
149 Description []
150
151 SideEffects []
152
153 SeeAlso []
154
155 ***********************************************************************/
Abc_NamRef(Abc_Nam_t * p)156 Abc_Nam_t * Abc_NamRef( Abc_Nam_t * p )
157 {
158 p->nRefs++;
159 return p;
160 }
161
162 /**Function*************************************************************
163
164 Synopsis [Dereferences the manager.]
165
166 Description []
167
168 SideEffects []
169
170 SeeAlso []
171
172 ***********************************************************************/
Abc_NamDeref(Abc_Nam_t * p)173 void Abc_NamDeref( Abc_Nam_t * p )
174 {
175 if ( p == NULL )
176 return;
177 if ( --p->nRefs == 0 )
178 Abc_NamStop( p );
179 }
180
181 /**Function*************************************************************
182
183 Synopsis [Returns the number of used entries.]
184
185 Description []
186
187 SideEffects []
188
189 SeeAlso []
190
191 ***********************************************************************/
Abc_NamObjNumMax(Abc_Nam_t * p)192 int Abc_NamObjNumMax( Abc_Nam_t * p )
193 {
194 return Vec_IntSize(&p->vInt2Handle);
195 }
196
197 /**Function*************************************************************
198
199 Synopsis [Reports memory usage of the manager.]
200
201 Description []
202
203 SideEffects []
204
205 SeeAlso []
206
207 ***********************************************************************/
Abc_NamMemUsed(Abc_Nam_t * p)208 int Abc_NamMemUsed( Abc_Nam_t * p )
209 {
210 if ( p == NULL )
211 return 0;
212 return sizeof(Abc_Nam_t) + p->iHandle + sizeof(int) * p->nBins +
213 sizeof(int) * (p->vInt2Handle.nSize + p->vInt2Next.nSize);
214 }
215
216 /**Function*************************************************************
217
218 Synopsis [Reports memory usage of the manager.]
219
220 Description []
221
222 SideEffects []
223
224 SeeAlso []
225
226 ***********************************************************************/
Abc_NamMemAlloc(Abc_Nam_t * p)227 int Abc_NamMemAlloc( Abc_Nam_t * p )
228 {
229 if ( p == NULL )
230 return 0;
231 return sizeof(Abc_Nam_t) + p->nStore + sizeof(int) * p->nBins +
232 sizeof(int) * (p->vInt2Handle.nCap + p->vInt2Next.nCap);
233 }
234
235 /**Function*************************************************************
236
237 Synopsis [Computes hash value of the C-string.]
238
239 Description []
240
241 SideEffects []
242
243 SeeAlso []
244
245 ***********************************************************************/
Abc_NamStrHash(const char * pStr,const char * pLim,int nTableSize)246 int Abc_NamStrHash( const char * pStr, const char * pLim, int nTableSize )
247 {
248 static int s_FPrimes[128] = {
249 1009, 1049, 1093, 1151, 1201, 1249, 1297, 1361, 1427, 1459,
250 1499, 1559, 1607, 1657, 1709, 1759, 1823, 1877, 1933, 1997,
251 2039, 2089, 2141, 2213, 2269, 2311, 2371, 2411, 2467, 2543,
252 2609, 2663, 2699, 2741, 2797, 2851, 2909, 2969, 3037, 3089,
253 3169, 3221, 3299, 3331, 3389, 3461, 3517, 3557, 3613, 3671,
254 3719, 3779, 3847, 3907, 3943, 4013, 4073, 4129, 4201, 4243,
255 4289, 4363, 4441, 4493, 4549, 4621, 4663, 4729, 4793, 4871,
256 4933, 4973, 5021, 5087, 5153, 5227, 5281, 5351, 5417, 5471,
257 5519, 5573, 5651, 5693, 5749, 5821, 5861, 5923, 6011, 6073,
258 6131, 6199, 6257, 6301, 6353, 6397, 6481, 6563, 6619, 6689,
259 6737, 6803, 6863, 6917, 6977, 7027, 7109, 7187, 7237, 7309,
260 7393, 7477, 7523, 7561, 7607, 7681, 7727, 7817, 7877, 7933,
261 8011, 8039, 8059, 8081, 8093, 8111, 8123, 8147
262 };
263 unsigned i, uHash;
264 if ( pLim )
265 {
266 for ( uHash = 0, i = 0; pStr+i < pLim; i++ )
267 if ( i & 1 )
268 uHash *= pStr[i] * s_FPrimes[i & 0x7F];
269 else
270 uHash ^= pStr[i] * s_FPrimes[i & 0x7F];
271 }
272 else
273 {
274 for ( uHash = 0, i = 0; pStr[i]; i++ )
275 if ( i & 1 )
276 uHash *= pStr[i] * s_FPrimes[i & 0x7F];
277 else
278 uHash ^= pStr[i] * s_FPrimes[i & 0x7F];
279 }
280 return uHash % nTableSize;
281 }
282 // https://en.wikipedia.org/wiki/Jenkins_hash_function
Abc_NamStrHash2(const char * pStr,const char * pLim,int nTableSize)283 int Abc_NamStrHash2( const char * pStr, const char * pLim, int nTableSize )
284 {
285 int nSize = pLim ? pLim - pStr : -1;
286 int i = 0; unsigned hash = 0;
287 while ( i != nSize && pStr[i] )
288 {
289 hash += pStr[i++];
290 hash += hash << 10;
291 hash ^= hash >> 6;
292 }
293 hash += hash << 3;
294 hash ^= hash >> 11;
295 hash += hash << 15;
296 return (int)(hash % nTableSize);
297 }
298
299 /**Function*************************************************************
300
301 Synopsis [Returns place where this string is, or should be.]
302
303 Description []
304
305 SideEffects []
306
307 SeeAlso []
308
309 ***********************************************************************/
Abc_NamStrcmp(char * pStr,char * pLim,char * pThis)310 static inline int Abc_NamStrcmp( char * pStr, char * pLim, char * pThis )
311 {
312 if ( pLim )
313 {
314 while ( pStr < pLim )
315 if ( *pStr++ != *pThis++ )
316 return 1;
317 return *pThis != '\0';
318 }
319 else
320 {
321 while ( *pStr )
322 if ( *pStr++ != *pThis++ )
323 return 1;
324 return *pThis != '\0';
325 }
326 }
Abc_NamStrHashFind(Abc_Nam_t * p,const char * pStr,const char * pLim)327 static inline int * Abc_NamStrHashFind( Abc_Nam_t * p, const char * pStr, const char * pLim )
328 {
329 char * pThis;
330 int * pPlace = (int *)(p->pBins + Abc_NamStrHash( pStr, pLim, p->nBins ));
331 assert( *pStr );
332 for ( pThis = (*pPlace)? Abc_NamIntToStr(p, *pPlace) : NULL;
333 pThis; pPlace = Abc_NamIntToNextP(p, *pPlace),
334 pThis = (*pPlace)? Abc_NamIntToStr(p, *pPlace) : NULL )
335 if ( !Abc_NamStrcmp( (char *)pStr, (char *)pLim, pThis ) )
336 break;
337 return pPlace;
338 }
339
340 /**Function*************************************************************
341
342 Synopsis [Resizes the hash table.]
343
344 Description []
345
346 SideEffects []
347
348 SeeAlso []
349
350 ***********************************************************************/
Abc_NamStrHashResize(Abc_Nam_t * p)351 void Abc_NamStrHashResize( Abc_Nam_t * p )
352 {
353 Vec_Int_t vInt2HandleOld; char * pThis;
354 int * piPlace, * pBinsOld, iHandleOld, i;//, clk = Abc_Clock();
355 assert( p->pBins != NULL );
356 // Abc_Print( 1, "Resizing names manager hash table from %6d to %6d. ", p->nBins, Abc_PrimeCudd( 3 * p->nBins ) );
357 // replace the table
358 pBinsOld = p->pBins;
359 p->nBins = Abc_PrimeCudd( 3 * p->nBins );
360 p->pBins = ABC_CALLOC( int, p->nBins );
361 // replace the handles array
362 vInt2HandleOld = p->vInt2Handle;
363 Vec_IntZero( &p->vInt2Handle );
364 Vec_IntGrow( &p->vInt2Handle, 2 * Vec_IntSize(&vInt2HandleOld) );
365 Vec_IntPush( &p->vInt2Handle, -1 );
366 Vec_IntClear( &p->vInt2Next ); Vec_IntPush( &p->vInt2Next, -1 );
367 // rehash the entries from the old table
368 Vec_IntForEachEntryStart( &vInt2HandleOld, iHandleOld, i, 1 )
369 {
370 pThis = Abc_NamHandleToStr( p, iHandleOld );
371 piPlace = Abc_NamStrHashFind( p, pThis, NULL );
372 assert( *piPlace == 0 );
373 *piPlace = Vec_IntSize( &p->vInt2Handle );
374 assert( Vec_IntSize( &p->vInt2Handle ) == i );
375 Vec_IntPush( &p->vInt2Handle, iHandleOld );
376 Vec_IntPush( &p->vInt2Next, 0 );
377 }
378 Vec_IntErase( &vInt2HandleOld );
379 ABC_FREE( pBinsOld );
380 // Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
381 }
382
383 /**Function*************************************************************
384
385 Synopsis [Returns the index of the string in the table.]
386
387 Description []
388
389 SideEffects []
390
391 SeeAlso []
392
393 ***********************************************************************/
Abc_NamStrFind(Abc_Nam_t * p,char * pStr)394 int Abc_NamStrFind( Abc_Nam_t * p, char * pStr )
395 {
396 return *Abc_NamStrHashFind( p, pStr, NULL );
397 }
Abc_NamStrFindLim(Abc_Nam_t * p,char * pStr,char * pLim)398 int Abc_NamStrFindLim( Abc_Nam_t * p, char * pStr, char * pLim )
399 {
400 return *Abc_NamStrHashFind( p, pStr, pLim );
401 }
402
403 /**Function*************************************************************
404
405 Synopsis [Finds or adds the given name to storage.]
406
407 Description []
408
409 SideEffects []
410
411 SeeAlso []
412
413 ***********************************************************************/
Abc_NamStrFindOrAdd(Abc_Nam_t * p,char * pStr,int * pfFound)414 int Abc_NamStrFindOrAdd( Abc_Nam_t * p, char * pStr, int * pfFound )
415 {
416 int i, iHandleNew;
417 int *piPlace;
418 if ( !(pStr[0] != '\\' || pStr[strlen(pStr)-1] == ' ') )
419 {
420 for ( i = strlen(pStr) - 1; i >= 0; i-- )
421 if ( *pStr == ' ' )
422 break;
423 assert( i < (int)strlen(pStr) );
424 }
425 piPlace = Abc_NamStrHashFind( p, pStr, NULL );
426 if ( *piPlace )
427 {
428 if ( pfFound )
429 *pfFound = 1;
430 return *piPlace;
431 }
432 if ( pfFound )
433 *pfFound = 0;
434 iHandleNew = p->iHandle + strlen(pStr) + 1;
435 while ( p->nStore < iHandleNew )
436 {
437 p->nStore *= 3;
438 p->nStore /= 2;
439 p->pStore = ABC_REALLOC( char, p->pStore, p->nStore );
440 }
441 assert( p->nStore >= iHandleNew );
442 // create new handle
443 *piPlace = Vec_IntSize( &p->vInt2Handle );
444 strcpy( Abc_NamHandleToStr( p, p->iHandle ), pStr );
445 Vec_IntPush( &p->vInt2Handle, p->iHandle );
446 Vec_IntPush( &p->vInt2Next, 0 );
447 p->iHandle = iHandleNew;
448 // extend the hash table
449 if ( Vec_IntSize(&p->vInt2Handle) > 2 * p->nBins )
450 Abc_NamStrHashResize( p );
451 return Vec_IntSize(&p->vInt2Handle) - 1;
452 }
Abc_NamStrFindOrAddLim(Abc_Nam_t * p,char * pStr,char * pLim,int * pfFound)453 int Abc_NamStrFindOrAddLim( Abc_Nam_t * p, char * pStr, char * pLim, int * pfFound )
454 {
455 int iHandleNew;
456 int *piPlace;
457 char * pStore;
458 assert( pStr < pLim );
459 piPlace = Abc_NamStrHashFind( p, pStr, pLim );
460 if ( *piPlace )
461 {
462 if ( pfFound )
463 *pfFound = 1;
464 return *piPlace;
465 }
466 if ( pfFound )
467 *pfFound = 0;
468 iHandleNew = p->iHandle + (pLim - pStr) + 1;
469 while ( p->nStore < iHandleNew )
470 {
471 p->nStore *= 3;
472 p->nStore /= 2;
473 p->pStore = ABC_REALLOC( char, p->pStore, p->nStore );
474 }
475 assert( p->nStore >= iHandleNew );
476 // create new handle
477 *piPlace = Vec_IntSize( &p->vInt2Handle );
478 pStore = Abc_NamHandleToStr( p, p->iHandle );
479 strncpy( pStore, pStr, pLim - pStr );
480 pStore[pLim - pStr] = 0;
481 Vec_IntPush( &p->vInt2Handle, p->iHandle );
482 Vec_IntPush( &p->vInt2Next, 0 );
483 p->iHandle = iHandleNew;
484 // extend the hash table
485 if ( Vec_IntSize(&p->vInt2Handle) > 2 * p->nBins )
486 Abc_NamStrHashResize( p );
487 return Vec_IntSize(&p->vInt2Handle) - 1;
488 }
Abc_NamStrFindOrAddF(Abc_Nam_t * p,const char * format,...)489 int Abc_NamStrFindOrAddF( Abc_Nam_t * p, const char * format, ... )
490 {
491 int nAdded, nSize = 1000;
492 va_list args; va_start( args, format );
493 Vec_StrGrow( &p->vBuffer, Vec_StrSize(&p->vBuffer) + nSize );
494 nAdded = vsnprintf( Vec_StrLimit(&p->vBuffer), nSize, format, args );
495 if ( nAdded > nSize )
496 {
497 Vec_StrGrow( &p->vBuffer, Vec_StrSize(&p->vBuffer) + nAdded + nSize );
498 nSize = vsnprintf( Vec_StrLimit(&p->vBuffer), nAdded, format, args );
499 assert( nSize == nAdded );
500 }
501 va_end( args );
502 return Abc_NamStrFindOrAddLim( p, Vec_StrLimit(&p->vBuffer), Vec_StrLimit(&p->vBuffer) + nAdded, NULL );
503 }
504
505 /**Function*************************************************************
506
507 Synopsis [Returns name from name ID.]
508
509 Description []
510
511 SideEffects []
512
513 SeeAlso []
514
515 ***********************************************************************/
Abc_NamStr(Abc_Nam_t * p,int NameId)516 char * Abc_NamStr( Abc_Nam_t * p, int NameId )
517 {
518 return NameId > 0 ? Abc_NamIntToStr(p, NameId) : NULL;
519 }
520
521 /**Function*************************************************************
522
523 Synopsis [Returns internal buffer.]
524
525 Description []
526
527 SideEffects []
528
529 SeeAlso []
530
531 ***********************************************************************/
Abc_NamBuffer(Abc_Nam_t * p)532 Vec_Str_t * Abc_NamBuffer( Abc_Nam_t * p )
533 {
534 Vec_StrClear(&p->vBuffer);
535 return &p->vBuffer;
536 }
537
538 /**Function*************************************************************
539
540 Synopsis [For each ID of the first manager, gives ID of the second one.]
541
542 Description []
543
544 SideEffects []
545
546 SeeAlso []
547
548 ***********************************************************************/
Abc_NamComputeIdMap(Abc_Nam_t * p1,Abc_Nam_t * p2)549 Vec_Int_t * Abc_NamComputeIdMap( Abc_Nam_t * p1, Abc_Nam_t * p2 )
550 {
551 Vec_Int_t * vMap;
552 char * pThis;
553 int * piPlace, iHandle1, i;
554 if ( p1 == p2 )
555 return Vec_IntStartNatural( Abc_NamObjNumMax(p1) );
556 vMap = Vec_IntStart( Abc_NamObjNumMax(p1) );
557 Vec_IntForEachEntryStart( &p1->vInt2Handle, iHandle1, i, 1 )
558 {
559 pThis = Abc_NamHandleToStr( p1, iHandle1 );
560 piPlace = Abc_NamStrHashFind( p2, pThis, NULL );
561 Vec_IntWriteEntry( vMap, i, *piPlace );
562 // Abc_Print( 1, "%d->%d ", i, *piPlace );
563 }
564 return vMap;
565 }
566
567 /**Function*************************************************************
568
569 Synopsis [Returns the number of common names in the array.]
570
571 Description [The array contains name IDs in the first manager.
572 The procedure returns the number of entries that correspond to names
573 in the first manager that appear in the second manager.]
574
575 SideEffects []
576
577 SeeAlso []
578
579 ***********************************************************************/
Abc_NamReportCommon(Vec_Int_t * vNameIds1,Abc_Nam_t * p1,Abc_Nam_t * p2)580 int Abc_NamReportCommon( Vec_Int_t * vNameIds1, Abc_Nam_t * p1, Abc_Nam_t * p2 )
581 {
582 int i, Entry, Counter = 0;
583 Vec_IntForEachEntry( vNameIds1, Entry, i )
584 {
585 assert( Entry > 0 && Entry < Abc_NamObjNumMax(p1) );
586 Counter += (Abc_NamStrFind(p2, Abc_NamStr(p1, Entry)) > 0);
587 // if ( Abc_NamStrFind(p2, Abc_NamStr(p1, Entry)) == 0 )
588 // Abc_Print( 1, "unique name <%s>\n", Abc_NamStr(p1, Entry) );
589 }
590 return Counter;
591 }
592
593 /**Function*************************************************************
594
595 Synopsis [Returns the name that appears in p1 does not appear in p2.]
596
597 Description []
598
599 SideEffects []
600
601 SeeAlso []
602
603 ***********************************************************************/
Abc_NamReportUnique(Vec_Int_t * vNameIds1,Abc_Nam_t * p1,Abc_Nam_t * p2)604 char * Abc_NamReportUnique( Vec_Int_t * vNameIds1, Abc_Nam_t * p1, Abc_Nam_t * p2 )
605 {
606 int i, Entry;
607 Vec_IntForEachEntry( vNameIds1, Entry, i )
608 {
609 assert( Entry > 0 && Entry < Abc_NamObjNumMax(p1) );
610 if ( Abc_NamStrFind(p2, Abc_NamStr(p1, Entry)) == 0 )
611 return Abc_NamStr(p1, Entry);
612 }
613 return NULL;
614 }
615
616 ////////////////////////////////////////////////////////////////////////
617 /// END OF FILE ///
618 ////////////////////////////////////////////////////////////////////////
619
620
621 ABC_NAMESPACE_IMPL_END
622
623