FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [Original HTTPS Page]

Port IdList to using a shared_ptr<vector>. · solvespace/solvespace@aefdd8f · GitHub

/ solvespace Public

Commit aefdd8f

Browse files
rpavlik
committed
Port IdList to using a shared_ptr<vector>.
The issue before is that much of the code relies on a copy or assignment of IdList being a shallow copy, so using a shared_ptr was the simplest way to preserve that meaning. (Using a Vector directly was unsuccessful due to changed copy semantics. The variety of iteration methods makes a port to shared_ptr<unordered_map> harder and more far-reaching, if nevertheless worthwhile.)
1 parent b284e80 commit aefdd8f

1 file changed

Lines changed: 98 additions & 64 deletions

File tree

‎src/dsc.h‎

Lines changed: 98 additions & 64 deletions
Original file line numberDiff line numberDiff line change
@@ -337,21 +337,64 @@ struct CompareId {
337337
// id.
338338
template <class T, class H>
339339
class IdList {
340-
T *elem = nullptr;
341-
int elemsAllocated = 0;
340+
std::shared_ptr<std::vector<T>> vec;
341+
int internalN = 0;
342+
void UpdateSize() {
343+
if(!vec) {
344+
internalN = 0;
345+
} else {
346+
internalN = static_cast<int>(vec->size());
347+
}
348+
}
349+
void AllocForOneMore() {
350+
if(!vec) {
351+
vec = std::make_shared<std::vector<T>>();
352+
}
353+
if(vec->capacity() == vec->size()) {
354+
// Let the built-in growth policy deal with this.
355+
vec->reserve(vec->size() + 1);
356+
}
357+
}
358+
342359
public:
343-
int n = 0;
360+
std::reference_wrapper<const int> n = std::cref(internalN);
344361

345362
using Compare = CompareId<T, H>;
346363

347-
bool IsEmpty() const {
348-
return n == 0;
364+
bool IsEmpty() const { return !vec || vec->empty(); }
365+
366+
IdList() : n(std::cref(internalN)) {}
367+
368+
// Makes a shallow copy that shares the underlying list!
369+
IdList(IdList const &other) : vec(other.vec), internalN(other.internalN), n(std::cref(internalN)) {}
370+
371+
// Assigns a shallow copy that shares the underlying list!
372+
IdList &operator=(IdList const &other) {
373+
if(this == &other || vec == other.vec) {
374+
// No self-assign
375+
return *this;
376+
}
377+
vec = other.vec;
378+
UpdateSize();
379+
return *this;
349380
}
350381

351-
void AllocForOneMore() {
352-
if(n >= elemsAllocated) {
353-
ReserveMore((elemsAllocated + 32)*2 - n);
382+
IdList(IdList &&other) : vec(std::move(other.vec)), internalN(other.internalN), n(std::cref(internalN)) {
383+
other.vec.reset();
384+
UpdateSize();
385+
other.UpdateSize();
386+
}
387+
388+
IdList &operator=(IdList &&other) {
389+
if(this == &other || vec == other.vec) {
390+
// No self-assign
391+
return *this;
354392
}
393+
Clear();
394+
vec = std::move(other.vec);
395+
UpdateSize();
396+
other.UpdateSize();
397+
return *this;
355398
}
356399

357400
uint32_t MaximumId() {
@@ -374,48 +417,43 @@ class IdList {
374417
return nullptr;
375418
}
376419
auto it = std::lower_bound(begin(), end(), t, Compare());
377-
return it;
420+
return &(*it);
378421
}
379422

380423
T * LowerBound(H const& h) {
381424
if(IsEmpty()) {
382425
return nullptr;
383426
}
384427
auto it = std::lower_bound(begin(), end(), h, Compare());
385-
return it;
428+
return &(*it);
386429
}
387430

388431
int LowerBoundIndex(T const& t) {
389432
if(IsEmpty()) {
390433
return 0;
391434
}
392-
auto it = LowerBound(t);
435+
auto it = std::lower_bound(begin(), end(), t, Compare());
393436
auto idx = std::distance(begin(), it);
394437
auto i = static_cast<int>(idx);
395438
return i;
396439
}
440+
397441
void ReserveMore(int howMuch) {
398-
if(n + howMuch > elemsAllocated) {
399-
elemsAllocated = n + howMuch;
400-
T *newElem = (T *)MemAlloc((size_t)elemsAllocated*sizeof(T));
401-
for(int i = 0; i < n; i++) {
402-
new(&newElem[i]) T(std::move(elem[i]));
403-
elem[i].~T();
404-
}
405-
MemFree(elem);
406-
elem = newElem;
442+
if(!vec) {
443+
vec = std::make_shared<std::vector<T>>();
407444
}
445+
vec->reserve(n + howMuch);
408446
}
409447

410448
void Add(T *t) {
411-
AllocForOneMore();
412-
413449
// Look to see if we already have something with the same handle value.
414450
ssassert(FindByIdNoOops(t->h) == nullptr, "Handle isn't unique");
415451

416452
// Copy-construct at the end of the list.
417-
new(&elem[n]) T(*t);
418-
++n;
453+
AllocForOneMore();
454+
vec->emplace_back(*t);
455+
UpdateSize();
456+
419457
// The item we just added is trivially sorted, so "merge"
420458
std::inplace_merge(begin(), end() - 1, end(), Compare());
421459
}
@@ -430,7 +468,7 @@ class IdList {
430468
if(IsEmpty()) {
431469
return -1;
432470
}
433-
auto it = LowerBound(h);
471+
auto it = std::lower_bound(begin(), end(), h, Compare());
434472
auto idx = std::distance(begin(), it);
435473
if (idx < n) {
436474
return idx;
@@ -442,39 +480,37 @@ class IdList {
442480
if(IsEmpty()) {
443481
return nullptr;
444482
}
445-
auto it = LowerBound(h);
446-
if (it == nullptr || it == end()) {
483+
auto it = std::lower_bound(begin(), end(), h, Compare());
484+
if (it == end()) {
447485
return nullptr;
448486
}
449487
if (it->h.v == h.v) {
450-
return it;
488+
return &(*it);
451489
}
452490
return nullptr;
453491
}
454492

455-
T *First() {
456-
return (IsEmpty()) ? NULL : &(elem[0]);
457-
}
458-
T *Last() {
459-
return (IsEmpty()) ? NULL : &(elem[n-1]);
460-
}
493+
T *First() { return (IsEmpty()) ? NULL : &(vec->front()); }
494+
T *Last() { return (IsEmpty()) ? NULL : &(vec->back()); }
461495
T *NextAfter(T *prev) {
462496
if(IsEmpty() || !prev) return NULL;
463497
if(prev - First() == (n - 1)) return NULL;
464498
return prev + 1;
465499
}
466500

467-
T &Get(size_t i) { return elem[i]; }
468-
T const &Get(size_t i) const { return elem[i]; }
501+
T &Get(size_t i) { return (*vec)[i]; }
502+
T const &Get(size_t i) const { return (*vec)[i]; }
469503
T &operator[](size_t i) { return Get(i); }
470504
T const &operator[](size_t i) const { return Get(i); }
471505

472-
T *begin() { return IsEmpty() ? nullptr : &elem[0]; }
473-
T *end() { return IsEmpty() ? nullptr : &elem[n]; }
474-
const T *begin() const { return IsEmpty() ? nullptr : &elem[0]; }
475-
const T *end() const { return IsEmpty() ? nullptr : &elem[n]; }
476-
const T *cbegin() const { return begin(); }
477-
const T *cend() const { return end(); }
506+
using iterator = typename std::vector<T>::iterator;
507+
using const_iterator = typename std::vector<T>::const_iterator;
508+
iterator begin() { return IsEmpty() ? iterator() : vec->begin(); }
509+
iterator end() { return IsEmpty() ? iterator() : vec->end(); }
510+
const_iterator begin() const { return IsEmpty() ? const_iterator() : vec->begin(); }
511+
const_iterator end() const { return IsEmpty() ? const_iterator() : vec->end(); }
512+
const_iterator cbegin() const { return begin(); }
513+
const_iterator cend() const { return end(); }
478514

479515
template<typename F>
480516
size_t CountIf(F &&predicate) const {
@@ -493,20 +529,20 @@ class IdList {
493529
}
494530

495531
void RemoveTagged() {
496-
auto newEnd = std::remove_if(this->begin(), this->end(), [](T &t) {
532+
if(IsEmpty()) {
533+
return;
534+
}
535+
auto newEnd = std::remove_if(begin(), end(), [](T &t) {
497536
if(t.tag) {
498537
t.Clear();
499538
return true;
500539
}
501540
return false;
502541
});
503-
if(newEnd != this->end()) {
504-
while (newEnd != this->end()) {
505-
newEnd->~T();
506-
++newEnd;
507-
}
542+
if(newEnd != end()) {
543+
vec->erase(newEnd);
508544
}
509-
n = newEnd - begin();
545+
UpdateSize();
510546
}
511547

512548
void RemoveById(H h) {
@@ -517,30 +553,28 @@ class IdList {
517553

518554
void MoveSelfInto(IdList<T,H> *l) {
519555
l->Clear();
520-
std::swap(l->elem, elem);
521-
std::swap(l->elemsAllocated, elemsAllocated);
522-
std::swap(l->n, n);
556+
l->vec = std::move(vec);
557+
vec.reset();
558+
l->UpdateSize();
559+
UpdateSize();
523560
}
524561

525562
void DeepCopyInto(IdList<T,H> *l) {
526563
l->Clear();
527-
l->elem = (T *)MemAlloc(elemsAllocated * sizeof(elem[0]));
528-
for(int i = 0; i < n; i++)
529-
new(&l->elem[i]) T(elem[i]);
530-
l->elemsAllocated = elemsAllocated;
531-
l->n = n;
564+
if(!IsEmpty()) {
565+
l->vec = std::make_shared<std::vector<T>>(*vec);
566+
}
567+
l->UpdateSize();
532568
}
533569

534570
void Clear() {
535-
for(int i = 0; i < n; i++) {
536-
elem[i].Clear();
537-
elem[i].~T();
571+
if(IsEmpty()) {
572+
return;
538573
}
539-
if(elem) MemFree(elem);
540-
elem = NULL;
541-
elemsAllocated = n = 0;
574+
std::for_each(begin(), end(), [](T &elt) { elt.Clear(); });
575+
vec.reset();
576+
UpdateSize();
542577
}
543-
544578
};
545579

546580
class BandedMatrix {

0 commit comments

Comments
 (0)
Back | FazBrowse Home | New Git URL