shithub: asif

--- a/asif.h

+++ b/asif.h

@@ -49,12 +49,10 @@

 	QNode *up;

 	QNode *down;

 	void *aux;

-	QNode *prev;

-	QNode *next;

};

 QNode*	qtmerge(QNode*);

 QNode*	qtsplit(QNode*);

+QNode*	qtnew(void);

 u32int	next32pow2(u32int);

 int	lsb64(uvlong);

@@ -106,6 +104,21 @@

 char*	estrdup(char*);

 void*	erealloc(void*, ulong, ulong);

 void*	emalloc(ulong);

+typedef struct Zpool Zpool;

+typedef struct Znode Znode;

+struct Znode{

+	Znode *next;

+	Znode *prev;

+	void data[];

+};

+struct Zpool{

+	int elsize;

+	Znode;

+};

+void	zfree(Znode*, Zpool*);

+void*	zalloc(Zpool*);

+Zpool*	znew(int);

 #define MIN(a,b)	((a) <= (b) ? (a) : (b))

 #define MAX(a,b)	((a) >= (b) ? (a) : (b))

--- a/qtree.c

+++ b/qtree.c

@@ -2,50 +2,8 @@

 #include <libc.h>

 #include "asif.h"

-enum{

-	Ninc = 128,

-};

+static Zpool *zpool;

-/* no nodes are ever freed */

-static QNode freeq = { .next = &freeq, .prev = &freeq };

-static void

-qtlink(QNode *q)

-{

-	assert(q != nil);

-	q->prev = freeq.prev;

-	q->next = &freeq;

-	freeq.prev->next = q;

-	freeq.prev = q;

-}

-static void

-qtfree(QNode *q)

-{

-	if(q == nil)

-		return;

-	free(q->aux);

-	memset(q, 0, sizeof *q);

-	qtlink(q);

-}

-static QNode *

-qtalloc(void)

-{

-	QNode *q, *fq;

-	if(freeq.next == &freeq){

-		q = emalloc(Ninc * sizeof *q);

-		for(fq=q; fq<q+Ninc; fq++)

-			qtlink(fq);

-	}

-	q = freeq.next;

-	q->next->prev = &freeq;

-	freeq.next = q->next;

-	q->prev = q->next = nil;

-	return q;

-}

 QNode *

 qtmerge(QNode *q)

@@ -55,10 +13,10 @@

 	qtmerge(q->right);

 	qtmerge(q->up);

 	qtmerge(q->down);

-	qtfree(q->left);

-	qtfree(q->right);

-	qtfree(q->up);

-	qtfree(q->down);

+	zfree(q->left, zpool);

+	zfree(q->right, zpool);

+	zfree(q->up, zpool);

+	zfree(q->down, zpool);

 	q->left = q->right = q->up = q->down = nil;

 	return q;

@@ -66,10 +24,23 @@

 QNode *

 qtsplit(QNode *q)

+	if(q == nil)

+		return nil;

 	assert(q->left == nil && q->right == nil && q->up == nil && q->down == nil);

-	q->left = qtalloc();

-	q->right = qtalloc();

-	q->up = qtalloc();

-	q->down = qtalloc();

+	q->left = zalloc(zpool);

+	q->right = zalloc(zpool);

+	q->up = zalloc(zpool);

+	q->down = zalloc(zpool);

+	return q;

+}

+QNode *

+qtnew(void)

+{

+	QNode *q;

+	q = emalloc(sizeof *q);

+	if(zpool == nil)

+		zpool = znew(sizeof *q);

 	return q;

--- /dev/null

+++ b/zalloc.c

@@ -1,0 +1,79 @@

+#include <u.h>

+#include <libc.h>

+#include "asif.h"

+/* no nodes are ever freed, left to be reclaimed by the kernel on exit */

+enum{

+	Ninc = 128,

+};

+static void

+zlink(Znode *p, Zpool *z)

+{

+	assert(p != nil && z != nil);

+	p->prev = z->prev;

+	p->next = &z->Znode;

+	z->prev->next = p;

+	z->prev = p;

+}

+static Znode *

+zunlink(Zpool *z)

+{

+	Znode *q;

+	assert(z != nil && z->next != nil);

+	q = z->next;

+	q->next->prev = &z->Znode;

+	z->next = q->next;

+	q->prev = q->next = nil;

+	return q;

+}

+static void

+zfeed(Zpool *z)

+{

+	int n;

+	uchar *p, *q;

+	assert(z != nil && z->elsize > 0);

+	if(z->next != z)

+		return;

+	n = z->elsize + sizeof *z;

+	p = emalloc(Ninc * n);		// see comment

+	for(q=p; q<p+Ninc*n; q+=n)

+		zlink((Znode*)q, z);

+}

+void

+zfree(Znode *p, Zpool *z)

+{

+	if(p == nil)

+		return;

+	assert(z != nil);

+	memset(p->data, 0, z->elsize);

+	zlink(p, z);

+}

+void *

+zalloc(Zpool *z)

+{

+	Znode *p;

+	zfeed(z);

+	p = zunlink(z);

+	return p->data;

+}

+Zpool *

+znew(int elsize)

+{

+	Zpool *z;

+	assert(elsize > 0);

+	z = emalloc(sizeof *z);

+	z->elsize = elsize;

+	z->next = z->prev = z;

+	zfeed(z);

+	return z;

+}