1 /**CFile****************************************************************
2 Copyright (c) The Regents of the University of California. All rights reserved.
3
4 Permission is hereby granted, without written agreement and without license or
5 royalty fees, to use, copy, modify, and distribute this software and its
6 documentation for any purpose, provided that the above copyright notice and
7 the following two paragraphs appear in all copies of this software.
8
9 IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
10 DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF
11 THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
12 CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
13
14 THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
15 BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
16 A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS,
17 AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE,
18 SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
19
20
21 FileName [vecVec.h]
22
23 SystemName [ABC: Logic synthesis and verification system.]
24
25 PackageName [Resizable arrays.]
26
27 Synopsis [Resizable vector of resizable vectors.]
28
29 Author [Alan Mishchenko]
30
31 Affiliation [UC Berkeley]
32
33 Date [Ver. 1.0. Started - June 20, 2005.]
34
35 Revision [$Id: vecVec.h,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
36
37 ***********************************************************************/
38
39 #ifndef __VEC_VEC_H__
40 #define __VEC_VEC_H__
41
42 ////////////////////////////////////////////////////////////////////////
43 /// INCLUDES ///
44 ////////////////////////////////////////////////////////////////////////
45
46 #include <stdio.h>
47
48 ////////////////////////////////////////////////////////////////////////
49 /// PARAMETERS ///
50 ////////////////////////////////////////////////////////////////////////
51
52 ////////////////////////////////////////////////////////////////////////
53 /// BASIC TYPES ///
54 ////////////////////////////////////////////////////////////////////////
55
56 typedef struct Vec_Vec_t_ Vec_Vec_t;
57 struct Vec_Vec_t_
58 {
59 int nCap;
60 int nSize;
61 void ** pArray;
62 };
63
64 ////////////////////////////////////////////////////////////////////////
65 /// MACRO DEFINITIONS ///
66 ////////////////////////////////////////////////////////////////////////
67
68 // iterators through levels
69 #define Vec_VecForEachLevel( vGlob, vVec, i ) \
70 for ( i = 0; (i < Vec_VecSize(vGlob)) && (((vVec) = (Vec_Ptr_t*)Vec_VecEntry(vGlob, i)), 1); i++ )
71 #define Vec_VecForEachLevelStart( vGlob, vVec, i, LevelStart ) \
72 for ( i = LevelStart; (i < Vec_VecSize(vGlob)) && (((vVec) = (Vec_Ptr_t*)Vec_VecEntry(vGlob, i)), 1); i++ )
73 #define Vec_VecForEachLevelStartStop( vGlob, vVec, i, LevelStart, LevelStop ) \
74 for ( i = LevelStart; (i <= LevelStop) && (((vVec) = (Vec_Ptr_t*)Vec_VecEntry(vGlob, i)), 1); i++ )
75 #define Vec_VecForEachLevelReverse( vGlob, vVec, i ) \
76 for ( i = Vec_VecSize(vGlob) - 1; (i >= 0) && (((vVec) = (Vec_Ptr_t*)Vec_VecEntry(vGlob, i)), 1); i-- )
77 #define Vec_VecForEachLevelReverseStartStop( vGlob, vVec, i, LevelStart, LevelStop ) \
78 for ( i = LevelStart; (i >= LevelStop) && (((vVec) = (Vec_Ptr_t*)Vec_VecEntry(vGlob, i)), 1); i-- )
79
80 // iteratores through entries
81 #define Vec_VecForEachEntry( vGlob, pEntry, i, k ) \
82 for ( i = 0; i < Vec_VecSize(vGlob); i++ ) \
83 Vec_PtrForEachEntry( Vec_VecEntry(vGlob, i), pEntry, k )
84 #define Vec_VecForEachEntryLevel( vGlob, pEntry, i, Level ) \
85 Vec_PtrForEachEntry( Vec_VecEntry(vGlob, Level), pEntry, i )
86 #define Vec_VecForEachEntryStart( vGlob, pEntry, i, k, LevelStart ) \
87 for ( i = LevelStart; i < Vec_VecSize(vGlob); i++ ) \
88 Vec_PtrForEachEntry( Vec_VecEntry(vGlob, i), pEntry, k )
89 #define Vec_VecForEachEntryStartStop( vGlob, pEntry, i, k, LevelStart, LevelStop ) \
90 for ( i = LevelStart; i <= LevelStop; i++ ) \
91 Vec_PtrForEachEntry( Vec_VecEntry(vGlob, i), pEntry, k )
92 #define Vec_VecForEachEntryReverse( vGlob, pEntry, i, k ) \
93 for ( i = 0; i < Vec_VecSize(vGlob); i++ ) \
94 Vec_PtrForEachEntryReverse( Vec_VecEntry(vGlob, i), pEntry, k )
95 #define Vec_VecForEachEntryReverseReverse( vGlob, pEntry, i, k ) \
96 for ( i = Vec_VecSize(vGlob) - 1; i >= 0; i-- ) \
97 Vec_PtrForEachEntryReverse( Vec_VecEntry(vGlob, i), pEntry, k )
98 #define Vec_VecForEachEntryReverseStart( vGlob, pEntry, i, k, LevelStart ) \
99 for ( i = LevelStart; i >= 0; i-- ) \
100 Vec_PtrForEachEntry( Vec_VecEntry(vGlob, i), pEntry, k )
101
102 ////////////////////////////////////////////////////////////////////////
103 /// FUNCTION DEFINITIONS ///
104 ////////////////////////////////////////////////////////////////////////
105
106 /**Function*************************************************************
107
108 Synopsis [Allocates a vector with the given capacity.]
109
110 Description []
111
112 SideEffects []
113
114 SeeAlso []
115
116 ***********************************************************************/
Vec_VecAlloc(int nCap)117 static inline Vec_Vec_t * Vec_VecAlloc( int nCap )
118 {
119 Vec_Vec_t * p;
120 p = ALLOC( Vec_Vec_t, 1 );
121 if ( nCap > 0 && nCap < 8 )
122 nCap = 8;
123 p->nSize = 0;
124 p->nCap = nCap;
125 p->pArray = p->nCap? ALLOC( void *, p->nCap ) : NULL;
126 return p;
127 }
128
129 /**Function*************************************************************
130
131 Synopsis [Allocates a vector with the given capacity.]
132
133 Description []
134
135 SideEffects []
136
137 SeeAlso []
138
139 ***********************************************************************/
Vec_VecStart(int nSize)140 static inline Vec_Vec_t * Vec_VecStart( int nSize )
141 {
142 Vec_Vec_t * p;
143 int i;
144 p = Vec_VecAlloc( nSize );
145 for ( i = 0; i < nSize; i++ )
146 p->pArray[i] = Vec_PtrAlloc( 0 );
147 p->nSize = nSize;
148 return p;
149 }
150
151 /**Function*************************************************************
152
153 Synopsis [Allocates a vector with the given capacity.]
154
155 Description []
156
157 SideEffects []
158
159 SeeAlso []
160
161 ***********************************************************************/
Vec_VecExpand(Vec_Vec_t * p,int Level)162 static inline void Vec_VecExpand( Vec_Vec_t * p, int Level )
163 {
164 int i;
165 if ( p->nSize >= Level + 1 )
166 return;
167 Vec_PtrGrow( (Vec_Ptr_t *)p, Level + 1 );
168 for ( i = p->nSize; i <= Level; i++ )
169 p->pArray[i] = Vec_PtrAlloc( 0 );
170 p->nSize = Level + 1;
171 }
172
173 /**Function*************************************************************
174
175 Synopsis []
176
177 Description []
178
179 SideEffects []
180
181 SeeAlso []
182
183 ***********************************************************************/
Vec_VecSize(Vec_Vec_t * p)184 static inline int Vec_VecSize( Vec_Vec_t * p )
185 {
186 return p->nSize;
187 }
188
189 /**Function*************************************************************
190
191 Synopsis []
192
193 Description []
194
195 SideEffects []
196
197 SeeAlso []
198
199 ***********************************************************************/
Vec_VecEntry(Vec_Vec_t * p,int i)200 static inline void * Vec_VecEntry( Vec_Vec_t * p, int i )
201 {
202 assert( i >= 0 && i < p->nSize );
203 return p->pArray[i];
204 }
205
206 /**Function*************************************************************
207
208 Synopsis [Frees the vector.]
209
210 Description []
211
212 SideEffects []
213
214 SeeAlso []
215
216 ***********************************************************************/
Vec_VecFree(Vec_Vec_t * p)217 static inline void Vec_VecFree( Vec_Vec_t * p )
218 {
219 Vec_Ptr_t * vVec;
220 int i;
221 Vec_VecForEachLevel( p, vVec, i )
222 Vec_PtrFree( vVec );
223 Vec_PtrFree( (Vec_Ptr_t *)p );
224 }
225
226 /**Function*************************************************************
227
228 Synopsis [Frees the vector of vectors.]
229
230 Description []
231
232 SideEffects []
233
234 SeeAlso []
235
236 ***********************************************************************/
Vec_VecSizeSize(Vec_Vec_t * p)237 static inline int Vec_VecSizeSize( Vec_Vec_t * p )
238 {
239 Vec_Ptr_t * vVec;
240 int i, Counter = 0;
241 Vec_VecForEachLevel( p, vVec, i )
242 Counter += vVec->nSize;
243 return Counter;
244 }
245
246 /**Function*************************************************************
247
248 Synopsis []
249
250 Description []
251
252 SideEffects []
253
254 SeeAlso []
255
256 ***********************************************************************/
Vec_VecClear(Vec_Vec_t * p)257 static inline void Vec_VecClear( Vec_Vec_t * p )
258 {
259 Vec_Ptr_t * vVec;
260 int i;
261 Vec_VecForEachLevel( p, vVec, i )
262 Vec_PtrClear( vVec );
263 }
264
265 /**Function*************************************************************
266
267 Synopsis []
268
269 Description []
270
271 SideEffects []
272
273 SeeAlso []
274
275 ***********************************************************************/
Vec_VecPush(Vec_Vec_t * p,int Level,void * Entry)276 static inline void Vec_VecPush( Vec_Vec_t * p, int Level, void * Entry )
277 {
278 if ( p->nSize < Level + 1 )
279 {
280 int i;
281 Vec_PtrGrow( (Vec_Ptr_t *)p, Level + 1 );
282 for ( i = p->nSize; i < Level + 1; i++ )
283 p->pArray[i] = Vec_PtrAlloc( 0 );
284 p->nSize = Level + 1;
285 }
286 Vec_PtrPush( (Vec_Ptr_t*)p->pArray[Level], Entry );
287 }
288
289 /**Function*************************************************************
290
291 Synopsis []
292
293 Description []
294
295 SideEffects []
296
297 SeeAlso []
298
299 ***********************************************************************/
Vec_VecPushUnique(Vec_Vec_t * p,int Level,void * Entry)300 static inline void Vec_VecPushUnique( Vec_Vec_t * p, int Level, void * Entry )
301 {
302 if ( p->nSize < Level + 1 )
303 Vec_VecPush( p, Level, Entry );
304 else
305 Vec_PtrPushUnique( (Vec_Ptr_t*)p->pArray[Level], Entry );
306 }
307
308 /**Function*************************************************************
309
310 Synopsis [Comparison procedure for two arrays.]
311
312 Description []
313
314 SideEffects []
315
316 SeeAlso []
317
318 ***********************************************************************/
Vec_VecSortCompare1(Vec_Ptr_t ** pp1,Vec_Ptr_t ** pp2)319 static inline int Vec_VecSortCompare1( Vec_Ptr_t ** pp1, Vec_Ptr_t ** pp2 )
320 {
321 if ( Vec_PtrSize(*pp1) < Vec_PtrSize(*pp2) )
322 return -1;
323 if ( Vec_PtrSize(*pp1) > Vec_PtrSize(*pp2) )
324 return 1;
325 return 0;
326 }
327
328 /**Function*************************************************************
329
330 Synopsis [Comparison procedure for two integers.]
331
332 Description []
333
334 SideEffects []
335
336 SeeAlso []
337
338 ***********************************************************************/
Vec_VecSortCompare2(Vec_Ptr_t ** pp1,Vec_Ptr_t ** pp2)339 static inline int Vec_VecSortCompare2( Vec_Ptr_t ** pp1, Vec_Ptr_t ** pp2 )
340 {
341 if ( Vec_PtrSize(*pp1) > Vec_PtrSize(*pp2) )
342 return -1;
343 if ( Vec_PtrSize(*pp1) < Vec_PtrSize(*pp2) )
344 return 1;
345 return 0;
346 }
347
348 /**Function*************************************************************
349
350 Synopsis [Sorting the entries by their integer value.]
351
352 Description []
353
354 SideEffects []
355
356 SeeAlso []
357
358 ***********************************************************************/
Vec_VecSort(Vec_Vec_t * p,int fReverse)359 static inline void Vec_VecSort( Vec_Vec_t * p, int fReverse )
360 {
361 if ( fReverse )
362 qsort( (void *)p->pArray, p->nSize, sizeof(void *),
363 (int (*)(const void *, const void *)) Vec_VecSortCompare2 );
364 else
365 qsort( (void *)p->pArray, p->nSize, sizeof(void *),
366 (int (*)(const void *, const void *)) Vec_VecSortCompare1 );
367 }
368
369 #endif
370
371 ////////////////////////////////////////////////////////////////////////
372 /// END OF FILE ///
373 ////////////////////////////////////////////////////////////////////////
374
375