Fossil SCM

Minor simplification to the graph layout logic.

drh 2016-03-18 13:06 trunk
Commit f73411025e8ebec70029040962f5faf7f419e1ab
Parent 64d321514d1fe94…
1 file changed +8 -15
~ src/graph.c
M src/graph.c
+8 -15
--- src/graph.c
+++ src/graph.c
@@ -218,17 +218,17 @@
218218
 ** top and bottom, inclusive.
219219
 */
220220
 static int findFreeRail(
221221
 GraphContext *p, /* The graph context */
222222
 int top, int btm, /* Span of rows for which the rail is needed */
223
- u64 inUseMask, /* Mask or rails already in use */
224223
 int iNearto /* Find rail nearest to this rail */
225224
 ){
226225
 GraphRow *pRow;
227226
 int i;
228227
 int iBest = 0;
229228
 int iBestDist = 9999;
229
+ u64 inUseMask = 0;
230230
 for(pRow=p->pFirst; pRow && pRow->idx<top; pRow=pRow->pNext){}
231231
 while( pRow && pRow->idx<=btm ){
232232
 inUseMask |= pRow->railInUse;
233233
 pRow = pRow->pNext;
234234
 }
@@ -299,12 +299,11 @@
299299
 pParent->mergeUpto = pChild->idx;
300300
 }else{
301301
 /* The thin merge arrow riser is taller than the thick primary
302302
 ** child riser, so use separate rails. */
303303
 int iTarget = pParent->iRail;
304
- pParent->mergeOut = findFreeRail(p, pChild->idx, pParent->idx-1,
305
- 0, iTarget);
304
+ pParent->mergeOut = findFreeRail(p, pChild->idx, pParent->idx-1, iTarget);
306305
 pParent->mergeUpto = pChild->idx;
307306
 mask = BIT(pParent->mergeOut);
308307
 for(pLoop=pChild->pNext; pLoop && pLoop->rid!=pParent->rid;
309308
 pLoop=pLoop->pNext){
310309
 pLoop->railInUse |= mask;
@@ -335,11 +334,10 @@
335334
 */
336335
 void graph_finish(GraphContext *p, int omitDescenders){
337336
 GraphRow *pRow, *pDesc, *pDup, *pLoop, *pParent;
338337
 int i;
339338
 u64 mask;
340
- u64 inUse;
341339
 int hasDup = 0; /* True if one or more isDup entries */
342340
 const char *zTrunk;
343341
344342
 if( p==0 || p->pFirst==0 || p->nErr ) return;
345343
 p->nErr = 1; /* Assume an error until proven otherwise */
@@ -440,11 +438,11 @@
440438
 }else {
441439
 if( pRow->iRail>=0 ) continue;
442440
 }
443441
 if( pRow->nParent==0 || hashFind(p,pRow->aParent[0])==0 ){
444442
 if( omitDescenders ){
445
- pRow->iRail = findFreeRail(p, pRow->idxTop, pRow->idx, 0, 0);
443
+ pRow->iRail = findFreeRail(p, pRow->idxTop, pRow->idx, 0);
446444
 }else{
447445
 pRow->iRail = ++p->mxRail;
448446
 }
449447
 if( p->mxRail>=GR_MAX_RAIL ) return;
450448
 mask = BIT(pRow->iRail);
@@ -459,18 +457,17 @@
459457
 }
460458
 }
461459
462460
 /* Assign rails to all rows that are still unassigned.
463461
 */
464
- inUse = BIT(p->mxRail+1) - 1;
465462
 for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
466463
 int parentRid;
467464
468465
 if( pRow->iRail>=0 ){
469466
 if( pRow->pChild==0 && !pRow->timeWarp ){
470
- if( omitDescenders || count_nonbranch_children(pRow->rid)==0 ){
471
- inUse &= ~BIT(pRow->iRail);
467
+ if( omitDescenders || pRow->isLeaf ){
468
+ /* no-op */
472469
 }else{
473470
 pRow->aiRiser[pRow->iRail] = 0;
474471
 mask = BIT(pRow->iRail);
475472
 for(pLoop=pRow; pLoop; pLoop=pLoop->pPrev){
476473
 pLoop->railInUse |= mask;
@@ -492,11 +489,11 @@
492489
 continue;
493490
 }
494491
 if( pParent->idx>pRow->idx ){
495492
 /* Common case: Child occurs after parent and is above the
496493
 ** parent in the timeline */
497
- pRow->iRail = findFreeRail(p, 0, pParent->idx, inUse, pParent->iRail);
494
+ pRow->iRail = findFreeRail(p, 0, pParent->idx, pParent->iRail);
498495
 if( p->mxRail>=GR_MAX_RAIL ) return;
499496
 pParent->aiRiser[pRow->iRail] = pRow->idx;
500497
 }else{
501498
 /* Timewarp case: Child occurs earlier in time than parent and
502499
 ** appears below the parent in the timeline. */
@@ -505,22 +502,18 @@
505502
 pRow->iRail = ++p->mxRail;
506503
 if( p->mxRail>=GR_MAX_RAIL ) return;
507504
 pRow->railInUse = BIT(pRow->iRail);
508505
 pParent->aiRiser[iDownRail] = pRow->idx;
509506
 mask = BIT(iDownRail);
510
- inUse |= mask;
511507
 for(pLoop=p->pFirst; pLoop; pLoop=pLoop->pNext){
512508
 pLoop->railInUse |= mask;
513509
 }
514510
 }
515511
 }
516512
 mask = BIT(pRow->iRail);
517513
 pRow->railInUse |= mask;
518
- if( pRow->pChild==0 ){
519
- inUse &= ~mask;
520
- }else{
521
- inUse |= mask;
514
+ if( pRow->pChild ){
522515
 assignChildrenToRail(pRow);
523516
 }
524517
 if( pParent ){
525518
 for(pLoop=pParent->pPrev; pLoop && pLoop!=pRow; pLoop=pLoop->pPrev){
526519
 pLoop->railInUse |= mask;
@@ -535,11 +528,11 @@
535528
 for(i=1; i<pRow->nParent; i++){
536529
 int parentRid = pRow->aParent[i];
537530
 pDesc = hashFind(p, parentRid);
538531
 if( pDesc==0 ){
539532
 /* Merge from a node that is off-screen */
540
- int iMrail = findFreeRail(p, pRow->idx, p->nRow, 0, 0);
533
+ int iMrail = findFreeRail(p, pRow->idx, p->nRow, 0);
541534
 if( p->mxRail>=GR_MAX_RAIL ) return;
542535
 mask = BIT(iMrail);
543536
 pRow->mergeIn[iMrail] = 1;
544537
 pRow->mergeDown |= mask;
545538
 for(pLoop=pRow->pNext; pLoop; pLoop=pLoop->pNext){
546539
--- src/graph.c
+++ src/graph.c
@@ -218,17 +218,17 @@
218 ** top and bottom, inclusive.
219 */
220 static int findFreeRail(
221 GraphContext *p, /* The graph context */
222 int top, int btm, /* Span of rows for which the rail is needed */
223 u64 inUseMask, /* Mask or rails already in use */
224 int iNearto /* Find rail nearest to this rail */
225 ){
226 GraphRow *pRow;
227 int i;
228 int iBest = 0;
229 int iBestDist = 9999;
 
230 for(pRow=p->pFirst; pRow && pRow->idx<top; pRow=pRow->pNext){}
231 while( pRow && pRow->idx<=btm ){
232 inUseMask |= pRow->railInUse;
233 pRow = pRow->pNext;
234 }
@@ -299,12 +299,11 @@
299 pParent->mergeUpto = pChild->idx;
300 }else{
301 /* The thin merge arrow riser is taller than the thick primary
302 ** child riser, so use separate rails. */
303 int iTarget = pParent->iRail;
304 pParent->mergeOut = findFreeRail(p, pChild->idx, pParent->idx-1,
305 0, iTarget);
306 pParent->mergeUpto = pChild->idx;
307 mask = BIT(pParent->mergeOut);
308 for(pLoop=pChild->pNext; pLoop && pLoop->rid!=pParent->rid;
309 pLoop=pLoop->pNext){
310 pLoop->railInUse |= mask;
@@ -335,11 +334,10 @@
335 */
336 void graph_finish(GraphContext *p, int omitDescenders){
337 GraphRow *pRow, *pDesc, *pDup, *pLoop, *pParent;
338 int i;
339 u64 mask;
340 u64 inUse;
341 int hasDup = 0; /* True if one or more isDup entries */
342 const char *zTrunk;
343
344 if( p==0 || p->pFirst==0 || p->nErr ) return;
345 p->nErr = 1; /* Assume an error until proven otherwise */
@@ -440,11 +438,11 @@
440 }else {
441 if( pRow->iRail>=0 ) continue;
442 }
443 if( pRow->nParent==0 || hashFind(p,pRow->aParent[0])==0 ){
444 if( omitDescenders ){
445 pRow->iRail = findFreeRail(p, pRow->idxTop, pRow->idx, 0, 0);
446 }else{
447 pRow->iRail = ++p->mxRail;
448 }
449 if( p->mxRail>=GR_MAX_RAIL ) return;
450 mask = BIT(pRow->iRail);
@@ -459,18 +457,17 @@
459 }
460 }
461
462 /* Assign rails to all rows that are still unassigned.
463 */
464 inUse = BIT(p->mxRail+1) - 1;
465 for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
466 int parentRid;
467
468 if( pRow->iRail>=0 ){
469 if( pRow->pChild==0 && !pRow->timeWarp ){
470 if( omitDescenders || count_nonbranch_children(pRow->rid)==0 ){
471 inUse &= ~BIT(pRow->iRail);
472 }else{
473 pRow->aiRiser[pRow->iRail] = 0;
474 mask = BIT(pRow->iRail);
475 for(pLoop=pRow; pLoop; pLoop=pLoop->pPrev){
476 pLoop->railInUse |= mask;
@@ -492,11 +489,11 @@
492 continue;
493 }
494 if( pParent->idx>pRow->idx ){
495 /* Common case: Child occurs after parent and is above the
496 ** parent in the timeline */
497 pRow->iRail = findFreeRail(p, 0, pParent->idx, inUse, pParent->iRail);
498 if( p->mxRail>=GR_MAX_RAIL ) return;
499 pParent->aiRiser[pRow->iRail] = pRow->idx;
500 }else{
501 /* Timewarp case: Child occurs earlier in time than parent and
502 ** appears below the parent in the timeline. */
@@ -505,22 +502,18 @@
505 pRow->iRail = ++p->mxRail;
506 if( p->mxRail>=GR_MAX_RAIL ) return;
507 pRow->railInUse = BIT(pRow->iRail);
508 pParent->aiRiser[iDownRail] = pRow->idx;
509 mask = BIT(iDownRail);
510 inUse |= mask;
511 for(pLoop=p->pFirst; pLoop; pLoop=pLoop->pNext){
512 pLoop->railInUse |= mask;
513 }
514 }
515 }
516 mask = BIT(pRow->iRail);
517 pRow->railInUse |= mask;
518 if( pRow->pChild==0 ){
519 inUse &= ~mask;
520 }else{
521 inUse |= mask;
522 assignChildrenToRail(pRow);
523 }
524 if( pParent ){
525 for(pLoop=pParent->pPrev; pLoop && pLoop!=pRow; pLoop=pLoop->pPrev){
526 pLoop->railInUse |= mask;
@@ -535,11 +528,11 @@
535 for(i=1; i<pRow->nParent; i++){
536 int parentRid = pRow->aParent[i];
537 pDesc = hashFind(p, parentRid);
538 if( pDesc==0 ){
539 /* Merge from a node that is off-screen */
540 int iMrail = findFreeRail(p, pRow->idx, p->nRow, 0, 0);
541 if( p->mxRail>=GR_MAX_RAIL ) return;
542 mask = BIT(iMrail);
543 pRow->mergeIn[iMrail] = 1;
544 pRow->mergeDown |= mask;
545 for(pLoop=pRow->pNext; pLoop; pLoop=pLoop->pNext){
546
--- src/graph.c
+++ src/graph.c
@@ -218,17 +218,17 @@
218 ** top and bottom, inclusive.
219 */
220 static int findFreeRail(
221 GraphContext *p, /* The graph context */
222 int top, int btm, /* Span of rows for which the rail is needed */
 
223 int iNearto /* Find rail nearest to this rail */
224 ){
225 GraphRow *pRow;
226 int i;
227 int iBest = 0;
228 int iBestDist = 9999;
229 u64 inUseMask = 0;
230 for(pRow=p->pFirst; pRow && pRow->idx<top; pRow=pRow->pNext){}
231 while( pRow && pRow->idx<=btm ){
232 inUseMask |= pRow->railInUse;
233 pRow = pRow->pNext;
234 }
@@ -299,12 +299,11 @@
299 pParent->mergeUpto = pChild->idx;
300 }else{
301 /* The thin merge arrow riser is taller than the thick primary
302 ** child riser, so use separate rails. */
303 int iTarget = pParent->iRail;
304 pParent->mergeOut = findFreeRail(p, pChild->idx, pParent->idx-1, iTarget);
 
305 pParent->mergeUpto = pChild->idx;
306 mask = BIT(pParent->mergeOut);
307 for(pLoop=pChild->pNext; pLoop && pLoop->rid!=pParent->rid;
308 pLoop=pLoop->pNext){
309 pLoop->railInUse |= mask;
@@ -335,11 +334,10 @@
334 */
335 void graph_finish(GraphContext *p, int omitDescenders){
336 GraphRow *pRow, *pDesc, *pDup, *pLoop, *pParent;
337 int i;
338 u64 mask;
 
339 int hasDup = 0; /* True if one or more isDup entries */
340 const char *zTrunk;
341
342 if( p==0 || p->pFirst==0 || p->nErr ) return;
343 p->nErr = 1; /* Assume an error until proven otherwise */
@@ -440,11 +438,11 @@
438 }else {
439 if( pRow->iRail>=0 ) continue;
440 }
441 if( pRow->nParent==0 || hashFind(p,pRow->aParent[0])==0 ){
442 if( omitDescenders ){
443 pRow->iRail = findFreeRail(p, pRow->idxTop, pRow->idx, 0);
444 }else{
445 pRow->iRail = ++p->mxRail;
446 }
447 if( p->mxRail>=GR_MAX_RAIL ) return;
448 mask = BIT(pRow->iRail);
@@ -459,18 +457,17 @@
457 }
458 }
459
460 /* Assign rails to all rows that are still unassigned.
461 */
 
462 for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
463 int parentRid;
464
465 if( pRow->iRail>=0 ){
466 if( pRow->pChild==0 && !pRow->timeWarp ){
467 if( omitDescenders || pRow->isLeaf ){
468 /* no-op */
469 }else{
470 pRow->aiRiser[pRow->iRail] = 0;
471 mask = BIT(pRow->iRail);
472 for(pLoop=pRow; pLoop; pLoop=pLoop->pPrev){
473 pLoop->railInUse |= mask;
@@ -492,11 +489,11 @@
489 continue;
490 }
491 if( pParent->idx>pRow->idx ){
492 /* Common case: Child occurs after parent and is above the
493 ** parent in the timeline */
494 pRow->iRail = findFreeRail(p, 0, pParent->idx, pParent->iRail);
495 if( p->mxRail>=GR_MAX_RAIL ) return;
496 pParent->aiRiser[pRow->iRail] = pRow->idx;
497 }else{
498 /* Timewarp case: Child occurs earlier in time than parent and
499 ** appears below the parent in the timeline. */
@@ -505,22 +502,18 @@
502 pRow->iRail = ++p->mxRail;
503 if( p->mxRail>=GR_MAX_RAIL ) return;
504 pRow->railInUse = BIT(pRow->iRail);
505 pParent->aiRiser[iDownRail] = pRow->idx;
506 mask = BIT(iDownRail);
 
507 for(pLoop=p->pFirst; pLoop; pLoop=pLoop->pNext){
508 pLoop->railInUse |= mask;
509 }
510 }
511 }
512 mask = BIT(pRow->iRail);
513 pRow->railInUse |= mask;
514 if( pRow->pChild ){
 
 
 
515 assignChildrenToRail(pRow);
516 }
517 if( pParent ){
518 for(pLoop=pParent->pPrev; pLoop && pLoop!=pRow; pLoop=pLoop->pPrev){
519 pLoop->railInUse |= mask;
@@ -535,11 +528,11 @@
528 for(i=1; i<pRow->nParent; i++){
529 int parentRid = pRow->aParent[i];
530 pDesc = hashFind(p, parentRid);
531 if( pDesc==0 ){
532 /* Merge from a node that is off-screen */
533 int iMrail = findFreeRail(p, pRow->idx, p->nRow, 0);
534 if( p->mxRail>=GR_MAX_RAIL ) return;
535 mask = BIT(iMrail);
536 pRow->mergeIn[iMrail] = 1;
537 pRow->mergeDown |= mask;
538 for(pLoop=pRow->pNext; pLoop; pLoop=pLoop->pNext){
539

Keyboard Shortcuts

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