KiCad PCB EDA Suite
queue.cpp
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
4  * Copyright (C) 2015 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr
5  * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
6  * Copyright (C) 2011 Wayne Stambaugh <stambaughw@verizon.net>
7  *
8  * Copyright (C) 1992-2015 KiCad Developers, see change_log.txt for contributors.
9  *
10  * First copyright (C) Randy Nevin, 1989 (see PCBCA package)
11  *
12  * This program is free software; you can redistribute it and/or
13  * modify it under the terms of the GNU General Public License
14  * as published by the Free Software Foundation; either version 2
15  * of the License, or (at your option) any later version.
16  *
17  * This program is distributed in the hope that it will be useful,
18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20  * GNU General Public License for more details.
21  *
22  * You should have received a copy of the GNU General Public License
23  * along with this program; if not, you may find one here:
24  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
25  * or you may search the http://www.gnu.org website for the version 2 license,
26  * or you may write to the Free Software Foundation, Inc.,
27  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
28  */
29 
30 
35 #include <fctsys.h>
36 #include <common.h>
37 
38 #include <pcbnew.h>
39 #include <autorout.h>
40 #include <cell.h>
41 
42 
43 struct PcbQueue /* search queue structure */
44 {
45  struct PcbQueue* Next;
46  int Row; /* current row */
47  int Col; /* current column */
48  int Side; /* 0=top, 1=bottom */
49  int Dist; /* path distance to this cell so far */
50  int ApxDist; /* approximate distance to target from here */
51 };
52 
53 static long qlen = 0; /* current queue length */
54 static struct PcbQueue* Head = NULL;
55 static struct PcbQueue* Tail = NULL;
56 static struct PcbQueue* Save = NULL; /* hold empty queue structs */
57 
58 
59 /* Free the memory used for storing all the queue */
60 void FreeQueue()
61 {
62  struct PcbQueue* p;
63 
64  InitQueue();
65 
66  while( (p = Save) != NULL )
67  {
68  Save = p->Next;
69  delete p;
70  }
71 }
72 
73 
74 /* initialize the search queue */
75 void InitQueue()
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 }
88 
89 
90 /* get search queue item from list */
91 void GetQueue( int* r, int* c, int* s, int* d, int* a )
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 }
113 
114 
115 /* add a search node to the list
116  * :
117  * 1 - OK
118  * 0 - Failed to allocate memory.
119  */
120 bool SetQueue( int r, int c, int side, int d, int a, int r2, int c2 )
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 }
182 
183 
184 /* reposition node in list */
185 void ReSetQueue( int r, int c, int s, int d, int a, int r2, int c2 )
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
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
int MoveNodes
Definition: solve.cpp:87
void InitQueue()
Definition: queue.cpp:75
static struct PcbQueue * Save
Definition: queue.cpp:56
void ReSetQueue(int r, int c, int s, int d, int a, int r2, int c2)
Definition: queue.cpp:185
int Row
Definition: queue.cpp:46
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
void GetQueue(int *r, int *c, int *s, int *d, int *a)
Definition: queue.cpp:91
int ClosNodes
Definition: solve.cpp:86
The common library.
void FreeQueue()
Definition: queue.cpp:60
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