/* * DBcellsel.c -- * * Cell selection. * * ********************************************************************* * * Copyright (C) 1985, 1990 Regents of the University of California. * * * Permission to use, copy, modify, and distribute this * * * software and its documentation for any purpose and without * * * fee is hereby granted, provided that the above copyright * * * notice appear in all copies. The University of California * * * makes no representations about the suitability of this * * * software for any purpose. It is provided "as is" without * * * express or implied warranty. Export of this software outside * * * of the United States of America may require an export license. * * ********************************************************************* */ #ifndef lint static char rcsid[] __attribute__ ((unused)) = "$Header: /usr/cvsroot/magic-8.0/database/DBcellsel.c,v 1.1.1.1 2008/02/03 20:43:50 tim Exp $"; #endif /* not lint */ #include #include #include "utils/magic.h" #include "utils/geometry.h" #include "tiles/tile.h" #include "utils/hash.h" #include "database/database.h" #include "database/databaseInt.h" #include "utils/utils.h" struct selectArg { int csa_xmask; /* Only the contents of uses whose * expand masks match csa_xmask are * visible. */ CellUse *csa_lastuse; /* Last cell selected */ Point csa_lastp; /* X, Y indices of csa_lastuse */ bool csa_sawlast; /* TRUE if csa_lastuse has been visited * in this pass. */ CellUse *csa_retuse; /* Cell we will return as selected */ CellUse *csa_bestuse; /* Best candidate seen in this pass */ Point *csa_bestp; /* X, Y indices of csa_bestuse */ Transform *csa_besttrans; /* Points to a Transform that will be * set to the transform from the parent * of csa_bestuse to the root use. */ TerminalPath *csa_bestpath; /* Pathname of best candidate found */ TerminalPath csa_curpath; /* Current candidate's pathname */ }; /* Forward declarations */ int dbSelectCellSr(); /* * ---------------------------------------------------------------------------- * * DBSelectCell -- * * Select the next cell containing a given point. * * Results: * Returns a pointer to the next CellUse containing the given * point, or NULL if we have visited all CellUses containing it. * The ordering of CellUses visited is smallest in area to largest. * Both expanded cells, and unexpanded cells all of whose parents * are expanded, are returned. * * Side effects: * Sets *transform to be the transform from coordinates of * the CellUse's definition to those of the root cell use. * Sets *selp to be the x and y array indices of the selected cell. * Returns path in the argument "tpath". * * ---------------------------------------------------------------------------- */ CellUse * DBSelectCell(rootUse, lastUse, lastP, rootRect, xMask, transform, selp, tpath) CellUse *rootUse; /* Root cell use for the search (usually * that of the window containing the point * tool). The pathname we construct into * tpath will be relative to this use. */ CellUse *lastUse; /* Pointer to last CellUse returned by * DBSelectCell(). This is only used when * stepping through multiple overlapping * cells. */ Point *lastP; /* X, Y array indices of last cell selected */ Rect *rootRect; /* Box around point tool in coordinates of * the parent def of rootUse. */ int xMask; /* Expand bit mask for determining whether * a cell is expanded or not. */ Transform *transform; /* Transform set by DBSelectCell, from * coordinates of the returned CellUse's * definition to those of the rootUse's * def. */ Point *selp; /* X, Y array indices of the selected cell, * also set by DBSelectCell. */ TerminalPath *tpath; /* Set to contain the use id of selected cell */ { int xlo, xhi, ylo, yhi, xbase, ybase, xsep, ysep; char currentId[BUFSIZ]; SearchContext scontext; struct selectArg arg; arg.csa_curpath.tp_first = arg.csa_curpath.tp_next = currentId; arg.csa_curpath.tp_last = ¤tId[sizeof currentId - 2]; currentId[0] = '\0'; arg.csa_xmask = xMask; arg.csa_lastp = *lastP; arg.csa_sawlast = FALSE; arg.csa_retuse = (CellUse *) NULL; arg.csa_lastuse = (CellUse *) NULL; /* * Sanity check in case lastUse has somehow been freed * prior to our being called. */ if (lastUse && lastUse->cu_def) arg.csa_lastuse = lastUse; arg.csa_besttrans = transform; arg.csa_bestp = selp; arg.csa_bestuse = (CellUse *) NULL; arg.csa_bestpath = tpath; DBArrayOverlap(rootUse, rootRect, &xlo, &xhi, &ylo, &yhi); scontext.scx_use = rootUse; scontext.scx_area = *rootRect; xsep = (rootUse->cu_xlo>rootUse->cu_xhi)?-rootUse->cu_xsep:rootUse->cu_xsep; ysep = (rootUse->cu_ylo>rootUse->cu_yhi)?-rootUse->cu_ysep:rootUse->cu_ysep; for (scontext.scx_y = ylo; scontext.scx_y <= yhi; scontext.scx_y++) { for (scontext.scx_x = xlo; scontext.scx_x <= xhi; scontext.scx_x++) { xbase = xsep * (scontext.scx_x - rootUse->cu_xlo); ybase = ysep * (scontext.scx_y - rootUse->cu_ylo); GeoTransTranslate(xbase, ybase, &GeoIdentityTransform, &scontext.scx_trans); (void) dbSelectCellSr(&scontext, &arg); if (arg.csa_retuse != (CellUse *) NULL) break; } } return (arg.csa_bestuse); } /* * Sets arg->csa_retuse if we've found the next use. This enables us * to short-circuit the remainder of the tree search (it has now been * changed to abort the search). * * Sets arg->csa_bestuse to point to the best candidate yet found * for being the next CellUse. Sets arg->csa_sawlast to TRUE once * arg->csa_lastuse has been seen. */ int dbSelectCellSr(scx, arg) SearchContext *scx; /* Context describing the cell use, the * x and y array element under consider- * ation, the area surrounding the * selection point in coordinates of * the def of the cell use, and a * transform back to the "root". */ struct selectArg *arg; /* Client data */ { /* BY NP */ dlong childArea, bestArea, lastArea; TerminalPath *cpath = &arg->csa_curpath; char *savenext; Rect *pbx; int n; /* * If we have already found the (use, element) to be returned, * prune the search short. */ if (arg->csa_retuse != (CellUse *) NULL) return 1; /* * If this was the (use, element) last returned by DBSelectCell, * we can prune the search not to look at any of its subcells. * Since the area of a parent must be at least as great as the * area of any of its subcells, these subcells must have already * been returned by a previous call to DBSelectCell. */ if (scx->scx_use == arg->csa_lastuse && scx->scx_x == arg->csa_lastp.p_x && scx->scx_y == arg->csa_lastp.p_y) { arg->csa_sawlast = TRUE; return 0; } pbx = &scx->scx_use->cu_def->cd_bbox; if (!GEO_OVERLAP((pbx), (&scx->scx_area))) return 0; /* compute childArea (using long long to avoid overflow). */ { int xDiff, yDiff; xDiff = pbx->r_xtop - pbx->r_xbot; yDiff = pbx->r_ytop - pbx->r_ybot; /* BY NP */ childArea = (dlong)xDiff * (dlong)yDiff; } /* Append the use identifier of this instance to the current path */ savenext = arg->csa_curpath.tp_next; if (cpath->tp_next != cpath->tp_first) *cpath->tp_next++ = '/'; n = cpath->tp_last - cpath->tp_next; cpath->tp_next = DBPrintUseId(scx, cpath->tp_next, n, FALSE); /* * Visit all the children of the def for this use first. * If, during the visiting of any of these, we get a non-NULL * arg->csa_retuse value, we can return immediately. */ if (DBDescendSubcell(scx->scx_use, arg->csa_xmask)) { (void) DBCellSrArea(scx, dbSelectCellSr, (ClientData) arg); if (arg->csa_retuse != (CellUse *) NULL) { cpath->tp_next = savenext; *savenext = '\0'; return 1; } } if (arg->csa_lastuse != (CellUse *) NULL) { pbx = &arg->csa_lastuse->cu_def->cd_bbox; /* compute lastArea (using long long to avoid overflow). */ { int xDiff, yDiff; xDiff = pbx->r_xtop - pbx->r_xbot; yDiff = pbx->r_ytop - pbx->r_ybot; /* BY NP */ lastArea = (dlong)xDiff * (dlong)yDiff; } } else /* BY NP */ lastArea = 0; if (arg->csa_sawlast) { /* * We have found a cell with the same area as the last cell * selected, later in the search tree than the last one. * We cut the search short and return this immediately. */ /* BY NP */ if (childArea == lastArea) { arg->csa_bestp->p_x = scx->scx_x; arg->csa_bestp->p_y = scx->scx_y; arg->csa_retuse = arg->csa_bestuse = scx->scx_use; *arg->csa_besttrans = scx->scx_trans; /* Copy current path into best path */ n = arg->csa_bestpath->tp_last - arg->csa_bestpath->tp_next; strncpy(arg->csa_bestpath->tp_next, cpath->tp_first, n); arg->csa_bestpath->tp_next[n] = '\0'; /* Pop last component of current path */ cpath->tp_next = savenext; *savenext = '\0'; /* Abort the search */ return 1; } } /* * We only update our best guess if this cell is larger than * the last one selected. This has the effect of ignoring all * cells already returned by DBSelectCell in previous calls. * * This one might be okay. It is larger than the previous one, but * there may be a smaller one to do first. */ if (childArea > lastArea) { if (arg->csa_bestuse != (CellUse *) NULL) { pbx = &arg->csa_bestuse->cu_def->cd_bbox; /* compute bestArea (using long long to avoid overflow). */ { int xDiff, yDiff; xDiff = pbx->r_xtop - pbx->r_xbot; yDiff = pbx->r_ytop - pbx->r_ybot; bestArea = (dlong)xDiff * (dlong)yDiff; } /* BY NP */ if (childArea >= bestArea) { /* Too big: pop last component of current path */ cpath->tp_next = savenext; *savenext = '\0'; /* Keep going */ return 0; } } arg->csa_bestp->p_x = scx->scx_x; arg->csa_bestp->p_y = scx->scx_y; arg->csa_bestuse = scx->scx_use; *arg->csa_besttrans = scx->scx_trans; /* Copy current path into best path */ n = arg->csa_bestpath->tp_last - arg->csa_bestpath->tp_next; strncpy(arg->csa_bestpath->tp_next, cpath->tp_first, n); arg->csa_bestpath->tp_next[n] = '\0'; } /* Pop last component of current path */ cpath->tp_next = savenext; *savenext = '\0'; return 0; }