1 /*
2 * DBtiles.c --
3 *
4 * Low-level tile primitives for the database.
5 * This includes area searching and all other primitives that
6 * need to know what lives in a tile body.
7 *
8 * *********************************************************************
9 * * Copyright (C) 1985, 1990 Regents of the University of California. *
10 * * Permission to use, copy, modify, and distribute this *
11 * * software and its documentation for any purpose and without *
12 * * fee is hereby granted, provided that the above copyright *
13 * * notice appear in all copies. The University of California *
14 * * makes no representations about the suitability of this *
15 * * software for any purpose. It is provided "as is" without *
16 * * express or implied warranty. Export of this software outside *
17 * * of the United States of America may require an export license. *
18 * *********************************************************************
19 */
20
21 #ifndef lint
22 static char rcsid[] __attribute__ ((unused)) = "$Header: /usr/cvsroot/magic-8.0/database/DBtiles.c,v 1.2 2010/06/24 12:37:15 tim Exp $";
23 #endif /* not lint */
24
25 #include <stdio.h>
26
27 #include "utils/magic.h"
28 #include "utils/geometry.h"
29 #include "tiles/tile.h"
30 #include "utils/signals.h"
31 #include "utils/hash.h"
32 #include "utils/undo.h"
33 #include "database/database.h"
34 #include "database/databaseInt.h"
35 #include "utils/malloc.h"
36
37 /* Used by DBCheckMaxHStrips() and DBCheckMaxVStrips() */
38 struct dbCheck
39 {
40 int (*dbc_proc)();
41 Rect dbc_area;
42 ClientData dbc_cdata;
43 };
44
45 int dbCheckMaxHFunc(), dbCheckMaxVFunc();
46
47 /*
48 * --------------------------------------------------------------------
49 *
50 * DBSrPaintNMArea --
51 *
52 * Find all tiles overlapping a given triangular area whose types are
53 * contained in the mask supplied. Apply the given procedure to each
54 * such tile. The procedure should be of the following form:
55 *
56 * int
57 * func(tile, cdata)
58 * Tile *tile;
59 * ClientData cdata;
60 * {
61 * }
62 *
63 * This is equivalent to DBSrPaintArea, but is used when only one
64 * diagonal half (nonmanhattan extension) of the area should be searched.
65 * The bitmask for the diagonal are passed in "ttype" (diagonal, side and
66 * direction only are used, as in DBNMPaintPlane).
67 *
68 * Results:
69 * 0 is returned if the search completed normally. 1 is returned
70 * if it aborted.
71 *
72 * Side effects:
73 * Whatever side effects result from application of the
74 * supplied procedure.
75 *
76 * Notes:
77 * Do not call this routine on an infinite search area (e.g., area
78 * == &TiPlaneRect), even if "ttype" is set appropriately.
79 * --------------------------------------------------------------------
80 */
81
82 #define IGNORE_LEFT 1
83 #define IGNORE_RIGHT 2
84
85 int
DBSrPaintNMArea(hintTile,plane,ttype,rect,mask,func,arg)86 DBSrPaintNMArea(hintTile, plane, ttype, rect, mask, func, arg)
87 Tile *hintTile; /* Tile at which to begin search, if not NULL.
88 * If this is NULL, use the hint tile supplied
89 * with plane.
90 */
91 Plane *plane; /* Plane in which tiles lie. This is used to
92 * provide a hint tile in case hintTile == NULL.
93 * The hint tile in the plane is updated to be
94 * the last tile visited in the area
95 * enumeration.
96 */
97 TileType ttype; /* Information about the non-manhattan area to
98 * search; zero if area is manhattan.
99 */
100 Rect *rect; /* Area to search. This area should not be
101 * degenerate. Tiles must OVERLAP the area.
102 */
103 TileTypeBitMask *mask; /* Mask of those paint tiles to be passed to
104 * func.
105 */
106 int (*func)(); /* Function to apply at each tile */
107 ClientData arg; /* Additional argument to pass to (*func)() */
108 {
109 Point start;
110 Tile *tp, *tpnew;
111 TileType tpt;
112 int rheight, rwidth, rmax;
113 dlong f1, f2, f3, f4;
114 bool ignore_sides;
115
116 /* If the search area is not diagonal, return the result of the */
117 /* standard (manhattan) search function. */
118
119 if (!(ttype & TT_DIAGONAL))
120 return DBSrPaintArea(hintTile, plane, rect, mask, func, arg);
121
122 start.p_x = rect->r_xbot;
123 start.p_y = rect->r_ytop - 1;
124 tp = hintTile ? hintTile : plane->pl_hint;
125 GOTOPOINT(tp, &start);
126
127 /* Each iteration visits another tile on the LHS of the search area */
128 while (TOP(tp) > rect->r_ybot)
129 {
130 /* Each iteration enumerates another tile */
131 nm_enum:
132 plane->pl_hint = tp;
133 if (SigInterruptPending)
134 return (1);
135
136 /* Check if the tile is in the (nonmanhattan) area, and continue */
137 /* the tile enumeration if it is not. */
138 /* Watch for calculations involving (M)INFINITY in tile (tp)! */
139
140 rheight = rect->r_ytop - rect->r_ybot;
141 rwidth = rect->r_xtop - rect->r_xbot;
142 rmax = MAX(rheight, rwidth);
143 f1 = (BOTTOM(tp) > MINFINITY + 2) ?
144 ((dlong)(rect->r_ytop - BOTTOM(tp)) * rwidth) : DLONG_MAX;
145 f2 = (TOP(tp) < INFINITY - 2) ?
146 ((dlong)(TOP(tp) - rect->r_ybot) * rwidth) : DLONG_MAX;
147
148 if (ttype & TT_SIDE)
149 {
150 /* Outside-of-triangle check---ignore sub-integer slivers */
151 if (RIGHT(tp) < INFINITY - 2)
152 {
153 f3 = (dlong)(rect->r_xtop - RIGHT(tp)) * rheight;
154 f3 += rmax;
155 }
156 else
157 f3 = DLONG_MIN;
158 if ((ttype & TT_DIRECTION) ? (f2 < f3) : (f1 < f3))
159 goto enum_next;
160 }
161 else
162 {
163 /* Outside-of-triangle check---ignore sub-integer slivers */
164 if (LEFT(tp) > MINFINITY + 2)
165 {
166 f4 = (dlong)(LEFT(tp) - rect->r_xbot) * rheight;
167 f4 += rmax;
168 }
169 else
170 f4 = DLONG_MIN;
171 if ((ttype & TT_DIRECTION) ? (f1 < f4) : (f2 < f4))
172 goto enum_next;
173 }
174
175 /* Secondary checks---if tile is also non-Manhattan, is */
176 /* either side of it outside the area? If so, restrict it. */
177 /* This check is only necessary if the split directions are */
178 /* the same, so we have to see if either of the neighboring */
179 /* points is also inside the search triangle. */
180
181 ignore_sides = 0;
182
183 if (IsSplit(tp))
184 {
185 if (!TTMaskHasType(mask, SplitLeftType(tp)))
186 ignore_sides |= IGNORE_LEFT;
187 if (!TTMaskHasType(mask, SplitRightType(tp)))
188 ignore_sides |= IGNORE_RIGHT;
189
190 tpt = TiGetTypeExact(tp);
191 if ((tpt & TT_DIRECTION) == (ttype & TT_DIRECTION))
192 {
193 f3 = (LEFT(tp) > MINFINITY + 2) ?
194 ((dlong)(rect->r_xtop - LEFT(tp)) * rheight) : DLONG_MAX;
195 f4 = (RIGHT(tp) < INFINITY - 2) ?
196 ((dlong)(RIGHT(tp) - rect->r_xbot) * rheight) : DLONG_MAX;
197
198 if (ttype & TT_SIDE)
199 {
200 /* Ignore sub-integer slivers */
201 if (f4 != DLONG_MAX) f4 -= rmax;
202 if (f3 != DLONG_MAX) f3 += rmax;
203
204 if (ttype & TT_DIRECTION)
205 {
206 if ((f2 < f3) && (f1 > f4))
207 /* Tile bottom left is outside search area */
208 ignore_sides |= IGNORE_LEFT;
209 }
210 else
211 {
212 if ((f1 < f3) && (f2 > f4))
213 /* Tile top left is outside search area */
214 ignore_sides |= IGNORE_LEFT;
215 }
216 }
217 else
218 {
219 /* Ignore sub-integer slivers */
220 if (f4 != DLONG_MAX) f4 += rmax;
221 if (f3 != DLONG_MAX) f3 -= rmax;
222
223 if (ttype & TT_DIRECTION)
224 {
225 if ((f2 > f3) && (f1 < f4))
226 /* Tile top right is outside search area */
227 ignore_sides |= IGNORE_RIGHT;
228 }
229 else
230 {
231 if ((f1 > f3) && (f2 < f4))
232 /* Tile bottom right is outside search area */
233 ignore_sides |= IGNORE_RIGHT;
234 }
235 }
236 }
237
238 /* If the tile is larger than the search area or overlaps */
239 /* the search area, we need to check if one of the sides */
240 /* of the tile is disjoint from the search area. */
241
242 rheight = TOP(tp) - BOTTOM(tp);
243 rwidth = RIGHT(tp) - LEFT(tp);
244 rmax = MAX(rheight, rwidth);
245 f1 = (TOP(tp) < INFINITY - 2) ?
246 ((dlong)(TOP(tp) - rect->r_ybot) * rwidth) : DLONG_MAX;
247 f2 = (BOTTOM(tp) > MINFINITY + 2) ?
248 ((dlong)(rect->r_ytop - BOTTOM(tp)) * rwidth) : DLONG_MAX;
249 f3 = (RIGHT(tp) < INFINITY - 2) ?
250 ((dlong)(RIGHT(tp) - rect->r_xtop) * rheight) : DLONG_MAX;
251 f4 = (LEFT(tp) > MINFINITY + 2) ?
252 ((dlong)(rect->r_xbot - LEFT(tp)) * rheight) : DLONG_MAX;
253
254 /* ignore sub-integer slivers */
255 if (f4 < DLONG_MAX) f4 += rmax;
256 if (f3 < DLONG_MAX) f3 += rmax;
257
258 if (SplitDirection(tp) ? (f1 < f4) : (f2 < f4))
259 ignore_sides |= IGNORE_LEFT;
260
261 if (SplitDirection(tp) ? (f2 < f3) : (f1 < f3))
262 ignore_sides |= IGNORE_RIGHT;
263
264 /* May call function twice to paint both sides of */
265 /* the split tile, if necessary. */
266
267 if (!(ignore_sides & IGNORE_LEFT))
268 {
269 TiSetBody(tp, (ClientData)(tpt & ~TT_SIDE)); /* bit clear */
270 if ((*func)(tp, arg)) return (1);
271 }
272 if (!(ignore_sides & IGNORE_RIGHT))
273 {
274 TiSetBody(tp, (ClientData)(tpt | TT_SIDE)); /* bit set */
275 if ((*func)(tp, arg)) return (1);
276 }
277 }
278 else
279 if (TTMaskHasType(mask, TiGetType(tp)) && (*func)(tp, arg))
280 return (1);
281
282 enum_next:
283 tpnew = TR(tp);
284 if (LEFT(tpnew) < rect->r_xtop)
285 {
286 while (BOTTOM(tpnew) >= rect->r_ytop) tpnew = LB(tpnew);
287 if (BOTTOM(tpnew) >= BOTTOM(tp) || BOTTOM(tp) <= rect->r_ybot)
288 {
289 tp = tpnew;
290 goto nm_enum;
291 }
292 }
293
294 /* Each iteration returns one tile further to the left */
295 while (LEFT(tp) > rect->r_xbot)
296 {
297 if (BOTTOM(tp) <= rect->r_ybot)
298 return (0);
299 tpnew = LB(tp);
300 tp = BL(tp);
301 if (BOTTOM(tpnew) >= BOTTOM(tp) || BOTTOM(tp) <= rect->r_ybot)
302 {
303 tp = tpnew;
304 goto nm_enum;
305 }
306 }
307
308 /* At left edge -- walk down to next tile along the left edge */
309 for (tp = LB(tp); RIGHT(tp) <= rect->r_xbot; tp = TR(tp))
310 /* Nothing */;
311 }
312 return (0);
313 }
314
315
316 /*
317 * --------------------------------------------------------------------
318 *
319 * DBSrPaintArea --
320 *
321 * Find all tiles overlapping a given area whose types are contained
322 * in the mask supplied. Apply the given procedure to each such tile.
323 * The procedure should be of the following form:
324 *
325 * int
326 * func(tile, cdata)
327 * Tile *tile;
328 * ClientData cdata;
329 * {
330 * }
331 *
332 * Func normally should return 0. If it returns 1 then the search
333 * will be aborted. WARNING: THE CALLED PROCEDURE MAY NOT MODIFY
334 * THE PLANE BEING SEARCHED!!!
335 *
336 * NOTE:
337 *
338 * Results:
339 * 0 is returned if the search completed normally. 1 is returned
340 * if it aborted.
341 *
342 * Side effects:
343 * Whatever side effects result from application of the
344 * supplied procedure.
345 *
346 * --------------------------------------------------------------------
347 */
348
349 int
DBSrPaintArea(hintTile,plane,rect,mask,func,arg)350 DBSrPaintArea(hintTile, plane, rect, mask, func, arg)
351 Tile *hintTile; /* Tile at which to begin search, if not NULL.
352 * If this is NULL, use the hint tile supplied
353 * with plane.
354 */
355 Plane *plane; /* Plane in which tiles lie. This is used to
356 * provide a hint tile in case hintTile == NULL.
357 * The hint tile in the plane is updated to be
358 * the last tile visited in the area
359 * enumeration.
360 */
361 Rect *rect; /* Area to search. This area should not be
362 * degenerate. Tiles must OVERLAP the area.
363 */
364 TileTypeBitMask *mask; /* Mask of those paint tiles to be passed to
365 * func.
366 */
367 int (*func)(); /* Function to apply at each tile */
368 ClientData arg; /* Additional argument to pass to (*func)() */
369 {
370 Point start;
371 Tile *tp, *tpnew;
372
373 start.p_x = rect->r_xbot;
374 start.p_y = rect->r_ytop - 1;
375 tp = hintTile ? hintTile : plane->pl_hint;
376 GOTOPOINT(tp, &start);
377
378 /* Each iteration visits another tile on the LHS of the search area */
379 while (TOP(tp) > rect->r_ybot)
380 {
381 /* Each iteration enumerates another tile */
382 enumerate:
383 plane->pl_hint = tp;
384 if (SigInterruptPending)
385 return (1);
386
387 /* Only perform func() on diagonal tiles if the mask includes the */
388 /* tile type for either the left or right sides of the tile (could */
389 /* also use top and bottom)---by definition, opposite sides must */
390 /* be the two tile types defined by the diagonal split. */
391 if (IsSplit(tp))
392 {
393 /* May call function twice to paint both sides of */
394 /* the split tile, if necessary. */
395
396 /* f1 to f4 are used to find if the search box rect */
397 /* is completely outside the triangle. If so, do */
398 /* not call the function func(). */
399
400 /* Watch for calculations involving (M)INFINITY */
401
402 int theight, twidth;
403 dlong f1, f2, f3, f4;
404
405 theight = TOP(tp) - BOTTOM(tp);
406 twidth = RIGHT(tp) - LEFT(tp);
407 f1 = (rect->r_ybot > MINFINITY + 2) ?
408 (dlong)(TOP(tp) - rect->r_ybot) * twidth : DLONG_MAX;
409 f2 = (rect->r_ytop < INFINITY - 2) ?
410 (dlong)(rect->r_ytop - BOTTOM(tp)) * twidth : DLONG_MAX;
411
412 if (TTMaskHasType(mask, SplitLeftType(tp)))
413 {
414 /* !Outside-of-triangle check */
415 f4 = (rect->r_xbot > MINFINITY + 2) ?
416 (dlong)(rect->r_xbot - LEFT(tp)) * theight : DLONG_MIN;
417 if (SplitDirection(tp) ? (f1 > f4) : (f2 > f4))
418 {
419 TiSetBody(tp, (ClientData)((TileType)TiGetBody(tp)
420 & ~TT_SIDE)); /* bit clear */
421 if ((*func)(tp, arg)) return (1);
422 }
423 }
424
425 if (TTMaskHasType(mask, SplitRightType(tp)))
426 {
427 /* !Outside-of-triangle check */
428 f3 = (rect->r_xtop < INFINITY - 2) ?
429 (dlong)(RIGHT(tp) - rect->r_xtop) * theight : DLONG_MIN;
430 if (SplitDirection(tp) ? (f2 > f3) : (f1 > f3))
431 {
432 TiSetBody(tp, (ClientData)((TileType)TiGetBody(tp)
433 | TT_SIDE)); /* bit set */
434 if ((*func)(tp, arg)) return (1);
435 }
436 }
437 }
438 else
439 if (TTMaskHasType(mask, TiGetType(tp)) && (*func)(tp, arg))
440 return (1);
441
442 tpnew = TR(tp);
443 if (LEFT(tpnew) < rect->r_xtop)
444 {
445 while (BOTTOM(tpnew) >= rect->r_ytop) tpnew = LB(tpnew);
446 if (BOTTOM(tpnew) >= BOTTOM(tp) || BOTTOM(tp) <= rect->r_ybot)
447 {
448 tp = tpnew;
449 goto enumerate;
450 }
451 }
452
453 /* Each iteration returns one tile further to the left */
454 while (LEFT(tp) > rect->r_xbot)
455 {
456 if (BOTTOM(tp) <= rect->r_ybot)
457 return (0);
458 tpnew = LB(tp);
459 tp = BL(tp);
460 if (BOTTOM(tpnew) >= BOTTOM(tp) || BOTTOM(tp) <= rect->r_ybot)
461 {
462 tp = tpnew;
463 goto enumerate;
464 }
465 }
466
467 /* At left edge -- walk down to next tile along the left edge */
468 for (tp = LB(tp); RIGHT(tp) <= rect->r_xbot; tp = TR(tp))
469 /* Nothing */;
470 }
471 return (0);
472 }
473
474
475 /*
476 * --------------------------------------------------------------------
477 *
478 * DBSrPaintClient --
479 *
480 * Find all tiles overlapping a given area whose types are contained
481 * in the mask supplied, and whose ti_client field matches 'client'.
482 * Apply the given procedure to each such tile. The procedure should
483 * be of the following form:
484 *
485 * int
486 * func(tile, cdata)
487 * Tile *tile;
488 * ClientData cdata;
489 * {
490 * }
491 *
492 * Func normally should return 0. If it returns 1 then the search
493 * will be aborted.
494 *
495 * Results:
496 * 0 is returned if the search completed normally. 1 is returned
497 * if it aborted.
498 *
499 * Side effects:
500 * Whatever side effects result from application of the
501 * supplied procedure.
502 *
503 * --------------------------------------------------------------------
504 */
505
506 int
DBSrPaintClient(hintTile,plane,rect,mask,client,func,arg)507 DBSrPaintClient(hintTile, plane, rect, mask, client, func, arg)
508 Tile *hintTile; /* Tile at which to begin search, if not NULL.
509 * If this is NULL, use the hint tile supplied
510 * with plane.
511 */
512 Plane *plane; /* Plane in which tiles lie. This is used to
513 * provide a hint tile in case hintTile == NULL.
514 * The hint tile in the plane is updated to be
515 * the last tile visited in the area
516 * enumeration.
517 */
518 Rect *rect; /* Area to search. This area should not be
519 * degenerate. Tiles must OVERLAP the area.
520 */
521 TileTypeBitMask *mask; /* Mask of those paint tiles to be passed to
522 * func.
523 */
524 ClientData client; /* The ti_client field of each tile must
525 * match this.
526 */
527 int (*func)(); /* Function to apply at each tile */
528 ClientData arg; /* Additional argument to pass to (*func)() */
529 {
530 Point start;
531 Tile *tp, *tpnew;
532
533 start.p_x = rect->r_xbot;
534 start.p_y = rect->r_ytop - 1;
535 tp = hintTile ? hintTile : plane->pl_hint;
536 GOTOPOINT(tp, &start);
537
538 /* Each iteration visits another tile on the LHS of the search area */
539 while (TOP(tp) > rect->r_ybot)
540 {
541 /* Each iteration enumerates another tile */
542 enumerate:
543 plane->pl_hint = tp;
544 if (SigInterruptPending)
545 return (1);
546
547 /* Only perform func() on diagonal tiles if the mask includes the */
548 /* tile type for either the left or right sides of the tile (could */
549 /* also use top and bottom)---by definition, opposite sides must */
550 /* be the two tile types defined by the diagonal split. */
551 if (IsSplit(tp))
552 {
553 /* May call function twice to paint both sides of */
554 /* the split tile, if necessary. */
555
556 /* f1 to f4 are used to find if the search box rect */
557 /* is completely outside the triangle. If so, do */
558 /* not call the function func(). */
559
560 /* Watch for calculations involving (M)INFINITY */
561
562 int theight, twidth;
563 dlong f1, f2, f3, f4;
564
565 theight = TOP(tp) - BOTTOM(tp);
566 twidth = RIGHT(tp) - LEFT(tp);
567 f1 = (rect->r_ybot > MINFINITY + 2) ?
568 (TOP(tp) - rect->r_ybot) * twidth : DLONG_MAX;
569 f2 = (rect->r_ytop < INFINITY - 2) ?
570 (rect->r_ytop - BOTTOM(tp)) * twidth : DLONG_MAX;
571
572 if (TTMaskHasType(mask, SplitLeftType(tp)))
573 {
574 /* !Outside-of-triangle check */
575 f4 = (rect->r_xbot > MINFINITY + 2) ?
576 (rect->r_xbot - LEFT(tp)) * theight : DLONG_MIN;
577 if (SplitDirection(tp) ? (f1 > f4) : (f2 > f4))
578 {
579 TiSetBody(tp, (ClientData)((TileType)TiGetBody(tp)
580 & ~TT_SIDE)); /* bit clear */
581 if ((tp->ti_client == client) && (*func)(tp, arg))
582 return (1);
583 }
584 }
585
586 if (TTMaskHasType(mask, SplitRightType(tp)))
587 {
588 /* !Outside-of-triangle check */
589 f3 = (rect->r_xtop < INFINITY - 2) ?
590 (RIGHT(tp) - rect->r_xtop) * theight : DLONG_MIN;
591 if (SplitDirection(tp) ? (f2 > f3) : (f1 > f3))
592 {
593 TiSetBody(tp, (ClientData)((TileType)TiGetBody(tp)
594 | TT_SIDE)); /* bit set */
595 if ((tp->ti_client == client) && (*func)(tp, arg))
596 return (1);
597 }
598 }
599 }
600 else
601 if (TTMaskHasType(mask, TiGetType(tp)) && tp->ti_client == client
602 && (*func)(tp, arg))
603 return (1);
604
605 tpnew = TR(tp);
606 if (LEFT(tpnew) < rect->r_xtop)
607 {
608 while (BOTTOM(tpnew) >= rect->r_ytop) tpnew = LB(tpnew);
609 if (BOTTOM(tpnew) >= BOTTOM(tp) || BOTTOM(tp) <= rect->r_ybot)
610 {
611 tp = tpnew;
612 goto enumerate;
613 }
614 }
615
616 /* Each iteration returns one tile further to the left */
617 while (LEFT(tp) > rect->r_xbot)
618 {
619 if (BOTTOM(tp) <= rect->r_ybot)
620 return (0);
621 tpnew = LB(tp);
622 tp = BL(tp);
623 if (BOTTOM(tpnew) >= BOTTOM(tp) || BOTTOM(tp) <= rect->r_ybot)
624 {
625 tp = tpnew;
626 goto enumerate;
627 }
628 }
629
630 /* At left edge -- walk down to next tile along the left edge */
631 for (tp = LB(tp); RIGHT(tp) <= rect->r_xbot; tp = TR(tp))
632 /* Nothing */;
633 }
634 return (0);
635 }
636
637 /*
638 * --------------------------------------------------------------------
639 *
640 * DBResetTilePlane --
641 *
642 * Reset the ti_client fields of all tiles in a paint tile plane to
643 * the value 'cdata'.
644 *
645 * Results:
646 * None.
647 *
648 * Side effects:
649 * Resets the ti_client fields of all tiles.
650 *
651 * --------------------------------------------------------------------
652 */
653
654 void
DBResetTilePlane(plane,cdata)655 DBResetTilePlane(plane, cdata)
656 Plane *plane; /* Plane whose tiles are to be reset */
657 ClientData cdata;
658 {
659 Tile *tp, *tpnew;
660 Rect *rect = &TiPlaneRect;
661
662 /* Start with the leftmost non-infinity tile in the plane */
663 tp = TR(plane->pl_left);
664
665 /* Each iteration visits another tile on the LHS of the search area */
666 while (TOP(tp) > rect->r_ybot)
667 {
668 /* Each iteration frees another tile */
669 enumerate:
670 tp->ti_client = cdata;
671
672 /* Move along to the next tile */
673 tpnew = TR(tp);
674 if (LEFT(tpnew) < rect->r_xtop)
675 {
676 while (BOTTOM(tpnew) >= rect->r_ytop) tpnew = LB(tpnew);
677 if (BOTTOM(tpnew) >= BOTTOM(tp) || BOTTOM(tp) <= rect->r_ybot)
678 {
679 tp = tpnew;
680 goto enumerate;
681 }
682 }
683
684 /* Each iteration returns one tile further to the left */
685 while (LEFT(tp) > rect->r_xbot)
686 {
687 if (BOTTOM(tp) <= rect->r_ybot)
688 return;
689 tpnew = LB(tp);
690 tp = BL(tp);
691 if (BOTTOM(tpnew) >= BOTTOM(tp) || BOTTOM(tp) <= rect->r_ybot)
692 {
693 tp = tpnew;
694 goto enumerate;
695 }
696 }
697
698 /* At left edge -- walk down to next tile along the left edge */
699 for (tp = LB(tp); RIGHT(tp) <= rect->r_xbot; tp = TR(tp))
700 /* Nothing */;
701 }
702 }
703
704 /*
705 * --------------------------------------------------------------------
706 *
707 * DBFreePaintPlane --
708 *
709 * Deallocate all tiles in a paint tile plane of a given CellDef.
710 * Don't deallocate the four boundary tiles, or the plane itself.
711 *
712 * This is a procedure internal to the database. The only reason
713 * it lives in DBtiles.c rather than DBcellsubr.c is that it requires
714 * intimate knowledge of the contents of paint tiles and tile planes.
715 *
716 * Results:
717 * None.
718 *
719 * Side effects:
720 * Deallocates a lot of memory.
721 *
722 * *** WARNING ***
723 *
724 * This procedure uses a carfully constructed non-recursive area
725 * enumeration algorithm. Care is taken to not access a tile that has
726 * been deallocated. The only exception is for a tile that has just been
727 * passed to free(), but no more calls to free() or malloc() have been made.
728 * Magic's malloc allows this.
729 *
730 * --------------------------------------------------------------------
731 */
732
733 void
DBFreePaintPlane(plane)734 DBFreePaintPlane(plane)
735 Plane *plane; /* Plane whose storage is to be freed */
736 {
737 Tile *tp, *tpnew;
738 Rect *rect = &TiPlaneRect;
739
740 /* Start with the bottom-right non-infinity tile in the plane */
741 tp = BL(plane->pl_right);
742
743 /* Each iteration visits another tile on the RHS of the search area */
744 while (BOTTOM(tp) < rect->r_ytop)
745 {
746 enumerate:
747
748 #define CLIP_TOP(t) (MIN(TOP(t),rect->r_ytop))
749
750 /* Move along to the next tile to the left */
751 if (LEFT(tp) > rect->r_xbot)
752 {
753 tpnew = BL(tp);
754 while (TOP(tpnew) <= rect->r_ybot) tpnew = RT(tpnew);
755 if (CLIP_TOP(tpnew) <= CLIP_TOP(tp))
756 {
757 tp = tpnew;
758 goto enumerate;
759 }
760 }
761
762 /* Each iteration returns one tile further to the right */
763 while (RIGHT(tp) < rect->r_xtop)
764 {
765 TiFree(tp);
766 tpnew = RT(tp);
767 tp = TR(tp);
768 if (CLIP_TOP(tpnew) <= CLIP_TOP(tp) && BOTTOM(tpnew) < rect->r_ytop)
769 {
770 tp = tpnew;
771 goto enumerate;
772 }
773 }
774
775 TiFree(tp);
776 /* At right edge -- walk up to next tile along the right edge */
777 tp = RT(tp);
778 if (BOTTOM(tp) < rect->r_ytop) {
779 while(LEFT(tp) >= rect->r_xtop) tp = BL(tp);
780 }
781 }
782 }
783
784 /*
785 * --------------------------------------------------------------------
786 *
787 * DBClearCellPlane --
788 *
789 * Removes all CellUses from a def's cell plane. Does not remove the
790 * cell plane itself.
791 *
792 * Results:
793 * None.
794 *
795 * Side effects:
796 * Deallocates a lot of memory.
797 *
798 * --------------------------------------------------------------------
799 */
800
801 void
DBClearCellPlane(def)802 DBClearCellPlane(def)
803 CellDef *def;
804 {
805 int dbDeleteCellUse(); /* Forward reference */
806
807 /* Don't let this search be interrupted. */
808 SigDisableInterrupts();
809
810 /* Remove everything from the BPlane */
811 /* Do not use BPDelete() inside a BPEnum loop. Use DBSrCellUses */
812 /* to get a linked list of cell instances, then remove each one. */
813
814 DBSrCellUses(def, dbDeleteCellUse, (ClientData)def);
815
816 SigEnableInterrupts();
817 }
818
819 /*
820 * --------------------------------------------------------------------
821 *
822 * dbDeleteCellUse ---
823 *
824 * Callback function from DBSrCellUses, calls BPDelete to remove a
825 * cell use from the cell plane
826 *
827 * --------------------------------------------------------------------
828 */
829
dbDeleteCellUse(CellUse * use,ClientData arg)830 int dbDeleteCellUse(CellUse *use, ClientData arg)
831 {
832 CellDef *def = (CellDef *)arg;
833 CellUse *defuses, *lastuse;
834
835 dbInstanceUnplace(use);
836
837 if (UndoIsEnabled())
838 DBUndoCellUse(use, UNDO_CELL_DELETE);
839
840 /* Remove use from cd_parents of the use's def */
841 lastuse = (CellUse *)NULL;
842 for (defuses = use->cu_def->cd_parents; defuses ; defuses = defuses->cu_nextuse)
843 {
844 if (defuses == use)
845 {
846 if (lastuse)
847 lastuse->cu_nextuse = defuses->cu_nextuse;
848 else
849 use->cu_def->cd_parents = defuses->cu_nextuse;
850 defuses->cu_nextuse = (CellUse *)NULL;
851 break;
852 }
853 lastuse = defuses;
854 }
855 if (use->cu_id) freeMagic(use->cu_id);
856 freeMagic(use);
857
858 return 0;
859 }
860
861
862 /*
863 * --------------------------------------------------------------------
864 *
865 * DBCheckMaxHStrips --
866 *
867 * Check the maximal horizontal strip property for the
868 * tile plane 'plane' over the area 'area'.
869 *
870 * Results:
871 * Normally returns 0; returns 1 if the procedure
872 * (*proc)() returned 1 or if the search were
873 * aborted with an interrupt.
874 *
875 * Side effects:
876 * Calls the procedure (*proc)() for each offending tile.
877 * This procedure should have the following form:
878 *
879 * int
880 * proc(tile, side, cdata)
881 * Tile *tile;
882 * int side;
883 * ClientData cdata;
884 * {
885 * }
886 *
887 * The client data is the argument 'cdata' passed to us.
888 * The argument 'side' is one of GEO_NORTH, GEO_SOUTH,
889 * GEO_EAST, or GEO_WEST, and indicates which side of
890 * the tile the strip property was violated on.
891 * If (*proc)() returns 1, we abort and return 1
892 * to our caller.
893 *
894 * --------------------------------------------------------------------
895 */
896
897 int
DBCheckMaxHStrips(plane,area,proc,cdata)898 DBCheckMaxHStrips(plane, area, proc, cdata)
899 Plane *plane; /* Search this plane */
900 Rect *area; /* Process all tiles in this area */
901 int (*proc)(); /* Filter procedure: see above */
902 ClientData cdata; /* Passed to (*proc)() */
903 {
904 struct dbCheck dbc;
905
906 dbc.dbc_proc = proc;
907 dbc.dbc_area = *area;
908 dbc.dbc_cdata = cdata;
909 return (DBSrPaintArea((Tile *) NULL, plane, area,
910 &DBAllTypeBits, dbCheckMaxHFunc, (ClientData) &dbc));
911 }
912
913 /*
914 * dbCheckMaxHFunc --
915 *
916 * Filter function for above.
917 * See the description at the top.
918 */
919
920 int
dbCheckMaxHFunc(tile,dbc)921 dbCheckMaxHFunc(tile, dbc)
922 Tile *tile;
923 struct dbCheck *dbc;
924 {
925 Tile *tp;
926
927 /*
928 * Property 1:
929 * No tile to the left or to the right should have the same
930 * type as 'tile'.
931 */
932 if (RIGHT(tile) < dbc->dbc_area.r_xtop)
933 for (tp = TR(tile); TOP(tp) > BOTTOM(tile); tp = LB(tp))
934 if (TiGetType(tp) == TiGetType(tile))
935 if ((*dbc->dbc_proc)(tile, GEO_EAST, dbc->dbc_cdata))
936 return (1);
937 if (LEFT(tile) > dbc->dbc_area.r_xbot)
938 for (tp = BL(tile); BOTTOM(tp) < TOP(tile); tp = RT(tp))
939 if (TiGetType(tp) == TiGetType(tile))
940 if ((*dbc->dbc_proc)(tile, GEO_WEST, dbc->dbc_cdata))
941 return (1);
942
943 /*
944 * Property 2:
945 * No tile to the top or bottom should be of the same type and
946 * have the same width.
947 */
948 if (TOP(tile) < dbc->dbc_area.r_ytop)
949 {
950 tp = RT(tile);
951 if (TiGetType(tp) == TiGetType(tile)
952 && LEFT(tp) == LEFT(tile)
953 && RIGHT(tp) == RIGHT(tile))
954 if ((*dbc->dbc_proc)(tile, GEO_NORTH, dbc->dbc_cdata))
955 return (1);
956 }
957 if (BOTTOM(tile) > dbc->dbc_area.r_ybot)
958 {
959 tp = LB(tile);
960 if (TiGetType(tp) == TiGetType(tile)
961 && LEFT(tp) == LEFT(tile)
962 && RIGHT(tp) == RIGHT(tile))
963 if ((*dbc->dbc_proc)(tile, GEO_SOUTH, dbc->dbc_cdata))
964 return (1);
965 }
966
967 return (0);
968 }
969
970 /*
971 * --------------------------------------------------------------------
972 *
973 * DBCheckMaxVStrips --
974 *
975 * Check the maximal vertical strip property for the
976 * tile plane 'plane' over the area 'area'.
977 *
978 * Results:
979 * Normally returns 0; returns 1 if the procedure
980 * (*proc)() returned 1 or if the search were
981 * aborted with an interrupt.
982 *
983 * Side effects:
984 * See DBCheckMaxHStrips() above.
985 *
986 * --------------------------------------------------------------------
987 */
988
989 int
DBCheckMaxVStrips(plane,area,proc,cdata)990 DBCheckMaxVStrips(plane, area, proc, cdata)
991 Plane *plane; /* Search this plane */
992 Rect *area; /* Process all tiles in this area */
993 int (*proc)(); /* Filter procedure: see above */
994 ClientData cdata; /* Passed to (*proc)() */
995 {
996 struct dbCheck dbc;
997
998 dbc.dbc_proc = proc;
999 dbc.dbc_area = *area;
1000 dbc.dbc_cdata = cdata;
1001 return (DBSrPaintArea((Tile *) NULL, plane, area,
1002 &DBAllTypeBits, dbCheckMaxVFunc, (ClientData) &dbc));
1003 }
1004
1005 /*
1006 * dbCheckMaxVFunc --
1007 *
1008 * Filter function for above.
1009 * See the description at the top.
1010 */
1011
1012 int
dbCheckMaxVFunc(tile,dbc)1013 dbCheckMaxVFunc(tile, dbc)
1014 Tile *tile;
1015 struct dbCheck *dbc;
1016 {
1017 Tile *tp;
1018
1019 /*
1020 * Property 1:
1021 * No tile to the top or to the bottom should have the same
1022 * type as 'tile'.
1023 */
1024 if (TOP(tile) < dbc->dbc_area.r_ytop)
1025 for (tp = RT(tile); RIGHT(tp) > LEFT(tile); tp = BL(tp))
1026 if (TiGetType(tp) == TiGetType(tile))
1027 if ((*dbc->dbc_proc)(tile, GEO_NORTH, dbc->dbc_cdata))
1028 return (1);
1029 if (BOTTOM(tile) > dbc->dbc_area.r_ybot)
1030 for (tp = LB(tile); LEFT(tp) < RIGHT(tile); tp = TR(tp))
1031 if (TiGetType(tp) == TiGetType(tile))
1032 if ((*dbc->dbc_proc)(tile, GEO_SOUTH, dbc->dbc_cdata))
1033 return (1);
1034
1035 /*
1036 * Property 2:
1037 * No tile to the left or right should be of the same type and
1038 * have the same height.
1039 */
1040 if (RIGHT(tile) < dbc->dbc_area.r_xtop)
1041 {
1042 tp = TR(tile);
1043 if (TiGetType(tp) == TiGetType(tile)
1044 && BOTTOM(tp) == BOTTOM(tile)
1045 && TOP(tp) == TOP(tile))
1046 if ((*dbc->dbc_proc)(tile, GEO_EAST, dbc->dbc_cdata))
1047 return (1);
1048 }
1049 if (LEFT(tile) > dbc->dbc_area.r_xbot)
1050 {
1051 tp = BL(tile);
1052 if (TiGetType(tp) == TiGetType(tile)
1053 && BOTTOM(tp) == BOTTOM(tile)
1054 && TOP(tp) == TOP(tile))
1055 if ((*dbc->dbc_proc)(tile, GEO_WEST, dbc->dbc_cdata))
1056 return (1);
1057 }
1058
1059 return (0);
1060 }
1061
1062