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