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,

34 typename MapType = DenseMap<KeyT, unsigned>,

35 typename VectorType = SmallVector<std::pair<KeyT, ValueT>, 0>>

37 MapType Map;

40 static_assert(

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

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

44public:

46 using value_type = typename VectorType::value_type;

47 using size_type = typename VectorType::size_type;

49 using iterator = typename VectorType::iterator;

56 Map.clear();

57 return std::move(Vector);

58 }

65 Map.reserve(NumEntries);

66 Vector.reserve(NumEntries);

67 }

80 return Vector.empty();

81 }

83 std::pair<KeyT, ValueT> &front() { return Vector.front(); }

84 const std::pair<KeyT, ValueT> &front() const { return Vector.front(); }

85 std::pair<KeyT, ValueT> &back() { return Vector.back(); }

86 const std::pair<KeyT, ValueT> &back() const { return Vector.back(); }

89 Map.clear();

91 }

96 }

99 std::pair<KeyT, typename MapType::mapped_type> Pair = std::make_pair(Key, 0);

100 std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);

101 auto &I = Result.first->second;

102 if (Result.second) {

103 Vector.push_back(std::make_pair(Key, ValueT()));

105 }

107 }

108

109

111 static_assert(std::is_copy_constructible_v,

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

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

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

115 }

116

117 template <typename... Ts>

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

119 auto [It, Inserted] = Map.insert(std::make_pair(Key, 0));

120 if (Inserted) {

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

122 Vector.emplace_back(std::piecewise_construct, std::forward_as_tuple(Key),

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

124 return std::make_pair(std::prev(end()), true);

125 }

126 return std::make_pair(begin() + It->second, false);

127 }

128 template <typename... Ts>

130 auto [It, Inserted] = Map.insert(std::make_pair(Key, 0));

131 if (Inserted) {

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

133 Vector.emplace_back(std::piecewise_construct,

134 std::forward_as_tuple(std::move(Key)),

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

136 return std::make_pair(std::prev(end()), true);

137 }

138 return std::make_pair(begin() + It->second, false);

139 }

140

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

143 }

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

145 return try_emplace(std::move(KV.first), std::move(KV.second));

146 }

147

148 template

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

151 if (!Ret.second)

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

153 return Ret;

154 }

155 template

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

158 if (!Ret.second)

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

160 return Ret;

161 }

162

163 bool contains(const KeyT &Key) const { return Map.find(Key) != Map.end(); }

164

166

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

169 return Pos == Map.end()? Vector.end() :

170 (Vector.begin() + Pos->second);

171 }

172

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

175 return Pos == Map.end()? Vector.end() :

176 (Vector.begin() + Pos->second);

177 }

178

179

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

182 Map.erase(Pos);

184 }

185

186

187

188

189

190

191

192

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

194 Map.erase(Iterator->first);

195 auto Next = Vector.erase(Iterator);

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

197 return Next;

198

199

201 for (auto &I : Map) {

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

203 if (I.second > Index)

204 --I.second;

205 }

206 return Next;

207 }

208

209

210

211

213 auto Iterator = find(Key);

214 if (Iterator == end())

215 return 0;

217 return 1;

218 }

219

220

221

222

223

224 template void remove_if(Predicate Pred);

225};

226

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

228template

230 auto O = Vector.begin();

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

232 if (Pred(*I)) {

233

234 Map.erase(I->first);

235 continue;

236 }

237

238 if (I != O) {

239

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

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

242 }

243 ++O;

244 }

245

247}

248

249

250

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

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

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

255};

256

257}

258

259#endif

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

This file defines the DenseMap class.

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

This file defines the SmallVector class.

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

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

size_type count(const KeyT &Key) const

typename VectorType::iterator iterator

void pop_back()

Remove the last element from the vector.

const_reverse_iterator rbegin() const

void swap(MapVector &RHS)

ValueT & operator[](const KeyT &Key)

const_iterator end() const

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

Remove the element given by Iterator.

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

VectorType takeVector()

Clear the MapVector and return the underlying vector.

typename VectorType::size_type size_type

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

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

typename VectorType::const_reverse_iterator const_reverse_iterator

typename VectorType::value_type value_type

iterator find(const KeyT &Key)

void remove_if(Predicate Pred)

Remove the elements that match the predicate.

bool contains(const KeyT &Key) const

const_iterator begin() const

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

const_iterator find(const KeyT &Key) const

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

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

ValueT lookup(const KeyT &Key) const

void reserve(size_type NumEntries)

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

typename VectorType::reverse_iterator reverse_iterator

size_type erase(const KeyT &Key)

Remove all elements with the key value Key.

typename VectorType::const_iterator const_iterator

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

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

const_reverse_iterator rend() const

reverse_iterator rbegin()

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

Base class of all SIMD vector types.

This is an optimization pass for GlobalISel generic memory operations.

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.