Implementation for "empty space" routines (needed for via-space tracking in the auto-router. More...

#include "global.h"
#include <assert.h>
#include <setjmp.h>
#include "box.h"
#include "heap.h"
#include "rtree.h"
#include "mtspace.h"
#include "vector.h"

Include dependency graph for mtspace.c:

Go to the source code of this file.

Data Structures
struct	mtspacebox
struct	mtspace
	This is an mtspace_t. More...
union	heap_or_vector
struct	vetting
	This is a vetting_t. More...
struct	mts_info
struct	query_closure
Defines
#define	SPECIAL 823157
Typedefs
typedef struct mtspacebox	mtspacebox_t
Functions
mtspacebox_t *	mtspace_create_box (const BoxType *box, Coord keepaway)
mtspace_t *	mtspace_create (void)
	Create an "empty space" representation with a shrunken boundary.
void	mtspace_destroy (mtspace_t **mtspacep)
	Destroy an "empty space" representation.
static int	mts_remove_one (const BoxType b, void cl)
rtree_t *	which_tree (mtspace_t *mtspace, mtspace_type_t which)
void	mtspace_add (mtspace_t mtspace, const BoxType box, mtspace_type_t which, Coord keepaway)
	Add a space-filler to the empty space representation.
void	mtspace_remove (mtspace_t mtspace, const BoxType box, mtspace_type_t which, Coord keepaway)
	Remove a space-filler from the empty space representation.
static void	heap_append (heap_t heap, CheapPointType desired, BoxType *newone)
static void	append (struct query_closure qc, BoxType newone)
static int	query_one (const BoxType box, void cl)
	We found some space filler that may intersect this query.
static void	qloop (struct query_closure qc, rtree_t tree, heap_or_vector res, bool is_vec)
	qloop takes a vector (or heap) of regions to check (checking) if they don't intersect anything.
void	mtsFreeWork (vetting_t **w)
	Free the memory used by the vetting structure.
vetting_t *	mtspace_query_rect (mtspace_t mtspace, const BoxType region, Coord radius, Coord keepaway, vetting_t work, vector_t free_space_vec, vector_t lo_conflict_space_vec, vector_t hi_conflict_space_vec, bool is_odd, bool with_conflicts, CheapPointType *desired)

int	mtsBoxCount (vetting_t *w)

Detailed Description

Implementation for "empty space" routines (needed for via-space tracking in the auto-router.

mtspace data structures are built on r-trees.

This file, mtspace.c, was written and is

Copyright.

PCB, interactive printed circuit board design

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.

Contact addresses for paper mail and Email:

harry eaton, 6697 Buttonhole Ct, Columbia, MD 21044 USA

haceaton@aplcomm.jhuapl.edu

Definition in file mtspace.c.

Define Documentation

#define SPECIAL 823157

Definition at line 108 of file mtspace.c.

Referenced by mtsFreeWork(), and mtspace_query_rect().

Typedef Documentation

typedef struct mtspacebox mtspacebox_t

Function Documentation

static void append	(	struct query_closure *	qc,
		BoxType *	newone
	)		`[inline, static]`

Definition at line 255 of file mtspace.c.

References query_closure::checking, query_closure::desired, heap_or_vector::h, heap_append(), heap_or_vector::v, and vector_append().

Referenced by query_one().

Here is the call graph for this function:

static void heap_append	(	heap_t *	heap,
		CheapPointType *	desired,
		BoxType *	newone
	)		`[inline, static]`

Definition at line 246 of file mtspace.c.

References closest_point_in_box(), heap_insert(), cheap_point::X, and cheap_point::Y.

Referenced by append(), qloop(), and query_one().

Here is the call graph for this function:

static int mts_remove_one	(	const BoxType *	b,
		void *	cl
	)		`[static]`

Definition at line 164 of file mtspace.c.

References mts_info::box, box, mts_info::env, mts_info::keepaway, mtspacebox::keepaway, r_delete_entry(), mts_info::tree, BoxType::X1, BoxType::X2, BoxType::Y1, and BoxType::Y2.

Referenced by mtspace_remove().

Here is the call graph for this function:

int mtsBoxCount ( vetting_t * w )

Definition at line 610 of file mtspace.c.

References vetting::hi_candidate, vetting::no_fix, vetting::no_hi, vetting::untested, and vector_size().

Here is the call graph for this function:

void mtsFreeWork ( vetting_t ** w )

Free the memory used by the vetting structure.

Definition at line 413 of file mtspace.c.

References vetting::desired, heap_or_vector::h, heap_destroy(), heap_free(), vetting::hi_candidate, vetting::no_fix, vetting::no_hi, SPECIAL, vetting::untested, heap_or_vector::v, vector_destroy(), vector_is_empty(), vector_remove_last(), cheap_point::X, and cheap_point::Y.

Referenced by CreateSearchEdge(), KillEdge(), and mtspace_query_rect().

Here is the call graph for this function:

void mtspace_add	(	mtspace_t *	mtspace,
		const BoxType *	box,
		mtspace_type_t	which,
		Coord	keepaway
	)

Add a space-filler to the empty space representation.

The given box should *not* be bloated; it should be "true". The feature will fill *at least* a radius of keepaway around it;

Definition at line 202 of file mtspace.c.

References mtspace_create_box(), r_insert_entry(), and which_tree().

Referenced by CreateRouteData(), RD_DrawLine(), RD_DrawVia(), and RouteAll().

Here is the call graph for this function:

mtspace_t* mtspace_create ( void )

Create an "empty space" representation with a shrunken boundary.

Definition at line 128 of file mtspace.c.

References mtspace::etree, mtspace::ftree, malloc(), mtspace::otree, and r_create_tree().

Referenced by CreateRouteData().

Here is the call graph for this function:

mtspacebox_t* mtspace_create_box	(	const BoxType *	box,
		Coord	keepaway
	)

Definition at line 111 of file mtspace.c.

References box, mtspacebox::box, box_is_good(), mtspacebox::keepaway, and malloc().

Referenced by mtspace_add().

Here is the call graph for this function:

void mtspace_destroy ( mtspace_t ** mtspacep )

Destroy an "empty space" representation.

Definition at line 145 of file mtspace.c.

References r_destroy_tree().

Referenced by DestroyRouteData().

Here is the call graph for this function:

vetting_t* mtspace_query_rect	(	mtspace_t *	mtspace,
		const BoxType *	region,
		Coord	radius,
		Coord	keepaway,
		vetting_t *	work,
		vector_t *	free_space_vec,
		vector_t *	lo_conflict_space_vec,
		vector_t *	hi_conflict_space_vec,
		bool	is_odd,
		bool	with_conflicts,
		CheapPointType *	desired
	)

It tries first to find Completely empty regions (which are appended to the free_space_vec vector). If that fails, it looks for regions filled only by objects generated by the previous pass (which are appended to the lo_conflict_space_vec vector). Then it looks for regions that are filled by objects generated during *this* pass (which are appended to the hi_conflict_space_vec vector). The current pass identity is given by 'is_odd'. As soon as one completely free region is found, it returns with that answer. It saves partially searched regions in vectors "untested", "no_fix", "no_hi", and "hi_candidate" which can be passed to future calls of this function to search harder for such regions if the computation becomes necessary.

Returns:: returns some empty spaces in 'region' (or former narrowed regions) that may hold a feature with the specified radius and keepaway

Definition at line 469 of file mtspace.c.

References bloat_box(), box_is_good(), query_closure::cbox, query_closure::checking, query_closure::desired, vetting::desired, mtspace::etree, mtspace::ftree, heap_or_vector::h, heap_create(), heap_insert(), heap_is_empty(), vetting::hi_candidate, query_closure::keepaway, vetting::keepaway, malloc(), mtsFreeWork(), vetting::no_fix, vetting::no_hi, mtspace::otree, qloop(), query_closure::radius, vetting::radius, SPECIAL, query_closure::touch_is_vec, query_closure::touching, vetting::untested, heap_or_vector::v, vector_append(), vector_create(), vector_is_empty(), cheap_point::X, and cheap_point::Y.

Referenced by add_via_sites(), and do_via_search().

Here is the call graph for this function:

void mtspace_remove	(	mtspace_t *	mtspace,
		const BoxType *	box,
		mtspace_type_t	which,
		Coord	keepaway
	)

Remove a space-filler from the empty space representation.

The given box should *not* be bloated; it should be "true". The feature will fill *at least* a radius of keepaway around it;

Definition at line 216 of file mtspace.c.

References box, mts_info::box, box_center(), mts_info::env, mts_info::keepaway, mts_remove_one(), r_search(), mts_info::tree, and which_tree().

Referenced by RouteAll().

Here is the call graph for this function:

static void qloop	(	struct query_closure *	qc,
		rtree_t *	tree,
		heap_or_vector	res,
		bool	is_vec
	)		`[static]`

qloop takes a vector (or heap) of regions to check (checking) if they don't intersect anything.

If a region does intersect something, it is broken into pieces that don't intersect that thing (if possible) which are put back into the vector/heap of regions to check.

Returns:: qloop returns false when it finds the first empty region. It returns true if it has exhausted the region vector/heap and never found an empty area.

Definition at line 376 of file mtspace.c.

References box_is_good(), query_closure::cbox, query_closure::checking, query_closure::desired, query_closure::env, heap_or_vector::h, heap_append(), heap_is_empty(), heap_remove_smallest(), n, query_one(), r_search(), heap_or_vector::v, vector_append(), vector_is_empty(), and vector_remove_last().