pcb 4.1.1
An interactive printed circuit board layout editor.

mtspace.h File Reference

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

#include "global.h"
#include "vector.h"
Include dependency graph for mtspace.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Typedefs

typedef struct mtspace mtspace_t
typedef struct vetting vetting_t

Enumerations

enum  mtspace_type_t { FIXED, ODD, EVEN }

Functions

mtspace_tmtspace_create (void)
 Create an "empty space" representation with a shrunken boundary.
void mtspace_destroy (mtspace_t **mtspacep)
 Destroy an "empty space" representation.
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.
vetting_tmtspace_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)
 
void mtsFreeWork (vetting_t **)
 Free the memory used by the vetting structure.
int mtsBoxCount (vetting_t *)

Detailed Description

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

mtspace data structures are built on r-trees.

This file, mtspace.h, was written and is

Copyright (c) 2001 C. Scott Ananian.


Copyright.


PCB, interactive printed circuit board design

Copyright (C) 1994,1995,1996 Thomas Nau

Copyright (C) 1998,1999,2000,2001 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 mtspace.h.


Typedef Documentation

typedef struct mtspace mtspace_t

Definition at line 51 of file mtspace.h.

typedef struct vetting vetting_t

Definition at line 54 of file mtspace.h.


Enumeration Type Documentation

Enumerator:
FIXED 
ODD 
EVEN 

Definition at line 52 of file mtspace.h.


Function Documentation

int mtsBoxCount ( vetting_t )

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 **  )
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:

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: