23 Align ComputedMaxAlign;
24 for (
auto &
Field : Fields) {
26 "didn't assign a fixed offset to field");
28 "didn't assign a correctly-aligned offset to field");
30 "didn't assign offsets in ascending order");
33 "didn't compute MaxAlign correctly");
36 assert(LastEnd ==
Size &&
"didn't compute LastEnd correctly");
37 assert(ComputedMaxAlign == MaxAlign &&
"didn't compute MaxAlign correctly");
41 std::pair<uint64_t, Align>
46 bool InFixedPrefix =
true;
48 for (
auto &
Field : Fields) {
52 "fixed-offset fields are not a strict prefix of array");
54 "fixed-offset fields overlap or are not in order");
57 "overflow in fixed-offset end offset");
59 InFixedPrefix =
false;
69 auto FirstFlexible = Fields.
begin(),
E = Fields.
end();
70 while (FirstFlexible !=
E && FirstFlexible->hasFixedOffset()) {
71 MaxAlign =
std::max(MaxAlign, FirstFlexible->Alignment);
76 if (FirstFlexible ==
E) {
84 return std::make_pair(
Size, MaxAlign);
93 uintptr_t UniqueNumber = 0;
94 for (
auto I = FirstFlexible;
I !=
E; ++
I) {
95 I->Scratch =
reinterpret_cast<void*
>(UniqueNumber++);
96 MaxAlign =
std::max(MaxAlign,
I->Alignment);
106 [](
const Field *lhs,
const Field *rhs) ->
int {
116 auto lhsNumber =
reinterpret_cast<uintptr_t
>(lhs->
Scratch);
117 auto rhsNumber =
reinterpret_cast<uintptr_t
>(rhs->
Scratch);
118 if (lhsNumber != rhsNumber)
119 return (lhsNumber < rhsNumber ? -1 : 1);
131 bool HasPadding =
false;
132 uint64_t LastEnd = 0;
135 for (
auto I = Fields.
begin();
I != FirstFlexible; ++
I) {
137 if (LastEnd !=
I->Offset) {
141 LastEnd =
I->getEndOffset();
150 for (
auto I = FirstFlexible;
I !=
E; ++
I) {
157 LastEnd =
I->getEndOffset();
166 return std::make_pair(LastEnd, MaxAlign);
235 struct AlignmentQueue {
254 for (
auto I = FirstFlexible;
I !=
E; ) {
256 auto Alignment =
I->Alignment;
258 uint64_t MinSize =
I->Size;
259 auto LastInQueue =
I;
260 for (++
I;
I !=
E &&
I->Alignment == Alignment; ++
I) {
261 LastInQueue->Scratch =
I;
265 LastInQueue->Scratch =
nullptr;
267 FlexibleFieldsByAlignment.push_back({MinSize, Head, Alignment});
272 auto checkQueues = [&]{
273 bool FirstQueue =
true;
274 Align LastQueueAlignment;
275 for (
auto &Queue : FlexibleFieldsByAlignment) {
276 assert((FirstQueue || Queue.Alignment < LastQueueAlignment) &&
277 "bins not in order of descending alignment");
278 LastQueueAlignment = Queue.Alignment;
281 assert(Queue.Head &&
"queue was empty");
282 uint64_t LastSize = ~(uint64_t)0;
283 for (
auto I = Queue.Head;
I;
I = Queue.getNext(
I)) {
284 assert(
I->Alignment == Queue.Alignment &&
"bad field in queue");
285 assert(
I->Size <= LastSize &&
"queue not in descending size order");
294 auto spliceFromQueue = [&](AlignmentQueue *Queue,
Field *Last,
Field *Cur) {
295 assert(Last ? Queue->getNext(Last) == Cur : Queue->Head == Cur);
300 Last->Scratch = Cur->Scratch;
306 Queue->MinSize = Last->Size;
310 if (
auto NewHead = Queue->getNext(Cur))
311 Queue->Head = NewHead;
315 FlexibleFieldsByAlignment.
erase(Queue);
325 uint64_t LastEnd = 0;
329 auto addToLayout = [&](AlignmentQueue *Queue,
Field *Last,
Field *Cur,
330 uint64_t
Offset) ->
bool {
334 spliceFromQueue(Queue, Last, Cur);
337 Layout.push_back(*Cur);
338 Layout.back().Offset =
Offset;
339 LastEnd = Layout.back().getEndOffset();
348 auto tryAddFillerFromQueue = [&](AlignmentQueue *Queue,
349 uint64_t StartOffset,
357 (EndOffset ? *EndOffset - StartOffset : ~(uint64_t)0);
358 if (Queue->MinSize > MaxViableSize)
return false;
362 for (
Field *Cur = Queue->Head, *Last =
nullptr;
true;
363 Last = Cur, Cur = Queue->getNext(Cur)) {
364 assert(Cur &&
"didn't find a match in queue despite its MinSize");
365 if (Cur->Size <= MaxViableSize)
366 return addToLayout(Queue, Last, Cur, StartOffset);
375 auto QueueB = FlexibleFieldsByAlignment.begin();
376 auto QueueE = FlexibleFieldsByAlignment.end();
380 auto FirstQueueToSearch = QueueB;
381 for (; FirstQueueToSearch != QueueE; ++FirstQueueToSearch) {
382 if (
isAligned(FirstQueueToSearch->Alignment, LastEnd))
386 uint64_t
Offset = LastEnd;
393 for (
auto Queue = FirstQueueToSearch; Queue != QueueE; ++Queue) {
394 if (tryAddFillerFromQueue(Queue,
Offset, BeforeOffset))
399 QueueE = FirstQueueToSearch;
402 if (FirstQueueToSearch == QueueB)
407 --FirstQueueToSearch;
409 while (FirstQueueToSearch != QueueB &&
410 Offset ==
alignTo(LastEnd, FirstQueueToSearch[-1].Alignment))
411 --FirstQueueToSearch;
417 for (
auto I = Fields.
begin();
I != FirstFlexible; ++
I) {
418 while (LastEnd !=
I->Offset) {
419 if (!tryAddBestField(
I->Offset))
422 Layout.push_back(*
I);
423 LastEnd =
I->getEndOffset();
432 while (!FlexibleFieldsByAlignment.empty()) {
434 assert(
Success &&
"didn't find a field with no fixed limit?");
448 return std::make_pair(LastEnd, MaxAlign);