LCOV - code coverage report
Current view: top level - lib/Support - StringMap.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 92 94 97.9 %
Date: 2018-02-17 17:14:17 Functions: 7 7 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===--- StringMap.cpp - String Hash table map implementation -------------===//
       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 StringMap class.
      11             : //
      12             : //===----------------------------------------------------------------------===//
      13             : 
      14             : #include "llvm/ADT/StringMap.h"
      15             : #include "llvm/ADT/StringExtras.h"
      16             : #include "llvm/Support/Compiler.h"
      17             : #include "llvm/Support/MathExtras.h"
      18             : #include <cassert>
      19             : 
      20             : using namespace llvm;
      21             : 
      22             : /// Returns the number of buckets to allocate to ensure that the DenseMap can
      23             : /// accommodate \p NumEntries without need to grow().
      24             : static unsigned getMinBucketToReserveForEntries(unsigned NumEntries) {
      25             :   // Ensure that "NumEntries * 4 < NumBuckets * 3"
      26             :   if (NumEntries == 0)
      27             :     return 0;
      28             :   // +1 is required because of the strict equality.
      29             :   // For example if NumEntries is 48, we need to return 401.
      30      779626 :   return NextPowerOf2(NumEntries * 4 / 3 + 1);
      31             : }
      32             : 
      33      909451 : StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) {
      34      909451 :   ItemSize = itemSize;
      35             :   
      36             :   // If a size is specified, initialize the table with that many buckets.
      37      909451 :   if (InitSize) {
      38             :     // The table will grow when the number of entries reach 3/4 of the number of
      39             :     // buckets. To guarantee that "InitSize" number of entries can be inserted
      40             :     // in the table without growing, we allocate just what is needed here.
      41      389813 :     init(getMinBucketToReserveForEntries(InitSize));
      42      389813 :     return;
      43             :   }
      44             :   
      45             :   // Otherwise, initialize it with zero buckets to avoid the allocation.
      46             :   TheTable = nullptr;
      47             :   NumBuckets = 0;
      48             :   NumItems = 0;
      49             :   NumTombstones = 0;
      50             : }
      51             : 
      52     3634398 : void StringMapImpl::init(unsigned InitSize) {
      53             :   assert((InitSize & (InitSize-1)) == 0 &&
      54             :          "Init Size must be a power of 2 or zero!");
      55             : 
      56     3634398 :   unsigned NewNumBuckets = InitSize ? InitSize : 16;
      57     3634398 :   NumItems = 0;
      58     3634398 :   NumTombstones = 0;
      59             :   
      60     3634398 :   TheTable = (StringMapEntryBase **)calloc(NewNumBuckets+1,
      61             :                                            sizeof(StringMapEntryBase **) +
      62             :                                            sizeof(unsigned));
      63             : 
      64     3634398 :   if (TheTable == nullptr)
      65           0 :     report_bad_alloc_error("Allocation of StringMap table failed.");
      66             : 
      67             :   // Set the member only if TheTable was successfully allocated
      68     3634398 :   NumBuckets = NewNumBuckets;
      69             : 
      70             :   // Allocate one extra bucket, set it to look filled so the iterators stop at
      71             :   // end.
      72     3634398 :   TheTable[NumBuckets] = (StringMapEntryBase*)2;
      73     3634398 : }
      74             : 
      75             : /// LookupBucketFor - Look up the bucket that the specified string should end
      76             : /// up in.  If it already exists as a key in the map, the Item pointer for the
      77             : /// specified bucket will be non-null.  Otherwise, it will be null.  In either
      78             : /// case, the FullHashValue field of the bucket will be set to the hash value
      79             : /// of the string.
      80   799084662 : unsigned StringMapImpl::LookupBucketFor(StringRef Name) {
      81   799084662 :   unsigned HTSize = NumBuckets;
      82   799084662 :   if (HTSize == 0) {  // Hash table unallocated so far?
      83     3228022 :     init(16);
      84     3228022 :     HTSize = NumBuckets;
      85             :   }
      86             :   unsigned FullHashValue = HashString(Name);
      87   799084662 :   unsigned BucketNo = FullHashValue & (HTSize-1);
      88   799084662 :   unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
      89             : 
      90             :   unsigned ProbeAmt = 1;
      91             :   int FirstTombstone = -1;
      92             :   while (true) {
      93  1272146965 :     StringMapEntryBase *BucketItem = TheTable[BucketNo];
      94             :     // If we found an empty bucket, this key isn't in the table yet, return it.
      95  1272146965 :     if (LLVM_LIKELY(!BucketItem)) {
      96             :       // If we found a tombstone, we want to reuse the tombstone instead of an
      97             :       // empty bucket.  This reduces probing.
      98   359064253 :       if (FirstTombstone != -1) {
      99      132366 :         HashTable[FirstTombstone] = FullHashValue;
     100      132366 :         return FirstTombstone;
     101             :       }
     102             :       
     103   358931887 :       HashTable[BucketNo] = FullHashValue;
     104   358931887 :       return BucketNo;
     105             :     }
     106             :     
     107   913082712 :     if (BucketItem == getTombstoneVal()) {
     108             :       // Skip over tombstones.  However, remember the first one we see.
     109      205504 :       if (FirstTombstone == -1) FirstTombstone = BucketNo;
     110   912877208 :     } else if (LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) {
     111             :       // If the full hash value matches, check deeply for a match.  The common
     112             :       // case here is that we are only looking at the buckets (for item info
     113             :       // being non-null and for the full hash value) not at the items.  This
     114             :       // is important for cache locality.
     115             :       
     116             :       // Do the comparison like this because Name isn't necessarily
     117             :       // null-terminated!
     118   440316698 :       char *ItemStr = (char*)BucketItem+ItemSize;
     119             :       if (Name == StringRef(ItemStr, BucketItem->getKeyLength())) {
     120             :         // We found a match!
     121             :         return BucketNo;
     122             :       }
     123             :     }
     124             :     
     125             :     // Okay, we didn't find the item.  Probe to the next bucket.
     126   473062303 :     BucketNo = (BucketNo+ProbeAmt) & (HTSize-1);
     127             :     
     128             :     // Use quadratic probing, it has fewer clumping artifacts than linear
     129             :     // probing and has good cache behavior in the common case.
     130   473062303 :     ++ProbeAmt;
     131   473062303 :   }
     132             : }
     133             : 
     134             : /// FindKey - Look up the bucket that contains the specified key. If it exists
     135             : /// in the map, return the bucket number of the key.  Otherwise return -1.
     136             : /// This does not modify the map.
     137    28556717 : int StringMapImpl::FindKey(StringRef Key) const {
     138    28556717 :   unsigned HTSize = NumBuckets;
     139    28556717 :   if (HTSize == 0) return -1;  // Really empty table?
     140             :   unsigned FullHashValue = HashString(Key);
     141    24297889 :   unsigned BucketNo = FullHashValue & (HTSize-1);
     142    24297889 :   unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
     143             : 
     144             :   unsigned ProbeAmt = 1;
     145             :   while (true) {
     146    48226954 :     StringMapEntryBase *BucketItem = TheTable[BucketNo];
     147             :     // If we found an empty bucket, this key isn't in the table yet, return.
     148    48226954 :     if (LLVM_LIKELY(!BucketItem))
     149             :       return -1;
     150             :     
     151    39433051 :     if (BucketItem == getTombstoneVal()) {
     152             :       // Ignore tombstones.
     153    37925176 :     } else if (LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) {
     154             :       // If the full hash value matches, check deeply for a match.  The common
     155             :       // case here is that we are only looking at the buckets (for item info
     156             :       // being non-null and for the full hash value) not at the items.  This
     157             :       // is important for cache locality.
     158             :       
     159             :       // Do the comparison like this because NameStart isn't necessarily
     160             :       // null-terminated!
     161    15504176 :       char *ItemStr = (char*)BucketItem+ItemSize;
     162             :       if (Key == StringRef(ItemStr, BucketItem->getKeyLength())) {
     163             :         // We found a match!
     164    15503986 :         return BucketNo;
     165             :       }
     166             :     }
     167             :     
     168             :     // Okay, we didn't find the item.  Probe to the next bucket.
     169    23929065 :     BucketNo = (BucketNo+ProbeAmt) & (HTSize-1);
     170             :     
     171             :     // Use quadratic probing, it has fewer clumping artifacts than linear
     172             :     // probing and has good cache behavior in the common case.
     173    23929065 :     ++ProbeAmt;
     174    23929065 :   }
     175             : }
     176             : 
     177             : /// RemoveKey - Remove the specified StringMapEntry from the table, but do not
     178             : /// delete it.  This aborts if the value isn't in the table.
     179     4077231 : void StringMapImpl::RemoveKey(StringMapEntryBase *V) {
     180     4077231 :   const char *VStr = (char*)V + ItemSize;
     181     4077231 :   StringMapEntryBase *V2 = RemoveKey(StringRef(VStr, V->getKeyLength()));
     182             :   (void)V2;
     183             :   assert(V == V2 && "Didn't find key?");
     184     4077231 : }
     185             : 
     186             : /// RemoveKey - Remove the StringMapEntry for the specified key from the
     187             : /// table, returning it.  If the key is not in the table, this returns null.
     188     4077231 : StringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) {
     189     4077231 :   int Bucket = FindKey(Key);
     190     4077231 :   if (Bucket == -1) return nullptr;
     191             :   
     192     4077231 :   StringMapEntryBase *Result = TheTable[Bucket];
     193     4077231 :   TheTable[Bucket] = getTombstoneVal();
     194     4077231 :   --NumItems;
     195     4077231 :   ++NumTombstones;
     196             :   assert(NumItems + NumTombstones <= NumBuckets);
     197             : 
     198     4077231 :   return Result;
     199             : }
     200             : 
     201             : /// RehashTable - Grow the table, redistributing values into the buckets with
     202             : /// the appropriate mod-of-hashtable-size.
     203   359066090 : unsigned StringMapImpl::RehashTable(unsigned BucketNo) {
     204             :   unsigned NewSize;
     205   359066090 :   unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
     206             : 
     207             :   // If the hash table is now more than 3/4 full, or if fewer than 1/8 of
     208             :   // the buckets are empty (meaning that many are filled with tombstones),
     209             :   // grow/rehash the table.
     210   359066090 :   if (LLVM_UNLIKELY(NumItems * 4 > NumBuckets * 3)) {
     211     1912728 :     NewSize = NumBuckets*2;
     212   357153362 :   } else if (LLVM_UNLIKELY(NumBuckets - (NumItems + NumTombstones) <=
     213             :                            NumBuckets / 8)) {
     214             :     NewSize = NumBuckets;
     215             :   } else {
     216             :     return BucketNo;
     217             :   }
     218             : 
     219             :   unsigned NewBucketNo = BucketNo;
     220             :   // Allocate one extra bucket which will always be non-empty.  This allows the
     221             :   // iterators to stop at end.
     222             :   StringMapEntryBase **NewTableArray =
     223     1914892 :     (StringMapEntryBase **)calloc(NewSize+1, sizeof(StringMapEntryBase *) +
     224     1914892 :                                              sizeof(unsigned));
     225             : 
     226     1914892 :   if (NewTableArray == nullptr)
     227           0 :     report_bad_alloc_error("Allocation of StringMap hash table failed.");
     228             : 
     229     1914892 :   unsigned *NewHashArray = (unsigned *)(NewTableArray + NewSize + 1);
     230     1914892 :   NewTableArray[NewSize] = (StringMapEntryBase*)2;
     231             : 
     232             :   // Rehash all the items into their new buckets.  Luckily :) we already have
     233             :   // the hash values available, so we don't have to rehash any strings.
     234   367516912 :   for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
     235   365602020 :     StringMapEntryBase *Bucket = TheTable[I];
     236   365602020 :     if (Bucket && Bucket != getTombstoneVal()) {
     237             :       // Fast case, bucket available.
     238   276112280 :       unsigned FullHash = HashTable[I];
     239   276112280 :       unsigned NewBucket = FullHash & (NewSize-1);
     240   500979410 :       if (!NewTableArray[NewBucket]) {
     241   224867130 :         NewTableArray[FullHash & (NewSize-1)] = Bucket;
     242   224867130 :         NewHashArray[FullHash & (NewSize-1)] = FullHash;
     243   224867130 :         if (I == BucketNo)
     244             :           NewBucketNo = NewBucket;
     245   224867130 :         continue;
     246             :       }
     247             :       
     248             :       // Otherwise probe for a spot.
     249             :       unsigned ProbeSize = 1;
     250             :       do {
     251    81789920 :         NewBucket = (NewBucket + ProbeSize++) & (NewSize-1);
     252    81789920 :       } while (NewTableArray[NewBucket]);
     253             :       
     254             :       // Finally found a slot.  Fill it in.
     255    51245150 :       NewTableArray[NewBucket] = Bucket;
     256    51245150 :       NewHashArray[NewBucket] = FullHash;
     257    51245150 :       if (I == BucketNo)
     258             :         NewBucketNo = NewBucket;
     259             :     }
     260             :   }
     261             :   
     262     1914892 :   free(TheTable);
     263             :   
     264     1914892 :   TheTable = NewTableArray;
     265     1914892 :   NumBuckets = NewSize;
     266     1914892 :   NumTombstones = 0;
     267     1914892 :   return NewBucketNo;
     268             : }

Generated by: LCOV version 1.13