allocators.h

/*************************************************************************/
/*  allocators.h                                                         */
/*************************************************************************/
/*                       This file is part of:                           */
/*                           GODOT ENGINE                                */
/*                    http://www.godotengine.org                         */
/*************************************************************************/
/* Copyright (c) 2007-2016 Juan Linietsky, Ariel Manzur.                 */
/*                                                                       */
/* Permission is hereby granted, free of charge, to any person obtaining */
/* a copy of this software and associated documentation files (the       */
/* "Software"), to deal in the Software without restriction, including   */
/* without limitation the rights to use, copy, modify, merge, publish,   */
/* distribute, sublicense, and/or sell copies of the Software, and to    */
/* permit persons to whom the Software is furnished to do so, subject to */
/* the following conditions:                                             */
/*                                                                       */
/* The above copyright notice and this permission notice shall be        */
/* included in all copies or substantial portions of the Software.       */
/*                                                                       */
/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,       */
/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF    */
/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/
/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY  */
/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,  */
/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE     */
/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.                */
/*************************************************************************/
#ifndef ALLOCATORS_H
#define ALLOCATORS_H

#include "os/memory.h"
template<int PREALLOC_COUNT=64, int MAX_HANDS=8>
class BalloonAllocator {

    enum {

        USED_FLAG=(1<<30),
        USED_MASK=USED_FLAG-1
    };

    struct Balloon {

        Balloon *next;
        Balloon *prev;
        uint32_t hand;
    };


    struct Hand {

        int used;
        int allocated;
        Balloon *first;
        Balloon *last;
    };


    Hand hands[MAX_HANDS];



public:

    void* alloc(size_t p_size) {

        size_t max=(1<<MAX_HANDS);
        ERR_FAIL_COND_V( p_size>max, NULL );

        unsigned int hand=0;

        while(p_size>(size_t)(1<<hand)) ++hand;

        Hand &h=hands[hand];

        if (h.used==h.allocated) {

            for(int i=0;i<PREALLOC_COUNT;i++) {

                Balloon *b = (Balloon*)memalloc(sizeof(Balloon)+(1<<hand));
                b->hand=hand;
                if (h.last) {

                    b->prev=h.last;
                    h.last->next=b;
                    h.last=b;
                } else {

                    b->prev=NULL;
                    h.last=b;
                    h.first=b;
                }
            }

            h.last->next=NULL;
            h.allocated+=PREALLOC_COUNT;
        }

        Balloon *pick=h.last;

        ERR_FAIL_COND_V( (pick->hand&USED_FLAG), NULL );

        // remove last
        h.last=h.last->prev;
        h.last->next=NULL;

        pick->next=h.first;
        h.first->prev=pick;
        pick->prev=NULL;
        h.first=pick;
        h.used++;
        pick->hand|=USED_FLAG;

        return (void*)(pick+1);
    }

    void free(void* p_ptr) {

        Balloon *b=(Balloon*)p_ptr;
        b-=1;

        ERR_FAIL_COND(!(b->hand&USED_FLAG) );

        b->hand=b->hand&USED_MASK; // not used
        int hand=b->hand;

        Hand &h=hands[hand];

        if (b==h.first)
            h.first=b->next;

        if (b->prev)
            b->prev->next=b->next;
        if (b->next)
            b->next->prev=b->prev;

        if (h.last!=b) {
            h.last->next=b;
            b->prev=h.last;
            b->next=NULL;
            h.last=b;
        }

        h.used--;

        if (h.used<=(h.allocated-(PREALLOC_COUNT*2))) { // this is done to ensure no alloc/free is done constantly

            for(int i=0;i<PREALLOC_COUNT;i++) {
                ERR_CONTINUE( h.last->hand& USED_FLAG );

                Balloon *new_last=h.last->prev;
                if (new_last)
                    new_last->next=NULL;
                memfree( h.last );
                h.last=new_last;
            }
            h.allocated-=PREALLOC_COUNT;
        }
    }

    BalloonAllocator() {

        for(int i=0;i<MAX_HANDS;i++) {

            hands[i].allocated=0;
            hands[i].used=0;
            hands[i].first=NULL;
            hands[i].last=NULL;
        }

    }

    void clear() {

        for(int i=0;i<MAX_HANDS;i++) {

            while(hands[i].first) {

                Balloon *b=hands[i].first;
                hands[i].first=b->next;
                memfree(b);
            }

            hands[i].allocated=0;
            hands[i].used=0;
            hands[i].first=NULL;
            hands[i].last=NULL;
        }
    }

    ~BalloonAllocator() {

        clear();
    }
};


#endif // ALLOCATORS_H