src/mtspace.c

   1 /* $Id$ */
   2
   3 /*
   4  *                            COPYRIGHT
   5  *
   6  *  PCB, interactive printed circuit board design
   7  *  Copyright (C) 1994,1995,1996 Thomas Nau
   8  *  Copyright (C) 1998,1999,2000,2001 harry eaton
   9  *
  10  *  This program is free software; you can redistribute it and/or modify
  11  *  it under the terms of the GNU General Public License as published by
  12  *  the Free Software Foundation; either version 2 of the License, or
  13  *  (at your option) any later version.
  14  *
  15  *  This program is distributed in the hope that it will be useful,
  16  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18  *  GNU General Public License for more details.
  19  *
  20  *  You should have received a copy of the GNU General Public License
  21  *  along with this program; if not, write to the Free Software
  22  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  23  *
  24  *  Contact addresses for paper mail and Email:
  25  *  harry eaton, 6697 Buttonhole Ct, Columbia, MD 21044 USA
  26  *  haceaton@aplcomm.jhuapl.edu
  27  *
  28  */
  29
  30 /* this file, mtspace.c, was written and is
  31  * Copyright (c) 2001 C. Scott Ananian.
  32  * Copyright (c) 2006 harry eaton.
  33  */
  34
  35 /* implementation for "empty space" routines (needed for via-space tracking
  36  * in the auto-router.
  37  */
  38
  39 #ifdef HAVE_CONFIG_H
  40 #include "config.h"
  41 #endif
  42
  43 #include "global.h"
  44
  45 #include <assert.h>
  46 #include <setjmp.h>
  47
  48 #include "box.h"
  49 #include "heap.h"
  50 #include "rtree.h"
  51 #include "mtspace.h"
  52 #include "vector.h"
  53
  54 #ifdef HAVE_LIBDMALLOC
  55 #include <dmalloc.h>
  56 #endif
  57
  58 RCSID ("$Id$");
  59
  60 /* mtspace data structures are built on r-trees. */
  61
  62 /* ---------------------------------------------------------------------------
  63  * some local types
  64  */
  65
  66 typedef struct mtspacebox
  67 {
  68   const BoxType box;
  69   Coord keepaway;               /* the smallest keepaway around this box */
  70 }
  71 mtspacebox_t;
  72
  73 /* this is an mtspace_t */
  74 struct mtspace
  75 {
  76   /* rtrees keeping track of regions expanded by their required clearance. */
  77   /* one for fixed, even, and odd */
  78   rtree_t *ftree, *etree, *otree;
  79 };
  80
  81 typedef union
  82 {
  83   vector_t * v;
  84   heap_t * h;
  85 } heap_or_vector;
  86
  87 /* this is a vetting_t */
  88 struct vetting
  89 {
  90   heap_or_vector untested;
  91   heap_or_vector no_fix;
  92   heap_or_vector no_hi;
  93   heap_or_vector hi_candidate;
  94   Coord radius;
  95   Coord keepaway;
  96   CheapPointType desired;
  97 };
  98
  99 #define SPECIAL 823157
 100
 101 mtspacebox_t *
 102 mtspace_create_box (const BoxType * box, Coord keepaway)
 103 {
 104   mtspacebox_t *mtsb;
 105   assert (box_is_good (box));
 106   mtsb = (mtspacebox_t *)malloc (sizeof (*mtsb));
 107   /* the box was sent to us pre-bloated by the keepaway amount */
 108   *((BoxTypePtr) & mtsb->box) = *box;
 109   mtsb->keepaway = keepaway;
 110   assert (box_is_good (&mtsb->box));
 111   return mtsb;
 112 }
 113
 114 /* create an "empty space" representation */
 115 mtspace_t *
 116 mtspace_create (void)
 117 {
 118   mtspace_t *mtspace;
 119
 120   /* create mtspace data structure */
 121   mtspace = (mtspace_t *)malloc (sizeof (*mtspace));
 122   mtspace->ftree = r_create_tree (NULL, 0, 0);
 123   mtspace->etree = r_create_tree (NULL, 0, 0);
 124   mtspace->otree = r_create_tree (NULL, 0, 0);
 125   /* done! */
 126   return mtspace;
 127 }
 128
 129 /* destroy an "empty space" representation. */
 130 void
 131 mtspace_destroy (mtspace_t ** mtspacep)
 132 {
 133   assert (mtspacep);
 134   r_destroy_tree (&(*mtspacep)->ftree);
 135   r_destroy_tree (&(*mtspacep)->etree);
 136   r_destroy_tree (&(*mtspacep)->otree);
 137   free (*mtspacep);
 138   *mtspacep = NULL;
 139 }
 140
 141 struct mts_info
 142 {
 143   Coord keepaway;
 144   BoxType box;
 145   rtree_t *tree;
 146   jmp_buf env;
 147 };
 148
 149 static int
 150 mts_remove_one (const BoxType * b, void *cl)
 151 {
 152   struct mts_info *info = (struct mts_info *) cl;
 153   mtspacebox_t *box = (mtspacebox_t *) b;
 154
 155   /* there can be duplicate boxes, we just remove one */
 156   /* the info box is pre-bloated, so just check equality */
 157   if (b->X1 == info->box.X1 && b->X2 == info->box.X2 &&
 158       b->Y1 == info->box.Y1 && b->Y2 == info->box.Y2 &&
 159       box->keepaway == info->keepaway)
 160     {
 161       r_delete_entry (info->tree, b);
 162       longjmp (info->env, 1);
 163     }
 164   return 0;
 165 }
 166
 167 rtree_t *
 168 which_tree (mtspace_t * mtspace, mtspace_type_t which)
 169 {
 170   switch (which)
 171     {
 172     case FIXED:
 173       return mtspace->ftree;
 174     case EVEN:
 175       return mtspace->etree;
 176     default:
 177       return mtspace->otree;
 178     }
 179 }
 180
 181 /* add a space-filler to the empty space representation.  */
 182 void
 183 mtspace_add (mtspace_t * mtspace, const BoxType * box, mtspace_type_t which,
 184              Coord keepaway)
 185 {
 186   mtspacebox_t *filler = mtspace_create_box (box, keepaway);
 187   r_insert_entry (which_tree (mtspace, which), (const BoxType *) filler, 1);
 188 }
 189
 190 /* remove a space-filler from the empty space representation. */
 191 void
 192 mtspace_remove (mtspace_t * mtspace,
 193                 const BoxType * box, mtspace_type_t which,
 194                 Coord keepaway)
 195 {
 196   struct mts_info cl;
 197   BoxType small_search;
 198
 199   cl.keepaway = keepaway;
 200   cl.box = *box;
 201   cl.tree = which_tree (mtspace, which);
 202   small_search = box_center(box);
 203   if (setjmp (cl.env) == 0)
 204     {
 205       r_search (cl.tree, &small_search, NULL, mts_remove_one, &cl);
 206       assert (0);               /* didn't find it?? */
 207     }
 208 }
 209
 210 struct query_closure
 211 {
 212   BoxType *cbox;
 213   heap_or_vector checking;
 214   heap_or_vector touching;
 215   CheapPointType *desired;
 216   Coord radius, keepaway;
 217   jmp_buf env;
 218   bool touch_is_vec;
 219 };
 220
 221 static inline void
 222 heap_append (heap_t *heap, CheapPointType *desired, BoxType *newone)
 223 {
 224   CheapPointType p = *desired;
 225   assert (desired);
 226   closest_point_in_box (&p, newone);
 227   heap_insert (heap, ABS(p.X - desired->X) + (p.Y - desired->Y), newone);
 228 }
 229
 230 static inline void
 231 append (struct query_closure * qc, BoxType *newone)
 232 {
 233   if (qc->desired)
 234     heap_append (qc->checking.h, qc->desired, newone);
 235   else
 236     vector_append (qc->checking.v, newone);
 237 }
 238
 239 /* we found some space filler that may intersect this query.
 240  * First check if it does intersect, then break it into
 241  * overlaping regions that don't intersect this box.
 242  */
 243 static int
 244 query_one (const BoxType * box, void *cl)
 245 {
 246   struct query_closure *qc = (struct query_closure *) cl;
 247   mtspacebox_t *mtsb = (mtspacebox_t *) box;
 248   Coord shrink;
 249   assert (box_intersect (qc->cbox, &mtsb->box));
 250   /* we need to satisfy the larger of the two keepaways */
 251   if (qc->keepaway > mtsb->keepaway)
 252     shrink = mtsb->keepaway;
 253   else
 254     shrink = qc->keepaway;
 255   /* if we shrink qc->box by this amount and it doesn't intersect
 256    * then we didn't actually touch this box */
 257   if (qc->cbox->X1 + shrink >= mtsb->box.X2 ||
 258       qc->cbox->X2 - shrink <= mtsb->box.X1 ||
 259       qc->cbox->Y1 + shrink >= mtsb->box.Y2 ||
 260       qc->cbox->Y2 - shrink <= mtsb->box.Y1)
 261     return 0;
 262   /* ok, we do touch this box, now create up to 4 boxes that don't */
 263   if (mtsb->box.Y1 > qc->cbox->Y1 + shrink)     /* top region exists */
 264     {
 265       Coord Y1 = qc->cbox->Y1;
 266       Coord Y2 = mtsb->box.Y1 + shrink;
 267       if (Y2 - Y1 >= 2 * (qc->radius + qc->keepaway))
 268         {
 269           BoxType *newone = (BoxType *) malloc (sizeof (BoxType));
 270           newone->X1 = qc->cbox->X1;
 271           newone->X2 = qc->cbox->X2;
 272           newone->Y1 = Y1;
 273           newone->Y2 = Y2;
 274           assert (newone->Y2 < qc->cbox->Y2);
 275           append(qc, newone);
 276         }
 277     }
 278   if (mtsb->box.Y2 < qc->cbox->Y2 - shrink)     /* bottom region exists */
 279     {
 280       Coord Y1 = mtsb->box.Y2 - shrink;
 281       Coord Y2 = qc->cbox->Y2;
 282       if (Y2 - Y1 >= 2 * (qc->radius + qc->keepaway))
 283         {
 284           BoxType *newone = (BoxType *) malloc (sizeof (BoxType));
 285           newone->X1 = qc->cbox->X1;
 286           newone->X2 = qc->cbox->X2;
 287           newone->Y2 = qc->cbox->Y2;
 288           newone->Y1 = Y1;
 289           assert (newone->Y1 > qc->cbox->Y1);
 290           append (qc, newone);
 291         }
 292     }
 293   if (mtsb->box.X1 > qc->cbox->X1 + shrink)     /* left region exists */
 294     {
 295       Coord X1 = qc->cbox->X1;
 296       Coord X2 = mtsb->box.X1 + shrink;
 297       if (X2 - X1 >= 2 * (qc->radius + qc->keepaway))
 298         {
 299           BoxType *newone;
 300           newone = (BoxType *) malloc (sizeof (BoxType));
 301           newone->Y1 = qc->cbox->Y1;
 302           newone->Y2 = qc->cbox->Y2;
 303           newone->X1 = qc->cbox->X1;
 304           newone->X2 = X2;
 305           assert (newone->X2 < qc->cbox->X2);
 306           append (qc, newone);
 307         }
 308     }
 309   if (mtsb->box.X2 < qc->cbox->X2 - shrink)     /* right region exists */
 310     {
 311       Coord X1 = mtsb->box.X2 - shrink;
 312       Coord X2 = qc->cbox->X2;
 313       if (X2 - X1 >= 2 * (qc->radius + qc->keepaway))
 314         {
 315           BoxType *newone = (BoxType *) malloc (sizeof (BoxType));
 316           newone->Y1 = qc->cbox->Y1;
 317           newone->Y2 = qc->cbox->Y2;
 318           newone->X2 = qc->cbox->X2;
 319           newone->X1 = X1;
 320           assert (newone->X1 > qc->cbox->X1);
 321           append (qc, newone);
 322         }
 323     }
 324   if (qc->touching.v)
 325     {
 326       if (qc->touch_is_vec || !qc->desired)
 327         vector_append (qc->touching.v, qc->cbox);
 328       else
 329         heap_append (qc->touching.h, qc->desired, qc->cbox);
 330     }
 331   else
 332     free (qc->cbox);            /* done with this one */
 333   longjmp (qc->env, 1);
 334   return 1;                     /* never reached */
 335 }
 336
 337 /* qloop takes a vector (or heap) of regions to check (checking) if they don't intersect
 338  * anything. If a region does intersect something, it is broken into
 339  * pieces that don't intersect that thing (if possible) which are
 340  * put back into the vector/heap of regions to check.
 341  * qloop returns false when it finds the first empty region
 342  * it returns true if it has exhausted the region vector/heap and never
 343  * found an empty area.
 344  */
 345 static void
 346 qloop (struct query_closure *qc, rtree_t * tree, heap_or_vector res, bool is_vec)
 347 {
 348   BoxType *cbox;
 349 #ifndef NDEBUG
 350   int n;
 351 #endif
 352   while (!(qc->desired ? heap_is_empty (qc->checking.h) : vector_is_empty (qc->checking.v)))
 353     {
 354       cbox = qc->desired ? (BoxTypePtr)heap_remove_smallest (qc->checking.h) : (BoxTypePtr)vector_remove_last (qc->checking.v);
 355       if (setjmp (qc->env) == 0)
 356         {
 357           assert (box_is_good (cbox));
 358           qc->cbox = cbox;
 359 #ifndef NDEBUG
 360           n =
 361 #endif
 362             r_search (tree, cbox, NULL, query_one, qc);
 363           assert (n == 0);
 364           /* nothing intersected with this tree, put it in the result vector */
 365           if (is_vec)
 366             vector_append (res.v, cbox);
 367           else
 368             {
 369               if (qc->desired)
 370                 heap_append (res.h, qc->desired, cbox);
 371               else
 372                 vector_append (res.v, cbox);
 373             }
 374           return;               /* found one - perhaps one answer is good enough */
 375         }
 376     }
 377 }
 378
 379 /* free the memory used by the vetting structure */
 380 void
 381 mtsFreeWork (vetting_t ** w)
 382 {
 383   vetting_t *work = (*w);
 384   if (work->desired.X != -SPECIAL || work->desired.Y != -SPECIAL)
 385     {
 386        heap_free (work->untested.h, free);
 387        heap_destroy (&work->untested.h);
 388        heap_free (work->no_fix.h, free);
 389        heap_destroy (&work->no_fix.h);
 390        heap_free (work->no_hi.h, free);
 391        heap_destroy (&work->no_hi.h);
 392        heap_free (work->hi_candidate.h, free);
 393        heap_destroy (&work->hi_candidate.h);
 394     }
 395   else
 396     {
 397        while (!vector_is_empty (work->untested.v))
 398          free (vector_remove_last (work->untested.v));
 399        vector_destroy (&work->untested.v);
 400        while (!vector_is_empty (work->no_fix.v))
 401          free (vector_remove_last (work->no_fix.v));
 402        vector_destroy (&work->no_fix.v);
 403        while (!vector_is_empty (work->no_hi.v))
 404          free (vector_remove_last (work->no_hi.v));
 405        vector_destroy (&work->no_hi.v);
 406        while (!vector_is_empty (work->hi_candidate.v))
 407          free (vector_remove_last (work->hi_candidate.v));
 408        vector_destroy (&work->hi_candidate.v);
 409     }
 410   free (work);
 411   (*w) = NULL;
 412 }
 413
 414
 415 /* returns some empty spaces in 'region' (or former narrowed regions)
 416  * that may hold a feature with the specified radius and keepaway
 417  * It tries first to find Completely empty regions (which are appended
 418  * to the free_space_vec vector). If that fails, it looks for regions
 419  * filled only by objects generated by the previous pass (which are
 420  * appended to the lo_conflict_space_vec vector). Then it looks for
 421  * regions that are filled by objects generated during *this* pass
 422  * (which  are appended to the hi_conflict_space_vec vector). The
 423  * current pass identity is given by 'is_odd'.  As soon as one completely
 424  * free region is found, it returns with that answer. It saves partially
 425  * searched regions in vectors "untested", "no_fix", "no_hi", and
 426  * "hi_candidate" which can be passed to future calls of this function
 427  * to search harder for such regions if the computation becomes
 428  * necessary.
 429  */
 430 vetting_t *
 431 mtspace_query_rect (mtspace_t * mtspace, const BoxType * region,
 432                     Coord radius, Coord keepaway,
 433                     vetting_t * work,
 434                     vector_t * free_space_vec,
 435                     vector_t * lo_conflict_space_vec,
 436                     vector_t * hi_conflict_space_vec,
 437                     bool is_odd, bool with_conflicts, CheapPointType *desired)
 438 {
 439   struct query_closure qc;
 440
 441   /* pre-assertions */
 442   assert (free_space_vec);
 443   assert (lo_conflict_space_vec);
 444   assert (hi_conflict_space_vec);
 445   /* search out to anything that might matter */
 446   if (region)
 447     {
 448       BoxType *cbox;
 449       assert (work == NULL);
 450       assert (box_is_good (region));
 451       assert(vector_is_empty (free_space_vec));
 452       assert(vector_is_empty (lo_conflict_space_vec));
 453       assert(vector_is_empty (hi_conflict_space_vec));
 454       work = (vetting_t *) malloc (sizeof (vetting_t));
 455       work->keepaway = keepaway;
 456       work->radius = radius;
 457       cbox = (BoxType *) malloc (sizeof (BoxType));
 458       *cbox = bloat_box (region, keepaway + radius);
 459       if (desired)
 460         {
 461           work->untested.h = heap_create ();
 462           work->no_fix.h = heap_create ();
 463           work->hi_candidate.h = heap_create ();
 464           work->no_hi.h =heap_create ();
 465           assert (work->untested.h && work->no_fix.h &&
 466                   work->no_hi.h && work->hi_candidate.h);
 467           heap_insert (work->untested.h, 0, cbox);
 468           work->desired = *desired;
 469         }
 470       else
 471         {
 472           work->untested.v = vector_create ();
 473           work->no_fix.v = vector_create ();
 474           work->hi_candidate.v = vector_create ();
 475           work->no_hi.v = vector_create ();
 476           assert (work->untested.v && work->no_fix.v &&
 477                   work->no_hi.v && work->hi_candidate.v);
 478           vector_append (work->untested.v, cbox);
 479           work->desired.X = work->desired.Y = -SPECIAL;
 480         }
 481       return work;
 482     }
 483   qc.keepaway = work->keepaway;
 484   qc.radius = work->radius;
 485   if (work->desired.X == -SPECIAL && work->desired.Y == -SPECIAL)
 486     qc.desired = NULL;
 487   else
 488     qc.desired = &work->desired;
 489   /* do the query */
 490   do
 491     {
 492       heap_or_vector temporary = {free_space_vec};
 493       /* search the fixed object tree discarding any intersections
 494        * and placing empty regions in the no_fix vector.
 495        */
 496       qc.checking = work->untested;
 497       qc.touching.v = NULL;
 498       qloop (&qc, mtspace->ftree, work->no_fix, false);
 499       /* search the hi-conflict tree placing intersectors in the
 500        * hi_candidate vector (if conflicts are allowed) and
 501        * placing empty regions in the no_hi vector.
 502        */
 503       qc.checking.v = work->no_fix.v;
 504       qc.touching.v = with_conflicts ? work->hi_candidate.v : NULL;
 505       qc.touch_is_vec = false;
 506       qloop (&qc, is_odd ? mtspace->otree : mtspace->etree, work->no_hi, false);
 507       /* search the lo-conflict tree placing intersectors in the
 508        * lo-conflict answer vector (if conflicts allowed) and
 509        * placing emptry regions in the free-space answer vector.
 510        */
 511       qc.checking = work->no_hi;
 512 /* XXX lo_conflict_space_vec will be treated like a heap! */
 513       qc.touching.v = (with_conflicts ? lo_conflict_space_vec : NULL);
 514       qc.touch_is_vec = true;
 515       qloop (&qc, is_odd ? mtspace->etree : mtspace->otree, temporary, true);
 516
 517       /* qloop (&qc, is_odd ? mtspace->etree : mtspace->otree, (heap_or_vector)free_space_vec, true); */
 518       if (!vector_is_empty (free_space_vec))
 519         {
 520           if (qc.desired)
 521           {
 522             if (heap_is_empty (work->untested.h))
 523               break;
 524           }
 525           else
 526           {
 527             if (vector_is_empty (work->untested.v))
 528               break;
 529           }
 530           return work;
 531         }
 532       /* finally check the hi-conflict intersectors against the
 533        * lo-conflict tree discarding intersectors (two types of conflict is real bad)
 534        * and placing empty regions in the hi-conflict answer vector.
 535        */
 536       if (with_conflicts)
 537         {
 538           heap_or_vector temporary = {hi_conflict_space_vec};
 539           qc.checking = work->hi_candidate;
 540           qc.touching.v = NULL;
 541           qloop (&qc, is_odd ? mtspace->etree : mtspace->otree,
 542                  temporary, true);
 543
 544           /* qloop (&qc, is_odd ? mtspace->etree : mtspace->otree, */
 545           /*     (heap_or_vector)hi_conflict_space_vec, true); */
 546         }
 547     }
 548   while (!(qc.desired ? heap_is_empty(work->untested.h) : vector_is_empty (work->untested.v)));
 549   if (qc.desired)
 550     {
 551       if (heap_is_empty (work->no_fix.h) &&
 552           heap_is_empty (work->no_hi.h) &&
 553           heap_is_empty (work->hi_candidate.h))
 554        {
 555           mtsFreeWork (&work);
 556           return NULL;
 557        }
 558     }
 559   else
 560     {
 561       if (vector_is_empty (work->no_fix.v) &&
 562           vector_is_empty (work->no_hi.v) && vector_is_empty (work->hi_candidate.v))
 563         {
 564           mtsFreeWork (&work);
 565           return NULL;
 566         }
 567      }
 568   return work;
 569 }
 570
 571 int
 572 mtsBoxCount (vetting_t * w)
 573 {
 574 #if 0
 575   int ans;
 576   ans = 3 * vector_size (w->untested);
 577   ans += 2 * vector_size (w->no_fix);
 578   ans += vector_size (w->no_hi);
 579   ans += vector_size (w->hi_candidate);
 580   return ans;
 581 #endif
 582   return 100;
 583 }