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    [aigOrder.c]
22 
23   SystemName  [ABC: Logic synthesis and verification system.]
24 
25   PackageName [AIG package.]
26 
27   Synopsis    [Dynamically updated topological order.]
28 
29   Author      [Alan Mishchenko]
30 
31   Affiliation [UC Berkeley]
32 
33   Date        [Ver. 1.0. Started - April 28, 2007.]
34 
35   Revision    [$Id: aigOrder.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $]
36 
37 ***********************************************************************/
38 
39 #include "aig.h"
40 
41 ////////////////////////////////////////////////////////////////////////
42 ///                        DECLARATIONS                              ///
43 ////////////////////////////////////////////////////////////////////////
44 
45 ////////////////////////////////////////////////////////////////////////
46 ///                     FUNCTION DEFINITIONS                         ///
47 ////////////////////////////////////////////////////////////////////////
48 
49 /**Function*************************************************************
50 
51   Synopsis    [Initializes the order datastructure.]
52 
53   Description []
54 
55   SideEffects []
56 
57   SeeAlso     []
58 
59 ***********************************************************************/
Aig_ManOrderStart(Aig_Man_t * p)60 void Aig_ManOrderStart( Aig_Man_t * p )
61 {
62     Aig_Obj_t * pObj;
63     int i;
64     assert( Aig_ManBufNum(p) == 0 );
65     // allocate order datastructure
66     assert( p->pOrderData == NULL );
67     p->nOrderAlloc = 2 * Aig_ManObjNumMax(p);
68     if ( p->nOrderAlloc < (1<<12) )
69         p->nOrderAlloc = (1<<12);
70     p->pOrderData = ALLOC( unsigned, 2 * p->nOrderAlloc );
71     memset( p->pOrderData, 0xFF, sizeof(unsigned) * 2 * p->nOrderAlloc );
72     // add the constant node
73     p->pOrderData[0] = p->pOrderData[1] = 0;
74     p->iPrev = p->iNext = 0;
75     // add the internal nodes
76     Aig_ManForEachNode( p, pObj, i )
77         Aig_ObjOrderInsert( p, pObj->Id );
78 }
79 
80 /**Function*************************************************************
81 
82   Synopsis    [Deletes the order datastructure.]
83 
84   Description []
85 
86   SideEffects []
87 
88   SeeAlso     []
89 
90 ***********************************************************************/
Aig_ManOrderStop(Aig_Man_t * p)91 void Aig_ManOrderStop( Aig_Man_t * p )
92 {
93     assert( p->pOrderData );
94     FREE( p->pOrderData );
95     p->nOrderAlloc = 0;
96     p->iPrev = p->iNext = 0;
97 }
98 
99 /**Function*************************************************************
100 
101   Synopsis    [Inserts an entry before iNext.]
102 
103   Description []
104 
105   SideEffects []
106 
107   SeeAlso     []
108 
109 ***********************************************************************/
Aig_ObjOrderInsert(Aig_Man_t * p,int ObjId)110 void Aig_ObjOrderInsert( Aig_Man_t * p, int ObjId )
111 {
112     int iPrev;
113     assert( ObjId != 0 );
114     assert( Aig_ObjIsNode( Aig_ManObj(p, ObjId) ) );
115     if ( ObjId >= p->nOrderAlloc )
116     {
117         int nOrderAlloc = 2 * ObjId;
118         p->pOrderData = REALLOC( unsigned, p->pOrderData, 2 * nOrderAlloc );
119         memset( p->pOrderData + 2 * p->nOrderAlloc, 0xFF, sizeof(unsigned) * 2 * (nOrderAlloc - p->nOrderAlloc) );
120         p->nOrderAlloc = nOrderAlloc;
121     }
122     assert( p->pOrderData[2*ObjId] == 0xFFFFFFFF );   // prev
123     assert( p->pOrderData[2*ObjId+1] == 0xFFFFFFFF ); // next
124     iPrev = p->pOrderData[2*p->iNext];
125     assert( p->pOrderData[2*iPrev+1] == (unsigned)p->iNext );
126     p->pOrderData[2*ObjId] = iPrev;
127     p->pOrderData[2*iPrev+1] = ObjId;
128     p->pOrderData[2*p->iNext] = ObjId;
129     p->pOrderData[2*ObjId+1] = p->iNext;
130     p->nAndTotal++;
131 }
132 
133 /**Function*************************************************************
134 
135   Synopsis    [Removes the entry.]
136 
137   Description [If iPrev is removed, it slides backward.
138   If iNext is removed, it slides forward.]
139 
140   SideEffects []
141 
142   SeeAlso     []
143 
144 ***********************************************************************/
Aig_ObjOrderRemove(Aig_Man_t * p,int ObjId)145 void Aig_ObjOrderRemove( Aig_Man_t * p, int ObjId )
146 {
147     int iPrev, iNext;
148     assert( ObjId != 0 );
149     assert( Aig_ObjIsNode( Aig_ManObj(p, ObjId) ) );
150     iPrev = p->pOrderData[2*ObjId];
151     iNext = p->pOrderData[2*ObjId+1];
152     p->pOrderData[2*ObjId] = 0xFFFFFFFF;
153     p->pOrderData[2*ObjId+1] = 0xFFFFFFFF;
154     p->pOrderData[2*iNext] = iPrev;
155     p->pOrderData[2*iPrev+1] = iNext;
156     if ( p->iPrev == ObjId )
157     {
158         p->nAndPrev--;
159         p->iPrev = iPrev;
160     }
161     if ( p->iNext == ObjId )
162         p->iNext = iNext;
163     p->nAndTotal--;
164 }
165 
166 /**Function*************************************************************
167 
168   Synopsis    [Advances the order forward.]
169 
170   Description []
171 
172   SideEffects []
173 
174   SeeAlso     []
175 
176 ***********************************************************************/
Aig_ObjOrderAdvance(Aig_Man_t * p)177 void Aig_ObjOrderAdvance( Aig_Man_t * p )
178 {
179     assert( p->pOrderData );
180     assert( p->pOrderData[2*p->iPrev+1] == (unsigned)p->iNext );
181     p->iPrev = p->iNext;
182     p->nAndPrev++;
183 }
184 
185 ////////////////////////////////////////////////////////////////////////
186 ///                       END OF FILE                                ///
187 ////////////////////////////////////////////////////////////////////////
188 
189 
190