Home | History | Annotate | Download | only in Support 
      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 <cassert>
     17 using namespace llvm;
     18 
     19 StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) {
     20   ItemSize = itemSize;
     21 
     22   // If a size is specified, initialize the table with that many buckets.
     23   if (InitSize) {
     24     init(InitSize);
     25     return;
     26   }
     27 
     28   // Otherwise, initialize it with zero buckets to avoid the allocation.
     29   TheTable = 0;
     30   NumBuckets = 0;
     31   NumItems = 0;
     32   NumTombstones = 0;
     33 }
     34 
     35 void StringMapImpl::init(unsigned InitSize) {
     36   assert((InitSize & (InitSize-1)) == 0 &&
     37          "Init Size must be a power of 2 or zero!");
     38   NumBuckets = InitSize ? InitSize : 16;
     39   NumItems = 0;
     40   NumTombstones = 0;
     41 
     42   TheTable = (StringMapEntryBase **)calloc(NumBuckets+1,
     43                                            sizeof(StringMapEntryBase **) +
     44                                            sizeof(unsigned));
     45 
     46   // Allocate one extra bucket, set it to look filled so the iterators stop at
     47   // end.
     48   TheTable[NumBuckets] = (StringMapEntryBase*)2;
     49 }
     50 
     51 
     52 /// LookupBucketFor - Look up the bucket that the specified string should end
     53 /// up in.  If it already exists as a key in the map, the Item pointer for the
     54 /// specified bucket will be non-null.  Otherwise, it will be null.  In either
     55 /// case, the FullHashValue field of the bucket will be set to the hash value
     56 /// of the string.
     57 unsigned StringMapImpl::LookupBucketFor(StringRef Name) {
     58   unsigned HTSize = NumBuckets;
     59   if (HTSize == 0) {  // Hash table unallocated so far?
     60     init(16);
     61     HTSize = NumBuckets;
     62   }
     63   unsigned FullHashValue = HashString(Name);
     64   unsigned BucketNo = FullHashValue & (HTSize-1);
     65   unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
     66 
     67   unsigned ProbeAmt = 1;
     68   int FirstTombstone = -1;
     69   while (1) {
     70     StringMapEntryBase *BucketItem = TheTable[BucketNo];
     71     // If we found an empty bucket, this key isn't in the table yet, return it.
     72     if (BucketItem == 0) {
     73       // If we found a tombstone, we want to reuse the tombstone instead of an
     74       // empty bucket.  This reduces probing.
     75       if (FirstTombstone != -1) {
     76         HashTable[FirstTombstone] = FullHashValue;
     77         return FirstTombstone;
     78       }
     79 
     80       HashTable[BucketNo] = FullHashValue;
     81       return BucketNo;
     82     }
     83 
     84     if (BucketItem == getTombstoneVal()) {
     85       // Skip over tombstones.  However, remember the first one we see.
     86       if (FirstTombstone == -1) FirstTombstone = BucketNo;
     87     } else if (HashTable[BucketNo] == FullHashValue) {
     88       // If the full hash value matches, check deeply for a match.  The common
     89       // case here is that we are only looking at the buckets (for item info
     90       // being non-null and for the full hash value) not at the items.  This
     91       // is important for cache locality.
     92 
     93       // Do the comparison like this because Name isn't necessarily
     94       // null-terminated!
     95       char *ItemStr = (char*)BucketItem+ItemSize;
     96       if (Name == StringRef(ItemStr, BucketItem->getKeyLength())) {
     97         // We found a match!
     98         return BucketNo;
     99       }
    100     }
    101 
    102     // Okay, we didn't find the item.  Probe to the next bucket.
    103     BucketNo = (BucketNo+ProbeAmt) & (HTSize-1);
    104 
    105     // Use quadratic probing, it has fewer clumping artifacts than linear
    106     // probing and has good cache behavior in the common case.
    107     ++ProbeAmt;
    108   }
    109 }
    110 
    111 
    112 /// FindKey - Look up the bucket that contains the specified key. If it exists
    113 /// in the map, return the bucket number of the key.  Otherwise return -1.
    114 /// This does not modify the map.
    115 int StringMapImpl::FindKey(StringRef Key) const {
    116   unsigned HTSize = NumBuckets;
    117   if (HTSize == 0) return -1;  // Really empty table?
    118   unsigned FullHashValue = HashString(Key);
    119   unsigned BucketNo = FullHashValue & (HTSize-1);
    120   unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
    121 
    122   unsigned ProbeAmt = 1;
    123   while (1) {
    124     StringMapEntryBase *BucketItem = TheTable[BucketNo];
    125     // If we found an empty bucket, this key isn't in the table yet, return.
    126     if (BucketItem == 0)
    127       return -1;
    128 
    129     if (BucketItem == getTombstoneVal()) {
    130       // Ignore tombstones.
    131     } else if (HashTable[BucketNo] == FullHashValue) {
    132       // If the full hash value matches, check deeply for a match.  The common
    133       // case here is that we are only looking at the buckets (for item info
    134       // being non-null and for the full hash value) not at the items.  This
    135       // is important for cache locality.
    136 
    137       // Do the comparison like this because NameStart isn't necessarily
    138       // null-terminated!
    139       char *ItemStr = (char*)BucketItem+ItemSize;
    140       if (Key == StringRef(ItemStr, BucketItem->getKeyLength())) {
    141         // We found a match!
    142         return BucketNo;
    143       }
    144     }
    145 
    146     // Okay, we didn't find the item.  Probe to the next bucket.
    147     BucketNo = (BucketNo+ProbeAmt) & (HTSize-1);
    148 
    149     // Use quadratic probing, it has fewer clumping artifacts than linear
    150     // probing and has good cache behavior in the common case.
    151     ++ProbeAmt;
    152   }
    153 }
    154 
    155 /// RemoveKey - Remove the specified StringMapEntry from the table, but do not
    156 /// delete it.  This aborts if the value isn't in the table.
    157 void StringMapImpl::RemoveKey(StringMapEntryBase *V) {
    158   const char *VStr = (char*)V + ItemSize;
    159   StringMapEntryBase *V2 = RemoveKey(StringRef(VStr, V->getKeyLength()));
    160   (void)V2;
    161   assert(V == V2 && "Didn't find key?");
    162 }
    163 
    164 /// RemoveKey - Remove the StringMapEntry for the specified key from the
    165 /// table, returning it.  If the key is not in the table, this returns null.
    166 StringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) {
    167   int Bucket = FindKey(Key);
    168   if (Bucket == -1) return 0;
    169 
    170   StringMapEntryBase *Result = TheTable[Bucket];
    171   TheTable[Bucket] = getTombstoneVal();
    172   --NumItems;
    173   ++NumTombstones;
    174   assert(NumItems + NumTombstones <= NumBuckets);
    175 
    176   return Result;
    177 }
    178 
    179 
    180 
    181 /// RehashTable - Grow the table, redistributing values into the buckets with
    182 /// the appropriate mod-of-hashtable-size.
    183 void StringMapImpl::RehashTable() {
    184   unsigned NewSize;
    185   unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
    186 
    187   // If the hash table is now more than 3/4 full, or if fewer than 1/8 of
    188   // the buckets are empty (meaning that many are filled with tombstones),
    189   // grow/rehash the table.
    190   if (NumItems*4 > NumBuckets*3) {
    191     NewSize = NumBuckets*2;
    192   } else if (NumBuckets-(NumItems+NumTombstones) < NumBuckets/8) {
    193     NewSize = NumBuckets;
    194   } else {
    195     return;
    196   }
    197 
    198   // Allocate one extra bucket which will always be non-empty.  This allows the
    199   // iterators to stop at end.
    200   StringMapEntryBase **NewTableArray =
    201     (StringMapEntryBase **)calloc(NewSize+1, sizeof(StringMapEntryBase *) +
    202                                              sizeof(unsigned));
    203   unsigned *NewHashArray = (unsigned *)(NewTableArray + NewSize + 1);
    204   NewTableArray[NewSize] = (StringMapEntryBase*)2;
    205 
    206   // Rehash all the items into their new buckets.  Luckily :) we already have
    207   // the hash values available, so we don't have to rehash any strings.
    208   for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
    209     StringMapEntryBase *Bucket = TheTable[I];
    210     if (Bucket && Bucket != getTombstoneVal()) {
    211       // Fast case, bucket available.
    212       unsigned FullHash = HashTable[I];
    213       unsigned NewBucket = FullHash & (NewSize-1);
    214       if (NewTableArray[NewBucket] == 0) {
    215         NewTableArray[FullHash & (NewSize-1)] = Bucket;
    216         NewHashArray[FullHash & (NewSize-1)] = FullHash;
    217         continue;
    218       }
    219 
    220       // Otherwise probe for a spot.
    221       unsigned ProbeSize = 1;
    222       do {
    223         NewBucket = (NewBucket + ProbeSize++) & (NewSize-1);
    224       } while (NewTableArray[NewBucket]);
    225 
    226       // Finally found a slot.  Fill it in.
    227       NewTableArray[NewBucket] = Bucket;
    228       NewHashArray[NewBucket] = FullHash;
    229     }
    230   }
    231 
    232   free(TheTable);
    233 
    234   TheTable = NewTableArray;
    235   NumBuckets = NewSize;
    236   NumTombstones = 0;
    237 }
    238