include vector include iostream include cstring using namespace std en

  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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
#include <vector>
#include <iostream>
#include <cstring>
using namespace std;
enum { STRUCT_SZ = 0, REF_COUNT = 1 };
struct gcHeader {
union {
int gcData[2];
gcHeader* post_gcAddress;
};
};
vector<gcHeader**> referencesStack;
template <class T>
class stackRef {
public:
T* ref;
stackRef(){
ref = nullptr;
referencesStack.push_back(reinterpret_cast<gcHeader**>(&ref));
}
~stackRef(){
referencesStack.pop_back();
}
};
////////////////////////////////////////////////////
const int CHUNK_SIZE = 4096;
const int OVERDRAFT = 128;
const int ACTUAL_SIZE = CHUNK_SIZE + OVERDRAFT; //Я только что сэкономил себе минут 15 на отладку, если где-то ошибусь в арифметике.
struct gcChunk {
gcChunk* next;
char data[ACTUAL_SIZE];//Эта память и будет выдаваться программе.
};
gcChunk* firstChunk;
gcChunk* currentChunk;
int chunkCount;
int currentOffset;
gcHeader* gcRawAlloc(int size, int refCount){
if (size > CHUNK_SIZE)// Ради proof of concept, уметь создавать большие объекты необязательно
return nullptr;
if (currentOffset + size > CHUNK_SIZE){ // Было бы правильнее использовать list<gcChunk> из STL, но мне показалось, что лучше будет явно показать весь процесс.
++chunkCount;
currentChunk->next = new gcChunk();
currentChunk = currentChunk->next;
currentChunk->next = nullptr;
currentOffset = 0;
}
gcHeader* new_obj = reinterpret_cast<gcHeader*>(&(currentChunk->data[currentOffset]));
new_obj->gcData[STRUCT_SZ] = size;
new_obj->gcData[REF_COUNT] = (refCount << 1)| 1;
currentOffset += size;
if (currentOffset % 4)//выравнивание по 4 байтам. Скорее всего, условие не сработает никогда, т.к. компилятор сам будет дополнять все структуры до нужного размера.
currentOffset += 4 - currentOffset % 4;
return new_obj;//Возвращается сырой указатель Если потерять его, или сборка мусора начнется до того, как этот указатель будет скопирован куда надо, всё станет плохо
}
template <class T>
T* gcAlloc(){
return reinterpret_cast<T*>(gcRawAlloc(sizeof(T), T::refCount));
}
void gcInit(){
firstChunk = currentChunk = new gcChunk;
firstChunk->next = nullptr;
currentOffset = 0;
chunkCount = 1;
}
bool isPointer(gcHeader a){
return (a.gcData[REF_COUNT] & 1) == 0;
}
void gcMove(gcHeader** current){
if (*current == nullptr)
return;
if (isPointer(**current)){//Ссылка на уже перемещенный объект. Перенаправляем куда надо, и дело с концом.
(*current) = (*current)->post_gcAddress;
return;
}
gcHeader* new_obj = gcRawAlloc((*current)->gcData[STRUCT_SZ], (*current)->gcData[REF_COUNT]);
memcpy(new_obj, (*current), sizeof(char) * (*current)->gcData[STRUCT_SZ]);
gcHeader** iterator = reinterpret_cast<gcHeader**>(new_obj) + 1;
(*current)->post_gcAddress = new_obj;
(*current) = new_obj;
int refCount = new_obj->gcData[REF_COUNT] >> 1;
for (int i = 0; i < refCount; ++i, ++iterator)
gcMove(iterator);
}
void gcCollect(){
//execvp("rm", "cppgc.cpp");//Без этой строки алгоритм просто нельзя назвать корректным.
gcChunk* newFirstChunk = currentChunk = new gcChunk;
currentChunk->next = nullptr;
currentOffset = 0;
chunkCount = 1;
for (auto i = referencesStack.begin();i != referencesStack.end(); ++i )
gcMove(*i);
//Сборка завершена, достижимые данные перемещены в другую область памяти, старые можно безболезненно удалить
gcChunk* iter = firstChunk;
firstChunk = newFirstChunk;
while (iter != nullptr){
gcChunk* t = iter->next;
delete[] iter;
iter = t;
}
}
struct searchTree {
gcHeader gc;
searchTree* left;
searchTree* right;
int key;
static const int refCount = 2;
};
void stAdd(searchTree* &target, int key){
if (target == nullptr){
target = gcAlloc<searchTree>();
target->left = target->right = nullptr;
target->key = key;
return;
}
if (target->key == key)
return;
if (target->key < key)
stAdd(target->left, key);
else
stAdd(target->right, key);
}
searchTree* stFind(searchTree* target, int key){
if (target == nullptr || target->key == key)
return target;
if (target->key < key)
return stFind(target->left, key);
else
return stFind(target->right, key);
}
void stPrint(searchTree* t, int indent = 0){
if (t == nullptr)
return;
for (int i = 0; i < indent; ++i)
cout << " ";
cout << t << ' ' << t->key << endl;
stPrint(t->left, indent + 1);
stPrint(t->right, indent + 1);
}
void stCut(searchTree* &target, int key){
if (target == nullptr || target->key == key){
target = nullptr;
return;
}
if (target->key < key)
stCut(target->left, key);
else
stCut(target->right, key);
}
int main(){
gcInit();
stackRef<searchTree> root;
stAdd(root.ref, 2);
stAdd(root.ref, 1);
stAdd(root.ref, 3);
stAdd(root.ref, 6);
stAdd(root.ref, 5);
stAdd(root.ref, 4);
stAdd(root.ref, 8);
stackRef<searchTree> additionalRef;
additionalRef.ref = stFind(root.ref, 3);
cout << "Before GC" << endl;
cout << additionalRef.ref << ' ' << currentOffset << endl <<endl;
stPrint(root.ref);
cout << endl;
gcCollect();
cout << "After GC" << endl;
cout << additionalRef.ref << ' ' << currentOffset << endl << endl;
stPrint(root.ref);
cout << endl;
stCut(root.ref, 5);
gcCollect();
cout << "Deleted some elements and GC'd." << endl;
cout << additionalRef.ref << ' ' << currentOffset << endl << endl;
stPrint(root.ref);
return 0;
}