LCOV - code coverage report
Current view: top level - lib/Support - StringMap.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 102 104 98.1 %
Date: 2017-09-14 15:23:50 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      640204 :   return NextPowerOf2(NumEntries * 4 / 3 + 1);
      31             : }
      32             : 
      33      747877 : StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) {
      34      747877 :   ItemSize = itemSize;
      35             :   
      36             :   // If a size is specified, initialize the table with that many buckets.
      37      747877 :   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      320102 :     init(getMinBucketToReserveForEntries(InitSize));
      42      320102 :     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     2769951 : void StringMapImpl::init(unsigned InitSize) {
      53             :   assert((InitSize & (InitSize-1)) == 0 &&
      54             :          "Init Size must be a power of 2 or zero!");
      55             : 
      56     2769951 :   unsigned NewNumBuckets = InitSize ? InitSize : 16;
      57     2769951 :   NumItems = 0;
      58     2769951 :   NumTombstones = 0;
      59             :   
      60     2769951 :   TheTable = (StringMapEntryBase **)calloc(NewNumBuckets+1,
      61             :                                            sizeof(StringMapEntryBase **) +
      62             :                                            sizeof(unsigned));
      63             : 
      64     2769951 :   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     2769951 :   NumBuckets = NewNumBuckets;
      69             : 
      70             :   // Allocate one extra bucket, set it to look filled so the iterators stop at
      71             :   // end.
      72     2769951 :   TheTable[NumBuckets] = (StringMapEntryBase*)2;
      73     2769951 : }
      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   471587472 : unsigned StringMapImpl::LookupBucketFor(StringRef Name) {
      81   471587472 :   unsigned HTSize = NumBuckets;
      82   471587472 :   if (HTSize == 0) {  // Hash table unallocated so far?
      83     2435928 :     init(16);
      84     2435930 :     HTSize = NumBuckets;
      85             :   }
      86   471587474 :   unsigned FullHashValue = HashString(Name);
      87   471587474 :   unsigned BucketNo = FullHashValue & (HTSize-1);
      88   471587474 :   unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
      89             : 
      90   471587474 :   unsigned ProbeAmt = 1;
      91   471587474 :   int FirstTombstone = -1;
      92             :   while (true) {
      93   785033820 :     StringMapEntryBase *BucketItem = TheTable[BucketNo];
      94             :     // If we found an empty bucket, this key isn't in the table yet, return it.
      95   785033820 :     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   242361019 :       if (FirstTombstone != -1) {
      99      108643 :         HashTable[FirstTombstone] = FullHashValue;
     100      108643 :         return FirstTombstone;
     101             :       }
     102             :       
     103   242252376 :       HashTable[BucketNo] = FullHashValue;
     104   242252376 :       return BucketNo;
     105             :     }
     106             :     
     107   542672801 :     if (BucketItem == getTombstoneVal()) {
     108             :       // Skip over tombstones.  However, remember the first one we see.
     109      172739 :       if (FirstTombstone == -1) FirstTombstone = BucketNo;
     110   542500062 :     } 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   229337760 :       char *ItemStr = (char*)BucketItem+ItemSize;
     119   229337760 :       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   313446346 :     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   313446346 :     ++ProbeAmt;
     131   313446346 :   }
     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    21103104 : int StringMapImpl::FindKey(StringRef Key) const {
     138    21103104 :   unsigned HTSize = NumBuckets;
     139    21103104 :   if (HTSize == 0) return -1;  // Really empty table?
     140    18292256 :   unsigned FullHashValue = HashString(Key);
     141    18292256 :   unsigned BucketNo = FullHashValue & (HTSize-1);
     142    18292256 :   unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
     143             : 
     144    18292256 :   unsigned ProbeAmt = 1;
     145             :   while (true) {
     146    40447641 :     StringMapEntryBase *BucketItem = TheTable[BucketNo];
     147             :     // If we found an empty bucket, this key isn't in the table yet, return.
     148    40447641 :     if (LLVM_LIKELY(!BucketItem))
     149             :       return -1;
     150             :     
     151    33654987 :     if (BucketItem == getTombstoneVal()) {
     152             :       // Ignore tombstones.
     153    32665418 :     } 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    11499783 :       char *ItemStr = (char*)BucketItem+ItemSize;
     162    11499783 :       if (Key == StringRef(ItemStr, BucketItem->getKeyLength())) {
     163             :         // We found a match!
     164    11499602 :         return BucketNo;
     165             :       }
     166             :     }
     167             :     
     168             :     // Okay, we didn't find the item.  Probe to the next bucket.
     169    22155385 :     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    22155385 :     ++ProbeAmt;
     174    22155385 :   }
     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     2872865 : void StringMapImpl::RemoveKey(StringMapEntryBase *V) {
     180     2872865 :   const char *VStr = (char*)V + ItemSize;
     181     5745730 :   StringMapEntryBase *V2 = RemoveKey(StringRef(VStr, V->getKeyLength()));
     182             :   (void)V2;
     183             :   assert(V == V2 && "Didn't find key?");
     184     2872865 : }
     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     2872865 : StringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) {
     189     2872865 :   int Bucket = FindKey(Key);
     190     2872865 :   if (Bucket == -1) return nullptr;
     191             :   
     192     2872865 :   StringMapEntryBase *Result = TheTable[Bucket];
     193     2872865 :   TheTable[Bucket] = getTombstoneVal();
     194     2872865 :   --NumItems;
     195     2872865 :   ++NumTombstones;
     196             :   assert(NumItems + NumTombstones <= NumBuckets);
     197             : 
     198     2872865 :   return Result;
     199             : }
     200             : 
     201             : /// RehashTable - Grow the table, redistributing values into the buckets with
     202             : /// the appropriate mod-of-hashtable-size.
     203   242361020 : unsigned StringMapImpl::RehashTable(unsigned BucketNo) {
     204             :   unsigned NewSize;
     205   242361020 :   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   242361020 :   if (LLVM_UNLIKELY(NumItems * 4 > NumBuckets * 3)) {
     211     1327561 :     NewSize = NumBuckets*2;
     212   241033459 :   } else if (LLVM_UNLIKELY(NumBuckets - (NumItems + NumTombstones) <=
     213             :                            NumBuckets / 8)) {
     214             :     NewSize = NumBuckets;
     215             :   } else {
     216             :     return BucketNo;
     217             :   }
     218             : 
     219     1329295 :   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     1329295 :     (StringMapEntryBase **)calloc(NewSize+1, sizeof(StringMapEntryBase *) +
     224     1329295 :                                              sizeof(unsigned));
     225             : 
     226     1329295 :   if (NewTableArray == nullptr)
     227           0 :     report_bad_alloc_error("Allocation of StringMap hash table failed.");
     228             : 
     229     1329295 :   unsigned *NewHashArray = (unsigned *)(NewTableArray + NewSize + 1);
     230     1329295 :   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   275676803 :   for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
     235   274347508 :     StringMapEntryBase *Bucket = TheTable[I];
     236   481448722 :     if (Bucket && Bucket != getTombstoneVal()) {
     237             :       // Fast case, bucket available.
     238   207087221 :       unsigned FullHash = HashTable[I];
     239   207087221 :       unsigned NewBucket = FullHash & (NewSize-1);
     240   375500475 :       if (!NewTableArray[NewBucket]) {
     241   168413254 :         NewTableArray[FullHash & (NewSize-1)] = Bucket;
     242   168413254 :         NewHashArray[FullHash & (NewSize-1)] = FullHash;
     243   168413254 :         if (I == BucketNo)
     244     1053220 :           NewBucketNo = NewBucket;
     245   168413254 :         continue;
     246             :       }
     247             :       
     248             :       // Otherwise probe for a spot.
     249             :       unsigned ProbeSize = 1;
     250             :       do {
     251    61285052 :         NewBucket = (NewBucket + ProbeSize++) & (NewSize-1);
     252    61285052 :       } while (NewTableArray[NewBucket]);
     253             :       
     254             :       // Finally found a slot.  Fill it in.
     255    38673967 :       NewTableArray[NewBucket] = Bucket;
     256    38673967 :       NewHashArray[NewBucket] = FullHash;
     257    38673967 :       if (I == BucketNo)
     258      271567 :         NewBucketNo = NewBucket;
     259             :     }
     260             :   }
     261             :   
     262     1329295 :   free(TheTable);
     263             :   
     264     1329295 :   TheTable = NewTableArray;
     265     1329295 :   NumBuckets = NewSize;
     266     1329295 :   NumTombstones = 0;
     267     1329295 :   return NewBucketNo;
     268             : }

Generated by: LCOV version 1.13