MicroGC/gc.cpp at master · Kerdek/MicroGC · GitHub

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
#include "gc.hpp"

#include <algorithm>
#include <cstring>
#include <stack>
#include <unordered_set>
#include <vector>

namespace gc {

struct cell {
size n, c;
char *p; };

static std::vector<ptr> range;
static std::vector<void (*)(value)> cleanups;
static ptr root;
constexpr size field_size = sizeof(value) + sizeof(type);

ptr alloc() {
ptr const p = new cell{ };
p->n = 0;
p->c = 0;
p->p = 0;
range.push_back(p);
return p; }

void resize(ptr p, size n) {
cell const old = *p;
size const nmin = std::min(n, old.n);
p->n = n;
p->c = n;
p->p = reinterpret_cast<char *>(malloc(p->c * field_size));
if (old.p) {
  memcpy(p->p, old.p, nmin * sizeof(value));
  memcpy(p->p + p->c * sizeof(value), old.p + old.c * sizeof(value), nmin * sizeof(type));
  free(old.p); } }

static void grow(ptr p) {
cell const old = *p;
p->c = p->c ? 2 * p->c : 2;
p->p = reinterpret_cast<char *>(malloc(p->c * field_size));
if (old.p) {
  memcpy(p->p, old.p, p->n * sizeof(value));
  memcpy(p->p + p->c * sizeof(value), old.p + old.c * sizeof(value), p->n * sizeof(type));
  free(old.p); } }

size get_size(ptr p) {
return p->n; }

void push_field(ptr p, type t, value v) {
if (p->c == p->n) {
  grow(p); }
set_field(p, p->n, t, v);
p->n++; }

void pop_field(ptr p) {
p->n--; }

void set_field(ptr p, size i, type t, value v) {
set_type(p, i, t);
set_value(p, i, v); }

void set_type(ptr p, size i, type t) {
*reinterpret_cast<type *>(p->p + p->c * sizeof(value) + i * sizeof(type)) = t; }

void set_value(ptr p, size i, value v) {
*reinterpret_cast<value *>(p->p + i * sizeof(value)) = v; }

type get_type(ptr p, size i) {
return *reinterpret_cast<type *>(p->p + p->c * sizeof(value) + i * sizeof(type)); }

value get_value(ptr p, size_t i) {
return *reinterpret_cast<value *>(p->p + i * sizeof(value)); }

void set_root(ptr p) {
root = p; }

void set_cleanup(size type, void (*f)(value)) {
if (cleanups.size() < type + 1) {
  cleanups.resize(type + 1); }
cleanups[type] = f; }

void cycle() {
std::unordered_set<ptr> s;
s.max_load_factor(0.5);
if (root) {
  std::stack<ptr> stack;
  stack.push(root);
  while (!stack.empty()) {
    ptr p = stack.top();
    stack.pop();
    if (s.find(p) != s.end()) {
      continue; }
    s.insert(p);
    for (size i = 0; i < p->n; i++) {
      if (get_type(p, i) == (type)-1) {
        value const v = get_value(p, i);
        if (v) {
          stack.push(reinterpret_cast<ptr>(v)); } } } } }
const auto pivot = std::partition(range.begin(), range.end(), [&s](ptr p) -> bool {
  auto const it = s.find(p);
  if (it == s.end()) {
    for (size i = 0; i < p->n; i++) {
      type const t = get_type(p, i);
      if (t != (type)-1) {
        cleanups[t](get_value(p, i)); } }
      if (p->p) {
        free(p->p); }
      delete p;
    return false; }
  else {
    return true; } });
range.erase(pivot, range.end()); }

static size const min_trigger = 16;
static size trigger = min_trigger;

void help() {
if (range.size() > trigger) {
  cycle();
  if (range.size() > trigger / 2) {
    trigger *= 2; }
  else if (range.size() < trigger / 4 && trigger > min_trigger) {
    trigger /= 2; } } }

}