MapVector.h Source File (original) (raw)

17#ifndef LLVM_ADT_MAPVECTOR_H

18#define LLVM_ADT_MAPVECTOR_H

22#include

23#include

24#include

25#include <type_traits>

26#include

28namespace llvm {

33template <typename KeyT, typename ValueT,

37public:

39 using value_type = typename VectorType::value_type;

40 using size_type = typename VectorType::size_type;

42 using iterator = typename VectorType::iterator;

49 Map.clear();

50 return std::move(Vector);

51 }

56 [[nodiscard]] size_type size() const { return Vector.size(); }

61 Map.reserve(NumEntries);

62 Vector.reserve(NumEntries);

63 }

67 [[nodiscard]] iterator end() { return Vector.end(); }

72 return Vector.rbegin();

73 }

77 [[nodiscard]] bool empty() const { return Vector.empty(); }

79 [[nodiscard]] std::pair<KeyT, ValueT> &front() { return Vector.front(); }

80 [[nodiscard]] const std::pair<KeyT, ValueT> &front() const {

81 return Vector.front();

82 }

83 [[nodiscard]] std::pair<KeyT, ValueT> &back() { return Vector.back(); }

84 [[nodiscard]] const std::pair<KeyT, ValueT> &back() const {

85 return Vector.back();

86 }

89 Map.clear();

90 Vector.clear();

91 }

99 return try_emplace_impl(Key).first->second;

100 }

101

106

107

109 static_assert(std::is_copy_constructible_v,

110 "Cannot call lookup() if ValueT is not copyable.");

111 typename MapType::const_iterator Pos = Map.find(Key);

112 return Pos == Map.end()? ValueT() : Vector[Pos->second].second;

113 }

114

115 template <typename... Ts>

117 return try_emplace_impl(Key, std::forward(Args)...);

118 }

119 template <typename... Ts>

121 return try_emplace_impl(std::move(Key), std::forward(Args)...);

122 }

123

124 std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {

125 return try_emplace_impl(KV.first, KV.second);

126 }

127 std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) {

128 return try_emplace_impl(std::move(KV.first), std::move(KV.second));

129 }

130

131 template

134 if (!Ret.second)

135 Ret.first->second = std::forward(Val);

136 return Ret;

137 }

138 template

140 auto Ret = try_emplace(std::move(Key), std::forward(Val));

141 if (!Ret.second)

142 Ret.first->second = std::forward(Val);

143 return Ret;

144 }

145

147 return Map.find(Key) != Map.end();

148 }

149

153

155 typename MapType::const_iterator Pos = Map.find(Key);

156 return Pos == Map.end() ? Vector.end() : (Vector.begin() + Pos->second);

157 }

158

160 typename MapType::const_iterator Pos = Map.find(Key);

161 return Pos == Map.end() ? Vector.end() : (Vector.begin() + Pos->second);

162 }

163

164

165

167 auto Pos = Map.find(Key);

168 assert(Pos != Map.end() && "MapVector::at failed due to a missing key");

169 return Vector[Pos->second].second;

170 }

171

172

173

174 [[nodiscard]] const ValueT &at(const KeyT &Key) const {

175 auto Pos = Map.find(Key);

176 assert(Pos != Map.end() && "MapVector::at failed due to a missing key");

177 return Vector[Pos->second].second;

178 }

179

180

182 typename MapType::iterator Pos = Map.find(Vector.back().first);

183 Map.erase(Pos);

184 Vector.pop_back();

185 }

186

187

188

189

190

191

192

193

194 typename VectorType::iterator erase(typename VectorType::iterator Iterator) {

195 Map.erase(Iterator->first);

196 auto Next = Vector.erase(Iterator);

197 if (Next == Vector.end())

199

200

201 size_t Index = Next - Vector.begin();

202 for (auto &I : Map) {

203 assert(I.second != Index && "Index was already erased!");

204 if (I.second > Index)

205 --I.second;

206 }

208 }

209

210

211

212

214 auto Iterator = find(Key);

215 if (Iterator == end())

216 return 0;

218 return 1;

219 }

220

221

222

223

224

226

227private:

228 MapType Map;

230

231 static_assert(

232 std::is_integral_v<typename MapType::mapped_type>,

233 "The mapped_type of the specified Map must be an integral type");

234

235 template <typename KeyArgT, typename... Ts>

236 std::pair<iterator, bool> try_emplace_impl(KeyArgT &&Key, Ts &&...Args) {

237 auto [It, Inserted] = Map.try_emplace(Key);

238 if (Inserted) {

239 It->second = Vector.size();

240 Vector.emplace_back(std::piecewise_construct,

241 std::forward_as_tuple(std::forward(Key)),

242 std::forward_as_tuple(std::forward(Args)...));

243 return {std::prev(end()), true};

244 }

245 return {begin() + It->second, false};

246 }

247};

248

249template <typename KeyT, typename ValueT, typename MapType, typename VectorType>

250template

252 auto O = Vector.begin();

253 for (auto I = O, E = Vector.end(); I != E; ++I) {

254 if (Pred(*I)) {

255

256 Map.erase(I->first);

257 continue;

258 }

259

260 if (I != O) {

261

262 *O = std::move(*I);

263 Map[O->first] = O - Vector.begin();

264 }

265 ++O;

266 }

267

268 Vector.erase(O, Vector.end());

269}

270

271

272

273template <typename KeyT, typename ValueT, unsigned N>

275 : MapVector<KeyT, ValueT, SmallDenseMap<KeyT, unsigned, N>,

276 SmallVector<std::pair<KeyT, ValueT>, N>> {

277};

278

279}

280

281#endif

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

This file defines the DenseMap class.

This file defines the SmallVector class.

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

This class implements a map that also provides access to all stored values in a deterministic order.

Definition MapVector.h:36

std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)

Definition MapVector.h:120

size_type count(const KeyT &Key) const

Definition MapVector.h:150

typename VectorType::iterator iterator

Definition MapVector.h:42

iterator end()

Definition MapVector.h:67

void pop_back()

Remove the last element from the vector.

Definition MapVector.h:181

const_reverse_iterator rbegin() const

Definition MapVector.h:71

void swap(MapVector &RHS)

Definition MapVector.h:93

reverse_iterator rend()

Definition MapVector.h:74

ValueT & operator[](const KeyT &Key)

Definition MapVector.h:98

const_iterator end() const

Definition MapVector.h:68

const ValueT & at(const KeyT &Key) const

at - Return the entry for the specified key, or abort if no such entry exists.

Definition MapVector.h:174

VectorType::iterator erase(typename VectorType::iterator Iterator)

Remove the element given by Iterator.

Definition MapVector.h:194

std::pair< iterator, bool > insert_or_assign(KeyT &&Key, V &&Val)

Definition MapVector.h:139

VectorType takeVector()

Clear the MapVector and return the underlying vector.

Definition MapVector.h:48

typename VectorType::size_type size_type

Definition MapVector.h:40

const std::pair< KeyT, ValueT > & back() const

Definition MapVector.h:84

const std::pair< KeyT, ValueT > & front() const

Definition MapVector.h:80

typename VectorType::const_reverse_iterator const_reverse_iterator

Definition MapVector.h:45

typename VectorType::value_type value_type

Definition MapVector.h:39

iterator find(const KeyT &Key)

Definition MapVector.h:154

auto values() const

Definition MapVector.h:105

auto values()

Definition MapVector.h:104

auto keys()

Definition MapVector.h:102

void remove_if(Predicate Pred)

Remove the elements that match the predicate.

bool contains(const KeyT &Key) const

Definition MapVector.h:146

bool empty() const

Definition MapVector.h:77

const_iterator begin() const

Definition MapVector.h:66

iterator begin()

Definition MapVector.h:65

ValueT & at(const KeyT &Key)

at - Return the entry for the specified key, or abort if no such entry exists.

Definition MapVector.h:166

std::pair< iterator, bool > insert_or_assign(const KeyT &Key, V &&Val)

Definition MapVector.h:132

const_iterator find(const KeyT &Key) const

Definition MapVector.h:159

KeyT key_type

Definition MapVector.h:38

std::pair< iterator, bool > try_emplace(const KeyT &Key, Ts &&...Args)

Definition MapVector.h:116

std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)

Definition MapVector.h:124

ArrayRef< value_type > getArrayRef() const

Returns an array reference of the underlying vector.

Definition MapVector.h:54

ValueT lookup(const KeyT &Key) const

Definition MapVector.h:108

void reserve(size_type NumEntries)

Grow the MapVector so that it can contain at least NumEntries items before resizing again.

Definition MapVector.h:60

typename VectorType::reverse_iterator reverse_iterator

Definition MapVector.h:44

size_type size() const

Definition MapVector.h:56

size_type erase(const KeyT &Key)

Remove all elements with the key value Key.

Definition MapVector.h:213

typename VectorType::const_iterator const_iterator

Definition MapVector.h:43

std::pair< KeyT, ValueT > & front()

Definition MapVector.h:79

void clear()

Definition MapVector.h:88

std::pair< iterator, bool > insert(std::pair< KeyT, ValueT > &&KV)

Definition MapVector.h:127

const_reverse_iterator rend() const

Definition MapVector.h:75

auto keys() const

Definition MapVector.h:103

reverse_iterator rbegin()

Definition MapVector.h:70

std::pair< KeyT, ValueT > & back()

Definition MapVector.h:83

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

Base class of all SIMD vector types.

This is an optimization pass for GlobalISel generic memory operations.

auto make_first_range(ContainerTy &&c)

Given a container of pairs, return a range over the first elements.

LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key

FunctionAddr VTableAddr Next

auto make_second_range(ContainerTy &&c)

Given a container of pairs, return a range over the second elements.

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.

A MapVector that performs no allocations if smaller than a certain size.

Definition MapVector.h:276