1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "llvm/ADT/DenseMap.h"
10#include "llvm/Support/MemAlloc.h"
11#include <cstring>
12
13using namespace llvm;
14using namespace llvm::densemap;
15using namespace llvm::densemap::detail;
16
17// A nonzero FixedSize turns the bucket copy into a couple of stores.
18template <size_t FixedSize, bool InlinePtrHash>
19static void rehashLoop(void *DstBuckets, UsedT *DstUsed, unsigned Mask,
20 const void *SrcBuckets, const UsedT *SrcUsed,
21 unsigned SrcNumBuckets, size_t RuntimeSize,
22 BucketHasher Hasher) {
23 const size_t BucketSize = FixedSize ? FixedSize : RuntimeSize;
24 char *Dst = static_cast<char *>(DstBuckets);
25 const char *Src = static_cast<const char *>(SrcBuckets);
26 forEachUsed(SrcUsed, SrcNumBuckets, [&](unsigned I) {
27 const char *SrcBucket = Src + static_cast<size_t>(I) * BucketSize;
28 unsigned Hash;
29 if constexpr (InlinePtrHash) {
30 void *Key;
31 std::memcpy(dest: &Key, src: SrcBucket, n: sizeof(Key));
32 Hash = DenseMapInfo<void *>::getHashValue(PtrVal: Key);
33 } else {
34 Hash = Hasher(SrcBucket);
35 }
36 unsigned BucketNo = Hash & Mask;
37 while (used(U: DstUsed, I: BucketNo))
38 BucketNo = (BucketNo + 1) & Mask;
39 std::memcpy(dest: Dst + static_cast<size_t>(BucketNo) * BucketSize, src: SrcBucket,
40 n: BucketSize);
41 setUsed(U: DstUsed, I: BucketNo);
42 });
43}
44
45template <bool InlinePtrHash>
46static void rehashBySize(void *Dst, UsedT *DstUsed, unsigned Mask,
47 const void *Src, const UsedT *SrcUsed,
48 unsigned SrcNumBuckets, size_t BucketSize,
49 BucketHasher Hasher) {
50 // The bucket sizes of 95% of the grow instantiations in an LLVM build.
51 switch (BucketSize) {
52#define REHASH_CASE(N) \
53 case N: \
54 return rehashLoop<N, InlinePtrHash>(Dst, DstUsed, Mask, Src, SrcUsed, \
55 SrcNumBuckets, BucketSize, Hasher);
56 REHASH_CASE(4)
57 REHASH_CASE(8)
58 REHASH_CASE(12)
59 REHASH_CASE(16)
60 REHASH_CASE(24)
61 REHASH_CASE(32)
62 REHASH_CASE(40)
63 REHASH_CASE(48)
64#undef REHASH_CASE
65 default:
66 return rehashLoop<0, InlinePtrHash>(Dst, DstUsed, Mask, Src, SrcUsed,
67 SrcNumBuckets, BucketSize, Hasher);
68 }
69}
70
71void densemap::detail::rehashRelocatable(void *Dst, UsedT *DstUsed,
72 unsigned DstNumBuckets,
73 const void *Src, const UsedT *SrcUsed,
74 unsigned SrcNumBuckets,
75 size_t BucketSize,
76 BucketHasher Hasher) {
77 const unsigned Mask = DstNumBuckets - 1;
78 if (!Hasher)
79 return rehashBySize<true>(Dst, DstUsed, Mask, Src, SrcUsed, SrcNumBuckets,
80 BucketSize, Hasher);
81 return rehashBySize<false>(Dst, DstUsed, Mask, Src, SrcUsed, SrcNumBuckets,
82 BucketSize, Hasher);
83}
84
85void *densemap::detail::growRelocatable(void *OldBuckets, const UsedT *OldUsed,
86 unsigned OldNumBuckets,
87 unsigned NewNumBuckets,
88 size_t BucketSize, size_t Align,
89 BucketHasher Hasher, bool FreeOld) {
90 void *Storage = allocate_buffer(Size: allocBytes(BucketSize, Num: NewNumBuckets), Alignment: Align);
91 UsedT *NewUsed = usedFor(Buckets: Storage, BucketSize, Num: NewNumBuckets);
92 clearUsed(U: NewUsed, Num: NewNumBuckets);
93 if (OldNumBuckets) {
94 rehashRelocatable(Dst: Storage, DstUsed: NewUsed, DstNumBuckets: NewNumBuckets, Src: OldBuckets, SrcUsed: OldUsed,
95 SrcNumBuckets: OldNumBuckets, BucketSize, Hasher);
96 if (FreeOld)
97 deallocate_buffer(Ptr: OldBuckets, Size: allocBytes(BucketSize, Num: OldNumBuckets),
98 Alignment: Align);
99 }
100 return Storage;
101}
102