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