Fossil SCM

Improvements to the graph layout algorithm.

drh 2010-08-20 19:42 trunk
Commit 98870a8510dc9a924330a41344b75c764848803e
Parent e0248776d31daa4…
2 files changed +100 -55 +2 -2
~ src/graph.c ~ src/timeline.c
M src/graph.c
+100 -55
--- src/graph.c
+++ src/graph.c
@@ -21,12 +21,12 @@
2121
 #include "graph.h"
2222
 #include <assert.h>
2323
2424
 #if INTERFACE
2525
26
-#define GR_MAX_PARENT 10
27
-#define GR_MAX_RAIL 32
26
+#define GR_MAX_PARENT 10 /* Most parents for any one node */
27
+#define GR_MAX_RAIL 32 /* Max number of "rails" to display */
2828
2929
 /* The graph appears vertically beside a timeline. Each row in the
3030
 ** timeline corresponds to a row in the graph.
3131
 */
3232
 struct GraphRow {
@@ -38,11 +38,12 @@
3838
3939
 GraphRow *pNext; /* Next row down in the list of all rows */
4040
 GraphRow *pPrev; /* Previous row */
4141
4242
 int idx; /* Row index. First is 1. 0 used for "none" */
43
- u8 isLeaf; /* True if no direct child nodes */
43
+ int idxTop; /* Direct descendent highest up on the graph */
44
+ GraphRow *pChild; /* Child immediately above this node */
4445
 u8 isDup; /* True if this is duplicate of a prior entry */
4546
 int iRail; /* Which rail this check-in appears on. 0-based.*/
4647
 int aiRaiser[GR_MAX_RAIL]; /* Raisers from this node to a higher row. */
4748
 int bDescender; /* Raiser from bottom of graph to here. */
4849
 u32 mergeIn; /* Merge in from other rails */
@@ -53,20 +54,19 @@
5354
 };
5455
5556
 /* Context while building a graph
5657
 */
5758
 struct GraphContext {
58
- int nErr; /* Number of errors encountered */
59
- int mxRail; /* Number of rails required to render the graph */
60
- GraphRow *pFirst; /* First row in the list */
61
- GraphRow *pLast; /* Last row in the list */
62
- int nBranch; /* Number of distinct branches */
63
- char **azBranch; /* Names of the branches */
59
+ int nErr; /* Number of errors encountered */
60
+ int mxRail; /* Number of rails required to render the graph */
61
+ GraphRow *pFirst; /* First row in the list */
62
+ GraphRow *pLast; /* Last row in the list */
63
+ int nBranch; /* Number of distinct branches */
64
+ char **azBranch; /* Names of the branches */
6465
 int nRow; /* Number of rows */
65
- int railMap[GR_MAX_RAIL]; /* Rail order mapping */
6666
 int nHash; /* Number of slots in apHash[] */
67
- GraphRow **apHash; /* Hash table of rows */
67
+ GraphRow **apHash; /* Hash table of GraphRow objects. Key: rid */
6868
 };
6969
7070
 #endif
7171
7272
 /*
@@ -103,13 +103,13 @@
103103
 free(p->apHash);
104104
 free(p);
105105
 }
106106
107107
 /*
108
-** Insert a row into the hash table. If there is already another
109
-** row with the same rid, overwrite the prior entry if the overwrite
110
-** flag is set.
108
+** Insert a row into the hash table. pRow->rid is the key. Keys must
109
+** be unique. If there is already another row with the same rid,
110
+** overwrite the prior entry if and only if the overwrite flag is set.
111111
 */
112112
 static void hashInsert(GraphContext *p, GraphRow *pRow, int overwrite){
113113
 int h;
114114
 h = pRow->rid % p->nHash;
115115
 while( p->apHash[h] && p->apHash[h]->rid!=pRow->rid ){
@@ -135,10 +135,14 @@
135135
136136
 /*
137137
 ** Return the canonical pointer for a given branch name.
138138
 ** Multiple calls to this routine with equivalent strings
139139
 ** will return the same pointer.
140
+**
141
+** The returned value is a pointer to a (readonly) string that
142
+** has the useful property that strings can be checked for
143
+** equality by comparing pointers.
140144
 **
141145
 ** Note: also used for background color names.
142146
 */
143147
 static char *persistBranchName(GraphContext *p, const char *zBranch){
144148
 int i;
@@ -151,11 +155,11 @@
151155
 p->azBranch[p->nBranch-1] = mprintf("%s", zBranch);
152156
 return p->azBranch[p->nBranch-1];
153157
 }
154158
155159
 /*
156
-** Add a new row t the graph context. Rows are added from top to bottom.
160
+** Add a new row to the graph context. Rows are added from top to bottom.
157161
 */
158162
 int graph_add_row(
159163
 GraphContext *p, /* The context to which the row is added */
160164
 int rid, /* RID for the check-in */
161165
 int nParent, /* Number of parents */
@@ -179,11 +183,11 @@
179183
 }else{
180184
 p->pLast->pNext = pRow;
181185
 }
182186
 p->pLast = pRow;
183187
 p->nRow++;
184
- pRow->idx = p->nRow;
188
+ pRow->idx = pRow->idxTop = p->nRow;
185189
 return pRow->idx;
186190
 }
187191
188192
 /*
189193
 ** Return the index of a rail currently not in use for any row between
@@ -219,16 +223,46 @@
219223
 }
220224
 }
221225
 if( iBestDist>1000 ) p->nErr++;
222226
 return iBest;
223227
 }
228
+
229
+/*
230
+** Assign all children of node pBottom to the same rail as pBottom.
231
+*/
232
+static void assignChildrenToRail(GraphRow *pBottom){
233
+ int iRail = pBottom->iRail;
234
+ GraphRow *pCurrent;
235
+ GraphRow *pPrior;
236
+ u32 mask = 1<<iRail;
237
+
238
+ pBottom->iRail = iRail;
239
+ pBottom->railInUse |= mask;
240
+ pPrior = pBottom;
241
+ for(pCurrent=pBottom->pChild; pCurrent; pCurrent=pCurrent->pChild){
242
+ assert( pPrior->idx > pCurrent->idx );
243
+ assert( pCurrent->iRail<0 );
244
+ pCurrent->iRail = iRail;
245
+ pCurrent->railInUse |= mask;
246
+ pPrior->aiRaiser[iRail] = pCurrent->idx;
247
+ while( pPrior!=pCurrent ){
248
+ pPrior->railInUse |= mask;
249
+ pPrior = pPrior->pPrev;
250
+ assert( pPrior!=0 );
251
+ }
252
+ if( pCurrent->pPrev ){
253
+ pCurrent->pPrev->railInUse |= mask;
254
+ }
255
+ }
256
+}
257
+
224258
225259
 /*
226260
 ** Compute the complete graph
227261
 */
228262
 void graph_finish(GraphContext *p, int omitDescenders){
229
- GraphRow *pRow, *pDesc, *pDup, *pLoop;
263
+ GraphRow *pRow, *pDesc, *pDup, *pLoop, *pParent;
230264
 int i;
231265
 u32 mask;
232266
 u32 inUse;
233267
 int hasDup = 0; /* True if one or more isDup entries */
234268
 const char *zTrunk;
@@ -248,11 +282,17 @@
248282
 }
249283
 hashInsert(p, pRow, 1);
250284
 }
251285
 p->mxRail = -1;
252286
253
- /* Purge merge-parents that are out-of-graph
287
+ /* Purge merge-parents that are out-of-graph.
288
+ **
289
+ ** Each node has one primary parent and zero or more "merge" parents.
290
+ ** A merge parent is a prior checkin from which changes were merged into
291
+ ** the current check-in. If a merge parent is not in the visible section
292
+ ** of this graph, then no arrows will be drawn for it, so remove it from
293
+ ** the aParent[] array.
254294
 */
255295
 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
256296
 for(i=1; i<pRow->nParent; i++){
257297
 if( hashFind(p, pRow->aParent[i])==0 ){
258298
 pRow->aParent[i] = pRow->aParent[--pRow->nParent];
@@ -259,99 +299,105 @@
259299
 i--;
260300
 }
261301
 }
262302
 }
263303
264
- /* Figure out which nodes have no direct children (children on
265
- ** the same rail). Mark such nodes as isLeaf.
304
+ /* Find the pChild pointer for each node.
305
+ **
306
+ ** The pChild points to node directly above on the same rail.
307
+ ** The pChild must be in the same branch. Leaf nodes have a NULL
308
+ ** pChild.
309
+ **
310
+ ** In the case of a fork, choose the pChild that results in the
311
+ ** longest rail.
266312
 */
267
- memset(p->apHash, 0, sizeof(p->apHash[0])*p->nHash);
268
- for(pRow=p->pLast; pRow; pRow=pRow->pPrev) pRow->isLeaf = 1;
269
- for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
270
- GraphRow *pParent;
271
- hashInsert(p, pRow, 0);
272
- if( !pRow->isDup
273
- && pRow->nParent>0
274
- && (pParent = hashFind(p, pRow->aParent[0]))!=0
275
- && pRow->zBranch==pParent->zBranch
276
- ){
277
- pParent->isLeaf = 0;
313
+ for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
314
+ if( pRow->isDup ) continue;
315
+ if( pRow->nParent==0 ) continue;
316
+ pParent = hashFind(p, pRow->aParent[0]);
317
+ if( pParent==0 ) continue;
318
+ if( pParent->zBranch!=pRow->zBranch ) continue;
319
+ if( pRow->idxTop < pParent->idxTop ){
320
+ pParent->pChild = pRow;
321
+ pParent->idxTop = pRow->idxTop;
278322
 }
279323
 }
280324
281325
 /* Identify rows where the primary parent is off screen. Assign
282326
 ** each to a rail and draw descenders to the bottom of the screen.
327
+ **
328
+ ** Strive to put the "trunk" branch on far left.
283329
 */
284330
 zTrunk = persistBranchName(p, "trunk");
285331
 for(i=0; i<2; i++){
286
- for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
332
+ for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
287333
 if( i==0 ){
288334
 if( pRow->zBranch!=zTrunk ) continue;
289335
 }else {
290336
 if( pRow->iRail>=0 ) continue;
291337
 }
292338
 if( pRow->nParent==0 || hashFind(p,pRow->aParent[0])==0 ){
293339
 if( omitDescenders ){
294
- pRow->iRail = findFreeRail(p, pRow->idx, pRow->idx, 0, 0);
340
+ pRow->iRail = findFreeRail(p, pRow->idxTop, pRow->idx, 0, 0);
295341
 }else{
296342
 pRow->iRail = ++p->mxRail;
297343
 }
298344
 mask = 1<<(pRow->iRail);
299345
 if( omitDescenders ){
300346
 if( pRow->pNext ) pRow->pNext->railInUse |= mask;
301
- for(pDesc=pRow; pDesc; pDesc=pDesc->pPrev){
302
- pDesc->railInUse |= mask;
303
- if( pDesc->zBranch==pRow->zBranch && pDesc->isLeaf ) break;
304
- }
305347
 }else{
306348
 pRow->bDescender = pRow->nParent>0;
307
- for(pDesc=pRow; pDesc; pDesc=pDesc->pNext){
308
- pDesc->railInUse |= mask;
349
+ for(pLoop=pRow; pLoop; pLoop=pLoop->pNext){
350
+ pLoop->railInUse |= mask;
309351
 }
310352
 }
353
+ assignChildrenToRail(pRow);
311354
 }
312355
 }
313356
 }
314357
315358
 /* Assign rails to all rows that are still unassigned.
316
- ** The first primary child of a row goes on the same rail as
317
- ** that row.
318359
 */
319360
 inUse = (1<<(p->mxRail+1))-1;
320361
 for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
321362
 int parentRid;
322
- if( pRow->iRail>=0 ) continue;
363
+
364
+ if( pRow->iRail>=0 ){
365
+ if( pRow->pChild==0 ) inUse &= ~(1<<pRow->iRail);
366
+ continue;
367
+ }
323368
 if( pRow->isDup ){
324369
 pRow->iRail = findFreeRail(p, pRow->idx, pRow->idx, inUse, 0);
325370
 pDesc = pRow;
371
+ pParent = 0;
326372
 }else{
327373
 assert( pRow->nParent>0 );
328374
 parentRid = pRow->aParent[0];
329
- pDesc = hashFind(p, parentRid);
330
- if( pDesc==0 ){
375
+ pParent = hashFind(p, parentRid);
376
+ if( pParent==0 ){
331377
 /* Time skew */
332378
 pRow->iRail = ++p->mxRail;
333379
 pRow->railInUse = 1<<pRow->iRail;
334380
 continue;
335381
 }
336
- if( pDesc->aiRaiser[pDesc->iRail]==0 && pDesc->zBranch==pRow->zBranch ){
337
- pRow->iRail = pDesc->iRail;
338
- }else{
339
- pRow->iRail = findFreeRail(p, 0, pDesc->idx, inUse, pDesc->iRail);
340
- }
341
- pDesc->aiRaiser[pRow->iRail] = pRow->idx;
382
+ pRow->iRail = findFreeRail(p, 0, pParent->idx, inUse, pParent->iRail);
383
+ pParent->aiRaiser[pRow->iRail] = pRow->idx;
342384
 }
343385
 mask = 1<<pRow->iRail;
344
- if( pRow->isLeaf ){
386
+ if( pRow->pPrev ) pRow->pPrev->railInUse |= mask;
387
+ if( pRow->pNext ) pRow->pNext->railInUse |= mask;
388
+ if( pRow->pChild==0 ){
345389
 inUse &= ~mask;
346390
 }else{
347391
 inUse |= mask;
392
+ assignChildrenToRail(pRow);
348393
 }
349
- for(pLoop=pRow; pLoop && pLoop!=pDesc; pLoop=pLoop->pNext){
350
- pLoop->railInUse |= mask;
394
+ if( pParent ){
395
+ for(pLoop=pParent; pLoop!=pRow; pLoop=pLoop->pPrev){
396
+ pLoop->railInUse |= mask;
397
+ }
351398
 }
352
- pDesc->railInUse |= mask;
353399
 }
354400
355401
 /*
356402
 ** Insert merge rails and merge arrows
357403
 */
@@ -398,12 +444,11 @@
398444
 }
399445
400446
 /*
401447
 ** Find the maximum rail number.
402448
 */
403
- for(i=0; i<GR_MAX_RAIL; i++) p->railMap[i] = i;
404449
 p->mxRail = 0;
405450
 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
406451
 if( pRow->iRail>p->mxRail ) p->mxRail = pRow->iRail;
407452
 if( pRow->mergeOut>p->mxRail ) p->mxRail = pRow->mergeOut;
408453
 }
409454
 }
410455
--- src/graph.c
+++ src/graph.c
@@ -21,12 +21,12 @@
21 #include "graph.h"
22 #include <assert.h>
23
24 #if INTERFACE
25
26 #define GR_MAX_PARENT 10
27 #define GR_MAX_RAIL 32
28
29 /* The graph appears vertically beside a timeline. Each row in the
30 ** timeline corresponds to a row in the graph.
31 */
32 struct GraphRow {
@@ -38,11 +38,12 @@
38
39 GraphRow *pNext; /* Next row down in the list of all rows */
40 GraphRow *pPrev; /* Previous row */
41
42 int idx; /* Row index. First is 1. 0 used for "none" */
43 u8 isLeaf; /* True if no direct child nodes */
 
44 u8 isDup; /* True if this is duplicate of a prior entry */
45 int iRail; /* Which rail this check-in appears on. 0-based.*/
46 int aiRaiser[GR_MAX_RAIL]; /* Raisers from this node to a higher row. */
47 int bDescender; /* Raiser from bottom of graph to here. */
48 u32 mergeIn; /* Merge in from other rails */
@@ -53,20 +54,19 @@
53 };
54
55 /* Context while building a graph
56 */
57 struct GraphContext {
58 int nErr; /* Number of errors encountered */
59 int mxRail; /* Number of rails required to render the graph */
60 GraphRow *pFirst; /* First row in the list */
61 GraphRow *pLast; /* Last row in the list */
62 int nBranch; /* Number of distinct branches */
63 char **azBranch; /* Names of the branches */
64 int nRow; /* Number of rows */
65 int railMap[GR_MAX_RAIL]; /* Rail order mapping */
66 int nHash; /* Number of slots in apHash[] */
67 GraphRow **apHash; /* Hash table of rows */
68 };
69
70 #endif
71
72 /*
@@ -103,13 +103,13 @@
103 free(p->apHash);
104 free(p);
105 }
106
107 /*
108 ** Insert a row into the hash table. If there is already another
109 ** row with the same rid, overwrite the prior entry if the overwrite
110 ** flag is set.
111 */
112 static void hashInsert(GraphContext *p, GraphRow *pRow, int overwrite){
113 int h;
114 h = pRow->rid % p->nHash;
115 while( p->apHash[h] && p->apHash[h]->rid!=pRow->rid ){
@@ -135,10 +135,14 @@
135
136 /*
137 ** Return the canonical pointer for a given branch name.
138 ** Multiple calls to this routine with equivalent strings
139 ** will return the same pointer.
 
 
 
 
140 **
141 ** Note: also used for background color names.
142 */
143 static char *persistBranchName(GraphContext *p, const char *zBranch){
144 int i;
@@ -151,11 +155,11 @@
151 p->azBranch[p->nBranch-1] = mprintf("%s", zBranch);
152 return p->azBranch[p->nBranch-1];
153 }
154
155 /*
156 ** Add a new row t the graph context. Rows are added from top to bottom.
157 */
158 int graph_add_row(
159 GraphContext *p, /* The context to which the row is added */
160 int rid, /* RID for the check-in */
161 int nParent, /* Number of parents */
@@ -179,11 +183,11 @@
179 }else{
180 p->pLast->pNext = pRow;
181 }
182 p->pLast = pRow;
183 p->nRow++;
184 pRow->idx = p->nRow;
185 return pRow->idx;
186 }
187
188 /*
189 ** Return the index of a rail currently not in use for any row between
@@ -219,16 +223,46 @@
219 }
220 }
221 if( iBestDist>1000 ) p->nErr++;
222 return iBest;
223 }
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
224
225 /*
226 ** Compute the complete graph
227 */
228 void graph_finish(GraphContext *p, int omitDescenders){
229 GraphRow *pRow, *pDesc, *pDup, *pLoop;
230 int i;
231 u32 mask;
232 u32 inUse;
233 int hasDup = 0; /* True if one or more isDup entries */
234 const char *zTrunk;
@@ -248,11 +282,17 @@
248 }
249 hashInsert(p, pRow, 1);
250 }
251 p->mxRail = -1;
252
253 /* Purge merge-parents that are out-of-graph
 
 
 
 
 
 
254 */
255 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
256 for(i=1; i<pRow->nParent; i++){
257 if( hashFind(p, pRow->aParent[i])==0 ){
258 pRow->aParent[i] = pRow->aParent[--pRow->nParent];
@@ -259,99 +299,105 @@
259 i--;
260 }
261 }
262 }
263
264 /* Figure out which nodes have no direct children (children on
265 ** the same rail). Mark such nodes as isLeaf.
 
 
 
 
 
 
266 */
267 memset(p->apHash, 0, sizeof(p->apHash[0])*p->nHash);
268 for(pRow=p->pLast; pRow; pRow=pRow->pPrev) pRow->isLeaf = 1;
269 for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
270 GraphRow *pParent;
271 hashInsert(p, pRow, 0);
272 if( !pRow->isDup
273 && pRow->nParent>0
274 && (pParent = hashFind(p, pRow->aParent[0]))!=0
275 && pRow->zBranch==pParent->zBranch
276 ){
277 pParent->isLeaf = 0;
278 }
279 }
280
281 /* Identify rows where the primary parent is off screen. Assign
282 ** each to a rail and draw descenders to the bottom of the screen.
 
 
283 */
284 zTrunk = persistBranchName(p, "trunk");
285 for(i=0; i<2; i++){
286 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
287 if( i==0 ){
288 if( pRow->zBranch!=zTrunk ) continue;
289 }else {
290 if( pRow->iRail>=0 ) continue;
291 }
292 if( pRow->nParent==0 || hashFind(p,pRow->aParent[0])==0 ){
293 if( omitDescenders ){
294 pRow->iRail = findFreeRail(p, pRow->idx, pRow->idx, 0, 0);
295 }else{
296 pRow->iRail = ++p->mxRail;
297 }
298 mask = 1<<(pRow->iRail);
299 if( omitDescenders ){
300 if( pRow->pNext ) pRow->pNext->railInUse |= mask;
301 for(pDesc=pRow; pDesc; pDesc=pDesc->pPrev){
302 pDesc->railInUse |= mask;
303 if( pDesc->zBranch==pRow->zBranch && pDesc->isLeaf ) break;
304 }
305 }else{
306 pRow->bDescender = pRow->nParent>0;
307 for(pDesc=pRow; pDesc; pDesc=pDesc->pNext){
308 pDesc->railInUse |= mask;
309 }
310 }
 
311 }
312 }
313 }
314
315 /* Assign rails to all rows that are still unassigned.
316 ** The first primary child of a row goes on the same rail as
317 ** that row.
318 */
319 inUse = (1<<(p->mxRail+1))-1;
320 for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
321 int parentRid;
322 if( pRow->iRail>=0 ) continue;
 
 
 
 
323 if( pRow->isDup ){
324 pRow->iRail = findFreeRail(p, pRow->idx, pRow->idx, inUse, 0);
325 pDesc = pRow;
 
326 }else{
327 assert( pRow->nParent>0 );
328 parentRid = pRow->aParent[0];
329 pDesc = hashFind(p, parentRid);
330 if( pDesc==0 ){
331 /* Time skew */
332 pRow->iRail = ++p->mxRail;
333 pRow->railInUse = 1<<pRow->iRail;
334 continue;
335 }
336 if( pDesc->aiRaiser[pDesc->iRail]==0 && pDesc->zBranch==pRow->zBranch ){
337 pRow->iRail = pDesc->iRail;
338 }else{
339 pRow->iRail = findFreeRail(p, 0, pDesc->idx, inUse, pDesc->iRail);
340 }
341 pDesc->aiRaiser[pRow->iRail] = pRow->idx;
342 }
343 mask = 1<<pRow->iRail;
344 if( pRow->isLeaf ){
 
 
345 inUse &= ~mask;
346 }else{
347 inUse |= mask;
 
348 }
349 for(pLoop=pRow; pLoop && pLoop!=pDesc; pLoop=pLoop->pNext){
350 pLoop->railInUse |= mask;
 
 
351 }
352 pDesc->railInUse |= mask;
353 }
354
355 /*
356 ** Insert merge rails and merge arrows
357 */
@@ -398,12 +444,11 @@
398 }
399
400 /*
401 ** Find the maximum rail number.
402 */
403 for(i=0; i<GR_MAX_RAIL; i++) p->railMap[i] = i;
404 p->mxRail = 0;
405 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
406 if( pRow->iRail>p->mxRail ) p->mxRail = pRow->iRail;
407 if( pRow->mergeOut>p->mxRail ) p->mxRail = pRow->mergeOut;
408 }
409 }
410
--- src/graph.c
+++ src/graph.c
@@ -21,12 +21,12 @@
21 #include "graph.h"
22 #include <assert.h>
23
24 #if INTERFACE
25
26 #define GR_MAX_PARENT 10 /* Most parents for any one node */
27 #define GR_MAX_RAIL 32 /* Max number of "rails" to display */
28
29 /* The graph appears vertically beside a timeline. Each row in the
30 ** timeline corresponds to a row in the graph.
31 */
32 struct GraphRow {
@@ -38,11 +38,12 @@
38
39 GraphRow *pNext; /* Next row down in the list of all rows */
40 GraphRow *pPrev; /* Previous row */
41
42 int idx; /* Row index. First is 1. 0 used for "none" */
43 int idxTop; /* Direct descendent highest up on the graph */
44 GraphRow *pChild; /* Child immediately above this node */
45 u8 isDup; /* True if this is duplicate of a prior entry */
46 int iRail; /* Which rail this check-in appears on. 0-based.*/
47 int aiRaiser[GR_MAX_RAIL]; /* Raisers from this node to a higher row. */
48 int bDescender; /* Raiser from bottom of graph to here. */
49 u32 mergeIn; /* Merge in from other rails */
@@ -53,20 +54,19 @@
54 };
55
56 /* Context while building a graph
57 */
58 struct GraphContext {
59 int nErr; /* Number of errors encountered */
60 int mxRail; /* Number of rails required to render the graph */
61 GraphRow *pFirst; /* First row in the list */
62 GraphRow *pLast; /* Last row in the list */
63 int nBranch; /* Number of distinct branches */
64 char **azBranch; /* Names of the branches */
65 int nRow; /* Number of rows */
 
66 int nHash; /* Number of slots in apHash[] */
67 GraphRow **apHash; /* Hash table of GraphRow objects. Key: rid */
68 };
69
70 #endif
71
72 /*
@@ -103,13 +103,13 @@
103 free(p->apHash);
104 free(p);
105 }
106
107 /*
108 ** Insert a row into the hash table. pRow->rid is the key. Keys must
109 ** be unique. If there is already another row with the same rid,
110 ** overwrite the prior entry if and only if the overwrite flag is set.
111 */
112 static void hashInsert(GraphContext *p, GraphRow *pRow, int overwrite){
113 int h;
114 h = pRow->rid % p->nHash;
115 while( p->apHash[h] && p->apHash[h]->rid!=pRow->rid ){
@@ -135,10 +135,14 @@
135
136 /*
137 ** Return the canonical pointer for a given branch name.
138 ** Multiple calls to this routine with equivalent strings
139 ** will return the same pointer.
140 **
141 ** The returned value is a pointer to a (readonly) string that
142 ** has the useful property that strings can be checked for
143 ** equality by comparing pointers.
144 **
145 ** Note: also used for background color names.
146 */
147 static char *persistBranchName(GraphContext *p, const char *zBranch){
148 int i;
@@ -151,11 +155,11 @@
155 p->azBranch[p->nBranch-1] = mprintf("%s", zBranch);
156 return p->azBranch[p->nBranch-1];
157 }
158
159 /*
160 ** Add a new row to the graph context. Rows are added from top to bottom.
161 */
162 int graph_add_row(
163 GraphContext *p, /* The context to which the row is added */
164 int rid, /* RID for the check-in */
165 int nParent, /* Number of parents */
@@ -179,11 +183,11 @@
183 }else{
184 p->pLast->pNext = pRow;
185 }
186 p->pLast = pRow;
187 p->nRow++;
188 pRow->idx = pRow->idxTop = p->nRow;
189 return pRow->idx;
190 }
191
192 /*
193 ** Return the index of a rail currently not in use for any row between
@@ -219,16 +223,46 @@
223 }
224 }
225 if( iBestDist>1000 ) p->nErr++;
226 return iBest;
227 }
228
229 /*
230 ** Assign all children of node pBottom to the same rail as pBottom.
231 */
232 static void assignChildrenToRail(GraphRow *pBottom){
233 int iRail = pBottom->iRail;
234 GraphRow *pCurrent;
235 GraphRow *pPrior;
236 u32 mask = 1<<iRail;
237
238 pBottom->iRail = iRail;
239 pBottom->railInUse |= mask;
240 pPrior = pBottom;
241 for(pCurrent=pBottom->pChild; pCurrent; pCurrent=pCurrent->pChild){
242 assert( pPrior->idx > pCurrent->idx );
243 assert( pCurrent->iRail<0 );
244 pCurrent->iRail = iRail;
245 pCurrent->railInUse |= mask;
246 pPrior->aiRaiser[iRail] = pCurrent->idx;
247 while( pPrior!=pCurrent ){
248 pPrior->railInUse |= mask;
249 pPrior = pPrior->pPrev;
250 assert( pPrior!=0 );
251 }
252 if( pCurrent->pPrev ){
253 pCurrent->pPrev->railInUse |= mask;
254 }
255 }
256 }
257
258
259 /*
260 ** Compute the complete graph
261 */
262 void graph_finish(GraphContext *p, int omitDescenders){
263 GraphRow *pRow, *pDesc, *pDup, *pLoop, *pParent;
264 int i;
265 u32 mask;
266 u32 inUse;
267 int hasDup = 0; /* True if one or more isDup entries */
268 const char *zTrunk;
@@ -248,11 +282,17 @@
282 }
283 hashInsert(p, pRow, 1);
284 }
285 p->mxRail = -1;
286
287 /* Purge merge-parents that are out-of-graph.
288 **
289 ** Each node has one primary parent and zero or more "merge" parents.
290 ** A merge parent is a prior checkin from which changes were merged into
291 ** the current check-in. If a merge parent is not in the visible section
292 ** of this graph, then no arrows will be drawn for it, so remove it from
293 ** the aParent[] array.
294 */
295 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
296 for(i=1; i<pRow->nParent; i++){
297 if( hashFind(p, pRow->aParent[i])==0 ){
298 pRow->aParent[i] = pRow->aParent[--pRow->nParent];
@@ -259,99 +299,105 @@
299 i--;
300 }
301 }
302 }
303
304 /* Find the pChild pointer for each node.
305 **
306 ** The pChild points to node directly above on the same rail.
307 ** The pChild must be in the same branch. Leaf nodes have a NULL
308 ** pChild.
309 **
310 ** In the case of a fork, choose the pChild that results in the
311 ** longest rail.
312 */
313 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
314 if( pRow->isDup ) continue;
315 if( pRow->nParent==0 ) continue;
316 pParent = hashFind(p, pRow->aParent[0]);
317 if( pParent==0 ) continue;
318 if( pParent->zBranch!=pRow->zBranch ) continue;
319 if( pRow->idxTop < pParent->idxTop ){
320 pParent->pChild = pRow;
321 pParent->idxTop = pRow->idxTop;
 
 
322 }
323 }
324
325 /* Identify rows where the primary parent is off screen. Assign
326 ** each to a rail and draw descenders to the bottom of the screen.
327 **
328 ** Strive to put the "trunk" branch on far left.
329 */
330 zTrunk = persistBranchName(p, "trunk");
331 for(i=0; i<2; i++){
332 for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
333 if( i==0 ){
334 if( pRow->zBranch!=zTrunk ) continue;
335 }else {
336 if( pRow->iRail>=0 ) continue;
337 }
338 if( pRow->nParent==0 || hashFind(p,pRow->aParent[0])==0 ){
339 if( omitDescenders ){
340 pRow->iRail = findFreeRail(p, pRow->idxTop, pRow->idx, 0, 0);
341 }else{
342 pRow->iRail = ++p->mxRail;
343 }
344 mask = 1<<(pRow->iRail);
345 if( omitDescenders ){
346 if( pRow->pNext ) pRow->pNext->railInUse |= mask;
 
 
 
 
347 }else{
348 pRow->bDescender = pRow->nParent>0;
349 for(pLoop=pRow; pLoop; pLoop=pLoop->pNext){
350 pLoop->railInUse |= mask;
351 }
352 }
353 assignChildrenToRail(pRow);
354 }
355 }
356 }
357
358 /* Assign rails to all rows that are still unassigned.
 
 
359 */
360 inUse = (1<<(p->mxRail+1))-1;
361 for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
362 int parentRid;
363
364 if( pRow->iRail>=0 ){
365 if( pRow->pChild==0 ) inUse &= ~(1<<pRow->iRail);
366 continue;
367 }
368 if( pRow->isDup ){
369 pRow->iRail = findFreeRail(p, pRow->idx, pRow->idx, inUse, 0);
370 pDesc = pRow;
371 pParent = 0;
372 }else{
373 assert( pRow->nParent>0 );
374 parentRid = pRow->aParent[0];
375 pParent = hashFind(p, parentRid);
376 if( pParent==0 ){
377 /* Time skew */
378 pRow->iRail = ++p->mxRail;
379 pRow->railInUse = 1<<pRow->iRail;
380 continue;
381 }
382 pRow->iRail = findFreeRail(p, 0, pParent->idx, inUse, pParent->iRail);
383 pParent->aiRaiser[pRow->iRail] = pRow->idx;
 
 
 
 
384 }
385 mask = 1<<pRow->iRail;
386 if( pRow->pPrev ) pRow->pPrev->railInUse |= mask;
387 if( pRow->pNext ) pRow->pNext->railInUse |= mask;
388 if( pRow->pChild==0 ){
389 inUse &= ~mask;
390 }else{
391 inUse |= mask;
392 assignChildrenToRail(pRow);
393 }
394 if( pParent ){
395 for(pLoop=pParent; pLoop!=pRow; pLoop=pLoop->pPrev){
396 pLoop->railInUse |= mask;
397 }
398 }
 
399 }
400
401 /*
402 ** Insert merge rails and merge arrows
403 */
@@ -398,12 +444,11 @@
444 }
445
446 /*
447 ** Find the maximum rail number.
448 */
 
449 p->mxRail = 0;
450 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
451 if( pRow->iRail>p->mxRail ) p->mxRail = pRow->iRail;
452 if( pRow->mergeOut>p->mxRail ) p->mxRail = pRow->mergeOut;
453 }
454 }
455
M src/timeline.c
+2 -2
--- src/timeline.c
+++ src/timeline.c
@@ -353,20 +353,20 @@
353353
 );
354354
 cSep = '[';
355355
 for(i=0; i<GR_MAX_RAIL; i++){
356356
 if( i==pRow->iRail ) continue;
357357
 if( pRow->aiRaiser[i]>0 ){
358
- cgi_printf("%c%d,%d", cSep, pGraph->railMap[i], pRow->aiRaiser[i]);
358
+ cgi_printf("%c%d,%d", cSep, i, pRow->aiRaiser[i]);
359359
 cSep = ',';
360360
 }
361361
 }
362362
 if( cSep=='[' ) cgi_printf("[");
363363
 cgi_printf("],mi:");
364364
 cSep = '[';
365365
 for(i=0; i<GR_MAX_RAIL; i++){
366366
 if( pRow->mergeIn & (1<<i) ){
367
- cgi_printf("%c%d", cSep, pGraph->railMap[i]);
367
+ cgi_printf("%c%d", cSep, i);
368368
 cSep = ',';
369369
 }
370370
 }
371371
 if( cSep=='[' ) cgi_printf("[");
372372
 cgi_printf("]}%s", pRow->pNext ? ",\n" : "];\n");
373373
--- src/timeline.c
+++ src/timeline.c
@@ -353,20 +353,20 @@
353 );
354 cSep = '[';
355 for(i=0; i<GR_MAX_RAIL; i++){
356 if( i==pRow->iRail ) continue;
357 if( pRow->aiRaiser[i]>0 ){
358 cgi_printf("%c%d,%d", cSep, pGraph->railMap[i], pRow->aiRaiser[i]);
359 cSep = ',';
360 }
361 }
362 if( cSep=='[' ) cgi_printf("[");
363 cgi_printf("],mi:");
364 cSep = '[';
365 for(i=0; i<GR_MAX_RAIL; i++){
366 if( pRow->mergeIn & (1<<i) ){
367 cgi_printf("%c%d", cSep, pGraph->railMap[i]);
368 cSep = ',';
369 }
370 }
371 if( cSep=='[' ) cgi_printf("[");
372 cgi_printf("]}%s", pRow->pNext ? ",\n" : "];\n");
373
--- src/timeline.c
+++ src/timeline.c
@@ -353,20 +353,20 @@
353 );
354 cSep = '[';
355 for(i=0; i<GR_MAX_RAIL; i++){
356 if( i==pRow->iRail ) continue;
357 if( pRow->aiRaiser[i]>0 ){
358 cgi_printf("%c%d,%d", cSep, i, pRow->aiRaiser[i]);
359 cSep = ',';
360 }
361 }
362 if( cSep=='[' ) cgi_printf("[");
363 cgi_printf("],mi:");
364 cSep = '[';
365 for(i=0; i<GR_MAX_RAIL; i++){
366 if( pRow->mergeIn & (1<<i) ){
367 cgi_printf("%c%d", cSep, i);
368 cSep = ',';
369 }
370 }
371 if( cSep=='[' ) cgi_printf("[");
372 cgi_printf("]}%s", pRow->pNext ? ",\n" : "];\n");
373

Keyboard Shortcuts

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