1 // Copyright 2020 The Abseil Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #ifndef ABSL_STRINGS_INTERNAL_CORD_REP_FLAT_H_
16 #define ABSL_STRINGS_INTERNAL_CORD_REP_FLAT_H_
17
18 #include <cassert>
19 #include <cstddef>
20 #include <cstdint>
21 #include <memory>
22
23 #include "absl/strings/internal/cord_internal.h"
24
25 namespace absl {
26 ABSL_NAMESPACE_BEGIN
27 namespace cord_internal {
28
29 // Note: all constants below are never ODR used and internal to cord, we define
30 // these as static constexpr to avoid 'in struct' definition and usage clutter.
31
32 // Largest and smallest flat node lengths we are willing to allocate
33 // Flat allocation size is stored in tag, which currently can encode sizes up
34 // to 4K, encoded as multiple of either 8 or 32 bytes.
35 // If we allow for larger sizes, we need to change this to 8/64, 16/128, etc.
36 // kMinFlatSize is bounded by tag needing to be at least FLAT * 8 bytes, and
37 // ideally a 'nice' size aligning with allocation and cacheline sizes like 32.
38 // kMaxFlatSize is bounded by the size resulting in a computed tag no greater
39 // than MAX_FLAT_TAG. MAX_FLAT_TAG provides for additional 'high' tag values.
40 static constexpr size_t kFlatOverhead = offsetof(CordRep, storage);
41 static constexpr size_t kMinFlatSize = 32;
42 static constexpr size_t kMaxFlatSize = 4096;
43 static constexpr size_t kMaxFlatLength = kMaxFlatSize - kFlatOverhead;
44 static constexpr size_t kMinFlatLength = kMinFlatSize - kFlatOverhead;
45
AllocatedSizeToTagUnchecked(size_t size)46 constexpr uint8_t AllocatedSizeToTagUnchecked(size_t size) {
47 return static_cast<uint8_t>((size <= 1024) ? size / 8 + 1
48 : 129 + size / 32 - 1024 / 32);
49 }
50
51 static_assert(kMinFlatSize / 8 + 1 >= FLAT, "");
52 static_assert(AllocatedSizeToTagUnchecked(kMaxFlatSize) <= MAX_FLAT_TAG, "");
53
54 // Helper functions for rounded div, and rounding to exact sizes.
DivUp(size_t n,size_t m)55 constexpr size_t DivUp(size_t n, size_t m) { return (n + m - 1) / m; }
RoundUp(size_t n,size_t m)56 constexpr size_t RoundUp(size_t n, size_t m) { return DivUp(n, m) * m; }
57
58 // Returns the size to the nearest equal or larger value that can be
59 // expressed exactly as a tag value.
RoundUpForTag(size_t size)60 inline size_t RoundUpForTag(size_t size) {
61 return RoundUp(size, (size <= 1024) ? 8 : 32);
62 }
63
64 // Converts the allocated size to a tag, rounding down if the size
65 // does not exactly match a 'tag expressible' size value. The result is
66 // undefined if the size exceeds the maximum size that can be encoded in
67 // a tag, i.e., if size is larger than TagToAllocatedSize(<max tag>).
AllocatedSizeToTag(size_t size)68 inline uint8_t AllocatedSizeToTag(size_t size) {
69 const uint8_t tag = AllocatedSizeToTagUnchecked(size);
70 assert(tag <= MAX_FLAT_TAG);
71 return tag;
72 }
73
74 // Converts the provided tag to the corresponding allocated size
TagToAllocatedSize(uint8_t tag)75 constexpr size_t TagToAllocatedSize(uint8_t tag) {
76 return (tag <= 129) ? ((tag - 1) * 8) : (1024 + (tag - 129) * 32);
77 }
78
79 // Converts the provided tag to the corresponding available data length
TagToLength(uint8_t tag)80 constexpr size_t TagToLength(uint8_t tag) {
81 return TagToAllocatedSize(tag) - kFlatOverhead;
82 }
83
84 // Enforce that kMaxFlatSize maps to a well-known exact tag value.
85 static_assert(TagToAllocatedSize(225) == kMaxFlatSize, "Bad tag logic");
86
87 struct CordRepFlat : public CordRep {
88 // Creates a new flat node.
NewCordRepFlat89 static CordRepFlat* New(size_t len) {
90 if (len <= kMinFlatLength) {
91 len = kMinFlatLength;
92 } else if (len > kMaxFlatLength) {
93 len = kMaxFlatLength;
94 }
95
96 // Round size up so it matches a size we can exactly express in a tag.
97 const size_t size = RoundUpForTag(len + kFlatOverhead);
98 void* const raw_rep = ::operator new(size);
99 CordRepFlat* rep = new (raw_rep) CordRepFlat();
100 rep->tag = AllocatedSizeToTag(size);
101 return rep;
102 }
103
104 // Deletes a CordRepFlat instance created previously through a call to New().
105 // Flat CordReps are allocated and constructed with raw ::operator new and
106 // placement new, and must be destructed and deallocated accordingly.
DeleteCordRepFlat107 static void Delete(CordRep*rep) {
108 assert(rep->tag >= FLAT && rep->tag <= MAX_FLAT_TAG);
109
110 #if defined(__cpp_sized_deallocation)
111 size_t size = TagToAllocatedSize(rep->tag);
112 rep->~CordRep();
113 ::operator delete(rep, size);
114 #else
115 rep->~CordRep();
116 ::operator delete(rep);
117 #endif
118 }
119
120 // Returns a pointer to the data inside this flat rep.
DataCordRepFlat121 char* Data() { return reinterpret_cast<char*>(storage); }
DataCordRepFlat122 const char* Data() const { return reinterpret_cast<const char*>(storage); }
123
124 // Returns the maximum capacity (payload size) of this instance.
CapacityCordRepFlat125 size_t Capacity() const { return TagToLength(tag); }
126
127 // Returns the allocated size (payload + overhead) of this instance.
AllocatedSizeCordRepFlat128 size_t AllocatedSize() const { return TagToAllocatedSize(tag); }
129 };
130
131 // Now that CordRepFlat is defined, we can define CordRep's helper casts:
flat()132 inline CordRepFlat* CordRep::flat() {
133 assert(tag >= FLAT && tag <= MAX_FLAT_TAG);
134 return reinterpret_cast<CordRepFlat*>(this);
135 }
136
flat()137 inline const CordRepFlat* CordRep::flat() const {
138 assert(tag >= FLAT && tag <= MAX_FLAT_TAG);
139 return reinterpret_cast<const CordRepFlat*>(this);
140 }
141
142 } // namespace cord_internal
143 ABSL_NAMESPACE_END
144 } // namespace absl
145
146 #endif // ABSL_STRINGS_INTERNAL_CORD_REP_FLAT_H_
147