Fossil SCM

Performance improvements on the compute_leavs() routine. There is opportunity for further improvement in this area.

drh 2009-08-27 15:00 trunk
Commit 6953ca813cce7f2275dde00ff6ebac44230607c8
Parent 1409fbe38c764e9…
1 file changed +88 -78
~ src/descendants.c
M src/descendants.c
+88 -78
--- src/descendants.c
+++ src/descendants.c
@@ -31,11 +31,12 @@
3131
3232
 /*
3333
 ** Create a temporary table named "leaves" if it does not
3434
 ** already exist. Load this table with the RID of all
3535
 ** check-ins that are leaves which are decended from
36
-** check-in iBase.
36
+** check-in iBase. If iBase==0, find all leaves within the
37
+** entire check-in hierarchy.
3738
 **
3839
 ** A "leaf" is a check-in that has no children in the same branch.
3940
 **
4041
 ** The closeMode flag determines behavior associated with the "closed"
4142
 ** tag:
@@ -49,15 +50,10 @@
4950
 ** The default behavior is to ignore closed leaves (closeMode==0). To
5051
 ** Show all leaves, use closeMode==1. To show only closed leaves, use
5152
 ** closeMode==2.
5253
 */
5354
 void compute_leaves(int iBase, int closeMode){
54
- Bag seen; /* Descendants seen */
55
- Bag pending; /* Unpropagated descendants */
56
- Stmt q1; /* Query to find children of a check-in */
57
- Stmt isBr; /* Query to check to see if a check-in starts a new branch */
58
- Stmt ins; /* INSERT statement for a new record */
5955
6056
 /* Create the LEAVES table if it does not already exist. Make sure
6157
 ** it is empty.
6258
 */
6359
 db_multi_exec(
@@ -66,84 +62,98 @@
6662
 ");"
6763
 "DELETE FROM leaves;"
6864
 );
6965
7066
 /* We are checking all descendants of iBase. If iBase==0, then
71
- ** change iBase to be the root of the entire check-in hierarchy.
67
+ ** use a short-cut to find all leaves anywhere in the hierarchy.
7268
 */
7369
 if( iBase<=0 ){
74
- iBase = db_int(0, "SELECT objid FROM event WHERE type='ci'"
75
- " ORDER BY mtime LIMIT 1");
76
- if( iBase==0 ) return;
77
- }
78
-
79
- /* Initialize the bags. */
80
- bag_init(&seen);
81
- bag_init(&pending);
82
- bag_insert(&pending, iBase);
83
-
84
- /* This query returns all non-branch-merge children of check-in :rid.
85
- **
86
- ** If a a child is a merge of a fork within the same branch, it is
87
- ** returned. Only merge children in different branches are excluded.
88
- */
89
- db_prepare(&q1,
90
- "SELECT cid FROM plink"
91
- " WHERE pid=:rid"
92
- " AND (isprim"
93
- " OR coalesce((SELECT value FROM tagxref"
94
- " WHERE tagid=%d AND rid=plink.pid), 'trunk')"
95
- "=coalesce((SELECT value FROM tagxref"
96
- " WHERE tagid=%d AND rid=plink.cid), 'trunk'))",
97
- TAG_BRANCH, TAG_BRANCH
98
- );
99
-
100
- /* This query returns a single row if check-in :rid is the first
101
- ** check-in of a new branch.
102
- */
103
- db_prepare(&isBr,
104
- "SELECT 1 FROM tagxref"
105
- " WHERE rid=:rid AND tagid=%d AND tagtype=2"
106
- " AND srcid>0",
107
- TAG_BRANCH
108
- );
109
-
110
- /* This statement inserts check-in :rid into the LEAVES table.
111
- */
112
- db_prepare(&ins, "INSERT OR IGNORE INTO leaves VALUES(:rid)");
113
-
114
- while( bag_count(&pending) ){
115
- int rid = bag_first(&pending);
116
- int cnt = 0;
117
- bag_remove(&pending, rid);
118
- db_bind_int(&q1, ":rid", rid);
119
- while( db_step(&q1)==SQLITE_ROW ){
120
- int cid = db_column_int(&q1, 0);
121
- if( bag_insert(&seen, cid) ){
122
- bag_insert(&pending, cid);
123
- }
124
- db_bind_int(&isBr, ":rid", cid);
125
- if( db_step(&isBr)==SQLITE_DONE ){
126
- cnt++;
127
- }
128
- db_reset(&isBr);
129
- }
130
- db_reset(&q1);
131
- if( cnt==0 && !is_a_leaf(rid) ){
132
- cnt++;
133
- }
134
- if( cnt==0 ){
135
- db_bind_int(&ins, ":rid", rid);
136
- db_step(&ins);
137
- db_reset(&ins);
138
- }
139
- }
140
- db_finalize(&ins);
141
- db_finalize(&isBr);
142
- db_finalize(&q1);
143
- bag_clear(&pending);
144
- bag_clear(&seen);
70
+ db_multi_exec(
71
+ "INSERT OR IGNORE INTO leaves"
72
+ " SELECT cid FROM plink"
73
+ " EXCEPT"
74
+ " SELECT pid FROM plink"
75
+ " WHERE coalesce((SELECT value FROM tagxref"
76
+ " WHERE tagid=%d AND rid=plink.pid),'trunk')"
77
+ " == coalesce((SELECT value FROM tagxref"
78
+ " WHERE tagid=%d AND rid=plink.cid),'trunk');",
79
+ TAG_BRANCH, TAG_BRANCH
80
+ );
81
+ }else{
82
+ Bag seen; /* Descendants seen */
83
+ Bag pending; /* Unpropagated descendants */
84
+ Stmt q1; /* Query to find children of a check-in */
85
+ Stmt isBr; /* Query to check to see if a check-in starts a new branch */
86
+ Stmt ins; /* INSERT statement for a new record */
87
+
88
+ /* Initialize the bags. */
89
+ bag_init(&seen);
90
+ bag_init(&pending);
91
+ bag_insert(&pending, iBase);
92
+
93
+ /* This query returns all non-branch-merge children of check-in :rid.
94
+ **
95
+ ** If a a child is a merge of a fork within the same branch, it is
96
+ ** returned. Only merge children in different branches are excluded.
97
+ */
98
+ db_prepare(&q1,
99
+ "SELECT cid FROM plink"
100
+ " WHERE pid=:rid"
101
+ " AND (isprim"
102
+ " OR coalesce((SELECT value FROM tagxref"
103
+ " WHERE tagid=%d AND rid=plink.pid), 'trunk')"
104
+ "=coalesce((SELECT value FROM tagxref"
105
+ " WHERE tagid=%d AND rid=plink.cid), 'trunk'))",
106
+ TAG_BRANCH, TAG_BRANCH
107
+ );
108
+
109
+ /* This query returns a single row if check-in :rid is the first
110
+ ** check-in of a new branch.
111
+ */
112
+ db_prepare(&isBr,
113
+ "SELECT 1 FROM tagxref"
114
+ " WHERE rid=:rid AND tagid=%d AND tagtype=2"
115
+ " AND srcid>0",
116
+ TAG_BRANCH
117
+ );
118
+
119
+ /* This statement inserts check-in :rid into the LEAVES table.
120
+ */
121
+ db_prepare(&ins, "INSERT OR IGNORE INTO leaves VALUES(:rid)");
122
+
123
+ while( bag_count(&pending) ){
124
+ int rid = bag_first(&pending);
125
+ int cnt = 0;
126
+ bag_remove(&pending, rid);
127
+ db_bind_int(&q1, ":rid", rid);
128
+ while( db_step(&q1)==SQLITE_ROW ){
129
+ int cid = db_column_int(&q1, 0);
130
+ if( bag_insert(&seen, cid) ){
131
+ bag_insert(&pending, cid);
132
+ }
133
+ db_bind_int(&isBr, ":rid", cid);
134
+ if( db_step(&isBr)==SQLITE_DONE ){
135
+ cnt++;
136
+ }
137
+ db_reset(&isBr);
138
+ }
139
+ db_reset(&q1);
140
+ if( cnt==0 && !is_a_leaf(rid) ){
141
+ cnt++;
142
+ }
143
+ if( cnt==0 ){
144
+ db_bind_int(&ins, ":rid", rid);
145
+ db_step(&ins);
146
+ db_reset(&ins);
147
+ }
148
+ }
149
+ db_finalize(&ins);
150
+ db_finalize(&isBr);
151
+ db_finalize(&q1);
152
+ bag_clear(&pending);
153
+ bag_clear(&seen);
154
+ }
145155
 if( closeMode==1 ){
146156
 db_multi_exec(
147157
 "DELETE FROM leaves WHERE rid IN"
148158
 " (SELECT leaves.rid FROM leaves, tagxref"
149159
 " WHERE tagxref.rid=leaves.rid "
150160
--- src/descendants.c
+++ src/descendants.c
@@ -31,11 +31,12 @@
31
32 /*
33 ** Create a temporary table named "leaves" if it does not
34 ** already exist. Load this table with the RID of all
35 ** check-ins that are leaves which are decended from
36 ** check-in iBase.
 
37 **
38 ** A "leaf" is a check-in that has no children in the same branch.
39 **
40 ** The closeMode flag determines behavior associated with the "closed"
41 ** tag:
@@ -49,15 +50,10 @@
49 ** The default behavior is to ignore closed leaves (closeMode==0). To
50 ** Show all leaves, use closeMode==1. To show only closed leaves, use
51 ** closeMode==2.
52 */
53 void compute_leaves(int iBase, int closeMode){
54 Bag seen; /* Descendants seen */
55 Bag pending; /* Unpropagated descendants */
56 Stmt q1; /* Query to find children of a check-in */
57 Stmt isBr; /* Query to check to see if a check-in starts a new branch */
58 Stmt ins; /* INSERT statement for a new record */
59
60 /* Create the LEAVES table if it does not already exist. Make sure
61 ** it is empty.
62 */
63 db_multi_exec(
@@ -66,84 +62,98 @@
66 ");"
67 "DELETE FROM leaves;"
68 );
69
70 /* We are checking all descendants of iBase. If iBase==0, then
71 ** change iBase to be the root of the entire check-in hierarchy.
72 */
73 if( iBase<=0 ){
74 iBase = db_int(0, "SELECT objid FROM event WHERE type='ci'"
75 " ORDER BY mtime LIMIT 1");
76 if( iBase==0 ) return;
77 }
78
79 /* Initialize the bags. */
80 bag_init(&seen);
81 bag_init(&pending);
82 bag_insert(&pending, iBase);
83
84 /* This query returns all non-branch-merge children of check-in :rid.
85 **
86 ** If a a child is a merge of a fork within the same branch, it is
87 ** returned. Only merge children in different branches are excluded.
88 */
89 db_prepare(&q1,
90 "SELECT cid FROM plink"
91 " WHERE pid=:rid"
92 " AND (isprim"
93 " OR coalesce((SELECT value FROM tagxref"
94 " WHERE tagid=%d AND rid=plink.pid), 'trunk')"
95 "=coalesce((SELECT value FROM tagxref"
96 " WHERE tagid=%d AND rid=plink.cid), 'trunk'))",
97 TAG_BRANCH, TAG_BRANCH
98 );
99
100 /* This query returns a single row if check-in :rid is the first
101 ** check-in of a new branch.
102 */
103 db_prepare(&isBr,
104 "SELECT 1 FROM tagxref"
105 " WHERE rid=:rid AND tagid=%d AND tagtype=2"
106 " AND srcid>0",
107 TAG_BRANCH
108 );
109
110 /* This statement inserts check-in :rid into the LEAVES table.
111 */
112 db_prepare(&ins, "INSERT OR IGNORE INTO leaves VALUES(:rid)");
113
114 while( bag_count(&pending) ){
115 int rid = bag_first(&pending);
116 int cnt = 0;
117 bag_remove(&pending, rid);
118 db_bind_int(&q1, ":rid", rid);
119 while( db_step(&q1)==SQLITE_ROW ){
120 int cid = db_column_int(&q1, 0);
121 if( bag_insert(&seen, cid) ){
122 bag_insert(&pending, cid);
123 }
124 db_bind_int(&isBr, ":rid", cid);
125 if( db_step(&isBr)==SQLITE_DONE ){
126 cnt++;
127 }
128 db_reset(&isBr);
129 }
130 db_reset(&q1);
131 if( cnt==0 && !is_a_leaf(rid) ){
132 cnt++;
133 }
134 if( cnt==0 ){
135 db_bind_int(&ins, ":rid", rid);
136 db_step(&ins);
137 db_reset(&ins);
138 }
139 }
140 db_finalize(&ins);
141 db_finalize(&isBr);
142 db_finalize(&q1);
143 bag_clear(&pending);
144 bag_clear(&seen);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
145 if( closeMode==1 ){
146 db_multi_exec(
147 "DELETE FROM leaves WHERE rid IN"
148 " (SELECT leaves.rid FROM leaves, tagxref"
149 " WHERE tagxref.rid=leaves.rid "
150
--- src/descendants.c
+++ src/descendants.c
@@ -31,11 +31,12 @@
31
32 /*
33 ** Create a temporary table named "leaves" if it does not
34 ** already exist. Load this table with the RID of all
35 ** check-ins that are leaves which are decended from
36 ** check-in iBase. If iBase==0, find all leaves within the
37 ** entire check-in hierarchy.
38 **
39 ** A "leaf" is a check-in that has no children in the same branch.
40 **
41 ** The closeMode flag determines behavior associated with the "closed"
42 ** tag:
@@ -49,15 +50,10 @@
50 ** The default behavior is to ignore closed leaves (closeMode==0). To
51 ** Show all leaves, use closeMode==1. To show only closed leaves, use
52 ** closeMode==2.
53 */
54 void compute_leaves(int iBase, int closeMode){
 
 
 
 
 
55
56 /* Create the LEAVES table if it does not already exist. Make sure
57 ** it is empty.
58 */
59 db_multi_exec(
@@ -66,84 +62,98 @@
62 ");"
63 "DELETE FROM leaves;"
64 );
65
66 /* We are checking all descendants of iBase. If iBase==0, then
67 ** use a short-cut to find all leaves anywhere in the hierarchy.
68 */
69 if( iBase<=0 ){
70 db_multi_exec(
71 "INSERT OR IGNORE INTO leaves"
72 " SELECT cid FROM plink"
73 " EXCEPT"
74 " SELECT pid FROM plink"
75 " WHERE coalesce((SELECT value FROM tagxref"
76 " WHERE tagid=%d AND rid=plink.pid),'trunk')"
77 " == coalesce((SELECT value FROM tagxref"
78 " WHERE tagid=%d AND rid=plink.cid),'trunk');",
79 TAG_BRANCH, TAG_BRANCH
80 );
81 }else{
82 Bag seen; /* Descendants seen */
83 Bag pending; /* Unpropagated descendants */
84 Stmt q1; /* Query to find children of a check-in */
85 Stmt isBr; /* Query to check to see if a check-in starts a new branch */
86 Stmt ins; /* INSERT statement for a new record */
87
88 /* Initialize the bags. */
89 bag_init(&seen);
90 bag_init(&pending);
91 bag_insert(&pending, iBase);
92
93 /* This query returns all non-branch-merge children of check-in :rid.
94 **
95 ** If a a child is a merge of a fork within the same branch, it is
96 ** returned. Only merge children in different branches are excluded.
97 */
98 db_prepare(&q1,
99 "SELECT cid FROM plink"
100 " WHERE pid=:rid"
101 " AND (isprim"
102 " OR coalesce((SELECT value FROM tagxref"
103 " WHERE tagid=%d AND rid=plink.pid), 'trunk')"
104 "=coalesce((SELECT value FROM tagxref"
105 " WHERE tagid=%d AND rid=plink.cid), 'trunk'))",
106 TAG_BRANCH, TAG_BRANCH
107 );
108
109 /* This query returns a single row if check-in :rid is the first
110 ** check-in of a new branch.
111 */
112 db_prepare(&isBr,
113 "SELECT 1 FROM tagxref"
114 " WHERE rid=:rid AND tagid=%d AND tagtype=2"
115 " AND srcid>0",
116 TAG_BRANCH
117 );
118
119 /* This statement inserts check-in :rid into the LEAVES table.
120 */
121 db_prepare(&ins, "INSERT OR IGNORE INTO leaves VALUES(:rid)");
122
123 while( bag_count(&pending) ){
124 int rid = bag_first(&pending);
125 int cnt = 0;
126 bag_remove(&pending, rid);
127 db_bind_int(&q1, ":rid", rid);
128 while( db_step(&q1)==SQLITE_ROW ){
129 int cid = db_column_int(&q1, 0);
130 if( bag_insert(&seen, cid) ){
131 bag_insert(&pending, cid);
132 }
133 db_bind_int(&isBr, ":rid", cid);
134 if( db_step(&isBr)==SQLITE_DONE ){
135 cnt++;
136 }
137 db_reset(&isBr);
138 }
139 db_reset(&q1);
140 if( cnt==0 && !is_a_leaf(rid) ){
141 cnt++;
142 }
143 if( cnt==0 ){
144 db_bind_int(&ins, ":rid", rid);
145 db_step(&ins);
146 db_reset(&ins);
147 }
148 }
149 db_finalize(&ins);
150 db_finalize(&isBr);
151 db_finalize(&q1);
152 bag_clear(&pending);
153 bag_clear(&seen);
154 }
155 if( closeMode==1 ){
156 db_multi_exec(
157 "DELETE FROM leaves WHERE rid IN"
158 " (SELECT leaves.rid FROM leaves, tagxref"
159 " WHERE tagxref.rid=leaves.rid "
160

Keyboard Shortcuts

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