4 * \brief Implementation for "empty space" routines (needed for
5 * via-space tracking in the auto-router.
7 * mtspace data structures are built on r-trees.
9 * This file, mtspace.c, was written and is
11 * Copyright (c) 2001 C. Scott Ananian.
13 * Copyright (c) 2006 harry eaton.
17 * <h1><b>Copyright.</b></h1>\n
19 * PCB, interactive printed circuit board design
21 * Copyright (C) 1994,1995,1996 Thomas Nau
23 * Copyright (C) 1998,1999,2000,2001 harry eaton
25 * This program is free software; you can redistribute it and/or modify
26 * it under the terms of the GNU General Public License as published by
27 * the Free Software Foundation; either version 2 of the License, or
28 * (at your option) any later version.
30 * This program is distributed in the hope that it will be useful,
31 * but WITHOUT ANY WARRANTY; without even the implied warranty of
32 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
33 * GNU General Public License for more details.
35 * You should have received a copy of the GNU General Public License
36 * along with this program; if not, write to the Free Software
37 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
39 * Contact addresses for paper mail and Email:
41 * harry eaton, 6697 Buttonhole Ct, Columbia, MD 21044 USA
43 * haceaton@aplcomm.jhuapl.edu
61 #ifdef HAVE_LIBDMALLOC
65 /* ---------------------------------------------------------------------------
69 typedef struct mtspacebox
72 Coord keepaway
; /*!< the smallest keepaway around this box */
77 * \brief This is an mtspace_t.
79 * \c rtrees keeping track of regions expanded by their required
81 * One for fixed, even, and odd.
85 rtree_t
*ftree
, *etree
, *otree
;
95 * \brief This is a vetting_t.
99 heap_or_vector untested
;
100 heap_or_vector no_fix
;
101 heap_or_vector no_hi
;
102 heap_or_vector hi_candidate
;
105 CheapPointType desired
;
108 #define SPECIAL 823157
111 mtspace_create_box (const BoxType
* box
, Coord keepaway
)
114 assert (box_is_good (box
));
115 mtsb
= (mtspacebox_t
*)malloc (sizeof (*mtsb
));
116 /* the box was sent to us pre-bloated by the keepaway amount */
117 *((BoxType
*) & mtsb
->box
) = *box
;
118 mtsb
->keepaway
= keepaway
;
119 assert (box_is_good (&mtsb
->box
));
124 * \brief Create an "empty space" representation with a shrunken
128 mtspace_create (void)
132 /* create mtspace data structure */
133 mtspace
= (mtspace_t
*)malloc (sizeof (*mtspace
));
134 mtspace
->ftree
= r_create_tree (NULL
, 0, 0);
135 mtspace
->etree
= r_create_tree (NULL
, 0, 0);
136 mtspace
->otree
= r_create_tree (NULL
, 0, 0);
142 * \brief Destroy an "empty space" representation.
145 mtspace_destroy (mtspace_t
** mtspacep
)
148 r_destroy_tree (&(*mtspacep
)->ftree
);
149 r_destroy_tree (&(*mtspacep
)->etree
);
150 r_destroy_tree (&(*mtspacep
)->otree
);
164 mts_remove_one (const BoxType
* b
, void *cl
)
166 struct mts_info
*info
= (struct mts_info
*) cl
;
167 mtspacebox_t
*box
= (mtspacebox_t
*) b
;
169 /* there can be duplicate boxes, we just remove one */
170 /* the info box is pre-bloated, so just check equality */
171 if (b
->X1
== info
->box
.X1
&& b
->X2
== info
->box
.X2
&&
172 b
->Y1
== info
->box
.Y1
&& b
->Y2
== info
->box
.Y2
&&
173 box
->keepaway
== info
->keepaway
)
175 r_delete_entry (info
->tree
, b
);
176 longjmp (info
->env
, 1);
182 which_tree (mtspace_t
* mtspace
, mtspace_type_t which
)
187 return mtspace
->ftree
;
189 return mtspace
->etree
;
191 return mtspace
->otree
;
196 * \brief Add a space-filler to the empty space representation.
198 * The given box should *not* be bloated; it should be "true".
199 * The feature will fill *at least* a radius of keepaway around it;
202 mtspace_add (mtspace_t
* mtspace
, const BoxType
* box
, mtspace_type_t which
,
205 mtspacebox_t
*filler
= mtspace_create_box (box
, keepaway
);
206 r_insert_entry (which_tree (mtspace
, which
), (const BoxType
*) filler
, 1);
210 * \brief Remove a space-filler from the empty space representation.
212 * The given box should *not* be bloated; it should be "true".
213 * The feature will fill *at least* a radius of keepaway around it;
216 mtspace_remove (mtspace_t
* mtspace
,
217 const BoxType
* box
, mtspace_type_t which
,
221 BoxType small_search
;
223 cl
.keepaway
= keepaway
;
225 cl
.tree
= which_tree (mtspace
, which
);
226 small_search
= box_center(box
);
227 if (setjmp (cl
.env
) == 0)
229 r_search (cl
.tree
, &small_search
, NULL
, mts_remove_one
, &cl
);
230 assert (0); /* didn't find it?? */
237 heap_or_vector checking
;
238 heap_or_vector touching
;
239 CheapPointType
*desired
;
240 Coord radius
, keepaway
;
246 heap_append (heap_t
*heap
, CheapPointType
*desired
, BoxType
*newone
)
248 CheapPointType p
= *desired
;
250 closest_point_in_box (&p
, newone
);
251 heap_insert (heap
, ABS(p
.X
- desired
->X
) + (p
.Y
- desired
->Y
), newone
);
255 append (struct query_closure
* qc
, BoxType
*newone
)
258 heap_append (qc
->checking
.h
, qc
->desired
, newone
);
260 vector_append (qc
->checking
.v
, newone
);
264 * \brief We found some space filler that may intersect this query.
266 * First check if it does intersect, then break it into overlaping
267 * regions that don't intersect this box.
270 query_one (const BoxType
* box
, void *cl
)
272 struct query_closure
*qc
= (struct query_closure
*) cl
;
273 mtspacebox_t
*mtsb
= (mtspacebox_t
*) box
;
275 assert (box_intersect (qc
->cbox
, &mtsb
->box
));
276 /* we need to satisfy the larger of the two keepaways */
277 if (qc
->keepaway
> mtsb
->keepaway
)
278 shrink
= mtsb
->keepaway
;
280 shrink
= qc
->keepaway
;
281 /* if we shrink qc->box by this amount and it doesn't intersect
282 * then we didn't actually touch this box */
283 if (qc
->cbox
->X1
+ shrink
>= mtsb
->box
.X2
||
284 qc
->cbox
->X2
- shrink
<= mtsb
->box
.X1
||
285 qc
->cbox
->Y1
+ shrink
>= mtsb
->box
.Y2
||
286 qc
->cbox
->Y2
- shrink
<= mtsb
->box
.Y1
)
288 /* ok, we do touch this box, now create up to 4 boxes that don't */
289 if (mtsb
->box
.Y1
> qc
->cbox
->Y1
+ shrink
) /* top region exists */
291 Coord Y1
= qc
->cbox
->Y1
;
292 Coord Y2
= mtsb
->box
.Y1
+ shrink
;
293 if (Y2
- Y1
>= 2 * (qc
->radius
+ qc
->keepaway
))
295 BoxType
*newone
= (BoxType
*) malloc (sizeof (BoxType
));
296 newone
->X1
= qc
->cbox
->X1
;
297 newone
->X2
= qc
->cbox
->X2
;
300 assert (newone
->Y2
< qc
->cbox
->Y2
);
304 if (mtsb
->box
.Y2
< qc
->cbox
->Y2
- shrink
) /* bottom region exists */
306 Coord Y1
= mtsb
->box
.Y2
- shrink
;
307 Coord Y2
= qc
->cbox
->Y2
;
308 if (Y2
- Y1
>= 2 * (qc
->radius
+ qc
->keepaway
))
310 BoxType
*newone
= (BoxType
*) malloc (sizeof (BoxType
));
311 newone
->X1
= qc
->cbox
->X1
;
312 newone
->X2
= qc
->cbox
->X2
;
313 newone
->Y2
= qc
->cbox
->Y2
;
315 assert (newone
->Y1
> qc
->cbox
->Y1
);
319 if (mtsb
->box
.X1
> qc
->cbox
->X1
+ shrink
) /* left region exists */
321 Coord X1
= qc
->cbox
->X1
;
322 Coord X2
= mtsb
->box
.X1
+ shrink
;
323 if (X2
- X1
>= 2 * (qc
->radius
+ qc
->keepaway
))
326 newone
= (BoxType
*) malloc (sizeof (BoxType
));
327 newone
->Y1
= qc
->cbox
->Y1
;
328 newone
->Y2
= qc
->cbox
->Y2
;
329 newone
->X1
= qc
->cbox
->X1
;
331 assert (newone
->X2
< qc
->cbox
->X2
);
335 if (mtsb
->box
.X2
< qc
->cbox
->X2
- shrink
) /* right region exists */
337 Coord X1
= mtsb
->box
.X2
- shrink
;
338 Coord X2
= qc
->cbox
->X2
;
339 if (X2
- X1
>= 2 * (qc
->radius
+ qc
->keepaway
))
341 BoxType
*newone
= (BoxType
*) malloc (sizeof (BoxType
));
342 newone
->Y1
= qc
->cbox
->Y1
;
343 newone
->Y2
= qc
->cbox
->Y2
;
344 newone
->X2
= qc
->cbox
->X2
;
346 assert (newone
->X1
> qc
->cbox
->X1
);
352 if (qc
->touch_is_vec
|| !qc
->desired
)
353 vector_append (qc
->touching
.v
, qc
->cbox
);
355 heap_append (qc
->touching
.h
, qc
->desired
, qc
->cbox
);
358 free (qc
->cbox
); /* done with this one */
359 longjmp (qc
->env
, 1);
360 return 1; /* never reached */
364 * \brief qloop takes a vector (or heap) of regions to check (checking)
365 * if they don't intersect anything.
367 * If a region does intersect something, it is broken into pieces that
368 * don't intersect that thing (if possible) which are put back into the
369 * vector/heap of regions to check.
371 * \return qloop returns false when it finds the first empty region.
372 * It returns true if it has exhausted the region vector/heap and never
373 * found an empty area.
376 qloop (struct query_closure
*qc
, rtree_t
* tree
, heap_or_vector res
, bool is_vec
)
382 while (!(qc
->desired
? heap_is_empty (qc
->checking
.h
) : vector_is_empty (qc
->checking
.v
)))
384 cbox
= qc
->desired
? (BoxType
*)heap_remove_smallest (qc
->checking
.h
) : (BoxType
*)vector_remove_last (qc
->checking
.v
);
385 if (setjmp (qc
->env
) == 0)
387 assert (box_is_good (cbox
));
392 r_search (tree
, cbox
, NULL
, query_one
, qc
);
394 /* nothing intersected with this tree, put it in the result vector */
396 vector_append (res
.v
, cbox
);
400 heap_append (res
.h
, qc
->desired
, cbox
);
402 vector_append (res
.v
, cbox
);
404 return; /* found one - perhaps one answer is good enough */
410 * \brief Free the memory used by the vetting structure.
413 mtsFreeWork (vetting_t
** w
)
415 vetting_t
*work
= (*w
);
416 if (work
->desired
.X
!= -SPECIAL
|| work
->desired
.Y
!= -SPECIAL
)
418 heap_free (work
->untested
.h
, free
);
419 heap_destroy (&work
->untested
.h
);
420 heap_free (work
->no_fix
.h
, free
);
421 heap_destroy (&work
->no_fix
.h
);
422 heap_free (work
->no_hi
.h
, free
);
423 heap_destroy (&work
->no_hi
.h
);
424 heap_free (work
->hi_candidate
.h
, free
);
425 heap_destroy (&work
->hi_candidate
.h
);
429 while (!vector_is_empty (work
->untested
.v
))
430 free (vector_remove_last (work
->untested
.v
));
431 vector_destroy (&work
->untested
.v
);
432 while (!vector_is_empty (work
->no_fix
.v
))
433 free (vector_remove_last (work
->no_fix
.v
));
434 vector_destroy (&work
->no_fix
.v
);
435 while (!vector_is_empty (work
->no_hi
.v
))
436 free (vector_remove_last (work
->no_hi
.v
));
437 vector_destroy (&work
->no_hi
.v
);
438 while (!vector_is_empty (work
->hi_candidate
.v
))
439 free (vector_remove_last (work
->hi_candidate
.v
));
440 vector_destroy (&work
->hi_candidate
.v
);
450 * It tries first to find Completely empty regions (which are
451 * appended to the free_space_vec vector).
452 * If that fails, it looks for regions filled only by objects generated
453 * by the previous pass (which are appended to the lo_conflict_space_vec
455 * Then it looks for regions that are filled by objects generated during
456 * *this* pass (which are appended to the hi_conflict_space_vec vector).
457 * The current pass identity is given by 'is_odd'.
458 * As soon as one completely free region is found, it returns with that
460 * It saves partially searched regions in vectors "untested", "no_fix",
461 * "no_hi", and "hi_candidate" which can be passed to future calls of
462 * this function to search harder for such regions if the computation
465 * \return returns some empty spaces in 'region' (or former narrowed regions)
466 * that may hold a feature with the specified radius and keepaway
469 mtspace_query_rect (mtspace_t
* mtspace
, const BoxType
* region
,
470 Coord radius
, Coord keepaway
,
472 vector_t
* free_space_vec
,
473 vector_t
* lo_conflict_space_vec
,
474 vector_t
* hi_conflict_space_vec
,
475 bool is_odd
, bool with_conflicts
, CheapPointType
*desired
)
477 struct query_closure qc
;
480 assert (free_space_vec
);
481 assert (lo_conflict_space_vec
);
482 assert (hi_conflict_space_vec
);
483 /* search out to anything that might matter */
487 assert (work
== NULL
);
488 assert (box_is_good (region
));
489 assert(vector_is_empty (free_space_vec
));
490 assert(vector_is_empty (lo_conflict_space_vec
));
491 assert(vector_is_empty (hi_conflict_space_vec
));
492 work
= (vetting_t
*) malloc (sizeof (vetting_t
));
493 work
->keepaway
= keepaway
;
494 work
->radius
= radius
;
495 cbox
= (BoxType
*) malloc (sizeof (BoxType
));
496 *cbox
= bloat_box (region
, keepaway
+ radius
);
499 work
->untested
.h
= heap_create ();
500 work
->no_fix
.h
= heap_create ();
501 work
->hi_candidate
.h
= heap_create ();
502 work
->no_hi
.h
=heap_create ();
503 assert (work
->untested
.h
&& work
->no_fix
.h
&&
504 work
->no_hi
.h
&& work
->hi_candidate
.h
);
505 heap_insert (work
->untested
.h
, 0, cbox
);
506 work
->desired
= *desired
;
510 work
->untested
.v
= vector_create ();
511 work
->no_fix
.v
= vector_create ();
512 work
->hi_candidate
.v
= vector_create ();
513 work
->no_hi
.v
= vector_create ();
514 assert (work
->untested
.v
&& work
->no_fix
.v
&&
515 work
->no_hi
.v
&& work
->hi_candidate
.v
);
516 vector_append (work
->untested
.v
, cbox
);
517 work
->desired
.X
= work
->desired
.Y
= -SPECIAL
;
521 qc
.keepaway
= work
->keepaway
;
522 qc
.radius
= work
->radius
;
523 if (work
->desired
.X
== -SPECIAL
&& work
->desired
.Y
== -SPECIAL
)
526 qc
.desired
= &work
->desired
;
530 heap_or_vector temporary
= {free_space_vec
};
531 /* search the fixed object tree discarding any intersections
532 * and placing empty regions in the no_fix vector.
534 qc
.checking
= work
->untested
;
535 qc
.touching
.v
= NULL
;
536 qloop (&qc
, mtspace
->ftree
, work
->no_fix
, false);
537 /* search the hi-conflict tree placing intersectors in the
538 * hi_candidate vector (if conflicts are allowed) and
539 * placing empty regions in the no_hi vector.
541 qc
.checking
.v
= work
->no_fix
.v
;
542 qc
.touching
.v
= with_conflicts
? work
->hi_candidate
.v
: NULL
;
543 qc
.touch_is_vec
= false;
544 qloop (&qc
, is_odd
? mtspace
->otree
: mtspace
->etree
, work
->no_hi
, false);
545 /* search the lo-conflict tree placing intersectors in the
546 * lo-conflict answer vector (if conflicts allowed) and
547 * placing emptry regions in the free-space answer vector.
549 qc
.checking
= work
->no_hi
;
550 /* XXX lo_conflict_space_vec will be treated like a heap! */
551 qc
.touching
.v
= (with_conflicts
? lo_conflict_space_vec
: NULL
);
552 qc
.touch_is_vec
= true;
553 qloop (&qc
, is_odd
? mtspace
->etree
: mtspace
->otree
, temporary
, true);
555 /* qloop (&qc, is_odd ? mtspace->etree : mtspace->otree, (heap_or_vector)free_space_vec, true); */
556 if (!vector_is_empty (free_space_vec
))
560 if (heap_is_empty (work
->untested
.h
))
565 if (vector_is_empty (work
->untested
.v
))
570 /* finally check the hi-conflict intersectors against the
571 * lo-conflict tree discarding intersectors (two types of conflict is real bad)
572 * and placing empty regions in the hi-conflict answer vector.
576 heap_or_vector temporary
= {hi_conflict_space_vec
};
577 qc
.checking
= work
->hi_candidate
;
578 qc
.touching
.v
= NULL
;
579 qloop (&qc
, is_odd
? mtspace
->etree
: mtspace
->otree
,
582 /* qloop (&qc, is_odd ? mtspace->etree : mtspace->otree, */
583 /* (heap_or_vector)hi_conflict_space_vec, true); */
586 while (!(qc
.desired
? heap_is_empty(work
->untested
.h
) : vector_is_empty (work
->untested
.v
)));
589 if (heap_is_empty (work
->no_fix
.h
) &&
590 heap_is_empty (work
->no_hi
.h
) &&
591 heap_is_empty (work
->hi_candidate
.h
))
599 if (vector_is_empty (work
->no_fix
.v
) &&
600 vector_is_empty (work
->no_hi
.v
) && vector_is_empty (work
->hi_candidate
.v
))
610 mtsBoxCount (vetting_t
* w
)
614 ans
= 3 * vector_size (w
->untested
);
615 ans
+= 2 * vector_size (w
->no_fix
);
616 ans
+= vector_size (w
->no_hi
);
617 ans
+= vector_size (w
->hi_candidate
);