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-05-20 00:06:23 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/DJB.h"
      18             : #include "llvm/Support/MathExtras.h"
      19             : #include <cassert>
      20             : 
      21             : using namespace llvm;
      22             : 
      23             : /// Returns the number of buckets to allocate to ensure that the DenseMap can
      24             : /// accommodate \p NumEntries without need to grow().
      25             : static unsigned getMinBucketToReserveForEntries(unsigned NumEntries) {
      26             :   // Ensure that "NumEntries * 4 < NumBuckets * 3"
      27             :   if (NumEntries == 0)
      28             :     return 0;
      29             :   // +1 is required because of the strict equality.
      30             :   // For example if NumEntries is 48, we need to return 401.
      31      827414 :   return NextPowerOf2(NumEntries * 4 / 3 + 1);
      32             : }
      33             : 
      34      964074 : StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) {
      35      964074 :   ItemSize = itemSize;
      36             : 
      37             :   // If a size is specified, initialize the table with that many buckets.
      38      964074 :   if (InitSize) {
      39             :     // The table will grow when the number of entries reach 3/4 of the number of
      40             :     // buckets. To guarantee that "InitSize" number of entries can be inserted
      41             :     // in the table without growing, we allocate just what is needed here.
      42      413707 :     init(getMinBucketToReserveForEntries(InitSize));
      43      413707 :     return;
      44             :   }
      45             : 
      46             :   // Otherwise, initialize it with zero buckets to avoid the allocation.
      47             :   TheTable = nullptr;
      48             :   NumBuckets = 0;
      49             :   NumItems = 0;
      50             :   NumTombstones = 0;
      51             : }
      52             : 
      53     3809602 : void StringMapImpl::init(unsigned InitSize) {
      54             :   assert((InitSize & (InitSize-1)) == 0 &&
      55             :          "Init Size must be a power of 2 or zero!");
      56             : 
      57     3809602 :   unsigned NewNumBuckets = InitSize ? InitSize : 16;
      58     3809602 :   NumItems = 0;
      59     3809602 :   NumTombstones = 0;
      60             : 
      61     3809602 :   TheTable = static_cast<StringMapEntryBase **>(
      62     3809602 :       std::calloc(NewNumBuckets+1,
      63             :                   sizeof(StringMapEntryBase **) + sizeof(unsigned)));
      64     3809602 :   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     3809602 :   NumBuckets = NewNumBuckets;
      69             : 
      70             :   // Allocate one extra bucket, set it to look filled so the iterators stop at
      71             :   // end.
      72     3809602 :   TheTable[NumBuckets] = (StringMapEntryBase*)2;
      73     3809602 : }
      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   782038033 : unsigned StringMapImpl::LookupBucketFor(StringRef Name) {
      81   782038033 :   unsigned HTSize = NumBuckets;
      82   782038033 :   if (HTSize == 0) {  // Hash table unallocated so far?
      83     3378421 :     init(16);
      84     3378424 :     HTSize = NumBuckets;
      85             :   }
      86             :   unsigned FullHashValue = djbHash(Name, 0);
      87   782038036 :   unsigned BucketNo = FullHashValue & (HTSize-1);
      88   782038036 :   unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
      89             : 
      90             :   unsigned ProbeAmt = 1;
      91             :   int FirstTombstone = -1;
      92             :   while (true) {
      93  1270559476 :     StringMapEntryBase *BucketItem = TheTable[BucketNo];
      94             :     // If we found an empty bucket, this key isn't in the table yet, return it.
      95  1270559476 :     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   371484794 :       if (FirstTombstone != -1) {
      99      139171 :         HashTable[FirstTombstone] = FullHashValue;
     100      139171 :         return FirstTombstone;
     101             :       }
     102             : 
     103   371345623 :       HashTable[BucketNo] = FullHashValue;
     104   371345623 :       return BucketNo;
     105             :     }
     106             : 
     107   899074682 :     if (BucketItem == getTombstoneVal()) {
     108             :       // Skip over tombstones.  However, remember the first one we see.
     109      214911 :       if (FirstTombstone == -1) FirstTombstone = BucketNo;
     110   898859771 :     } 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   410818339 :       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   488521440 :     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   488521440 :     ++ProbeAmt;
     131   488521440 :   }
     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    31799364 : int StringMapImpl::FindKey(StringRef Key) const {
     138    31799364 :   unsigned HTSize = NumBuckets;
     139    31799364 :   if (HTSize == 0) return -1;  // Really empty table?
     140             :   unsigned FullHashValue = djbHash(Key, 0);
     141    27210163 :   unsigned BucketNo = FullHashValue & (HTSize-1);
     142    27210163 :   unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
     143             : 
     144             :   unsigned ProbeAmt = 1;
     145             :   while (true) {
     146    51245629 :     StringMapEntryBase *BucketItem = TheTable[BucketNo];
     147             :     // If we found an empty bucket, this key isn't in the table yet, return.
     148    51245629 :     if (LLVM_LIKELY(!BucketItem))
     149             :       return -1;
     150             : 
     151    42119312 :     if (BucketItem == getTombstoneVal()) {
     152             :       // Ignore tombstones.
     153    40529252 :     } 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    18084029 :       char *ItemStr = (char*)BucketItem+ItemSize;
     162             :       if (Key == StringRef(ItemStr, BucketItem->getKeyLength())) {
     163             :         // We found a match!
     164    18083846 :         return BucketNo;
     165             :       }
     166             :     }
     167             : 
     168             :     // Okay, we didn't find the item.  Probe to the next bucket.
     169    24035466 :     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    24035466 :     ++ProbeAmt;
     174    24035466 :   }
     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     4279351 : void StringMapImpl::RemoveKey(StringMapEntryBase *V) {
     180     4279351 :   const char *VStr = (char*)V + ItemSize;
     181     4279351 :   StringMapEntryBase *V2 = RemoveKey(StringRef(VStr, V->getKeyLength()));
     182             :   (void)V2;
     183             :   assert(V == V2 && "Didn't find key?");
     184     4279351 : }
     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     4279351 : StringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) {
     189     4279351 :   int Bucket = FindKey(Key);
     190     4279351 :   if (Bucket == -1) return nullptr;
     191             : 
     192     4279351 :   StringMapEntryBase *Result = TheTable[Bucket];
     193     4279351 :   TheTable[Bucket] = getTombstoneVal();
     194     4279351 :   --NumItems;
     195     4279351 :   ++NumTombstones;
     196             :   assert(NumItems + NumTombstones <= NumBuckets);
     197             : 
     198     4279351 :   return Result;
     199             : }
     200             : 
     201             : /// RehashTable - Grow the table, redistributing values into the buckets with
     202             : /// the appropriate mod-of-hashtable-size.
     203   371484423 : unsigned StringMapImpl::RehashTable(unsigned BucketNo) {
     204             :   unsigned NewSize;
     205   371484423 :   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   371484423 :   if (LLVM_UNLIKELY(NumItems * 4 > NumBuckets * 3)) {
     211     1985993 :     NewSize = NumBuckets*2;
     212   369498430 :   } 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             :   auto NewTableArray = static_cast<StringMapEntryBase **>(
     223     1988171 :       std::calloc(NewSize+1, sizeof(StringMapEntryBase *) + sizeof(unsigned)));
     224     1988171 :   if (NewTableArray == nullptr)
     225           0 :     report_bad_alloc_error("Allocation of StringMap hash table failed.");
     226             : 
     227     1988171 :   unsigned *NewHashArray = (unsigned *)(NewTableArray + NewSize + 1);
     228     1988171 :   NewTableArray[NewSize] = (StringMapEntryBase*)2;
     229             : 
     230             :   // Rehash all the items into their new buckets.  Luckily :) we already have
     231             :   // the hash values available, so we don't have to rehash any strings.
     232   400061631 :   for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
     233   398073460 :     StringMapEntryBase *Bucket = TheTable[I];
     234   398073460 :     if (Bucket && Bucket != getTombstoneVal()) {
     235             :       // Fast case, bucket available.
     236   300539096 :       unsigned FullHash = HashTable[I];
     237   300539096 :       unsigned NewBucket = FullHash & (NewSize-1);
     238   546176637 :       if (!NewTableArray[NewBucket]) {
     239   245637541 :         NewTableArray[FullHash & (NewSize-1)] = Bucket;
     240   245637541 :         NewHashArray[FullHash & (NewSize-1)] = FullHash;
     241   245637541 :         if (I == BucketNo)
     242             :           NewBucketNo = NewBucket;
     243   245637541 :         continue;
     244             :       }
     245             : 
     246             :       // Otherwise probe for a spot.
     247             :       unsigned ProbeSize = 1;
     248             :       do {
     249    88928025 :         NewBucket = (NewBucket + ProbeSize++) & (NewSize-1);
     250    88928025 :       } while (NewTableArray[NewBucket]);
     251             : 
     252             :       // Finally found a slot.  Fill it in.
     253    54901555 :       NewTableArray[NewBucket] = Bucket;
     254    54901555 :       NewHashArray[NewBucket] = FullHash;
     255    54901555 :       if (I == BucketNo)
     256             :         NewBucketNo = NewBucket;
     257             :     }
     258             :   }
     259             : 
     260     1988171 :   free(TheTable);
     261             : 
     262     1988171 :   TheTable = NewTableArray;
     263     1988171 :   NumBuckets = NewSize;
     264     1988171 :   NumTombstones = 0;
     265     1988171 :   return NewBucketNo;
     266             : }

Generated by: LCOV version 1.13