LCOV - code coverage report
Current view: top level - lib/Support - StringMap.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 93 93 100.0 %
Date: 2018-09-23 13:06:45 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      482080 :   return NextPowerOf2(NumEntries * 4 / 3 + 1);
      32             : }
      33             : 
      34     1088702 : StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) {
      35     1088702 :   ItemSize = itemSize;
      36             : 
      37             :   // If a size is specified, initialize the table with that many buckets.
      38     1088702 :   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      482080 :     init(getMinBucketToReserveForEntries(InitSize));
      43      482080 :     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     4784607 : void StringMapImpl::init(unsigned InitSize) {
      54             :   assert((InitSize & (InitSize-1)) == 0 &&
      55             :          "Init Size must be a power of 2 or zero!");
      56             : 
      57     4784607 :   unsigned NewNumBuckets = InitSize ? InitSize : 16;
      58     4784607 :   NumItems = 0;
      59     4784607 :   NumTombstones = 0;
      60             : 
      61     4784606 :   TheTable = static_cast<StringMapEntryBase **>(
      62     4784607 :       safe_calloc(NewNumBuckets+1,
      63             :                   sizeof(StringMapEntryBase **) + sizeof(unsigned)));
      64             : 
      65             :   // Set the member only if TheTable was successfully allocated
      66     4784606 :   NumBuckets = NewNumBuckets;
      67             : 
      68             :   // Allocate one extra bucket, set it to look filled so the iterators stop at
      69             :   // end.
      70     4784606 :   TheTable[NumBuckets] = (StringMapEntryBase*)2;
      71     4784606 : }
      72             : 
      73             : /// LookupBucketFor - Look up the bucket that the specified string should end
      74             : /// up in.  If it already exists as a key in the map, the Item pointer for the
      75             : /// specified bucket will be non-null.  Otherwise, it will be null.  In either
      76             : /// case, the FullHashValue field of the bucket will be set to the hash value
      77             : /// of the string.
      78  1503895222 : unsigned StringMapImpl::LookupBucketFor(StringRef Name) {
      79  1503895222 :   unsigned HTSize = NumBuckets;
      80  1503895222 :   if (HTSize == 0) {  // Hash table unallocated so far?
      81     4278485 :     init(16);
      82     4278488 :     HTSize = NumBuckets;
      83             :   }
      84             :   unsigned FullHashValue = djbHash(Name, 0);
      85  1503895225 :   unsigned BucketNo = FullHashValue & (HTSize-1);
      86  1503895225 :   unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
      87             : 
      88             :   unsigned ProbeAmt = 1;
      89             :   int FirstTombstone = -1;
      90             :   while (true) {
      91  2415867175 :     StringMapEntryBase *BucketItem = TheTable[BucketNo];
      92             :     // If we found an empty bucket, this key isn't in the table yet, return it.
      93  2415867175 :     if (LLVM_LIKELY(!BucketItem)) {
      94             :       // If we found a tombstone, we want to reuse the tombstone instead of an
      95             :       // empty bucket.  This reduces probing.
      96   492764983 :       if (FirstTombstone != -1) {
      97      254898 :         HashTable[FirstTombstone] = FullHashValue;
      98      254898 :         return FirstTombstone;
      99             :       }
     100             : 
     101   492510085 :       HashTable[BucketNo] = FullHashValue;
     102   492510085 :       return BucketNo;
     103             :     }
     104             : 
     105  1923102192 :     if (BucketItem == getTombstoneVal()) {
     106             :       // Skip over tombstones.  However, remember the first one we see.
     107      350439 :       if (FirstTombstone == -1) FirstTombstone = BucketNo;
     108  1922751753 :     } else if (LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) {
     109             :       // If the full hash value matches, check deeply for a match.  The common
     110             :       // case here is that we are only looking at the buckets (for item info
     111             :       // being non-null and for the full hash value) not at the items.  This
     112             :       // is important for cache locality.
     113             : 
     114             :       // Do the comparison like this because Name isn't necessarily
     115             :       // null-terminated!
     116  1012170770 :       char *ItemStr = (char*)BucketItem+ItemSize;
     117  1012170770 :       if (Name == StringRef(ItemStr, BucketItem->getKeyLength())) {
     118             :         // We found a match!
     119  1011130242 :         return BucketNo;
     120             :       }
     121             :     }
     122             : 
     123             :     // Okay, we didn't find the item.  Probe to the next bucket.
     124   911971950 :     BucketNo = (BucketNo+ProbeAmt) & (HTSize-1);
     125             : 
     126             :     // Use quadratic probing, it has fewer clumping artifacts than linear
     127             :     // probing and has good cache behavior in the common case.
     128   911971950 :     ++ProbeAmt;
     129   911971950 :   }
     130             : }
     131             : 
     132             : /// FindKey - Look up the bucket that contains the specified key. If it exists
     133             : /// in the map, return the bucket number of the key.  Otherwise return -1.
     134             : /// This does not modify the map.
     135    56954918 : int StringMapImpl::FindKey(StringRef Key) const {
     136    56954918 :   unsigned HTSize = NumBuckets;
     137    56954918 :   if (HTSize == 0) return -1;  // Really empty table?
     138             :   unsigned FullHashValue = djbHash(Key, 0);
     139    47003648 :   unsigned BucketNo = FullHashValue & (HTSize-1);
     140    47003648 :   unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
     141             : 
     142             :   unsigned ProbeAmt = 1;
     143             :   while (true) {
     144    98008255 :     StringMapEntryBase *BucketItem = TheTable[BucketNo];
     145             :     // If we found an empty bucket, this key isn't in the table yet, return.
     146    98008255 :     if (LLVM_LIKELY(!BucketItem))
     147             :       return -1;
     148             : 
     149    78102907 :     if (BucketItem == getTombstoneVal()) {
     150             :       // Ignore tombstones.
     151    74709554 :     } else if (LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) {
     152             :       // If the full hash value matches, check deeply for a match.  The common
     153             :       // case here is that we are only looking at the buckets (for item info
     154             :       // being non-null and for the full hash value) not at the items.  This
     155             :       // is important for cache locality.
     156             : 
     157             :       // Do the comparison like this because NameStart isn't necessarily
     158             :       // null-terminated!
     159    27098499 :       char *ItemStr = (char*)BucketItem+ItemSize;
     160    27098499 :       if (Key == StringRef(ItemStr, BucketItem->getKeyLength())) {
     161             :         // We found a match!
     162    27098300 :         return BucketNo;
     163             :       }
     164             :     }
     165             : 
     166             :     // Okay, we didn't find the item.  Probe to the next bucket.
     167    51004607 :     BucketNo = (BucketNo+ProbeAmt) & (HTSize-1);
     168             : 
     169             :     // Use quadratic probing, it has fewer clumping artifacts than linear
     170             :     // probing and has good cache behavior in the common case.
     171    51004607 :     ++ProbeAmt;
     172    51004607 :   }
     173             : }
     174             : 
     175             : /// RemoveKey - Remove the specified StringMapEntry from the table, but do not
     176             : /// delete it.  This aborts if the value isn't in the table.
     177     5638504 : void StringMapImpl::RemoveKey(StringMapEntryBase *V) {
     178     5638504 :   const char *VStr = (char*)V + ItemSize;
     179    11277008 :   StringMapEntryBase *V2 = RemoveKey(StringRef(VStr, V->getKeyLength()));
     180             :   (void)V2;
     181             :   assert(V == V2 && "Didn't find key?");
     182     5638511 : }
     183             : 
     184             : /// RemoveKey - Remove the StringMapEntry for the specified key from the
     185             : /// table, returning it.  If the key is not in the table, this returns null.
     186     5638504 : StringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) {
     187     5638504 :   int Bucket = FindKey(Key);
     188     5638507 :   if (Bucket == -1) return nullptr;
     189             : 
     190     5638507 :   StringMapEntryBase *Result = TheTable[Bucket];
     191     5638507 :   TheTable[Bucket] = getTombstoneVal();
     192     5638507 :   --NumItems;
     193     5638507 :   ++NumTombstones;
     194             :   assert(NumItems + NumTombstones <= NumBuckets);
     195             : 
     196     5638507 :   return Result;
     197             : }
     198             : 
     199             : /// RehashTable - Grow the table, redistributing values into the buckets with
     200             : /// the appropriate mod-of-hashtable-size.
     201   492764188 : unsigned StringMapImpl::RehashTable(unsigned BucketNo) {
     202             :   unsigned NewSize;
     203   492764188 :   unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
     204             : 
     205             :   // If the hash table is now more than 3/4 full, or if fewer than 1/8 of
     206             :   // the buckets are empty (meaning that many are filled with tombstones),
     207             :   // grow/rehash the table.
     208   492764188 :   if (LLVM_UNLIKELY(NumItems * 4 > NumBuckets * 3)) {
     209     2630705 :     NewSize = NumBuckets*2;
     210   490133483 :   } else if (LLVM_UNLIKELY(NumBuckets - (NumItems + NumTombstones) <=
     211             :                            NumBuckets / 8)) {
     212             :     NewSize = NumBuckets;
     213             :   } else {
     214             :     return BucketNo;
     215             :   }
     216             : 
     217             :   unsigned NewBucketNo = BucketNo;
     218             :   // Allocate one extra bucket which will always be non-empty.  This allows the
     219             :   // iterators to stop at end.
     220             :   auto NewTableArray = static_cast<StringMapEntryBase **>(
     221     2633149 :       safe_calloc(NewSize+1, sizeof(StringMapEntryBase *) + sizeof(unsigned)));
     222             : 
     223     2633146 :   unsigned *NewHashArray = (unsigned *)(NewTableArray + NewSize + 1);
     224     2633146 :   NewTableArray[NewSize] = (StringMapEntryBase*)2;
     225             : 
     226             :   // Rehash all the items into their new buckets.  Luckily :) we already have
     227             :   // the hash values available, so we don't have to rehash any strings.
     228   490960830 :   for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
     229   488327684 :     StringMapEntryBase *Bucket = TheTable[I];
     230   488327684 :     if (Bucket && Bucket != getTombstoneVal()) {
     231             :       // Fast case, bucket available.
     232   368874119 :       unsigned FullHash = HashTable[I];
     233   368874119 :       unsigned NewBucket = FullHash & (NewSize-1);
     234   368874119 :       if (!NewTableArray[NewBucket]) {
     235   298930826 :         NewTableArray[FullHash & (NewSize-1)] = Bucket;
     236   298930826 :         NewHashArray[FullHash & (NewSize-1)] = FullHash;
     237   298930826 :         if (I == BucketNo)
     238             :           NewBucketNo = NewBucket;
     239   298930826 :         continue;
     240             :       }
     241             : 
     242             :       // Otherwise probe for a spot.
     243             :       unsigned ProbeSize = 1;
     244             :       do {
     245   117333483 :         NewBucket = (NewBucket + ProbeSize++) & (NewSize-1);
     246   117333483 :       } while (NewTableArray[NewBucket]);
     247             : 
     248             :       // Finally found a slot.  Fill it in.
     249    69943293 :       NewTableArray[NewBucket] = Bucket;
     250    69943293 :       NewHashArray[NewBucket] = FullHash;
     251    69943293 :       if (I == BucketNo)
     252             :         NewBucketNo = NewBucket;
     253             :     }
     254             :   }
     255             : 
     256     2633146 :   free(TheTable);
     257             : 
     258     2633146 :   TheTable = NewTableArray;
     259     2633146 :   NumBuckets = NewSize;
     260     2633146 :   NumTombstones = 0;
     261     2633146 :   return NewBucketNo;
     262             : }

Generated by: LCOV version 1.13