| | @@ -35,19 +35,19 @@ |
| 35 | 35 | /* The graph appears vertically beside a timeline. Each row in the |
| 36 | 36 | ** timeline corresponds to a row in the graph. |
| 37 | 37 | */ |
| 38 | 38 | struct GraphRow { |
| 39 | 39 | int rid; /* The rid for the check-in */ |
| 40 | | - int isLeaf; /* True if the check-in is an open leaf */ |
| 41 | 40 | int nParent; /* Number of parents */ |
| 42 | 41 | int aParent[GR_MAX_PARENT]; /* Array of parents. 0 element is primary .*/ |
| 43 | 42 | char *zBranch; /* Branch name */ |
| 44 | 43 | |
| 45 | 44 | GraphRow *pNext; /* Next row down in the list of all rows */ |
| 46 | 45 | GraphRow *pPrev; /* Previous row */ |
| 47 | 46 | |
| 48 | 47 | int idx; /* Row index. First is 1. 0 used for "none" */ |
| 48 | + int isLeaf; /* True if no direct child nodes */ |
| 49 | 49 | int iRail; /* Which rail this check-in appears on. 0-based.*/ |
| 50 | 50 | int aiRaiser[GR_MAX_RAIL]; /* Raisers from this node to a higher row. */ |
| 51 | 51 | int bDescender; /* Raiser from bottom of graph to here. */ |
| 52 | 52 | u32 mergeIn; /* Merge in from other rails */ |
| 53 | 53 | int mergeOut; /* Merge out to this rail */ |
| | @@ -63,11 +63,14 @@ |
| 63 | 63 | int mxRail; /* Number of rails required to render the graph */ |
| 64 | 64 | GraphRow *pFirst; /* First row in the list */ |
| 65 | 65 | GraphRow *pLast; /* Last row in the list */ |
| 66 | 66 | int nBranch; /* Number of distinct branches */ |
| 67 | 67 | char **azBranch; /* Names of the branches */ |
| 68 | + int nRow; /* Number of rows */ |
| 68 | 69 | int railMap[GR_MAX_RAIL]; /* Rail order mapping */ |
| 70 | + int nHash; /* Number of slots in apHash[] */ |
| 71 | + GraphRow **apHash; /* Hash table of rows */ |
| 69 | 72 | }; |
| 70 | 73 | |
| 71 | 74 | #endif |
| 72 | 75 | |
| 73 | 76 | /* |
| | @@ -99,12 +102,39 @@ |
| 99 | 102 | p->pFirst = pRow->pNext; |
| 100 | 103 | free(pRow); |
| 101 | 104 | } |
| 102 | 105 | for(i=0; i<p->nBranch; i++) free(p->azBranch[i]); |
| 103 | 106 | free(p->azBranch); |
| 107 | + free(p->apHash); |
| 104 | 108 | free(p); |
| 105 | 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 | +*/ |
| 128 | +static GraphRow *hashFind(GraphContext *p, int rid){ |
| 129 | + int h = rid % p->nHash; |
| 130 | + while( p->apHash[h] && p->apHash[h]->rid!=rid ){ |
| 131 | + h++; |
| 132 | + if( h>=p->nHash ) h = 0; |
| 133 | + } |
| 134 | + return p->apHash[h]; |
| 135 | +} |
| 106 | 136 | |
| 107 | 137 | /* |
| 108 | 138 | ** Return the canonical pointer for a given branch name. |
| 109 | 139 | ** Multiple calls to this routine with equivalent strings |
| 110 | 140 | ** will return the same pointer. |
| | @@ -122,34 +152,35 @@ |
| 122 | 152 | } |
| 123 | 153 | |
| 124 | 154 | /* |
| 125 | 155 | ** Add a new row t the graph context. Rows are added from top to bottom. |
| 126 | 156 | */ |
| 127 | | -void graph_add_row( |
| 157 | +int graph_add_row( |
| 128 | 158 | GraphContext *p, /* The context to which the row is added */ |
| 129 | 159 | int rid, /* RID for the check-in */ |
| 130 | | - int isLeaf, /* True if the check-in is an leaf */ |
| 131 | 160 | int nParent, /* Number of parents */ |
| 132 | 161 | int *aParent, /* Array of parents */ |
| 133 | 162 | const char *zBranch /* Branch for this check-in */ |
| 134 | 163 | ){ |
| 135 | 164 | GraphRow *pRow; |
| 136 | 165 | |
| 137 | | - if( p->nErr ) return; |
| 138 | | - if( nParent>GR_MAX_PARENT ){ p->nErr++; return; } |
| 166 | + if( p->nErr ) return 0; |
| 167 | + if( nParent>GR_MAX_PARENT ){ p->nErr++; return 0; } |
| 139 | 168 | pRow = (GraphRow*)safeMalloc( sizeof(GraphRow) ); |
| 140 | 169 | pRow->rid = rid; |
| 141 | | - pRow->isLeaf = isLeaf; |
| 142 | 170 | pRow->nParent = nParent; |
| 143 | 171 | pRow->zBranch = persistBranchName(p, zBranch); |
| 144 | 172 | memcpy(pRow->aParent, aParent, sizeof(aParent[0])*nParent); |
| 145 | 173 | if( p->pFirst==0 ){ |
| 146 | 174 | p->pFirst = pRow; |
| 147 | 175 | }else{ |
| 148 | 176 | p->pLast->pNext = pRow; |
| 149 | 177 | } |
| 150 | 178 | p->pLast = pRow; |
| 179 | + p->nRow++; |
| 180 | + pRow->idx = p->nRow; |
| 181 | + return pRow->idx; |
| 151 | 182 | } |
| 152 | 183 | |
| 153 | 184 | /* |
| 154 | 185 | ** Return the index of a rail currently not in use for any row between |
| 155 | 186 | ** top and bottom, inclusive. |
| | @@ -188,51 +219,59 @@ |
| 188 | 219 | /* |
| 189 | 220 | ** Compute the complete graph |
| 190 | 221 | */ |
| 191 | 222 | void graph_finish(GraphContext *p, int omitDescenders){ |
| 192 | 223 | GraphRow *pRow, *pDesc; |
| 193 | | - Bag allRids; |
| 194 | | - Bag notLeaf; |
| 195 | 224 | int i; |
| 196 | | - int nRow; |
| 197 | 225 | u32 mask; |
| 198 | 226 | u32 inUse; |
| 199 | 227 | |
| 200 | 228 | if( p==0 || p->pFirst==0 || p->nErr ) return; |
| 201 | 229 | |
| 202 | 230 | /* Initialize all rows */ |
| 203 | | - bag_init(&allRids); |
| 204 | | - bag_init(¬Leaf); |
| 205 | | - nRow = 0; |
| 231 | + p->nHash = p->nRow*2 + 1; |
| 232 | + p->apHash = safeMalloc( sizeof(p->apHash[0])*p->nHash ); |
| 206 | 233 | for(pRow=p->pFirst; pRow; pRow=pRow->pNext){ |
| 207 | 234 | if( pRow->pNext ) pRow->pNext->pPrev = pRow; |
| 208 | | - pRow->idx = ++nRow; |
| 209 | 235 | pRow->iRail = -1; |
| 210 | 236 | pRow->mergeOut = -1; |
| 211 | | - bag_insert(&allRids, pRow->rid); |
| 237 | + hashInsert(p, pRow); |
| 212 | 238 | } |
| 213 | 239 | p->mxRail = -1; |
| 214 | 240 | |
| 215 | 241 | /* Purge merge-parents that are out-of-graph |
| 216 | 242 | */ |
| 217 | 243 | for(pRow=p->pFirst; pRow; pRow=pRow->pNext){ |
| 218 | 244 | for(i=1; i<pRow->nParent; i++){ |
| 219 | | - if( !bag_find(&allRids, pRow->aParent[i]) ){ |
| 245 | + if( hashFind(p, pRow->aParent[i])==0 ){ |
| 220 | 246 | pRow->aParent[i] = pRow->aParent[--pRow->nParent]; |
| 221 | 247 | i--; |
| 222 | 248 | } |
| 223 | 249 | } |
| 224 | | - if( pRow->nParent>0 && bag_find(&allRids, pRow->aParent[0]) ){ |
| 225 | | - bag_insert(¬Leaf, pRow->aParent[0]); |
| 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; |
| 226 | 265 | } |
| 227 | 266 | } |
| 228 | 267 | |
| 229 | 268 | /* Identify rows where the primary parent is off screen. Assign |
| 230 | 269 | ** each to a rail and draw descenders to the bottom of the screen. |
| 231 | 270 | */ |
| 232 | 271 | for(pRow=p->pFirst; pRow; pRow=pRow->pNext){ |
| 233 | | - if( pRow->nParent==0 || !bag_find(&allRids,pRow->aParent[0]) ){ |
| 272 | + if( pRow->nParent==0 || hashFind(p,pRow->aParent[0])==0 ){ |
| 234 | 273 | if( omitDescenders ){ |
| 235 | 274 | pRow->iRail = findFreeRail(p, pRow->idx, pRow->idx, 0, 0); |
| 236 | 275 | }else{ |
| 237 | 276 | pRow->iRail = ++p->mxRail; |
| 238 | 277 | } |
| | @@ -257,11 +296,10 @@ |
| 257 | 296 | for(pRow=p->pLast; pRow; pRow=pRow->pPrev){ |
| 258 | 297 | int parentRid; |
| 259 | 298 | if( pRow->iRail>=0 ) continue; |
| 260 | 299 | assert( pRow->nParent>0 ); |
| 261 | 300 | parentRid = pRow->aParent[0]; |
| 262 | | - assert( bag_find(&allRids, parentRid) ); |
| 263 | 301 | for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid; pDesc=pDesc->pNext){} |
| 264 | 302 | if( pDesc==0 ){ |
| 265 | 303 | /* Time skew */ |
| 266 | 304 | pRow->iRail = ++p->mxRail; |
| 267 | 305 | pRow->railInUse = 1<<pRow->iRail; |
| | @@ -272,14 +310,14 @@ |
| 272 | 310 | }else{ |
| 273 | 311 | pRow->iRail = findFreeRail(p, 0, pDesc->idx, inUse, 0); |
| 274 | 312 | } |
| 275 | 313 | pDesc->aiRaiser[pRow->iRail] = pRow->idx; |
| 276 | 314 | mask = 1<<pRow->iRail; |
| 277 | | - if( bag_find(¬Leaf, pRow->rid) ){ |
| 278 | | - inUse |= mask; |
| 315 | + if( pRow->isLeaf ){ |
| 316 | + inUse &= ~mask; |
| 279 | 317 | }else{ |
| 280 | | - inUse &= ~mask; |
| 318 | + inUse |= mask; |
| 281 | 319 | } |
| 282 | 320 | for(pDesc = pRow; ; pDesc=pDesc->pNext){ |
| 283 | 321 | assert( pDesc!=0 ); |
| 284 | 322 | pDesc->railInUse |= mask; |
| 285 | 323 | if( pDesc->rid==parentRid ) break; |
| | @@ -309,29 +347,14 @@ |
| 309 | 347 | pRow->mergeIn |= 1<<pDesc->mergeOut; |
| 310 | 348 | } |
| 311 | 349 | } |
| 312 | 350 | |
| 313 | 351 | /* |
| 314 | | - ** Sort the rail numbers |
| 352 | + ** Find the maximum rail number. |
| 315 | 353 | */ |
| 316 | | -#if 0 |
| 317 | | - p->mxRail = -1; |
| 318 | | - mask = 0; |
| 319 | | - for(pRow=p->pLast; pRow; pRow=pRow->pPrev){ |
| 320 | | - if( (mask & (1<<pRow->iRail))==0 ){ |
| 321 | | - p->railMap[pRow->iRail] = ++p->mxRail; |
| 322 | | - mask |= 1<<pRow->iRail; |
| 323 | | - } |
| 324 | | - if( pRow->mergeOut>=0 && (mask & (1<<pRow->mergeOut))==0 ){ |
| 325 | | - p->railMap[pRow->mergeOut] = ++p->mxRail; |
| 326 | | - mask |= 1<<pRow->mergeOut; |
| 327 | | - } |
| 328 | | - } |
| 329 | | -#else |
| 330 | 354 | for(i=0; i<GR_MAX_RAIL; i++) p->railMap[i] = i; |
| 331 | 355 | p->mxRail = 0; |
| 332 | 356 | for(pRow=p->pFirst; pRow; pRow=pRow->pNext){ |
| 333 | 357 | if( pRow->iRail>p->mxRail ) p->mxRail = pRow->iRail; |
| 334 | 358 | if( pRow->mergeOut>p->mxRail ) p->mxRail = pRow->mergeOut; |
| 335 | 359 | } |
| 336 | | -#endif |
| 337 | 360 | } |
| 338 | 361 | |