Fossil SCM

Reimplement path_shortest() using the new PQueue with pointer content.

drh 2025-03-08 18:44 min-from-to
Commit 14372167c9c34054ead1df81b47f38d2c5a163b94ead6c422daf34ba17f7755a
Parent 4111717eae6f26d…
3 files changed +18 -3 +82 -90 +4 -7
~ src/descendants.c ~ src/path.c ~ src/timeline.c
M src/descendants.c
+18 -3
--- src/descendants.c
+++ src/descendants.c
@@ -156,10 +156,27 @@
156156
 " AND tagxref.tagtype>0)",
157157
 TAG_CLOSED
158158
 );
159159
 }
160160
 }
161
+
162
+/*
163
+** If RID refers to a check-in, return the mtime of that check-in - the
164
+** julian day number of when the check-in occurred.
165
+*/
166
+double mtime_of_rid(int rid, double mtime){
167
+ static Stmt q;
168
+ db_static_prepare(&q,"SELECT mtime FROM event WHERE objid=:rid");
169
+ db_bind_int(&q, ":rid", rid);
170
+ if( db_step(&q)==SQLITE_ROW ){
171
+ mtime = db_column_double(&q,0);
172
+ }
173
+ db_reset(&q);
174
+ return mtime;
175
+}
176
+
177
+
161178
162179
 /*
163180
 ** Load the record ID rid and up to |N|-1 closest ancestors into
164181
 ** the "ok" table. If N is zero, no limit. If ridBackTo is not zero
165182
 ** then stop the search upon reaching the ancestor with rid==ridBackTo.
@@ -197,13 +214,11 @@
197214
 ** (3) Cherrypick merge parents.
198215
 ** (4) All ancestores of 1 and 2 but not of 3.
199216
 */
200217
 double rLimitMtime = 0.0;
201218
 if( ridBackTo ){
202
- rLimitMtime = db_double(0.0,
203
- "SELECT mtime FROM event WHERE objid=%d",
204
- ridBackTo);
219
+ rLimitMtime = mtime_of_rid(ridBackTo, 0.0);
205220
 }
206221
 db_multi_exec(
207222
 "WITH RECURSIVE\n"
208223
 " parent(pid,cid,isCP) AS (\n"
209224
 " SELECT plink.pid, plink.cid, 0 AS xisCP FROM plink\n"
210225
--- src/descendants.c
+++ src/descendants.c
@@ -156,10 +156,27 @@
156 " AND tagxref.tagtype>0)",
157 TAG_CLOSED
158 );
159 }
160 }
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
161
162 /*
163 ** Load the record ID rid and up to |N|-1 closest ancestors into
164 ** the "ok" table. If N is zero, no limit. If ridBackTo is not zero
165 ** then stop the search upon reaching the ancestor with rid==ridBackTo.
@@ -197,13 +214,11 @@
197 ** (3) Cherrypick merge parents.
198 ** (4) All ancestores of 1 and 2 but not of 3.
199 */
200 double rLimitMtime = 0.0;
201 if( ridBackTo ){
202 rLimitMtime = db_double(0.0,
203 "SELECT mtime FROM event WHERE objid=%d",
204 ridBackTo);
205 }
206 db_multi_exec(
207 "WITH RECURSIVE\n"
208 " parent(pid,cid,isCP) AS (\n"
209 " SELECT plink.pid, plink.cid, 0 AS xisCP FROM plink\n"
210
--- src/descendants.c
+++ src/descendants.c
@@ -156,10 +156,27 @@
156 " AND tagxref.tagtype>0)",
157 TAG_CLOSED
158 );
159 }
160 }
161
162 /*
163 ** If RID refers to a check-in, return the mtime of that check-in - the
164 ** julian day number of when the check-in occurred.
165 */
166 double mtime_of_rid(int rid, double mtime){
167 static Stmt q;
168 db_static_prepare(&q,"SELECT mtime FROM event WHERE objid=:rid");
169 db_bind_int(&q, ":rid", rid);
170 if( db_step(&q)==SQLITE_ROW ){
171 mtime = db_column_double(&q,0);
172 }
173 db_reset(&q);
174 return mtime;
175 }
176
177
178
179 /*
180 ** Load the record ID rid and up to |N|-1 closest ancestors into
181 ** the "ok" table. If N is zero, no limit. If ridBackTo is not zero
182 ** then stop the search upon reaching the ancestor with rid==ridBackTo.
@@ -197,13 +214,11 @@
214 ** (3) Cherrypick merge parents.
215 ** (4) All ancestores of 1 and 2 but not of 3.
216 */
217 double rLimitMtime = 0.0;
218 if( ridBackTo ){
219 rLimitMtime = mtime_of_rid(ridBackTo, 0.0);
 
 
220 }
221 db_multi_exec(
222 "WITH RECURSIVE\n"
223 " parent(pid,cid,isCP) AS (\n"
224 " SELECT plink.pid, plink.cid, 0 AS xisCP FROM plink\n"
225
M src/path.c
+82 -90
--- src/path.c
+++ src/path.c
@@ -18,40 +18,41 @@
1818
 ** directed acyclic graph (DAG) of check-ins.
1919
 */
2020
 #include "config.h"
2121
 #include "path.h"
2222
 #include <assert.h>
23
+#include <math.h>
2324
2425
 #if INTERFACE
2526
 /* Nodes for the paths through the DAG.
2627
 */
2728
 struct PathNode {
2829
 int rid; /* ID for this node */
2930
 u8 fromIsParent; /* True if pFrom is the parent of rid */
3031
 u8 isPrim; /* True if primary side of common ancestor */
3132
 u8 isHidden; /* Abbreviate output in "fossil bisect ls" */
32
- u8 nDelay; /* Delay this many steps before walking */
3333
 char *zBranch; /* Branch name for this node. Might be NULL */
34
+ double mtime; /* Date/time of this check-in */
3435
 PathNode *pFrom; /* Node we came from */
3536
 union {
36
- PathNode *pPeer; /* List of nodes of the same generation */
37
+ double rCost; /* Cost of getting to this node from pStart */
3738
 PathNode *pTo; /* Next on path from beginning to end */
3839
 } u;
39
- PathNode *pAll; /* List of all nodes */
40
+ PathNode *pAll; /* List of all nodes */
4041
 };
4142
 #endif
4243
4344
 /*
4445
 ** Local variables for this module
4546
 */
4647
 static struct {
47
- PathNode *pCurrent; /* Current generation of nodes */
48
+ PQueue pending; /* Nodes pending review for inclusion in the graph */
4849
 PathNode *pAll; /* All nodes */
49
- Bag seen; /* Nodes seen before */
5050
 int nStep; /* Number of steps from first to last */
5151
 int nNotHidden; /* Number of steps not counting hidden nodes */
52
- u8 brCost; /* Extra cost for moving to a different branch */
52
+ int brCost; /* Extra cost for moving to a different branch */
53
+ int revCost; /* Extra cost for changing directions */
5354
 PathNode *pStart; /* Earliest node */
5455
 PathNode *pEnd; /* Most recent */
5556
 } path;
5657
5758
 /*
@@ -69,31 +70,40 @@
6970
 ** Return the number of non-hidden steps in the computed path.
7071
 */
7172
 int path_length_not_hidden(void){ return path.nNotHidden; }
7273
7374
 /*
74
-** Create a new node
75
+** Create a new node and insert it into the path.pending queue.
7576
 */
7677
 static PathNode *path_new_node(int rid, PathNode *pFrom, int isParent){
7778
 PathNode *p;
7879
7980
 p = fossil_malloc( sizeof(*p) );
8081
 memset(p, 0, sizeof(*p));
82
+ p->pAll = path.pAll;
83
+ path.pAll = p;
8184
 p->rid = rid;
8285
 p->fromIsParent = isParent;
8386
 p->pFrom = pFrom;
87
+ p->u.rCost = pFrom ? pFrom->u.rCost : 0.0;
8488
 if( path.brCost ){
8589
 p->zBranch = branch_of_rid(rid);
86
- if( pFrom && fossil_strcmp(p->zBranch, pFrom->zBranch)!=0 ){
87
- p->nDelay = path.brCost;
88
- }
89
- }
90
- p->u.pPeer = path.pCurrent;
91
- path.pCurrent = p;
92
- p->pAll = path.pAll;
93
- path.pAll = p;
94
- bag_insert(&path.seen, rid);
90
+ p->mtime = mtime_of_rid(rid, 0.0);
91
+ if( pFrom ){
92
+ p->u.rCost += fabs(pFrom->mtime - p->mtime);
93
+ if( fossil_strcmp(p->zBranch, pFrom->zBranch)!=0 ){
94
+ p->u.rCost += path.brCost;
95
+ }
96
+ }
97
+ }else{
98
+ /* When brCost==0, we try to minimize the number of nodes
99
+ ** along the path. The cost is just the number of nodes back
100
+ ** to the start. We do not need to know the branch name nor
101
+ ** the mtime */
102
+ p->u.rCost += 1.0;
103
+ }
104
+ pqueuex_insert_ptr(&path.pending, (void*)p, p->u.rCost);
95105
 return p;
96106
 }
97107
98108
 /*
99109
 ** Reset memory used by the shortest path algorithm.
@@ -104,11 +114,11 @@
104114
 p = path.pAll;
105115
 path.pAll = p->pAll;
106116
 fossil_free(p->zBranch);
107117
 fossil_free(p);
108118
 }
109
- bag_clear(&path.seen);
119
+ pqueuex_clear(&path.pending);
110120
 memset(&path, 0, sizeof(path));
111121
 }
112122
113123
 /*
114124
 ** Construct the path from path.pStart to path.pEnd in the u.pTo fields.
@@ -142,13 +152,12 @@
142152
 int oneWayOnly, /* Parent->child only if true */
143153
 Bag *pHidden, /* Hidden nodes */
144154
 int branchCost /* Add extra codes to changing branches */
145155
 ){
146156
 Stmt s;
147
- PathNode *pPrev;
157
+ Bag seen;
148158
 PathNode *p;
149
- int nPriorPeer = 1;
150159
151160
 path_reset();
152161
 path.brCost = branchCost;
153162
 path.pStart = path_new_node(iFrom, 0, 0);
154163
 if( iTo==iFrom ){
@@ -174,45 +183,33 @@
174183
 "SELECT cid, 1 FROM plink WHERE pid=:pid "
175184
 "UNION ALL "
176185
 "SELECT pid, 0 FROM plink WHERE cid=:pid"
177186
 );
178187
 }
179
- while( path.pCurrent ){
180
- if( nPriorPeer ) path.nStep++;
181
- nPriorPeer = 0;
182
- pPrev = path.pCurrent;
183
- path.pCurrent = 0;
184
- while( pPrev ){
185
- if( pPrev->nDelay>0 && (nPriorPeer>0 || pPrev->u.pPeer!=0) ){
186
- PathNode *pThis = pPrev;
187
- pPrev = pThis->u.pPeer;
188
- pThis->u.pPeer = path.pCurrent;
189
- path.pCurrent = pThis;
190
- pThis->nDelay--;
191
- continue;
192
- }
193
- nPriorPeer++;
194
- db_bind_int(&s, ":pid", pPrev->rid);
195
- while( db_step(&s)==SQLITE_ROW ){
196
- int cid = db_column_int(&s, 0);
197
- int isParent = db_column_int(&s, 1);
198
- if( bag_find(&path.seen, cid) ) continue;
199
- p = path_new_node(cid, pPrev, isParent);
200
- if( pHidden && bag_find(pHidden,cid) ) p->isHidden = 1;
201
- if( cid==iTo ){
202
- db_finalize(&s);
203
- path.pEnd = p;
204
- path_reverse_path();
205
- for(p=path.pStart->u.pTo; p; p=p->u.pTo ){
206
- if( !p->isHidden ) path.nNotHidden++;
207
- }
208
- return path.pStart;
209
- }
210
- }
211
- db_reset(&s);
212
- pPrev = pPrev->u.pPeer;
213
- }
188
+ bag_init(&seen);
189
+ while( (p = pqueuex_extract_ptr(&path.pending))!=0 ){
190
+ if( p->rid==iTo ){
191
+ db_finalize(&s);
192
+ path.pEnd = p;
193
+ path_reverse_path();
194
+ for(p=path.pStart->u.pTo; p; p=p->u.pTo ){
195
+ if( !p->isHidden ) path.nNotHidden++;
196
+ }
197
+ return path.pStart;
198
+ }
199
+ if( bag_find(&seen, p->rid) ) continue;
200
+ bag_insert(&seen, p->rid);
201
+ db_bind_int(&s, ":pid", p->rid);
202
+ while( db_step(&s)==SQLITE_ROW ){
203
+ int cid = db_column_int(&s, 0);
204
+ int isParent = db_column_int(&s, 1);
205
+ PathNode *pNew;
206
+ if( bag_find(&seen, cid) ) continue;
207
+ pNew = path_new_node(cid, p, isParent);
208
+ if( pHidden && bag_find(pHidden,cid) ) pNew->isHidden = 1;
209
+ }
210
+ db_reset(&s);
214211
 }
215212
 db_finalize(&s);
216213
 path_reset();
217214
 return 0;
218215
 }
@@ -333,11 +330,11 @@
333330
 ** Find the closest common ancestor of two nodes. "Closest" means the
334331
 ** fewest number of arcs.
335332
 */
336333
 int path_common_ancestor(int iMe, int iYou){
337334
 Stmt s;
338
- PathNode *pPrev;
335
+ PathNode *pThis;
339336
 PathNode *p;
340337
 Bag me, you;
341338
342339
 if( iMe==iYou ) return iMe;
343340
 if( iMe==0 || iYou==0 ) return 0;
@@ -348,45 +345,40 @@
348345
 db_prepare(&s, "SELECT pid FROM plink WHERE cid=:cid");
349346
 bag_init(&me);
350347
 bag_insert(&me, iMe);
351348
 bag_init(&you);
352349
 bag_insert(&you, iYou);
353
- while( path.pCurrent ){
354
- pPrev = path.pCurrent;
355
- path.pCurrent = 0;
356
- while( pPrev ){
357
- db_bind_int(&s, ":cid", pPrev->rid);
358
- while( db_step(&s)==SQLITE_ROW ){
359
- int pid = db_column_int(&s, 0);
360
- if( bag_find(pPrev->isPrim ? &you : &me, pid) ){
361
- /* pid is the common ancestor */
362
- PathNode *pNext;
363
- for(p=path.pAll; p && p->rid!=pid; p=p->pAll){}
364
- assert( p!=0 );
365
- pNext = p;
366
- while( pNext ){
367
- pNext = p->pFrom;
368
- p->pFrom = pPrev;
369
- pPrev = p;
370
- p = pNext;
371
- }
372
- if( pPrev==path.pStart ) path.pStart = path.pEnd;
373
- path.pEnd = pPrev;
374
- path_reverse_path();
375
- db_finalize(&s);
376
- return pid;
377
- }else if( bag_find(&path.seen, pid) ){
378
- /* pid is just an alternative path on one of the legs */
379
- continue;
380
- }
381
- p = path_new_node(pid, pPrev, 0);
382
- p->isPrim = pPrev->isPrim;
383
- bag_insert(pPrev->isPrim ? &me : &you, pid);
384
- }
385
- db_reset(&s);
386
- pPrev = pPrev->u.pPeer;
387
- }
350
+ while( (pThis = pqueuex_extract_ptr(&path.pending))!=0 ){
351
+ db_bind_int(&s, ":cid", pThis->rid);
352
+ while( db_step(&s)==SQLITE_ROW ){
353
+ int pid = db_column_int(&s, 0);
354
+ if( bag_find(pThis->isPrim ? &you : &me, pid) ){
355
+ /* pid is the common ancestor */
356
+ PathNode *pNext;
357
+ for(p=path.pAll; p && p->rid!=pid; p=p->pAll){}
358
+ assert( p!=0 );
359
+ pNext = p;
360
+ while( pNext ){
361
+ pNext = p->pFrom;
362
+ p->pFrom = pThis;
363
+ pThis = p;
364
+ p = pNext;
365
+ }
366
+ if( pThis==path.pStart ) path.pStart = path.pEnd;
367
+ path.pEnd = pThis;
368
+ path_reverse_path();
369
+ db_finalize(&s);
370
+ return pid;
371
+ }else if( bag_find(pThis->isPrim ? &me : &you, pid) ){
372
+ /* pid is just an alternative path to a node we've already visited */
373
+ continue;
374
+ }
375
+ p = path_new_node(pid, pThis, 0);
376
+ p->isPrim = pThis->isPrim;
377
+ bag_insert(pThis->isPrim ? &me : &you, pid);
378
+ }
379
+ db_reset(&s);
388380
 }
389381
 db_finalize(&s);
390382
 path_reset();
391383
 return 0;
392384
 }
393385
--- src/path.c
+++ src/path.c
@@ -18,40 +18,41 @@
18 ** directed acyclic graph (DAG) of check-ins.
19 */
20 #include "config.h"
21 #include "path.h"
22 #include <assert.h>
 
23
24 #if INTERFACE
25 /* Nodes for the paths through the DAG.
26 */
27 struct PathNode {
28 int rid; /* ID for this node */
29 u8 fromIsParent; /* True if pFrom is the parent of rid */
30 u8 isPrim; /* True if primary side of common ancestor */
31 u8 isHidden; /* Abbreviate output in "fossil bisect ls" */
32 u8 nDelay; /* Delay this many steps before walking */
33 char *zBranch; /* Branch name for this node. Might be NULL */
 
34 PathNode *pFrom; /* Node we came from */
35 union {
36 PathNode *pPeer; /* List of nodes of the same generation */
37 PathNode *pTo; /* Next on path from beginning to end */
38 } u;
39 PathNode *pAll; /* List of all nodes */
40 };
41 #endif
42
43 /*
44 ** Local variables for this module
45 */
46 static struct {
47 PathNode *pCurrent; /* Current generation of nodes */
48 PathNode *pAll; /* All nodes */
49 Bag seen; /* Nodes seen before */
50 int nStep; /* Number of steps from first to last */
51 int nNotHidden; /* Number of steps not counting hidden nodes */
52 u8 brCost; /* Extra cost for moving to a different branch */
 
53 PathNode *pStart; /* Earliest node */
54 PathNode *pEnd; /* Most recent */
55 } path;
56
57 /*
@@ -69,31 +70,40 @@
69 ** Return the number of non-hidden steps in the computed path.
70 */
71 int path_length_not_hidden(void){ return path.nNotHidden; }
72
73 /*
74 ** Create a new node
75 */
76 static PathNode *path_new_node(int rid, PathNode *pFrom, int isParent){
77 PathNode *p;
78
79 p = fossil_malloc( sizeof(*p) );
80 memset(p, 0, sizeof(*p));
 
 
81 p->rid = rid;
82 p->fromIsParent = isParent;
83 p->pFrom = pFrom;
 
84 if( path.brCost ){
85 p->zBranch = branch_of_rid(rid);
86 if( pFrom && fossil_strcmp(p->zBranch, pFrom->zBranch)!=0 ){
87 p->nDelay = path.brCost;
88 }
89 }
90 p->u.pPeer = path.pCurrent;
91 path.pCurrent = p;
92 p->pAll = path.pAll;
93 path.pAll = p;
94 bag_insert(&path.seen, rid);
 
 
 
 
 
 
95 return p;
96 }
97
98 /*
99 ** Reset memory used by the shortest path algorithm.
@@ -104,11 +114,11 @@
104 p = path.pAll;
105 path.pAll = p->pAll;
106 fossil_free(p->zBranch);
107 fossil_free(p);
108 }
109 bag_clear(&path.seen);
110 memset(&path, 0, sizeof(path));
111 }
112
113 /*
114 ** Construct the path from path.pStart to path.pEnd in the u.pTo fields.
@@ -142,13 +152,12 @@
142 int oneWayOnly, /* Parent->child only if true */
143 Bag *pHidden, /* Hidden nodes */
144 int branchCost /* Add extra codes to changing branches */
145 ){
146 Stmt s;
147 PathNode *pPrev;
148 PathNode *p;
149 int nPriorPeer = 1;
150
151 path_reset();
152 path.brCost = branchCost;
153 path.pStart = path_new_node(iFrom, 0, 0);
154 if( iTo==iFrom ){
@@ -174,45 +183,33 @@
174 "SELECT cid, 1 FROM plink WHERE pid=:pid "
175 "UNION ALL "
176 "SELECT pid, 0 FROM plink WHERE cid=:pid"
177 );
178 }
179 while( path.pCurrent ){
180 if( nPriorPeer ) path.nStep++;
181 nPriorPeer = 0;
182 pPrev = path.pCurrent;
183 path.pCurrent = 0;
184 while( pPrev ){
185 if( pPrev->nDelay>0 && (nPriorPeer>0 || pPrev->u.pPeer!=0) ){
186 PathNode *pThis = pPrev;
187 pPrev = pThis->u.pPeer;
188 pThis->u.pPeer = path.pCurrent;
189 path.pCurrent = pThis;
190 pThis->nDelay--;
191 continue;
192 }
193 nPriorPeer++;
194 db_bind_int(&s, ":pid", pPrev->rid);
195 while( db_step(&s)==SQLITE_ROW ){
196 int cid = db_column_int(&s, 0);
197 int isParent = db_column_int(&s, 1);
198 if( bag_find(&path.seen, cid) ) continue;
199 p = path_new_node(cid, pPrev, isParent);
200 if( pHidden && bag_find(pHidden,cid) ) p->isHidden = 1;
201 if( cid==iTo ){
202 db_finalize(&s);
203 path.pEnd = p;
204 path_reverse_path();
205 for(p=path.pStart->u.pTo; p; p=p->u.pTo ){
206 if( !p->isHidden ) path.nNotHidden++;
207 }
208 return path.pStart;
209 }
210 }
211 db_reset(&s);
212 pPrev = pPrev->u.pPeer;
213 }
214 }
215 db_finalize(&s);
216 path_reset();
217 return 0;
218 }
@@ -333,11 +330,11 @@
333 ** Find the closest common ancestor of two nodes. "Closest" means the
334 ** fewest number of arcs.
335 */
336 int path_common_ancestor(int iMe, int iYou){
337 Stmt s;
338 PathNode *pPrev;
339 PathNode *p;
340 Bag me, you;
341
342 if( iMe==iYou ) return iMe;
343 if( iMe==0 || iYou==0 ) return 0;
@@ -348,45 +345,40 @@
348 db_prepare(&s, "SELECT pid FROM plink WHERE cid=:cid");
349 bag_init(&me);
350 bag_insert(&me, iMe);
351 bag_init(&you);
352 bag_insert(&you, iYou);
353 while( path.pCurrent ){
354 pPrev = path.pCurrent;
355 path.pCurrent = 0;
356 while( pPrev ){
357 db_bind_int(&s, ":cid", pPrev->rid);
358 while( db_step(&s)==SQLITE_ROW ){
359 int pid = db_column_int(&s, 0);
360 if( bag_find(pPrev->isPrim ? &you : &me, pid) ){
361 /* pid is the common ancestor */
362 PathNode *pNext;
363 for(p=path.pAll; p && p->rid!=pid; p=p->pAll){}
364 assert( p!=0 );
365 pNext = p;
366 while( pNext ){
367 pNext = p->pFrom;
368 p->pFrom = pPrev;
369 pPrev = p;
370 p = pNext;
371 }
372 if( pPrev==path.pStart ) path.pStart = path.pEnd;
373 path.pEnd = pPrev;
374 path_reverse_path();
375 db_finalize(&s);
376 return pid;
377 }else if( bag_find(&path.seen, pid) ){
378 /* pid is just an alternative path on one of the legs */
379 continue;
380 }
381 p = path_new_node(pid, pPrev, 0);
382 p->isPrim = pPrev->isPrim;
383 bag_insert(pPrev->isPrim ? &me : &you, pid);
384 }
385 db_reset(&s);
386 pPrev = pPrev->u.pPeer;
387 }
388 }
389 db_finalize(&s);
390 path_reset();
391 return 0;
392 }
393
--- src/path.c
+++ src/path.c
@@ -18,40 +18,41 @@
18 ** directed acyclic graph (DAG) of check-ins.
19 */
20 #include "config.h"
21 #include "path.h"
22 #include <assert.h>
23 #include <math.h>
24
25 #if INTERFACE
26 /* Nodes for the paths through the DAG.
27 */
28 struct PathNode {
29 int rid; /* ID for this node */
30 u8 fromIsParent; /* True if pFrom is the parent of rid */
31 u8 isPrim; /* True if primary side of common ancestor */
32 u8 isHidden; /* Abbreviate output in "fossil bisect ls" */
 
33 char *zBranch; /* Branch name for this node. Might be NULL */
34 double mtime; /* Date/time of this check-in */
35 PathNode *pFrom; /* Node we came from */
36 union {
37 double rCost; /* Cost of getting to this node from pStart */
38 PathNode *pTo; /* Next on path from beginning to end */
39 } u;
40 PathNode *pAll; /* List of all nodes */
41 };
42 #endif
43
44 /*
45 ** Local variables for this module
46 */
47 static struct {
48 PQueue pending; /* Nodes pending review for inclusion in the graph */
49 PathNode *pAll; /* All nodes */
 
50 int nStep; /* Number of steps from first to last */
51 int nNotHidden; /* Number of steps not counting hidden nodes */
52 int brCost; /* Extra cost for moving to a different branch */
53 int revCost; /* Extra cost for changing directions */
54 PathNode *pStart; /* Earliest node */
55 PathNode *pEnd; /* Most recent */
56 } path;
57
58 /*
@@ -69,31 +70,40 @@
70 ** Return the number of non-hidden steps in the computed path.
71 */
72 int path_length_not_hidden(void){ return path.nNotHidden; }
73
74 /*
75 ** Create a new node and insert it into the path.pending queue.
76 */
77 static PathNode *path_new_node(int rid, PathNode *pFrom, int isParent){
78 PathNode *p;
79
80 p = fossil_malloc( sizeof(*p) );
81 memset(p, 0, sizeof(*p));
82 p->pAll = path.pAll;
83 path.pAll = p;
84 p->rid = rid;
85 p->fromIsParent = isParent;
86 p->pFrom = pFrom;
87 p->u.rCost = pFrom ? pFrom->u.rCost : 0.0;
88 if( path.brCost ){
89 p->zBranch = branch_of_rid(rid);
90 p->mtime = mtime_of_rid(rid, 0.0);
91 if( pFrom ){
92 p->u.rCost += fabs(pFrom->mtime - p->mtime);
93 if( fossil_strcmp(p->zBranch, pFrom->zBranch)!=0 ){
94 p->u.rCost += path.brCost;
95 }
96 }
97 }else{
98 /* When brCost==0, we try to minimize the number of nodes
99 ** along the path. The cost is just the number of nodes back
100 ** to the start. We do not need to know the branch name nor
101 ** the mtime */
102 p->u.rCost += 1.0;
103 }
104 pqueuex_insert_ptr(&path.pending, (void*)p, p->u.rCost);
105 return p;
106 }
107
108 /*
109 ** Reset memory used by the shortest path algorithm.
@@ -104,11 +114,11 @@
114 p = path.pAll;
115 path.pAll = p->pAll;
116 fossil_free(p->zBranch);
117 fossil_free(p);
118 }
119 pqueuex_clear(&path.pending);
120 memset(&path, 0, sizeof(path));
121 }
122
123 /*
124 ** Construct the path from path.pStart to path.pEnd in the u.pTo fields.
@@ -142,13 +152,12 @@
152 int oneWayOnly, /* Parent->child only if true */
153 Bag *pHidden, /* Hidden nodes */
154 int branchCost /* Add extra codes to changing branches */
155 ){
156 Stmt s;
157 Bag seen;
158 PathNode *p;
 
159
160 path_reset();
161 path.brCost = branchCost;
162 path.pStart = path_new_node(iFrom, 0, 0);
163 if( iTo==iFrom ){
@@ -174,45 +183,33 @@
183 "SELECT cid, 1 FROM plink WHERE pid=:pid "
184 "UNION ALL "
185 "SELECT pid, 0 FROM plink WHERE cid=:pid"
186 );
187 }
188 bag_init(&seen);
189 while( (p = pqueuex_extract_ptr(&path.pending))!=0 ){
190 if( p->rid==iTo ){
191 db_finalize(&s);
192 path.pEnd = p;
193 path_reverse_path();
194 for(p=path.pStart->u.pTo; p; p=p->u.pTo ){
195 if( !p->isHidden ) path.nNotHidden++;
196 }
197 return path.pStart;
198 }
199 if( bag_find(&seen, p->rid) ) continue;
200 bag_insert(&seen, p->rid);
201 db_bind_int(&s, ":pid", p->rid);
202 while( db_step(&s)==SQLITE_ROW ){
203 int cid = db_column_int(&s, 0);
204 int isParent = db_column_int(&s, 1);
205 PathNode *pNew;
206 if( bag_find(&seen, cid) ) continue;
207 pNew = path_new_node(cid, p, isParent);
208 if( pHidden && bag_find(pHidden,cid) ) pNew->isHidden = 1;
209 }
210 db_reset(&s);
 
 
 
 
 
 
 
 
 
 
 
 
211 }
212 db_finalize(&s);
213 path_reset();
214 return 0;
215 }
@@ -333,11 +330,11 @@
330 ** Find the closest common ancestor of two nodes. "Closest" means the
331 ** fewest number of arcs.
332 */
333 int path_common_ancestor(int iMe, int iYou){
334 Stmt s;
335 PathNode *pThis;
336 PathNode *p;
337 Bag me, you;
338
339 if( iMe==iYou ) return iMe;
340 if( iMe==0 || iYou==0 ) return 0;
@@ -348,45 +345,40 @@
345 db_prepare(&s, "SELECT pid FROM plink WHERE cid=:cid");
346 bag_init(&me);
347 bag_insert(&me, iMe);
348 bag_init(&you);
349 bag_insert(&you, iYou);
350 while( (pThis = pqueuex_extract_ptr(&path.pending))!=0 ){
351 db_bind_int(&s, ":cid", pThis->rid);
352 while( db_step(&s)==SQLITE_ROW ){
353 int pid = db_column_int(&s, 0);
354 if( bag_find(pThis->isPrim ? &you : &me, pid) ){
355 /* pid is the common ancestor */
356 PathNode *pNext;
357 for(p=path.pAll; p && p->rid!=pid; p=p->pAll){}
358 assert( p!=0 );
359 pNext = p;
360 while( pNext ){
361 pNext = p->pFrom;
362 p->pFrom = pThis;
363 pThis = p;
364 p = pNext;
365 }
366 if( pThis==path.pStart ) path.pStart = path.pEnd;
367 path.pEnd = pThis;
368 path_reverse_path();
369 db_finalize(&s);
370 return pid;
371 }else if( bag_find(pThis->isPrim ? &me : &you, pid) ){
372 /* pid is just an alternative path to a node we've already visited */
373 continue;
374 }
375 p = path_new_node(pid, pThis, 0);
376 p->isPrim = pThis->isPrim;
377 bag_insert(pThis->isPrim ? &me : &you, pid);
378 }
379 db_reset(&s);
 
 
 
 
 
380 }
381 db_finalize(&s);
382 path_reset();
383 return 0;
384 }
385
M src/timeline.c
+4 -7
--- src/timeline.c
+++ src/timeline.c
@@ -1113,11 +1113,11 @@
11131113
 return mtime;
11141114
 }
11151115
 }
11161116
 rid = symbolic_name_to_rid(z, "*");
11171117
 if( rid ){
1118
- mtime = db_double(0.0, "SELECT mtime FROM event WHERE objid=%d", rid);
1118
+ mtime = mtime_of_rid(rid, 0.0);
11191119
 }else{
11201120
 mtime = db_double(-1.0,
11211121
 "SELECT max(event.mtime) FROM event, tag, tagxref"
11221122
 " WHERE tag.tagname GLOB 'event-%q*'"
11231123
 " AND tagxref.tagid=tag.tagid AND tagxref.tagtype"
@@ -2264,20 +2264,18 @@
22642264
 nd = 0;
22652265
 if( d_rid ){
22662266
 double rStopTime = 9e99;
22672267
 zFwdTo = P("ft");
22682268
 if( zFwdTo ){
2269
- double rStartDate = db_double(0.0,
2270
- "SELECT mtime FROM event WHERE objid=%d", d_rid);
2269
+ double rStartDate = mtime_of_rid(d_rid, 0.0);
22712270
 ridFwdTo = first_checkin_with_tag_after_date(zFwdTo, rStartDate);
22722271
 if( ridFwdTo==0 ){
22732272
 ridFwdTo = name_to_typed_rid(zBackTo,"ci");
22742273
 }
22752274
 if( ridFwdTo ){
22762275
 if( !haveParameterN ) nEntry = 0;
2277
- rStopTime = db_double(9e99,
2278
- "SELECT mtime FROM event WHERE objid=%d", ridFwdTo);
2276
+ rStopTime = mtime_of_rid(ridFwdTo, 9e99);
22792277
 }
22802278
 }
22812279
 if( rStopTime<9e99 ){
22822280
 rStopTime += 5.8e-6; /* Round up by 1/2 second */
22832281
 }
@@ -2302,12 +2300,11 @@
23022300
 db_multi_exec("DELETE FROM ok");
23032301
 }
23042302
 if( p_rid ){
23052303
 zBackTo = P("bt");
23062304
 if( zBackTo ){
2307
- double rDateLimit = db_double(0.0,
2308
- "SELECT mtime FROM event WHERE objid=%d", p_rid);
2305
+ double rDateLimit = mtime_of_rid(p_rid, 0.0);
23092306
 ridBackTo = last_checkin_with_tag_before_date(zBackTo, rDateLimit);
23102307
 if( ridBackTo==0 ){
23112308
 ridBackTo = name_to_typed_rid(zBackTo,"ci");
23122309
 }
23132310
 if( ridBackTo && !haveParameterN ) nEntry = 0;
23142311
--- src/timeline.c
+++ src/timeline.c
@@ -1113,11 +1113,11 @@
1113 return mtime;
1114 }
1115 }
1116 rid = symbolic_name_to_rid(z, "*");
1117 if( rid ){
1118 mtime = db_double(0.0, "SELECT mtime FROM event WHERE objid=%d", rid);
1119 }else{
1120 mtime = db_double(-1.0,
1121 "SELECT max(event.mtime) FROM event, tag, tagxref"
1122 " WHERE tag.tagname GLOB 'event-%q*'"
1123 " AND tagxref.tagid=tag.tagid AND tagxref.tagtype"
@@ -2264,20 +2264,18 @@
2264 nd = 0;
2265 if( d_rid ){
2266 double rStopTime = 9e99;
2267 zFwdTo = P("ft");
2268 if( zFwdTo ){
2269 double rStartDate = db_double(0.0,
2270 "SELECT mtime FROM event WHERE objid=%d", d_rid);
2271 ridFwdTo = first_checkin_with_tag_after_date(zFwdTo, rStartDate);
2272 if( ridFwdTo==0 ){
2273 ridFwdTo = name_to_typed_rid(zBackTo,"ci");
2274 }
2275 if( ridFwdTo ){
2276 if( !haveParameterN ) nEntry = 0;
2277 rStopTime = db_double(9e99,
2278 "SELECT mtime FROM event WHERE objid=%d", ridFwdTo);
2279 }
2280 }
2281 if( rStopTime<9e99 ){
2282 rStopTime += 5.8e-6; /* Round up by 1/2 second */
2283 }
@@ -2302,12 +2300,11 @@
2302 db_multi_exec("DELETE FROM ok");
2303 }
2304 if( p_rid ){
2305 zBackTo = P("bt");
2306 if( zBackTo ){
2307 double rDateLimit = db_double(0.0,
2308 "SELECT mtime FROM event WHERE objid=%d", p_rid);
2309 ridBackTo = last_checkin_with_tag_before_date(zBackTo, rDateLimit);
2310 if( ridBackTo==0 ){
2311 ridBackTo = name_to_typed_rid(zBackTo,"ci");
2312 }
2313 if( ridBackTo && !haveParameterN ) nEntry = 0;
2314
--- src/timeline.c
+++ src/timeline.c
@@ -1113,11 +1113,11 @@
1113 return mtime;
1114 }
1115 }
1116 rid = symbolic_name_to_rid(z, "*");
1117 if( rid ){
1118 mtime = mtime_of_rid(rid, 0.0);
1119 }else{
1120 mtime = db_double(-1.0,
1121 "SELECT max(event.mtime) FROM event, tag, tagxref"
1122 " WHERE tag.tagname GLOB 'event-%q*'"
1123 " AND tagxref.tagid=tag.tagid AND tagxref.tagtype"
@@ -2264,20 +2264,18 @@
2264 nd = 0;
2265 if( d_rid ){
2266 double rStopTime = 9e99;
2267 zFwdTo = P("ft");
2268 if( zFwdTo ){
2269 double rStartDate = mtime_of_rid(d_rid, 0.0);
 
2270 ridFwdTo = first_checkin_with_tag_after_date(zFwdTo, rStartDate);
2271 if( ridFwdTo==0 ){
2272 ridFwdTo = name_to_typed_rid(zBackTo,"ci");
2273 }
2274 if( ridFwdTo ){
2275 if( !haveParameterN ) nEntry = 0;
2276 rStopTime = mtime_of_rid(ridFwdTo, 9e99);
 
2277 }
2278 }
2279 if( rStopTime<9e99 ){
2280 rStopTime += 5.8e-6; /* Round up by 1/2 second */
2281 }
@@ -2302,12 +2300,11 @@
2300 db_multi_exec("DELETE FROM ok");
2301 }
2302 if( p_rid ){
2303 zBackTo = P("bt");
2304 if( zBackTo ){
2305 double rDateLimit = mtime_of_rid(p_rid, 0.0);
 
2306 ridBackTo = last_checkin_with_tag_before_date(zBackTo, rDateLimit);
2307 if( ridBackTo==0 ){
2308 ridBackTo = name_to_typed_rid(zBackTo,"ci");
2309 }
2310 if( ridBackTo && !haveParameterN ) nEntry = 0;
2311

Keyboard Shortcuts

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