Fossil SCM

For file history graphs, use merge arrows to show when the same file appears in multiple check-ins.

drh 2010-04-04 21:47 trunk
Commit 6ea10c5e990d2e6eb6f5a0d8638eb8be6d7bace7
Parent 1d2608b7f4d7486…
1 file changed +52 -21
~ src/graph.c
M src/graph.c
+52 -21
--- src/graph.c
+++ src/graph.c
@@ -205,31 +205,36 @@
205205
 pRow = pRow->pNext;
206206
 }
207207
 for(i=0; i<32; i++){
208208
 if( (inUseMask & (1<<i))==0 ){
209209
 int dist;
210
- if( iNearto<=0 ) return i;
210
+ if( iNearto<=0 ){
211
+ if( i>p->mxRail ) p->mxRail = i;
212
+ return i;
213
+ }
211214
 dist = i - iNearto;
212215
 if( dist<0 ) dist = -dist;
213216
 if( dist<iBestDist ){
214217
 iBestDist = dist;
215218
 iBest = i;
216219
 }
217220
 }
218221
 }
219222
 if( iBestDist>1000 ) p->nErr++;
223
+ if( iBest>p->mxRail ) p->mxRail = iBest;
220224
 return iBest;
221225
 }
222226
223227
 /*
224228
 ** Compute the complete graph
225229
 */
226230
 void graph_finish(GraphContext *p, int omitDescenders){
227
- GraphRow *pRow, *pDesc, *pDup;
231
+ GraphRow *pRow, *pDesc, *pDup, *pLoop;
228232
 int i;
229233
 u32 mask;
230234
 u32 inUse;
235
+ int hasDup = 0; /* True if one or more isDup entries */
231236
232237
 if( p==0 || p->pFirst==0 || p->nErr ) return;
233238
234239
 /* Initialize all rows */
235240
 p->nHash = p->nRow*2 + 1;
@@ -237,10 +242,11 @@
237242
 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
238243
 if( pRow->pNext ) pRow->pNext->pPrev = pRow;
239244
 pRow->iRail = -1;
240245
 pRow->mergeOut = -1;
241246
 if( (pDup = hashFind(p, pRow->rid))!=0 ){
247
+ hasDup = 1;
242248
 pDup->isDup = 1;
243249
 }
244250
 hashInsert(p, pRow, 1);
245251
 }
246252
 p->mxRail = -1;
@@ -301,46 +307,49 @@
301307
 */
302308
 inUse = (1<<(p->mxRail+1))-1;
303309
 for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
304310
 int parentRid;
305311
 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
- }
315
- if( pDesc->aiRaiser[pDesc->iRail]==0 && pDesc->zBranch==pRow->zBranch ){
316
- pRow->iRail = pDesc->iRail;
312
+ if( pRow->isDup ){
313
+ pRow->iRail = findFreeRail(p, pRow->idx, pRow->idx, inUse, 0);
314
+ pDesc = pRow;
317315
 }else{
318
- pRow->iRail = findFreeRail(p, 0, pDesc->idx, inUse, pDesc->iRail);
316
+ assert( pRow->nParent>0 );
317
+ parentRid = pRow->aParent[0];
318
+ pDesc = hashFind(p, parentRid);
319
+ if( pDesc==0 ){
320
+ /* Time skew */
321
+ pRow->iRail = ++p->mxRail;
322
+ pRow->railInUse = 1<<pRow->iRail;
323
+ continue;
324
+ }
325
+ if( pDesc->aiRaiser[pDesc->iRail]==0 && pDesc->zBranch==pRow->zBranch ){
326
+ pRow->iRail = pDesc->iRail;
327
+ }else{
328
+ pRow->iRail = findFreeRail(p, 0, pDesc->idx, inUse, pDesc->iRail);
329
+ }
330
+ pDesc->aiRaiser[pRow->iRail] = pRow->idx;
319331
 }
320
- pDesc->aiRaiser[pRow->iRail] = pRow->idx;
321332
 mask = 1<<pRow->iRail;
322333
 if( pRow->isLeaf ){
323334
 inUse &= ~mask;
324335
 }else{
325336
 inUse |= mask;
326337
 }
327
- for(pDesc = pRow; ; pDesc=pDesc->pNext){
328
- assert( pDesc!=0 );
329
- pDesc->railInUse |= mask;
330
- if( pDesc->rid==parentRid ) break;
338
+ for(pLoop=pRow; pLoop && pLoop!=pDesc; pLoop=pLoop->pNext){
339
+ pLoop->railInUse |= mask;
331340
 }
341
+ pDesc->railInUse |= mask;
332342
 }
333343
334344
 /*
335345
 ** Insert merge rails and merge arrows
336346
 */
337347
 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
338348
 for(i=1; i<pRow->nParent; i++){
339349
 int parentRid = pRow->aParent[i];
340
- for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid;
341
- pDesc=pDesc->pNext){}
350
+ pDesc = hashFind(p, parentRid);
342351
 if( pDesc==0 ) continue;
343352
 if( pDesc->mergeOut<0 ){
344353
 int iTarget = (pRow->iRail + pDesc->iRail)/2;
345354
 pDesc->mergeOut = findFreeRail(p, pRow->idx, pDesc->idx, 0, iTarget);
346355
 pDesc->mergeUpto = pRow->idx;
@@ -348,10 +357,32 @@
348357
 pDesc->railInUse |= mask;
349358
 for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid;
350359
 pDesc=pDesc->pNext){
351360
 pDesc->railInUse |= mask;
352361
 }
362
+ }
363
+ pRow->mergeIn |= 1<<pDesc->mergeOut;
364
+ }
365
+ }
366
+
367
+ /*
368
+ ** Insert merge rails from primaries to duplicates.
369
+ */
370
+ if( hasDup ){
371
+ for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
372
+ if( !pRow->isDup ) continue;
373
+ pDesc = hashFind(p, pRow->rid);
374
+ assert( pDesc!=0 && pDesc!=pRow );
375
+ if( pDesc->mergeOut<0 ){
376
+ int iTarget = (pRow->iRail + pDesc->iRail)/2;
377
+ pDesc->mergeOut = findFreeRail(p, pRow->idx, pDesc->idx, 0, iTarget);
378
+ pDesc->mergeUpto = pRow->idx;
379
+ mask = 1<<pDesc->mergeOut;
380
+ pDesc->railInUse |= mask;
381
+ for(pLoop=pRow->pNext; pLoop && pLoop!=pDesc; pLoop=pLoop->pNext){
382
+ pLoop->railInUse |= mask;
383
+ }
353384
 }
354385
 pRow->mergeIn |= 1<<pDesc->mergeOut;
355386
 }
356387
 }
357388
358389
--- src/graph.c
+++ src/graph.c
@@ -205,31 +205,36 @@
205 pRow = pRow->pNext;
206 }
207 for(i=0; i<32; i++){
208 if( (inUseMask & (1<<i))==0 ){
209 int dist;
210 if( iNearto<=0 ) return i;
 
 
 
211 dist = i - iNearto;
212 if( dist<0 ) dist = -dist;
213 if( dist<iBestDist ){
214 iBestDist = dist;
215 iBest = i;
216 }
217 }
218 }
219 if( iBestDist>1000 ) p->nErr++;
 
220 return iBest;
221 }
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;
233
234 /* Initialize all rows */
235 p->nHash = p->nRow*2 + 1;
@@ -237,10 +242,11 @@
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;
@@ -301,46 +307,49 @@
301 */
302 inUse = (1<<(p->mxRail+1))-1;
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 }
315 if( pDesc->aiRaiser[pDesc->iRail]==0 && pDesc->zBranch==pRow->zBranch ){
316 pRow->iRail = pDesc->iRail;
317 }else{
318 pRow->iRail = findFreeRail(p, 0, pDesc->idx, inUse, pDesc->iRail);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
319 }
320 pDesc->aiRaiser[pRow->iRail] = pRow->idx;
321 mask = 1<<pRow->iRail;
322 if( pRow->isLeaf ){
323 inUse &= ~mask;
324 }else{
325 inUse |= mask;
326 }
327 for(pDesc = pRow; ; pDesc=pDesc->pNext){
328 assert( pDesc!=0 );
329 pDesc->railInUse |= mask;
330 if( pDesc->rid==parentRid ) break;
331 }
 
332 }
333
334 /*
335 ** Insert merge rails and merge arrows
336 */
337 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
338 for(i=1; i<pRow->nParent; i++){
339 int parentRid = pRow->aParent[i];
340 for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid;
341 pDesc=pDesc->pNext){}
342 if( pDesc==0 ) continue;
343 if( pDesc->mergeOut<0 ){
344 int iTarget = (pRow->iRail + pDesc->iRail)/2;
345 pDesc->mergeOut = findFreeRail(p, pRow->idx, pDesc->idx, 0, iTarget);
346 pDesc->mergeUpto = pRow->idx;
@@ -348,10 +357,32 @@
348 pDesc->railInUse |= mask;
349 for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid;
350 pDesc=pDesc->pNext){
351 pDesc->railInUse |= mask;
352 }
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
353 }
354 pRow->mergeIn |= 1<<pDesc->mergeOut;
355 }
356 }
357
358
--- src/graph.c
+++ src/graph.c
@@ -205,31 +205,36 @@
205 pRow = pRow->pNext;
206 }
207 for(i=0; i<32; i++){
208 if( (inUseMask & (1<<i))==0 ){
209 int dist;
210 if( iNearto<=0 ){
211 if( i>p->mxRail ) p->mxRail = i;
212 return i;
213 }
214 dist = i - iNearto;
215 if( dist<0 ) dist = -dist;
216 if( dist<iBestDist ){
217 iBestDist = dist;
218 iBest = i;
219 }
220 }
221 }
222 if( iBestDist>1000 ) p->nErr++;
223 if( iBest>p->mxRail ) p->mxRail = iBest;
224 return iBest;
225 }
226
227 /*
228 ** Compute the complete graph
229 */
230 void graph_finish(GraphContext *p, int omitDescenders){
231 GraphRow *pRow, *pDesc, *pDup, *pLoop;
232 int i;
233 u32 mask;
234 u32 inUse;
235 int hasDup = 0; /* True if one or more isDup entries */
236
237 if( p==0 || p->pFirst==0 || p->nErr ) return;
238
239 /* Initialize all rows */
240 p->nHash = p->nRow*2 + 1;
@@ -237,10 +242,11 @@
242 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
243 if( pRow->pNext ) pRow->pNext->pPrev = pRow;
244 pRow->iRail = -1;
245 pRow->mergeOut = -1;
246 if( (pDup = hashFind(p, pRow->rid))!=0 ){
247 hasDup = 1;
248 pDup->isDup = 1;
249 }
250 hashInsert(p, pRow, 1);
251 }
252 p->mxRail = -1;
@@ -301,46 +307,49 @@
307 */
308 inUse = (1<<(p->mxRail+1))-1;
309 for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
310 int parentRid;
311 if( pRow->iRail>=0 ) continue;
312 if( pRow->isDup ){
313 pRow->iRail = findFreeRail(p, pRow->idx, pRow->idx, inUse, 0);
314 pDesc = pRow;
 
 
 
 
 
 
 
 
315 }else{
316 assert( pRow->nParent>0 );
317 parentRid = pRow->aParent[0];
318 pDesc = hashFind(p, parentRid);
319 if( pDesc==0 ){
320 /* Time skew */
321 pRow->iRail = ++p->mxRail;
322 pRow->railInUse = 1<<pRow->iRail;
323 continue;
324 }
325 if( pDesc->aiRaiser[pDesc->iRail]==0 && pDesc->zBranch==pRow->zBranch ){
326 pRow->iRail = pDesc->iRail;
327 }else{
328 pRow->iRail = findFreeRail(p, 0, pDesc->idx, inUse, pDesc->iRail);
329 }
330 pDesc->aiRaiser[pRow->iRail] = pRow->idx;
331 }
 
332 mask = 1<<pRow->iRail;
333 if( pRow->isLeaf ){
334 inUse &= ~mask;
335 }else{
336 inUse |= mask;
337 }
338 for(pLoop=pRow; pLoop && pLoop!=pDesc; pLoop=pLoop->pNext){
339 pLoop->railInUse |= mask;
 
 
340 }
341 pDesc->railInUse |= mask;
342 }
343
344 /*
345 ** Insert merge rails and merge arrows
346 */
347 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
348 for(i=1; i<pRow->nParent; i++){
349 int parentRid = pRow->aParent[i];
350 pDesc = hashFind(p, parentRid);
 
351 if( pDesc==0 ) continue;
352 if( pDesc->mergeOut<0 ){
353 int iTarget = (pRow->iRail + pDesc->iRail)/2;
354 pDesc->mergeOut = findFreeRail(p, pRow->idx, pDesc->idx, 0, iTarget);
355 pDesc->mergeUpto = pRow->idx;
@@ -348,10 +357,32 @@
357 pDesc->railInUse |= mask;
358 for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid;
359 pDesc=pDesc->pNext){
360 pDesc->railInUse |= mask;
361 }
362 }
363 pRow->mergeIn |= 1<<pDesc->mergeOut;
364 }
365 }
366
367 /*
368 ** Insert merge rails from primaries to duplicates.
369 */
370 if( hasDup ){
371 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
372 if( !pRow->isDup ) continue;
373 pDesc = hashFind(p, pRow->rid);
374 assert( pDesc!=0 && pDesc!=pRow );
375 if( pDesc->mergeOut<0 ){
376 int iTarget = (pRow->iRail + pDesc->iRail)/2;
377 pDesc->mergeOut = findFreeRail(p, pRow->idx, pDesc->idx, 0, iTarget);
378 pDesc->mergeUpto = pRow->idx;
379 mask = 1<<pDesc->mergeOut;
380 pDesc->railInUse |= mask;
381 for(pLoop=pRow->pNext; pLoop && pLoop!=pDesc; pLoop=pLoop->pNext){
382 pLoop->railInUse |= mask;
383 }
384 }
385 pRow->mergeIn |= 1<<pDesc->mergeOut;
386 }
387 }
388
389

Keyboard Shortcuts

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