tngc.c

/*
 * tngc.c
 *
 * The garbage collection algorithm to be used by Typhon's C platform, possibly.
 *
 *  Created on: Aug 11, 2015
 *      Author: jrobbins
 */

#include "tngc.h"

#include <stdio.h>

tngc_blist* tngc_blocks = NULL;

void tngc_deplist_add(tngc_binfo* binfo, tngc_deplist* deplist) {
    tngc_deplist* node = binfo->deps;

    if (node == NULL) {
        binfo->deps = deplist;
        return;
    }

    while (node->next != NULL) {
        node = node->next;
    }

    node->next = deplist;
}

void tngc_deplist_del(tngc_binfo* binfo, tngc_binfo* deplist) {
    tngc_deplist* node = binfo->deps;
    tngc_deplist* prev = NULL;

    if (node->dep == deplist) {
        binfo->deps = node->next;
        free(node);
        return;
    }

    while (node != NULL) {
        if (node->dep == deplist) {
            prev->next = node->next;
            free(node);
            return;
        }

        prev = node;
        node = node->next;
    }

    prev->next = NULL;
    free(node);
}

void tngc_blist_add(tngc_blist* blist) {
    tngc_blist* node = tngc_blocks;

    if (node == NULL) {
        tngc_blocks = blist;
        return;
    }

    while (node->next != NULL) {
        node = node->next;
    }

    node->next = blist;
}

void tngc_blist_del(tngc_blist* blist) {
    tngc_blist* node = tngc_blocks;
    tngc_blist* prev = NULL;

    if (node == blist) {
        tngc_blocks = node->next;
        return;
    }

    while (node != NULL) {
        if (node == blist) {
            prev->next = node->next;
            return;
        }

        prev = node;
        node = node->next;
    }

    prev->next = NULL;
}

tngc_blist* tngc_blist_from_data(void* data) {
    tngc_blist* node = tngc_blocks;

    while (node != NULL) {
        if (data >= node->info.data && data < node->info.data+node->info.size) {
            return node;
        }
        node = node->next;
    }

    return NULL;
}

void* tngc_alloc(size_t size) {
    //allocate the data and the block info
    void* data = malloc(size);
    if (data == NULL) {
        //out of memory, do a GC pass and retry if space was collected
        if (!tngc_single_pass()) {
            return NULL;
        } else {
            return tngc_alloc(size);
        }
    }
    tngc_blist* blist = malloc(sizeof(tngc_blist));
    if (blist == NULL) {
        //out of memory, do a GC pass and retry if space was collected
        free(data);
        if (!tngc_single_pass()) {
            return NULL;
        } else {
            return tngc_alloc(size);
        }
    }

    blist->info.data = data;
    blist->info.size = size;
    blist->info.refs = 1;
    blist->info.deps = NULL;
    blist->next = NULL;

    tngc_blist_add(blist);

    return data;
}

void* tngc_realloc(void* data, size_t size) {
    tngc_blist* blist = tngc_blist_from_data(data);
    if (blist == NULL || blist->info.data != data) {
        //either double free or incorrectly aligned free
        return NULL;
    }

    void* new_data = realloc(data, size);
    if (new_data == NULL) {
        //out of memory, do a GC pass and retry if space was collected
        if (!tngc_single_pass()) {
            return NULL;
        } else {
            return tngc_realloc(data, size);
        }
    }

    blist->info.data = new_data;
    blist->info.size = size;

    return new_data;
}

void tngc_free(void* data) {
    tngc_blist* blist = tngc_blist_from_data(data);
    if (blist == NULL || blist->info.data != data) {
        //either double free or incorrectly aligned free
        return;
    }

    tngc_free_dlist(blist->info.deps);
    tngc_blist_del(blist);
    free(blist->info.data);
    free(blist);
}

void tngc_free_dlist(tngc_deplist* node) {
    if (node == NULL) {
        return;
    }
    (((tngc_binfo*)node->dep)->refs)--;
    tngc_deplist* node2 = node->next; //this is so maybe we can tail recurse??
    free(node);
    tngc_free_dlist(node2);
}

void tngc_open(void* data) {
    tngc_blist* blist = tngc_blist_from_data(data);
    if (blist == NULL) {
        //isn't actually an allocated block
        return;
    }

    (blist->info.refs)++;
}

void tngc_close(void* data) {
    tngc_blist* blist = tngc_blist_from_data(data);
    if (blist == NULL) {
        //isn't actually an allocated block
        return;
    }

    (blist->info.refs)--;
}

void tngc_link(void* user, void* usee) {
    tngc_blist* user_blist = tngc_blist_from_data(user);
    if (user_blist == NULL) {
        //isn't actually an allocated block
        return;
    }
    tngc_blist* usee_blist = tngc_blist_from_data(usee);
    if (usee_blist == NULL) {
        //isn't actually an allocated block
        return;
    }
    tngc_deplist* deplist = malloc(sizeof(tngc_deplist));
    if (deplist == NULL) {
        //out of memory, do a GC pass and retry if space was collected
        if (!tngc_single_pass()) {
            return;
        }
        tngc_link(user, usee);
        return;
    }
    deplist->dep = usee_blist;
    deplist->next = NULL;
    tngc_deplist_add(&(user_blist->info), deplist);
    (usee_blist->info.refs)++;
}

void tngc_unlink(void* user, void* usee) {
    tngc_blist* user_blist = tngc_blist_from_data(user);
    if (user_blist == NULL) {
        //isn't actually an allocated block
        return;
    }
    tngc_blist* usee_blist = tngc_blist_from_data(usee);
    if (usee_blist == NULL) {
        //isn't actually an allocated block
        return;
    }
    tngc_deplist_del(&(user_blist->info), &(usee_blist->info));
    (usee_blist->info.refs)--;
}

int tngc_single_pass() {
    tngc_blist* node = tngc_blocks;

    while (node != NULL) {
        if (node->info.refs == 0) {
            tngc_free(node->info.data);
            return 1;
        }
        node = node->next;
    }

    return 0;
}

int tngc_pass() {
    int res = 0;
    do {
        if (!tngc_single_pass()) {
            return res;
        } else {
            res = 1;
        }
    } while (1);
}

void tngc_dump() {
    int i = 1;

    printf("== TNGC DUMP ==\n");

    tngc_blist* node = tngc_blocks;

    while (node != NULL) {
        printf("\tNode %i: %p\n", i, node);
        printf("\t\tSize: %i\n", node->info.size);
        printf("\t\tRefs: %i\n", node->info.refs);
        printf("\t\tData: %p\n", node->info.data);
        printf("\t\tDeps:\n");

        int ii = 1;
        tngc_deplist* node2 = node->info.deps;
        while (node2 != NULL) {
            printf("\t\t\t%i: %p\n", ii, node2->dep);
            ii++;
            node2 = node2->next;
        }
        i++;
        node = node->next;
    }
}


/*
 * tngc.h
 *
 *  Created on: Aug 11, 2015
 *      Author: jrobbins
 */

#ifndef TNGC_H_
#define TNGC_H_

#include <stdlib.h>

#define TNGC_INIT_BLOCK_SPACE 256
#define TNGC_INIT_DEPLIST_SPACE 4

typedef struct tngc_deplist {
    void* dep;
    struct tngc_deplist* next;
} tngc_deplist;

typedef struct tngc_binfo {
    unsigned int refs;
    tngc_deplist* deps;
    size_t size;
    void* data;
} tngc_binfo;

typedef struct tngc_blist {
    tngc_binfo info;
    struct tngc_blist* next;
} tngc_blist;

tngc_blist* tngc_blocks;

void tngc_deplist_add(tngc_binfo* binfo, tngc_deplist* deplist);
void tngc_deplist_del(tngc_binfo* binfo, tngc_binfo* deplist);
void tngc_blist_add(tngc_blist* blist);
tngc_blist* tngc_blist_from_data(void* data);
void* tngc_alloc(size_t size);
void* tngc_realloc(void* data, size_t size);
void tngc_free(void* data);
void tngc_free_dlist(tngc_deplist* node);
void tngc_open(void* data);
void tngc_close(void* data);
void tngc_link(void* user, void* usee);
void tngc_unlink(void* user, void* usee);
int tngc_single_pass();
int tngc_pass();

void tngc_dump();

#endif /* TNGC_H_ */