← Back to branch summary

~ubuntu-branches/ubuntu/precise/pcb/precise

« back to all changes in this revision

Viewing changes to src/mtspace.c

  • Committer: Bazaar Package Importer
  • Author(s): Hamish Moffatt
  • Date: 2005-02-20 13:14:00 UTC
  • mfrom: (1.1.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20050220131400-pfz66g5vhx0azl8f
Tags: 1.99j+20050127-2
http://bugs.debian.org/295405
http://bugs.debian.org/295404
http://bugs.debian.org/269578
http://bugs.debian.org/294319
* Improved package description: (closes: #295405)
* Fixed dependency: tk84 -> tk8.4 (closes: #295404)
* Updated README.debian (closes: #269578)
* Applied patch to src/djopt.c to allow compilation with gcc-4.0
  (closes: #294319), thanks to Andreas Jochens for the patch.
* Prevent example files from being compressed

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/mtspace.c
 
1
/* $Id: mtspace.c,v 1.11 2005/01/03 12:57:00 danmc Exp $ */
 
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
 */
 
33
 
 
34
/* implementation for "empty space" routines (needed for via-space tracking
 
35
 * in the auto-router.
 
36
 */
 
37
 
 
38
#ifdef HAVE_CONFIG_H
 
39
#include "config.h"
 
40
#endif
 
41
 
 
42
#include <assert.h>
 
43
#include <setjmp.h>
 
44
#include <stdlib.h>
 
45
 
 
46
#include "box.h"
 
47
#include "global.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
RCSID("$Id: mtspace.c,v 1.11 2005/01/03 12:57:00 danmc Exp $");
 
57
 
 
58
 
 
59
/* define this for more thorough self-checking of data structures */
 
60
#define SLOW_ASSERTIONS
 
61
 
 
62
/* mtspace data structures are built on r-trees. */
 
63
 
 
64
/* ---------------------------------------------------------------------------
 
65
 * some local types
 
66
 */
 
67
typedef struct mtspacebox
 
68
{
 
69
  const BoxType box;
 
70
  int fixed_count;
 
71
  int even_count;
 
72
  int odd_count;
 
73
  BDimension keepaway; /* the smallest keepaway around this box */
 
74
}
 
75
mtspacebox_t;
 
76
 
 
77
/* this is an mtspace_t */
 
78
struct mtspace
 
79
{
 
80
  /* r-tree keeping track of "empty" regions. */
 
81
  rtree_t *rtree;
 
82
  /* bounding box */
 
83
  BoxType bounds;
 
84
};
 
85
 
 
86
#ifndef NDEBUG
 
87
static int
 
88
__mtspace_box_is_good (mtspacebox_t * mtsb)
 
89
{
 
90
  int r = mtsb &&
 
91
    __box_is_good (&mtsb->box) &&
 
92
    mtsb->fixed_count >= 0 && mtsb->even_count >= 0 && mtsb->odd_count >= 0 &&
 
93
    mtsb->keepaway > 0 && 1;
 
94
  assert (r);
 
95
  return r;
 
96
}
 
97
static int
 
98
__mtspace_is_good (mtspace_t * mtspace)
 
99
{
 
100
  int r = mtspace && mtspace->rtree && __box_is_good (&mtspace->bounds) &&
 
101
    /* XXX: check that no boxed in mtspace tree overlap */
 
102
    1;
 
103
  assert (r);
 
104
  return r;
 
105
}
 
106
#endif /* !NDEBUG */
 
107
 
 
108
mtspacebox_t *
 
109
mtspace_create_box (const BoxType * box, int fixed, int even, int odd)
 
110
{
 
111
  mtspacebox_t *mtsb;
 
112
  assert (__box_is_good (box));
 
113
  mtsb = calloc (1, sizeof (*mtsb));
 
114
  *((BoxTypePtr) & mtsb->box) = *box;
 
115
  mtsb->fixed_count = fixed;
 
116
  mtsb->even_count = even;
 
117
  mtsb->odd_count = odd;
 
118
  mtsb->keepaway = MAX_COORD; /* impossibly large start */
 
119
  assert (__mtspace_box_is_good (mtsb));
 
120
  return mtsb;
 
121
}
 
122
 
 
123
/* create an "empty space" representation */
 
124
mtspace_t *
 
125
mtspace_create (const BoxType * bounds, BDimension keepaway)
 
126
{
 
127
  BoxType smaller_bounds;
 
128
  mtspacebox_t *mtsb;
 
129
  mtspace_t *mtspace;
 
130
  assert (bounds);
 
131
  assert (__box_is_good (bounds));
 
132
  /* create initial "empty region" */
 
133
  smaller_bounds = shrink_box (bounds, keepaway);
 
134
  mtsb = mtspace_create_box (&smaller_bounds, 0, 0, 0);
 
135
  mtsb->keepaway = keepaway;
 
136
  /* create mtspace data structure */
 
137
  mtspace = calloc (1, sizeof (*mtspace));
 
138
  mtspace->rtree = r_create_tree ((const BoxType **) &mtsb, 1, 1);
 
139
  mtspace->bounds = smaller_bounds;
 
140
  /* done! */
 
141
  assert (__mtspace_is_good (mtspace));
 
142
  return mtspace;
 
143
}
 
144
 
 
145
/* destroy an "empty space" representation. */
 
146
void
 
147
mtspace_destroy (mtspace_t ** mtspacep)
 
148
{
 
149
  assert (mtspacep && __mtspace_is_good (*mtspacep));
 
150
  r_destroy_tree (&(*mtspacep)->rtree);
 
151
  free (*mtspacep);
 
152
  *mtspacep = NULL;
 
153
}
 
154
 
 
155
struct coalesce_closure
 
156
{
 
157
  vector_t *add_vec;
 
158
  vector_t *remove_vec;
 
159
  /* these are for convenience */
 
160
  mtspacebox_t *mtsb;
 
161
  Boolean is_add;
 
162
  jmp_buf env;
 
163
};
 
164
 
 
165
static int
 
166
boxtype (mtspacebox_t * mtsb)
 
167
{
 
168
  assert (__mtspace_box_is_good (mtsb));
 
169
  return
 
170
    ((mtsb->fixed_count > 0) ? 1 : 0) |
 
171
    ((mtsb->even_count > 0) ? 2 : 0) | ((mtsb->odd_count > 0) ? 4 : 0);
 
172
}
 
173
 
 
174
/* look at last element in add_vec to see if it can be coalesced with
 
175
 * adjacent rectangles.  If it can, add the adjacent rectangle to the
 
176
 * remove_vec and replace the item in add_vec with the coalesced rect.
 
177
 * then remove all in remove_vec and invoke again.  otherwise, we
 
178
 * add the rectangle in add_vec and invoke again, until add_vec is empty. */
 
179
static int
 
180
check_one (const BoxType * box, void *cl)
 
181
{
 
182
  struct coalesce_closure *cc = (struct coalesce_closure *) cl;
 
183
  mtspacebox_t *adj = (mtspacebox_t *) box, *nb;
 
184
  direction_t d;
 
185
  BoxType a, b, c;
 
186
  LocationType x1, x2;
 
187
  int i;
 
188
  float new_area, area_a, area_b;
 
189
  assert (__mtspace_box_is_good (cc->mtsb));
 
190
  assert (__mtspace_box_is_good (adj));
 
191
  /* nothing should intersect mtsb */
 
192
  assert (!box_intersect (&adj->box, &cc->mtsb->box));
 
193
  /* if the box types are different, we can't coalesce */
 
194
  if (cc->mtsb->fixed_count != adj->fixed_count)
 
195
    return 0;
 
196
  if (cc->mtsb->even_count != adj->even_count)
 
197
    return 0;
 
198
  if (cc->mtsb->odd_count != adj->odd_count)
 
199
    return 0;
 
200
  /* determine on which side (if any) adj is adjacent to cc->mtsb */
 
201
  if (0) /* this is just to justify the lines below */ ;
 
202
  else if (adj->box.X1 == cc->mtsb->box.X2)
 
203
    d = EAST;
 
204
  else if (adj->box.X2 == cc->mtsb->box.X1)
 
205
    d = WEST;
 
206
  else if (adj->box.Y1 == cc->mtsb->box.Y2)
 
207
    d = SOUTH;
 
208
  else if (adj->box.Y2 == cc->mtsb->box.Y1)
 
209
    d = NORTH;
 
210
  else
 
211
    return 0;                   /* not adjacent */
 
212
  a = adj->box;
 
213
  b = cc->mtsb->box;
 
214
  ROTATEBOX_TO_NORTH (a, d);
 
215
  ROTATEBOX_TO_NORTH (b, d);
 
216
  assert (a.Y2 == b.Y1);
 
217
  x1 = MAX (a.X1, b.X1);
 
218
  x2 = MIN (a.X2, b.X2);
 
219
  assert (x1 <= x2);            /* overlap */
 
220
  /* area of new coalesced box is (b.Y2-a.Y1)*(x2-x1).  this must be
 
221
   * larger than area of either box a or box b for this to be a win */
 
222
  new_area = (float) (b.Y2 - a.Y1) * (float) (x2 - x1);
 
223
  area_a = (float) (a.Y2 - a.Y1) * (float) (a.X2 - a.X1);
 
224
  area_b = (float) (b.Y2 - b.Y1) * (float) (b.X2 - b.X1);
 
225
  if ((new_area <= area_a) || (new_area <= area_b))
 
226
    return 0;
 
227
  /* okay! coalesce these boxes! */
 
228
  /* add the adjacent rectangle to remove_vec... */
 
229
  vector_append (cc->remove_vec, adj);
 
230
  /* ...and add the split/coalesced rectangles to add_vec */
 
231
  for (i = 0; i < 5; i++)
 
232
    {                           /* five possible rectangles (only 3 ever created) */
 
233
      switch (i)
 
234
        {
 
235
        default:
 
236
          assert (0);
 
237
        case 0:
 
238
          c = a;
 
239
          c.X2 = x1;
 
240
          break;                /* left top */
 
241
        case 1:
 
242
          c = a;
 
243
          c.X1 = x2;
 
244
          break;                /* right top */
 
245
        case 2:
 
246
          c = b;
 
247
          c.X2 = x1;
 
248
          break;                /* left bottom */
 
249
        case 3:
 
250
          c = b;
 
251
          c.X1 = x2;
 
252
          break;                /* right bottom */
 
253
        case 4:
 
254
          c.X1 = x1;
 
255
          c.X2 = x2;
 
256
          c.Y1 = a.Y1;
 
257
          c.Y2 = b.Y2;
 
258
          break;                /* coalesced box */
 
259
        }
 
260
      if (c.X1 < c.X2)
 
261
        {
 
262
          ROTATEBOX_FROM_NORTH (c, d);
 
263
          nb = mtspace_create_box
 
264
            (&c, adj->fixed_count, adj->even_count, adj->odd_count);
 
265
          nb->keepaway = MIN (adj->keepaway, cc->mtsb->keepaway);
 
266
          vector_append (cc->add_vec, nb);
 
267
        }
 
268
    }
 
269
  /* done coalescing! */
 
270
  longjmp (cc->env, 1);         /* don't continue searching */
 
271
  return 1;                     /* never reached! */
 
272
}
 
273
static void
 
274
mtspace_coalesce (mtspace_t * mtspace, struct coalesce_closure *cc)
 
275
{
 
276
  do
 
277
    {
 
278
      /* first, remove anything in remove_vec */
 
279
      while (!vector_is_empty (cc->remove_vec))
 
280
        {
 
281
          mtspacebox_t *mtsb = (mtspacebox_t *)
 
282
            vector_remove_last (cc->remove_vec);
 
283
          r_delete_entry (mtspace->rtree, &mtsb->box);
 
284
        }
 
285
      assert (vector_is_empty (cc->remove_vec));
 
286
      assert (!vector_is_empty (cc->add_vec));
 
287
      cc->mtsb = (mtspacebox_t *) vector_remove_last (cc->add_vec);
 
288
      if (setjmp (cc->env) == 0)
 
289
        {
 
290
          /* search region is one larger than mtsb on all sides */
 
291
          BoxType region = bloat_box (&cc->mtsb->box, 1);
 
292
          int r;
 
293
          r = r_search (mtspace->rtree, &region, NULL, check_one, cc);
 
294
          assert (r == 0);      /* otherwise we would have called 'longjmp' */
 
295
          /* ----- didn't find anything to coalesce ----- */
 
296
#ifndef NDEBUG
 
297
          r = r_region_is_empty (mtspace->rtree, &cc->mtsb->box);
 
298
          assert(r);
 
299
#endif
 
300
          r_insert_entry (mtspace->rtree, &cc->mtsb->box, 1);
 
301
        }
 
302
      else
 
303
        {
 
304
          /* ----- found something to coalesce and added it to add_vec ---- */
 
305
          /* free old mtsb */
 
306
          free (cc->mtsb);
 
307
        }
 
308
    }
 
309
  while (!vector_is_empty (cc->add_vec));
 
310
  assert (vector_is_empty (cc->add_vec));
 
311
  assert (vector_is_empty (cc->remove_vec));
 
312
  assert (__mtspace_is_good (mtspace));
 
313
}
 
314
 
 
315
/* for every box which intersects mtsb->box, split off a chunk with
 
316
 * altered counts.  Add original to remove_vec and add replacements to
 
317
 * add_vec */
 
318
static int
 
319
remove_one (const BoxType * box, void *cl)
 
320
{
 
321
  struct coalesce_closure *cc = (struct coalesce_closure *) cl;
 
322
  mtspacebox_t *ibox = (mtspacebox_t *) box, *nb;
 
323
  BoxType a, b;
 
324
  int i, j;
 
325
  assert (__mtspace_box_is_good (cc->mtsb));
 
326
  assert (__mtspace_box_is_good (ibox));
 
327
  /* some of the candidates won't intersect */
 
328
  if (!box_intersect (&ibox->box, &cc->mtsb->box))
 
329
    return 0;
 
330
  /* remove the intersecting box by adding it to remove_vec */
 
331
  vector_append (cc->remove_vec, ibox);
 
332
  /* there are nine possible split boxes to add */
 
333
  a = cc->mtsb->box;
 
334
  for (i = 0; i < 3; i++)
 
335
    {
 
336
      for (j = 0; j < 3; j++)
 
337
        {
 
338
          b = ibox->box;
 
339
          switch (i)
 
340
            {
 
341
            default:
 
342
              assert (0);
 
343
            case 0:
 
344
              b.X2 = MIN (b.X2, a.X1);
 
345
              break;            /* left */
 
346
            case 1:
 
347
              b.X1 = MAX (b.X1, a.X1);
 
348
              b.X2 = MIN (b.X2, a.X2);
 
349
              break;            /* center */
 
350
            case 2:
 
351
              b.X1 = MAX (b.X1, a.X2);
 
352
              break;            /* right */
 
353
            }
 
354
          switch (j)
 
355
            {
 
356
            default:
 
357
              assert (0);
 
358
            case 0:
 
359
              b.Y2 = MIN (b.Y2, a.Y1);
 
360
              break;            /* top */
 
361
            case 1:
 
362
              b.Y1 = MAX (b.Y1, a.Y1);
 
363
              b.Y2 = MIN (b.Y2, a.Y2);
 
364
              break;            /* center */
 
365
            case 2:
 
366
              b.Y1 = MAX (b.Y1, a.Y2);
 
367
              break;            /* bottom */
 
368
            }
 
369
          if (b.X1 < b.X2 && b.Y1 < b.Y2)
 
370
            {
 
371
              nb = mtspace_create_box
 
372
                (&b, ibox->fixed_count, ibox->even_count, ibox->odd_count);
 
373
              nb->keepaway = MIN (nb->keepaway, cc->mtsb->keepaway);
 
374
              if (i == 1 && j == 1)
 
375
                {               /* this is the intersecting piece */
 
376
                  assert (box_intersect (&nb->box, &cc->mtsb->box));
 
377
                  if (cc->is_add)
 
378
                    {
 
379
                      nb->fixed_count += cc->mtsb->fixed_count;
 
380
                      nb->even_count += cc->mtsb->even_count;
 
381
                      nb->odd_count += cc->mtsb->odd_count;
 
382
                    }
 
383
                  else
 
384
                    {
 
385
                      nb->fixed_count -= cc->mtsb->fixed_count;
 
386
                      nb->even_count -= cc->mtsb->even_count;
 
387
                      nb->odd_count -= cc->mtsb->odd_count;
 
388
                    }
 
389
                }
 
390
              else
 
391
                assert (!box_intersect (&nb->box, &cc->mtsb->box));
 
392
              vector_append (cc->add_vec, nb);
 
393
            }
 
394
        }
 
395
    }
 
396
  return 1;
 
397
}
 
398
static int
 
399
mtspace_remove_chunk (mtspace_t * mtspace, struct coalesce_closure *cc)
 
400
{
 
401
  return r_search (mtspace->rtree, &cc->mtsb->box, NULL, remove_one, cc);
 
402
}
 
403
 
 
404
/* add/remove a chunk from the empty-space representation */
 
405
static void
 
406
mtspace_mutate (mtspace_t * mtspace,
 
407
                const BoxType * box, mtspace_type_t which,
 
408
                BDimension keepaway, Boolean is_add)
 
409
{
 
410
  struct coalesce_closure cc;
 
411
  BoxType bloated;
 
412
  assert (__mtspace_is_good (mtspace));
 
413
  assert (__box_is_good (box));
 
414
  assert (which == FIXED || which == ODD || which == EVEN);
 
415
  /* create coalesce_closure */
 
416
  cc.add_vec = vector_create ();
 
417
  cc.remove_vec = vector_create ();
 
418
  cc.is_add = is_add;
 
419
  /* clip to bounds */
 
420
  bloated = bloat_box (box, keepaway);
 
421
  bloated = clip_box (&bloated, &mtspace->bounds);
 
422
  assert (__box_is_good (&bloated));
 
423
  cc.mtsb = mtspace_create_box
 
424
    (&bloated, which == FIXED ? 1 : 0, which == EVEN ? 1 : 0,
 
425
     which == ODD ? 1 : 0);
 
426
  cc.mtsb->keepaway = keepaway;
 
427
  assert (boxtype (cc.mtsb) != 0);
 
428
  /* take a chunk out of anything which intersects our clipped bloated box */
 
429
  mtspace_remove_chunk (mtspace, &cc);
 
430
  free (cc.mtsb);
 
431
  /* coalesce adjacent chunks */
 
432
  mtspace_coalesce (mtspace, &cc);
 
433
  /* clean up coalesce_closure */
 
434
  vector_destroy (&cc.add_vec);
 
435
  vector_destroy (&cc.remove_vec);
 
436
  /* done! */
 
437
  return;
 
438
}
 
439
 
 
440
/* add a space-filler to the empty space representation.  */
 
441
void
 
442
mtspace_add (mtspace_t * mtspace, const BoxType * box, mtspace_type_t which,
 
443
             BDimension keepaway)
 
444
{
 
445
  mtspace_mutate (mtspace, box, which, keepaway, True);
 
446
}
 
447
 
 
448
/* remove a space-filler from the empty space representation. */
 
449
void
 
450
mtspace_remove (mtspace_t * mtspace,
 
451
                const BoxType * box, mtspace_type_t which, BDimension keepaway)
 
452
{
 
453
  mtspace_mutate (mtspace, box, which, keepaway, False);
 
454
}
 
455
 
 
456
struct query_closure
 
457
{
 
458
  const BoxType *region;
 
459
  vector_t *free_space_vec;
 
460
  vector_t *lo_conflict_space_vec;
 
461
  vector_t *hi_conflict_space_vec;
 
462
  BDimension radius, keepaway;
 
463
  Boolean is_odd;
 
464
};
 
465
 
 
466
static int
 
467
query_one (const BoxType * box, void *cl)
 
468
{
 
469
  struct query_closure *qc = (struct query_closure *) cl;
 
470
  mtspacebox_t *mtsb = (mtspacebox_t *) box;
 
471
  BDimension shrink = 0;
 
472
  BoxTypePtr shrunk;
 
473
  assert (box_intersect (qc->region, &mtsb->box));
 
474
  if (mtsb->fixed_count > 0)
 
475
    /* ignore fixed boxes */
 
476
    return 0;
 
477
  if (qc->keepaway > mtsb->keepaway)
 
478
    shrink = qc->keepaway - mtsb->keepaway;
 
479
  shrink += qc->radius;
 
480
  shrunk = (BoxType *) calloc (1, sizeof(*shrunk));
 
481
  *shrunk = shrink_box (box, shrink);
 
482
  if (shrunk->X2 <= shrunk->X1
 
483
      || shrunk->Y2 <= shrunk->Y1 ||
 
484
  !box_intersect (qc->region, shrunk))
 
485
    {
 
486
      free (shrunk);
 
487
      return 0;
 
488
    }
 
489
  else if ((qc->is_odd ? mtsb->odd_count : mtsb->even_count) > 0)
 
490
    {
 
491
      /* this is a hi_conflict */
 
492
      vector_append (qc->hi_conflict_space_vec, shrunk);
 
493
    }
 
494
  else if (mtsb->odd_count > 0 || mtsb->even_count > 0)
 
495
    {
 
496
      /* this is a lo_conflict */
 
497
      vector_append (qc->lo_conflict_space_vec, shrunk);
 
498
    }
 
499
  else
 
500
    {
 
501
      /* no conflict! */
 
502
      assert (boxtype (mtsb) == 0);
 
503
      vector_append (qc->free_space_vec, shrunk);
 
504
    }
 
505
  return 1;
 
506
}
 
507
 
 
508
/* returns all empty spaces in 'region' which may hold a feature with the
 
509
 * mtspace feature_radius with the specified minimum keepaway.  Completely
 
510
 * empty regions are appended to the free_space_vec vector; regions which
 
511
 * are filled by objects generated by the previous pass are appended to the
 
512
 * lo_conflict_space_vec vector, and regions which are filled by objects
 
513
 * generated during *this* pass are appended to the hi_conflict_space_vec
 
514
 * vector.  The current pass identity is given by 'is_odd'.  Regions which
 
515
 * are filled by fixed objects are not returned at all. */
 
516
void
 
517
mtspace_query_rect (mtspace_t * mtspace, const BoxType * region,
 
518
                    BDimension radius, BDimension keepaway,
 
519
                    vector_t * free_space_vec,
 
520
                    vector_t * lo_conflict_space_vec,
 
521
                    vector_t * hi_conflict_space_vec, Boolean is_odd)
 
522
{
 
523
  struct query_closure qc;
 
524
  /* pre-assertions */
 
525
  assert (__mtspace_is_good (mtspace));
 
526
  assert (__box_is_good (region));
 
527
  assert (free_space_vec && vector_is_empty (free_space_vec));
 
528
  assert (lo_conflict_space_vec && vector_is_empty (lo_conflict_space_vec));
 
529
  assert (hi_conflict_space_vec && vector_is_empty (hi_conflict_space_vec));
 
530
  /* initialize closure */
 
531
  qc.region = region;
 
532
  qc.free_space_vec = free_space_vec;
 
533
  qc.lo_conflict_space_vec = lo_conflict_space_vec;
 
534
  qc.hi_conflict_space_vec = hi_conflict_space_vec;
 
535
  qc.is_odd = is_odd;
 
536
  qc.keepaway = keepaway;
 
537
  qc.radius = radius;
 
538
  /* do the query */
 
539
  r_search (mtspace->rtree, region, NULL, query_one, &qc);
 
540
  /* post-assertions */
 
541
#ifndef NDEBUG
 
542
#ifdef SLOW_ASSERTIONS
 
543
  {                             /* assert that all returned boxes are inside the given search region */
 
544
    int i, j;
 
545
    for (i = 0; i < 3; i++)
 
546
      {
 
547
        vector_t *v =
 
548
          (i == 0) ? free_space_vec :
 
549
          (i == 1) ? lo_conflict_space_vec : hi_conflict_space_vec;
 
550
        for (j = 0; j < vector_size (v); j++)
 
551
          {
 
552
            const BoxType *b = (const BoxType *) vector_element (v, j);
 
553
            assert (__box_is_good (b));
 
554
            assert (box_intersect (region, b));
 
555
          }
 
556
      }
 
557
  }
 
558
#endif /* SLOW_ASSERTIONS */
 
559
#endif /* !NDEBUG */
 
560
}