contrib/llvm/lib/Support/SmallPtrSet.cpp

   1 //===- llvm/ADT/SmallPtrSet.cpp - 'Normally small' pointer set ------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the SmallPtrSet class.  See SmallPtrSet.h for an
  11 // overview of the algorithm.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/ADT/SmallPtrSet.h"
  16 #include "llvm/ADT/DenseMapInfo.h"
  17 #include "llvm/Support/MathExtras.h"
  18 #include <algorithm>
  19 #include <cstdlib>
  20
  21 using namespace llvm;
  22
  23 void SmallPtrSetImplBase::shrink_and_clear() {
  24   assert(!isSmall() && "Can't shrink a small set!");
  25   free(CurArray);
  26
  27   // Reduce the number of buckets.
  28   unsigned Size = size();
  29   CurArraySize = Size > 16 ? 1 << (Log2_32_Ceil(Size) + 1) : 32;
  30   NumNonEmpty = NumTombstones = 0;
  31
  32   // Install the new array.  Clear all the buckets to empty.
  33   CurArray = (const void**)malloc(sizeof(void*) * CurArraySize);
  34   assert(CurArray && "Failed to allocate memory?");
  35   memset(CurArray, -1, CurArraySize*sizeof(void*));
  36 }
  37
  38 std::pair<const void *const *, bool>
  39 SmallPtrSetImplBase::insert_imp_big(const void *Ptr) {
  40   if (LLVM_UNLIKELY(size() * 4 >= CurArraySize * 3)) {
  41     // If more than 3/4 of the array is full, grow.
  42     Grow(CurArraySize < 64 ? 128 : CurArraySize * 2);
  43   } else if (LLVM_UNLIKELY(CurArraySize - NumNonEmpty < CurArraySize / 8)) {
  44     // If fewer of 1/8 of the array is empty (meaning that many are filled with
  45     // tombstones), rehash.
  46     Grow(CurArraySize);
  47   }
  48
  49   // Okay, we know we have space.  Find a hash bucket.
  50   const void **Bucket = const_cast<const void**>(FindBucketFor(Ptr));
  51   if (*Bucket == Ptr)
  52     return std::make_pair(Bucket, false); // Already inserted, good.
  53
  54   // Otherwise, insert it!
  55   if (*Bucket == getTombstoneMarker())
  56     --NumTombstones;
  57   else
  58     ++NumNonEmpty; // Track density.
  59   *Bucket = Ptr;
  60   return std::make_pair(Bucket, true);
  61 }
  62
  63 bool SmallPtrSetImplBase::erase_imp(const void * Ptr) {
  64   if (isSmall()) {
  65     // Check to see if it is in the set.
  66     for (const void **APtr = CurArray, **E = CurArray + NumNonEmpty; APtr != E;
  67          ++APtr)
  68       if (*APtr == Ptr) {
  69         // If it is in the set, replace this element.
  70         *APtr = getTombstoneMarker();
  71         ++NumTombstones;
  72         return true;
  73       }
  74
  75     return false;
  76   }
  77
  78   // Okay, we know we have space.  Find a hash bucket.
  79   void **Bucket = const_cast<void**>(FindBucketFor(Ptr));
  80   if (*Bucket != Ptr) return false;  // Not in the set?
  81
  82   // Set this as a tombstone.
  83   *Bucket = getTombstoneMarker();
  84   ++NumTombstones;
  85   return true;
  86 }
  87
  88 const void * const *SmallPtrSetImplBase::FindBucketFor(const void *Ptr) const {
  89   unsigned Bucket = DenseMapInfo<void *>::getHashValue(Ptr) & (CurArraySize-1);
  90   unsigned ArraySize = CurArraySize;
  91   unsigned ProbeAmt = 1;
  92   const void *const *Array = CurArray;
  93   const void *const *Tombstone = nullptr;
  94   while (1) {
  95     // If we found an empty bucket, the pointer doesn't exist in the set.
  96     // Return a tombstone if we've seen one so far, or the empty bucket if
  97     // not.
  98     if (LLVM_LIKELY(Array[Bucket] == getEmptyMarker()))
  99       return Tombstone ? Tombstone : Array+Bucket;
 100
 101     // Found Ptr's bucket?
 102     if (LLVM_LIKELY(Array[Bucket] == Ptr))
 103       return Array+Bucket;
 104
 105     // If this is a tombstone, remember it.  If Ptr ends up not in the set, we
 106     // prefer to return it than something that would require more probing.
 107     if (Array[Bucket] == getTombstoneMarker() && !Tombstone)
 108       Tombstone = Array+Bucket;  // Remember the first tombstone found.
 109
 110     // It's a hash collision or a tombstone. Reprobe.
 111     Bucket = (Bucket + ProbeAmt++) & (ArraySize-1);
 112   }
 113 }
 114
 115 /// Grow - Allocate a larger backing store for the buckets and move it over.
 116 ///
 117 void SmallPtrSetImplBase::Grow(unsigned NewSize) {
 118   const void **OldBuckets = CurArray;
 119   const void **OldEnd = EndPointer();
 120   bool WasSmall = isSmall();
 121
 122   // Install the new array.  Clear all the buckets to empty.
 123   CurArray = (const void**)malloc(sizeof(void*) * NewSize);
 124   assert(CurArray && "Failed to allocate memory?");
 125   CurArraySize = NewSize;
 126   memset(CurArray, -1, NewSize*sizeof(void*));
 127
 128   // Copy over all valid entries.
 129   for (const void **BucketPtr = OldBuckets; BucketPtr != OldEnd; ++BucketPtr) {
 130     // Copy over the element if it is valid.
 131     const void *Elt = *BucketPtr;
 132     if (Elt != getTombstoneMarker() && Elt != getEmptyMarker())
 133       *const_cast<void**>(FindBucketFor(Elt)) = const_cast<void*>(Elt);
 134   }
 135
 136   if (!WasSmall)
 137     free(OldBuckets);
 138   NumNonEmpty -= NumTombstones;
 139   NumTombstones = 0;
 140 }
 141
 142 SmallPtrSetImplBase::SmallPtrSetImplBase(const void **SmallStorage,
 143                                          const SmallPtrSetImplBase &that) {
 144   SmallArray = SmallStorage;
 145
 146   // If we're becoming small, prepare to insert into our stack space
 147   if (that.isSmall()) {
 148     CurArray = SmallArray;
 149   // Otherwise, allocate new heap space (unless we were the same size)
 150   } else {
 151     CurArray = (const void**)malloc(sizeof(void*) * that.CurArraySize);
 152     assert(CurArray && "Failed to allocate memory?");
 153   }
 154
 155   // Copy over the that array.
 156   CopyHelper(that);
 157 }
 158
 159 SmallPtrSetImplBase::SmallPtrSetImplBase(const void **SmallStorage,
 160                                          unsigned SmallSize,
 161                                          SmallPtrSetImplBase &&that) {
 162   SmallArray = SmallStorage;
 163   MoveHelper(SmallSize, std::move(that));
 164 }
 165
 166 void SmallPtrSetImplBase::CopyFrom(const SmallPtrSetImplBase &RHS) {
 167   assert(&RHS != this && "Self-copy should be handled by the caller.");
 168
 169   if (isSmall() && RHS.isSmall())
 170     assert(CurArraySize == RHS.CurArraySize &&
 171            "Cannot assign sets with different small sizes");
 172
 173   // If we're becoming small, prepare to insert into our stack space
 174   if (RHS.isSmall()) {
 175     if (!isSmall())
 176       free(CurArray);
 177     CurArray = SmallArray;
 178   // Otherwise, allocate new heap space (unless we were the same size)
 179   } else if (CurArraySize != RHS.CurArraySize) {
 180     if (isSmall())
 181       CurArray = (const void**)malloc(sizeof(void*) * RHS.CurArraySize);
 182     else {
 183       const void **T = (const void**)realloc(CurArray,
 184                                              sizeof(void*) * RHS.CurArraySize);
 185       if (!T)
 186         free(CurArray);
 187       CurArray = T;
 188     }
 189     assert(CurArray && "Failed to allocate memory?");
 190   }
 191
 192   CopyHelper(RHS);
 193 }
 194
 195 void SmallPtrSetImplBase::CopyHelper(const SmallPtrSetImplBase &RHS) {
 196   // Copy over the new array size
 197   CurArraySize = RHS.CurArraySize;
 198
 199   // Copy over the contents from the other set
 200   std::copy(RHS.CurArray, RHS.EndPointer(), CurArray);
 201
 202   NumNonEmpty = RHS.NumNonEmpty;
 203   NumTombstones = RHS.NumTombstones;
 204 }
 205
 206 void SmallPtrSetImplBase::MoveFrom(unsigned SmallSize,
 207                                    SmallPtrSetImplBase &&RHS) {
 208   if (!isSmall())
 209     free(CurArray);
 210   MoveHelper(SmallSize, std::move(RHS));
 211 }
 212
 213 void SmallPtrSetImplBase::MoveHelper(unsigned SmallSize,
 214                                      SmallPtrSetImplBase &&RHS) {
 215   assert(&RHS != this && "Self-move should be handled by the caller.");
 216
 217   if (RHS.isSmall()) {
 218     // Copy a small RHS rather than moving.
 219     CurArray = SmallArray;
 220     std::copy(RHS.CurArray, RHS.CurArray + RHS.NumNonEmpty, CurArray);
 221   } else {
 222     CurArray = RHS.CurArray;
 223     RHS.CurArray = RHS.SmallArray;
 224   }
 225
 226   // Copy the rest of the trivial members.
 227   CurArraySize = RHS.CurArraySize;
 228   NumNonEmpty = RHS.NumNonEmpty;
 229   NumTombstones = RHS.NumTombstones;
 230
 231   // Make the RHS small and empty.
 232   RHS.CurArraySize = SmallSize;
 233   assert(RHS.CurArray == RHS.SmallArray);
 234   RHS.NumNonEmpty = 0;
 235   RHS.NumTombstones = 0;
 236 }
 237
 238 void SmallPtrSetImplBase::swap(SmallPtrSetImplBase &RHS) {
 239   if (this == &RHS) return;
 240
 241   // We can only avoid copying elements if neither set is small.
 242   if (!this->isSmall() && !RHS.isSmall()) {
 243     std::swap(this->CurArray, RHS.CurArray);
 244     std::swap(this->CurArraySize, RHS.CurArraySize);
 245     std::swap(this->NumNonEmpty, RHS.NumNonEmpty);
 246     std::swap(this->NumTombstones, RHS.NumTombstones);
 247     return;
 248   }
 249
 250   // FIXME: From here on we assume that both sets have the same small size.
 251
 252   // If only RHS is small, copy the small elements into LHS and move the pointer
 253   // from LHS to RHS.
 254   if (!this->isSmall() && RHS.isSmall()) {
 255     assert(RHS.CurArray == RHS.SmallArray);
 256     std::copy(RHS.CurArray, RHS.CurArray + RHS.NumNonEmpty, this->SmallArray);
 257     std::swap(RHS.CurArraySize, this->CurArraySize);
 258     std::swap(this->NumNonEmpty, RHS.NumNonEmpty);
 259     std::swap(this->NumTombstones, RHS.NumTombstones);
 260     RHS.CurArray = this->CurArray;
 261     this->CurArray = this->SmallArray;
 262     return;
 263   }
 264
 265   // If only LHS is small, copy the small elements into RHS and move the pointer
 266   // from RHS to LHS.
 267   if (this->isSmall() && !RHS.isSmall()) {
 268     assert(this->CurArray == this->SmallArray);
 269     std::copy(this->CurArray, this->CurArray + this->NumNonEmpty,
 270               RHS.SmallArray);
 271     std::swap(RHS.CurArraySize, this->CurArraySize);
 272     std::swap(RHS.NumNonEmpty, this->NumNonEmpty);
 273     std::swap(RHS.NumTombstones, this->NumTombstones);
 274     this->CurArray = RHS.CurArray;
 275     RHS.CurArray = RHS.SmallArray;
 276     return;
 277   }
 278
 279   // Both a small, just swap the small elements.
 280   assert(this->isSmall() && RHS.isSmall());
 281   unsigned MinNonEmpty = std::min(this->NumNonEmpty, RHS.NumNonEmpty);
 282   std::swap_ranges(this->SmallArray, this->SmallArray + MinNonEmpty,
 283                    RHS.SmallArray);
 284   if (this->NumNonEmpty > MinNonEmpty) {
 285     std::copy(this->SmallArray + MinNonEmpty,
 286               this->SmallArray + this->NumNonEmpty,
 287               RHS.SmallArray + MinNonEmpty);
 288   } else {
 289     std::copy(RHS.SmallArray + MinNonEmpty, RHS.SmallArray + RHS.NumNonEmpty,
 290               this->SmallArray + MinNonEmpty);
 291   }
 292   assert(this->CurArraySize == RHS.CurArraySize);
 293   std::swap(this->NumNonEmpty, RHS.NumNonEmpty);
 294   std::swap(this->NumTombstones, RHS.NumTombstones);
 295 }