| #include "geo.h" |
| #define DEBUG |
| |
| extern int tprop( TNODEPTR r , int value ); |
| extern void tinsert( TNODEPTR *root , int value , int property ); |
| |
| void doubleDown( DLINK1PTR rptr ); |
| |
| void vprobes(void) |
| { |
| |
| DLINK1PTR ritePtr , left1ptr , left2ptr , checkPtr , ptr ; |
| int ry , rx1 , rx2 , redge , dx1 , dx2 , ledge , edge , check ; |
| int l1x2 , l1x1 , l1y , l2x2 , l2x1 , l2y ; |
| |
| ritePtr = hFixedList ; |
| for( ; ritePtr != (DLINK1PTR) NULL ; ritePtr = ritePtr->next ) { |
| redge = ritePtr->edge ; |
| if( edgeList[redge].UorR < 0 ) { |
| continue ; |
| } |
| ry = edgeList[redge].loc ; |
| rx1 = edgeList[redge].start ; |
| rx2 = edgeList[redge].end ; |
| |
| if( edgeList[ edgeList[redge].prevEdge ].UorR == 1 ) { |
| left1ptr = Hptrs[ tprop( Hroot , ry ) ] ; |
| for(; left1ptr != (DLINK1PTR)NULL; left1ptr = left1ptr->next){ |
| ledge = left1ptr->edge ; |
| if( edgeList[ledge].UorR > 0 ) { |
| continue ; |
| } |
| l1y = edgeList[ledge].loc ; |
| l1x1 = edgeList[ledge].start ; |
| l1x2 = edgeList[ledge].end ; |
| if( l1x2 <= rx1 || l1x1 > rx1 ) { |
| continue ; |
| } |
| break ; |
| } |
| } else { |
| left1ptr = (DLINK1PTR) NULL ; |
| } |
| if( edgeList[ edgeList[redge].nextEdge ].UorR == -1 ) { |
| left2ptr = Hptrs[ tprop( Hroot , ry ) ] ; |
| for(; left2ptr != (DLINK1PTR) NULL ; left2ptr = left2ptr->next){ |
| ledge = left2ptr->edge ; |
| if( edgeList[ledge].UorR > 0 ) { |
| continue ; |
| } |
| l2y = edgeList[ledge].loc ; |
| l2x1 = edgeList[ledge].start ; |
| l2x2 = edgeList[ledge].end ; |
| if( l2x2 < rx2 || l2x1 >= rx2 ) { |
| continue ; |
| } |
| break ; |
| } |
| } else { |
| left2ptr = (DLINK1PTR) NULL ; |
| } |
| if( left1ptr != (DLINK1PTR) NULL && left1ptr == left2ptr ) { |
| check = 1 ; |
| checkPtr = Hptrs[ tprop( Hroot , ry ) ] ; |
| for(; checkPtr != (DLINK1PTR)NULL; checkPtr = checkPtr->next){ |
| if( edgeList[ checkPtr->edge ].UorR > 0 ) { |
| continue ; |
| } |
| if( edgeList[ checkPtr->edge ].loc >= l2y ) { |
| break ; |
| } |
| if( edgeList[ checkPtr->edge ].start >= rx2 || |
| edgeList[ checkPtr->edge ].end <= rx1 ) { |
| continue ; |
| } |
| check = 0 ; |
| break ; |
| } |
| if( check ) { |
| edgeList[++numProbes + edgeCount].start = ry ; |
| edgeList[numProbes + edgeCount].end = l2y ; |
| edgeList[numProbes + edgeCount].loc = rx1 ; |
| edgeList[numProbes + edgeCount].length = l2y - ry ; |
| edgeList[numProbes + edgeCount].fixed = 0 ; |
| edgeList[numProbes + edgeCount].cell = 0 ; |
| edgeList[numProbes + edgeCount].UorR = 1 ; |
| tinsert( &vEdgeRoot, rx1 , numProbes + edgeCount ) ; |
| #ifdef DEBUG |
| fprintf(fpdebug,"vprobe:%d ", numProbes ) ; |
| fprintf(fpdebug,"start:%d end:%d loc:%d UorR:%d\n", |
| ry , l2y , rx1 , 1 ) ; |
| #endif |
| edgeList[++numProbes + edgeCount].start = ry ; |
| edgeList[numProbes + edgeCount].end = l2y ; |
| edgeList[numProbes + edgeCount].loc = rx2 ; |
| edgeList[numProbes + edgeCount].length = l2y - ry ; |
| edgeList[numProbes + edgeCount].fixed = 0 ; |
| edgeList[numProbes + edgeCount].cell = 0 ; |
| edgeList[numProbes + edgeCount].UorR = -1 ; |
| tinsert( &vEdgeRoot, rx2 , numProbes + edgeCount ) ; |
| #ifdef DEBUG |
| fprintf(fpdebug,"vprobe:%d ", numProbes ) ; |
| fprintf(fpdebug,"start:%d end:%d loc:%d UorR:%d\n", |
| ry , l2y , rx2 , -1 ) ; |
| #endif |
| } else { |
| doubleDown( ritePtr ) ; |
| } |
| continue ; |
| } |
| if( left1ptr != (DLINK1PTR) NULL && |
| edgeList[ edgeList[left1ptr->edge].prevEdge ].UorR == -1 ) { |
| ptr = Hptrs[ tprop( Hroot , l1y ) ] ; |
| for( ptr = ptr->next; ptr != (DLINK1PTR) NULL; ptr = ptr->next){ |
| if( edgeList[ptr->edge].loc > l1y ) { |
| break ; |
| } |
| } |
| if( ptr == (DLINK1PTR) NULL ) { |
| ptr = hFixedEnd ; |
| } else { |
| ptr = ptr->prev ; |
| } |
| for( ; ptr != (DLINK1PTR) NULL; ptr = ptr->prev){ |
| edge = ptr->edge ; |
| if( edgeList[edge].UorR < 0 ) { |
| continue ; |
| } |
| dx1 = edgeList[edge].start ; |
| dx2 = edgeList[edge].end ; |
| if( dx2 < l1x2 || dx1 >= l1x2 ) { |
| continue ; |
| } |
| break ; |
| } |
| if( ritePtr == ptr ) { |
| check = 1 ; |
| checkPtr = Hptrs[ tprop( Hroot , ry ) ] ; |
| for(; checkPtr != (DLINK1PTR) NULL ; |
| checkPtr = checkPtr->next ) { |
| if( edgeList[ checkPtr->edge ].UorR > 0 ) { |
| continue ; |
| } |
| if( edgeList[ checkPtr->edge ].loc >= l1y ) { |
| break ; |
| } |
| if( edgeList[ checkPtr->edge ].start >= l1x2 || |
| edgeList[ checkPtr->edge ].end <= rx1 ) { |
| continue ; |
| } |
| check = 0 ; |
| break ; |
| } |
| if( check ) { |
| edgeList[++numProbes + edgeCount].start = ry ; |
| edgeList[numProbes + edgeCount].end = l1y ; |
| edgeList[numProbes + edgeCount].loc = rx1 ; |
| edgeList[numProbes + edgeCount].length = l1y - ry ; |
| edgeList[numProbes + edgeCount].fixed = 0 ; |
| edgeList[numProbes + edgeCount].cell = 0 ; |
| edgeList[numProbes + edgeCount].UorR = 1 ; |
| tinsert( &vEdgeRoot, rx1 , numProbes + edgeCount ) ; |
| #ifdef DEBUG |
| fprintf(fpdebug,"vprobe:%d ", numProbes ) ; |
| fprintf(fpdebug,"start:%d end:%d loc:%d UorR:%d\n", |
| ry , l1y , rx1 , 1 ) ; |
| #endif |
| edgeList[++numProbes + edgeCount].start = ry ; |
| edgeList[numProbes + edgeCount].end = l1y ; |
| edgeList[numProbes + edgeCount].loc = l1x2 ; |
| edgeList[numProbes + edgeCount].length = l1y - ry ; |
| edgeList[numProbes + edgeCount].fixed = 0 ; |
| edgeList[numProbes + edgeCount].cell = 0 ; |
| edgeList[numProbes + edgeCount].UorR = -1 ; |
| tinsert( &vEdgeRoot, l1x2 , numProbes + edgeCount ) ; |
| #ifdef DEBUG |
| fprintf(fpdebug,"vprobe:%d ", numProbes ) ; |
| fprintf(fpdebug,"start:%d end:%d loc:%d UorR:%d\n", |
| ry , l1y , l1x2 , -1 ) ; |
| #endif |
| } |
| } |
| } |
| if( left2ptr != (DLINK1PTR) NULL && |
| edgeList[ edgeList[left2ptr->edge].nextEdge ].UorR == 1 ) { |
| ptr = Hptrs[ tprop( Hroot , l2y ) ] ; |
| for( ptr = ptr->next; ptr != (DLINK1PTR) NULL; ptr = ptr->next){ |
| if( edgeList[ptr->edge].loc > l2y ) { |
| break ; |
| } |
| } |
| if( ptr == (DLINK1PTR) NULL ) { |
| ptr = hFixedEnd ; |
| } else { |
| ptr = ptr->prev ; |
| } |
| for( ; ptr != (DLINK1PTR) NULL; ptr = ptr->prev){ |
| edge = ptr->edge ; |
| if( edgeList[edge].UorR < 0 ) { |
| continue ; |
| } |
| dx1 = edgeList[edge].start ; |
| dx2 = edgeList[edge].end ; |
| if( dx2 <= l2x1 || dx1 > l2x1 ) { |
| continue ; |
| } |
| break ; |
| } |
| if( ritePtr == ptr ) { |
| check = 1 ; |
| checkPtr = Hptrs[ tprop( Hroot , ry ) ] ; |
| for(; checkPtr != (DLINK1PTR) NULL ; |
| checkPtr = checkPtr->next ) { |
| if( edgeList[ checkPtr->edge ].UorR > 0 ) { |
| continue ; |
| } |
| if( edgeList[ checkPtr->edge ].loc >= l2y ) { |
| break ; |
| } |
| if( edgeList[ checkPtr->edge ].start >= rx2 || |
| edgeList[ checkPtr->edge ].end <= l2x1 ) { |
| continue ; |
| } |
| check = 0 ; |
| break ; |
| } |
| if( check ) { |
| edgeList[++numProbes + edgeCount].start = ry ; |
| edgeList[numProbes + edgeCount].end = l2y ; |
| edgeList[numProbes + edgeCount].loc = l2x1 ; |
| edgeList[numProbes + edgeCount].length = l2y - ry ; |
| edgeList[numProbes + edgeCount].fixed = 0 ; |
| edgeList[numProbes + edgeCount].cell = 0 ; |
| edgeList[numProbes + edgeCount].UorR = 1 ; |
| tinsert( &vEdgeRoot, l2x1 , numProbes + edgeCount ) ; |
| #ifdef DEBUG |
| fprintf(fpdebug,"vprobe:%d ", numProbes ) ; |
| fprintf(fpdebug,"start:%d end:%d loc:%d UorR:%d\n", |
| ry , l2y , l2x1 , 1 ) ; |
| #endif |
| edgeList[++numProbes + edgeCount].start = ry ; |
| edgeList[numProbes + edgeCount].end = l2y ; |
| edgeList[numProbes + edgeCount].loc = rx2 ; |
| edgeList[numProbes + edgeCount].length = l2y - ry ; |
| edgeList[numProbes + edgeCount].fixed = 0 ; |
| edgeList[numProbes + edgeCount].cell = 0 ; |
| edgeList[numProbes + edgeCount].UorR = -1 ; |
| tinsert( &vEdgeRoot, rx2 , numProbes + edgeCount ) ; |
| #ifdef DEBUG |
| fprintf(fpdebug,"vprobe:%d ", numProbes ) ; |
| fprintf(fpdebug,"start:%d end:%d loc:%d UorR:%d\n", |
| ry , l2y , rx2 , -1 ) ; |
| #endif |
| } |
| } |
| } |
| doubleDown( ritePtr ) ; |
| } |
| return ; |
| } |
| |
| |
| |
| void doubleDown( DLINK1PTR rptr ) |
| { |
| |
| int ry , rx1 , rx2 , ly , lx1 , lx2 , check , edge ; |
| DLINK1PTR checkPtr , ptr ; |
| |
| ry = edgeList[ rptr->edge ].loc ; |
| rx2 = edgeList[ rptr->edge ].end ; |
| rx1 = edgeList[ rptr->edge ].start ; |
| |
| ptr = Hptrs[ tprop( Hroot , ry ) ] ; |
| for( ; ptr != (DLINK1PTR) NULL ; ptr = ptr->next ) { |
| edge = ptr->edge ; |
| if( edgeList[edge].UorR > 0 ) { |
| continue ; |
| } |
| ly = edgeList[edge].loc ; |
| lx1 = edgeList[edge].start ; |
| lx2 = edgeList[edge].end ; |
| if( ! ( lx2 < rx2 && lx1 > rx1 ) ) { |
| continue ; |
| } |
| if( edgeList[ edgeList[edge].prevEdge ].UorR == -1 && |
| edgeList[ edgeList[edge].nextEdge ].UorR == 1 ) { |
| check = 1 ; |
| checkPtr = Hptrs[ tprop( Hroot , ry ) ] ; |
| for(; checkPtr != (DLINK1PTR) NULL ; checkPtr = checkPtr->next){ |
| if( checkPtr == rptr ) { |
| continue ; |
| } |
| if( edgeList[ checkPtr->edge ].UorR < 0 ) { |
| continue ; |
| } |
| if( edgeList[ checkPtr->edge ].loc > ly ) { |
| break ; |
| } |
| if( edgeList[ checkPtr->edge ].start >= lx2 || |
| edgeList[ checkPtr->edge ].end <= lx1 ) { |
| continue ; |
| } |
| check = 0 ; |
| break ; |
| } |
| } else { |
| check = 0 ; |
| } |
| if( check ) { |
| edgeList[++numProbes + edgeCount].start = ry ; |
| edgeList[numProbes + edgeCount].end = ly ; |
| edgeList[numProbes + edgeCount].loc = lx1 ; |
| edgeList[numProbes + edgeCount].length = ly - ry ; |
| edgeList[numProbes + edgeCount].fixed = 0 ; |
| edgeList[numProbes + edgeCount].cell = 0 ; |
| edgeList[numProbes + edgeCount].UorR = 1 ; |
| tinsert( &vEdgeRoot, lx1 , numProbes + edgeCount ) ; |
| #ifdef DEBUG |
| fprintf(fpdebug,"vprobe:%d start:%d end:%d loc:%d UorR:%d\n", |
| numProbes, ry , ly , lx1 , 1 ) ; |
| #endif |
| edgeList[++numProbes + edgeCount].start = ry ; |
| edgeList[numProbes + edgeCount].end = ly ; |
| edgeList[numProbes + edgeCount].loc = lx2 ; |
| edgeList[numProbes + edgeCount].length = ly - ry ; |
| edgeList[numProbes + edgeCount].fixed = 0 ; |
| edgeList[numProbes + edgeCount].cell = 0 ; |
| edgeList[numProbes + edgeCount].UorR = -1 ; |
| tinsert( &vEdgeRoot, lx2 , numProbes + edgeCount ) ; |
| #ifdef DEBUG |
| fprintf(fpdebug,"vprobe:%d start:%d end:%d loc:%d UorR:%d\n", |
| numProbes, ry , ly , lx2 , -1 ) ; |
| #endif |
| } |
| } |
| return ; |
| } |