1 files changed, 254 insertions, 0 deletions
diff --git a/nestegg/halloc/src/halloc.c b/nestegg/halloc/src/halloc.c
new file mode 100644
index 000000000..38fd6c11a
--- /dev/null
+++ b/nestegg/halloc/src/halloc.c
@@ -0,0 +1,254 @@
+/*
+ *	Copyright (c) 2004i-2010 Alex Pankratov. All rights reserved.
+ *
+ *	Hierarchical memory allocator, 1.2.1
+ *	http://swapped.cc/halloc
+ */
+
+/*
+ *	The program is distributed under terms of BSD license. 
+ *	You can obtain the copy of the license by visiting:
+ *	
+ *	http://www.opensource.org/licenses/bsd-license.php
+ */
+
+#include <stdlib.h>  /* realloc */
+#include <string.h>  /* memset & co */
+
+#include "../halloc.h"
+#include "align.h"
+#include "hlist.h"
+
+/*
+ *	block control header
+ */
+typedef struct hblock
+{
+#ifndef NDEBUG
+#define HH_MAGIC    0x20040518L
+	long          magic;
+#endif
+	hlist_item_t  siblings; /* 2 pointers */
+	hlist_head_t  children; /* 1 pointer  */
+	max_align_t   data[1];  /* not allocated, see below */
+	
+} hblock_t;
+
+#define sizeof_hblock offsetof(hblock_t, data)
+
+/*
+ *
+ */
+realloc_t halloc_allocator = NULL;
+
+#define allocator halloc_allocator
+
+/*
+ *	static methods
+ */
+static void _set_allocator(void);
+static void * _realloc(void * ptr, size_t n);
+
+static int  _relate(hblock_t * b, hblock_t * p);
+static void _free_children(hblock_t * p);
+
+/*
+ *	Core API
+ */
+void * halloc(void * ptr, size_t len)
+{
+	hblock_t * p;
+
+	/* set up default allocator */
+	if (! allocator)
+	{
+		_set_allocator();
+		assert(allocator);
+	}
+
+	/* calloc */
+	if (! ptr)
+	{
+		if (! len)
+			return NULL;
+
+		p = allocator(0, len + sizeof_hblock);
+		if (! p)
+			return NULL;
+#ifndef NDEBUG
+		p->magic = HH_MAGIC;
+#endif
+		hlist_init(&p->children);
+		hlist_init_item(&p->siblings);
+
+		return p->data;
+	}
+
+	p = structof(ptr, hblock_t, data);
+	assert(p->magic == HH_MAGIC);
+
+	/* realloc */
+	if (len)
+	{
+		p = allocator(p, len + sizeof_hblock);
+		if (! p)
+			return NULL;
+
+		hlist_relink(&p->siblings);
+		hlist_relink_head(&p->children);
+		
+		return p->data;
+	}
+
+	/* free */
+	_free_children(p);
+	hlist_del(&p->siblings);
+	allocator(p, 0);
+
+	return NULL;
+}
+
+void hattach(void * block, void * parent)
+{
+	hblock_t * b, * p;
+	
+	if (! block)
+	{
+		assert(! parent);
+		return;
+	}
+
+	/* detach */
+	b = structof(block, hblock_t, data);
+	assert(b->magic == HH_MAGIC);
+
+	hlist_del(&b->siblings);
+
+	if (! parent)
+		return;
+
+	/* attach */
+	p = structof(parent, hblock_t, data);
+	assert(p->magic == HH_MAGIC);
+	
+	/* sanity checks */
+	assert(b != p);          /* trivial */
+	assert(! _relate(p, b)); /* heavy ! */
+
+	hlist_add(&p->children, &b->siblings);
+}
+
+/*
+ *	malloc/free api
+ */
+void * h_malloc(size_t len)
+{
+	return halloc(0, len);
+}
+
+void * h_calloc(size_t n, size_t len)
+{
+	void * ptr = halloc(0, len*=n);
+	return ptr ? memset(ptr, 0, len) : NULL;
+}
+
+void * h_realloc(void * ptr, size_t len)
+{
+	return halloc(ptr, len);
+}
+
+void   h_free(void * ptr)
+{
+	halloc(ptr, 0);
+}
+
+char * h_strdup(const char * str)
+{
+	size_t len = strlen(str);
+	char * ptr = halloc(0, len + 1);
+	return ptr ? (ptr[len] = 0, memcpy(ptr, str, len)) : NULL;
+}
+
+/*
+ *	static stuff
+ */
+static void _set_allocator(void)
+{
+	void * p;
+	assert(! allocator);
+	
+	/*
+	 *	the purpose of the test below is to check the behaviour
+	 *	of realloc(ptr, 0), which is defined in the standard
+	 *	as an implementation-specific. if it returns zero,
+	 *	then it's equivalent to free(). it can however return
+	 *	non-zero, in which case it cannot be used for freeing
+	 *	memory blocks and we'll need to supply our own version
+	 *
+	 *	Thanks to Stan Tobias for pointing this tricky part out.
+	 */
+	allocator = realloc;
+	if (! (p = malloc(1)))
+		/* hmm */
+		return;
+		
+	if ((p = realloc(p, 0)))
+	{
+		/* realloc cannot be used as free() */
+		allocator = _realloc;
+		free(p);
+	}
+}
+
+static void * _realloc(void * ptr, size_t n)
+{
+	/*
+	 *	free'ing realloc()
+	 */
+	if (n)
+		return realloc(ptr, n);
+	free(ptr);
+	return NULL;
+}
+
+static int _relate(hblock_t * b, hblock_t * p)
+{
+	hlist_item_t * i;
+
+	if (!b || !p)
+		return 0;
+
+	/* 
+	 *  since there is no 'parent' pointer, which would've allowed
+	 *  O(log(n)) upward traversal, the check must use O(n) downward 
+	 *  iteration of the entire hierarchy; and this can be VERY SLOW
+	 */
+	hlist_for_each(i, &p->children)
+	{
+		hblock_t * q = structof(i, hblock_t, siblings);
+		if (q == b || _relate(b, q))
+			return 1;
+	}
+	return 0;
+}
+
+static void _free_children(hblock_t * p)
+{
+	hlist_item_t * i, * tmp;
+	
+#ifndef NDEBUG
+	/*
+	 *	this catches loops in hierarchy with almost zero 
+	 *	overhead (compared to _relate() running time)
+	 */
+	assert(p && p->magic == HH_MAGIC);
+	p->magic = 0; 
+#endif
+	hlist_for_each_safe(i, tmp, &p->children)
+	{
+		hblock_t * q = structof(i, hblock_t, siblings);
+		_free_children(q);
+		allocator(q, 0);
+	}
+}
+