1 //===--- StringMap.cpp - String Hash table map implementation -------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
11 //===----------------------------------------------------------------------===//
68   assert((InitSize & (InitSize - 1)) == 0 &&  in init()
81 /// LookupBucketFor - Look up the bucket that the specified string should end
83 /// specified bucket will be non-null.  Otherwise, it will be null.  In either
96   unsigned BucketNo = FullHashValue & (NumBuckets - 1);  in LookupBucketFor()
100   int FirstTombstone = -1;  in LookupBucketFor()
107       if (FirstTombstone != -1) {  in LookupBucketFor()
118       if (FirstTombstone == -1)  in LookupBucketFor()
123       // being non-null and for the full hash value) not at the items.  This  in LookupBucketFor()
127       // null-terminated!  in LookupBucketFor()
129       if (Name == StringRef(ItemStr, BucketItem->getKeyLength())) {  in LookupBucketFor()
136     BucketNo = (BucketNo + ProbeAmt) & (NumBuckets - 1);  in LookupBucketFor()
138     // Use quadratic probing, it has fewer clumping artifacts than linear  in LookupBucketFor()
144 /// FindKey - Look up the bucket that contains the specified key. If it exists
145 /// in the map, return the bucket number of the key.  Otherwise return -1.
149     return -1; // Really empty table?  in FindKey()
155   unsigned BucketNo = FullHashValue & (NumBuckets - 1);  in FindKey()
163       return -1;  in FindKey()
170       // being non-null and for the full hash value) not at the items.  This  in FindKey()
174       // null-terminated!  in FindKey()
176       if (Key == StringRef(ItemStr, BucketItem->getKeyLength())) {  in FindKey()
183     BucketNo = (BucketNo + ProbeAmt) & (NumBuckets - 1);  in FindKey()
185     // Use quadratic probing, it has fewer clumping artifacts than linear  in FindKey()
191 /// RemoveKey - Remove the specified StringMapEntry from the table, but do not
195   StringMapEntryBase *V2 = RemoveKey(StringRef(VStr, V->getKeyLength()));  in RemoveKey()
200 /// RemoveKey - Remove the StringMapEntry for the specified key from the
204   if (Bucket == -1)  in RemoveKey()
209   --NumItems;  in RemoveKey()
216 /// RehashTable - Grow the table, redistributing values into the buckets with
217 /// the appropriate mod-of-hashtable-size.
225   } else if (LLVM_UNLIKELY(NumBuckets - (NumItems + NumTombstones) <=  in RehashTable()
244       unsigned NewBucket = FullHash & (NewSize - 1);  in RehashTable()
248           NewBucket = (NewBucket + ProbeSize++) & (NewSize - 1);  in RehashTable()