queue.cpp 5.77 KB
Newer Older
1 2 3
/*
 * This program source code file is part of KiCad, a free EDA CAD application.
 *
4 5
 * Copyright (C) 2012 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr
 * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
6
 * Copyright (C) 2011 Wayne Stambaugh <stambaughw@verizon.net>
7 8 9 10
 *
 * Copyright (C) 1992-2012 KiCad Developers, see change_log.txt for contributors.
 *
 * First copyright (C) Randy Nevin, 1989 (see PCBCA package)
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
 *
 * 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, you may find one here:
 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
 * or you may search the http://www.gnu.org website for the version 2 license,
 * or you may write to the Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
 */

30

31 32 33
/**
 * @file queue.cpp
 */
34

35 36
#include <fctsys.h>
#include <common.h>
37

38 39 40
#include <pcbnew.h>
#include <autorout.h>
#include <cell.h>
41

42

43 44
struct PcbQueue /* search queue structure */
{
45
    struct PcbQueue* Next;
46 47 48 49 50
    int              Row;       /* current row                  */
    int              Col;       /* current column               */
    int              Side;      /* 0=top, 1=bottom              */
    int              Dist;      /* path distance to this cell so far        */
    int              ApxDist;   /* approximate distance to target from here */
51 52
};

53 54 55 56 57
static long             qlen = 0;   /* current queue length */
static struct PcbQueue* Head = NULL;
static struct PcbQueue* Tail = NULL;
static struct PcbQueue* Save = NULL;    /* hold empty queue structs */

58

59
void InitQueue();
60 61
void GetQueue( int*, int*, int*, int*, int* );
int  SetQueue( int, int, int, int, int, int, int );
62 63 64 65
void ReSetQueue( int, int, int, int, int, int, int );


/* Free the memory used for storing all the queue */
66
void FreeQueue()
67
{
68
    struct PcbQueue* p;
69

70
    InitQueue();
71

72 73
    while( (p = Save) != NULL )
    {
74 75
        Save = p->Next;
        delete p;
76
    }
77
}
78

79 80

/* initialize the search queue */
81
void InitQueue()
82
{
83
    struct PcbQueue* p;
84

85 86 87 88 89 90 91 92 93
    while( (p = Head) != NULL )
    {
        Head    = p->Next;
        p->Next = Save; Save = p;
    }

    Tail = NULL;
    OpenNodes = ClosNodes = MoveNodes = MaxNodes = qlen = 0;
}
94 95 96


/* get search queue item from list */
97
void GetQueue( int* r, int* c, int* s, int* d, int* a )
98
{
99 100 101 102 103 104 105
    struct PcbQueue* p;

    if( (p = Head) != NULL )  /* return first item in list */
    {
        *r = p->Row; *c = p->Col;
        *s = p->Side;
        *d = p->Dist; *a = p->ApxDist;
106

107 108 109 110 111 112 113 114 115 116 117
        if( (Head = p->Next) == NULL )
            Tail = NULL;

        /* put node on free list */
        p->Next = Save; Save = p;
        ClosNodes++; qlen--;
    }
    else /* empty list */
    {
        *r = *c = *s = *d = *a = ILLEGAL;
    }
118 119 120 121
}


/* add a search node to the list
122 123 124
 *  Return:
 *      1 - OK
 *      0 - Failed to allocate memory.
125 126
 */
int SetQueue( int r, int c, int side, int d, int a, int r2, int c2 )
127
{
128
    struct PcbQueue* p, * q, * t;
f3nix's avatar
f3nix committed
129
    int i, j;
130 131 132 133 134 135 136

    j = 0;                      // gcc warning fix

    if( (p = Save) != NULL )    /* try free list first */
    {
        Save = p->Next;
    }
137
    else if( ( p = (PcbQueue*) operator new( sizeof( PcbQueue ), std::nothrow ) ) == NULL )
138
    {
139
        return 0;
140
    }
141 142 143 144 145 146

    p->Row  = r;
    p->Col  = c;
    p->Side = side;
    i = (p->Dist = d) + (p->ApxDist = a);
    p->Next = NULL;
147

148 149 150 151 152 153 154 155
    if( (q = Head) != NULL ) /* insert in proper position in list */
    {
        if( q->Dist + q->ApxDist > i ) /* insert at head */
        {
            p->Next = q; Head = p;
        }
        else   /* search for proper position */
        {
156
            for( t = q, q = q->Next; q && i > ( j = q->Dist + q->ApxDist ); t = q, q = q->Next )
157 158 159 160 161 162 163
                ;

            if( q && i == j && q->Row == r2 && q->Col == c2 )
            {
                /* insert after q, which is a goal node */
                if( ( p->Next = q->Next ) == NULL )
                    Tail = p;
164

165 166 167 168 169 170
                q->Next = p;
            }
            else  /* insert in front of q */
            {
                if( ( p->Next = q ) == NULL )
                    Tail = p;
171

172 173 174 175 176
                t->Next = p;
            }
        }
    }
    else /* empty search list */
177
    {
178
        Head = Tail = p;
179 180
    }

181
    OpenNodes++;
182

183 184
    if( ++qlen > MaxNodes )
        MaxNodes = qlen;
185

186
    return 1;
187 188 189 190
}


/* reposition node in list */
191
void ReSetQueue( int r, int c, int s, int d, int a, int r2, int c2 )
192
{
193 194 195 196 197 198 199 200 201 202 203 204 205 206
    struct PcbQueue* p, * q;

    /* first, see if it is already in the list */
    for( q = NULL, p = Head; p; q = p, p = p->Next )
    {
        if( p->Row == r && p->Col == c && p->Side == s )
        {
            /* old one to remove */
            if( q )
            {
                if( ( q->Next = p->Next ) == NULL )
                    Tail = q;
            }
            else if( ( Head = p->Next ) == NULL )
207
            {
208
                Tail = NULL;
209 210
            }

211 212 213 214 215 216 217 218 219 220 221
            p->Next = Save;
            Save = p;
            OpenNodes--;
            MoveNodes++;
            qlen--;
            break;
        }
    }

    if( !p )            /* not found, it has already been closed once */
        ClosNodes--;    /* we will close it again, but just count once */
222

223 224
    /* if it was there, it's gone now; insert it at the proper position */
    SetQueue( r, c, s, d, a, r2, c2 );
225
}