Debian Codegraph @

extra/protobuf/protobuf-24.4/src/google/protobuf/string_block.h

raw
1 // Protocol Buffers - Google's data interchange format
2 // Copyright 2023 Google Inc. All rights reserved.
3 // https://developers.google.com/protocol-buffers/
4 //
5 // Redistribution and use in source and binary forms, with or without
6 // modification, are permitted provided that the following conditions are
7 // met:
8 //
9 // * Redistributions of source code must retain the above copyright
10 // notice, this list of conditions and the following disclaimer.
11 // * Redistributions in binary form must reproduce the above
12 // copyright notice, this list of conditions and the following disclaimer
13 // in the documentation and/or other materials provided with the
14 // distribution.
15 // * Neither the name of Google Inc. nor the names of its
16 // contributors may be used to endorse or promote products derived from
17 // this software without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 //
31 // This file defines the internal StringBlock class
32
33 #ifndef GOOGLE_PROTOBUF_STRING_BLOCK_H__
34 #define GOOGLE_PROTOBUF_STRING_BLOCK_H__
35
36 #include <algorithm>
37 #include <cstddef>
38 #include <cstdint>
39 #include <string>
40
41 #include "absl/base/attributes.h"
42 #include "absl/log/absl_check.h"
43 #include "google/protobuf/arena_align.h"
44 #include "google/protobuf/port.h"
45
46 // Must be included last.
47 #include "google/protobuf/port_def.inc"
48
49 namespace google {
50 namespace protobuf {
51 namespace internal {
52
53 // StringBlock provides heap allocated, dynamically sized blocks (mini arenas)
54 // for allocating std::string instances. StringBlocks are allocated through
55 // the `New` function, and must be freed using the `Delete` function.
56 // StringBlocks are automatically sized from 256B to 8KB depending on the
57 // `next` instance provided in the `New` function to keep the average maximum
58 // unused space limited to 25%, or up to 4KB.
59 class alignas(std::string) StringBlock {
60 public:
61 StringBlock() = delete;
62 StringBlock(const StringBlock&) = delete;
63 StringBlock& operator=(const StringBlock&) = delete;
64
65 // Returns the size of the next string block based on the size information
66 // stored in `block`. `block` may be null in which case the size of the
67 // initial string block is returned.
68 static size_t NextSize(StringBlock* block);
69
70 // Allocates a new StringBlock pointing to `next`, which can be null.
71 // The size of the returned block depends on the allocated size of `next`.
72 static StringBlock* New(StringBlock* next);
73
74 // Allocates a new string block `in place`. `n` must be the value returned
75 // from a previous call to `StringBlock::NextSize(next)`
76 static StringBlock* Emplace(void* p, size_t n, StringBlock* next);
77
78 // Deletes `block` if `block` is heap allocated. `block` must not be null.
79 // Returns the allocated size of `block`, or 0 if the block was emplaced.
80 static size_t Delete(StringBlock* block);
81
82 StringBlock* next() const;
83
84 // Returns the string instance at offset `offset`.
85 // `offset` must be a multiple of sizeof(std::string), and be less than or
86 // equal to `effective_size()`. `AtOffset(effective_size())` returns the
87 // end of the allocated string instances and must not be de-referenced.
88 ABSL_ATTRIBUTE_RETURNS_NONNULL std::string* AtOffset(size_t offset);
89
90 // Returns a pointer to the first string instance in this block.
91 ABSL_ATTRIBUTE_RETURNS_NONNULL std::string* begin();
92
93 // Returns a pointer directly beyond the last string instance in this block.
94 ABSL_ATTRIBUTE_RETURNS_NONNULL std::string* end();
95
96 // Returns the total allocation size of this instance.
97 size_t allocated_size() const { return allocated_size_; }
98
99 // Returns true if this block is heap allocated, false if emplaced.
100 bool heap_allocated() const { return heap_allocated_; }
101
102 // Returns the effective size available for allocation string instances.
103 // This value is guaranteed to be a multiple of sizeof(std::string), and
104 // guaranteed to never be zero.
105 size_t effective_size() const;
106
107 private:
108 static_assert(alignof(std::string) <= sizeof(void*), "");
109 static_assert(alignof(std::string) <= ArenaAlignDefault::align, "");
110
111 ~StringBlock() = default;
112
113 explicit StringBlock(StringBlock* next, bool heap_allocated, uint32_t size,
114 uint32_t next_size) noexcept
115 : next_(next),
116 heap_allocated_(heap_allocated),
117 allocated_size_(size),
118 next_size_(next_size) {}
119
120 static constexpr uint32_t min_size() { return size_t{256}; }
121 static constexpr uint32_t max_size() { return size_t{8192}; }
122
123 // Returns `size` rounded down such that we can fit a perfect number
124 // of std::string instances inside a StringBlock of that size.
125 static constexpr uint32_t RoundedSize(uint32_t size);
126
127 // Returns the size of the next block.
128 size_t next_size() const { return next_size_; }
129
130 StringBlock* const next_;
131 const bool heap_allocated_ : 1;
132 const uint32_t allocated_size_ : 31;
133 const uint32_t next_size_;
134 };
135
136 constexpr uint32_t StringBlock::RoundedSize(uint32_t size) {
137 return size - (size - sizeof(StringBlock)) % sizeof(std::string);
138 }
139
140 inline size_t StringBlock::NextSize(StringBlock* block) {
141 return block ? block->next_size() : min_size();
142 }
143
144 inline StringBlock* StringBlock::Emplace(void* p, size_t n, StringBlock* next) {
145 const auto count = static_cast<uint32_t>(n);
146 ABSL_DCHECK_EQ(count, NextSize(next));
147 uint32_t doubled = count * 2;
148 uint32_t next_size = next ? std::min(doubled, max_size()) : min_size();
149 return new (p) StringBlock(next, false, RoundedSize(count), next_size);
150 }
151
152 inline StringBlock* StringBlock::New(StringBlock* next) {
153 // Compute required size, rounding down to a multiple of sizeof(std:string)
154 // so that we can optimize the allocation path. I.e., we incur a (constant
155 // size) MOD() operation cost here to avoid any MUL() later on.
156 uint32_t size = min_size();
157 uint32_t next_size = min_size();
158 if (next) {
159 size = next->next_size_;
160 next_size = std::min(size * 2, max_size());
161 }
162 size = RoundedSize(size);
163 void* p = ::operator new(size);
164 return new (p) StringBlock(next, true, size, next_size);
165 }
166
167 inline size_t StringBlock::Delete(StringBlock* block) {
168 ABSL_DCHECK(block != nullptr);
169 if (!block->heap_allocated_) return size_t{0};
170 size_t size = block->allocated_size();
171 internal::SizedDelete(block, size);
172 return size;
173 }
174
175 inline StringBlock* StringBlock::next() const { return next_; }
176
177 inline size_t StringBlock::effective_size() const {
178 return allocated_size_ - sizeof(StringBlock);
179 }
180
181 ABSL_ATTRIBUTE_RETURNS_NONNULL inline std::string* StringBlock::AtOffset(
182 size_t offset) {
183 ABSL_DCHECK_LE(offset, effective_size());
184 return reinterpret_cast<std::string*>(reinterpret_cast<char*>(this + 1) +
185 offset);
186 }
187
188 ABSL_ATTRIBUTE_RETURNS_NONNULL inline std::string* StringBlock::begin() {
189 return AtOffset(0);
190 }
191
192 ABSL_ATTRIBUTE_RETURNS_NONNULL inline std::string* StringBlock::end() {
193 return AtOffset(effective_size());
194 }
195
196 } // namespace internal
197 } // namespace protobuf
198 } // namespace google
199
200 #include "google/protobuf/port_undef.inc"
201
202 #endif // GOOGLE_PROTOBUF_STRING_BLOCK_H__