← Back to branch summary

~ubuntu-branches/ubuntu/hoary/kdemultimedia/hoary

« back to all changes in this revision

Viewing changes to arts/builder/autorouter.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Martin Schulze
  • Date: 2003-01-22 15:00:51 UTC
  • Revision ID: james.westby@ubuntu.com-20030122150051-uihwkdoxf15mi1tn
Tags: upstream-2.2.2
Import upstream version 2.2.2

Show diffs side-by-side

added added

removed removed

Lines of Context:
arts/builder/autorouter.cpp
 
1
        /*
 
2
 
 
3
        Copyright (C) 1998 Stefan Westerfeld
 
4
                       stefan@space.twc.de
 
5
 
 
6
    This program is free software; you can redistribute it and/or modify
 
7
    it under the terms of the GNU General Public License as published by
 
8
    the Free Software Foundation; either version 2 of the License, or
 
9
    (at your option) any later version.
 
10
 
 
11
    This program is distributed in the hope that it will be useful,
 
12
    but WITHOUT ANY WARRANTY; without even the implied warranty of
 
13
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
14
    GNU General Public License for more details.
 
15
 
 
16
    You should have received a copy of the GNU General Public License
 
17
    along with this program; if not, write to the Free Software
 
18
    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 
19
 
 
20
    */
 
21
 
 
22
#include "autorouter.h"
 
23
#include <assert.h>
 
24
#include <stdlib.h>
 
25
#include <stdio.h>
 
26
#include <unistd.h>
 
27
#include <arts/debug.h>
 
28
 
 
29
#ifndef HAVE_LIBPTHREAD
 
30
#define pthread_create(a,b,c,d) ;
 
31
#define pthread_join(a,b) ;
 
32
#define pthread_mutex_lock(a) ;
 
33
#define pthread_mutex_unlock(a) ;
 
34
#define pthread_mutex_init(a,b) ;
 
35
#define pthread_attr_init(a) ;
 
36
#endif
 
37
 
 
38
using namespace std;
 
39
 
 
40
void *startroute(void *where)
 
41
{
 
42
        ((AutoRouter *)where)->thread_command_loop();
 
43
        // just to prevent the compiler warning
 
44
        return 0;
 
45
}
 
46
 
 
47
AutoRouter::AutoRouter(int width, int height)
 
48
{
 
49
        int i;
 
50
        const int PRSIZE = 16; // size of the pseudo random table
 
51
 
 
52
//      field = new Field[width][height];         anybody knows how to do this correct?
 
53
 
 
54
        field = (Field **)malloc(sizeof(Field *)*width);
 
55
        completefield = (Field **)malloc(sizeof(Field *)*width);
 
56
 
 
57
        for(i=0;i<width;i++)
 
58
        {
 
59
                field[i] = (Field *)malloc(sizeof(Field)*height);
 
60
                completefield[i] = (Field *)calloc(1,sizeof(Field)*height);
 
61
        }
 
62
 
 
63
        for(i=0;i<255;i++) directionmask[i] = 0xffff;
 
64
 
 
65
        directionmask['d'] = ~(left | right);
 
66
        directionmask['u'] = ~(left | right);
 
67
        directionmask['l'] = ~(up | down);
 
68
        directionmask['r'] = ~(up | down);
 
69
 
 
70
        ownerindex['d'] = OWNER_UD;
 
71
        ownerindex['u'] = OWNER_UD;
 
72
        ownerindex['l'] = OWNER_LR;
 
73
        ownerindex['r'] = OWNER_LR;
 
74
 
 
75
        prstart = (long *)malloc((PRSIZE + 1) * sizeof(long));
 
76
        prp = prstart;
 
77
 
 
78
        int remaining[4];       
 
79
        for(i=0;i<PRSIZE;i++)
 
80
        {
 
81
                if((i & 3) == 0)
 
82
                {
 
83
                        int j;
 
84
                        for (j=0;j<4;j++) remaining[j] = j+1;
 
85
#ifdef AR_DEBUG
 
86
                        arts_debug("");
 
87
#endif
 
88
                }
 
89
 
 
90
                int rnd;
 
91
                do
 
92
                {
 
93
                        rnd = rand()&3;
 
94
                } while(!remaining[rnd]);
 
95
 
 
96
                *prp++ = remaining[rnd];
 
97
#ifdef AR_DEBUG
 
98
                arts_debug("%d ",remaining[rnd]);
 
99
#endif
 
100
                remaining[rnd]=0;
 
101
        }
 
102
        *prp = 0;
 
103
#ifdef AR_DEBUG
 
104
        arts_debug("");
 
105
#endif
 
106
        
 
107
        this->width = width;
 
108
        this->height = height;
 
109
 
 
110
        thread_terminate_now = false;           // not yet
 
111
        newowner = 1;
 
112
 
 
113
        thread_clear();
 
114
 
 
115
#ifdef HAVE_LIBPTHREAD
 
116
        pthread_attr_t attrs;
 
117
 
 
118
        pthread_attr_init(&attrs);
 
119
        pthread_mutex_init(&mutex_sync,0);
 
120
        pthread_mutex_init(&mutex_queue,0);
 
121
 
 
122
        pthread_create(&route_thread,&attrs,startroute,this);
 
123
#endif
 
124
 
 
125
        arts_debug("AR UP...");
 
126
}
 
127
 
 
128
AutoRouter::~AutoRouter()
 
129
{
 
130
        void *rc;
 
131
        pthread_mutex_lock(&mutex_queue);
 
132
        thread_terminate_now = true;
 
133
        pthread_mutex_unlock(&mutex_queue);
 
134
        pthread_join(route_thread,&rc);
 
135
        arts_debug("AR DOWN...");
 
136
}
 
137
 
 
138
void AutoRouter::queue(ARCommand *command)
 
139
{
 
140
#ifdef HAVE_LIBPTHREAD
 
141
        // threaded execution
 
142
        pthread_mutex_lock(&mutex_queue);
 
143
        if(command->isDestructive())
 
144
        {
 
145
                // ok, then we can kill the whole list, since this will clear
 
146
                // the whole results anyway
 
147
 
 
148
                while(command_queue.size() > 0)
 
149
                {
 
150
                        delete *command_queue.begin();
 
151
                        command_queue.pop_front();
 
152
                }
 
153
        }
 
154
        command_queue.push_back(command);
 
155
        pthread_mutex_unlock(&mutex_queue);
 
156
#else
 
157
        // immediate execution
 
158
        command->execute(this);
 
159
        delete command;
 
160
#endif
 
161
}
 
162
 
 
163
void AutoRouter::thread_command_loop()
 
164
{
 
165
        ARCommand *command;
 
166
        while(1)
 
167
        {
 
168
                command = 0;
 
169
 
 
170
 
 
171
                pthread_mutex_lock(&mutex_queue);
 
172
                if(command_queue.size() > 0)
 
173
                {
 
174
                        command = (*command_queue.begin());
 
175
                        command_queue.pop_front();
 
176
                }
 
177
                else
 
178
                {
 
179
                        if(thread_terminate_now) return;
 
180
                }
 
181
                pthread_mutex_unlock(&mutex_queue);
 
182
 
 
183
                if(command)
 
184
                {
 
185
                        command->execute(this);
 
186
                        delete command;
 
187
                } 
 
188
                else usleep(40000);
 
189
        }
 
190
}
 
191
 
 
192
void AutoRouter::sync()
 
193
{
 
194
        queue(new ARSyncCommand());
 
195
}
 
196
 
 
197
void ARSyncCommand::execute(AutoRouter *router)
 
198
{
 
199
        router->thread_sync();
 
200
}
 
201
 
 
202
void AutoRouter::thread_sync()
 
203
{
 
204
        int i;
 
205
        pthread_mutex_lock(&mutex_sync);
 
206
        for(i=0;i<width;i++) memcpy(completefield[i],field[i],sizeof(Field)*height);
 
207
        _needRedraw = true;
 
208
        pthread_mutex_unlock(&mutex_sync);
 
209
}
 
210
 
 
211
bool AutoRouter::needRedraw()
 
212
{
 
213
        bool result;
 
214
 
 
215
        pthread_mutex_lock(&mutex_sync);
 
216
        result = _needRedraw;
 
217
        _needRedraw = false;
 
218
#ifdef AR_DEBUG
 
219
        if(result) arts_debug("NEED REDRAW NOW!");
 
220
#endif
 
221
        pthread_mutex_unlock(&mutex_sync);
 
222
 
 
223
        return result;
 
224
}
 
225
 
 
226
void AutoRouter::clear()
 
227
{
 
228
        queue(new ARClearCommand());
 
229
}
 
230
 
 
231
bool ARCommand::isDestructive()
 
232
{
 
233
        return false;
 
234
}
 
235
 
 
236
bool ARClearCommand::isDestructive()
 
237
{
 
238
        return true;
 
239
}
 
240
 
 
241
void ARClearCommand::execute(AutoRouter *router)
 
242
{
 
243
        router->thread_clear();
 
244
}
 
245
 
 
246
void AutoRouter::thread_clear()
 
247
{
 
248
        int x,y;
 
249
 
 
250
        // if there is lots of movement on the screen this usleep will prevent
 
251
        // lots of calculations to be done; normally you shouldn't need it as
 
252
        // the calculations will take place in a seperate thread and don't
 
253
        // bother the gui
 
254
        //
 
255
        // usleep(300000);
 
256
 
 
257
        for (x=0;x<width;x++)
 
258
                for (y=0;y<height;y++)
 
259
                {
 
260
                        field[x][y].data = none;
 
261
                        field[x][y].penalty = 0;
 
262
                        field[x][y].owner[0] = -1;
 
263
                        field[x][y].owner[1] = -1;
 
264
                }
 
265
 
 
266
        //newowner = 1;
 
267
}
 
268
 
 
269
long AutoRouter::get(int x,int y)
 
270
{
 
271
        assert(x >= 0 && x < width);
 
272
        assert(y >= 0 && y < height);
 
273
 
 
274
        pthread_mutex_lock(&mutex_sync);
 
275
        long result = completefield[x][y].data;
 
276
        pthread_mutex_unlock(&mutex_sync);
 
277
        return(result);
 
278
}
 
279
 
 
280
void AutoRouter::getowners(int x, int y, long& ud_owner, long& lr_owner)
 
281
{
 
282
        assert(x >= 0 && x < width);
 
283
        assert(y >= 0 && y < height);
 
284
 
 
285
        pthread_mutex_lock(&mutex_sync);
 
286
        ud_owner = completefield[x][y].owner[OWNER_UD];
 
287
        lr_owner = completefield[x][y].owner[OWNER_LR];
 
288
        pthread_mutex_unlock(&mutex_sync);
 
289
}
 
290
 
 
291
void AutoRouter::set(int x1,int y1, int x2, int y2, long lt)
 
292
{
 
293
        queue(new ARSetCommand(x1,y1,x2,y2,lt));
 
294
}
 
295
 
 
296
ARSetCommand::ARSetCommand(int x1,int y1, int x2, int y2, long lt)
 
297
{
 
298
        _x1 = x1; _y1 = y1; _x2 = x2; _y2 = y2; _lt = lt;
 
299
}
 
300
 
 
301
void ARSetCommand::execute(AutoRouter *router)
 
302
{
 
303
        router->thread_set(_x1,_y1,_x2,_y2,_lt);
 
304
}
 
305
 
 
306
void AutoRouter::thread_set(int x1,int y1, int x2, int y2, long lt)
 
307
{
 
308
        int x,y;
 
309
        for(x=x1; x <= x2; x++)
 
310
        {
 
311
                for(y=y1; y <= y2; y++)
 
312
                {
 
313
                        assert(x >= 0 && x < width);
 
314
                        assert(y >= 0 && y < height);
 
315
 
 
316
                        if(lt & solid)
 
317
                        {
 
318
                                if((y-1) >= 0)
 
319
                                        field[x][y-1].penalty += 5;
 
320
 
 
321
                                if((y-2) >= 0)
 
322
                                        field[x][y-2].penalty += 2;
 
323
 
 
324
                                if((y+1) < height)
 
325
                                        field[x][y+1].penalty += 5;
 
326
 
 
327
                                if((y+2) < height)
 
328
                                        field[x][y+2].penalty += 2;
 
329
                        }
 
330
                        field[x][y].data = lt;
 
331
                        field[x][y].owner[0] = 0;
 
332
                        field[x][y].owner[1] = 0;               // don't pass
 
333
                }
 
334
        }
 
335
}
 
336
 
 
337
 
 
338
// gms = global min score: score of the best connection that was achieved
 
339
// new routing steps are only tried if their score does not exceed gms
 
340
 
 
341
int gms, gmsd;
 
342
 
 
343
long AutoRouter::connect(int x1, int y1, int x2, int y2, long owner)
 
344
{
 
345
        if(owner == 0) owner = newowner++;
 
346
 
 
347
        queue(new ARConnectCommand(x1,y1,x2,y2,owner));
 
348
 
 
349
        return(owner);
 
350
}
 
351
 
 
352
ARConnectCommand::ARConnectCommand(int x1, int y1, int x2, int y2, long owner)
 
353
{
 
354
        _x1 = x1; _y1 = y1; _x2 = x2; _y2 = y2; _owner = owner;
 
355
}
 
356
 
 
357
void ARConnectCommand::execute(AutoRouter *router)
 
358
{
 
359
        router->thread_connect(_x1,_y1,_x2,_y2,_owner);
 
360
}
 
361
 
 
362
void AutoRouter::thread_connect(int x1, int y1, int x2, int y2, long owner)
 
363
{
 
364
        int x,y;
 
365
        long dat_source, dat_dest;
 
366
 
 
367
        currentowner = owner;
 
368
 
 
369
        // clear data(source) & data(dest) first and restore later, since they
 
370
        // might be solid
 
371
 
 
372
#ifdef AR_DEBUG
 
373
        arts_debug("-field[x1][y1].owner[0..1] = %ld,%ld",field[x1][y1].owner[0],
 
374
                                                                                                        field[x1][y1].owner[1]);
 
375
        arts_debug("-field[x2][y2].owner[0..1] = %ld,%ld",field[x2][y2].owner[0],
 
376
                                                                                                        field[x2][y2].owner[1]);
 
377
#endif
 
378
        dat_source = field[x1][y1].data; field[x1][y1].data = none;
 
379
        dat_dest   = field[x2][y2].data; field[x2][y2].data = none;
 
380
 
 
381
        for (x=0;x<width;x++)
 
382
                for (y=0;y<height;y++)
 
383
                        field[x][y].minscore = 20000;
 
384
 
 
385
#ifdef AR_DEBUG
 
386
        arts_debug("autorouter: trying to connect %d,%d with %d,%d (owner %ld)",
 
387
                                                                x1,y1,x2,y2,owner);
 
388
#endif
 
389
        QString history("");
 
390
 
 
391
        gmsd = 0; gms=20000;
 
392
 
 
393
        int activelist = 0;
 
394
        triesleft = 0;
 
395
 
 
396
        prp = prstart;
 
397
        q_try_connect(x1,y1,x2,y2,0,0,history);
 
398
 
 
399
        while(triesleft)
 
400
        {
 
401
                list<tryinfo>::iterator ti,minti;
 
402
                int mintry=20000;
 
403
 
 
404
                while(!trylist[activelist].size()) activelist++;
 
405
                list<tryinfo>& activetrylist = trylist[activelist];
 
406
 
 
407
                minti = activetrylist.begin();
 
408
                ti = activetrylist.begin();
 
409
                while(ti != activetrylist.end())
 
410
                {
 
411
                        if((*ti).score < mintry)
 
412
                        {
 
413
                                mintry = (*ti).score;
 
414
                                minti = ti;
 
415
                        }
 
416
                        ti++;
 
417
                }
 
418
 
 
419
                try_connect((*minti).x1, (*minti).y1,
 
420
                                        (*minti).x2, (*minti).y2, (*minti).score, (*minti).depth, (*minti).history);
 
421
                activetrylist.erase(minti);
 
422
                triesleft--;
 
423
        }
 
424
        //arts_debug("gmsd= %d",gmsd);
 
425
 
 
426
        field[x1][y1].data = dat_source;
 
427
        field[x2][y2].data = dat_dest;
 
428
 
 
429
        if(gms != 20000)
 
430
        {
 
431
                //arts_debug("minhistory for this connection is %s",minhistory.data());
 
432
                //arts_debug("minscore for that was %d",gms);
 
433
 
 
434
                char *walk = (char*)minhistory.ascii();
 
435
 
 
436
                int x = x1;
 
437
                int y = y1;
 
438
 
 
439
                while(*walk)
 
440
                {
 
441
                        field[x][y].owner[ownerindex[*walk]] = currentowner;
 
442
                        switch(*walk)
 
443
                        {
 
444
                                case 'd':       field[x][y++].data |= down;
 
445
                                                        field[x][y].data |= up;
 
446
                                                break;
 
447
                                case 'u':       field[x][y--].data |= up;
 
448
                                                        field[x][y].data |= down;
 
449
                                                break;
 
450
                                case 'l':       field[x--][y].data |= left;
 
451
                                                        field[x][y].data |= right;
 
452
                                                break;
 
453
                                case 'r':       field[x++][y].data |= right;
 
454
                                                        field[x][y].data |= left;
 
455
                                                break;
 
456
                        }
 
457
                        field[x][y].owner[ownerindex[*walk]] = currentowner;
 
458
                        walk++;
 
459
                }
 
460
        }
 
461
        else
 
462
        {
 
463
#ifdef AR_DEBUG
 
464
                arts_debug("!! sorry, this connection is impossible !!");
 
465
#endif
 
466
        }
 
467
}
 
468
 
 
469
void AutoRouter::q_try_connect(int x1, int y1, int x2, int y2, int score, int depth, QString history)
 
470
{
 
471
        tryinfo newtry;
 
472
 
 
473
        newtry.x1 = x1;
 
474
        newtry.x2 = x2;
 
475
        newtry.y1 = y1;
 
476
        newtry.y2 = y2;
 
477
        newtry.score = score;
 
478
        newtry.depth = depth;
 
479
        newtry.history = history;
 
480
 
 
481
        int targetlist = newtry.score/5;
 
482
        if(targetlist > 1023) targetlist = 1023;
 
483
 
 
484
        trylist[targetlist].push_back(newtry);
 
485
        triesleft++;
 
486
}
 
487
 
 
488
void AutoRouter::try_connect(int x1, int y1, int x2, int y2, int score, int depth, QString history)
 
489
{
 
490
        char *walk = (char*)history.ascii();
 
491
 
 
492
// check if we can go here:
 
493
 
 
494
        if(x1 < 0 || x1 >= width) return;
 
495
        if(y1 < 0 || y1 >= width) return;
 
496
 
 
497
        if(depth > 0)
 
498
        {
 
499
                if(field[x1][y1].data != 0) score += 100;
 
500
                // going over a field where already connections are is bad...
 
501
 
 
502
                if(directionmask[walk[depth-1]] & field[x1][y1].data)
 
503
                {
 
504
                        // someone already uses that field... we can continue
 
505
                        // only if the connection has the same sourceport
 
506
 
 
507
                        long fieldowner = field[x1][y1].owner[ownerindex[walk[depth-1]]];
 
508
 
 
509
                        if(fieldowner != -1)            // used?
 
510
                        {
 
511
                                if(fieldowner != currentowner) return;
 
512
                                score -= 100;
 
513
                                // ... or a good idea, if the connections are from the
 
514
                                // same owner
 
515
                        }
 
516
                }
 
517
        }
 
518
 
 
519
        //score++;
 
520
        score += abs(x1-x2) + abs(y1-y2);
 
521
        score += field[x1][y1].penalty;
 
522
 
 
523
        if(depth > 2)
 
524
                if(walk[depth-2] != walk[depth-1]) score += 100;
 
525
        
 
526
        if(field[x1][y1].minscore <= score) return;
 
527
        if(score > gms) { gmsd++; return; }
 
528
 
 
529
        field[x1][y1].minscore = score;
 
530
 
 
531
// check if we are where we wanted to be:
 
532
 
 
533
        if(x1 == x2 && y1 == y2) {
 
534
                // success
 
535
 
 
536
                if(score < gms)
 
537
                {
 
538
                        // best solution until now
 
539
                        minhistory = history;
 
540
                        gms = score;
 
541
                }
 
542
                return;
 
543
        }
 
544
 
 
545
// search next place to go; take some pseudo random direction order
 
546
// this method improves search speed ;)
 
547
 
 
548
        depth++;
 
549
 
 
550
        int i;
 
551
        for(i=0;i<4;i++)
 
552
        {
 
553
                switch(*prp++)
 
554
                {
 
555
                        case 0: i--;
 
556
                                        prp = prstart;
 
557
                                break;
 
558
                        case 1: q_try_connect(x1-1,y1,x2,y2,score,depth,history+"l");
 
559
                                break;
 
560
                        case 2: q_try_connect(x1+1,y1,x2,y2,score,depth,history+"r");
 
561
                                break;
 
562
                        case 3: q_try_connect(x1,y1-1,x2,y2,score,depth,history+"u");
 
563
                                break;
 
564
                        case 4: q_try_connect(x1,y1+1,x2,y2,score,depth,history+"d");
 
565
                                break;
 
566
                }
 
567
        }
 
568
}
 
569