LLVM API Documentation
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 }