#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct Ptr *Ptr;
typedef struct Ref *Ref;

typedef struct Ptr
{
    Ref ref;
    Ptr next, prev;
} *Ptr;
typedef struct Ref
{
    int *data;
    Ptr head, tail;
} *Ref;

Ref ref_new(int value)
{
    Ref result = malloc(sizeof(struct Ref));

    result->data = malloc(sizeof(int));
    *result->data = value;

    result->head = result->tail = NULL;

    return result;
}

Ref ref_move(Ref ref)
{
    Ref result = malloc(sizeof(struct Ref));

    result->data = ref->data;

    result->head = ref->head;
    result->tail = ref->tail;

    for (Ptr p = ref->head; p != NULL; p = p->next)
    {
        p->ref = result;
    }
    free(ref);
    return result;
}

void ref_add_ptr(Ref ref, Ptr ptr)
{
    if (ref->head == NULL)
    {
        ref->head = ptr;
        ref->tail = ptr;
        ptr->next = ptr->prev = NULL;
        return;
    }
    ref->tail->next = ptr;
    ptr->prev = ref->tail;
    ptr->next = NULL;
    ref->tail = ptr;
}

void ref_remove_ptr(Ref ref, Ptr ptr)
{
    for (Ptr p = ref->head; p != NULL; p = p->next)
    {
        if (p == ptr)
        {
            if (p->prev == NULL)
                ref->head = p->next;
            else
                p->prev->next = p->next;

            if (p->next == NULL)
                ref->tail = p->prev;
            else
                p->next->prev = p->prev;

            return;
        }
    }
}

void ref_free(Ref ref)
{
    for (Ptr p = ref->head; p != NULL; p = p->next)
    {
        p->ref = NULL;
    }
    free(ref->data);
    free(ref);
}

Ptr ptr_new(Ref ref)
{
    Ptr result = malloc(sizeof(struct Ptr));

    result->ref = ref;

    ref_add_ptr(ref, result);

    return result;
}

int ptr_get(Ptr ptr)
{
    if (ptr->ref != NULL)
        return *ptr->ref->data;
    return 0;
}

void ptr_free(Ptr ptr)
{
    if (ptr->ref != NULL)
        ref_remove_ptr(ptr->ref, ptr);
    free(ptr);
}

void test_ref()
{
    Ref r1 = ref_new(123);

    Ptr p1 = ptr_new(r1);
    Ptr p2 = ptr_new(r1);
    Ptr p3 = ptr_new(r1);
    Ptr p4 = ptr_new(r1);

    Ref r2 = ref_move(r1);

    int i = ptr_get(p1) + ptr_get(p2) + ptr_get(p3) + ptr_get(p4);

    ptr_free(p1);
    ptr_free(p2);

    ref_free(r2);

    ptr_free(p3);
    ptr_free(p4);
}

void test_reg()
{
    int *r1 = malloc(sizeof(int));
    *r1 = 123;

    int *p1 = r1;
    int *p2 = r1;
    int *p3 = r1;
    int *p4 = r1;

    int i = *p1 + *p2 + *p3 + *p4;

    int *r2 = r1;
    r1 = NULL;

    free(r2);
}

int main(int argc, char **argv)
{
    const long N = 1000000;

    clock_t start, end;

    start = clock();
    for (long i = 0; i < N; i++)
        test_ref();
    end = clock();
    printf("ref: %fms\n", ((double)(end - start)) / CLOCKS_PER_SEC * 1000);

    start = clock();
    for (long i = 0; i < N; i++)
        test_reg();
    end = clock();
    printf("reg: %fms\n", ((double)(end - start)) / CLOCKS_PER_SEC * 1000);

    return 0;
}