maze.java

The ElectricTM VLSI Design System is an open-source Electronic Design Automation (EDA) system that c

						bWavePt.layer = wavePt.layer;   bWavePt.port = wavePt.port;
						bx = wavePt.x; by = wavePt.y;
						bLayer = layer.down;
					}
					found = true;
					connected = true;
				}
			}
			next = wavePt.next;

			// now release this wavept
			if (wavePt.prev == null)
			{
				port.wavefront = wavePt.next;
				if (wavePt.next != null)
					wavePt.next.prev = null;
			} else
			{
				wavePt.prev.next = wavePt.next;
				if (wavePt.next != null)
					wavePt.next.prev = wavePt.prev;
			}

			// set the grid point to a core point
			if (!connected) layer.grids[wavePt.x][wavePt.y] &= ~SR_GWAVE;
		}

		if (found)
			return initPath(port, bLayer, bWavePt, bx, by);

		if (port.wavefront == null) return SRBLOCKED;
		return SRSUCCESS;
	}

	private int initPath(SRPORT port, SRLAYER layer, SRWAVEPT wavePt, int x, int y)
	{
		// search for others
		SRPORT target = null;
		SRWAVEPT tWavePt = null;
		for (target = port.net.ports; target != null; target = target.next)
		{
			if (target == port || target.master != null) continue;
			tWavePt = searchWavefront(target, layer, x, y);
			if (tWavePt != null) break;
		}
		if (target == null) return SRERROR;

		/* now move the target's paths to the master. This is done to retain the
		 * original path creation order (port out), and also insures the existance
		 * of the arc in t-junction connections
		 */
		if (port.lastpath != null)
		{
			if ((port.lastpath.next = target.paths) != null)
				port.lastpath = target.lastpath;
		} else
		{
			// this should never happen
			port.paths = target.paths;
			port.lastpath = target.lastpath;
		}
		target.paths = null;
		target.lastpath = null;

		// connect the port with target
		SRPATH path = null;
		if (wavePt.layer == tWavePt.layer)
		{
			path = getPath(port, layer, false, false, wavePt.x, wavePt.y, tWavePt.x, tWavePt.y);
		}

		// now create paths to each target point
		if (findPaths(wavePt, path) != SRSUCCESS) return SRERROR;
		if (findPaths(tWavePt, path) != SRSUCCESS) return SRERROR;

		// now set the target master
		target.master = port;

		// now scan through all ports and change target as master to port
		for (SRPORT sport = port.net.ports; sport != null; sport = sport.next)
		{
			if (sport.master == target) sport.master = port;
		}

		// now move the rest of the paths to the master port
		if (port.lastpath != null)
		{
			if ((port.lastpath.next = target.paths) != null)
				port.lastpath = target.lastpath;
		} else
		{
			// this should never happen
			port.paths = target.paths;
			port.lastpath = target.lastpath;
		}
		target.paths = null;
		target.lastpath = null;

		return SRROUTED;
	}

	/**
	 * Method to find the path through the maze to the target point.
	 * Will merge the starting point path with the first internal path if possible.
	 */
	private int findPaths(SRWAVEPT wavePt, SRPATH path)
	{
		// Start scan from the first point
		int sx = wavePt.x;
		int sy = wavePt.y;

		SRLAYER layer = wavePt.layer;
		int code = layer.grids[sx][sy] & SR_GMASK;
		if (code == SR_GSTART) code = SR_GMAX;
			else code--;
		int pStart = 0;
		int ex = 0, ey = 0;
		for(;;)
		{
			int dx = 0, dy = 0;

			// scan around the point
			for(;;)
			{
				if (pStart == 1)
				{
					// always try to jump layer after the first path
					// now try jumping layers
					if (layer.up != null)
					{
						ex = sx; ey = sy;
						int status = testPoint(layer.up.grids[ex][ey], code);
						if (status == SRROUTED) return SRSUCCESS;
						if (status == SRSUCCESS)
						{
							layer = layer.up;
							if (code == SR_GSTART) code = SR_GMAX;
								else code--;
							pStart = 2;
							continue;
						}
					}
					if (layer.down != null)
					{
						ex = sx; ey = sy;
						int status = testPoint(layer.down.grids[ex][ey], code);
						if (status == SRROUTED) return SRSUCCESS;
						if (status == SRSUCCESS)
						{
							layer = layer.down;
							if (code == SR_GSTART) code = SR_GMAX;
								else code--;
							pStart = 2;
							continue;
						}
					}
				}
				if (layer.dir == SRALL || layer.dir == SRHORIPREF)
				{
					// try right first
					if ((ex = sx + 1) != layer.wid)
					{
						ey = sy;
						int status = testPoint(layer.grids[ex][ey], code);
						if (status == SRROUTED)
						{
							// check for common original path
							if (path != null && path.layer == layer &&
								path.y[0] == path.y[1] && path.y[0] == ey &&
									Math.max(path.x[0], path.x[1]) == sx)
							{
								if (path.x[0] == sx)
								{
									path.x[0] = ex;
									path.wx[0] = getWorldX(ex, layer);
								} else
								{
									path.x[1] = ex;
									path.wx[1] = getWorldX(ex, layer);
								}
								setLine(path.layer, SR_GPORT | SR_GSET,
									path.wx[0], path.wy[0], path.wx[1], path.wy[1], true);
								return SRSUCCESS;
							}
							getPath(wavePt.port, layer, false, true, sx, sy, ex, ey);
							return SRSUCCESS;
						} else if (status == SRSUCCESS)
						{
							dx = 1;
							break;
						}
					}
				}
				if (layer.dir == SRALL || layer.dir == SRVERTPREF)
				{
					// try down first
					if ((ey = sy - 1) >= 0)
					{
						ex = sx;
						int status = testPoint(layer.grids[ex][ey], code);
						if (status == SRROUTED)
						{
							// check for common original path
							if (path != null && path.layer == layer &&
								path.x[0] == path.x[1] && path.x[0] == ex &&
									Math.min(path.y[0], path.y[1]) == sy)
							{
								if (path.y[0] == sy)
								{
									path.y[0] = ey;
									path.wy[0] = getWorldY(ey, layer);
								} else
								{
									path.y[1] = ey;
									path.wy[1] = getWorldY(ey, layer);
								}
								setLine(path.layer, SR_GPORT | SR_GSET,
									path.wx[0], path.wy[0], path.wx[1], path.wy[1], true);
								return SRSUCCESS;
							}
							getPath(wavePt.port, layer, false, true, sx, sy, ex, ey);
							return SRSUCCESS;
						} else if (status == SRSUCCESS)
						{
							dy = -1;
							break;
						}
					}
				}
				if (layer.dir == SRALL || layer.dir == SRHORIPREF)
				{
					// try left
					if ((ex = sx - 1) >= 0)
					{
						ey = sy;
						int status = testPoint(layer.grids[ex][ey], code);
						if (status == SRROUTED)
						{
							// check for common original path
							if (path != null && path.layer == layer &&
								path.y[0] == path.y[1] && path.y[0] == ey &&
									Math.min(path.x[0], path.x[1]) == sx)
							{
								if (path.x[0] == sx)
								{
									path.x[0] = ex;
									path.wx[0] = getWorldX(ex, layer);
								} else
								{
									path.x[1] = ex;
									path.wx[1] = getWorldX(ex, layer);
								}
								setLine(path.layer, SR_GPORT | SR_GSET,
									path.wx[0], path.wy[0], path.wx[1], path.wy[1], true);
								return SRSUCCESS;
							}
							getPath(wavePt.port, layer, false, true, sx, sy, ex, ey);
							return SRSUCCESS;
						} else if (status == SRSUCCESS)
						{
							dx = -1;
							break;
						}
					}
				}
				if (layer.dir == SRALL || layer.dir == SRVERTPREF)
				{
					// try up
					if ((ey = sy + 1) != layer.hei)
					{
						ex = sx;
						int status = testPoint(layer.grids[ex][ey], code);
						if (status == SRROUTED)
						{
							// check for common original path
							if (path != null && path.layer == layer &&
								path.x[0] == path.x[1] && path.x[0] == ex &&
									Math.max(path.y[0], path.y[1]) == sy)
							{
								if (path.y[0] == sy)
								{
									path.y[0] = ey;
									path.wy[0] = getWorldY(ey, layer);
								} else
								{
									path.y[1] = ey;
									path.wy[1] = getWorldY(ey, layer);
								}
								setLine(path.layer, SR_GPORT | SR_GSET,
									path.wx[0], path.wy[0], path.wx[1], path.wy[1], true);
								return SRSUCCESS;
							}
							getPath(wavePt.port, layer, false, true, sx, sy, ex, ey);
							return SRSUCCESS;
						} else if (status == SRSUCCESS)
						{
							dy = 1;
							break;
						}
					}
				}

				// now try jumping layers
				if (pStart == 0)
				{
					if (layer.up != null)
					{
						ex = sx; ey = sy;
						int status = testPoint(layer.up.grids[ex][ey], code);
						if (status == SRROUTED) return SRSUCCESS;
						if (status == SRSUCCESS)
						{
							layer = layer.up;
							if (code == SR_GSTART) code = SR_GMAX;
								else code--;
							continue;
						}
					}
					if (layer.down != null)
					{
						ex = sx; ey = sy;
						int status = testPoint(layer.down.grids[ex][ey], code);
						if (status == SRROUTED) return SRSUCCESS;
						if (status == SRSUCCESS)
						{
							layer = layer.down;
							if (code == SR_GSTART) code = SR_GMAX;
								else code--;
							continue;
						}
					}
				}

				// could not start route, just return
				return SRERROR;
			}

			// set path started
			pStart = 1;

			// now continue scan until the end of the path
			for(;;)
			{
				if (code == SR_GSTART) code = SR_GMAX;
					else code--;
				if (dx != 0)
				{
					// horizontal scan
					int nx = ex + dx;
					int ny = ey;
					int status = testPoint(layer.grids[nx][ny], code);
					if (status == SRROUTED)
					{
						// check for common original path
						if (path != null && path.layer == layer &&
							path.y[0] == path.y[1] && path.y[0] == sy &&
							((dx < 0 && Math.min(path.x[0], path.x[1]) == sx) ||
							(dx > 0 && Math.max(path.x[0], path.x[1]) == sx)))
						{
							if (path.x[0] == sx)
							{
								path.x[0] = nx;
								path.wx[0] = getWorldX(nx, layer);
							} else
							{
								path.x[1] = nx;
								path.wx[1] = getWorldX(nx, layer);
							}
							setLine(path.layer, SR_GPORT | SR_GSET,
								path.wx[0], path.wy[0], path.wx[1], path.wy[1], true);
							return SRSUCCESS;
						}
						getPath(wavePt.port, layer, false, true, sx, sy, nx, ny);
						return SRSUCCESS;
					} else if (status == SRSUCCESS)
					{
						ex = nx;
						continue;
					}
				}
				if (dy != 0)
				{
					// veritical scan
					int nx = ex;
					int ny = ey + dy;
					int status = testPoint(layer.grids[nx][ny], code);
					if (status == SRROUTED)
					{
						// check for common original path
						if (path != null && path.layer == layer &&
							path.x[0] == path.x[1] && path.x[0] == sx &&
							((dy < 0 && Math.min(path.y[0], path.y[1]) == sy) ||
							(dy > 0 && Math.max(path.y[0], path.y[1]) == sy)))
						{
							if (path.y[0] == sy)
							{
								path.y[0] = ny;
								path.wy[0] = getWorldY(ny, layer);
							} else
							{
								path.y[1] = ny;
								path.wy[1] = getWorldY(ny, layer);
							}
							setLine(path.layer, SR_GPORT | SR_GSET,
								path.wx[0], path.wy[0], path.wx[1], path.wy[1], true);
							return SRSUCCESS;
						}
						getPath(wavePt.port, layer, false, true, sx, sy, nx, ny);
						return SRSUCCESS;
					} else if (status == SRSUCCESS)
					{
						ey = ny;
						continue;
					}
				}

				// end of the path, add and break loop

				// check for common original path
				if (path != null && path.layer == layer &&
					// horizontal path check
					((sy == ey && path.y[0] == path.y[1] && path.y[0] == ey &&
					(path.x[0] == sx || path.x[1] == sx)) ||
					// vertical path check
					(sx == ex && path.x[0] == path.x[1] && path.x[0] == ex &&
					(path.y[0] == sy || path.y[1] == sy))))
				{
					// vertical path ?
					if (sx == ex)
					{
						if (sy == path.y[0])
						{
							path.y[0] = ey;
							path.wy[0] = getWorldY(ey, layer);
						} else
						{
							path.y[1] = ey;
							path.wy[1] = getWorldY(ey, layer);
						}
					}

					// horizontal path ?
					else
					{
						if (sx == path.x[0])
						{
							path.x[0] = ex;
							path.wx[0] = getWorldX(ex, layer);
						} else
						{
							path.x[1] = ex;
							path.wx[1] = getWorldX(ex, layer);
						}
					}

					setLine(path.layer, SR_GPORT | SR_GSET,
						path.wx[0], path.wy[0], path.wx[1], path.wy[1], true);
					path = null;
				} else
				{
					getPath(wavePt.port, layer, false, false, sx, sy, ex, ey);