Index: trunk/mem.c
===================================================================
--- trunk/mem.c	(revision 1)
+++ trunk/mem.c	(revision 49)
@@ -1,11 +1,33 @@
+#ifdef TEST
+#include <limits.h>
+#include <stdio.h>
+#else
 #include <php.h>
+#endif
+
+#include <assert.h>
 #include <stdlib.h>
+#include <string.h>
 #include "mem.h"
 #include "align.h"
-#define PADD(p, a) (((char*)p) + a)
+
+#ifdef TEST
+#	define ALLOC_DEBUG
+#endif
+#ifdef ALLOC_DEBUG
+#	define ALLOC_DEBUG_BLOCK_CHECK
+#endif
+
+#if 0
+#undef ALLOC_DEBUG_BLOCK_CHECK
+#endif
+
+#define CHAR_PTR(p) ((char *) (p))
+#define PADD(p, a) (CHAR_PTR(p) + a)
+#define PSUB(p1, p2) (CHAR_PTR(p1) - CHAR_PTR(p2))
 
 // {{{ mem
 struct _xc_block_t {
-#ifdef ALLOC_DEBUG
+#ifdef ALLOC_DEBUG_BLOCK_CHECK
 	unsigned int magic;
 #endif
@@ -20,9 +42,11 @@
 };
 
-#ifndef offsetof
-#	define offsetof(type, field) ((int) ((char *) &((type *) 0)->field))
-#endif
+#ifndef XtOffsetOf
+#	include <linux/stddef.h>
+#	define XtOffsetOf(s_type, field) offsetof(s_type, field)
+#endif
+
 #define SizeOf(type, field) sizeof( ((type *) 0)->field )
-#define BLOCK_HEADER_SIZE() (ALIGN( offsetof(xc_block_t, size) + SizeOf(xc_block_t, size) ))
+#define BLOCK_HEADER_SIZE() (ALIGN( XtOffsetOf(xc_block_t, size) + SizeOf(xc_block_t, size) ))
 
 #define BLOCK_MAGIC ((unsigned int) 0x87655678)
@@ -31,5 +55,5 @@
 static inline void xc_block_setup(xc_block_t *b, xc_memsize_t size, xc_block_t *next) /* {{{ */
 {
-#ifdef ALLOC_DEBUG
+#ifdef ALLOC_DEBUG_BLOCK_CHECK
 	b->magic = BLOCK_MAGIC;
 #endif
@@ -38,5 +62,5 @@
 }
 /* }}} */
-#ifdef ALLOC_DEBUG
+#ifdef ALLOC_DEBUG_BLOCK_CHECK
 static void xc_block_check(xc_block_t *b) /* {{{ */
 {
@@ -63,7 +87,17 @@
 	realsize = ALIGN(realsize);
 
+#ifdef ALLOC_DEBUG
+	fprintf(stderr, "avail: %d (%dKB). Allocate size: %d realsize: %d (%dKB)"
+			, mem->avail, mem->avail / 1024
+			, size
+			, realsize, realsize / 1024
+			);
+#endif
 	do {
 		p = NULL;
 		if (mem->avail < realsize) {
+#ifdef ALLOC_DEBUG
+			fprintf(stderr, " oom\n");
+#endif
 			break;
 		}
@@ -94,4 +128,7 @@
 
 		if (b == NULL) {
+#ifdef ALLOC_DEBUG
+			fprintf(stderr, " no fit chunk\n");
+#endif
 			break;
 		}
@@ -105,7 +142,10 @@
 		mem->avail -= realsize;
 
-		/*perfect fit, just unlink */
+		/* perfect fit, just unlink */
 		if (cur->size == realsize) {
 			prev->next = cur->next;
+#ifdef ALLOC_DEBUG
+			fprintf(stderr, " perfect fit. Got: %p\n", p);
+#endif
 			break;
 		}
@@ -126,10 +166,9 @@
 
 #ifdef ALLOC_DEBUG
-		fprintf(stderr, "avail: %d (%dKB). size: %d %d (%dKB) new next: %p offset: %d %dKB\n"
-				, mem->avail, mem->avail/1024
-				, size
-				, realsize, realsize/1024
+		fprintf(stderr, " -> avail: %d (%dKB). new next: %p offset: %d %dKB. Got: %p\n"
+				, mem->avail, mem->avail / 1024
 				, newb
-				, ((char*)newb - mem->rw), ((char*)newb - mem->rw) / 1024
+				, PSUB(newb, mem), PSUB(newb, mem) / 1024
+				, p
 				);
 #endif
@@ -149,5 +188,9 @@
 	int size;
 
-	cur = (xc_block_t *) (((char *) p) - BLOCK_HEADER_SIZE());
+	cur = (xc_block_t *) (CHAR_PTR(p) - BLOCK_HEADER_SIZE());
+#ifdef ALLOC_DEBUG
+	fprintf(stderr, "freeing: %p", p);
+	fprintf(stderr, ", size=%d", cur->size);
+#endif
 	xc_block_check(cur);
 	assert((char*)mem < (char*)cur && (char*)cur < (char*)mem + mem->size);
@@ -164,4 +207,7 @@
 	size = cur->size;
 
+#ifdef ALLOC_DEBUG
+	fprintf(stderr, ", avail %d (%dKB)", mem->avail, mem->avail / 1024);
+#endif
 	mem->avail += size;
 
@@ -171,4 +217,7 @@
 		b->next = cur->next;
 		cur = b;
+#ifdef ALLOC_DEBUG
+		fprintf(stderr, ", combine prev");
+#endif
 	}
 
@@ -178,5 +227,11 @@
 		cur->size += b->size;
 		cur->next = b->next;
-	}
+#ifdef ALLOC_DEBUG
+		fprintf(stderr, ", combine next");
+#endif
+	}
+#ifdef ALLOC_DEBUG
+	fprintf(stderr, " -> avail %d (%dKB)\n", mem->avail, mem->avail / 1024);
+#endif
 	return size;
 }
@@ -246,17 +301,25 @@
 xc_mem_t *xc_mem_init(void *ptr, xc_memsize_t size) /* {{{ */
 {
-	xc_mem_t *mem = (xc_mem_t *) ptr;
-	xc_block_t  *b;
-
+	xc_mem_t   *mem;
+	xc_block_t *b;
+
+#define MINSIZE (ALIGN(sizeof(xc_mem_t)) + sizeof(xc_block_t))
+	/* requires at least the header and 1 tail block */
+	if (size < MINSIZE) {
+		fprintf(stderr, "xc_mem_init requires %d bytes at least\n", MINSIZE);
+		return NULL;
+	}
+	mem = (xc_mem_t *) ptr;
 	mem->size = size;
-	mem->avail = size - ALIGN(sizeof(xc_mem_t));
-
-	/* pointer to first block */
+	mem->avail = size - MINSIZE;
+
+	/* pointer to first block, right after ALIGNed header */
 	b = mem->headblock;
-	xc_block_setup(b, 0, (xc_block_t *)(mem + ALIGN(sizeof(xc_mem_t))));
+	xc_block_setup(b, 0, (xc_block_t *) PADD(mem, ALIGN(sizeof(xc_mem_t))));
 
 	/* first block*/
 	b = b->next;
 	xc_block_setup(b, mem->avail, 0);
+#undef MINSIZE
 
 	return mem;
@@ -267,2 +330,46 @@
 }
 /* }}} */
+
+#ifdef TEST
+/* {{{ */
+#undef CHECK
+#define CHECK(a, msg) do { if ((a) == NULL) { puts(msg); return -1; } } while (0)
+#include <time.h>
+
+int main()
+{
+	int count = 0;
+	void *p;
+	void *memory;
+	xc_mem_t *mem;
+	void **ptrs;
+	int size, i;
+
+#if 0
+	fprintf(stderr, "%s", "Input test size: ");
+	scanf("%d", &size);
+#else
+	size = 100;
+#endif
+	CHECK(memory = malloc(size), "OOM");
+	CHECK(ptrs   = malloc(size * sizeof(void*)), "OOM");
+	CHECK(mem    = xc_mem_init(memory, size), "Failed init memory allocator");
+
+	while ((p = xc_mem_malloc(mem, 1))) {
+		ptrs[count ++] = p;
+	}
+	fprintf(stderr, "count=%d, random freeing\n", count);
+	srandom(time(NULL));
+	while (count) {
+		i = (random() % count);
+		fprintf(stderr, "freeing %d: ", i);
+		xc_mem_free(mem, ptrs[i]);
+		ptrs[i] = ptrs[count - 1];
+		count --;
+	}
+
+	free(memory);
+	return 0;
+}
+/* }}} */
+#endif