aboutsummaryrefslogtreecommitdiffstats
path: root/lib/Support/StringMap.cpp
blob: 0c61732a61b307996080b910da932eadb9f4867a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
//===--- StringMap.cpp - String Hash table map implementation -------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the StringMap class.
//
//===----------------------------------------------------------------------===//

#include "llvm/ADT/StringMap.h"
#include <cassert>
using namespace llvm;

StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) {
  ItemSize = itemSize;
  
  // If a size is specified, initialize the table with that many buckets.
  if (InitSize) {
    init(InitSize);
    return;
  }
  
  // Otherwise, initialize it with zero buckets to avoid the allocation.
  TheTable = 0;
  NumBuckets = 0;
  NumItems = 0;
  NumTombstones = 0;
}

void StringMapImpl::init(unsigned InitSize) {
  assert((InitSize & (InitSize-1)) == 0 &&
         "Init Size must be a power of 2 or zero!");
  NumBuckets = InitSize ? InitSize : 16;
  NumItems = 0;
  NumTombstones = 0;
  
  TheTable = (ItemBucket*)calloc(NumBuckets+1, sizeof(ItemBucket));
  
  // Allocate one extra bucket, set it to look filled so the iterators stop at
  // end.
  TheTable[NumBuckets].Item = (StringMapEntryBase*)2;
}


/// HashString - Compute a hash code for the specified string.
///
static unsigned HashString(const char *Start, const char *End) {
  // Bernstein hash function.
  unsigned int Result = 0;
  // TODO: investigate whether a modified bernstein hash function performs
  // better: http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
  //   X*33+c -> X*33^c
  while (Start != End)
    Result = Result * 33 + *Start++;
  Result = Result + (Result >> 5);
  return Result;
}

/// LookupBucketFor - Look up the bucket that the specified string should end
/// up in.  If it already exists as a key in the map, the Item pointer for the
/// specified bucket will be non-null.  Otherwise, it will be null.  In either
/// case, the FullHashValue field of the bucket will be set to the hash value
/// of the string.
unsigned StringMapImpl::LookupBucketFor(const char *NameStart,
                                        const char *NameEnd) {
  unsigned HTSize = NumBuckets;
  if (HTSize == 0) {  // Hash table unallocated so far?
    init(16);
    HTSize = NumBuckets;
  }
  unsigned FullHashValue = HashString(NameStart, NameEnd);
  unsigned BucketNo = FullHashValue & (HTSize-1);
  
  unsigned ProbeAmt = 1;
  int FirstTombstone = -1;
  while (1) {
    ItemBucket &Bucket = TheTable[BucketNo];
    StringMapEntryBase *BucketItem = Bucket.Item;
    // If we found an empty bucket, this key isn't in the table yet, return it.
    if (BucketItem == 0) {
      // If we found a tombstone, we want to reuse the tombstone instead of an
      // empty bucket.  This reduces probing.
      if (FirstTombstone != -1) {
        TheTable[FirstTombstone].FullHashValue = FullHashValue;
        return FirstTombstone;
      }
      
      Bucket.FullHashValue = FullHashValue;
      return BucketNo;
    }
    
    if (BucketItem == getTombstoneVal()) {
      // Skip over tombstones.  However, remember the first one we see.
      if (FirstTombstone == -1) FirstTombstone = BucketNo;
    } else if (Bucket.FullHashValue == FullHashValue) {
      // If the full hash value matches, check deeply for a match.  The common
      // case here is that we are only looking at the buckets (for item info
      // being non-null and for the full hash value) not at the items.  This
      // is important for cache locality.
      
      // Do the comparison like this because NameStart isn't necessarily
      // null-terminated!
      char *ItemStr = (char*)BucketItem+ItemSize;
      unsigned ItemStrLen = BucketItem->getKeyLength();
      if (unsigned(NameEnd-NameStart) == ItemStrLen &&
          memcmp(ItemStr, NameStart, ItemStrLen) == 0) {
        // We found a match!
        return BucketNo;
      }
    }
    
    // Okay, we didn't find the item.  Probe to the next bucket.
    BucketNo = (BucketNo+ProbeAmt) & (HTSize-1);
    
    // Use quadratic probing, it has fewer clumping artifacts than linear
    // probing and has good cache behavior in the common case.
    ++ProbeAmt;
  }
}


/// FindKey - Look up the bucket that contains the specified key. If it exists
/// in the map, return the bucket number of the key.  Otherwise return -1.
/// This does not modify the map.
int StringMapImpl::FindKey(const char *KeyStart, const char *KeyEnd) const {
  unsigned HTSize = NumBuckets;
  if (HTSize == 0) return -1;  // Really empty table?
  unsigned FullHashValue = HashString(KeyStart, KeyEnd);
  unsigned BucketNo = FullHashValue & (HTSize-1);
  
  unsigned ProbeAmt = 1;
  while (1) {
    ItemBucket &Bucket = TheTable[BucketNo];
    StringMapEntryBase *BucketItem = Bucket.Item;
    // If we found an empty bucket, this key isn't in the table yet, return.
    if (BucketItem == 0)
      return -1;
    
    if (BucketItem == getTombstoneVal()) {
      // Ignore tombstones.
    } else if (Bucket.FullHashValue == FullHashValue) {
      // If the full hash value matches, check deeply for a match.  The common
      // case here is that we are only looking at the buckets (for item info
      // being non-null and for the full hash value) not at the items.  This
      // is important for cache locality.
      
      // Do the comparison like this because NameStart isn't necessarily
      // null-terminated!
      char *ItemStr = (char*)BucketItem+ItemSize;
      unsigned ItemStrLen = BucketItem->getKeyLength();
      if (unsigned(KeyEnd-KeyStart) == ItemStrLen &&
          memcmp(ItemStr, KeyStart, ItemStrLen) == 0) {
        // We found a match!
        return BucketNo;
      }
    }
    
    // Okay, we didn't find the item.  Probe to the next bucket.
    BucketNo = (BucketNo+ProbeAmt) & (HTSize-1);
    
    // Use quadratic probing, it has fewer clumping artifacts than linear
    // probing and has good cache behavior in the common case.
    ++ProbeAmt;
  }
}

/// RemoveKey - Remove the specified StringMapEntry from the table, but do not
/// delete it.  This aborts if the value isn't in the table.
void StringMapImpl::RemoveKey(StringMapEntryBase *V) {
  const char *VStr = (char*)V + ItemSize;
  StringMapEntryBase *V2 = RemoveKey(VStr, VStr+V->getKeyLength());
  V2 = V2;
  assert(V == V2 && "Didn't find key?");
}

/// RemoveKey - Remove the StringMapEntry for the specified key from the
/// table, returning it.  If the key is not in the table, this returns null.
StringMapEntryBase *StringMapImpl::RemoveKey(const char *KeyStart,
                                             const char *KeyEnd) {
  int Bucket = FindKey(KeyStart, KeyEnd);
  if (Bucket == -1) return 0;
  
  StringMapEntryBase *Result = TheTable[Bucket].Item;
  TheTable[Bucket].Item = getTombstoneVal();
  --NumItems;
  ++NumTombstones;
  return Result;
}



/// RehashTable - Grow the table, redistributing values into the buckets with
/// the appropriate mod-of-hashtable-size.
void StringMapImpl::RehashTable() {
  unsigned NewSize = NumBuckets*2;
  // Allocate one extra bucket which will always be non-empty.  This allows the
  // iterators to stop at end.
  ItemBucket *NewTableArray =(ItemBucket*)calloc(NewSize+1, sizeof(ItemBucket));
  NewTableArray[NewSize].Item = (StringMapEntryBase*)2;
  
  // Rehash all the items into their new buckets.  Luckily :) we already have
  // the hash values available, so we don't have to rehash any strings.
  for (ItemBucket *IB = TheTable, *E = TheTable+NumBuckets; IB != E; ++IB) {
    if (IB->Item && IB->Item != getTombstoneVal()) {
      // Fast case, bucket available.
      unsigned FullHash = IB->FullHashValue;
      unsigned NewBucket = FullHash & (NewSize-1);
      if (NewTableArray[NewBucket].Item == 0) {
        NewTableArray[FullHash & (NewSize-1)].Item = IB->Item;
        NewTableArray[FullHash & (NewSize-1)].FullHashValue = FullHash;
        continue;
      }
      
      // Otherwise probe for a spot.
      unsigned ProbeSize = 1;
      do {
        NewBucket = (NewBucket + ProbeSize++) & (NewSize-1);
      } while (NewTableArray[NewBucket].Item);
      
      // Finally found a slot.  Fill it in.
      NewTableArray[NewBucket].Item = IB->Item;
      NewTableArray[NewBucket].FullHashValue = FullHash;
    }
  }
  
  free(TheTable);
  
  TheTable = NewTableArray;
  NumBuckets = NewSize;
}