1
2 // -*- C++ -*-
3 //
4 // $Id: MPri.cpp,v 1.5 2002/10/29 18:46:03 jpc Exp $
5 //
6 // +----------------------------------------------------------------+
7 // | A l l i a n c e C A D S y s t e m |
8 // | S i m p l e R o u t e r |
9 // | |
10 // | Author : Jean-Paul CHAPUT |
11 // | E-mail : alliance-support@asim.lip6.fr |
12 // | ============================================================== |
13 // | C++ Module : "./MPri.cpp" |
14 // +----------------------------------------------------------------+
15
16
17
18
19 # include "MDefs.h"
20
21
22
23
24 // +----------------------------------------------------------------+
25 // | Methods Definitions |
26 // +----------------------------------------------------------------+
27
28
29 // -------------------------------------------------------------------
30 // Method : "CMatrixPri::findfree()".
31
findfree(int index,CNet & net)32 void CMatrixPri::findfree (int index, CNet &net)
33 {
34 CDRGrid::iterator coord;
35 int radius, i, j, cx, cy;
36 bool freed;
37 CNet *other;
38
39
40 freed = false;
41 radius = 0;
42 cx = _drgrid->x(index);
43 cy = _drgrid->y(index);
44 coord = _drgrid->origin;
45
46 // Check for blocked upper nodes.
47 other = (*_drgrid->nodes)[index].data.owner;
48
49 if ( ! (*_drgrid->nodes)[index].data.obstacle
50 && ((other == NULL) || (other == &net)) )
51 return;
52
53 cdebug << "Looking for an escape!\n" << "\n";
54
55 while (!freed) {
56 radius += 1;
57
58 for (i = cx - radius; i < cx + radius + 1; i++) {
59 for (j = cy - radius; j < cy + radius + 1; j++) {
60 // Proccess only nodes of the ring.
61 // if ( (i > cx - radius) || (i < cx + radius) ) continue;
62 // if ( (j > cy - radius) || (j < cy + radius) ) continue;
63
64 coord.set (i,j,2);
65
66 // Check if we are outside.
67 if (coord.outside()) continue;
68
69 other = (*_drgrid->nodes)[coord].data.owner;
70 if ( ( ! (*_drgrid->nodes)[coord].data.obstacle )
71 && ((other == NULL) || (other == &net)) ) {
72 if (!freed)
73 cdebug << "Escape found at " << coord << "\n";
74
75 freed = true;
76 }
77
78 (*this)[ coord.set(i,j,1) ] = (char)1;
79 (*this)[ coord.set(i,j,2) ] = (char)1;
80 }
81 }
82 }
83
84 cdebug << "Escape radius := " << radius << "\n";
85 }
86
87
88
89
90 // -------------------------------------------------------------------
91 // Method : "CMatrixPri::clear()".
92
clear(void)93 void CMatrixPri::clear (void)
94 {
95 memset (_grid, (char)0, (size_t)(_drgrid->size));
96
97 cleared = true;
98 offset = 0;
99 delta = 0;
100 }
101
102
103
104
105 // -------------------------------------------------------------------
106 // Method : "CMatrixPri::nextPri()".
107
nextPri(char curpri)108 char CMatrixPri::nextPri (char curpri)
109 {
110 return ((curpri > 1) ? (curpri >> 1) : 1);
111 }
112
113
114
115
116 // -------------------------------------------------------------------
117 // Method : "CMatrixPri::load()".
118
load(CNet & net,bool global,int expand)119 void CMatrixPri::load (CNet &net, bool global, int expand)
120 {
121 list<CDRGrid::iterator>::iterator itNode, beginNode, endNode;
122 queue<CDRGrid::iterator*> queue1, queue2;
123 queue<CDRGrid::iterator*> *currentBorder, *nextBorder;
124 CDRGrid::iterator *pCoord, coord;
125
126 char currentPri, *pmap;
127 int x, y, z, nx, ny, nz, edge, id, ex, ey;
128 bool breakLoop;
129
130
131 clear ();
132
133 offset = net.pri;
134 delta = 0;
135
136 currentBorder = &queue1;
137 nextBorder = &queue2;
138 currentPri = 64;
139
140
141 // Expand the original BB if too small.
142 ex = 0;
143 ey = 0;
144
145 if (net.bb.x2 - net.bb.x1 < 5) ex = 5;
146 if (net.bb.y2 - net.bb.y1 < 5) ey = 5;
147
148 if (expand) ex = ey = expand;
149
150 _bb.x1 = max (0 , net.bb.x1 - ex);
151 _bb.x2 = min (_drgrid->X - 1, net.bb.x2 + ex);
152 _bb.y1 = max (0 , net.bb.y1 - ey);
153 _bb.y2 = min (_drgrid->Y - 1, net.bb.y2 + ey);
154
155
156 // Build the initials border lists : coordinates of the terminals.
157 // The table doesn't have a z = 0 layer (never used for routing),
158 // so when a terminal on layer 0 is encountered, we queue the
159 // the coordinate on top in the next border queue.
160 // That is, in the first step of the algorithm we fill both queue
161 // at the same time.
162 // In the case of the map of a global signal (i.e. using z=3&4 for
163 // the time beeing, set to one the map points above the terminal
164 // in z=1&2, as they will not be set by the _bb loop.
165
166 for (id = 0; id < net.size; id++) {
167 beginNode = (net.terms[id])->nodes.begin ();
168 endNode = (net.terms[id])->nodes.end ();
169
170 for (itNode = beginNode; itNode != endNode; itNode++) {
171 coord = *itNode;
172
173 // Initial queues filling.
174 if (coord.z() > 0) {
175 (*this)[ coord ] = currentPri;
176 currentBorder->push (new CDRGrid::iterator (coord));
177
178 // Enable z=1 (in case of global signal, no effet otherwise).
179 if (coord.z() < _drgrid->Z - 1) (*this)[ coord.dz(1) ] = (char)1;
180
181 if (global) findfree (coord, net);
182
183 continue;
184 }
185
186 (*this)[ coord.dz(1) ] = nextPri (currentPri);
187 nextBorder->push (new CDRGrid::iterator (coord));
188
189 if (global) findfree (coord, net);
190
191 // Enable z=2 (in case of global signal, no effet otherwise).
192 (*this)[ coord.dz(1) ] = (char)1;
193
194 // Look if the upper node is blocked, in that case expand the
195 // allowed zone till a non-blocked node is found.
196 if (global) findfree (coord, net);
197 }
198 }
199
200
201 // Set to one all the points inside the enclosing box.
202 // (except those in the initial queues)
203 cdebug << _bb << "\n";
204 for (x = _bb.x1; x <= _bb.x2; x++) {
205 for (y = _bb.y1; y <= _bb.y2; y++) {
206 for (z = (global) ? 3 : 1; z < _drgrid->Z; z++) {
207 pmap = & ( (*this)[ coord.set (x, y, z) ] );
208 if (pmap && (!(*pmap))) *pmap = (char)1;
209 }
210 }
211 }
212
213
214 breakLoop = false;
215 currentPri = nextPri (currentPri);
216
217 // And here we go!
218 while (true) {
219 // Checks if the current border is finished. If so swap it with the
220 // nextBorder. If the current border is still empty, we are done.
221 if (currentBorder->empty ()) {
222 currentPri = nextPri (currentPri);
223 swap (currentBorder, nextBorder);
224
225 if (currentBorder->empty ()) {
226 breakLoop = true;
227 }
228 }
229 if (breakLoop) break;
230
231 pCoord = currentBorder->front ();
232 currentBorder->pop ();
233
234 x = pCoord->x ();
235 y = pCoord->y ();
236 z = pCoord->z ();
237
238 delete pCoord;
239
240 for (edge = 0; edge < 6; edge++) {
241 nx = x; ny = y; nz =z;
242
243 // Look at all six neighbors.
244 switch (edge) {
245 case 0: nx -= 1; break;
246 case 1: nx += 1; break;
247 case 2: ny -= 1; break;
248 case 3: ny += 1; break;
249 case 4: nz -= 1; break;
250 case 5: nz += 1; break;
251 }
252
253 pmap = & ( (*this)[ coord.set (nx, ny, nz) ] );
254 if (pmap == &(this->hole)) { continue; }
255
256 // Usable nodes have been set to at least one, if not skip it.
257 if ( (pmap == NULL) || (*pmap == (char)0) ) continue;
258
259 if (*pmap == (char)1) {
260 *pmap = currentPri;
261 // Push only nodes that are not of minimal priority.
262 if (currentPri > (char)1)
263 nextBorder->push (new CDRGrid::iterator (coord));
264 }
265 }
266
267 }
268
269
270 cleared = false;
271 }
272
273
274
275
276 // -------------------------------------------------------------------
277 // Method : "CMatrixPri::take()".
278
take(int pri,int index)279 bool CMatrixPri::take (int pri, int index)
280 {
281 char *mappri;
282
283
284 mappri = &(*this)[index];
285
286 if (mappri == &hole) return (false);
287 if (!*mappri) return (false);
288 if (!pri) return (true);
289
290 return (pri + 256 < *mappri + delta);
291 }
292
293
294
295
296 // -------------------------------------------------------------------
297 // Friend : "&operator<<()".
298
operator <<(ostream & o,CMatrixPri & self)299 ostream &operator<< (ostream &o, CMatrixPri &self)
300 {
301 CDRGrid::iterator coord;
302 int x, y, z;
303
304 o << "cleared := " << self.cleared << "\n"
305 << "offset := " << self.offset << "\n"
306 << "delta := " << self.delta << "\n";
307
308 coord = self._drgrid->origin;
309
310 for (z = 1; z < self._drgrid->Z; z++) {
311 o << " (layer) z := " << z << "\n";
312
313 for (y = 1; y <= self._drgrid->Y; y++) {
314 o << " ";
315 for (x = 0; x < self._drgrid->X; x++) {
316 o << setw(5) << (int)(self[
317 coord.set (x, self._drgrid->Y - y, z)]);
318 }
319 o << "\n";
320 }
321 }
322
323 return (o);
324 }
325