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;
+}