Fossil

Check-in [0f27a59808]
Login

Check-in [0f27a59808]

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Improved graph layout algorithm attempts to keep merge arrows in between their source and destination.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 0f27a59808e214b274d76aba89d669fd7abe34c7
User & Date: drh 2010-02-23 21:30:36.000
Context
2010-02-24
04:11
Updates to the file format documentation. ... (check-in: f01ec9db8b user: drh tags: trunk)
2010-02-23
21:30
Improved graph layout algorithm attempts to keep merge arrows in between their source and destination. ... (check-in: 0f27a59808 user: drh tags: trunk)
16:14
Fix the Makefile so that all parameters are commented and so that it works with non-GNU makes. ... (check-in: 8fe33aa575 user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/graph.c.
︙︙
150
151
152
153
154
155
156
157





158
159


160
161
162
163
164
165
166







167


168
169
170
171
172
173
174
175
176

  p->pLast = pRow;
}

/*
** Return the index of a rail currently not in use for any row between
** top and bottom, inclusive.  
*/
static int findFreeRail(GraphContext *p, int top, int btm, u32 inUseMask){





  GraphRow *pRow;
  int i;


  for(pRow=p->pFirst; pRow && pRow->idx<top; pRow=pRow->pNext){}
  while( pRow && pRow->idx<=btm ){
    inUseMask |= pRow->railInUse;
    pRow = pRow->pNext;
  }
  for(i=0; i<32; i++){
    if( (inUseMask & (1<<i))==0 ) return i;







  }


  p->nErr++;
  return 0;
}

/*
** Compute the complete graph
*/
void graph_finish(GraphContext *p, int omitDescenders){
  GraphRow *pRow, *pDesc;








|
>
>
>
>
>


>
>






|
>
>
>
>
>
>
>
|
>
>
|
|








150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192

  p->pLast = pRow;
}

/*
** Return the index of a rail currently not in use for any row between
** top and bottom, inclusive.  
*/
static int findFreeRail(
  GraphContext *p,         /* The graph context */
  int top, int btm,        /* Span of rows for which the rail is needed */
  u32 inUseMask,           /* Mask or rails already in use */
  int iNearto              /* Find rail nearest to this rail */
){
  GraphRow *pRow;
  int i;
  int iBest = 0;
  int iBestDist = 9999;
  for(pRow=p->pFirst; pRow && pRow->idx<top; pRow=pRow->pNext){}
  while( pRow && pRow->idx<=btm ){
    inUseMask |= pRow->railInUse;
    pRow = pRow->pNext;
  }
  for(i=0; i<32; i++){
    if( (inUseMask & (1<<i))==0 ){
      int dist;
      if( iNearto<=0 ) return i;
      dist = i - iNearto;
      if( dist<0 ) dist = -dist;
      if( dist<iBestDist ){
        iBestDist = dist;
        iBest = i;
      }
    }
  }
  if( iBestDist>1000 ) p->nErr++;
  return iBest;
}

/*
** Compute the complete graph
*/
void graph_finish(GraphContext *p, int omitDescenders){
  GraphRow *pRow, *pDesc;
︙︙
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221


  /* Identify rows where the primary parent is off screen.  Assign
  ** each to a rail and draw descenders to the bottom of the screen.
  */
  for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
    if( pRow->nParent==0 || !bag_find(&allRids,pRow->aParent[0]) ){
      if( omitDescenders ){
        pRow->iRail = findFreeRail(p, pRow->idx, pRow->idx, 0);
      }else{
        pRow->iRail = ++p->mxRail;
      }
      mask = 1<<(pRow->iRail);
      if( omitDescenders ){
        pRow->railInUse |= mask;
        if( pRow->pNext ) pRow->pNext->railInUse |= mask;








|








223
224
225
226
227
228
229
230
231
232
233
234
235
236
237


  /* Identify rows where the primary parent is off screen.  Assign
  ** each to a rail and draw descenders to the bottom of the screen.
  */
  for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
    if( pRow->nParent==0 || !bag_find(&allRids,pRow->aParent[0]) ){
      if( omitDescenders ){
        pRow->iRail = findFreeRail(p, pRow->idx, pRow->idx, 0, 0);
      }else{
        pRow->iRail = ++p->mxRail;
      }
      mask = 1<<(pRow->iRail);
      if( omitDescenders ){
        pRow->railInUse |= mask;
        if( pRow->pNext ) pRow->pNext->railInUse |= mask;
︙︙
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259

      pRow->iRail = ++p->mxRail;
      pRow->railInUse = 1<<pRow->iRail;
      continue;
    }
    if( pDesc->aiRaiser[pDesc->iRail]==0 && pDesc->zBranch==pRow->zBranch ){
      pRow->iRail = pDesc->iRail;
    }else{
      pRow->iRail = findFreeRail(p, 0, pDesc->idx, inUse);
    }
    pDesc->aiRaiser[pRow->iRail] = pRow->idx;
    mask = 1<<pRow->iRail;
    if( pRow->isLeaf ){
      inUse &= ~mask;
    }else{
      inUse |= mask;








|








261
262
263
264
265
266
267
268
269
270
271
272
273
274
275

      pRow->iRail = ++p->mxRail;
      pRow->railInUse = 1<<pRow->iRail;
      continue;
    }
    if( pDesc->aiRaiser[pDesc->iRail]==0 && pDesc->zBranch==pRow->zBranch ){
      pRow->iRail = pDesc->iRail;
    }else{
      pRow->iRail = findFreeRail(p, 0, pDesc->idx, inUse, 0);
    }
    pDesc->aiRaiser[pRow->iRail] = pRow->idx;
    mask = 1<<pRow->iRail;
    if( pRow->isLeaf ){
      inUse &= ~mask;
    }else{
      inUse |= mask;
︙︙
271
272
273
274
275
276
277

278
279
280
281
282
283
284
285

  for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
    for(i=1; i<pRow->nParent; i++){
      int parentRid = pRow->aParent[i];
      for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid;
          pDesc=pDesc->pNext){}
      if( pDesc==0 ) continue;
      if( pDesc->mergeOut<0 ){

        pDesc->mergeOut = findFreeRail(p, pRow->idx, pDesc->idx, 0);
        pDesc->mergeUpto = pRow->idx;
        mask = 1<<pDesc->mergeOut;
        pDesc->railInUse |= mask;
        for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid;
             pDesc=pDesc->pNext){
          pDesc->railInUse |= mask;
        }








>
|








287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302

  for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
    for(i=1; i<pRow->nParent; i++){
      int parentRid = pRow->aParent[i];
      for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid;
          pDesc=pDesc->pNext){}
      if( pDesc==0 ) continue;
      if( pDesc->mergeOut<0 ){
        int iTarget = (pRow->iRail + pDesc->iRail)/2;
        pDesc->mergeOut = findFreeRail(p, pRow->idx, pDesc->idx, 0, iTarget);
        pDesc->mergeUpto = pRow->idx;
        mask = 1<<pDesc->mergeOut;
        pDesc->railInUse |= mask;
        for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid;
             pDesc=pDesc->pNext){
          pDesc->railInUse |= mask;
        }
︙︙