1 //===--- CStringMap.cpp - CString Hash table map implementation -----------===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
10 // This file implements the CStringMap class.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/ADT/CStringMap.h"
18 CStringMapVisitor::~CStringMapVisitor() {
21 CStringMapImpl::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;
28 TheTable = new ItemBucket[NumBuckets]();
29 memset(TheTable, 0, NumBuckets*sizeof(ItemBucket));
33 /// HashString - Compute a hash code for the specified string.
35 static unsigned HashString(const char *Start, const char *End) {
36 unsigned int Result = 0;
37 // Perl hash function.
39 Result = Result * 33 + *Start++;
40 Result = Result + (Result >> 5);
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
49 unsigned 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);
55 unsigned ProbeAmt = 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;
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
72 char *ItemStr = (char*)BucketItem+ItemSize;
73 if (strlen(ItemStr) == unsigned(NameEnd-NameStart) &&
74 memcmp(ItemStr, NameStart, (NameEnd-NameStart)) == 0) {
80 // Okay, we didn't find the item. Probe to the next bucket.
81 BucketNo = (BucketNo+ProbeAmt) & (HTSize-1);
83 // Use quadratic probing, it has fewer clumping artifacts than linear
84 // probing and has good cache behavior in the common case.
89 /// RehashTable - Grow the table, redistributing values into the buckets with
90 /// the appropriate mod-of-hashtable-size.
91 void CStringMapImpl::RehashTable() {
92 unsigned NewSize = NumBuckets*2;
93 ItemBucket *NewTableArray = new ItemBucket[NewSize]();
94 memset(NewTableArray, 0, NewSize*sizeof(ItemBucket));
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) {
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;
109 unsigned ProbeSize = 1;
111 NewBucket = (NewBucket + ProbeSize++) & (NewSize-1);
112 } while (NewTableArray[NewBucket].Item);
114 // Finally found a slot. Fill it in.
115 NewTableArray[NewBucket].Item = IB->Item;
116 NewTableArray[NewBucket].FullHashValue = FullHash;
122 TheTable = NewTableArray;
123 NumBuckets = NewSize;
127 /// VisitEntries - This method walks through all of the items,
128 /// invoking Visitor.Visit for each of them.
129 void 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);