DenseSet.h Source File (original) (raw)

14#ifndef LLVM_ADT_DENSESET_H

15#define LLVM_ADT_DENSESET_H

21#include

22#include <initializer_list>

23#include

24#include

26namespace llvm {

37public:

42};

53template <typename ValueT, typename MapTy, typename ValueInfoT>

55 static_assert(sizeof(typename MapTy::value_type) == sizeof(ValueT),

56 "DenseMap buckets unexpectedly large!");

57 MapTy TheMap;

59 template

62public:

67 explicit DenseSetImpl(unsigned InitialReserve = 0) : TheMap(InitialReserve) {}

69 template

73 }

77 insert(Elems.begin(), Elems.end());

78 }

80 bool empty() const { return TheMap.empty(); }

82 size_t getMemorySize() const { return TheMap.getMemorySize(); }

92 void clear() { TheMap.clear(); }

95 size_type count(const_arg_type_t V) const { return TheMap.count(V); }

97 bool erase(const ValueT &V) { return TheMap.erase(V); }

100

101

102

103 class ConstIterator;

104

106 typename MapTy::iterator I;

109

110 public:

116

118 Iterator(const typename MapTy::iterator &i) : I(i) {}

119

124

126 ++I;

127 return *this;

128 }

130 auto T = *this;

131 ++I;

132 return T;

133 }

135 return X.I == Y.I;

136 }

138 return X.I != Y.I;

139 }

140 };

141

143 typename MapTy::const_iterator I;

146

147 public:

148 using difference_type = typename MapTy::const_iterator::difference_type;

153

157

160

162 ++I;

163 return *this;

164 }

166 auto T = *this;

167 ++I;

168 return T;

169 }

171 return X.I == Y.I;

172 }

174 return X.I != Y.I;

175 }

176 };

177

180

183

186

190 }

191

192

193 bool contains(const_arg_type_t V) const {

194 return TheMap.find(V) != TheMap.end();

195 }

196

197

198

199

200

201

202 template iterator find_as(const LookupKeyT &Val) {

203 return Iterator(TheMap.find_as(Val));

204 }

205 template

208 }

209

212

215 return TheMap.try_emplace(V, Empty);

216 }

217

220 return TheMap.try_emplace(std::move(V), Empty);

221 }

222

223

224

225 template

227 const LookupKeyT &LookupKey) {

229 }

230 template

231 std::pair<iterator, bool> insert_as(ValueT &&V, const LookupKeyT &LookupKey) {

233 }

234

235

236 template void insert(InputIt I, InputIt E) {

237 for (; I != E; ++I)

239 }

240};

241

242

243

244

245

246

247

248template <typename ValueT, typename MapTy, typename ValueInfoT>

251 if (LHS.size() != RHS.size())

252 return false;

253

254 for (auto &E : LHS)

255 if ( RHS .count(E))

256 return false;

257

258 return true;

259}

260

261

262

263

264template <typename ValueT, typename MapTy, typename ValueInfoT>

267 return !(LHS == RHS);

268}

269

270}

271

272

273template <typename ValueT, typename ValueInfoT = DenseMapInfo>

275 ValueT,

276 DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,

277 detail::DenseSetPair>,

278 ValueInfoT> {

283 ValueInfoT>;

284

285public:

286 using BaseT::BaseT;

287};

288

289

290

291template <typename ValueT, unsigned InlineBuckets = 4,

295 ValueT,

296 SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,

297 ValueInfoT, detail::DenseSetPair>,

298 ValueInfoT> {

303 ValueInfoT>;

304

305public:

306 using BaseT::BaseT;

307};

308

309}

310

311#endif

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

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

This file defines DenseMapInfo traits for DenseMap.

This file defines the DenseMap class.

static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")

static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")

Implements a dense probed hash-table based set.

Implements a dense probed hash-table based set with some number of buckets stored inline.

ConstIterator operator++(int)

const ValueT & operator*() const

friend bool operator!=(const ConstIterator &X, const ConstIterator &Y)

friend bool operator==(const ConstIterator &X, const ConstIterator &Y)

typename MapTy::const_iterator::difference_type difference_type

ConstIterator & operator++()

ConstIterator(const typename MapTy::const_iterator &i)

std::forward_iterator_tag iterator_category

const ValueT * operator->() const

ConstIterator(const Iterator &B)

friend bool operator==(const Iterator &X, const Iterator &Y)

const ValueT & operator*() const

const ValueT * operator->() const

std::forward_iterator_tag iterator_category

friend bool operator!=(const Iterator &X, const Iterator &Y)

typename MapTy::iterator::difference_type difference_type

Iterator(const typename MapTy::iterator &i)

Base class for DenseSet and DenseSmallSet.

const_iterator find(const_arg_type_t< ValueT > V) const

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

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

size_t getMemorySize() const

const_iterator end() const

const_iterator begin() const

iterator find(const_arg_type_t< ValueT > V)

std::pair< iterator, bool > insert_as(const ValueT &V, const LookupKeyT &LookupKey)

Alternative version of insert that uses a different (and possibly less expensive) key type.

void reserve(size_t Size)

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

iterator find_as(const LookupKeyT &Val)

Alternative version of find() which allows a different, and possibly less expensive,...

const_iterator find_as(const LookupKeyT &Val) const

std::pair< iterator, bool > insert_as(ValueT &&V, const LookupKeyT &LookupKey)

void insert(InputIt I, InputIt E)

void swap(DenseSetImpl &RHS)

DenseSetImpl(unsigned InitialReserve=0)

bool contains(const_arg_type_t< ValueT > V) const

Check if the set contains the given element.

DenseSetImpl(const InputIt &I, const InputIt &E)

void resize(size_t Size)

Grow the DenseSet so that it has at least Size buckets.

void erase(ConstIterator CI)

bool erase(const ValueT &V)

DenseSetImpl(std::initializer_list< ValueT > Elems)

size_type count(const_arg_type_t< ValueT > V) const

Return 1 if the specified key is in the set, 0 otherwise.

const DenseSetEmpty & getSecond() const

const KeyT & getFirst() const

DenseSetEmpty & getSecond()

bool operator!=(const DenseSetImpl< ValueT, MapTy, ValueInfoT > &LHS, const DenseSetImpl< ValueT, MapTy, ValueInfoT > &RHS)

Inequality comparison for DenseSet.

This is an optimization pass for GlobalISel generic memory operations.

bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)

uint64_t PowerOf2Ceil(uint64_t A)

Returns the power of two which is greater than or equal to the given value.

Implement std::hash so that hash_code can be used in STL containers.

An information struct used to provide DenseMap with the various necessary components for a given valu...