Skip to content

Commit 6bc1aa9

Browse files
ruevsruevs
committed
IdList clean up the iterator, remove unnecessary bounds checking.
Fix RemoveTagged not to leave removed elements at the end of the index.
1 parent 1d44f00 commit 6bc1aa9

1 file changed

Lines changed: 27 additions & 106 deletions

File tree

‎src/dsc.h‎

Lines changed: 27 additions & 106 deletions
Original file line numberDiff line numberDiff line change
@@ -383,18 +383,12 @@ struct CompareId {
383383
}
384384

385385
bool operator()(int lhs, T const& rhs) const {
386-
// return idlist->elemstore[idlist->elemidx[lhs]].h.v < rhs.h.v;
387386
return idlist->elemstore[lhs].h.v < rhs.h.v;
388387
}
389388
bool operator()(int lhs, H rhs) const {
390-
// return idlist->elemstore[idlist->elemidx[lhs]].h.v < rhs.v;
391389
return idlist->elemstore[lhs].h.v < rhs.v;
392390
}
393-
/* bool operator()(T *lhs, T const *rhs) const {
394-
return lhs->h.v < rhs->h.v;
395-
}*/
396391
bool operator()(T *lhs, int rhs) const {
397-
// return lhs->h.v < idlist->elemstore[idlist->elemidx[rhs]].h.v;
398392
return lhs->h.v < idlist->elemstore[rhs].h.v;
399393
}
400394

@@ -422,114 +416,67 @@ class IdList {
422416
typedef int difference_type;
423417
typedef T *pointer;
424418
typedef T &reference;
419+
425420
public:
426-
T &operator*() const noexcept {
427-
ssassert(1 == isInBounds(), "Dereferencing out of bounds iterator");
428-
return *elem;
429-
}
430-
const T *operator->() const noexcept {
431-
ssassert(1 == isInBounds(), "Dereferencing out of bounds iterator");
432-
// return &(list->elemstore[list->elemidx[position]]);
433-
return elem;
434-
}
421+
T &operator*() const noexcept { return *elem; }
422+
const T *operator->() const noexcept { return elem; }
435423

436424
T &operator=(const T &e) const noexcept {
437-
ssassert(1 == isInBounds(), "Assigning to out of bounds iterator");
438425
*elem = e;
439426
return *this;
440427
}
441428
T &operator=(const H h) const noexcept {
442-
ssassert(1 == isInBounds(), "Assigning to out of bounds iterator");
443429
elem->h = e;
444430
return *this;
445431
}
446432

447-
bool operator==(const iterator &p) const {
448-
ssassert(list == p.list, "Comparison of iterators of different lists");
449-
if(isInBounds() && p.isInBounds())
450-
return p.position == position;
451-
else
452-
return p.outOfBounds == outOfBounds;
453-
}
454-
bool operator<(const iterator &p) const {
455-
ssassert(list == p.list, "Comparison of iterators of different lists");
456-
if(p.isInBounds()) {
457-
if(!isInBounds())
458-
return outOfBounds < 0; // < if we are out of bounds at the beginning
459-
return position < p.position;
460-
} else if(isInBounds()) {
461-
return 0 < p.outOfBounds; // < if compared iterator is out of bounds at the end
462-
} else { // both iterators are before or after their beginnings or ends
463-
return outOfBounds < p.outOfBounds;
464-
}
465-
}
433+
bool operator==(const iterator &p) const { return p.position == position; }
434+
bool operator<(const iterator &p) const { return position < p.position; }
466435
bool operator!=(const iterator &p) const { return !operator==(p); }
467436
bool operator>(const iterator &p) const { return operator!=(p) && !operator<(p); }
468437
bool operator>=(const iterator &p) const { return !operator<(p); }
469438
bool operator<=(const iterator &p) const { return !operator>(p); }
470439

471440
iterator &operator++() {
472-
if(isInBounds()) {
473-
++position;
474-
if(position == list->elemidx.size()) {
475-
outOfBounds = 1;
476-
elem = nullptr; // PAR@@@@ Remove just debugging
477-
} else {
478-
elem = &(list->elemstore[list->elemidx[position]]);
479-
}
480-
} else {
481-
outOfBounds++;
441+
++position;
442+
if(position >= (int)list->elemidx.size()) {
443+
elem = nullptr; // PAR@@@@ Remove just debugging
444+
} else if(0 <= position) {
445+
elem = &(list->elemstore[list->elemidx[position]]);
482446
}
483447
return *this;
484448
}
485449
iterator &operator--() {
486-
if(isInBounds()) {
487-
if(position == 0) { // move one backwards out-of-bounds
488-
outOfBounds = -1;
489-
elem = nullptr; // PAR@@@@ Remove just debugging
490-
} else {
491-
--position;
492-
elem = &(list->elemstore[list->elemidx[position]]);
493-
}
494-
} else {
495-
outOfBounds--;
496-
if(outOfBounds == 0) {
497-
// iterator was at end (+1)
498-
position = list->elemidx.size() - 1;
499-
elem = &(list->elemstore[list->elemidx[position]]);
500-
}
450+
--position;
451+
if(0 > position) {
452+
elem = nullptr; // PAR@@@@ Remove just debugging
453+
} else if(position < list->elemidx.size()) {
454+
elem = &(list->elemstore[list->elemidx[position]]);
501455
}
502456
return *this;
503457
}
504-
bool isInBounds() const {
505-
return outOfBounds == 0;
506-
}
507458

508-
iterator(IdList<T, H> *l) : list(l), position(0), outOfBounds(0) {
459+
iterator(IdList<T, H> *l) : list(l), position(0) {
509460
if(list) {
510461
if(list->elemstore.size() && list->elemidx.size()) {
511462
elem = &(list->elemstore[list->elemidx[position]]);
512463
}
513464
}
514465
};
515466
iterator(const iterator &iter)
516-
: list(iter.list), position(iter.position), outOfBounds(iter.outOfBounds),
517-
elem(iter.elem){};
518-
iterator(IdList<T, H> *l, int pos, int relToBounds = 0)
519-
: list(l), position(pos), outOfBounds(relToBounds) {
520-
if(position == list->elemidx.size()) {
521-
outOfBounds = 1;
522-
elem = nullptr;
523-
} else {
467+
: list(iter.list), position(iter.position), elem(iter.elem){};
468+
iterator(IdList<T, H> *l, int pos) : list(l), position(pos) {
469+
if(position >= (int)list->elemidx.size()) {
470+
elem = nullptr;
471+
} else if(0 <= position) {
524472
elem = &((list->elemstore)[list->elemidx[position]]);
525473
}
526474
};
527475

528476
private:
529477
int position;
530478
T *elem;
531-
IdList<T, H> *list; // pointer to the list
532-
int outOfBounds; // before the beginning (-1) or after the end (+1), else 0
479+
IdList<T, H> *list;
533480
};
534481

535482

@@ -548,33 +495,14 @@ class IdList {
548495
H AddAndAssignId(T *t) {
549496
t->h.v = (MaximumId() + 1);
550497

551-
// Copy-construct at the end of the list.
498+
// Add at the end of the list.
552499
elemstore.push_back(*t);
553500
elemidx.push_back(elemstore.size()-1);
554-
555501
++n;
556502

557503
return t->h;
558504
}
559505

560-
/*
561-
T * LowerBound(T const& t) {
562-
return LowerBound(t.h);
563-
}
564-
565-
T * LowerBound(H const& h) {
566-
if(IsEmpty()) {
567-
return nullptr;
568-
}
569-
auto it = std::lower_bound(elemptr.begin(), elemptr.end(), h, Compare(this));
570-
if(it == elemptr.end()) {
571-
return nullptr;
572-
} else {
573-
return *it;
574-
}
575-
}
576-
*/
577-
578506
int LowerBoundIndex(T const& t) {
579507
if(IsEmpty()) {
580508
return 0;
@@ -584,6 +512,7 @@ class IdList {
584512
auto i = static_cast<int>(idx);
585513
return i;
586514
}
515+
587516
void ReserveMore(int howMuch) {
588517
elemstore.reserve(n + howMuch);
589518
elemidx.reserve(n + howMuch);
@@ -649,7 +578,6 @@ class IdList {
649578
return nullptr;
650579
} else {
651580
if(elemstore[*it].h.v != h.v) {
652-
// dbp("lower_bound failed in FindByIdNoOops!?"); // This is normal when looking for non-existing elements - i.e. each Add operation
653581
return nullptr;
654582
}
655583
return &elemstore[*it];
@@ -708,7 +636,7 @@ class IdList {
708636
if(elemstore[elemidx[src]].tag) {
709637
// this item should be deleted
710638
elemstore[elemidx[src]].Clear();
711-
elemstore[elemidx[src]].~T();
639+
// elemstore[elemidx[src]].~T(); // Clear below calls the destructors
712640
freelist.push_back(elemidx[src]);
713641
elemidx[src] = 0xDEADBEEF; // PAR@@@@@ just for debugging, not needed, remove later
714642
} else {
@@ -719,7 +647,7 @@ class IdList {
719647
}
720648
}
721649
n = dest;
722-
650+
elemidx.resize(n); // Clear left over elements at the end.
723651
}
724652
void RemoveById(H h) { // PAR@@@@@ this can be optimized
725653
ClearTags();
@@ -737,8 +665,7 @@ class IdList {
737665

738666
void DeepCopyInto(IdList<T,H> *l) {
739667
l->Clear();
740-
// l->elemstor.reserve(elemstor.capacity()); // Make the element store the same size as ours since the freelist may point to elements
741-
// no need do not waste memory
668+
742669
for(auto const &it : elemstore) {
743670
l->elemstore.push_back(it);
744671
}
@@ -747,12 +674,6 @@ class IdList {
747674
l->elemidx.push_back(it);
748675
}
749676

750-
/* Do not copy the freelist - no need to waste memory.
751-
for(auto &it : freelist) {
752-
l->freelist.push_back(it);
753-
}
754-
*/
755-
756677
l->n = n;
757678
}
758679

0 commit comments

Comments
 (0)