ref: fd50731b43864c9e2e7dcaf1a8aae4d3a3c7c8fb
parent: 88d10fd7cc9f47e67c1813b98984e8b3393a71b3
author: qwx <qwx@sciops.net>
date: Tue Feb 22 21:26:49 EST 2022
add simple quadtree implementation
--- a/dat.h
+++ b/dat.h
@@ -18,6 +18,7 @@
typedef struct Cbuf Cbuf;
typedef struct Msg Msg;
typedef struct Vector Vector;
+typedef struct QNode QNode;
enum{Nresource = 3,
@@ -44,6 +45,17 @@
ulong bufsz;
ulong totsz;
int firstempty;
+};
+
+struct QNode{+ QNode *left;
+ QNode *right;
+ QNode *up;
+ QNode *down;
+ void *aux;
+
+ QNode *prev;
+ QNode *next;
};
struct Pairheap{--- /dev/null
+++ b/qtree.c
@@ -1,0 +1,79 @@
+#include <u.h>
+#include <libc.h>
+#include <draw.h>
+#include "dat.h"
+#include "fns.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;
+}
+
+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;
+ dprint("qtmerge %#p\n", q);+ return q;
+}
+
+QNode *
+qtsplit(QNode *q)
+{+ assert(q->left == nil && q->right == nil && q->up == nil && q->down == nil);
+ dprint("qtsplit %#p\n", q);+ q->left = qtalloc();
+ q->right = qtalloc();
+ q->up = qtalloc();
+ q->down = qtalloc();
+ return q;
+}