}
// If more than 3/4 of the array is full, grow.
- if (NumElements*4 >= CurArraySize*3)
+ if (NumElements*4 >= CurArraySize*3 ||
+ CurArraySize-(NumElements+NumTombstones) < CurArraySize/8)
Grow();
// Okay, we know we have space. Find a hash bucket.
if (*Bucket == Ptr) return false; // Already inserted, good.
// Otherwise, insert it!
+ if (*Bucket == getTombstoneMarker())
+ --NumTombstones;
*Bucket = Ptr;
++NumElements; // Track density.
return true;
}
+bool SmallPtrSetImpl::erase(void *Ptr) {
+ if (isSmall()) {
+ // Check to see if it is in the set.
+ for (void **APtr = SmallArray, **E = SmallArray+NumElements;
+ APtr != E; ++APtr)
+ if (*APtr == Ptr) {
+ // If it is in the set, move everything over, replacing this element.
+ memmove(APtr, APtr+1, sizeof(void*)*(E-APtr-1));
+ // Clear the end element.
+ E[-1] = getEmptyMarker();
+ --NumElements;
+ return true;
+ }
+
+ return false;
+ }
+
+ // Okay, we know we have space. Find a hash bucket.
+ void **Bucket = const_cast<void**>(FindBucketFor(Ptr));
+ if (*Bucket != Ptr) return false; // Not in the set?
+
+ // Set this as a tombstone.
+ *Bucket = getTombstoneMarker();
+ --NumElements;
+ ++NumTombstones;
+ return true;
+}
+
void * const *SmallPtrSetImpl::FindBucketFor(void *Ptr) const {
unsigned Bucket = Hash(Ptr);
unsigned ArraySize = CurArraySize;
}
delete [] OldBuckets;
+ NumTombstones = 0;
+ }
+}
+
+SmallPtrSetImpl::SmallPtrSetImpl(const SmallPtrSetImpl& that) {
+ NumElements = that.NumElements;
+ NumTombstones = 0;
+ if (that.isSmall()) {
+ CurArraySize = that.CurArraySize;
+ CurArray = &SmallArray[0];
+ memcpy(CurArray, that.CurArray, sizeof(void*)*CurArraySize);
+ } else {
+ CurArraySize = that.NumElements < 64 ? 128 : that.NumElements*2;
+ CurArray = new void*[CurArraySize+1];
+ memset(CurArray, -1, CurArraySize*sizeof(void*));
+
+ // The end pointer, always valid, is set to a valid element to help the
+ // iterator.
+ CurArray[CurArraySize] = 0;
+
+ // Copy over all valid entries.
+ for (void **BucketPtr = that.CurArray, **E = that.CurArray+CurArraySize;
+ BucketPtr != E; ++BucketPtr) {
+ // Copy over the element if it is valid.
+ void *Elt = *BucketPtr;
+ if (Elt != getTombstoneMarker() && Elt != getEmptyMarker())
+ *const_cast<void**>(FindBucketFor(Elt)) = Elt;
+ }
}
}