Fossil SCM

Improved graph layout algorithm attempts to keep merge arrows in between their source and destination.

drh 2010-02-23 21:30 trunk
Commit 0f27a59808e214b274d76aba89d669fd7abe34c7
Parent 8fe33aa575be5c8…
1 file changed +24 -7
~ src/graph.c
M src/graph.c
+24 -7
--- src/graph.c
+++ src/graph.c
@@ -152,23 +152,39 @@
152152
153153
 /*
154154
 ** Return the index of a rail currently not in use for any row between
155155
 ** top and bottom, inclusive.
156156
 */
157
-static int findFreeRail(GraphContext *p, int top, int btm, u32 inUseMask){
157
+static int findFreeRail(
158
+ GraphContext *p, /* The graph context */
159
+ int top, int btm, /* Span of rows for which the rail is needed */
160
+ u32 inUseMask, /* Mask or rails already in use */
161
+ int iNearto /* Find rail nearest to this rail */
162
+){
158163
 GraphRow *pRow;
159164
 int i;
165
+ int iBest = 0;
166
+ int iBestDist = 9999;
160167
 for(pRow=p->pFirst; pRow && pRow->idx<top; pRow=pRow->pNext){}
161168
 while( pRow && pRow->idx<=btm ){
162169
 inUseMask |= pRow->railInUse;
163170
 pRow = pRow->pNext;
164171
 }
165172
 for(i=0; i<32; i++){
166
- if( (inUseMask & (1<<i))==0 ) return i;
173
+ if( (inUseMask & (1<<i))==0 ){
174
+ int dist;
175
+ if( iNearto<=0 ) return i;
176
+ dist = i - iNearto;
177
+ if( dist<0 ) dist = -dist;
178
+ if( dist<iBestDist ){
179
+ iBestDist = dist;
180
+ iBest = i;
181
+ }
182
+ }
167183
 }
168
- p->nErr++;
169
- return 0;
184
+ if( iBestDist>1000 ) p->nErr++;
185
+ return iBest;
170186
 }
171187
172188
 /*
173189
 ** Compute the complete graph
174190
 */
@@ -209,11 +225,11 @@
209225
 ** each to a rail and draw descenders to the bottom of the screen.
210226
 */
211227
 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
212228
 if( pRow->nParent==0 || !bag_find(&allRids,pRow->aParent[0]) ){
213229
 if( omitDescenders ){
214
- pRow->iRail = findFreeRail(p, pRow->idx, pRow->idx, 0);
230
+ pRow->iRail = findFreeRail(p, pRow->idx, pRow->idx, 0, 0);
215231
 }else{
216232
 pRow->iRail = ++p->mxRail;
217233
 }
218234
 mask = 1<<(pRow->iRail);
219235
 if( omitDescenders ){
@@ -247,11 +263,11 @@
247263
 continue;
248264
 }
249265
 if( pDesc->aiRaiser[pDesc->iRail]==0 && pDesc->zBranch==pRow->zBranch ){
250266
 pRow->iRail = pDesc->iRail;
251267
 }else{
252
- pRow->iRail = findFreeRail(p, 0, pDesc->idx, inUse);
268
+ pRow->iRail = findFreeRail(p, 0, pDesc->idx, inUse, 0);
253269
 }
254270
 pDesc->aiRaiser[pRow->iRail] = pRow->idx;
255271
 mask = 1<<pRow->iRail;
256272
 if( pRow->isLeaf ){
257273
 inUse &= ~mask;
@@ -273,11 +289,12 @@
273289
 int parentRid = pRow->aParent[i];
274290
 for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid;
275291
 pDesc=pDesc->pNext){}
276292
 if( pDesc==0 ) continue;
277293
 if( pDesc->mergeOut<0 ){
278
- pDesc->mergeOut = findFreeRail(p, pRow->idx, pDesc->idx, 0);
294
+ int iTarget = (pRow->iRail + pDesc->iRail)/2;
295
+ pDesc->mergeOut = findFreeRail(p, pRow->idx, pDesc->idx, 0, iTarget);
279296
 pDesc->mergeUpto = pRow->idx;
280297
 mask = 1<<pDesc->mergeOut;
281298
 pDesc->railInUse |= mask;
282299
 for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid;
283300
 pDesc=pDesc->pNext){
284301
--- src/graph.c
+++ src/graph.c
@@ -152,23 +152,39 @@
152
153 /*
154 ** Return the index of a rail currently not in use for any row between
155 ** top and bottom, inclusive.
156 */
157 static int findFreeRail(GraphContext *p, int top, int btm, u32 inUseMask){
 
 
 
 
 
158 GraphRow *pRow;
159 int i;
 
 
160 for(pRow=p->pFirst; pRow && pRow->idx<top; pRow=pRow->pNext){}
161 while( pRow && pRow->idx<=btm ){
162 inUseMask |= pRow->railInUse;
163 pRow = pRow->pNext;
164 }
165 for(i=0; i<32; i++){
166 if( (inUseMask & (1<<i))==0 ) return i;
 
 
 
 
 
 
 
 
 
167 }
168 p->nErr++;
169 return 0;
170 }
171
172 /*
173 ** Compute the complete graph
174 */
@@ -209,11 +225,11 @@
209 ** each to a rail and draw descenders to the bottom of the screen.
210 */
211 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
212 if( pRow->nParent==0 || !bag_find(&allRids,pRow->aParent[0]) ){
213 if( omitDescenders ){
214 pRow->iRail = findFreeRail(p, pRow->idx, pRow->idx, 0);
215 }else{
216 pRow->iRail = ++p->mxRail;
217 }
218 mask = 1<<(pRow->iRail);
219 if( omitDescenders ){
@@ -247,11 +263,11 @@
247 continue;
248 }
249 if( pDesc->aiRaiser[pDesc->iRail]==0 && pDesc->zBranch==pRow->zBranch ){
250 pRow->iRail = pDesc->iRail;
251 }else{
252 pRow->iRail = findFreeRail(p, 0, pDesc->idx, inUse);
253 }
254 pDesc->aiRaiser[pRow->iRail] = pRow->idx;
255 mask = 1<<pRow->iRail;
256 if( pRow->isLeaf ){
257 inUse &= ~mask;
@@ -273,11 +289,12 @@
273 int parentRid = pRow->aParent[i];
274 for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid;
275 pDesc=pDesc->pNext){}
276 if( pDesc==0 ) continue;
277 if( pDesc->mergeOut<0 ){
278 pDesc->mergeOut = findFreeRail(p, pRow->idx, pDesc->idx, 0);
 
279 pDesc->mergeUpto = pRow->idx;
280 mask = 1<<pDesc->mergeOut;
281 pDesc->railInUse |= mask;
282 for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid;
283 pDesc=pDesc->pNext){
284
--- src/graph.c
+++ src/graph.c
@@ -152,23 +152,39 @@
152
153 /*
154 ** Return the index of a rail currently not in use for any row between
155 ** top and bottom, inclusive.
156 */
157 static int findFreeRail(
158 GraphContext *p, /* The graph context */
159 int top, int btm, /* Span of rows for which the rail is needed */
160 u32 inUseMask, /* Mask or rails already in use */
161 int iNearto /* Find rail nearest to this rail */
162 ){
163 GraphRow *pRow;
164 int i;
165 int iBest = 0;
166 int iBestDist = 9999;
167 for(pRow=p->pFirst; pRow && pRow->idx<top; pRow=pRow->pNext){}
168 while( pRow && pRow->idx<=btm ){
169 inUseMask |= pRow->railInUse;
170 pRow = pRow->pNext;
171 }
172 for(i=0; i<32; i++){
173 if( (inUseMask & (1<<i))==0 ){
174 int dist;
175 if( iNearto<=0 ) return i;
176 dist = i - iNearto;
177 if( dist<0 ) dist = -dist;
178 if( dist<iBestDist ){
179 iBestDist = dist;
180 iBest = i;
181 }
182 }
183 }
184 if( iBestDist>1000 ) p->nErr++;
185 return iBest;
186 }
187
188 /*
189 ** Compute the complete graph
190 */
@@ -209,11 +225,11 @@
225 ** each to a rail and draw descenders to the bottom of the screen.
226 */
227 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
228 if( pRow->nParent==0 || !bag_find(&allRids,pRow->aParent[0]) ){
229 if( omitDescenders ){
230 pRow->iRail = findFreeRail(p, pRow->idx, pRow->idx, 0, 0);
231 }else{
232 pRow->iRail = ++p->mxRail;
233 }
234 mask = 1<<(pRow->iRail);
235 if( omitDescenders ){
@@ -247,11 +263,11 @@
263 continue;
264 }
265 if( pDesc->aiRaiser[pDesc->iRail]==0 && pDesc->zBranch==pRow->zBranch ){
266 pRow->iRail = pDesc->iRail;
267 }else{
268 pRow->iRail = findFreeRail(p, 0, pDesc->idx, inUse, 0);
269 }
270 pDesc->aiRaiser[pRow->iRail] = pRow->idx;
271 mask = 1<<pRow->iRail;
272 if( pRow->isLeaf ){
273 inUse &= ~mask;
@@ -273,11 +289,12 @@
289 int parentRid = pRow->aParent[i];
290 for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid;
291 pDesc=pDesc->pNext){}
292 if( pDesc==0 ) continue;
293 if( pDesc->mergeOut<0 ){
294 int iTarget = (pRow->iRail + pDesc->iRail)/2;
295 pDesc->mergeOut = findFreeRail(p, pRow->idx, pDesc->idx, 0, iTarget);
296 pDesc->mergeUpto = pRow->idx;
297 mask = 1<<pDesc->mergeOut;
298 pDesc->railInUse |= mask;
299 for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid;
300 pDesc=pDesc->pNext){
301

Keyboard Shortcuts

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