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