Fossil SCM

Improvements to the graph layout algorithm yielding a more compact graph in many cases.

drh 2010-12-20 01:06 trunk
Commit ea61f4aa551df588f55f1734bea6bd60e1a79afc
Parent 5ae54b39fd739db…
3 files changed +4 -10 +6 -2 +3 -2
~ src/graph.c ~ src/timeline.c ~ src/translate.c
M src/graph.c
+4 -10
--- src/graph.c
+++ src/graph.c
@@ -245,13 +245,10 @@
245245
 while( pPrior->idx > pCurrent->idx ){
246246
 pPrior->railInUse |= mask;
247247
 pPrior = pPrior->pPrev;
248248
 assert( pPrior!=0 );
249249
 }
250
- if( pCurrent->pPrev ){
251
- pCurrent->pPrev->railInUse |= mask;
252
- }
253250
 }
254251
 }
255252
256253
257254
 /*
@@ -380,20 +377,19 @@
380377
 }
381378
 pRow->iRail = findFreeRail(p, 0, pParent->idx, inUse, pParent->iRail);
382379
 pParent->aiRaiser[pRow->iRail] = pRow->idx;
383380
 }
384381
 mask = 1<<pRow->iRail;
385
-/* if( pRow->pPrev ) pRow->pPrev->railInUse |= mask; */
386
- if( pRow->pNext ) pRow->pNext->railInUse |= mask;
382
+ pRow->railInUse |= mask;
387383
 if( pRow->pChild==0 ){
388384
 inUse &= ~mask;
389385
 }else{
390386
 inUse |= mask;
391387
 assignChildrenToRail(pRow);
392388
 }
393389
 if( pParent ){
394
- for(pLoop=pParent; pLoop && pLoop!=pRow; pLoop=pLoop->pPrev){
390
+ for(pLoop=pParent->pPrev; pLoop && pLoop!=pRow; pLoop=pLoop->pPrev){
395391
 pLoop->railInUse |= mask;
396392
 }
397393
 }
398394
 }
399395
@@ -405,14 +401,13 @@
405401
 int parentRid = pRow->aParent[i];
406402
 pDesc = hashFind(p, parentRid);
407403
 if( pDesc==0 ) continue;
408404
 if( pDesc->mergeOut<0 ){
409405
 int iTarget = (pRow->iRail + pDesc->iRail)/2;
410
- pDesc->mergeOut = findFreeRail(p, pRow->idx, pDesc->idx, 0, iTarget);
406
+ pDesc->mergeOut = findFreeRail(p, pRow->idx, pDesc->idx-1, 0, iTarget);
411407
 pDesc->mergeUpto = pRow->idx;
412408
 mask = 1<<pDesc->mergeOut;
413
- pDesc->railInUse |= mask;
414409
 for(pLoop=pRow->pNext; pLoop && pLoop->rid!=parentRid;
415410
 pLoop=pLoop->pNext){
416411
 pLoop->railInUse |= mask;
417412
 }
418413
 }
@@ -428,14 +423,13 @@
428423
 if( !pRow->isDup ) continue;
429424
 pDesc = hashFind(p, pRow->rid);
430425
 assert( pDesc!=0 && pDesc!=pRow );
431426
 if( pDesc->mergeOut<0 ){
432427
 int iTarget = (pRow->iRail + pDesc->iRail)/2;
433
- pDesc->mergeOut = findFreeRail(p, pRow->idx, pDesc->idx, 0, iTarget);
428
+ pDesc->mergeOut = findFreeRail(p, pRow->idx, pDesc->idx-1, 0, iTarget);
434429
 pDesc->mergeUpto = pRow->idx;
435430
 mask = 1<<pDesc->mergeOut;
436
- pDesc->railInUse |= mask;
437431
 for(pLoop=pRow->pNext; pLoop && pLoop!=pDesc; pLoop=pLoop->pNext){
438432
 pLoop->railInUse |= mask;
439433
 }
440434
 }
441435
 pRow->mergeIn |= 1<<pDesc->mergeOut;
442436
--- src/graph.c
+++ src/graph.c
@@ -245,13 +245,10 @@
245 while( pPrior->idx > pCurrent->idx ){
246 pPrior->railInUse |= mask;
247 pPrior = pPrior->pPrev;
248 assert( pPrior!=0 );
249 }
250 if( pCurrent->pPrev ){
251 pCurrent->pPrev->railInUse |= mask;
252 }
253 }
254 }
255
256
257 /*
@@ -380,20 +377,19 @@
380 }
381 pRow->iRail = findFreeRail(p, 0, pParent->idx, inUse, pParent->iRail);
382 pParent->aiRaiser[pRow->iRail] = pRow->idx;
383 }
384 mask = 1<<pRow->iRail;
385 /* if( pRow->pPrev ) pRow->pPrev->railInUse |= mask; */
386 if( pRow->pNext ) pRow->pNext->railInUse |= mask;
387 if( pRow->pChild==0 ){
388 inUse &= ~mask;
389 }else{
390 inUse |= mask;
391 assignChildrenToRail(pRow);
392 }
393 if( pParent ){
394 for(pLoop=pParent; pLoop && pLoop!=pRow; pLoop=pLoop->pPrev){
395 pLoop->railInUse |= mask;
396 }
397 }
398 }
399
@@ -405,14 +401,13 @@
405 int parentRid = pRow->aParent[i];
406 pDesc = hashFind(p, parentRid);
407 if( pDesc==0 ) continue;
408 if( pDesc->mergeOut<0 ){
409 int iTarget = (pRow->iRail + pDesc->iRail)/2;
410 pDesc->mergeOut = findFreeRail(p, pRow->idx, pDesc->idx, 0, iTarget);
411 pDesc->mergeUpto = pRow->idx;
412 mask = 1<<pDesc->mergeOut;
413 pDesc->railInUse |= mask;
414 for(pLoop=pRow->pNext; pLoop && pLoop->rid!=parentRid;
415 pLoop=pLoop->pNext){
416 pLoop->railInUse |= mask;
417 }
418 }
@@ -428,14 +423,13 @@
428 if( !pRow->isDup ) continue;
429 pDesc = hashFind(p, pRow->rid);
430 assert( pDesc!=0 && pDesc!=pRow );
431 if( pDesc->mergeOut<0 ){
432 int iTarget = (pRow->iRail + pDesc->iRail)/2;
433 pDesc->mergeOut = findFreeRail(p, pRow->idx, pDesc->idx, 0, iTarget);
434 pDesc->mergeUpto = pRow->idx;
435 mask = 1<<pDesc->mergeOut;
436 pDesc->railInUse |= mask;
437 for(pLoop=pRow->pNext; pLoop && pLoop!=pDesc; pLoop=pLoop->pNext){
438 pLoop->railInUse |= mask;
439 }
440 }
441 pRow->mergeIn |= 1<<pDesc->mergeOut;
442
--- src/graph.c
+++ src/graph.c
@@ -245,13 +245,10 @@
245 while( pPrior->idx > pCurrent->idx ){
246 pPrior->railInUse |= mask;
247 pPrior = pPrior->pPrev;
248 assert( pPrior!=0 );
249 }
 
 
 
250 }
251 }
252
253
254 /*
@@ -380,20 +377,19 @@
377 }
378 pRow->iRail = findFreeRail(p, 0, pParent->idx, inUse, pParent->iRail);
379 pParent->aiRaiser[pRow->iRail] = pRow->idx;
380 }
381 mask = 1<<pRow->iRail;
382 pRow->railInUse |= mask;
 
383 if( pRow->pChild==0 ){
384 inUse &= ~mask;
385 }else{
386 inUse |= mask;
387 assignChildrenToRail(pRow);
388 }
389 if( pParent ){
390 for(pLoop=pParent->pPrev; pLoop && pLoop!=pRow; pLoop=pLoop->pPrev){
391 pLoop->railInUse |= mask;
392 }
393 }
394 }
395
@@ -405,14 +401,13 @@
401 int parentRid = pRow->aParent[i];
402 pDesc = hashFind(p, parentRid);
403 if( pDesc==0 ) continue;
404 if( pDesc->mergeOut<0 ){
405 int iTarget = (pRow->iRail + pDesc->iRail)/2;
406 pDesc->mergeOut = findFreeRail(p, pRow->idx, pDesc->idx-1, 0, iTarget);
407 pDesc->mergeUpto = pRow->idx;
408 mask = 1<<pDesc->mergeOut;
 
409 for(pLoop=pRow->pNext; pLoop && pLoop->rid!=parentRid;
410 pLoop=pLoop->pNext){
411 pLoop->railInUse |= mask;
412 }
413 }
@@ -428,14 +423,13 @@
423 if( !pRow->isDup ) continue;
424 pDesc = hashFind(p, pRow->rid);
425 assert( pDesc!=0 && pDesc!=pRow );
426 if( pDesc->mergeOut<0 ){
427 int iTarget = (pRow->iRail + pDesc->iRail)/2;
428 pDesc->mergeOut = findFreeRail(p, pRow->idx, pDesc->idx-1, 0, iTarget);
429 pDesc->mergeUpto = pRow->idx;
430 mask = 1<<pDesc->mergeOut;
 
431 for(pLoop=pRow->pNext; pLoop && pLoop!=pDesc; pLoop=pLoop->pNext){
432 pLoop->railInUse |= mask;
433 }
434 }
435 pRow->mergeIn |= 1<<pDesc->mergeOut;
436
M src/timeline.c
+6 -2
--- src/timeline.c
+++ src/timeline.c
@@ -462,11 +462,15 @@
462462
 @ var x1 = p.mo*20 + left;
463463
 @ var y1 = p.y-3;
464464
 @ var x0 = x1>p.x ? p.x+7 : p.x-6;
465465
 @ var u = rowinfo[p.mu-1];
466466
 @ var y0 = u.y+5;
467
- @ drawThinLine(x0,y1,x1,y1);
467
+ @ if( x1==p.x ){
468
+ @ y1 -= 2;
469
+ @ }else{
470
+ @ drawThinLine(x0,y1,x1,y1);
471
+ @ }
468472
 @ drawThinLine(x1,y0,x1,y1);
469473
 @ }
470474
 @ var n = p.au.length;
471475
 @ for(var i=0; i<n; i+=2){
472476
 @ var x1 = p.au[i]*20 + left;
@@ -477,11 +481,11 @@
477481
 @ }
478482
 @ for(var j in p.mi){
479483
 @ var y0 = p.y+5;
480484
 @ var mx = p.mi[j]*20 + left;
481485
 @ if( mx>p.x ){
482
- @ drawThinArrow(y0,mx,p.x+5);
486
+ @ drawThinArrow(y0,mx,p.x+6);
483487
 @ }else{
484488
 @ drawThinArrow(y0,mx,p.x-5);
485489
 @ }
486490
 @ }
487491
 @ }
488492
--- src/timeline.c
+++ src/timeline.c
@@ -462,11 +462,15 @@
462 @ var x1 = p.mo*20 + left;
463 @ var y1 = p.y-3;
464 @ var x0 = x1>p.x ? p.x+7 : p.x-6;
465 @ var u = rowinfo[p.mu-1];
466 @ var y0 = u.y+5;
467 @ drawThinLine(x0,y1,x1,y1);
 
 
 
 
468 @ drawThinLine(x1,y0,x1,y1);
469 @ }
470 @ var n = p.au.length;
471 @ for(var i=0; i<n; i+=2){
472 @ var x1 = p.au[i]*20 + left;
@@ -477,11 +481,11 @@
477 @ }
478 @ for(var j in p.mi){
479 @ var y0 = p.y+5;
480 @ var mx = p.mi[j]*20 + left;
481 @ if( mx>p.x ){
482 @ drawThinArrow(y0,mx,p.x+5);
483 @ }else{
484 @ drawThinArrow(y0,mx,p.x-5);
485 @ }
486 @ }
487 @ }
488
--- src/timeline.c
+++ src/timeline.c
@@ -462,11 +462,15 @@
462 @ var x1 = p.mo*20 + left;
463 @ var y1 = p.y-3;
464 @ var x0 = x1>p.x ? p.x+7 : p.x-6;
465 @ var u = rowinfo[p.mu-1];
466 @ var y0 = u.y+5;
467 @ if( x1==p.x ){
468 @ y1 -= 2;
469 @ }else{
470 @ drawThinLine(x0,y1,x1,y1);
471 @ }
472 @ drawThinLine(x1,y0,x1,y1);
473 @ }
474 @ var n = p.au.length;
475 @ for(var i=0; i<n; i+=2){
476 @ var x1 = p.au[i]*20 + left;
@@ -477,11 +481,11 @@
481 @ }
482 @ for(var j in p.mi){
483 @ var y0 = p.y+5;
484 @ var mx = p.mi[j]*20 + left;
485 @ if( mx>p.x ){
486 @ drawThinArrow(y0,mx,p.x+6);
487 @ }else{
488 @ drawThinArrow(y0,mx,p.x-5);
489 @ }
490 @ }
491 @ }
492
M src/translate.c
+3 -2
--- src/translate.c
+++ src/translate.c
@@ -13,12 +13,13 @@
1313
 ** [email protected]
1414
 ** http://www.hwaci.com/drh/
1515
 **
1616
 *******************************************************************************
1717
 **
18
-** begin with the "@" character are translated into cgi_printf() statements
19
-** and the translated code is written on standard output.
18
+** Input lines that begin with the "@" character are translated into
19
+** either cgi_printf() statements or string literals and the
20
+** translated code is written on standard output.
2021
 **
2122
 ** The problem this program is attempt to solve is as follows: When
2223
 ** writing CGI programs in C, we typically want to output a lot of HTML
2324
 ** text to standard output. In pure C code, this involves doing a
2425
 ** printf() with a big string containing all that text. But we have
2526
--- src/translate.c
+++ src/translate.c
@@ -13,12 +13,13 @@
13 ** [email protected]
14 ** http://www.hwaci.com/drh/
15 **
16 *******************************************************************************
17 **
18 ** begin with the "@" character are translated into cgi_printf() statements
19 ** and the translated code is written on standard output.
 
20 **
21 ** The problem this program is attempt to solve is as follows: When
22 ** writing CGI programs in C, we typically want to output a lot of HTML
23 ** text to standard output. In pure C code, this involves doing a
24 ** printf() with a big string containing all that text. But we have
25
--- src/translate.c
+++ src/translate.c
@@ -13,12 +13,13 @@
13 ** [email protected]
14 ** http://www.hwaci.com/drh/
15 **
16 *******************************************************************************
17 **
18 ** Input lines that begin with the "@" character are translated into
19 ** either cgi_printf() statements or string literals and the
20 ** translated code is written on standard output.
21 **
22 ** The problem this program is attempt to solve is as follows: When
23 ** writing CGI programs in C, we typically want to output a lot of HTML
24 ** text to standard output. In pure C code, this involves doing a
25 ** printf() with a big string containing all that text. But we have
26

Keyboard Shortcuts

Open search /
Next entry (timeline) j
Previous entry (timeline) k
Open focused entry Enter
Show this help ?
Toggle theme Top nav button