/prog/ - shitalloc.c

Name: Anonymous 2009-02-02 2:34

I was bored, so I wrote an extremely shitty "memory allocator", if you could call it that.



#include <stdbool.h>

#include <stdlib.h>



typedef struct Node {

    bool   in_use;      // whether the node is in use.

    size_t size;        // the size of the node

    struct Node  *next; // the next node in the list.

} Node;



static Node *heap = NULL;



void shitalloc_init(size_t size)

{

    if((heap = malloc(size))) {

        heap->in_use = false;

        heap->size   = size - sizeof(Node);

        heap->next   = NULL;

    }

}



void shitalloc_cleanup()

{

    free(heap);

}



void *shitalloc(size_t size)

{

    Node *n = heap;

    void *ptr = NULL;

    

    // Look for a node that's not in use and that's big enough.

    while(n && (n->in_use || n->size < size))

        n = n->next;



    // If we've found a node that's too big, split it up.

    if(n && n->size > size) {

        Node *n2   = (void*)n + sizeof(Node) + size;

        n2->in_use = false;

        n2->size   = n->size - size - sizeof(Node);

        n2->next   = n->next;

        n->next    = n2;

        n->size    = size;

    }



    // If we've found a node, mark it as in-use and get the pointer.

    if(n) {

        n->in_use = true;

        ptr = (void*)n + sizeof(Node);

    }



    return ptr;

}



void shitfree(void *ptr)

{

    Node *n;



    if(ptr) {

        n = ptr - sizeof(Node);

        n->in_use = false;

    }

}



size_t shitused()

{

    Node *n;

    size_t size = 0;



    for(n = heap; n; n = n->next)

        size += sizeof(Node) + (n->in_use ? n->size : 0);



    return size;

}

Name: Anonymous 2009-02-02 12:31

OP here, here's basically the same thing as >>1 but changed to be an actual allocator using sbrk().

myalloc.c



#include "myalloc.h"

#include <stdbool.h>

#include <unistd.h>



struct Node {

    bool   in_use; // flag whether this block is in use.

    size_t size;   // the size of this block in bytes.

};

typedef struct Node Node;



static Node *heap = NULL;



void *myalloc(size_t size)

{

    Node *n;

    void *pbrk = NULL;

    void *ptr  = NULL;



    // No heap? Then make one!

    if(!heap) {

        // The heap will start at the end of the program break.

        heap = sbrk(0);



        // Allocate enough for two requests of this size.

        sbrk(2 * (size + sizeof(Node)));



        // Structure the heap correctly.

        heap->in_use = false;

        heap->size   = (pbrk = sbrk(0)) - (void*)heap - sizeof(Node);

    }



    // If we don't know where the program break is, find it.

    if(!pbrk)

        pbrk = sbrk(0);



    // Try to find a node within the heap that's free and has enough space.

    for(n = heap;

        (void*)n < pbrk && (n->in_use || size > n->size);

        n = (void*)n + n->size + sizeof(Node));



    // If the node isn't within the heap, then we gotta expand the heap.

    if(n == pbrk) {

        // Allocate enough for this request and another same-sized request.

        sbrk(2 * (size + sizeof(Node)));

        pbrk = sbrk(0);



        // Structure the heap correctly.

        n->in_use = false;

        n->size   = pbrk - (void*)n - sizeof(Node);

    }



    // If the node is too big for this request, split it up.

    if(n->size > size) {

        Node *n2 = (void*)n + size + sizeof(Node);

        n2->in_use = false;

        n2->size   = n->size - size - sizeof(Node);

        n->size    = size;

    }



    // If we really have a node, get the pointer.

    if(n) {

        n->in_use = true;

        ptr = (void*)n + sizeof(Node);

    }



    return ptr;

}



void myfree(void *ptr)

{

    Node *n = ptr - sizeof(Node);

    void *pbrk = sbrk(0);

    bool in_use;



    // Deallocate the node!

    n->in_use = in_use = false;



    // See if everything from here until the break is not in use.

    for(; !in_use && (void*)n < pbrk; n = (void*)n + n->size + sizeof(Node))

        in_use = in_use || n->in_use;



    // If nothing is in use, shrink the heap.

    if(!in_use)

        sbrk(-(pbrk - ptr) - sizeof(Node));

}



size_t myheapsize()

{

    return sbrk(0) - (void*)heap;

}

myalloc.h



#ifndef MYALLOC_H

#define MYALLOC_H



#include <stddef.h>



void *myalloc(size_t size);

void myfree(void *ptr);

size_t myheapsize();



#endif

test.c



#include "myalloc.h"

#include <stdio.h>



struct Foo

{

    int    foo;

    char   bar;

    double baz;

};



int main()

{

    void *p = myalloc(1024);

    printf("p: %p\n", p);

    printf("heap size: %zu\n", myheapsize());



    struct Foo *f = myalloc(sizeof(struct Foo));

    f->foo = 123;

    f->bar = '!';

    f->baz = 3.14;

    printf("f: %p\n", f);

    printf("heap size: %zu\n", myheapsize());



    void *q = myalloc(1024);

    printf("q: %p\n", q);

    printf("heap size: %zu\n", myheapsize());



    myfree(q);

    printf("Freed q\n");

    printf("heap size: %zu\n", myheapsize());



    q = myalloc(1024);

    printf("q: %p\n", q);

    printf("heap size: %zu\n", myheapsize());



    myfree(q);

    myfree(f);

    myfree(p);

    printf("heap size: %zu\n", myheapsize());



    f = myalloc(sizeof(struct Foo));

    printf("heap size: %zu\n", myheapsize());

    myfree(f);

    printf("heap size: %zu\n", myheapsize());



    return 0;

}

shitalloc.c

1 Name: Anonymous 2009-02-02 2:34

10 Name: Anonymous 2009-02-02 12:31

Name: Anonymous 2009-02-02 2:34

Name: Anonymous 2009-02-02 12:31