KiCad PCB EDA Suite
queue.cpp File Reference
#include <fctsys.h>
#include <common.h>
#include <pcbnew.h>
#include <autorout.h>
#include <cell.h>

Go to the source code of this file.

Classes

struct  PcbQueue
 

Functions

void FreeQueue ()
 
void InitQueue ()
 
void GetQueue (int *r, int *c, int *s, int *d, int *a)
 
bool SetQueue (int r, int c, int side, int d, int a, int r2, int c2)
 
void ReSetQueue (int r, int c, int s, int d, int a, int r2, int c2)
 

Variables

static long qlen = 0
 
static struct PcbQueueHead = NULL
 
static struct PcbQueueTail = NULL
 
static struct PcbQueueSave = NULL
 

Function Documentation

void FreeQueue ( )

Definition at line 60 of file queue.cpp.

References InitQueue(), and PcbQueue::Next.

61 {
62  struct PcbQueue* p;
63 
64  InitQueue();
65 
66  while( (p = Save) != NULL )
67  {
68  Save = p->Next;
69  delete p;
70  }
71 }
struct PcbQueue * Next
Definition: queue.cpp:45
void InitQueue()
Definition: queue.cpp:75
static struct PcbQueue * Save
Definition: queue.cpp:56
void GetQueue ( int *  r,
int *  c,
int *  s,
int *  d,
int *  a 
)

Definition at line 91 of file queue.cpp.

References PcbQueue::ApxDist, ClosNodes, PcbQueue::Col, PcbQueue::Dist, ILLEGAL, PcbQueue::Next, qlen, PcbQueue::Row, Save, and PcbQueue::Side.

Referenced by Autoroute_One_Track().

92 {
93  struct PcbQueue* p;
94 
95  if( (p = Head) != NULL ) /* return first item in list */
96  {
97  *r = p->Row; *c = p->Col;
98  *s = p->Side;
99  *d = p->Dist; *a = p->ApxDist;
100 
101  if( (Head = p->Next) == NULL )
102  Tail = NULL;
103 
104  /* put node on free list */
105  p->Next = Save; Save = p;
106  ClosNodes++; qlen--;
107  }
108  else /* empty list */
109  {
110  *r = *c = *s = *d = *a = ILLEGAL;
111  }
112 }
int Dist
Definition: queue.cpp:49
struct PcbQueue * Next
Definition: queue.cpp:45
int Col
Definition: queue.cpp:47
#define ILLEGAL
Definition: autorout.h:52
static struct PcbQueue * Save
Definition: queue.cpp:56
int Row
Definition: queue.cpp:46
static struct PcbQueue * Tail
Definition: queue.cpp:55
int ClosNodes
Definition: solve.cpp:86
static struct PcbQueue * Head
Definition: queue.cpp:54
int Side
Definition: queue.cpp:48
static long qlen
Definition: queue.cpp:53
int ApxDist
Definition: queue.cpp:50
void InitQueue ( )

Definition at line 75 of file queue.cpp.

References ClosNodes, MaxNodes, MoveNodes, PcbQueue::Next, OpenNodes, qlen, and Save.

Referenced by Autoroute_One_Track(), and FreeQueue().

76 {
77  struct PcbQueue* p;
78 
79  while( (p = Head) != NULL )
80  {
81  Head = p->Next;
82  p->Next = Save; Save = p;
83  }
84 
85  Tail = NULL;
87 }
int OpenNodes
Definition: solve.cpp:85
struct PcbQueue * Next
Definition: queue.cpp:45
int MoveNodes
Definition: solve.cpp:87
static struct PcbQueue * Save
Definition: queue.cpp:56
static struct PcbQueue * Tail
Definition: queue.cpp:55
int ClosNodes
Definition: solve.cpp:86
int MaxNodes
Definition: solve.cpp:88
static struct PcbQueue * Head
Definition: queue.cpp:54
static long qlen
Definition: queue.cpp:53
void ReSetQueue ( int  r,
int  c,
int  s,
int  d,
int  a,
int  r2,
int  c2 
)

Definition at line 185 of file queue.cpp.

References ClosNodes, MoveNodes, PcbQueue::Next, OpenNodes, qlen, Save, and SetQueue().

Referenced by Autoroute_One_Track().

186 {
187  struct PcbQueue* p, * q;
188 
189  /* first, see if it is already in the list */
190  for( q = NULL, p = Head; p; q = p, p = p->Next )
191  {
192  if( p->Row == r && p->Col == c && p->Side == s )
193  {
194  /* old one to remove */
195  if( q )
196  {
197  if( ( q->Next = p->Next ) == NULL )
198  Tail = q;
199  }
200  else if( ( Head = p->Next ) == NULL )
201  {
202  Tail = NULL;
203  }
204 
205  p->Next = Save;
206  Save = p;
207  OpenNodes--;
208  MoveNodes++;
209  qlen--;
210  break;
211  }
212  }
213 
214  if( !p ) /* not found, it has already been closed once */
215  ClosNodes--; /* we will close it again, but just count once */
216 
217  /* if it was there, it's gone now; insert it at the proper position */
218  bool res = SetQueue( r, c, s, d, a, r2, c2 );
219  (void) res;
220 }
int OpenNodes
Definition: solve.cpp:85
struct PcbQueue * Next
Definition: queue.cpp:45
int MoveNodes
Definition: solve.cpp:87
static struct PcbQueue * Save
Definition: queue.cpp:56
bool SetQueue(int r, int c, int side, int d, int a, int r2, int c2)
Definition: queue.cpp:120
static struct PcbQueue * Tail
Definition: queue.cpp:55
int ClosNodes
Definition: solve.cpp:86
static struct PcbQueue * Head
Definition: queue.cpp:54
static long qlen
Definition: queue.cpp:53
bool SetQueue ( int  r,
int  c,
int  side,
int  d,
int  a,
int  r2,
int  c2 
)

Definition at line 120 of file queue.cpp.

References PcbQueue::ApxDist, PcbQueue::Col, PcbQueue::Dist, MaxNodes, PcbQueue::Next, OpenNodes, qlen, PcbQueue::Row, and PcbQueue::Side.

Referenced by Autoroute_One_Track(), and ReSetQueue().

121 {
122  struct PcbQueue* p, * q, * t;
123  int i, j;
124 
125  j = 0; // gcc warning fix
126 
127  if( (p = Save) != NULL ) /* try free list first */
128  {
129  Save = p->Next;
130  }
131  else if( ( p = (PcbQueue*) operator new( sizeof( PcbQueue ), std::nothrow ) ) == NULL )
132  {
133  return 0;
134  }
135 
136  p->Row = r;
137  p->Col = c;
138  p->Side = side;
139  i = (p->Dist = d) + (p->ApxDist = a);
140  p->Next = NULL;
141 
142  if( (q = Head) != NULL ) /* insert in proper position in list */
143  {
144  if( q->Dist + q->ApxDist > i ) /* insert at head */
145  {
146  p->Next = q; Head = p;
147  }
148  else /* search for proper position */
149  {
150  for( t = q, q = q->Next; q && i > ( j = q->Dist + q->ApxDist ); t = q, q = q->Next )
151  ;
152 
153  if( q && i == j && q->Row == r2 && q->Col == c2 )
154  {
155  /* insert after q, which is a goal node */
156  if( ( p->Next = q->Next ) == NULL )
157  Tail = p;
158 
159  q->Next = p;
160  }
161  else /* insert in front of q */
162  {
163  if( ( p->Next = q ) == NULL )
164  Tail = p;
165 
166  t->Next = p;
167  }
168  }
169  }
170  else /* empty search list */
171  {
172  Head = Tail = p;
173  }
174 
175  OpenNodes++;
176 
177  if( ++qlen > MaxNodes )
178  MaxNodes = qlen;
179 
180  return 1;
181 }
int OpenNodes
Definition: solve.cpp:85
int Dist
Definition: queue.cpp:49
struct PcbQueue * Next
Definition: queue.cpp:45
int Col
Definition: queue.cpp:47
static struct PcbQueue * Save
Definition: queue.cpp:56
int Row
Definition: queue.cpp:46
static struct PcbQueue * Tail
Definition: queue.cpp:55
int MaxNodes
Definition: solve.cpp:88
static struct PcbQueue * Head
Definition: queue.cpp:54
int Side
Definition: queue.cpp:48
static long qlen
Definition: queue.cpp:53
int ApxDist
Definition: queue.cpp:50

Variable Documentation

struct PcbQueue* Head = NULL
static

Definition at line 54 of file queue.cpp.

long qlen = 0
static

Definition at line 53 of file queue.cpp.

Referenced by GetQueue(), InitQueue(), ReSetQueue(), and SetQueue().

struct PcbQueue* Save = NULL
static

Definition at line 56 of file queue.cpp.

Referenced by GetQueue(), InitQueue(), and ReSetQueue().

struct PcbQueue* Tail = NULL
static

Definition at line 55 of file queue.cpp.