TrieRawHashMap.h Source File (original) (raw)

9#ifndef LLVM_ADT_TRIERAWHASHMAP_H

10#define LLVM_ADT_TRIERAWHASHMAP_H

14#include

15#include

17namespace llvm {

68public:

73private:

74 template struct AllocValueType {

76 alignas(T) char Content[sizeof(T)];

77 };

79protected:

80 template

83 template

86 template

88 offsetof(AllocValueType, Content);

90public:

91 static void *operator new(size_t Size) { return ::operator new(Size); }

92 void operator delete(void *Ptr) { ::operator delete(Ptr); }

94#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

96#endif

100protected:

101

102

103

104

106 protected:

107 void *get() const { return I == -2u ? P : nullptr; }

108

109 public:

111

112 private:

114 explicit PointerBase(void *Content) : P(Content), I(-2u) {}

116

117 bool isHint() const { return I != -1u && I != -2u; }

118

119 void *P = nullptr;

120 unsigned I = -1u;

121 unsigned B = 0;

122 };

123

124

126

127

130 function_ref<const uint8_t *(void *Mem, ArrayRef<uint8_t> Hash)>

131 Constructor);

132

134

136 size_t ContentAllocSize, size_t ContentAllocAlign, size_t ContentOffset,

137 std::optional<size_t> NumRootBits = std::nullopt,

138 std::optional<size_t> NumSubtrieBits = std::nullopt);

139

140

141

142

143

146

148

149

152

153

157

158

159

166

168

169private:

171 const unsigned short ContentAllocSize;

172 const unsigned short ContentAllocAlign;

173 const unsigned short ContentOffset;

174 unsigned short NumRootBits;

175 unsigned short NumSubtrieBits;

177

178

179 std::atomic<ImplType *> ImplPtr;

182};

183

184

185template <class T, size_t NumHashBytes>

187public:

188 using HashT = std::array<uint8_t, NumHashBytes>;

189

194

197

202

203 private:

205

206 struct EmplaceTag {};

207 template <class... ArgsT>

209 : Hash(makeHash(Hash)), Data(std::forward(Args)...) {}

210

213 std::copy(HashRef.begin(), HashRef.end(), Hash.data());

215 }

216 };

217

218 using ThreadSafeTrieRawHashMapBase::operator delete;

220

221#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

223#endif

224

226

227private:

228 template class PointerImpl : PointerBase {

230

231 ValueT *get() const {

232 return reinterpret_cast<ValueT *>(PointerBase::get());

233 }

234

235 public:

238 return *get();

239 }

240 ValueT *operator->() const {

242 return get();

243 }

244 explicit operator bool() const { return get(); }

245

246 PointerImpl() = default;

247

248 protected:

250 };

251

252public:

253 class pointer;

254 class const_pointer;

255 class pointer : public PointerImpl<value_type> {

258

259 public:

261

262 private:

264 };

265

268

269 public:

272

273 private:

275 };

276

278 public:

280 assert(Mem && "Constructor already called, or moved away");

281 return assign(::new (Mem) value_type(Hash, std::move(RHS)));

282 }

284 assert(Mem && "Constructor already called, or moved away");

285 return assign(::new (Mem) value_type(Hash, RHS));

286 }

288 assert(Mem && "Constructor already called, or moved away");

289 return assign(::new (Mem)

290 value_type(Hash, typename value_type::EmplaceTag{},

291 std::forward(Args)...));

292 }

293

295 : Mem(RHS.Mem), Result(RHS.Result), Hash(RHS.Hash) {

296 RHS.Mem = nullptr;

297 }

299

300 private:

302 Mem = nullptr;

303 Result = V;

304 return *V;

305 }

309 : Mem(Mem), Result(Result), Hash(Hash) {

310 assert(Hash.size() == sizeof(HashT) && "Invalid hash");

311 assert(Mem && "Invalid memory for construction");

312 }

313 void *Mem;

316 };

317

318

319

320

322 function_ref<void(LazyValueConstructor)> OnConstruct) {

325 value_type *Result = nullptr;

326 OnConstruct(LazyValueConstructor(Mem, Result, Hash));

327 return Result->Hash.data();

328 }));

329 }

330

332 function_ref<void(LazyValueConstructor)> OnConstruct) {

333 return insertLazy(const_pointer(), Hash, OnConstruct);

334 }

335

336 pointer insert(const_pointer Hint, value_type &&HashedData) {

337 return insertLazy(Hint, HashedData.Hash, [&](LazyValueConstructor C) {

338 C(std::move(HashedData.Data));

339 });

340 }

341

342 pointer insert(const_pointer Hint, const value_type &HashedData) {

343 return insertLazy(Hint, HashedData.Hash,

344 [&](LazyValueConstructor C) { C(HashedData.Data); });

345 }

346

348 assert(Hash.size() == std::tuple_size::value);

350 }

351

353 assert(Hash.size() == std::tuple_size::value);

355 }

356

358 std::optional<size_t> NumSubtrieBits = std::nullopt)

362 NumRootBits, NumSubtrieBits) {}

363

365 if constexpr (std::is_trivially_destructible<value_type>::value)

367 else

369 [](void *P) { static_cast<value_type *>(P)->~value_type(); });

370 }

371

372

374

375

380};

381

382}

383

384#endif

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

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

#define LLVM_DUMP_METHOD

Mark debug helper function definitions like dump() that should not be stripped from debug builds.

#define offsetof(TYPE, MEMBER)

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

size_t size() const

size - Get the array size.

Result of a lookup.

Definition TrieRawHashMap.h:105

PointerBase() noexcept=default

void * get() const

Definition TrieRawHashMap.h:107

friend class ThreadSafeTrieRawHashMapBase

Definition TrieRawHashMap.h:113

LLVM_ABI PointerBase getNextTrie(PointerBase P) const

LLVM_ABI unsigned getNumTries() const

LLVM_ABI unsigned getNumBits(PointerBase P) const

ThreadSafeTrieRawHashMapBase & operator=(const ThreadSafeTrieRawHashMapBase &)=delete

LLVM_ABI unsigned getNumSlotUsed(PointerBase P) const

LLVM_ABI ~ThreadSafeTrieRawHashMapBase()

Destructor, which asserts if there's anything to do.

LLVM_ABI void destroyImpl(function_ref< void(void *ValueMem)> Destructor)

static constexpr size_t DefaultContentAllocSize

Definition TrieRawHashMap.h:81

friend class TrieRawHashMapTestHelper

Definition TrieRawHashMap.h:170

static constexpr size_t DefaultContentAllocAlign

Definition TrieRawHashMap.h:84

static constexpr size_t DefaultContentOffset

Definition TrieRawHashMap.h:87

static constexpr size_t DefaultNumSubtrieBits

Definition TrieRawHashMap.h:71

ThreadSafeTrieRawHashMapBase()=delete

LLVM_ABI PointerBase find(ArrayRef< uint8_t > Hash) const

Find the stored content with hash.

LLVM_DUMP_METHOD void dump() const

LLVM_ABI PointerBase getRoot() const

LLVM_ABI PointerBase insert(PointerBase Hint, ArrayRef< uint8_t > Hash, function_ref< const uint8_t *(void *Mem, ArrayRef< uint8_t > Hash)> Constructor)

Insert and return the stored content.

LLVM_ABI unsigned getStartBit(PointerBase P) const

LLVM_ABI void print(raw_ostream &OS) const

ThreadSafeTrieRawHashMapBase & operator=(ThreadSafeTrieRawHashMapBase &&RHS)=delete

LLVM_ABI std::string getTriePrefixAsString(PointerBase P) const

static constexpr size_t TrieContentBaseSize

Definition TrieRawHashMap.h:69

static constexpr size_t DefaultNumRootBits

Definition TrieRawHashMap.h:70

ThreadSafeTrieRawHashMapBase(const ThreadSafeTrieRawHashMapBase &)=delete

Definition TrieRawHashMap.h:277

friend class ThreadSafeTrieRawHashMap

Definition TrieRawHashMap.h:306

value_type & operator()(T &&RHS)

Definition TrieRawHashMap.h:279

value_type & emplace(ArgsT &&...Args)

Definition TrieRawHashMap.h:287

value_type & operator()(const T &RHS)

Definition TrieRawHashMap.h:283

~LazyValueConstructor()

Definition TrieRawHashMap.h:298

LazyValueConstructor(LazyValueConstructor &&RHS)

Definition TrieRawHashMap.h:294

Definition TrieRawHashMap.h:266

friend class ThreadSafeTrieRawHashMap

Definition TrieRawHashMap.h:267

const_pointer(const pointer &P)

Definition TrieRawHashMap.h:271

Definition TrieRawHashMap.h:255

friend class ThreadSafeTrieRawHashMap

Definition TrieRawHashMap.h:256

friend class const_pointer

Definition TrieRawHashMap.h:257

ThreadSafeTrieRawHashMap & operator=(const ThreadSafeTrieRawHashMap &)=delete

pointer insertLazy(ArrayRef< uint8_t > Hash, function_ref< void(LazyValueConstructor)> OnConstruct)

Definition TrieRawHashMap.h:331

ThreadSafeTrieRawHashMap & operator=(ThreadSafeTrieRawHashMap &&)=delete

pointer find(ArrayRef< uint8_t > Hash)

Definition TrieRawHashMap.h:347

std::array< uint8_t, NumHashBytes > HashT

Definition TrieRawHashMap.h:188

pointer insertLazy(const_pointer Hint, ArrayRef< uint8_t > Hash, function_ref< void(LazyValueConstructor)> OnConstruct)

Insert with a hint.

Definition TrieRawHashMap.h:321

HashT HashType

Definition TrieRawHashMap.h:219

const_pointer find(ArrayRef< uint8_t > Hash) const

Definition TrieRawHashMap.h:352

pointer insert(const_pointer Hint, value_type &&HashedData)

Definition TrieRawHashMap.h:336

pointer insert(const_pointer Hint, const value_type &HashedData)

Definition TrieRawHashMap.h:342

ThreadSafeTrieRawHashMap(std::optional< size_t > NumRootBits=std::nullopt, std::optional< size_t > NumSubtrieBits=std::nullopt)

Definition TrieRawHashMap.h:357

ThreadSafeTrieRawHashMap(const ThreadSafeTrieRawHashMap &)=delete

ThreadSafeTrieRawHashMap(ThreadSafeTrieRawHashMap &&)=default

~ThreadSafeTrieRawHashMap()

Definition TrieRawHashMap.h:364

An efficient, type-erasing, non-owning reference to a callable.

This class implements an extremely fast bulk output stream that can only output to a stream.

@ C

The default llvm calling convention, compatible with C.

This is an optimization pass for GlobalISel generic memory operations.

APInt operator*(APInt a, uint64_t RHS)

FunctionAddr VTableAddr uintptr_t uintptr_t Data

OutputIt move(R &&Range, OutputIt Out)

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

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

Definition TrieRawHashMap.h:191

T Data

Definition TrieRawHashMap.h:193

const HashT Hash

Definition TrieRawHashMap.h:192

friend class LazyValueConstructor

Definition TrieRawHashMap.h:204

value_type(const value_type &)=default

value_type(value_type &&)=default

value_type(ArrayRef< uint8_t > Hash, T &&Data)

Definition TrieRawHashMap.h:200

value_type(ArrayRef< uint8_t > Hash, const T &Data)

Definition TrieRawHashMap.h:198