SmallSet.h Source File (original) (raw)

14#ifndef LLVM_ADT_SMALLSET_H

15#define LLVM_ADT_SMALLSET_H

20#include

21#include

22#include <initializer_list>

23#include

24#include

26namespace llvm {

30template <typename T, unsigned N, typename C>

33 std::forward_iterator_tag, T> {

34private:

35 using SetIterTy = typename std::set<T, C>::const_iterator;

41 union {

44 };

46 bool IsSmall;

48public:

56 if (IsSmall)

58 else

60 }

63 if (IsSmall)

65 else

69 }

72 if (IsSmall)

74 else

77 new (&SetIter) SetIterTy(std::move(Other.SetIter));

78 }

83 if (!IsSmall)

86 IsSmall = Other.IsSmall;

87 if (IsSmall)

89 else

91 return *this;

92 }

97 if (!IsSmall)

100 IsSmall = Other.IsSmall;

101 if (IsSmall)

103 else

104 new (&SetIter) SetIterTy(std::move(Other.SetIter));

105 return *this;

106 }

107

109 if (IsSmall != RHS.IsSmall)

110 return false;

111 if (IsSmall)

114 }

115

117 if (IsSmall)

119 else

121 return *this;

122 }

123

125};

126

127

128

129

130

131template <typename T, unsigned N, typename C = std::less>

133

134

135

137 std::set<T, C> Set;

138

139

140

141

142 static_assert(N <= 32, "N should be small");

143

144public:

149

153

154 template SmallSet(IterT Begin, IterT End) {

156 }

157

158 template

160 insert(R.begin(), R.end());

161 }

162

163 SmallSet(std::initializer_list L) { insert(L.begin(), L.end()); }

164

167

168 [[nodiscard]] bool empty() const { return Vector.empty() && Set.empty(); }

169

171 return isSmall() ? Vector.size() : Set.size();

172 }

173

174

176

177

178

179

180

181 std::pair<const_iterator, bool> insert(const T &V) { return insertImpl(V); }

182

183 std::pair<const_iterator, bool> insert(T &&V) {

184 return insertImpl(std::move(V));

185 }

186

187 template

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

191 }

192

194 if (!isSmall())

195 return Set.erase(V);

196 auto I = vfind(V);

199 return true;

200 }

201 return false;

202 }

203

206 Set.clear();

207 }

208

210 if (isSmall())

211 return {Vector.begin()};

212 return {Set.begin()};

213 }

214

216 if (isSmall())

217 return {Vector.end()};

218 return {Set.end()};

219 }

220

221

223 if (isSmall())

224 return vfind(V) != Vector.end();

225 return Set.find(V) != Set.end();

226 }

227

228private:

229 bool isSmall() const { return Set.empty(); }

230

231 template

232 std::pair<const_iterator, bool> insertImpl(ArgType &&V) {

233 static_assert(std::is_convertible_v<ArgType, T>,

234 "ArgType must be convertible to T!");

235 if (!isSmall()) {

236 auto [I, Inserted] = Set.insert(std::forward(V));

238 }

239

240 auto I = vfind(V);

241 if (I != Vector.end())

244 Vector.push_back(std::forward(V));

246 }

247

248 Set.insert(std::make_move_iterator(Vector.begin()),

249 std::make_move_iterator(Vector.end()));

251 return {const_iterator(Set.insert(std::forward(V)).first), true};

252 }

253

254

255

256 typename SmallVector<T, N>::const_iterator vfind(const T &V) const {

258 if (*I == V)

259 return I;

261 }

262};

263

264

265

266template <typename PointeeType, unsigned N>

268

269

270

271

272

273

274

275

276

277template <typename T, unsigned LN, unsigned RN, typename C>

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

280 return false;

281

282

284}

285

286

287

288

289template <typename T, unsigned LN, unsigned RN, typename C>

291 return !(LHS == RHS);

292}

293

294}

295

296#endif

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

This file defines the SmallPtrSet class.

This file defines the SmallVector class.

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

SmallSetIterator - This class implements a const_iterator for SmallSet by delegating to the underlyin...

SmallSetIterator & operator=(SmallSetIterator &&Other)

SmallSetIterator & operator++()

bool operator==(const SmallSetIterator &RHS) const

SmallSetIterator(SetIterTy SetIter)

SmallSetIterator & operator=(const SmallSetIterator &Other)

SmallSetIterator(const SmallSetIterator &Other)

const T & operator*() const

SmallSetIterator(VecIterTy VecIter)

SmallSetIterator(SmallSetIterator &&Other)

SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...

SmallSet(const iterator_range< RangeT > &R)

const_iterator begin() const

size_type count(const T &V) const

count - Return 1 if the element is in the set, 0 otherwise.

SmallSetIterator< T, N, C > const_iterator

void insert(IterT I, IterT E)

std::pair< const_iterator, bool > insert(T &&V)

SmallSet(std::initializer_list< T > L)

SmallSet & operator=(const SmallSet &)=default

SmallSet(SmallSet &&)=default

SmallSet(const SmallSet &)=default

const_iterator end() const

SmallSet(IterT Begin, IterT End)

bool contains(const T &V) const

Check if the SmallSet contains the given element.

SmallSet & operator=(SmallSet &&)=default

std::pair< const_iterator, bool > insert(const T &V)

insert - Insert an element into the set if it isn't already there.

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

CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...

A range adaptor for a pair of iterators.

This is an optimization pass for GlobalISel generic memory operations.

bool all_of(R &&range, UnaryPredicate P)

Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.

bool operator!=(uint64_t V1, const APInt &V2)

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