Bug Summary

File:lib/Support/StringPool.cpp
Warning:line 176, column 41
Called C++ object pointer is null

Annotated Source Code

[?] Use j/k keys for keyboard navigation

/build/llvm-toolchain-snapshot-6.0~svn321639/lib/Support/StringPool.cpp

→
1//===-- StringPool.cpp - Interned string pool -----------------------------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements the StringPool class.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/Support/StringPool.h"
15#include "llvm/ADT/StringRef.h"
16
17using namespace llvm;
18
19StringPool::StringPool() {}
20
21StringPool::~StringPool() {
22 assert(InternTable.empty() && "PooledStringPtr leaked!")(static_cast <bool> (InternTable.empty() && "PooledStringPtr leaked!"
) ? void (0) : __assert_fail ("InternTable.empty() && \"PooledStringPtr leaked!\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/Support/StringPool.cpp"
, 22, __extension__ __PRETTY_FUNCTION__));
23}
24
25PooledStringPtr StringPool::intern(StringRef Key) {
26 table_t::iterator I = InternTable.find(Key);
27 if (I != InternTable.end())
1
Assuming the condition is false
→
2
←
Taking false branch
→
28 return PooledStringPtr(&*I);
29
30 entry_t *S = entry_t::Create(Key);
3
←
Calling 'StringMapEntry::Create'
→
31 S->getValue().Pool = this;
32 InternTable.insert(S);
33
34 return PooledStringPtr(S);
35}
←

/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/ADT/StringMap.h

1//===- StringMap.h - String Hash table map interface ------------*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defines the StringMap class.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_ADT_STRINGMAP_H
15#define LLVM_ADT_STRINGMAP_H
16
17#include "llvm/ADT/StringRef.h"
18#include "llvm/ADT/iterator.h"
19#include "llvm/ADT/iterator_range.h"
20#include "llvm/Support/Allocator.h"
21#include "llvm/Support/PointerLikeTypeTraits.h"
22#include "llvm/Support/ErrorHandling.h"
23#include <algorithm>
24#include <cassert>
25#include <cstdint>
26#include <cstdlib>
27#include <cstring>
28#include <initializer_list>
29#include <iterator>
30#include <utility>
31
32namespace llvm {
33
34template<typename ValueTy> class StringMapConstIterator;
35template<typename ValueTy> class StringMapIterator;
36template<typename ValueTy> class StringMapKeyIterator;
37
38/// StringMapEntryBase - Shared base class of StringMapEntry instances.
39class StringMapEntryBase {
40 unsigned StrLen;
41
42public:
43 explicit StringMapEntryBase(unsigned Len) : StrLen(Len) {}
44
45 unsigned getKeyLength() const { return StrLen; }
46};
47
48/// StringMapImpl - This is the base class of StringMap that is shared among
49/// all of its instantiations.
50class StringMapImpl {
51protected:
52 // Array of NumBuckets pointers to entries, null pointers are holes.
53 // TheTable[NumBuckets] contains a sentinel value for easy iteration. Followed
54 // by an array of the actual hash values as unsigned integers.
55 StringMapEntryBase **TheTable = nullptr;
56 unsigned NumBuckets = 0;
57 unsigned NumItems = 0;
58 unsigned NumTombstones = 0;
59 unsigned ItemSize;
60
61protected:
62 explicit StringMapImpl(unsigned itemSize)
63 : ItemSize(itemSize) {}
64 StringMapImpl(StringMapImpl &&RHS)
65 : TheTable(RHS.TheTable), NumBuckets(RHS.NumBuckets),
66 NumItems(RHS.NumItems), NumTombstones(RHS.NumTombstones),
67 ItemSize(RHS.ItemSize) {
68 RHS.TheTable = nullptr;
69 RHS.NumBuckets = 0;
70 RHS.NumItems = 0;
71 RHS.NumTombstones = 0;
72 }
73
74 StringMapImpl(unsigned InitSize, unsigned ItemSize);
75 unsigned RehashTable(unsigned BucketNo = 0);
76
77 /// LookupBucketFor - Look up the bucket that the specified string should end
78 /// up in. If it already exists as a key in the map, the Item pointer for the
79 /// specified bucket will be non-null. Otherwise, it will be null. In either
80 /// case, the FullHashValue field of the bucket will be set to the hash value
81 /// of the string.
82 unsigned LookupBucketFor(StringRef Key);
83
84 /// FindKey - Look up the bucket that contains the specified key. If it exists
85 /// in the map, return the bucket number of the key. Otherwise return -1.
86 /// This does not modify the map.
87 int FindKey(StringRef Key) const;
88
89 /// RemoveKey - Remove the specified StringMapEntry from the table, but do not
90 /// delete it. This aborts if the value isn't in the table.
91 void RemoveKey(StringMapEntryBase *V);
92
93 /// RemoveKey - Remove the StringMapEntry for the specified key from the
94 /// table, returning it. If the key is not in the table, this returns null.
95 StringMapEntryBase *RemoveKey(StringRef Key);
96
97 /// Allocate the table with the specified number of buckets and otherwise
98 /// setup the map as empty.
99 void init(unsigned Size);
100
101public:
102 static StringMapEntryBase *getTombstoneVal() {
103 uintptr_t Val = static_cast<uintptr_t>(-1);
104 Val <<= PointerLikeTypeTraits<StringMapEntryBase *>::NumLowBitsAvailable;
105 return reinterpret_cast<StringMapEntryBase *>(Val);
106 }
107
108 unsigned getNumBuckets() const { return NumBuckets; }
109 unsigned getNumItems() const { return NumItems; }
110
111 bool empty() const { return NumItems == 0; }
112 unsigned size() const { return NumItems; }
113
114 void swap(StringMapImpl &Other) {
115 std::swap(TheTable, Other.TheTable);
116 std::swap(NumBuckets, Other.NumBuckets);
117 std::swap(NumItems, Other.NumItems);
118 std::swap(NumTombstones, Other.NumTombstones);
119 }
120};
121
122/// StringMapEntry - This is used to represent one value that is inserted into
123/// a StringMap. It contains the Value itself and the key: the string length
124/// and data.
125template<typename ValueTy>
126class StringMapEntry : public StringMapEntryBase {
127public:
128 ValueTy second;
129
130 explicit StringMapEntry(unsigned strLen)
131 : StringMapEntryBase(strLen), second() {}
132 template <typename... InitTy>
133 StringMapEntry(unsigned strLen, InitTy &&... InitVals)
134 : StringMapEntryBase(strLen), second(std::forward<InitTy>(InitVals)...) {}
135 StringMapEntry(StringMapEntry &E) = delete;
136
137 StringRef getKey() const {
138 return StringRef(getKeyData(), getKeyLength());
139 }
140
141 const ValueTy &getValue() const { return second; }
142 ValueTy &getValue() { return second; }
143
144 void setValue(const ValueTy &V) { second = V; }
145
146 /// getKeyData - Return the start of the string data that is the key for this
147 /// value. The string data is always stored immediately after the
148 /// StringMapEntry object.
149 const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);}
150
151 StringRef first() const { return StringRef(getKeyData(), getKeyLength()); }
152
153 /// Create a StringMapEntry for the specified key construct the value using
154 /// \p InitiVals.
155 template <typename AllocatorTy, typename... InitTy>
156 static StringMapEntry *Create(StringRef Key, AllocatorTy &Allocator,
157 InitTy &&... InitVals) {
158 unsigned KeyLength = Key.size();
159
160 // Allocate a new item with space for the string at the end and a null
161 // terminator.
162 unsigned AllocSize = static_cast<unsigned>(sizeof(StringMapEntry))+
163 KeyLength+1;
164 unsigned Alignment = alignof(StringMapEntry);
165
166 StringMapEntry *NewItem =
8
←
'NewItem' initialized here
→
167 static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment));
6
←
Calling 'MallocAllocator::Allocate'
→
7
←
Returning from 'MallocAllocator::Allocate'
→
168
169 if (NewItem == nullptr)
9
←
Assuming the condition is true
→
10
←
Assuming pointer value is null
→
11
←
Taking true branch
→
170 report_bad_alloc_error("Allocation of StringMap entry failed.");
171
172 // Construct the value.
173 new (NewItem) StringMapEntry(KeyLength, std::forward<InitTy>(InitVals)...);
174
175 // Copy the string information.
176 char *StrBuffer = const_cast<char*>(NewItem->getKeyData());
12
←
Called C++ object pointer is null
177 if (KeyLength > 0)
178 memcpy(StrBuffer, Key.data(), KeyLength);
179 StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients.
180 return NewItem;
181 }
182
183 /// Create - Create a StringMapEntry with normal malloc/free.
184 template <typename... InitType>
185 static StringMapEntry *Create(StringRef Key, InitType &&... InitVal) {
186 MallocAllocator A;
187 return Create(Key, A, std::forward<InitType>(InitVal)...);
5
←
Calling 'StringMapEntry::Create'
→
188 }
189
190 static StringMapEntry *Create(StringRef Key) {
191 return Create(Key, ValueTy());
4
←
Calling 'StringMapEntry::Create'
→
192 }
193
194 /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded
195 /// into a StringMapEntry, return the StringMapEntry itself.
196 static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) {
197 char *Ptr = const_cast<char*>(KeyData) - sizeof(StringMapEntry<ValueTy>);
198 return *reinterpret_cast<StringMapEntry*>(Ptr);
199 }
200
201 /// Destroy - Destroy this StringMapEntry, releasing memory back to the
202 /// specified allocator.
203 template<typename AllocatorTy>
204 void Destroy(AllocatorTy &Allocator) {
205 // Free memory referenced by the item.
206 unsigned AllocSize =
207 static_cast<unsigned>(sizeof(StringMapEntry)) + getKeyLength() + 1;
208 this->~StringMapEntry();
209 Allocator.Deallocate(static_cast<void *>(this), AllocSize);
210 }
211
212 /// Destroy this object, releasing memory back to the malloc allocator.
213 void Destroy() {
214 MallocAllocator A;
215 Destroy(A);
216 }
217};
218
219/// StringMap - This is an unconventional map that is specialized for handling
220/// keys that are "strings", which are basically ranges of bytes. This does some
221/// funky memory allocation and hashing things to make it extremely efficient,
222/// storing the string data *after* the value in the map.
223template<typename ValueTy, typename AllocatorTy = MallocAllocator>
224class StringMap : public StringMapImpl {
225 AllocatorTy Allocator;
226
227public:
228 using MapEntryTy = StringMapEntry<ValueTy>;
229
230 StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {}
231
232 explicit StringMap(unsigned InitialSize)
233 : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {}
234
235 explicit StringMap(AllocatorTy A)
236 : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {}
237
238 StringMap(unsigned InitialSize, AllocatorTy A)
239 : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))),
240 Allocator(A) {}
241
242 StringMap(std::initializer_list<std::pair<StringRef, ValueTy>> List)
243 : StringMapImpl(List.size(), static_cast<unsigned>(sizeof(MapEntryTy))) {
244 for (const auto &P : List) {
245 insert(P);
246 }
247 }
248
249 StringMap(StringMap &&RHS)
250 : StringMapImpl(std::move(RHS)), Allocator(std::move(RHS.Allocator)) {}
251
252 StringMap(const StringMap &RHS) :
253 StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))),
254 Allocator(RHS.Allocator) {
255 if (RHS.empty())
256 return;
257
258 // Allocate TheTable of the same size as RHS's TheTable, and set the
259 // sentinel appropriately (and NumBuckets).
260 init(RHS.NumBuckets);
261 unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1),
262 *RHSHashTable = (unsigned *)(RHS.TheTable + NumBuckets + 1);
263
264 NumItems = RHS.NumItems;
265 NumTombstones = RHS.NumTombstones;
266 for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
267 StringMapEntryBase *Bucket = RHS.TheTable[I];
268 if (!Bucket || Bucket == getTombstoneVal()) {
269 TheTable[I] = Bucket;
270 continue;
271 }
272
273 TheTable[I] = MapEntryTy::Create(
274 static_cast<MapEntryTy *>(Bucket)->getKey(), Allocator,
275 static_cast<MapEntryTy *>(Bucket)->getValue());
276 HashTable[I] = RHSHashTable[I];
277 }
278
279 // Note that here we've copied everything from the RHS into this object,
280 // tombstones included. We could, instead, have re-probed for each key to
281 // instantiate this new object without any tombstone buckets. The
282 // assumption here is that items are rarely deleted from most StringMaps,
283 // and so tombstones are rare, so the cost of re-probing for all inputs is
284 // not worthwhile.
285 }
286
287 StringMap &operator=(StringMap RHS) {
288 StringMapImpl::swap(RHS);
289 std::swap(Allocator, RHS.Allocator);
290 return *this;
291 }
292
293 ~StringMap() {
294 // Delete all the elements in the map, but don't reset the elements
295 // to default values. This is a copy of clear(), but avoids unnecessary
296 // work not required in the destructor.
297 if (!empty()) {
298 for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
299 StringMapEntryBase *Bucket = TheTable[I];
300 if (Bucket && Bucket != getTombstoneVal()) {
301 static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
302 }
303 }
304 }
305 free(TheTable);
306 }
307
308 AllocatorTy &getAllocator() { return Allocator; }
309 const AllocatorTy &getAllocator() const { return Allocator; }
310
311 using key_type = const char*;
312 using mapped_type = ValueTy;
313 using value_type = StringMapEntry<ValueTy>;
314 using size_type = size_t;
315
316 using const_iterator = StringMapConstIterator<ValueTy>;
317 using iterator = StringMapIterator<ValueTy>;
318
319 iterator begin() {
320 return iterator(TheTable, NumBuckets == 0);
321 }
322 iterator end() {
323 return iterator(TheTable+NumBuckets, true);
324 }
325 const_iterator begin() const {
326 return const_iterator(TheTable, NumBuckets == 0);
327 }
328 const_iterator end() const {
329 return const_iterator(TheTable+NumBuckets, true);
330 }
331
332 iterator_range<StringMapKeyIterator<ValueTy>> keys() const {
333 return make_range(StringMapKeyIterator<ValueTy>(begin()),
334 StringMapKeyIterator<ValueTy>(end()));
335 }
336
337 iterator find(StringRef Key) {
338 int Bucket = FindKey(Key);
339 if (Bucket == -1) return end();
340 return iterator(TheTable+Bucket, true);
341 }
342
343 const_iterator find(StringRef Key) const {
344 int Bucket = FindKey(Key);
345 if (Bucket == -1) return end();
346 return const_iterator(TheTable+Bucket, true);
347 }
348
349 /// lookup - Return the entry for the specified key, or a default
350 /// constructed value if no such entry exists.
351 ValueTy lookup(StringRef Key) const {
352 const_iterator it = find(Key);
353 if (it != end())
354 return it->second;
355 return ValueTy();
356 }
357
358 /// Lookup the ValueTy for the \p Key, or create a default constructed value
359 /// if the key is not in the map.
360 ValueTy &operator[](StringRef Key) { return try_emplace(Key).first->second; }
361
362 /// count - Return 1 if the element is in the map, 0 otherwise.
363 size_type count(StringRef Key) const {
364 return find(Key) == end() ? 0 : 1;
365 }
366
367 /// insert - Insert the specified key/value pair into the map. If the key
368 /// already exists in the map, return false and ignore the request, otherwise
369 /// insert it and return true.
370 bool insert(MapEntryTy *KeyValue) {
371 unsigned BucketNo = LookupBucketFor(KeyValue->getKey());
372 StringMapEntryBase *&Bucket = TheTable[BucketNo];
373 if (Bucket && Bucket != getTombstoneVal())
374 return false; // Already exists in map.
375
376 if (Bucket == getTombstoneVal())
377 --NumTombstones;
378 Bucket = KeyValue;
379 ++NumItems;
380 assert(NumItems + NumTombstones <= NumBuckets)(static_cast <bool> (NumItems + NumTombstones <= NumBuckets
) ? void (0) : __assert_fail ("NumItems + NumTombstones <= NumBuckets"
, "/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/ADT/StringMap.h"
, 380, __extension__ __PRETTY_FUNCTION__));
381
382 RehashTable();
383 return true;
384 }
385
386 /// insert - Inserts the specified key/value pair into the map if the key
387 /// isn't already in the map. The bool component of the returned pair is true
388 /// if and only if the insertion takes place, and the iterator component of
389 /// the pair points to the element with key equivalent to the key of the pair.
390 std::pair<iterator, bool> insert(std::pair<StringRef, ValueTy> KV) {
391 return try_emplace(KV.first, std::move(KV.second));
392 }
393
394 /// Emplace a new element for the specified key into the map if the key isn't
395 /// already in the map. The bool component of the returned pair is true
396 /// if and only if the insertion takes place, and the iterator component of
397 /// the pair points to the element with key equivalent to the key of the pair.
398 template <typename... ArgsTy>
399 std::pair<iterator, bool> try_emplace(StringRef Key, ArgsTy &&... Args) {
400 unsigned BucketNo = LookupBucketFor(Key);
401 StringMapEntryBase *&Bucket = TheTable[BucketNo];
402 if (Bucket && Bucket != getTombstoneVal())
403 return std::make_pair(iterator(TheTable + BucketNo, false),
404 false); // Already exists in map.
405
406 if (Bucket == getTombstoneVal())
407 --NumTombstones;
408 Bucket = MapEntryTy::Create(Key, Allocator, std::forward<ArgsTy>(Args)...);
409 ++NumItems;
410 assert(NumItems + NumTombstones <= NumBuckets)(static_cast <bool> (NumItems + NumTombstones <= NumBuckets
) ? void (0) : __assert_fail ("NumItems + NumTombstones <= NumBuckets"
, "/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/ADT/StringMap.h"
, 410, __extension__ __PRETTY_FUNCTION__));
411
412 BucketNo = RehashTable(BucketNo);
413 return std::make_pair(iterator(TheTable + BucketNo, false), true);
414 }
415
416 // clear - Empties out the StringMap
417 void clear() {
418 if (empty()) return;
419
420 // Zap all values, resetting the keys back to non-present (not tombstone),
421 // which is safe because we're removing all elements.
422 for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
423 StringMapEntryBase *&Bucket = TheTable[I];
424 if (Bucket && Bucket != getTombstoneVal()) {
425 static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
426 }
427 Bucket = nullptr;
428 }
429
430 NumItems = 0;
431 NumTombstones = 0;
432 }
433
434 /// remove - Remove the specified key/value pair from the map, but do not
435 /// erase it. This aborts if the key is not in the map.
436 void remove(MapEntryTy *KeyValue) {
437 RemoveKey(KeyValue);
438 }
439
440 void erase(iterator I) {
441 MapEntryTy &V = *I;
442 remove(&V);
443 V.Destroy(Allocator);
444 }
445
446 bool erase(StringRef Key) {
447 iterator I = find(Key);
448 if (I == end()) return false;
449 erase(I);
450 return true;
451 }
452};
453
454template <typename DerivedTy, typename ValueTy>
455class StringMapIterBase
456 : public iterator_facade_base<DerivedTy, std::forward_iterator_tag,
457 ValueTy> {
458protected:
459 StringMapEntryBase **Ptr = nullptr;
460
461public:
462 StringMapIterBase() = default;
463
464 explicit StringMapIterBase(StringMapEntryBase **Bucket,
465 bool NoAdvance = false)
466 : Ptr(Bucket) {
467 if (!NoAdvance) AdvancePastEmptyBuckets();
468 }
469
470 DerivedTy &operator=(const DerivedTy &Other) {
471 Ptr = Other.Ptr;
472 return static_cast<DerivedTy &>(*this);
473 }
474
475 bool operator==(const DerivedTy &RHS) const { return Ptr == RHS.Ptr; }
476
477 DerivedTy &operator++() { // Preincrement
478 ++Ptr;
479 AdvancePastEmptyBuckets();
480 return static_cast<DerivedTy &>(*this);
481 }
482
483 DerivedTy operator++(int) { // Post-increment
484 DerivedTy Tmp(Ptr);
485 ++*this;
486 return Tmp;
487 }
488
489private:
490 void AdvancePastEmptyBuckets() {
491 while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal())
492 ++Ptr;
493 }
494};
495
496template <typename ValueTy>
497class StringMapConstIterator
498 : public StringMapIterBase<StringMapConstIterator<ValueTy>,
499 const StringMapEntry<ValueTy>> {
500 using base = StringMapIterBase<StringMapConstIterator<ValueTy>,
501 const StringMapEntry<ValueTy>>;
502
503public:
504 StringMapConstIterator() = default;
505 explicit StringMapConstIterator(StringMapEntryBase **Bucket,
506 bool NoAdvance = false)
507 : base(Bucket, NoAdvance) {}
508
509 const StringMapEntry<ValueTy> &operator*() const {
510 return *static_cast<const StringMapEntry<ValueTy> *>(*this->Ptr);
511 }
512};
513
514template <typename ValueTy>
515class StringMapIterator : public StringMapIterBase<StringMapIterator<ValueTy>,
516 StringMapEntry<ValueTy>> {
517 using base =
518 StringMapIterBase<StringMapIterator<ValueTy>, StringMapEntry<ValueTy>>;
519
520public:
521 StringMapIterator() = default;
522 explicit StringMapIterator(StringMapEntryBase **Bucket,
523 bool NoAdvance = false)
524 : base(Bucket, NoAdvance) {}
525
526 StringMapEntry<ValueTy> &operator*() const {
527 return *static_cast<StringMapEntry<ValueTy> *>(*this->Ptr);
528 }
529
530 operator StringMapConstIterator<ValueTy>() const {
531 return StringMapConstIterator<ValueTy>(this->Ptr, true);
532 }
533};
534
535template <typename ValueTy>
536class StringMapKeyIterator
537 : public iterator_adaptor_base<StringMapKeyIterator<ValueTy>,
538 StringMapConstIterator<ValueTy>,
539 std::forward_iterator_tag, StringRef> {
540 using base = iterator_adaptor_base<StringMapKeyIterator<ValueTy>,
541 StringMapConstIterator<ValueTy>,
542 std::forward_iterator_tag, StringRef>;
543
544public:
545 StringMapKeyIterator() = default;
546 explicit StringMapKeyIterator(StringMapConstIterator<ValueTy> Iter)
547 : base(std::move(Iter)) {}
548
549 StringRef &operator*() {
550 Key = this->wrapped()->getKey();
551 return Key;
552 }
553
554private:
555 StringRef Key;
556};
557
558} // end namespace llvm
559
560#endif // LLVM_ADT_STRINGMAP_H