rtree.c File Reference

Implements r-tree structures. More...

#include "global.h"
#include <assert.h>
#include <inttypes.h>
#include <setjmp.h>
#include "mymem.h"
#include "rtree.h"

Include dependency graph for rtree.c:

Go to the source code of this file.

Data Structures
struct	Rentry
struct	rtree_node
struct	r_arg
struct	centroid
Defines
#define	SLOW_ASSERTS
#define	M_SIZE   6
#define	SORT_NONLEAF
#define	DELETE_BY_POINTER
#define	sort_node(x)
Functions
static int	__r_node_is_good (struct rtree_node *node)
static bool	__r_tree_is_good (struct rtree_node *node)
	Check the whole tree from this node down for consistency.
void	__r_dump_tree (struct rtree_node *node, int depth)
	Print out the tree.
static void	adjust_bounds (struct rtree_node *node)
	Set the node bounds large enough to encompass all of the children's rectangles.
rtree_t *	r_create_tree (const BoxType *boxlist[], int N, int manage)
	Create an r-tree from an unsorted list of boxes.
static void	__r_destroy_tree (struct rtree_node *node)
	Destroy an rtree.
void	r_destroy_tree (rtree_t **rtree)
	Free the memory associated with an rtree.
int	__r_search (struct rtree_node *node, const BoxType *query, r_arg *arg)
int	r_search (rtree_t *rtree, const BoxType *query, int(*check_region)(const BoxType *region, void *cl), int(*found_rectangle)(const BoxType *box, void *cl), void *cl)
	Parameterized search in the rtree.
static int	__r_region_is_empty_rect_in_reg (const BoxType *box, void *cl)
	r_region_is_empty.
int	r_region_is_empty (rtree_t *rtree, const BoxType *region)
	Special-purpose searches build upon r_search.
struct rtree_node *	find_clusters (struct rtree_node *node)
	Split the node into two nodes putting clusters in each use the k-means clustering algorithm.
static void	split_node (struct rtree_node *node)
	Split a node according to clusters.
static int	contained (struct rtree_node *node, const BoxType *query)
static double	penalty (struct rtree_node *node, const BoxType *query)
	Compute the area penalty for inserting here and return.
static void	__r_insert_node (struct rtree_node *node, const BoxType *query, int manage, bool force)
void	r_insert_entry (rtree_t *rtree, const BoxType *which, int man)
bool	__r_delete (struct rtree_node *node, const BoxType *query)
bool	r_delete_entry (rtree_t *rtree, const BoxType *box)

---

Detailed Description

Implements r-tree structures.

These should be much faster for the auto-router because the recursive search is much more efficient and that's where the auto-router spends all its time.

Author:

this file, rtree.c, was written and is Copyright (c) 2004, harry eaton

---

Copyright.

PCB, interactive printed circuit board design

Copyright (C) 1994,1995,1996 Thomas Nau

Copyright (C) 1998,1999,2000,2001,2002,2003,2004 harry eaton

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 rtree.c.

---

Define Documentation

#define DELETE_BY_POINTER

Definition at line 79 of file rtree.c.

#define M_SIZE   6

Definition at line 71 of file rtree.c.

Referenced by __r_delete(), __r_destroy_tree(), __r_dump_tree(), __r_insert_node(), __r_node_is_good(), __r_tree_is_good(), adjust_bounds(), find_clusters(), and split_node().

#define SLOW_ASSERTS

Definition at line 62 of file rtree.c.

#define sort_node

(

x

)

Definition at line 370 of file rtree.c.

Referenced by __r_insert_node(), find_clusters(), and split_node().

#define SORT_NONLEAF

Definition at line 77 of file rtree.c.

---

Function Documentation

bool __r_delete	(	struct rtree_node *	node,
		const BoxType *	query
	)

Definition at line 1067 of file rtree.c.

References adjust_bounds(), Rentry::bounds, rtree_node::box, Rentry::bptr, rtree_node::flags, rtree_node::is_leaf, rtree_node::kids, M_SIZE, rtree_node::manage, rtree_node::parent, rtree_node::rects, rtree_node::u, BoxType::X1, BoxType::X2, BoxType::Y1, and BoxType::Y2.

Referenced by r_delete_entry().

Here is the call graph for this function:

static void __r_destroy_tree

(

struct rtree_node *

node

)

[static]

Destroy an rtree.

Definition at line 454 of file rtree.c.

References Rentry::bptr, rtree_node::flags, rtree_node::is_leaf, rtree_node::kids, M_SIZE, rtree_node::manage, rtree_node::rects, and rtree_node::u.

Referenced by r_destroy_tree().

void __r_dump_tree	(	struct rtree_node *	node,
		int	depth
	)

Print out the tree.

Definition at line 227 of file rtree.c.

References __r_dump_tree(), rtree_node::box, rtree_node::flags, rtree_node::is_leaf, rtree_node::kids, M_SIZE, rtree_node::manage, rtree_node::u, BoxType::X1, BoxType::X2, BoxType::Y1, and BoxType::Y2.

Referenced by __r_dump_tree(), and ReportDialog().

Here is the call graph for this function:

static void __r_insert_node	(	struct rtree_node *	node,
		const BoxType *	query,
		int	manage,
		bool	force
	)		[static]

Definition at line 927 of file rtree.c.

References __r_node_is_good(), Rentry::bounds, rtree_node::box, Rentry::bptr, contained(), rtree_node::flags, rtree_node::is_leaf, rtree_node::kids, M_SIZE, MAKEMAX, MAKEMIN, rtree_node::manage, node, rtree_node::parent, penalty(), rtree_node::rects, sort_node, split_node(), rtree_node::u, UNLIKELY, BoxType::X1, BoxType::X2, BoxType::Y1, and BoxType::Y2.

Referenced by r_insert_entry().

Here is the call graph for this function:

static int __r_node_is_good

(

struct rtree_node *

node

)

[static]

Definition at line 107 of file rtree.c.

References Rentry::bounds, rtree_node::box, Rentry::bptr, rtree_node::flags, rtree_node::is_leaf, rtree_node::kids, M_SIZE, rtree_node::parent, rtree_node::rects, rtree_node::u, BoxType::X1, BoxType::X2, BoxType::Y1, and BoxType::Y2.

Referenced by __r_insert_node(), __r_search(), __r_tree_is_good(), and split_node().

static int __r_region_is_empty_rect_in_reg	(	const BoxType *	box,
		void *	cl
	)		[static]

r_region_is_empty.

Definition at line 653 of file rtree.c.

Referenced by r_region_is_empty().

int __r_search	(	struct rtree_node *	node,
		const BoxType *	query,
		r_arg *	arg
	)

Most of the auto-routing time is spent in this routine so some careful thought has been given to maximizing the speed.

Definition at line 504 of file rtree.c.

References __r_node_is_good(), Rentry::bounds, rtree_node::box, Rentry::bptr, r_arg::check_it, r_arg::closure, rtree_node::flags, r_arg::found_it, rtree_node::is_leaf, rtree_node::kids, n, rtree_node::rects, rtree_node::u, BoxType::X1, BoxType::X2, BoxType::Y1, and BoxType::Y2.

Referenced by r_search().

Here is the call graph for this function:

static bool __r_tree_is_good

(

struct rtree_node *

node

)

[static]

Check the whole tree from this node down for consistency.

Definition at line 202 of file rtree.c.

References __r_node_is_good(), rtree_node::flags, rtree_node::is_leaf, rtree_node::kids, M_SIZE, and rtree_node::u.

Referenced by r_create_tree(), r_delete_entry(), r_search(), and split_node().

Here is the call graph for this function:

static void adjust_bounds

(

struct rtree_node *

node

)

[static]

Set the node bounds large enough to encompass all of the children's rectangles.

Definition at line 378 of file rtree.c.

References Rentry::bounds, rtree_node::box, Rentry::bptr, rtree_node::flags, rtree_node::is_leaf, rtree_node::kids, M_SIZE, MAKEMAX, MAKEMIN, rtree_node::rects, rtree_node::u, BoxType::X1, BoxType::X2, BoxType::Y1, and BoxType::Y2.

Referenced by __r_delete(), find_clusters(), and split_node().

static int contained	(	struct rtree_node *	node,
		const BoxType *	query
	)		[inline, static]

Definition at line 899 of file rtree.c.

References rtree_node::box, BoxType::X1, BoxType::X2, BoxType::Y1, and BoxType::Y2.

Referenced by __r_insert_node().

struct rtree_node* find_clusters

(

struct rtree_node *

node

)

[read]

Split the node into two nodes putting clusters in each use the k-means clustering algorithm.

Definition at line 694 of file rtree.c.

References adjust_bounds(), centroid::area, Rentry::bounds, rtree_node::box, Rentry::bptr, rtree_node::flags, rtree_node::is_leaf, rtree_node::kids, M_SIZE, rtree_node::manage, rtree_node::parent, rtree_node::rects, sort_node, SQUARE, rtree_node::u, x, centroid::x, BoxType::X1, BoxType::X2, y, centroid::y, BoxType::Y1, and BoxType::Y2.

Referenced by split_node().

Here is the call graph for this function:

static double penalty	(	struct rtree_node *	node,
		const BoxType *	query
	)		[inline, static]

Compute the area penalty for inserting here and return.

The penalty is the increase in area necessary to include the query.

Definition at line 914 of file rtree.c.

References rtree_node::box, MAX, MIN, BoxType::X1, BoxType::X2, BoxType::Y1, and BoxType::Y2.

Referenced by __r_insert_node(), edge_cost(), and vertices_routing_conflict_cost().

rtree_t* r_create_tree	(	const BoxType *	boxlist[],
		int	N,
		int	manage
	)

Create an r-tree from an unsorted list of boxes.

Create an rtree from the list of boxes. If 'manage' is true, then the tree will take ownership of 'boxlist' and free it when the tree is destroyed.

The r-tree will keep pointers into it, so don't free the box list until you've called r_destroy_tree.

If you set 'manage' to true, r_destroy_tree will free your boxlist.

Definition at line 425 of file rtree.c.

References __r_tree_is_good(), rtree_node::flags, rtree_node::is_leaf, N, node, rtree_node::parent, r_insert_entry(), and rtree::root.

Referenced by AddPolygonToBuffer(), ComputeCost(), CopyAttachedPolygonToLayer(), CopyPolygon(), CreateNewArcOnLayer(), CreateNewLineOnLayer(), CreateNewPolygonFromRectangle(), CreateNewRat(), CreateNewText(), CreateNewVia(), CreateRouteData(), InsCntr(), InsertHoles(), make_edge_tree(), MoveArcToBuffer(), MoveArcToLayerLowLevel(), MoveLineToBuffer(), MoveLineToLayerLowLevel(), MovePolygonToBuffer(), MovePolygonToLayerLowLevel(), MoveRatToBuffer(), MoveTextToBuffer(), MoveTextToLayerLowLevel(), MoveViaToBuffer(), mtspace_create(), poly_Copy0(), poly_Init(), PolyToPolygonsOnLayer(), RouteOne(), and SetElementBoundingBox().

Here is the call graph for this function:

bool r_delete_entry	(	rtree_t *	rtree,
		const BoxType *	box
	)

Definition at line 1174 of file rtree.c.

References __r_delete(), __r_tree_is_good(), rtree::root, and rtree::size.

Referenced by adjust_tree(), ChangeArcAngles(), ChangeArcClearSize(), ChangeArcSize(), ChangeElementNameSize(), ChangeElementText(), ChangeHole(), ChangeLineClearSize(), ChangeLineSize(), ChangePadClearSize(), ChangePadMaskSize(), ChangePadSize(), ChangePinClearSize(), ChangePinMaskSize(), ChangePinSize(), ChangeTextName(), ChangeTextSize(), ChangeViaClearSize(), ChangeViaMaskSize(), ChangeViaSize(), DestroyArc(), DestroyElement(), DestroyLine(), DestroyPolygon(), DestroyPolygonPoint(), DestroyRat(), DestroyText(), DestroyVia(), FreeRotateBuffer(), FreeRotateElementLowLevel(), InsertPointIntoLine(), InsertPointIntoPolygon(), MirrorBuffer(), MoveArc(), MoveArcToBuffer(), MoveArcToLayerLowLevel(), MoveElementLowLevel(), MoveElementName(), MoveLine(), MoveLinePoint(), MoveLineToBuffer(), MoveLineToLayerLowLevel(), MovePolygon(), MovePolygonPoint(), MovePolygonToBuffer(), MovePolygonToLayerLowLevel(), MoveRatToBuffer(), MoveText(), MoveTextToBuffer(), MoveTextToLayerLowLevel(), MoveVia(), MoveViaToBuffer(), mts_remove_one(), NotifyMode(), PutContour(), r_delete_element(), remove_contour(), RemovePolygonPoint(), RemoveText(), RotateArc(), RotateBuffer(), RotateElementLowLevel(), RotateElementName(), RotateLinePoint(), RotateObject(), RotateText(), RouteAll(), RouteOne(), SetElementBoundingBox(), SwapBuffer(), and UndoChangeAngles().

Here is the call graph for this function:

void r_destroy_tree

(

rtree_t **

rtree

)

Free the memory associated with an rtree.

Definition at line 481 of file rtree.c.

References __r_destroy_tree().

Referenced by ComputeCost(), DestroyRouteData(), FreeDataMemory(), InsertHoles(), mtspace_destroy(), poly_DelContour(), poly_Free(), and RouteOne().

Here is the call graph for this function:

void r_insert_entry	(	rtree_t *	rtree,
		const BoxType *	which,
		int	man
	)

Definition at line 1051 of file rtree.c.

References __r_insert_node(), rtree_node::box, rtree::root, rtree::size, BoxType::X1, BoxType::X2, BoxType::Y1, and BoxType::Y2.

Referenced by AddPolygonToBuffer(), adjust_tree(), ChangeArcAngles(), ChangeArcClearSize(), ChangeArcSize(), ChangeElementNameSize(), ChangeElementText(), ChangeHole(), ChangeLineClearSize(), ChangeLineSize(), ChangeTextName(), ChangeTextSize(), ChangeViaClearSize(), ChangeViaMaskSize(), ChangeViaSize(), CopyAttachedPolygonToLayer(), CopyPolygon(), CreateNewArcOnLayer(), CreateNewLineOnLayer(), CreateNewPolygonFromRectangle(), CreateNewRat(), CreateNewText(), CreateNewVia(), DestroyPolygonPoint(), FreeRotateBuffer(), InsCntr(), InsertHoles(), InsertPointIntoLine(), InsertPointIntoPolygon(), make_edge_tree(), MirrorBuffer(), MorphPolygon(), moveable_edge(), MoveArc(), MoveArcToBuffer(), MoveArcToLayerLowLevel(), MoveElementLowLevel(), MoveElementName(), MoveLine(), MoveLinePoint(), MoveLineToBuffer(), MoveLineToLayerLowLevel(), MovePolygon(), MovePolygonPoint(), MovePolygonToBuffer(), MovePolygonToLayerLowLevel(), MoveRatToBuffer(), MoveText(), MoveTextToBuffer(), MoveTextToLayerLowLevel(), MoveVia(), MoveViaToBuffer(), mtspace_add(), NotifyMode(), poly_Copy1(), poly_InclContour(), PolyToPolygonsOnLayer(), PutContour(), r_create_tree(), RD_DrawLine(), RD_DrawThermal(), RD_DrawVia(), RemovePolygonPoint(), RotateArc(), RotateBuffer(), RotateElementName(), RotateLinePoint(), RotateObject(), RotateText(), RouteOne(), SetElementBoundingBox(), SwapBuffer(), and UndoChangeAngles().

Here is the call graph for this function:

int r_region_is_empty	(	rtree_t *	rtree,
		const BoxType *	region
	)

Special-purpose searches build upon r_search.

Returns:

0 if there are any rectangles in the given region.

Definition at line 665 of file rtree.c.

References __r_region_is_empty_rect_in_reg(), and r_search().

Here is the call graph for this function:

int r_search	(	rtree_t *	rtree,
		const BoxType *	query,
		int(*)(const BoxType *region, void *cl)	check_region,
		int(*)(const BoxType *box, void *cl)	found_rectangle,
		void *	cl
	)

Parameterized search in the rtree.

Calls found_rectangle for each intersection seen and calls check_region with the current sub-region to see whether deeper searching is desired.

Generic search routine.

region_in_search should return true if "what you're looking for" is within the specified region; regions, like rectangles, are closed on top and left and open on bottom and right.

rectangle_in_region should return true if the given rectangle is "what you're looking for".

The search will find all rectangles matching the criteria given by region_in_search and rectangle_in_region and return a count of how many things rectangle_in_region returned true for.

Closure is used to abort the search if desired from within rectangel_in_region.

Look at the implementation of r_region_is_empty for how to abort the search if that is the desired behavior.

Returns:

the number of rectangles found.

Definition at line 612 of file rtree.c.

References __r_search(), __r_tree_is_good(), rtree_node::box, r_arg::check_it, r_arg::closure, r_arg::found_it, rtree::root, rtree::size, BoxType::X1, BoxType::X2, BoxType::Y1, and BoxType::Y2.

Referenced by AutoRoute(), BreakManyEdges(), check_pin(), CheckArcPointForRubberbandConnection(), CheckLinePointForRat(), CheckLinePointForRubberbandConnection(), CheckPadForRat(), CheckPadForRubberbandConnection(), CheckPinForRat(), CheckPinForRubberbandConnection(), clearPoly(), cntr_in_M_POLYAREA(), contour_bounds_touch(), CountHoles(), CountHolesEx(), CreateDrawnLineOnLayer(), DrawEverything(), DrawHoles(), DrawLayer(), DrawMask(), DrawPPV(), DrawRats(), DrawSilk(), drc_lines(), Expand(), fill_polyarea(), find_pair(), find_pairs(), find_pairs_1(), FindOneInBox(), FindPin(), FindRouteBoxOnLayerGroup(), FindThermable(), InsertHoles(), intersect_impl(), LookupLOConnectionsToArc(), LookupLOConnectionsToLine(), LookupLOConnectionsToPad(), LookupLOConnectionsToPolygon(), LookupLOConnectionsToPVList(), LookupPVConnectionsToLOList(), LookupPVConnectionsToPVList(), M_POLYAREA_update_primary(), maybe_pull_1(), mincost_target_to_point(), MoveLineToLayer(), MovePolygonToLayer(), mtspace_remove(), no_expansion_boxes(), PlowsPolygon(), poly_InsideContour(), poly_InvContour(), qloop(), r_find_neighbor(), r_region_is_empty(), r_search_pt(), RemoveLinePoint(), SearchArcByLocation(), SearchArcPointByLocation(), SearchElementByLocation(), SearchElementNameByLocation(), SearchLineByLocation(), SearchLinePointByLocation(), SearchPadByLocation(), SearchPinByLocation(), SearchPolygonByLocation(), SearchRatLineByLocation(), SearchTextByLocation(), SearchViaByLocation(), and source_conflicts().

Here is the call graph for this function:

static void split_node

(

struct rtree_node *

node

)

[static]

Split a node according to clusters.

Definition at line 846 of file rtree.c.

References __r_node_is_good(), __r_tree_is_good(), adjust_bounds(), find_clusters(), rtree_node::flags, rtree_node::is_leaf, rtree_node::kids, M_SIZE, rtree_node::manage, node, rtree_node::parent, rtree_node::rects, sort_node, and rtree_node::u.

Referenced by __r_insert_node().

Here is the call graph for this function: