pcb 4.1.1
An interactive printed circuit board layout editor.

mtspace.c

Go to the documentation of this file.
00001 
00046 #ifdef HAVE_CONFIG_H
00047 #include "config.h"
00048 #endif
00049 
00050 #include "global.h"
00051 
00052 #include <assert.h>
00053 #include <setjmp.h>
00054 
00055 #include "box.h"
00056 #include "heap.h"
00057 #include "rtree.h"
00058 #include "mtspace.h"
00059 #include "vector.h"
00060 
00061 #ifdef HAVE_LIBDMALLOC
00062 #include <dmalloc.h>
00063 #endif
00064 
00065 /* ---------------------------------------------------------------------------
00066  * some local types
00067  */
00068 
00069 typedef struct mtspacebox
00070 {
00071   const BoxType box;
00072   Coord keepaway; 
00073 }
00074 mtspacebox_t;
00075 
00083 struct mtspace
00084 {
00085   rtree_t *ftree, *etree, *otree;
00086 };
00087 
00088 typedef union
00089 {
00090   vector_t * v;
00091   heap_t * h;
00092 } heap_or_vector;
00093 
00097 struct vetting
00098 {
00099   heap_or_vector untested;
00100   heap_or_vector no_fix;
00101   heap_or_vector no_hi;
00102   heap_or_vector hi_candidate;
00103   Coord radius;
00104   Coord keepaway;
00105   CheapPointType desired;
00106 };
00107 
00108 #define SPECIAL 823157
00109 
00110 mtspacebox_t *
00111 mtspace_create_box (const BoxType * box, Coord keepaway)
00112 {
00113   mtspacebox_t *mtsb;
00114   assert (box_is_good (box));
00115   mtsb = (mtspacebox_t *)malloc (sizeof (*mtsb));
00116   /* the box was sent to us pre-bloated by the keepaway amount */
00117   *((BoxType *) & mtsb->box) = *box;
00118   mtsb->keepaway = keepaway;
00119   assert (box_is_good (&mtsb->box));
00120   return mtsb;
00121 }
00122 
00127 mtspace_t *
00128 mtspace_create (void)
00129 {
00130   mtspace_t *mtspace;
00131 
00132   /* create mtspace data structure */
00133   mtspace = (mtspace_t *)malloc (sizeof (*mtspace));
00134   mtspace->ftree = r_create_tree (NULL, 0, 0);
00135   mtspace->etree = r_create_tree (NULL, 0, 0);
00136   mtspace->otree = r_create_tree (NULL, 0, 0);
00137   /* done! */
00138   return mtspace;
00139 }
00140 
00144 void
00145 mtspace_destroy (mtspace_t ** mtspacep)
00146 {
00147   assert (mtspacep);
00148   r_destroy_tree (&(*mtspacep)->ftree);
00149   r_destroy_tree (&(*mtspacep)->etree);
00150   r_destroy_tree (&(*mtspacep)->otree);
00151   free (*mtspacep);
00152   *mtspacep = NULL;
00153 }
00154 
00155 struct mts_info
00156 {
00157   Coord keepaway;
00158   BoxType box;
00159   rtree_t *tree;
00160   jmp_buf env;
00161 };
00162 
00163 static int
00164 mts_remove_one (const BoxType * b, void *cl)
00165 {
00166   struct mts_info *info = (struct mts_info *) cl;
00167   mtspacebox_t *box = (mtspacebox_t *) b;
00168 
00169   /* there can be duplicate boxes, we just remove one */
00170   /* the info box is pre-bloated, so just check equality */
00171   if (b->X1 == info->box.X1 && b->X2 == info->box.X2 &&
00172       b->Y1 == info->box.Y1 && b->Y2 == info->box.Y2 &&
00173       box->keepaway == info->keepaway)
00174     {
00175       r_delete_entry (info->tree, b);
00176       longjmp (info->env, 1);
00177     }
00178   return 0;
00179 }
00180 
00181 rtree_t *
00182 which_tree (mtspace_t * mtspace, mtspace_type_t which)
00183 {
00184   switch (which)
00185     {
00186     case FIXED:
00187       return mtspace->ftree;
00188     case EVEN:
00189       return mtspace->etree;
00190     default:
00191       return mtspace->otree;
00192     }
00193 }
00194 
00201 void
00202 mtspace_add (mtspace_t * mtspace, const BoxType * box, mtspace_type_t which,
00203              Coord keepaway)
00204 {
00205   mtspacebox_t *filler = mtspace_create_box (box, keepaway);
00206   r_insert_entry (which_tree (mtspace, which), (const BoxType *) filler, 1);
00207 }
00208 
00215 void
00216 mtspace_remove (mtspace_t * mtspace,
00217                 const BoxType * box, mtspace_type_t which,
00218                 Coord keepaway)
00219 {
00220   struct mts_info cl;
00221   BoxType small_search;
00222 
00223   cl.keepaway = keepaway;
00224   cl.box = *box;
00225   cl.tree = which_tree (mtspace, which);
00226   small_search = box_center(box);
00227   if (setjmp (cl.env) == 0)
00228     {
00229       r_search (cl.tree, &small_search, NULL, mts_remove_one, &cl);
00230       assert (0);               /* didn't find it?? */
00231     }
00232 }
00233 
00234 struct query_closure
00235 {
00236   BoxType *cbox;
00237   heap_or_vector checking;
00238   heap_or_vector touching;
00239   CheapPointType *desired;
00240   Coord radius, keepaway;
00241   jmp_buf env;
00242   bool touch_is_vec;
00243 };
00244 
00245 static inline void
00246 heap_append (heap_t *heap, CheapPointType *desired, BoxType *newone)
00247 {
00248   CheapPointType p = *desired;
00249   assert (desired);
00250   closest_point_in_box (&p, newone);
00251   heap_insert (heap, ABS(p.X - desired->X) + (p.Y - desired->Y), newone);
00252 }
00253 
00254 static inline void
00255 append (struct query_closure * qc, BoxType *newone)
00256 { 
00257   if (qc->desired)
00258     heap_append (qc->checking.h, qc->desired, newone);
00259   else
00260     vector_append (qc->checking.v, newone);
00261 }
00262 
00269 static int
00270 query_one (const BoxType * box, void *cl)
00271 {
00272   struct query_closure *qc = (struct query_closure *) cl;
00273   mtspacebox_t *mtsb = (mtspacebox_t *) box;
00274   Coord shrink;
00275   assert (box_intersect (qc->cbox, &mtsb->box));
00276   /* we need to satisfy the larger of the two keepaways */
00277   if (qc->keepaway > mtsb->keepaway)
00278     shrink = mtsb->keepaway;
00279   else
00280     shrink = qc->keepaway;
00281   /* if we shrink qc->box by this amount and it doesn't intersect
00282    * then we didn't actually touch this box */
00283   if (qc->cbox->X1 + shrink >= mtsb->box.X2 ||
00284       qc->cbox->X2 - shrink <= mtsb->box.X1 ||
00285       qc->cbox->Y1 + shrink >= mtsb->box.Y2 ||
00286       qc->cbox->Y2 - shrink <= mtsb->box.Y1)
00287     return 0;
00288   /* ok, we do touch this box, now create up to 4 boxes that don't */
00289   if (mtsb->box.Y1 > qc->cbox->Y1 + shrink)     /* top region exists */
00290     {
00291       Coord Y1 = qc->cbox->Y1;
00292       Coord Y2 = mtsb->box.Y1 + shrink;
00293       if (Y2 - Y1 >= 2 * (qc->radius + qc->keepaway))
00294         {
00295           BoxType *newone = (BoxType *) malloc (sizeof (BoxType));
00296           newone->X1 = qc->cbox->X1;
00297           newone->X2 = qc->cbox->X2;
00298           newone->Y1 = Y1;
00299           newone->Y2 = Y2;
00300           assert (newone->Y2 < qc->cbox->Y2);
00301           append(qc, newone);
00302         }
00303     }
00304   if (mtsb->box.Y2 < qc->cbox->Y2 - shrink)     /* bottom region exists */
00305     {
00306       Coord Y1 = mtsb->box.Y2 - shrink;
00307       Coord Y2 = qc->cbox->Y2;
00308       if (Y2 - Y1 >= 2 * (qc->radius + qc->keepaway))
00309         {
00310           BoxType *newone = (BoxType *) malloc (sizeof (BoxType));
00311           newone->X1 = qc->cbox->X1;
00312           newone->X2 = qc->cbox->X2;
00313           newone->Y2 = qc->cbox->Y2;
00314           newone->Y1 = Y1;
00315           assert (newone->Y1 > qc->cbox->Y1);
00316           append (qc, newone);
00317         }
00318     }
00319   if (mtsb->box.X1 > qc->cbox->X1 + shrink)     /* left region exists */
00320     {
00321       Coord X1 = qc->cbox->X1;
00322       Coord X2 = mtsb->box.X1 + shrink;
00323       if (X2 - X1 >= 2 * (qc->radius + qc->keepaway))
00324         {
00325           BoxType *newone;
00326           newone = (BoxType *) malloc (sizeof (BoxType));
00327           newone->Y1 = qc->cbox->Y1;
00328           newone->Y2 = qc->cbox->Y2;
00329           newone->X1 = qc->cbox->X1;
00330           newone->X2 = X2;
00331           assert (newone->X2 < qc->cbox->X2);
00332           append (qc, newone);
00333         }
00334     }
00335   if (mtsb->box.X2 < qc->cbox->X2 - shrink)     /* right region exists */
00336     {
00337       Coord X1 = mtsb->box.X2 - shrink;
00338       Coord X2 = qc->cbox->X2;
00339       if (X2 - X1 >= 2 * (qc->radius + qc->keepaway))
00340         {
00341           BoxType *newone = (BoxType *) malloc (sizeof (BoxType));
00342           newone->Y1 = qc->cbox->Y1;
00343           newone->Y2 = qc->cbox->Y2;
00344           newone->X2 = qc->cbox->X2;
00345           newone->X1 = X1;
00346           assert (newone->X1 > qc->cbox->X1);
00347           append (qc, newone);
00348         }
00349     }
00350   if (qc->touching.v)
00351     {
00352       if (qc->touch_is_vec || !qc->desired)
00353         vector_append (qc->touching.v, qc->cbox);
00354       else
00355         heap_append (qc->touching.h, qc->desired, qc->cbox);
00356     }
00357   else
00358     free (qc->cbox);            /* done with this one */
00359   longjmp (qc->env, 1);
00360   return 1;                     /* never reached */
00361 }
00362 
00375 static void
00376 qloop (struct query_closure *qc, rtree_t * tree, heap_or_vector res, bool is_vec)
00377 {
00378   BoxType *cbox;
00379 #ifndef NDEBUG
00380   int n;
00381 #endif
00382   while (!(qc->desired ? heap_is_empty (qc->checking.h) : vector_is_empty (qc->checking.v)))
00383     {
00384       cbox = qc->desired ? (BoxType *)heap_remove_smallest (qc->checking.h) : (BoxType *)vector_remove_last (qc->checking.v);
00385       if (setjmp (qc->env) == 0)
00386         {
00387           assert (box_is_good (cbox));
00388           qc->cbox = cbox;
00389 #ifndef NDEBUG
00390           n =
00391 #endif
00392             r_search (tree, cbox, NULL, query_one, qc);
00393           assert (n == 0);
00394           /* nothing intersected with this tree, put it in the result vector */
00395           if (is_vec)
00396             vector_append (res.v, cbox);
00397           else
00398             {
00399               if (qc->desired)
00400                 heap_append (res.h, qc->desired, cbox);
00401               else
00402                 vector_append (res.v, cbox);
00403             }
00404           return;               /* found one - perhaps one answer is good enough */
00405         }
00406     }
00407 }
00408 
00412 void
00413 mtsFreeWork (vetting_t ** w)
00414 {
00415   vetting_t *work = (*w);
00416   if (work->desired.X != -SPECIAL || work->desired.Y != -SPECIAL)
00417     {
00418        heap_free (work->untested.h, free);
00419        heap_destroy (&work->untested.h);
00420        heap_free (work->no_fix.h, free);
00421        heap_destroy (&work->no_fix.h);
00422        heap_free (work->no_hi.h, free);
00423        heap_destroy (&work->no_hi.h);
00424        heap_free (work->hi_candidate.h, free);
00425        heap_destroy (&work->hi_candidate.h);
00426     }
00427   else
00428     {
00429        while (!vector_is_empty (work->untested.v))
00430          free (vector_remove_last (work->untested.v));
00431        vector_destroy (&work->untested.v);
00432        while (!vector_is_empty (work->no_fix.v))
00433          free (vector_remove_last (work->no_fix.v));
00434        vector_destroy (&work->no_fix.v);
00435        while (!vector_is_empty (work->no_hi.v))
00436          free (vector_remove_last (work->no_hi.v));
00437        vector_destroy (&work->no_hi.v);
00438        while (!vector_is_empty (work->hi_candidate.v))
00439          free (vector_remove_last (work->hi_candidate.v));
00440        vector_destroy (&work->hi_candidate.v);
00441     }
00442   free (work);
00443   (*w) = NULL;
00444 }
00445 
00446 
00468 vetting_t *
00469 mtspace_query_rect (mtspace_t * mtspace, const BoxType * region,
00470                     Coord radius, Coord keepaway,
00471                     vetting_t * work,
00472                     vector_t * free_space_vec,
00473                     vector_t * lo_conflict_space_vec,
00474                     vector_t * hi_conflict_space_vec,
00475                     bool is_odd, bool with_conflicts, CheapPointType *desired)
00476 {
00477   struct query_closure qc;
00478 
00479   /* pre-assertions */
00480   assert (free_space_vec);
00481   assert (lo_conflict_space_vec);
00482   assert (hi_conflict_space_vec);
00483   /* search out to anything that might matter */
00484   if (region)
00485     {
00486       BoxType *cbox;
00487       assert (work == NULL);
00488       assert (box_is_good (region));
00489       assert(vector_is_empty (free_space_vec));
00490       assert(vector_is_empty (lo_conflict_space_vec));
00491       assert(vector_is_empty (hi_conflict_space_vec));
00492       work = (vetting_t *) malloc (sizeof (vetting_t));
00493       work->keepaway = keepaway;
00494       work->radius = radius;
00495       cbox = (BoxType *) malloc (sizeof (BoxType));
00496       *cbox = bloat_box (region, keepaway + radius);
00497       if (desired)
00498         {
00499           work->untested.h = heap_create ();
00500           work->no_fix.h = heap_create ();
00501           work->hi_candidate.h = heap_create ();
00502           work->no_hi.h =heap_create ();
00503           assert (work->untested.h && work->no_fix.h &&
00504                   work->no_hi.h && work->hi_candidate.h);
00505           heap_insert (work->untested.h, 0, cbox);
00506           work->desired = *desired;
00507         }
00508       else
00509         {
00510           work->untested.v = vector_create ();
00511           work->no_fix.v = vector_create ();
00512           work->hi_candidate.v = vector_create ();
00513           work->no_hi.v = vector_create ();
00514           assert (work->untested.v && work->no_fix.v &&
00515                   work->no_hi.v && work->hi_candidate.v);
00516           vector_append (work->untested.v, cbox);
00517           work->desired.X = work->desired.Y = -SPECIAL;
00518         }
00519       return work;
00520     }
00521   qc.keepaway = work->keepaway;
00522   qc.radius = work->radius;
00523   if (work->desired.X == -SPECIAL && work->desired.Y == -SPECIAL)
00524     qc.desired = NULL;
00525   else
00526     qc.desired = &work->desired;
00527   /* do the query */
00528   do
00529     {
00530       heap_or_vector temporary = {free_space_vec};
00531       /* search the fixed object tree discarding any intersections
00532        * and placing empty regions in the no_fix vector.
00533        */
00534       qc.checking = work->untested;
00535       qc.touching.v = NULL;
00536       qloop (&qc, mtspace->ftree, work->no_fix, false);
00537       /* search the hi-conflict tree placing intersectors in the
00538        * hi_candidate vector (if conflicts are allowed) and
00539        * placing empty regions in the no_hi vector.
00540        */
00541       qc.checking.v = work->no_fix.v;
00542       qc.touching.v = with_conflicts ? work->hi_candidate.v : NULL;
00543       qc.touch_is_vec = false;
00544       qloop (&qc, is_odd ? mtspace->otree : mtspace->etree, work->no_hi, false);
00545       /* search the lo-conflict tree placing intersectors in the
00546        * lo-conflict answer vector (if conflicts allowed) and
00547        * placing emptry regions in the free-space answer vector.
00548        */
00549       qc.checking = work->no_hi;
00550 /* XXX lo_conflict_space_vec will be treated like a heap! */
00551       qc.touching.v = (with_conflicts ? lo_conflict_space_vec : NULL);
00552       qc.touch_is_vec = true;
00553       qloop (&qc, is_odd ? mtspace->etree : mtspace->otree, temporary, true);
00554 
00555       /* qloop (&qc, is_odd ? mtspace->etree : mtspace->otree, (heap_or_vector)free_space_vec, true); */
00556       if (!vector_is_empty (free_space_vec))
00557         {
00558           if (qc.desired)
00559           {
00560             if (heap_is_empty (work->untested.h))
00561               break;
00562           }
00563           else
00564           {
00565             if (vector_is_empty (work->untested.v))
00566               break;
00567           }
00568           return work;
00569         }
00570       /* finally check the hi-conflict intersectors against the
00571        * lo-conflict tree discarding intersectors (two types of conflict is real bad)
00572        * and placing empty regions in the hi-conflict answer vector.
00573        */
00574       if (with_conflicts)
00575         {
00576           heap_or_vector temporary = {hi_conflict_space_vec};
00577           qc.checking = work->hi_candidate;
00578           qc.touching.v = NULL;
00579           qloop (&qc, is_odd ? mtspace->etree : mtspace->otree,
00580                  temporary, true);
00581 
00582           /* qloop (&qc, is_odd ? mtspace->etree : mtspace->otree, */
00583           /*     (heap_or_vector)hi_conflict_space_vec, true); */
00584         }
00585     }
00586   while (!(qc.desired ? heap_is_empty(work->untested.h) : vector_is_empty (work->untested.v)));
00587   if (qc.desired)
00588     {
00589       if (heap_is_empty (work->no_fix.h) &&
00590           heap_is_empty (work->no_hi.h) &&
00591           heap_is_empty (work->hi_candidate.h))
00592        {
00593           mtsFreeWork (&work);
00594           return NULL;
00595        }
00596     }
00597   else
00598     {
00599       if (vector_is_empty (work->no_fix.v) &&
00600           vector_is_empty (work->no_hi.v) && vector_is_empty (work->hi_candidate.v))
00601         {
00602           mtsFreeWork (&work);
00603           return NULL;
00604         }
00605      }
00606   return work;
00607 }
00608 
00609 int
00610 mtsBoxCount (vetting_t * w)
00611 {
00612 #if 0
00613   int ans;
00614   ans = 3 * vector_size (w->untested);
00615   ans += 2 * vector_size (w->no_fix);
00616   ans += vector_size (w->no_hi);
00617   ans += vector_size (w->hi_candidate);
00618   return ans;
00619 #endif
00620   return 100;
00621 }