Fossil SCM

Tweaks to the graph layout algorithm to try to get better graphs for individual file histories.

drh 2010-04-04 18:38 trunk
Commit 1d2608b7f4d748632ab0068f51e81e7b33bee058
Parent 251fd001a8c6e7a…
1 file changed +15 -8
~ src/graph.c
M src/graph.c
+15 -8
--- src/graph.c
+++ src/graph.c
@@ -43,11 +43,12 @@
4343
4444
 GraphRow *pNext; /* Next row down in the list of all rows */
4545
 GraphRow *pPrev; /* Previous row */
4646
4747
 int idx; /* Row index. First is 1. 0 used for "none" */
48
- int isLeaf; /* True if no direct child nodes */
48
+ u8 isLeaf; /* True if no direct child nodes */
49
+ u8 isDup; /* True if this is duplicate of a prior entry */
4950
 int iRail; /* Which rail this check-in appears on. 0-based.*/
5051
 int aiRaiser[GR_MAX_RAIL]; /* Raisers from this node to a higher row. */
5152
 int bDescender; /* Raiser from bottom of graph to here. */
5253
 u32 mergeIn; /* Merge in from other rails */
5354
 int mergeOut; /* Merge out to this rail */
@@ -108,20 +109,23 @@
108109
 free(p);
109110
 }
110111
111112
 /*
112113
 ** Insert a row into the hash table. If there is already another
113
-** row with the same rid, the other row is replaced.
114
+** row with the same rid, overwrite the prior entry if the overwrite
115
+** flag is set.
114116
 */
115
-static void hashInsert(GraphContext *p, GraphRow *pRow){
117
+static void hashInsert(GraphContext *p, GraphRow *pRow, int overwrite){
116118
 int h;
117119
 h = pRow->rid % p->nHash;
118120
 while( p->apHash[h] && p->apHash[h]->rid!=pRow->rid ){
119121
 h++;
120122
 if( h>=p->nHash ) h = 0;
121123
 }
122
- p->apHash[h] = pRow;
124
+ if( p->apHash[h]==0 || overwrite ){
125
+ p->apHash[h] = pRow;
126
+ }
123127
 }
124128
125129
 /*
126130
 ** Look up the row with rid.
127131
 */
@@ -218,11 +222,11 @@
218222
219223
 /*
220224
 ** Compute the complete graph
221225
 */
222226
 void graph_finish(GraphContext *p, int omitDescenders){
223
- GraphRow *pRow, *pDesc;
227
+ GraphRow *pRow, *pDesc, *pDup;
224228
 int i;
225229
 u32 mask;
226230
 u32 inUse;
227231
228232
 if( p==0 || p->pFirst==0 || p->nErr ) return;
@@ -232,11 +236,14 @@
232236
 p->apHash = safeMalloc( sizeof(p->apHash[0])*p->nHash );
233237
 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
234238
 if( pRow->pNext ) pRow->pNext->pPrev = pRow;
235239
 pRow->iRail = -1;
236240
 pRow->mergeOut = -1;
237
- hashInsert(p, pRow);
241
+ if( (pDup = hashFind(p, pRow->rid))!=0 ){
242
+ pDup->isDup = 1;
243
+ }
244
+ hashInsert(p, pRow, 1);
238245
 }
239246
 p->mxRail = -1;
240247
241248
 /* Purge merge-parents that are out-of-graph
242249
 */
@@ -254,11 +261,11 @@
254261
 */
255262
 memset(p->apHash, 0, sizeof(p->apHash[0])*p->nHash);
256263
 for(pRow=p->pLast; pRow; pRow=pRow->pPrev) pRow->isLeaf = 1;
257264
 for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
258265
 GraphRow *pParent;
259
- hashInsert(p, pRow);
266
+ hashInsert(p, pRow, 0);
260267
 if( pRow->nParent>0
261268
 && (pParent = hashFind(p, pRow->aParent[0]))!=0
262269
 && pRow->zBranch==pParent->zBranch
263270
 ){
264271
 pParent->isLeaf = 0;
@@ -296,11 +303,11 @@
296303
 for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
297304
 int parentRid;
298305
 if( pRow->iRail>=0 ) continue;
299306
 assert( pRow->nParent>0 );
300307
 parentRid = pRow->aParent[0];
301
- for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid; pDesc=pDesc->pNext){}
308
+ pDesc = hashFind(p, parentRid);
302309
 if( pDesc==0 ){
303310
 /* Time skew */
304311
 pRow->iRail = ++p->mxRail;
305312
 pRow->railInUse = 1<<pRow->iRail;
306313
 continue;
307314
--- src/graph.c
+++ src/graph.c
@@ -43,11 +43,12 @@
43
44 GraphRow *pNext; /* Next row down in the list of all rows */
45 GraphRow *pPrev; /* Previous row */
46
47 int idx; /* Row index. First is 1. 0 used for "none" */
48 int isLeaf; /* True if no direct child nodes */
 
49 int iRail; /* Which rail this check-in appears on. 0-based.*/
50 int aiRaiser[GR_MAX_RAIL]; /* Raisers from this node to a higher row. */
51 int bDescender; /* Raiser from bottom of graph to here. */
52 u32 mergeIn; /* Merge in from other rails */
53 int mergeOut; /* Merge out to this rail */
@@ -108,20 +109,23 @@
108 free(p);
109 }
110
111 /*
112 ** Insert a row into the hash table. If there is already another
113 ** row with the same rid, the other row is replaced.
 
114 */
115 static void hashInsert(GraphContext *p, GraphRow *pRow){
116 int h;
117 h = pRow->rid % p->nHash;
118 while( p->apHash[h] && p->apHash[h]->rid!=pRow->rid ){
119 h++;
120 if( h>=p->nHash ) h = 0;
121 }
122 p->apHash[h] = pRow;
 
 
123 }
124
125 /*
126 ** Look up the row with rid.
127 */
@@ -218,11 +222,11 @@
218
219 /*
220 ** Compute the complete graph
221 */
222 void graph_finish(GraphContext *p, int omitDescenders){
223 GraphRow *pRow, *pDesc;
224 int i;
225 u32 mask;
226 u32 inUse;
227
228 if( p==0 || p->pFirst==0 || p->nErr ) return;
@@ -232,11 +236,14 @@
232 p->apHash = safeMalloc( sizeof(p->apHash[0])*p->nHash );
233 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
234 if( pRow->pNext ) pRow->pNext->pPrev = pRow;
235 pRow->iRail = -1;
236 pRow->mergeOut = -1;
237 hashInsert(p, pRow);
 
 
 
238 }
239 p->mxRail = -1;
240
241 /* Purge merge-parents that are out-of-graph
242 */
@@ -254,11 +261,11 @@
254 */
255 memset(p->apHash, 0, sizeof(p->apHash[0])*p->nHash);
256 for(pRow=p->pLast; pRow; pRow=pRow->pPrev) pRow->isLeaf = 1;
257 for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
258 GraphRow *pParent;
259 hashInsert(p, pRow);
260 if( pRow->nParent>0
261 && (pParent = hashFind(p, pRow->aParent[0]))!=0
262 && pRow->zBranch==pParent->zBranch
263 ){
264 pParent->isLeaf = 0;
@@ -296,11 +303,11 @@
296 for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
297 int parentRid;
298 if( pRow->iRail>=0 ) continue;
299 assert( pRow->nParent>0 );
300 parentRid = pRow->aParent[0];
301 for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid; pDesc=pDesc->pNext){}
302 if( pDesc==0 ){
303 /* Time skew */
304 pRow->iRail = ++p->mxRail;
305 pRow->railInUse = 1<<pRow->iRail;
306 continue;
307
--- src/graph.c
+++ src/graph.c
@@ -43,11 +43,12 @@
43
44 GraphRow *pNext; /* Next row down in the list of all rows */
45 GraphRow *pPrev; /* Previous row */
46
47 int idx; /* Row index. First is 1. 0 used for "none" */
48 u8 isLeaf; /* True if no direct child nodes */
49 u8 isDup; /* True if this is duplicate of a prior entry */
50 int iRail; /* Which rail this check-in appears on. 0-based.*/
51 int aiRaiser[GR_MAX_RAIL]; /* Raisers from this node to a higher row. */
52 int bDescender; /* Raiser from bottom of graph to here. */
53 u32 mergeIn; /* Merge in from other rails */
54 int mergeOut; /* Merge out to this rail */
@@ -108,20 +109,23 @@
109 free(p);
110 }
111
112 /*
113 ** Insert a row into the hash table. If there is already another
114 ** row with the same rid, overwrite the prior entry if the overwrite
115 ** flag is set.
116 */
117 static void hashInsert(GraphContext *p, GraphRow *pRow, int overwrite){
118 int h;
119 h = pRow->rid % p->nHash;
120 while( p->apHash[h] && p->apHash[h]->rid!=pRow->rid ){
121 h++;
122 if( h>=p->nHash ) h = 0;
123 }
124 if( p->apHash[h]==0 || overwrite ){
125 p->apHash[h] = pRow;
126 }
127 }
128
129 /*
130 ** Look up the row with rid.
131 */
@@ -218,11 +222,11 @@
222
223 /*
224 ** Compute the complete graph
225 */
226 void graph_finish(GraphContext *p, int omitDescenders){
227 GraphRow *pRow, *pDesc, *pDup;
228 int i;
229 u32 mask;
230 u32 inUse;
231
232 if( p==0 || p->pFirst==0 || p->nErr ) return;
@@ -232,11 +236,14 @@
236 p->apHash = safeMalloc( sizeof(p->apHash[0])*p->nHash );
237 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
238 if( pRow->pNext ) pRow->pNext->pPrev = pRow;
239 pRow->iRail = -1;
240 pRow->mergeOut = -1;
241 if( (pDup = hashFind(p, pRow->rid))!=0 ){
242 pDup->isDup = 1;
243 }
244 hashInsert(p, pRow, 1);
245 }
246 p->mxRail = -1;
247
248 /* Purge merge-parents that are out-of-graph
249 */
@@ -254,11 +261,11 @@
261 */
262 memset(p->apHash, 0, sizeof(p->apHash[0])*p->nHash);
263 for(pRow=p->pLast; pRow; pRow=pRow->pPrev) pRow->isLeaf = 1;
264 for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
265 GraphRow *pParent;
266 hashInsert(p, pRow, 0);
267 if( pRow->nParent>0
268 && (pParent = hashFind(p, pRow->aParent[0]))!=0
269 && pRow->zBranch==pParent->zBranch
270 ){
271 pParent->isLeaf = 0;
@@ -296,11 +303,11 @@
303 for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
304 int parentRid;
305 if( pRow->iRail>=0 ) continue;
306 assert( pRow->nParent>0 );
307 parentRid = pRow->aParent[0];
308 pDesc = hashFind(p, parentRid);
309 if( pDesc==0 ){
310 /* Time skew */
311 pRow->iRail = ++p->mxRail;
312 pRow->railInUse = 1<<pRow->iRail;
313 continue;
314

Keyboard Shortcuts

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