shithub: asif

Download patch

ref: 516586152ab26883f5e57436634d9e5a715ff60a
parent: 2603b42d0f2caa502411848f7c4062e290dde2dd
author: qwx <qwx@sciops.net>
date: Tue Feb 22 21:33:52 EST 2022 

import simple quad trees from sce


--- a/asif.h
+++ b/asif.h
@@ -32,6 +32,20 @@
 void*	pushvec(Vector*, void*);
 void*	newvec(Vector*, int, int);
 
+typedef struct QNode QNode;
+struct QNode{
+	QNode *left;
+	QNode *right;
+	QNode *up;
+	QNode *down;
+	void *aux;
+
+	QNode *prev;
+	QNode *next;
+};
+QNode*	qtmerge(QNode*);
+QNode*	qtsplit(QNode*);
+
 u32int	next32pow2(u32int);
 int	lsb64(uvlong);
 int	msb64(uvlong);
--- /dev/null
+++ b/qtree.c
@@ -1,0 +1,75 @@
+#include <u.h>
+#include <libc.h>
+#include "asif.h"
+
+enum{
+	Ninc = 128,
+};
+
+/* 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)
+{
+	if(q == nil)
+		return nil;
+	qtmerge(q->left);
+	qtmerge(q->right);
+	qtmerge(q->up);
+	qtmerge(q->down);
+	qtfree(q->left);
+	qtfree(q->right);
+	qtfree(q->up);
+	qtfree(q->down);
+	q->left = q->right = q->up = q->down = nil;
+	return q;
+}
+
+QNode *
+qtsplit(QNode *q)
+{
+	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();
+	return q;
+}