SmallSet.h Source File (original) (raw)

14#ifndef LLVM_ADT_SMALLSET_H

15#define LLVM_ADT_SMALLSET_H

22#include

23#include

24#include <initializer_list>

25#include

26#include

28namespace llvm {

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

35 std::forward_iterator_tag, T> {

36private:

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

42 union {

45 };

47 bool IsSmall;

49public:

57 if (IsSmall)

59 else

61 }

64 if (IsSmall)

66 else

70 }

73 if (IsSmall)

75 else

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

79 }

84 if (!IsSmall)

87 IsSmall = Other.IsSmall;

88 if (IsSmall)

90 else

92 return *this;

93 }

98 if (!IsSmall)

100

101 IsSmall = Other.IsSmall;

102 if (IsSmall)

104 else

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

106 return *this;

107 }

108

110 if (IsSmall != RHS.IsSmall)

111 return false;

112 if (IsSmall)

115 }

116

118 if (IsSmall)

120 else

122 return *this;

123 }

124

126};

127

128

129

130

131

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

134

135

136

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

139

140

141

142

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

144

145public:

150

154

155 template SmallSet(IterT Begin, IterT End) {

157 }

158

159 template

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

178

179

180

181

182

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

184

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

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

187 }

188

189 template

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

193 }

194

198

200 if (!isSmall())

201 return Set.erase(V);

202 auto I = vfind(V);

203 if (I != Vector.end()) {

204 Vector.erase(I);

205 return true;

206 }

207 return false;

208 }

209

211 Vector.clear();

212 Set.clear();

213 }

214

216 if (isSmall())

217 return {Vector.begin()};

218 return {Set.begin()};

219 }

220

222 if (isSmall())

223 return {Vector.end()};

224 return {Set.end()};

225 }

226

227

228 [[nodiscard]] bool contains(const T &V) const {

229 if (isSmall())

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

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

232 }

233

234private:

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

236

237 template

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

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

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

241 if (!isSmall()) {

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

244 }

245

246 auto I = vfind(V);

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

249 if (Vector.size() < N) {

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

251 return {const_iterator(std::prev(Vector.end())), true};

252 }

253

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

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

256 Vector.clear();

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

258 }

259

260

261

263 for (auto I = Vector.begin(), E = Vector.end(); I != E; ++I)

264 if (*I == V)

265 return I;

266 return Vector.end();

267 }

268};

269

270

271

272template <typename PointeeType, unsigned N>

274

275

276

277

278

279

280

281

282

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

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

287 return false;

288

289

291}

292

293

294

295

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

299 return !(LHS == RHS);

300}

301

302}

303

304#endif

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

ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))

This file contains library features backported from future STL versions.

This file defines the SmallPtrSet class.

This file defines the SmallVector class.

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

Definition SmallSet.h:35

SmallSetIterator & operator=(SmallSetIterator &&Other)

Definition SmallSet.h:95

SmallSetIterator & operator++()

Definition SmallSet.h:117

bool operator==(const SmallSetIterator &RHS) const

Definition SmallSet.h:109

SetIterTy SetIter

Definition SmallSet.h:43

SmallSetIterator(SetIterTy SetIter)

Definition SmallSet.h:50

SmallSetIterator & operator=(const SmallSetIterator &Other)

Definition SmallSet.h:81

SmallSetIterator(const SmallSetIterator &Other)

Definition SmallSet.h:63

const T & operator*() const

Definition SmallSet.h:125

VecIterTy VecIter

Definition SmallSet.h:44

~SmallSetIterator()

Definition SmallSet.h:56

SmallSetIterator(VecIterTy VecIter)

Definition SmallSet.h:52

SmallSetIterator(SmallSetIterator &&Other)

Definition SmallSet.h:72

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

Definition SmallSet.h:133

const_iterator begin() const

Definition SmallSet.h:215

size_type count(const T &V) const

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

Definition SmallSet.h:175

SmallSetIterator< T, N, C > const_iterator

Definition SmallSet.h:149

bool empty() const

Definition SmallSet.h:168

void insert(IterT I, IterT E)

Definition SmallSet.h:190

void insert_range(Range &&R)

Definition SmallSet.h:195

T key_type

Definition SmallSet.h:146

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

Definition SmallSet.h:185

SmallSet(std::initializer_list< T > L)

Definition SmallSet.h:163

bool erase(const T &V)

Definition SmallSet.h:199

size_t size_type

Definition SmallSet.h:147

void clear()

Definition SmallSet.h:210

SmallSet(llvm::from_range_t, Range &&R)

Definition SmallSet.h:160

T value_type

Definition SmallSet.h:148

SmallSet & operator=(const SmallSet &)=default

SmallSet(SmallSet &&)=default

SmallSet(const SmallSet &)=default

const_iterator end() const

Definition SmallSet.h:221

SmallSet(IterT Begin, IterT End)

Definition SmallSet.h:155

bool contains(const T &V) const

Check if the SmallSet contains the given element.

Definition SmallSet.h:228

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.

Definition SmallSet.h:183

size_type size() const

Definition SmallSet.h:170

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 ...

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.

constexpr auto adl_begin(RangeT &&range) -> decltype(adl_detail::begin_impl(std::forward< RangeT >(range)))

Returns the begin iterator to range using std::begin and function found through Argument-Dependent Lo...

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

constexpr auto adl_end(RangeT &&range) -> decltype(adl_detail::end_impl(std::forward< RangeT >(range)))

Returns the end iterator to range using std::end and functions found through Argument-Dependent Looku...

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