Fossil

Diff
Login

Diff

Differences From Artifact [f5c1c50ce4]:

To Artifact [a50528c5a7]:


41
42
43
44
45
46
47
48

49
50
51
52
53
54
55
  int aParent[GR_MAX_PARENT]; /* Array of parents.  0 element is primary .*/
  char *zBranch;              /* Branch name */

  GraphRow *pNext;            /* Next row down in the list of all rows */
  GraphRow *pPrev;            /* Previous row */
  
  int idx;                    /* Row index.  First is 1.  0 used for "none" */
  int isLeaf;                 /* True if no direct child nodes */

  int iRail;                  /* Which rail this check-in appears on. 0-based.*/
  int aiRaiser[GR_MAX_RAIL];  /* Raisers from this node to a higher row. */
  int bDescender;             /* Raiser from bottom of graph to here. */
  u32 mergeIn;                /* Merge in from other rails */
  int mergeOut;               /* Merge out to this rail */
  int mergeUpto;              /* Draw the merge rail up to this level */








|
>







41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
  int aParent[GR_MAX_PARENT]; /* Array of parents.  0 element is primary .*/
  char *zBranch;              /* Branch name */

  GraphRow *pNext;            /* Next row down in the list of all rows */
  GraphRow *pPrev;            /* Previous row */
  
  int idx;                    /* Row index.  First is 1.  0 used for "none" */
  u8 isLeaf;                  /* True if no direct child nodes */
  u8 isDup;                   /* True if this is duplicate of a prior entry */
  int iRail;                  /* Which rail this check-in appears on. 0-based.*/
  int aiRaiser[GR_MAX_RAIL];  /* Raisers from this node to a higher row. */
  int bDescender;             /* Raiser from bottom of graph to here. */
  u32 mergeIn;                /* Merge in from other rails */
  int mergeOut;               /* Merge out to this rail */
  int mergeUpto;              /* Draw the merge rail up to this level */

106
107
108
109
110
111
112
113

114
115
116
117
118
119
120
121

122

123
124
125
126
127
128
129
  free(p->azBranch);
  free(p->apHash);
  free(p);
}

/*
** Insert a row into the hash table.  If there is already another
** row with the same rid, the other row is replaced.

*/
static void hashInsert(GraphContext *p, GraphRow *pRow){
  int h;
  h = pRow->rid % p->nHash;
  while( p->apHash[h] && p->apHash[h]->rid!=pRow->rid ){
    h++;
    if( h>=p->nHash ) h = 0;
  }

  p->apHash[h] = pRow;

}

/*
** Look up the row with rid.
*/
static GraphRow *hashFind(GraphContext *p, int rid){
  int h = rid % p->nHash;







|
>

|






>
|
>







107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
  free(p->azBranch);
  free(p->apHash);
  free(p);
}

/*
** Insert a row into the hash table.  If there is already another
** row with the same rid, overwrite the prior entry if the overwrite
** flag is set.
*/
static void hashInsert(GraphContext *p, GraphRow *pRow, int overwrite){
  int h;
  h = pRow->rid % p->nHash;
  while( p->apHash[h] && p->apHash[h]->rid!=pRow->rid ){
    h++;
    if( h>=p->nHash ) h = 0;
  }
  if( p->apHash[h]==0 || overwrite ){
    p->apHash[h] = pRow;
  }
}

/*
** Look up the row with rid.
*/
static GraphRow *hashFind(GraphContext *p, int rid){
  int h = rid % p->nHash;
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236



237
238
239
240
241
242
243
244
  return iBest;
}

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

  if( p==0 || p->pFirst==0 || p->nErr ) return;

  /* Initialize all rows */
  p->nHash = p->nRow*2 + 1;
  p->apHash = safeMalloc( sizeof(p->apHash[0])*p->nHash );
  for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
    if( pRow->pNext ) pRow->pNext->pPrev = pRow;
    pRow->iRail = -1;
    pRow->mergeOut = -1;



    hashInsert(p, pRow);
  }
  p->mxRail = -1;

  /* Purge merge-parents that are out-of-graph
  */
  for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
    for(i=1; i<pRow->nParent; i++){







|













>
>
>
|







220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
  return iBest;
}

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

  if( p==0 || p->pFirst==0 || p->nErr ) return;

  /* Initialize all rows */
  p->nHash = p->nRow*2 + 1;
  p->apHash = safeMalloc( sizeof(p->apHash[0])*p->nHash );
  for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
    if( pRow->pNext ) pRow->pNext->pPrev = pRow;
    pRow->iRail = -1;
    pRow->mergeOut = -1;
    if( (pDup = hashFind(p, pRow->rid))!=0 ){
      pDup->isDup = 1;
    }
    hashInsert(p, pRow, 1);
  }
  p->mxRail = -1;

  /* Purge merge-parents that are out-of-graph
  */
  for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
    for(i=1; i<pRow->nParent; i++){
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
  /* Figure out which nodes have no direct children (children on
  ** the same rail).  Mark such nodes is isLeaf.
  */
  memset(p->apHash, 0, sizeof(p->apHash[0])*p->nHash);
  for(pRow=p->pLast; pRow; pRow=pRow->pPrev) pRow->isLeaf = 1;
  for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
    GraphRow *pParent;
    hashInsert(p, pRow);
    if( pRow->nParent>0
     && (pParent = hashFind(p, pRow->aParent[0]))!=0
     && pRow->zBranch==pParent->zBranch
    ){
      pParent->isLeaf = 0;
    }
  }







|







259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
  /* Figure out which nodes have no direct children (children on
  ** the same rail).  Mark such nodes is isLeaf.
  */
  memset(p->apHash, 0, sizeof(p->apHash[0])*p->nHash);
  for(pRow=p->pLast; pRow; pRow=pRow->pPrev) pRow->isLeaf = 1;
  for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
    GraphRow *pParent;
    hashInsert(p, pRow, 0);
    if( pRow->nParent>0
     && (pParent = hashFind(p, pRow->aParent[0]))!=0
     && pRow->zBranch==pParent->zBranch
    ){
      pParent->isLeaf = 0;
    }
  }
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
  */
  inUse = (1<<(p->mxRail+1))-1;
  for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
    int parentRid;
    if( pRow->iRail>=0 ) continue;
    assert( pRow->nParent>0 );
    parentRid = pRow->aParent[0];
    for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid; pDesc=pDesc->pNext){}
    if( pDesc==0 ){
      /* Time skew */
      pRow->iRail = ++p->mxRail;
      pRow->railInUse = 1<<pRow->iRail;
      continue;
    }
    if( pDesc->aiRaiser[pDesc->iRail]==0 && pDesc->zBranch==pRow->zBranch ){







|







301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
  */
  inUse = (1<<(p->mxRail+1))-1;
  for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
    int parentRid;
    if( pRow->iRail>=0 ) continue;
    assert( pRow->nParent>0 );
    parentRid = pRow->aParent[0];
    pDesc = hashFind(p, parentRid);
    if( pDesc==0 ){
      /* Time skew */
      pRow->iRail = ++p->mxRail;
      pRow->railInUse = 1<<pRow->iRail;
      continue;
    }
    if( pDesc->aiRaiser[pDesc->iRail]==0 && pDesc->zBranch==pRow->zBranch ){