Fossil SCM

Pull in recent graph layout changes.

drh 2010-04-04 23:20 clear-title merge
Commit 0551ff817897b267c22632f6684fa16b13c47c48
Parent 64541535d92a6fd…
1 file changed +66 -29
~ src/graph.c
M src/graph.c
+66 -29
--- 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
 */
@@ -201,11 +205,13 @@
201205
 pRow = pRow->pNext;
202206
 }
203207
 for(i=0; i<32; i++){
204208
 if( (inUseMask & (1<<i))==0 ){
205209
 int dist;
206
- if( iNearto<=0 ) return i;
210
+ if( iNearto<=0 ){
211
+ return i;
212
+ }
207213
 dist = i - iNearto;
208214
 if( dist<0 ) dist = -dist;
209215
 if( dist<iBestDist ){
210216
 iBestDist = dist;
211217
 iBest = i;
@@ -218,14 +224,15 @@
218224
219225
 /*
220226
 ** Compute the complete graph
221227
 */
222228
 void graph_finish(GraphContext *p, int omitDescenders){
223
- GraphRow *pRow, *pDesc;
229
+ GraphRow *pRow, *pDesc, *pDup, *pLoop;
224230
 int i;
225231
 u32 mask;
226232
 u32 inUse;
233
+ int hasDup = 0; /* True if one or more isDup entries */
227234
228235
 if( p==0 || p->pFirst==0 || p->nErr ) return;
229236
230237
 /* Initialize all rows */
231238
 p->nHash = p->nRow*2 + 1;
@@ -232,11 +239,15 @@
232239
 p->apHash = safeMalloc( sizeof(p->apHash[0])*p->nHash );
233240
 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
234241
 if( pRow->pNext ) pRow->pNext->pPrev = pRow;
235242
 pRow->iRail = -1;
236243
 pRow->mergeOut = -1;
237
- hashInsert(p, pRow);
244
+ if( (pDup = hashFind(p, pRow->rid))!=0 ){
245
+ hasDup = 1;
246
+ pDup->isDup = 1;
247
+ }
248
+ hashInsert(p, pRow, 1);
238249
 }
239250
 p->mxRail = -1;
240251
241252
 /* Purge merge-parents that are out-of-graph
242253
 */
@@ -248,18 +259,19 @@
248259
 }
249260
 }
250261
 }
251262
252263
 /* Figure out which nodes have no direct children (children on
253
- ** the same rail). Mark such nodes is isLeaf.
264
+ ** the same rail). Mark such nodes as isLeaf.
254265
 */
255266
 memset(p->apHash, 0, sizeof(p->apHash[0])*p->nHash);
256267
 for(pRow=p->pLast; pRow; pRow=pRow->pPrev) pRow->isLeaf = 1;
257268
 for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
258269
 GraphRow *pParent;
259
- hashInsert(p, pRow);
260
- if( pRow->nParent>0
270
+ hashInsert(p, pRow, 0);
271
+ if( !pRow->isDup
272
+ && pRow->nParent>0
261273
 && (pParent = hashFind(p, pRow->aParent[0]))!=0
262274
 && pRow->zBranch==pParent->zBranch
263275
 ){
264276
 pParent->isLeaf = 0;
265277
 }
@@ -294,46 +306,49 @@
294306
 */
295307
 inUse = (1<<(p->mxRail+1))-1;
296308
 for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
297309
 int parentRid;
298310
 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
- }
308
- if( pDesc->aiRaiser[pDesc->iRail]==0 && pDesc->zBranch==pRow->zBranch ){
309
- pRow->iRail = pDesc->iRail;
311
+ if( pRow->isDup ){
312
+ pRow->iRail = findFreeRail(p, pRow->idx, pRow->idx, inUse, 0);
313
+ pDesc = pRow;
310314
 }else{
311
- pRow->iRail = findFreeRail(p, 0, pDesc->idx, inUse, pDesc->iRail);
315
+ assert( pRow->nParent>0 );
316
+ parentRid = pRow->aParent[0];
317
+ pDesc = hashFind(p, parentRid);
318
+ if( pDesc==0 ){
319
+ /* Time skew */
320
+ pRow->iRail = ++p->mxRail;
321
+ pRow->railInUse = 1<<pRow->iRail;
322
+ continue;
323
+ }
324
+ if( pDesc->aiRaiser[pDesc->iRail]==0 && pDesc->zBranch==pRow->zBranch ){
325
+ pRow->iRail = pDesc->iRail;
326
+ }else{
327
+ pRow->iRail = findFreeRail(p, 0, pDesc->idx, inUse, pDesc->iRail);
328
+ }
329
+ pDesc->aiRaiser[pRow->iRail] = pRow->idx;
312330
 }
313
- pDesc->aiRaiser[pRow->iRail] = pRow->idx;
314331
 mask = 1<<pRow->iRail;
315332
 if( pRow->isLeaf ){
316333
 inUse &= ~mask;
317334
 }else{
318335
 inUse |= mask;
319336
 }
320
- for(pDesc = pRow; ; pDesc=pDesc->pNext){
321
- assert( pDesc!=0 );
322
- pDesc->railInUse |= mask;
323
- if( pDesc->rid==parentRid ) break;
337
+ for(pLoop=pRow; pLoop && pLoop!=pDesc; pLoop=pLoop->pNext){
338
+ pLoop->railInUse |= mask;
324339
 }
340
+ pDesc->railInUse |= mask;
325341
 }
326342
327343
 /*
328344
 ** Insert merge rails and merge arrows
329345
 */
330346
 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
331347
 for(i=1; i<pRow->nParent; i++){
332348
 int parentRid = pRow->aParent[i];
333
- for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid;
334
- pDesc=pDesc->pNext){}
349
+ pDesc = hashFind(p, parentRid);
335350
 if( pDesc==0 ) continue;
336351
 if( pDesc->mergeOut<0 ){
337352
 int iTarget = (pRow->iRail + pDesc->iRail)/2;
338353
 pDesc->mergeOut = findFreeRail(p, pRow->idx, pDesc->idx, 0, iTarget);
339354
 pDesc->mergeUpto = pRow->idx;
@@ -341,10 +356,32 @@
341356
 pDesc->railInUse |= mask;
342357
 for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid;
343358
 pDesc=pDesc->pNext){
344359
 pDesc->railInUse |= mask;
345360
 }
361
+ }
362
+ pRow->mergeIn |= 1<<pDesc->mergeOut;
363
+ }
364
+ }
365
+
366
+ /*
367
+ ** Insert merge rails from primaries to duplicates.
368
+ */
369
+ if( hasDup ){
370
+ for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
371
+ if( !pRow->isDup ) continue;
372
+ pDesc = hashFind(p, pRow->rid);
373
+ assert( pDesc!=0 && pDesc!=pRow );
374
+ if( pDesc->mergeOut<0 ){
375
+ int iTarget = (pRow->iRail + pDesc->iRail)/2;
376
+ pDesc->mergeOut = findFreeRail(p, pRow->idx, pDesc->idx, 0, iTarget);
377
+ pDesc->mergeUpto = pRow->idx;
378
+ mask = 1<<pDesc->mergeOut;
379
+ pDesc->railInUse |= mask;
380
+ for(pLoop=pRow->pNext; pLoop && pLoop!=pDesc; pLoop=pLoop->pNext){
381
+ pLoop->railInUse |= mask;
382
+ }
346383
 }
347384
 pRow->mergeIn |= 1<<pDesc->mergeOut;
348385
 }
349386
 }
350387
351388
--- 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 */
@@ -201,11 +205,13 @@
201 pRow = pRow->pNext;
202 }
203 for(i=0; i<32; i++){
204 if( (inUseMask & (1<<i))==0 ){
205 int dist;
206 if( iNearto<=0 ) return i;
 
 
207 dist = i - iNearto;
208 if( dist<0 ) dist = -dist;
209 if( dist<iBestDist ){
210 iBestDist = dist;
211 iBest = i;
@@ -218,14 +224,15 @@
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;
229
230 /* Initialize all rows */
231 p->nHash = p->nRow*2 + 1;
@@ -232,11 +239,15 @@
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 */
@@ -248,18 +259,19 @@
248 }
249 }
250 }
251
252 /* Figure out which nodes have no direct children (children on
253 ** the same rail). Mark such nodes is isLeaf.
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;
265 }
@@ -294,46 +306,49 @@
294 */
295 inUse = (1<<(p->mxRail+1))-1;
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 }
308 if( pDesc->aiRaiser[pDesc->iRail]==0 && pDesc->zBranch==pRow->zBranch ){
309 pRow->iRail = pDesc->iRail;
310 }else{
311 pRow->iRail = findFreeRail(p, 0, pDesc->idx, inUse, pDesc->iRail);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
312 }
313 pDesc->aiRaiser[pRow->iRail] = pRow->idx;
314 mask = 1<<pRow->iRail;
315 if( pRow->isLeaf ){
316 inUse &= ~mask;
317 }else{
318 inUse |= mask;
319 }
320 for(pDesc = pRow; ; pDesc=pDesc->pNext){
321 assert( pDesc!=0 );
322 pDesc->railInUse |= mask;
323 if( pDesc->rid==parentRid ) break;
324 }
 
325 }
326
327 /*
328 ** Insert merge rails and merge arrows
329 */
330 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
331 for(i=1; i<pRow->nParent; i++){
332 int parentRid = pRow->aParent[i];
333 for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid;
334 pDesc=pDesc->pNext){}
335 if( pDesc==0 ) continue;
336 if( pDesc->mergeOut<0 ){
337 int iTarget = (pRow->iRail + pDesc->iRail)/2;
338 pDesc->mergeOut = findFreeRail(p, pRow->idx, pDesc->idx, 0, iTarget);
339 pDesc->mergeUpto = pRow->idx;
@@ -341,10 +356,32 @@
341 pDesc->railInUse |= mask;
342 for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid;
343 pDesc=pDesc->pNext){
344 pDesc->railInUse |= mask;
345 }
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
346 }
347 pRow->mergeIn |= 1<<pDesc->mergeOut;
348 }
349 }
350
351
--- 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 */
@@ -201,11 +205,13 @@
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 return i;
212 }
213 dist = i - iNearto;
214 if( dist<0 ) dist = -dist;
215 if( dist<iBestDist ){
216 iBestDist = dist;
217 iBest = i;
@@ -218,14 +224,15 @@
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
235 if( p==0 || p->pFirst==0 || p->nErr ) return;
236
237 /* Initialize all rows */
238 p->nHash = p->nRow*2 + 1;
@@ -232,11 +239,15 @@
239 p->apHash = safeMalloc( sizeof(p->apHash[0])*p->nHash );
240 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
241 if( pRow->pNext ) pRow->pNext->pPrev = pRow;
242 pRow->iRail = -1;
243 pRow->mergeOut = -1;
244 if( (pDup = hashFind(p, pRow->rid))!=0 ){
245 hasDup = 1;
246 pDup->isDup = 1;
247 }
248 hashInsert(p, pRow, 1);
249 }
250 p->mxRail = -1;
251
252 /* Purge merge-parents that are out-of-graph
253 */
@@ -248,18 +259,19 @@
259 }
260 }
261 }
262
263 /* Figure out which nodes have no direct children (children on
264 ** the same rail). Mark such nodes as isLeaf.
265 */
266 memset(p->apHash, 0, sizeof(p->apHash[0])*p->nHash);
267 for(pRow=p->pLast; pRow; pRow=pRow->pPrev) pRow->isLeaf = 1;
268 for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
269 GraphRow *pParent;
270 hashInsert(p, pRow, 0);
271 if( !pRow->isDup
272 && pRow->nParent>0
273 && (pParent = hashFind(p, pRow->aParent[0]))!=0
274 && pRow->zBranch==pParent->zBranch
275 ){
276 pParent->isLeaf = 0;
277 }
@@ -294,46 +306,49 @@
306 */
307 inUse = (1<<(p->mxRail+1))-1;
308 for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
309 int parentRid;
310 if( pRow->iRail>=0 ) continue;
311 if( pRow->isDup ){
312 pRow->iRail = findFreeRail(p, pRow->idx, pRow->idx, inUse, 0);
313 pDesc = pRow;
 
 
 
 
 
 
 
 
314 }else{
315 assert( pRow->nParent>0 );
316 parentRid = pRow->aParent[0];
317 pDesc = hashFind(p, parentRid);
318 if( pDesc==0 ){
319 /* Time skew */
320 pRow->iRail = ++p->mxRail;
321 pRow->railInUse = 1<<pRow->iRail;
322 continue;
323 }
324 if( pDesc->aiRaiser[pDesc->iRail]==0 && pDesc->zBranch==pRow->zBranch ){
325 pRow->iRail = pDesc->iRail;
326 }else{
327 pRow->iRail = findFreeRail(p, 0, pDesc->idx, inUse, pDesc->iRail);
328 }
329 pDesc->aiRaiser[pRow->iRail] = pRow->idx;
330 }
 
331 mask = 1<<pRow->iRail;
332 if( pRow->isLeaf ){
333 inUse &= ~mask;
334 }else{
335 inUse |= mask;
336 }
337 for(pLoop=pRow; pLoop && pLoop!=pDesc; pLoop=pLoop->pNext){
338 pLoop->railInUse |= mask;
 
 
339 }
340 pDesc->railInUse |= mask;
341 }
342
343 /*
344 ** Insert merge rails and merge arrows
345 */
346 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
347 for(i=1; i<pRow->nParent; i++){
348 int parentRid = pRow->aParent[i];
349 pDesc = hashFind(p, parentRid);
 
350 if( pDesc==0 ) continue;
351 if( pDesc->mergeOut<0 ){
352 int iTarget = (pRow->iRail + pDesc->iRail)/2;
353 pDesc->mergeOut = findFreeRail(p, pRow->idx, pDesc->idx, 0, iTarget);
354 pDesc->mergeUpto = pRow->idx;
@@ -341,10 +356,32 @@
356 pDesc->railInUse |= mask;
357 for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid;
358 pDesc=pDesc->pNext){
359 pDesc->railInUse |= mask;
360 }
361 }
362 pRow->mergeIn |= 1<<pDesc->mergeOut;
363 }
364 }
365
366 /*
367 ** Insert merge rails from primaries to duplicates.
368 */
369 if( hasDup ){
370 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
371 if( !pRow->isDup ) continue;
372 pDesc = hashFind(p, pRow->rid);
373 assert( pDesc!=0 && pDesc!=pRow );
374 if( pDesc->mergeOut<0 ){
375 int iTarget = (pRow->iRail + pDesc->iRail)/2;
376 pDesc->mergeOut = findFreeRail(p, pRow->idx, pDesc->idx, 0, iTarget);
377 pDesc->mergeUpto = pRow->idx;
378 mask = 1<<pDesc->mergeOut;
379 pDesc->railInUse |= mask;
380 for(pLoop=pRow->pNext; pLoop && pLoop!=pDesc; pLoop=pLoop->pNext){
381 pLoop->railInUse |= mask;
382 }
383 }
384 pRow->mergeIn |= 1<<pDesc->mergeOut;
385 }
386 }
387
388

Keyboard Shortcuts

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