StringMap.cpp revision 23d7b3611759c7fb3a853dfce3ee3d43ef5ca67d
1//===--- CStringMap.cpp - CString Hash table map implementation -----------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by Chris Lattner and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the CStringMap class. 11// 12//===----------------------------------------------------------------------===// 13 14#include "llvm/ADT/CStringMap.h" 15#include <cassert> 16using namespace llvm; 17 18CStringMapVisitor::~CStringMapVisitor() { 19} 20 21CStringMapImpl::CStringMapImpl(unsigned InitSize, unsigned itemSize) { 22 assert((InitSize & (InitSize-1)) == 0 && 23 "Init Size must be a power of 2 or zero!"); 24 NumBuckets = InitSize ? InitSize : 512; 25 ItemSize = itemSize; 26 NumItems = 0; 27 28 TheTable = new ItemBucket[NumBuckets](); 29 memset(TheTable, 0, NumBuckets*sizeof(ItemBucket)); 30} 31 32 33/// HashString - Compute a hash code for the specified string. 34/// 35static unsigned HashString(const char *Start, const char *End) { 36 unsigned int Result = 0; 37 // Perl hash function. 38 while (Start != End) 39 Result = Result * 33 + *Start++; 40 Result = Result + (Result >> 5); 41 return Result; 42} 43 44/// LookupBucketFor - Look up the bucket that the specified string should end 45/// up in. If it already exists as a key in the map, the Item pointer for the 46/// specified bucket will be non-null. Otherwise, it will be null. In either 47/// case, the FullHashValue field of the bucket will be set to the hash value 48/// of the string. 49unsigned CStringMapImpl::LookupBucketFor(const char *NameStart, 50 const char *NameEnd) { 51 unsigned HTSize = NumBuckets; 52 unsigned FullHashValue = HashString(NameStart, NameEnd); 53 unsigned BucketNo = FullHashValue & (HTSize-1); 54 55 unsigned ProbeAmt = 1; 56 while (1) { 57 ItemBucket &Bucket = TheTable[BucketNo]; 58 void *BucketItem = Bucket.Item; 59 // If we found an empty bucket, this key isn't in the table yet, return it. 60 if (BucketItem == 0) { 61 Bucket.FullHashValue = FullHashValue; 62 return BucketNo; 63 } 64 65 // If the full hash value matches, check deeply for a match. The common 66 // case here is that we are only looking at the buckets (for item info 67 // being non-null and for the full hash value) not at the items. This 68 // is important for cache locality. 69 if (Bucket.FullHashValue == FullHashValue) { 70 // Do the comparison like this because NameStart isn't necessarily 71 // null-terminated! 72 char *ItemStr = (char*)BucketItem+ItemSize; 73 if (strlen(ItemStr) == unsigned(NameEnd-NameStart) && 74 memcmp(ItemStr, NameStart, (NameEnd-NameStart)) == 0) { 75 // We found a match! 76 return BucketNo; 77 } 78 } 79 80 // Okay, we didn't find the item. Probe to the next bucket. 81 BucketNo = (BucketNo+ProbeAmt) & (HTSize-1); 82 83 // Use quadratic probing, it has fewer clumping artifacts than linear 84 // probing and has good cache behavior in the common case. 85 ++ProbeAmt; 86 } 87} 88 89/// RehashTable - Grow the table, redistributing values into the buckets with 90/// the appropriate mod-of-hashtable-size. 91void CStringMapImpl::RehashTable() { 92 unsigned NewSize = NumBuckets*2; 93 ItemBucket *NewTableArray = new ItemBucket[NewSize](); 94 memset(NewTableArray, 0, NewSize*sizeof(ItemBucket)); 95 96 // Rehash all the items into their new buckets. Luckily :) we already have 97 // the hash values available, so we don't have to rehash any strings. 98 for (ItemBucket *IB = TheTable, *E = TheTable+NumBuckets; IB != E; ++IB) { 99 if (IB->Item) { 100 // Fast case, bucket available. 101 unsigned FullHash = IB->FullHashValue; 102 unsigned NewBucket = FullHash & (NewSize-1); 103 if (NewTableArray[NewBucket].Item == 0) { 104 NewTableArray[FullHash & (NewSize-1)].Item = IB->Item; 105 NewTableArray[FullHash & (NewSize-1)].FullHashValue = FullHash; 106 continue; 107 } 108 109 unsigned ProbeSize = 1; 110 do { 111 NewBucket = (NewBucket + ProbeSize++) & (NewSize-1); 112 } while (NewTableArray[NewBucket].Item); 113 114 // Finally found a slot. Fill it in. 115 NewTableArray[NewBucket].Item = IB->Item; 116 NewTableArray[NewBucket].FullHashValue = FullHash; 117 } 118 } 119 120 delete[] TheTable; 121 122 TheTable = NewTableArray; 123 NumBuckets = NewSize; 124} 125 126 127/// VisitEntries - This method walks through all of the items, 128/// invoking Visitor.Visit for each of them. 129void CStringMapImpl::VisitEntries(const CStringMapVisitor &Visitor) const { 130 for (ItemBucket *IB = TheTable, *E = TheTable+NumBuckets; IB != E; ++IB) { 131 if (void *Id = IB->Item) 132 Visitor.Visit((char*)Id + ItemSize, Id); 133 } 134} 135