/*
 * mzInternal.h --
 *
 * This file defines data structures, variables, and constants internal to
 * the maze router module.
 *
 *
 *
 *     *********************************************************************
 *     * Copyright (C) 1988, 1990 Michael H. Arnold and the 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.    *
 *     *********************************************************************
 *
 *
 * rcsid $Header: /usr/cvsroot/magic-8.0/mzrouter/mzInternal.h,v 1.2 2008/06/01 18:37:44 tim Exp $
 */

#ifndef _MAGIC__MZROUTER__MZINTERNAL_H
#define _MAGIC__MZROUTER__MZINTERNAL_H

/*
 * Structures etc. that are exported by the mzrouter are defined in
 * mzrouter.h.
 *
 *  Structures (etc.) defined here are shared between files in this module.
 *
 *  Structures local to a given source
 *  file are defined at the top of that source file.
 *
 *  Structures specific to a given function are defined at
 *  the head of that function.
 */

#ifndef _MAGIC__UTILS__MAGIC_H
#include "utils/magic.h"
#endif

#ifndef _MAGIC__MZROUTER__MZROUTER_H
#include "mzrouter/mzrouter.h"
#endif

#ifndef _MAGIC__UTILS__HEAP_H
#include "utils/heap.h"
#endif

/* ------------------------ Version String --------------------------- */
#define MZROUTER_VERSION "0.6"

/* ------------------------ Debugging flags ----------------------------- */
extern ClientData mzDebugID;
#include "mzDebug.h"

/* ---------- Default Parameter Values ----------------------------------- */

/* Penalty factor applied to cost estimate in excess of max window bound
 * represented as mantissa / 2**nExponent
 */
/* (2048/2**1 = 1028) */
#define DEF_PENALTY_MANTISSA 2048
#define DEF_PENALTY_NEXPONENT 1

/* Window rate in cost/bloom */
#define DEF_WINDOW_RATE 500

/* Window width in cost */
#define DEF_WINDOW_WIDTH 10000

/* Maximum cost increase allowed during blooming */
#define DEF_BLOOM_DELTA_COST 1

/* minimum radius of blockage plane info required around point being expanded.
 * value of -1 causes mzrouter to compute its own best guess.
 * (Areas twice this size are gened. whenever the minimum is not met.)
 */
#define DEF_BOUNDS_INCREMENT -1

/* If reset, degenerate estimation plane used (just 4 tiles - one for each
 * quadrant with respect to destination point).
 */
#define DEF_ESTIMATE 1
/* If set, routes may start or terminate at any geometry that is
 * electrically connected to specified start or dest regions.
 */
#define DEF_EXPAND_ENDPOINTS 1
#define MZ_EXPAND_START	     INT2CD(1)	/* ClientData type for start tiles */
#define MZ_EXPAND_DEST	     INT2CD(0)  /* ClientData type for dest tiles */
#define MZ_EXPAND_NONE	     CLIENTDEFAULT  /* Normal ClientData type */

/* If set only hints in toplevel cell are recognized - speeds up processing
 * of hint planes when there are lots of expanded subcells.
 */
#define DEF_TOP_HINTS_ONLY 0
/* Maximum distance route can penetrate blocked areas to reach destination.
 * Note only "same node" blockage will be penetrated, i.e. blocks steming from
 * spacing to unrelated nodes are always honored.
 *
 * A value of -1 causes the max penetration to be recomputed prior to each
 * route based on the design rules for the active routetypes.
 */
#define DEF_MAX_WALK_LENGTH -1
/* controls message printing:  0 = errors and warnings only, 1 = brief, 2 =
 * lots of statistics.
 */
#define DEF_VERBOSITY	1
/* if positive, puts upper limit on number of blooms during search.
 * After limit is reached routing is terminated and best complete route
 * to date is returned.
 */
#define DEF_BLOOM_LIMIT	0

/* This struc used to make list of named parameter sets for maze routing.
 * Only the MazeParameters themselves are passed to the routines
 * in this module.
 */
typedef struct mazestyle
{
    char *ms_name;		/* name of style */
    List *ms_spacingL;		/* used to store spacing during tech readin. */
    MazeParameters ms_parms;	/* parameter settings for this style */
    struct mazestyle *ms_next;
} MazeStyle;


/* ----- TileTypes, Paint Tables, and Paint Planes, and Internal Cells  ---- */
/* RESULT CELL */
extern CellDef *mzResultDef;
extern CellUse *mzResultUse;

/* Types are offset to coincide with hint types.
 * This facilitates display for debugging.
 */
#define TT_OFF	(TT_MAGNET - 1)

/* BLOCKAGE PLANES - AND CELL FOR DISPLAY */
/* Higher numbered blockage types ALWAYS take priority during painting */

    /* Start or destination terminal */
#define TT_SAMENODE	  (1 + TT_OFF)
    /* Block due to start or destination terminal */
#define TT_SAMENODE_BLOCK (2 + TT_OFF)
    /* Can reach dest via contact */
#define TT_ABOVE_UD_WALK  (3 + TT_OFF)
#define TT_BELOW_UD_WALK  (4 + TT_OFF)
#define TT_ABOVE_LR_WALK  (5 + TT_OFF)
#define TT_BELOW_LR_WALK  (6 + TT_OFF)
    /* Approach to dest area */
#define TT_LEFT_WALK	  (7 + TT_OFF)
#define TT_RIGHT_WALK     (8 + TT_OFF)
#define TT_TOP_WALK       (9 + TT_OFF)
#define TT_BOTTOM_WALK    (10 + TT_OFF)
    /* route destination area */
#define TT_DEST_AREA      (11 + TT_OFF)
    /* Can't route in this space */
#define	TT_BLOCKED	  (12 + TT_OFF)

#define TT_MAXROUTETYPES (1 + TT_BLOCKED)

extern PaintResultType mzBlockPaintTbl[TT_MAXROUTETYPES][TT_MAXROUTETYPES];
extern CellDef *mzBlockDef ;

/* BOUNDS PLANE */
    /* Blockage planes generated here */
#define TT_INBOUNDS	(1 + TT_OFF)
#define TT_GENBLOCK	(2 + TT_OFF)
extern PaintResultType mzBoundsPaintTbl[TT_MAXROUTETYPES][TT_MAXROUTETYPES];
extern Plane *mzHBoundsPlane;
extern Plane *mzVBoundsPlane;

/* ESTIMATION PLANE */
#define TT_EST_SUBCELL 	(1 + TT_OFF)
#define TT_EST_FENCE 	(2 + TT_OFF)
#define TT_EST_DEST	(3 + TT_OFF)
extern PaintResultType mzEstimatePaintTbl[TT_MAXROUTETYPES][TT_MAXROUTETYPES];
extern Plane *mzEstimatePlane;

/* HINT TYPES */
extern TileTypeBitMask mzHintTypesMask;     /* map of hint, fence
						and rotate types */
extern TileTypeBitMask mzStartTypesMask;    /* mask of valid types for a route start */

/* HINT (magnet) PLANES */
extern Plane *mzHHintPlane;
extern Plane *mzVHintPlane;

/* FENCE PLANE */
extern Plane *mzHFencePlane;

/* ROTATE PLANES */
extern Plane *mzHRotatePlane;
extern Plane *mzVRotatePlane;

/* Number Lines - used to mark points aligned with dest tile corners */
typedef struct numberLine
{
    int		nl_sizeAlloced;  /* Number of entries allocated */
    int		nl_sizeUsed;
    int  	*nl_entries;
} NumberLine;

/*
 * Macros for allocating segments of a RoutePath.
 * During maze-routing, we allocate RoutePaths from our own private area.
 * When the time comes to return a RoutePath, it is copied to permanent
 * storage (i.e., mallocMagic/freeMagic-managed) and the rest of the
 * temporary storage is reclaimed.  This approach avoids the need for
 * additional pointers in each RoutePath that would otherwise be required
 * for storage reclamation.
 */
#define	PATHSPERSEG	200	/* Number of RoutePaths per segment */

typedef struct routePage
{
    struct routePage	*rpp_next;
    int			 rpp_free;
    RoutePath		 rpp_array[PATHSPERSEG];
} RoutePage;

/* First, last, and current RoutePages on list for allocating RoutePaths */
extern RoutePage *mzFirstPage;
extern RoutePage *mzLastPage;
extern RoutePage *mzCurPage;

/* Allocate a new RoutePath */
#define	NEWPATH() \
	((mzCurPage == NULL \
		    || mzCurPage->rpp_free >= PATHSPERSEG) \
	    ? mzAllocRPath() \
	    : (RoutePath *) (&mzCurPage->rpp_array[mzCurPage->rpp_free++]))

/*------------------- Start and Dest Terminals ---------------------------- */
/* A start or destination terminal is a rectangle and a type to connect
 * on. This struct is used to create lists of legal start and destination
 * areas.  (This structure also used in other situations requiring rects
 * with an associated tiletype.)
 */
typedef struct
{
    Rect 	cr_rect;
    TileType	cr_type;
} ColoredRect;

/*----------------------Path Hash Table and Queues ----------------------- */

/*
 * The following hash table is used to index points
 * so that redundant extension from points reached more than once
 * is avoided.
 * It is indexed by (x,y,routeLayer, orientation).  Orientation is either
 * Horizontal, vertical, or original (point on layer).  Horizontal and
 * vertical entries to the point are both extended from since they
 * may vary in number of jogs and hence cost.
 */
typedef struct
{
    Point	 pk_point;	/* (x, y) */
    RouteLayer  *pk_rLayer;	/* "z" - Layer we are on */
    int 	 pk_orient;	/* Because of jogCost, we must distinguish
				 * between endpts of horizontal and vertical
				 * segments.
				 */
#if SIZEOF_VOID_P == 8
    unsigned	 pk_buffer;	/* Structure size will be to word boundary!
				 * make sure we don't pass an uninitialized
				 * byte block to the hash function!
				 */
#endif
} PointKey;

extern HashTable mzPointHash;
#define INITHASHSIZE	64

/* Queues for partial paths */
extern Heap mzMaxToGoHeap;	/* paths nearer destination than WINDOW */
extern Heap mzMinCostHeap;	/* paths in WINDOW */
extern Heap mzMinAdjCostHeap;   /* paths farther from dest than WINDOW*/
extern List *mzBloomStack;	/* paths in current local focus */
extern List *mzStraightStack;	/* focus paths being extended in straightline*/
extern List *mzDownHillStack;	/* focus paths followed only until cost
				   increases */
extern List *mzWalkStack;	/* paths inside walk (i.e. inside blocked
				 * area adjacent to destination.
				 */
extern Heap mzMinCostCompleteHeap;  /* completed paths */
#define	INITHEAPSIZE	64

/* ------------------------ Routines Global to MazeRouter --------------- */
extern RoutePath *mzAllocRPath();
extern char *mzCost2String();
extern char *mzDICost2String();
extern RouteType *mzFindRouteType();
extern void mzNLClear();
extern int *mzNLGetContainingInterval();
extern void mzNLInit();
extern void mzNLInsert();
extern void mzTechFinal();
extern int mzPaintContact();
extern TileTypeBitMask mzTouchingTypes();

extern void mzAddPoint(RoutePath *, Point *, RouteLayer *, int, int, dlong *);
extern void mzWalkRight(RoutePath *);
extern void mzWalkLeft(RoutePath *);
extern void mzWalkUp(RoutePath *);
extern void mzWalkDown(RoutePath *);
extern void mzWalkContact(RoutePath *);
extern dlong mzEstimatedCost(Point *);
extern RoutePath *mzSearch();


/* --------------------- Variables Global to MazeRouter ----------------- */

/* Use a maximum cost which we can add to without overflowing */
#define COST_MAX        (DLONG_MAX >> 2)

/* Parameter sets for mzrouting - from tech file. */
extern MazeStyle *mzStyles;

/* Source of path currently being extended */
extern int mzPathSource;
#define SOURCE_INIT 0
#define SOURCE_BLOOM 1
#define SOURCE_STRAIGHT 2
#define SOURCE_DOWNHILL 3
#define SOURCE_WALK 4

/* Paint generated by router */
extern CellDef *mzResultDef;
extern CellUse *mzResultUse;

/* Cell to do routing in */
extern CellUse *mzRouteUse;

/* Mask giving expanded subcells */
extern int mzCellExpansionMask;

/* Don't route outside of this area */
extern Rect mzBoundingRect;

/* List of Route starting terminals */
extern List *mzStartTerms;

/* Cell containing dest areas */
extern CellDef *mzDestAreasDef;
extern CellUse *mzDestAreasUse;

/* dest terminal alignment coordinates */
extern NumberLine mzXAlignNL;
extern NumberLine mzYAlignNL;
/* initial size of above number lines */
#define INITIAL_ALIGN_SIZE 100

/* Fence parity */
extern bool mzInsideFence;

/* largest design rule distance - used during incremental blockage gen. */
extern int mzContextRadius;

/* Route types */
extern RouteLayer *mzRouteLayers;
extern RouteLayer *mzActiveRLs;
extern RouteContact *mzRouteContacts;
extern RouteType *mzRouteTypes;
extern RouteType *mzActiveRTs;

/* minimum radius of blockage plane info required around point being expanded.
 * (Areas twice this size are gened. whenever the minimum is not met.)
 */
extern int mzBoundsIncrement;

/* If reset, degenerate estimation plane used (just 4 tiles - one for each
 * quadrant with respect to destination point).
 */
extern int mzEstimate;
/* If set, routes may terminate at any geometry that is
 * electrically connected to specified dest areas (default TRUE)
 */
extern int mzExpandDests;
/* If set, routes may start at any geometry that is
 * electrically connected to specified start areas (default TRUE)
 */
extern int mzExpandStarts;
/* If set, only hints in toplevel cell are recognized */
extern int mzTopHintsOnly;
/* Maximum distance route will extend into blocked area to connect to dest. */
extern int mzMaxWalkLength;
/* limits area of route for performance,
 * NOTE: IF NONNULL, USER MUST MAKE SURE ROUTE IS ACTUALLY LIMITED TO THIS
 * AREA WITH FENCES, OTHERWISE THE RESULT IS UNPREDICTABLE.
 */
extern Rect *mzBoundsHint;

/* how generous to be with messages */
extern int mzVerbosity;
/* if positive, limit on number of blooms */
extern int mzBloomLimit;

/* minimum estimated total cost for initial paths */
extern dlong mzMinInitialCost;

/* Parameters controlling search */
extern RouteFloat mzPenalty;
extern dlong mzWRate;
extern dlong mzBloomDeltaCost;
extern dlong mzWWidth;

/* Statistics */
extern dlong mzInitialEstimate;  /* Initial estimated cost of route */
extern int mzNumBlooms;
extern int mzNumOutsideBlooms;	/* num blooms from outside window */
extern int mzNumComplete;	/* number of complete paths so far */
extern int mzBlockGenCalls;	/* # of calls to blockage gen. code */
extern double mzBlockGenArea;   /* area over which blockage planes
				 * have been gened. */
extern int mzNumPathsGened;	/* number of partial paths added to heap */
extern int mzNumPaths;		/* number of paths processed */
extern int mzReportInterval;    /* frequency that # of paths etc.
				 * is reported. */
extern int mzPathsTilReport;	/* counts down to next path report */

/* Variables controlling search */
extern dlong mzWInitialMinToGo;
extern dlong mzWInitialMaxToGo;
extern dlong mzBloomMaxCost;

/* Search status */
extern dlong mzWindowMinToGo; /* Window location */
extern dlong mzWindowMaxToGo;

/* Marked cell list */
extern List *mzMarkedCellsList;

/* C99 compat */
extern void mzExtendBlockBounds();
extern void mzBuildDestAreaBlocks();
extern void mzBuildEstimate();
extern void mzBuildHFR();
extern void mzCleanEstimate();
extern void mzComputeDerivedParms();
extern void mzDumpEstimates();
extern void mzDumpTags();
extern void mzExtendDown();
extern void mzExtendLeft();
extern void mzExtendRight();
extern void mzExtendUp();
extern void mzFreeAllRPaths();
extern void mzMarkConnectedTiles();
extern void mzPaintBlockType();
extern void mzPrintPathHead();
extern bool mzStart();
extern void mzWalkLRContact();
extern void mzWalkUDContact();

/* ------------ Interesting Point Macros -------------------------------- */
/* The following macros are used in the low-level routines for finding
 * the NEXT interesting point to the Right, Left, Up and Down.
 *
 * The macros are used to choose the first among 2 interesting points.
 */
#define PRUNE_TO_MIN(a,new,reasonSet,reason) \
    if (1) \
    { \
	if((new)<(a)) \
	{ \
            (a) = (new); \
            (reasonSet) = (reason); \
        } \
	else if ((new)==(a)) \
	{ \
	    (reasonSet) |= (reason); \
	} \
    } else

#define PRUNE_TO_MAX(a,new,reasonSet,reason) \
    if (1) \
    { \
	if((new)>(a)) \
	{ \
            (a) = (new); \
            (reasonSet) = (reason); \
        } \
	else if ((new)==(a)) \
	{ \
	    (reasonSet) |= (reason); \
	} \
    } else

#define RC_JOG		1
#define RC_ALIGNOTHER   2
#define RC_CONTACT	4
#define RC_ALIGNGOAL	8
#define RC_HINT		16
#define RC_ROTBEFORE	32
#define RC_ROTINSIDE	64
#define RC_BOUNDS	128
#define RC_WALK		256
#define RC_WALKUDC	512
#define RC_WALKLRC	1024
#define RC_DONE		2048

#endif /* _MAGIC__MZROUTER__MZINTERNAL_H */
