LLVM API Documentation

StringMap.cpp

Go to the documentation of this file.
00001 //===--- StringMap.cpp - String Hash table map implementation -------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements the StringMap class.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #include "llvm/ADT/StringMap.h"
00015 #include <cassert>
00016 using namespace llvm;
00017 
00018 StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) {
00019   ItemSize = itemSize;
00020   
00021   // If a size is specified, initialize the table with that many buckets.
00022   if (InitSize) {
00023     init(InitSize);
00024     return;
00025   }
00026   
00027   // Otherwise, initialize it with zero buckets to avoid the allocation.
00028   TheTable = 0;
00029   NumBuckets = 0;
00030   NumItems = 0;
00031   NumTombstones = 0;
00032 }
00033 
00034 void StringMapImpl::init(unsigned InitSize) {
00035   assert((InitSize & (InitSize-1)) == 0 &&
00036          "Init Size must be a power of 2 or zero!");
00037   NumBuckets = InitSize ? InitSize : 16;
00038   NumItems = 0;
00039   NumTombstones = 0;
00040   
00041   TheTable = (ItemBucket*)calloc(NumBuckets+1, sizeof(ItemBucket));
00042   
00043   // Allocate one extra bucket, set it to look filled so the iterators stop at
00044   // end.
00045   TheTable[NumBuckets].Item = (StringMapEntryBase*)2;
00046 }
00047 
00048 
00049 /// HashString - Compute a hash code for the specified string.
00050 ///
00051 static unsigned HashString(const char *Start, const char *End) {
00052   // Bernstein hash function.
00053   unsigned int Result = 0;
00054   // TODO: investigate whether a modified bernstein hash function performs
00055   // better: http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
00056   //   X*33+c -> X*33^c
00057   while (Start != End)
00058     Result = Result * 33 + *Start++;
00059   Result = Result + (Result >> 5);
00060   return Result;
00061 }
00062 
00063 /// LookupBucketFor - Look up the bucket that the specified string should end
00064 /// up in.  If it already exists as a key in the map, the Item pointer for the
00065 /// specified bucket will be non-null.  Otherwise, it will be null.  In either
00066 /// case, the FullHashValue field of the bucket will be set to the hash value
00067 /// of the string.
00068 unsigned StringMapImpl::LookupBucketFor(const StringRef &Name) {
00069   unsigned HTSize = NumBuckets;
00070   if (HTSize == 0) {  // Hash table unallocated so far?
00071     init(16);
00072     HTSize = NumBuckets;
00073   }
00074   unsigned FullHashValue = HashString(Name.begin(), Name.end());
00075   unsigned BucketNo = FullHashValue & (HTSize-1);
00076   
00077   unsigned ProbeAmt = 1;
00078   int FirstTombstone = -1;
00079   while (1) {
00080     ItemBucket &Bucket = TheTable[BucketNo];
00081     StringMapEntryBase *BucketItem = Bucket.Item;
00082     // If we found an empty bucket, this key isn't in the table yet, return it.
00083     if (BucketItem == 0) {
00084       // If we found a tombstone, we want to reuse the tombstone instead of an
00085       // empty bucket.  This reduces probing.
00086       if (FirstTombstone != -1) {
00087         TheTable[FirstTombstone].FullHashValue = FullHashValue;
00088         return FirstTombstone;
00089       }
00090       
00091       Bucket.FullHashValue = FullHashValue;
00092       return BucketNo;
00093     }
00094     
00095     if (BucketItem == getTombstoneVal()) {
00096       // Skip over tombstones.  However, remember the first one we see.
00097       if (FirstTombstone == -1) FirstTombstone = BucketNo;
00098     } else if (Bucket.FullHashValue == FullHashValue) {
00099       // If the full hash value matches, check deeply for a match.  The common
00100       // case here is that we are only looking at the buckets (for item info
00101       // being non-null and for the full hash value) not at the items.  This
00102       // is important for cache locality.
00103       
00104       // Do the comparison like this because Name isn't necessarily
00105       // null-terminated!
00106       char *ItemStr = (char*)BucketItem+ItemSize;
00107       if (Name == StringRef(ItemStr, BucketItem->getKeyLength())) {
00108         // We found a match!
00109         return BucketNo;
00110       }
00111     }
00112     
00113     // Okay, we didn't find the item.  Probe to the next bucket.
00114     BucketNo = (BucketNo+ProbeAmt) & (HTSize-1);
00115     
00116     // Use quadratic probing, it has fewer clumping artifacts than linear
00117     // probing and has good cache behavior in the common case.
00118     ++ProbeAmt;
00119   }
00120 }
00121 
00122 
00123 /// FindKey - Look up the bucket that contains the specified key. If it exists
00124 /// in the map, return the bucket number of the key.  Otherwise return -1.
00125 /// This does not modify the map.
00126 int StringMapImpl::FindKey(const StringRef &Key) const {
00127   unsigned HTSize = NumBuckets;
00128   if (HTSize == 0) return -1;  // Really empty table?
00129   unsigned FullHashValue = HashString(Key.begin(), Key.end());
00130   unsigned BucketNo = FullHashValue & (HTSize-1);
00131   
00132   unsigned ProbeAmt = 1;
00133   while (1) {
00134     ItemBucket &Bucket = TheTable[BucketNo];
00135     StringMapEntryBase *BucketItem = Bucket.Item;
00136     // If we found an empty bucket, this key isn't in the table yet, return.
00137     if (BucketItem == 0)
00138       return -1;
00139     
00140     if (BucketItem == getTombstoneVal()) {
00141       // Ignore tombstones.
00142     } else if (Bucket.FullHashValue == FullHashValue) {
00143       // If the full hash value matches, check deeply for a match.  The common
00144       // case here is that we are only looking at the buckets (for item info
00145       // being non-null and for the full hash value) not at the items.  This
00146       // is important for cache locality.
00147       
00148       // Do the comparison like this because NameStart isn't necessarily
00149       // null-terminated!
00150       char *ItemStr = (char*)BucketItem+ItemSize;
00151       if (Key == StringRef(ItemStr, BucketItem->getKeyLength())) {
00152         // We found a match!
00153         return BucketNo;
00154       }
00155     }
00156     
00157     // Okay, we didn't find the item.  Probe to the next bucket.
00158     BucketNo = (BucketNo+ProbeAmt) & (HTSize-1);
00159     
00160     // Use quadratic probing, it has fewer clumping artifacts than linear
00161     // probing and has good cache behavior in the common case.
00162     ++ProbeAmt;
00163   }
00164 }
00165 
00166 /// RemoveKey - Remove the specified StringMapEntry from the table, but do not
00167 /// delete it.  This aborts if the value isn't in the table.
00168 void StringMapImpl::RemoveKey(StringMapEntryBase *V) {
00169   const char *VStr = (char*)V + ItemSize;
00170   StringMapEntryBase *V2 = RemoveKey(StringRef(VStr, V->getKeyLength()));
00171   V2 = V2;
00172   assert(V == V2 && "Didn't find key?");
00173 }
00174 
00175 /// RemoveKey - Remove the StringMapEntry for the specified key from the
00176 /// table, returning it.  If the key is not in the table, this returns null.
00177 StringMapEntryBase *StringMapImpl::RemoveKey(const StringRef &Key) {
00178   int Bucket = FindKey(Key);
00179   if (Bucket == -1) return 0;
00180   
00181   StringMapEntryBase *Result = TheTable[Bucket].Item;
00182   TheTable[Bucket].Item = getTombstoneVal();
00183   --NumItems;
00184   ++NumTombstones;
00185   return Result;
00186 }
00187 
00188 
00189 
00190 /// RehashTable - Grow the table, redistributing values into the buckets with
00191 /// the appropriate mod-of-hashtable-size.
00192 void StringMapImpl::RehashTable() {
00193   unsigned NewSize = NumBuckets*2;
00194   // Allocate one extra bucket which will always be non-empty.  This allows the
00195   // iterators to stop at end.
00196   ItemBucket *NewTableArray =(ItemBucket*)calloc(NewSize+1, sizeof(ItemBucket));
00197   NewTableArray[NewSize].Item = (StringMapEntryBase*)2;
00198   
00199   // Rehash all the items into their new buckets.  Luckily :) we already have
00200   // the hash values available, so we don't have to rehash any strings.
00201   for (ItemBucket *IB = TheTable, *E = TheTable+NumBuckets; IB != E; ++IB) {
00202     if (IB->Item && IB->Item != getTombstoneVal()) {
00203       // Fast case, bucket available.
00204       unsigned FullHash = IB->FullHashValue;
00205       unsigned NewBucket = FullHash & (NewSize-1);
00206       if (NewTableArray[NewBucket].Item == 0) {
00207         NewTableArray[FullHash & (NewSize-1)].Item = IB->Item;
00208         NewTableArray[FullHash & (NewSize-1)].FullHashValue = FullHash;
00209         continue;
00210       }
00211       
00212       // Otherwise probe for a spot.
00213       unsigned ProbeSize = 1;
00214       do {
00215         NewBucket = (NewBucket + ProbeSize++) & (NewSize-1);
00216       } while (NewTableArray[NewBucket].Item);
00217       
00218       // Finally found a slot.  Fill it in.
00219       NewTableArray[NewBucket].Item = IB->Item;
00220       NewTableArray[NewBucket].FullHashValue = FullHash;
00221     }
00222   }
00223   
00224   free(TheTable);
00225   
00226   TheTable = NewTableArray;
00227   NumBuckets = NewSize;
00228 }