1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
#pragma once
#include <util/generic/intrlist.h>
namespace NRopeDetails {
template<typename TChunk>
class TChunkList {
struct TItem : TIntrusiveListItem<TItem>, TChunk {
// delegating constructor
template<typename... TArgs> TItem(TArgs&&... args) : TChunk(std::forward<TArgs>(args)...) {}
};
using TList = TIntrusiveList<TItem>;
TList List;
static constexpr size_t NumInplaceItems = 2;
char InplaceItems[sizeof(TItem) * NumInplaceItems];
template<typename... TArgs>
TItem *AllocateItem(TArgs&&... args) {
for (size_t index = 0; index < NumInplaceItems; ++index) {
TItem *chunk = GetInplaceItemPtr(index);
if (!TItem::IsInUse(*chunk)) {
return new(chunk) TItem(std::forward<TArgs>(args)...);
}
}
return new TItem(std::forward<TArgs>(args)...);
}
void ReleaseItem(TItem *chunk) {
if (IsInplaceItem(chunk)) {
chunk->~TItem();
TItem::Clear(*chunk);
} else {
delete chunk;
}
}
void ReleaseItems(TList& list) {
while (list) {
ReleaseItem(list.Front());
}
}
void Prepare() {
for (size_t index = 0; index < NumInplaceItems; ++index) {
TItem::Clear(*GetInplaceItemPtr(index));
}
}
TItem *GetInplaceItemPtr(size_t index) { return reinterpret_cast<TItem*>(InplaceItems + index * sizeof(TItem)); }
bool IsInplaceItem(TItem *chunk) { return chunk >= GetInplaceItemPtr(0) && chunk < GetInplaceItemPtr(NumInplaceItems); }
public:
using iterator = typename TList::iterator;
using const_iterator = typename TList::const_iterator;
public:
TChunkList() {
Prepare();
}
~TChunkList() {
ReleaseItems(List);
#ifndef NDEBUG
for (size_t index = 0; index < NumInplaceItems; ++index) {
Y_VERIFY(!TItem::IsInUse(*GetInplaceItemPtr(index)));
}
#endif
}
TChunkList(const TChunkList& other) {
Prepare();
for (const TItem& chunk : other.List) {
PutToEnd(TChunk(chunk));
}
}
TChunkList(TChunkList&& other) {
Prepare();
Splice(end(), other, other.begin(), other.end());
}
TChunkList& operator=(const TChunkList& other) {
if (this != &other) {
ReleaseItems(List);
for (const TItem& chunk : other.List) {
PutToEnd(TChunk(chunk));
}
}
return *this;
}
TChunkList& operator=(TChunkList&& other) {
if (this != &other) {
ReleaseItems(List);
Splice(end(), other, other.begin(), other.end());
}
return *this;
}
template<typename... TArgs>
void PutToEnd(TArgs&&... args) {
InsertBefore(end(), std::forward<TArgs>(args)...);
}
template<typename... TArgs>
iterator InsertBefore(iterator pos, TArgs&&... args) {
TItem *item = AllocateItem<TArgs...>(std::forward<TArgs>(args)...);
item->LinkBefore(pos.Item());
return item;
}
iterator Erase(iterator pos) {
ReleaseItem(&*pos++);
return pos;
}
iterator Erase(iterator first, iterator last) {
TList temp;
TList::Cut(first, last, temp.end());
ReleaseItems(temp);
return last;
}
void EraseFront() {
ReleaseItem(List.PopFront());
}
void EraseBack() {
ReleaseItem(List.PopBack());
}
iterator Splice(iterator pos, TChunkList& from, iterator first, iterator last) {
for (auto it = first; it != last; ) {
if (from.IsInplaceItem(&*it)) {
TList::Cut(first, it, pos);
InsertBefore(pos, std::move(*it));
it = first = from.Erase(it);
} else {
++it;
}
}
TList::Cut(first, last, pos);
return last;
}
operator bool() const { return static_cast<bool>(List); }
TChunk& GetFirstChunk() { return *List.Front(); }
const TChunk& GetFirstChunk() const { return *List.Front(); }
TChunk& GetLastChunk() { return *List.Back(); }
iterator begin() { return List.begin(); }
const_iterator begin() const { return List.begin(); }
iterator end() { return List.end(); }
const_iterator end() const { return List.end(); }
};
} // NRopeDetails
|
