Lines Matching +full:non +full:- +full:linear
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 &&
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);
100 int FirstTombstone = -1;
107 if (FirstTombstone != -1) {
118 if (FirstTombstone == -1)
123 // being non-null and for the full hash value) not at the items. This
127 // null-terminated!
129 if (Name == StringRef(ItemStr, BucketItem->getKeyLength())) {
136 BucketNo = (BucketNo + ProbeAmt) & (NumBuckets - 1);
138 // Use quadratic probing, it has fewer clumping artifacts than linear
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?
155 unsigned BucketNo = FullHashValue & (NumBuckets - 1);
163 return -1;
170 // being non-null and for the full hash value) not at the items. This
174 // null-terminated!
176 if (Key == StringRef(ItemStr, BucketItem->getKeyLength())) {
183 BucketNo = (BucketNo + ProbeAmt) & (NumBuckets - 1);
185 // Use quadratic probing, it has fewer clumping artifacts than linear
191 /// RemoveKey - Remove the specified StringMapEntry from the table, but do not
195 StringMapEntryBase *V2 = RemoveKey(StringRef(VStr, V->getKeyLength()));
200 /// RemoveKey - Remove the StringMapEntry for the specified key from the
204 if (Bucket == -1)
209 --NumItems;
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) <=
244 unsigned NewBucket = FullHash & (NewSize - 1);
248 NewBucket = (NewBucket + ProbeSize++) & (NewSize - 1);