/* 세대 번호를 단 핸들 --- 댕글링 포인터를 *검출할 수 있는* 참조.
 * 포인터 대신 (칸 번호, 세대)를 건넨다. 칸을 돌려받을 때마다 그 칸의 세대를 올리므로,
 * 옛 핸들은 세대가 맞지 않아 「이미 죽은 객체」로 판정된다. 칸은 다시 쓰여도 된다. */
#include <stdint.h>
#include <stdio.h>

enum { SLOTS = 4 };

typedef struct { uint32_t index, gen; } handle;

typedef struct {
    double   value[SLOTS];
    uint32_t gen[SLOTS];        /* 칸마다의 세대 */
    bool     used[SLOTS];
} pool;

static bool pool_new(pool *p, double v, handle *out)
{
    for (uint32_t i = 0; i < SLOTS; i++) {
        if (!p->used[i]) {
            p->used[i] = true;
            p->value[i] = v;
            *out = (handle){ i, p->gen[i] };
            return true;
        }
    }
    return false;               /* 빈칸이 없다 */
}

static void pool_free(pool *p, handle h)
{
    if (h.index < SLOTS && p->used[h.index] && p->gen[h.index] == h.gen) {
        p->used[h.index] = false;
        p->gen[h.index]++;      /* ★ 이 칸을 가리키던 모든 핸들이 이 순간 낡는다 */
    }
}

/* 살아 있는 객체면 그 자리를, 아니면 NULL 을 돌려준다 --- 쓰기 전에 *물어볼 수* 있다. */
static double *pool_get(pool *p, handle h)
{
    if (h.index >= SLOTS || !p->used[h.index] || p->gen[h.index] != h.gen)
        return NULL;
    return &p->value[h.index];
}

static void show(pool *p, const char *name, handle h)
{
    double *v = pool_get(p, h);
    if (v) printf("%-6s (slot %u, gen %u) -> %.1f\n", name, (unsigned)h.index, (unsigned)h.gen, *v);
    else   printf("%-6s (slot %u, gen %u) -> stale handle, object is gone\n",
                  name, (unsigned)h.index, (unsigned)h.gen);
}

int main(void)
{
    pool p = {0};
    handle a, b;
    if (!pool_new(&p, 1.5, &a)) return 1;
    show(&p, "a", a);

    pool_free(&p, a);               /* a 가 가리키던 객체를 돌려준다 */
    if (!pool_new(&p, 9.0, &b)) return 1;  /* 같은 칸이 다시 쓰인다 */
    show(&p, "b", b);
    show(&p, "a", a);               /* 포인터였다면 b 의 값을 읽었을 자리 */
    return 0;
}

/* 작은 점검용 할당자 --- 빌린 블록마다 장부에 적는다.
 * 돌려받은 블록은 곧바로 풀지 않고 *격리*해 둔다(독 0xDD 를 칠해서). 그래서 두 번째
 * 해제가 와도 그 주소는 아직 살아 있는 객체를 가리키고, 장부와 견줘 볼 수 있다.
 * 진짜로 풀어 버렸다면 그 포인터 값을 쓰는 것부터가 계약 밖이다(C23 6.2.4p2). */
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

enum { MAX_BLOCKS = 16 };

typedef struct {
    unsigned char *p;
    size_t size;
    const char *where;
    bool released;          /* 돌려받았으나 격리 중 */
} entry;
static entry book[MAX_BLOCKS];

static void *chk_malloc(size_t size, const char *where)
{
    for (size_t i = 0; i < MAX_BLOCKS; i++) {
        if (book[i].p == NULL) {
            unsigned char *p = malloc(size);
            if (p == NULL) return NULL;
            book[i] = (entry){ p, size, where, false };
            return p;
        }
    }
    return NULL;                        /* 장부가 찼다 */
}

static void chk_free(void *ptr, const char *where)
{
    if (ptr == NULL) return;
    unsigned char *p = ptr;
    for (size_t i = 0; i < MAX_BLOCKS; i++) {
        entry *e = &book[i];
        if (e->p == NULL) continue;
        if (p == e->p) {
            if (e->released) {
                printf("  %s: double free of the block from %s\n", where, e->where);
            } else {
                memset(e->p, 0xDD, e->size);    /* 독 칠하기 */
                e->released = true;             /* 격리: 아직 free 하지 않는다 */
            }
            return;
        }
        /* 「이 블록 안인가」는 포인터의 < 로 묻지 않는다 --- 서로 다른 객체의 포인터를
           크기로 견주는 것은 계약 밖이다(6.5.9). 정수로 바꾼 주소로 묻는다(구현 정의). */
        uintptr_t a = (uintptr_t)p, lo = (uintptr_t)e->p;
        if (a > lo && a - lo < e->size) {
            printf("  %s: free of an address inside the block from %s (offset %ju)\n",
                   where, e->where, (uintmax_t)(a - lo));
            return;
        }
    }
    printf("  %s: free of a pointer this allocator never gave out\n", where);
}

/* 끝에서: 돌려받지 못한 것은 누수로 알리고, 격리한 것까지 모두 실제로 푼다. */
static void chk_finish(void)
{
    for (size_t i = 0; i < MAX_BLOCKS; i++) {
        if (book[i].p == NULL) continue;
        if (!book[i].released)
            printf("  leak: %zu bytes from %s\n", book[i].size, book[i].where);
        free(book[i].p);
        book[i] = (entry){0};
    }
}

int main(void)
{
    char *name = chk_malloc(16, "line A");
    char *tmp  = chk_malloc(64, "line B");
    int  *nums = chk_malloc(4 * sizeof *nums, "line C");
    if (!name || !tmp || !nums) return 1;

    strcpy(name, "ok");
    chk_free(tmp, "line D");
    chk_free(tmp, "line E");            /* 두 번째 해제 */
    chk_free(name + 1, "line F");       /* 블록의 가운데 */
    chk_free(name, "line G");
    printf("  first byte of the released block from line B: 0x%02X\n",
           (unsigned)(unsigned char)tmp[0]);    /* 격리 중이라 읽어도 계약 안이다 */

    puts("at exit:");
    chk_finish();                       /* nums 는 돌려주지 않았다 */
    return 0;
}

/* 참조 계수 --- 「나를 가리키는 것이 몇인가」를 세어, 0 이 되는 순간 돌려준다.
 * 그리고 그 약점: 서로 가리키는 둘(순환)은 계수가 끝내 0 이 되지 않는다.
 * 한쪽을 *약한 참조*(계수를 올리지 않는 참조)로 바꾸면 순환이 풀린다. */
#include <stdio.h>
#include <stdlib.h>

typedef struct node node;
struct node {
    const char *name;
    int   refs;
    node *strong;       /* 계수를 올리는 참조 */
    node *weak;         /* 계수를 올리지 않는 참조 --- 소유하지 않는다 */
};

static int live;        /* 아직 돌려주지 않은 노드 수 */

static node *node_new(const char *name)
{
    node *n = calloc(1, sizeof *n);
    if (n == NULL) exit(1);
    n->name = name;
    n->refs = 1;        /* 만든 쪽이 첫 참조를 쥔다 */
    live++;
    return n;
}

static node *retain(node *n) { if (n) n->refs++; return n; }

static void release(node *n)
{
    if (n == NULL || --n->refs > 0) return;
    printf("  free %s\n", n->name);
    release(n->strong);             /* 내가 쥔 강한 참조를 놓는다 */
    free(n);
    live--;
}

int main(void)
{
    puts("cycle of two strong references:");
    node *a = node_new("a"), *b = node_new("b");
    a->strong = retain(b);
    b->strong = retain(a);          /* a -> b -> a */
    release(a);
    release(b);                     /* 바깥 참조를 다 놓았다 */
    printf("  still alive: %d (a.refs %d, b.refs %d) --- leaked\n", live, a->refs, b->refs);

    /* 시연이 끝났으니 손으로 끊어 정리한다 --- 수집기가 없으면 이 일은 사람 몫이다. */
    a->strong = NULL; b->strong = NULL;
    free(a); free(b); live -= 2;

    puts("same shape, back edge made weak:");
    node *c = node_new("c"), *d = node_new("d");
    c->strong = retain(d);
    d->weak = c;                    /* d -> c 는 계수를 올리지 않는다 */
    release(c);
    release(d);
    printf("  still alive: %d\n", live);
    return 0;
}

/* 장난감 표시-쓸기 수집기 --- 「뿌리에서 닿을 수 있는가」로 살고 죽음을 가른다.
 * 참조 계수가 못 거둔 순환도, 뿌리에서 끊기면 거둔다. 실제 수집기와 달리 뿌리를
 * 손으로 등록한다 --- C 에는 「어디가 포인터인가」를 알려 주는 장부가 없기 때문이다. */
#include <stdio.h>
#include <stdlib.h>

typedef struct obj obj;
struct obj {
    char  name;
    obj  *ref[2];       /* 다른 객체를 가리키는 칸 둘 */
    bool  marked;
    int   survived;     /* 수집을 몇 번 살아남았나 */
    obj  *next_alloc;   /* 수집기가 아는 모든 객체의 목록 */
};

static obj *all;                /* 할당한 모든 객체 */
static obj *roots[4];           /* 뿌리: 프로그램이 지금 쥐고 있는 것 */

static obj *gc_new(char name)
{
    obj *o = calloc(1, sizeof *o);
    if (o == NULL) exit(1);
    o->name = name;
    o->next_alloc = all;
    all = o;
    return o;
}

static void mark(obj *o)
{
    obj *stack[64];             /* 재귀 대신 명시적 스택 --- 깊은 그래프에서 호출 스택을 넘치지 않게 */
    size_t top = 0;
    if (o) stack[top++] = o;
    while (top > 0) {
        obj *x = stack[--top];
        if (x->marked) continue;        /* 순환이어도 한 번만 표시한다 */
        x->marked = true;
        for (int i = 0; i < 2; i++)
            if (x->ref[i] && !x->ref[i]->marked && top < sizeof stack / sizeof stack[0])
                stack[top++] = x->ref[i];
    }
}

static void collect(void)
{
    for (size_t i = 0; i < sizeof roots / sizeof roots[0]; i++)
        mark(roots[i]);                 /* ① 표시: 뿌리에서 닿는 것 */

    printf("  freed:");
    for (obj **p = &all; *p != NULL; ) { /* ② 쓸기: 표시가 없는 것을 돌려준다 */
        obj *o = *p;
        if (!o->marked) {
            *p = o->next_alloc;
            printf(" %c", o->name);
            free(o);
        } else {
            o->marked = false;          /* 다음 수집을 위해 지운다 */
            o->survived++;
            p = &o->next_alloc;
        }
    }
    printf("\n  alive:");
    for (obj *o = all; o != NULL; o = o->next_alloc)
        printf(" %c(survived %d)", o->name, o->survived);
    printf("\n");
}

int main(void)
{
    obj *a = gc_new('a'), *b = gc_new('b'), *c = gc_new('c');
    a->ref[0] = b;
    b->ref[0] = c;
    c->ref[0] = b;                      /* b <-> c 순환 */
    roots[0] = a;
    (void)gc_new('t');                  /* 아무도 쥐지 않는 임시 객체 */

    puts("collection 1 (root: a):");
    collect();

    a->ref[0] = NULL;                   /* a 에서 순환으로 가는 길을 끊는다 */
    (void)gc_new('u');
    puts("collection 2 (a no longer points at the cycle):");
    collect();

    roots[0] = NULL;                    /* 뿌리를 비우고 마지막 수집 */
    puts("collection 3 (no roots):");
    collect();
    return 0;
}