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