src/mtspace.c

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