GODOT IS OPEN SOURCE

1 files changed, 198 insertions, 0 deletions

diff --git a/core/allocators.h b/core/allocators.h
new file mode 100644
index 0000000000..42eb4effaf
--- /dev/null
+++ b/core/allocators.h
@@ -0,0 +1,198 @@
+/*************************************************************************/
+/*  allocators.h                                                         */
+/*************************************************************************/
+/*                       This file is part of:                           */
+/*                           GODOT ENGINE                                */
+/*                    http://www.godotengine.org                         */
+/*************************************************************************/
+/* Copyright (c) 2007-2014 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