Skip to content

Commit 3b395bb

Browse files
pjanxpjanx
committed
IdList speedup 5: use range for rather than NextAfter
Resolves another performance regression of iteration being O(n * log n) rather than O(n).
1 parent 6c55182 commit 3b395bb

File tree

16 files changed

+211
-256
lines changed

16 files changed

+211
-256
lines changed

‎src/clipboard.cpp‎

Lines changed: 9 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -138,18 +138,17 @@ void GraphicsWindow::CopySelection() {
138138
}
139139
}
140140

141-
Constraint *c;
142-
for(c = SK.constraint.First(); c; c = SK.constraint.NextAfter(c)) {
143-
if(!SS.clipboard.ContainsEntity(c->ptA) ||
144-
!SS.clipboard.ContainsEntity(c->ptB) ||
145-
!SS.clipboard.ContainsEntity(c->entityA) ||
146-
!SS.clipboard.ContainsEntity(c->entityB) ||
147-
!SS.clipboard.ContainsEntity(c->entityC) ||
148-
!SS.clipboard.ContainsEntity(c->entityD) ||
149-
c->type == Constraint::Type::COMMENT) {
141+
for(Constraint &c : SK.constraint) {
142+
if(!SS.clipboard.ContainsEntity(c.ptA) ||
143+
!SS.clipboard.ContainsEntity(c.ptB) ||
144+
!SS.clipboard.ContainsEntity(c.entityA) ||
145+
!SS.clipboard.ContainsEntity(c.entityB) ||
146+
!SS.clipboard.ContainsEntity(c.entityC) ||
147+
!SS.clipboard.ContainsEntity(c.entityD) ||
148+
c.type == Constraint::Type::COMMENT) {
150149
continue;
151150
}
152-
SS.clipboard.c.Add(c);
151+
SS.clipboard.c.Add(&c);
153152
}
154153
}
155154

‎src/draw.cpp‎

Lines changed: 8 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -210,16 +210,15 @@ void GraphicsWindow::SelectByMarquee() {
210210
BBox marqueeBBox = BBox::From(Vector::From(marqueePoint.x, marqueePoint.y, VERY_NEGATIVE),
211211
Vector::From(orig.mouse.x, orig.mouse.y, VERY_POSITIVE));
212212

213-
Entity *e;
214-
for(e = SK.entity.First(); e; e = SK.entity.NextAfter(e)) {
215-
if(e->group != SS.GW.activeGroup) continue;
216-
if(e->IsFace() || e->IsDistance()) continue;
217-
if(!e->IsVisible()) continue;
213+
for(Entity &e : SK.entity) {
214+
if(e.group != SS.GW.activeGroup) continue;
215+
if(e.IsFace() || e.IsDistance()) continue;
216+
if(!e.IsVisible()) continue;
218217

219218
bool entityHasBBox;
220-
BBox entityBBox = e->GetOrGenerateScreenBBox(&entityHasBBox);
219+
BBox entityBBox = e.GetOrGenerateScreenBBox(&entityHasBBox);
221220
if(entityHasBBox && entityBBox.Overlaps(marqueeBBox)) {
222-
MakeSelected(e->h);
221+
MakeSelected(e.h);
223222
}
224223
}
225224
}
@@ -412,8 +411,8 @@ void GraphicsWindow::HitTestMakeSelection(Point2d mp) {
412411
cached.projRight = projRight;
413412
cached.projUp = projUp;
414413
cached.scale = scale;
415-
for(Entity *e = SK.entity.First(); e; e = SK.entity.NextAfter(e)) {
416-
e->screenBBoxValid = false;
414+
for(Entity &e : SK.entity) {
415+
e.screenBBoxValid = false;
417416
}
418417
}
419418

‎src/dsc.h‎

Lines changed: 1 addition & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -432,7 +432,7 @@ class IdList {
432432
if(IsEmpty()) {
433433
return 0;
434434
} else {
435-
return Last()->h.v;
435+
return elem[indexes[n-1]].h.v;
436436
}
437437
}
438438

@@ -507,20 +507,6 @@ class IdList {
507507
return nullptr;
508508
}
509509

510-
T *First() {
511-
return (IsEmpty()) ? NULL : &(elem[indexes[0]]);
512-
}
513-
T *Last() {
514-
return (IsEmpty()) ? NULL : &(elem[indexes[n-1]]);
515-
}
516-
T *NextAfter(T *prev) {
517-
if(IsEmpty() || !prev) return NULL;
518-
auto it = LowerBound(*prev);
519-
if(it->h.v != prev->h.v) return nullptr;
520-
if(std::distance(begin(), it) == (n - 1)) return nullptr;
521-
return &*++it;
522-
}
523-
524510
T &Get(size_t i) { return elem[indexes[i]]; }
525511
T const &Get(size_t i) const { return elem[indexes[i]]; }
526512
T &operator[](size_t i) { return Get(i); }

‎src/exportstep.cpp‎

Lines changed: 5 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -353,22 +353,21 @@ void StepFileWriter::ExportSurfacesTo(const Platform::Path &filename) {
353353

354354
advancedFaces = {};
355355

356-
SSurface *ss;
357-
for(ss = shell->surface.First(); ss; ss = shell->surface.NextAfter(ss)) {
358-
if(ss->trim.IsEmpty())
356+
for(SSurface &ss : shell->surface) {
357+
if(ss.trim.IsEmpty())
359358
continue;
360359

361360
// Get all of the loops of Beziers that trim our surface (with each
362361
// Bezier split so that we use the section as t goes from 0 to 1), and
363362
// the piecewise linearization of those loops in xyz space.
364363
SBezierList sbl = {};
365-
ss->MakeSectionEdgesInto(shell, NULL, &sbl);
364+
ss.MakeSectionEdgesInto(shell, NULL, &sbl);
366365

367366
// Apply the export scale factor.
368-
ss->ScaleSelfBy(1.0/SS.exportScale);
367+
ss.ScaleSelfBy(1.0/SS.exportScale);
369368
sbl.ScaleSelfBy(1.0/SS.exportScale);
370369

371-
ExportSurface(ss, &sbl);
370+
ExportSurface(&ss, &sbl);
372371

373372
sbl.Clear();
374373
}

‎src/exportvector.cpp‎

Lines changed: 28 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -170,22 +170,21 @@ class DxfWriteInterface : public DRW_Interface {
170170
}
171171

172172
if(writer->constraint) {
173-
Constraint *c;
174-
for(c = writer->constraint->First(); c; c = writer->constraint->NextAfter(c)) {
175-
if(!writer->NeedToOutput(c)) continue;
176-
switch(c->type) {
173+
for(Constraint &c : *writer->constraint) {
174+
if(!writer->NeedToOutput(&c)) continue;
175+
switch(c.type) {
177176
case Constraint::Type::PT_PT_DISTANCE: {
178-
Vector ap = SK.GetEntity(c->ptA)->PointGetNum();
179-
Vector bp = SK.GetEntity(c->ptB)->PointGetNum();
180-
Vector ref = ((ap.Plus(bp)).ScaledBy(0.5)).Plus(c->disp.offset);
177+
Vector ap = SK.GetEntity(c.ptA)->PointGetNum();
178+
Vector bp = SK.GetEntity(c.ptB)->PointGetNum();
179+
Vector ref = ((ap.Plus(bp)).ScaledBy(0.5)).Plus(c.disp.offset);
181180
writeAlignedDimension(xfrm(ap), xfrm(bp), xfrm(ref),
182-
xfrm(ref), c->Label(), c->GetStyle(), c->valA);
181+
xfrm(ref), c.Label(), c.GetStyle(), c.valA);
183182
break;
184183
}
185184

186185
case Constraint::Type::PT_LINE_DISTANCE: {
187-
Vector pt = SK.GetEntity(c->ptA)->PointGetNum();
188-
Entity *line = SK.GetEntity(c->entityA);
186+
Vector pt = SK.GetEntity(c.ptA)->PointGetNum();
187+
Entity *line = SK.GetEntity(c.entityA);
189188
Vector lA = SK.GetEntity(line->point[0])->PointGetNum();
190189
Vector lB = SK.GetEntity(line->point[1])->PointGetNum();
191190
Vector dl = lB.Minus(lA);
@@ -194,7 +193,7 @@ class DxfWriteInterface : public DRW_Interface {
194193

195194
if(pt.Equals(closest)) break;
196195

197-
Vector ref = ((closest.Plus(pt)).ScaledBy(0.5)).Plus(c->disp.offset);
196+
Vector ref = ((closest.Plus(pt)).ScaledBy(0.5)).Plus(c.disp.offset);
198197
Vector refClosest = ref.ClosestPointOnLine(lA, dl);
199198

200199
double ddl = dl.Dot(dl);
@@ -209,54 +208,54 @@ class DxfWriteInterface : public DRW_Interface {
209208

210209
Vector xdl = xfrm(lB).Minus(xfrm(lA));
211210
writeLinearDimension(xfrm(pt), xfrm(refClosest), xfrm(ref),
212-
xfrm(ref), c->Label(),
211+
xfrm(ref), c.Label(),
213212
atan2(xdl.y, xdl.x) / PI * 180.0 + 90.0, 0.0,
214-
c->GetStyle(), c->valA);
213+
c.GetStyle(), c.valA);
215214
break;
216215
}
217216

218217
case Constraint::Type::DIAMETER: {
219-
Entity *circle = SK.GetEntity(c->entityA);
218+
Entity *circle = SK.GetEntity(c.entityA);
220219
Vector center = SK.GetEntity(circle->point[0])->PointGetNum();
221220
Quaternion q = SK.GetEntity(circle->normal)->NormalGetNum();
222221
Vector n = q.RotationN().WithMagnitude(1);
223222
double r = circle->CircleGetRadiusNum();
224223

225-
Vector ref = center.Plus(c->disp.offset);
224+
Vector ref = center.Plus(c.disp.offset);
226225
// Force the label into the same plane as the circle.
227226
ref = ref.Minus(n.ScaledBy(n.Dot(ref) - n.Dot(center)));
228227

229228
Vector rad = ref.Minus(center).WithMagnitude(r);
230-
if(/*isRadius*/c->other) {
229+
if(/*isRadius*/c.other) {
231230
writeRadialDimension(
232231
xfrm(center), xfrm(center.Plus(rad)),
233-
xfrm(ref), c->Label(), c->GetStyle(), c->valA);
232+
xfrm(ref), c.Label(), c.GetStyle(), c.valA);
234233
} else {
235234
writeDiametricDimension(
236235
xfrm(center.Minus(rad)), xfrm(center.Plus(rad)),
237-
xfrm(ref), c->Label(), c->GetStyle(), c->valA);
236+
xfrm(ref), c.Label(), c.GetStyle(), c.valA);
238237
}
239238
break;
240239
}
241240

242241
case Constraint::Type::ANGLE: {
243-
Entity *a = SK.GetEntity(c->entityA);
244-
Entity *b = SK.GetEntity(c->entityB);
242+
Entity *a = SK.GetEntity(c.entityA);
243+
Entity *b = SK.GetEntity(c.entityB);
245244

246245
Vector a0 = a->VectorGetStartPoint();
247246
Vector b0 = b->VectorGetStartPoint();
248247
Vector da = a->VectorGetNum();
249248
Vector db = b->VectorGetNum();
250-
if(/*otherAngle*/c->other) {
249+
if(/*otherAngle*/c.other) {
251250
a0 = a0.Plus(da);
252251
da = da.ScaledBy(-1);
253252
}
254253

255254
bool skew = false;
256-
Vector ref = c->disp.offset;
255+
Vector ref = c.disp.offset;
257256
Vector pi = Vector::AtIntersectionOfLines(a0, a0.Plus(da), b0, b0.Plus(db),
258257
&skew);
259-
if(!skew) ref = pi.Plus(c->disp.offset);
258+
if(!skew) ref = pi.Plus(c.disp.offset);
260259

261260
Vector norm = da.Cross(db);
262261
Vector dna = norm.Cross(da).WithMagnitude(1.0);
@@ -277,7 +276,7 @@ class DxfWriteInterface : public DRW_Interface {
277276
Vector bisect = da.WithMagnitude(1.0).ScaledBy(cos(thetaf / 2.0)).Plus(
278277
dna.ScaledBy(sin(thetaf / 2.0)));
279278

280-
ref = pi.Plus(bisect.WithMagnitude(c->disp.offset.Magnitude()));
279+
ref = pi.Plus(bisect.WithMagnitude(c.disp.offset.Magnitude()));
281280

282281
// Get lines again to write exact line.
283282
a0 = a->VectorGetStartPoint();
@@ -287,15 +286,15 @@ class DxfWriteInterface : public DRW_Interface {
287286

288287
writeAngularDimension(
289288
xfrm(a0), xfrm(a0.Plus(da)), xfrm(b0), xfrm(b0.Plus(db)), xfrm(ref),
290-
xfrm(ref), c->Label(), c->GetStyle(), c->valA);
289+
xfrm(ref), c.Label(), c.GetStyle(), c.valA);
291290
break;
292291
}
293292

294293
case Constraint::Type::COMMENT: {
295-
Style *st = SK.style.FindById(c->GetStyle());
296-
writeText(xfrm(c->disp.offset), c->Label(),
297-
Style::TextHeight(c->GetStyle()) / SS.GW.scale,
298-
st->textAngle, st->textOrigin, c->GetStyle());
294+
Style *st = SK.style.FindById(c.GetStyle());
295+
writeText(xfrm(c.disp.offset), c.Label(),
296+
Style::TextHeight(c.GetStyle()) / SS.GW.scale,
297+
st->textAngle, st->textOrigin, c.GetStyle());
299298
break;
300299
}
301300

‎src/file.cpp‎

Lines changed: 14 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -354,41 +354,39 @@ bool SolveSpaceUI::SaveToFile(const Platform::Path &filename) {
354354
}
355355

356356
SShell *s = &g->runningShell;
357-
SSurface *srf;
358-
for(srf = s->surface.First(); srf; srf = s->surface.NextAfter(srf)) {
357+
for(SSurface &srf : s->surface) {
359358
fprintf(fh, "Surface %08x %08x %08x %d %d\n",
360-
srf->h.v, srf->color.ToPackedInt(), srf->face, srf->degm, srf->degn);
361-
for(i = 0; i <= srf->degm; i++) {
362-
for(j = 0; j <= srf->degn; j++) {
359+
srf.h.v, srf.color.ToPackedInt(), srf.face, srf.degm, srf.degn);
360+
for(i = 0; i <= srf.degm; i++) {
361+
for(j = 0; j <= srf.degn; j++) {
363362
fprintf(fh, "SCtrl %d %d %.20f %.20f %.20f Weight %20.20f\n",
364-
i, j, CO(srf->ctrl[i][j]), srf->weight[i][j]);
363+
i, j, CO(srf.ctrl[i][j]), srf.weight[i][j]);
365364
}
366365
}
367366

368367
STrimBy *stb;
369-
for(stb = srf->trim.First(); stb; stb = srf->trim.NextAfter(stb)) {
368+
for(stb = srf.trim.First(); stb; stb = srf.trim.NextAfter(stb)) {
370369
fprintf(fh, "TrimBy %08x %d %.20f %.20f %.20f %.20f %.20f %.20f\n",
371370
stb->curve.v, stb->backwards ? 1 : 0,
372371
CO(stb->start), CO(stb->finish));
373372
}
374373

375374
fprintf(fh, "AddSurface\n");
376375
}
377-
SCurve *sc;
378-
for(sc = s->curve.First(); sc; sc = s->curve.NextAfter(sc)) {
376+
for(SCurve &sc : s->curve) {
379377
fprintf(fh, "Curve %08x %d %d %08x %08x\n",
380-
sc->h.v,
381-
sc->isExact ? 1 : 0, sc->exact.deg,
382-
sc->surfA.v, sc->surfB.v);
378+
sc.h.v,
379+
sc.isExact ? 1 : 0, sc.exact.deg,
380+
sc.surfA.v, sc.surfB.v);
383381

384-
if(sc->isExact) {
385-
for(i = 0; i <= sc->exact.deg; i++) {
382+
if(sc.isExact) {
383+
for(i = 0; i <= sc.exact.deg; i++) {
386384
fprintf(fh, "CCtrl %d %.20f %.20f %.20f Weight %.20f\n",
387-
i, CO(sc->exact.ctrl[i]), sc->exact.weight[i]);
385+
i, CO(sc.exact.ctrl[i]), sc.exact.weight[i]);
388386
}
389387
}
390388
SCurvePt *scpt;
391-
for(scpt = sc->pts.First(); scpt; scpt = sc->pts.NextAfter(scpt)) {
389+
for(scpt = sc.pts.First(); scpt; scpt = sc.pts.NextAfter(scpt)) {
392390
fprintf(fh, "CurvePt %d %.20f %.20f %.20f\n",
393391
scpt->vertex ? 1 : 0, CO(scpt->p));
394392
}

0 commit comments

Comments
 (0)