shithub: sce

Download patch

ref: f2a1c2c13ea8f9e0ece5500dd7783754362c3099
parent: 596459dd77e5c3e66a57be31e711a58624024881
author: qwx <qwx@sciops.net>
date: Thu Jun 22 00:53:14 EDT 2023

add pheap fixes from asif

--- a/fns.h
+++ b/fns.h
@@ -68,7 +68,7 @@
 void	nukequeue(Pairheap**);
 Pairheap*	popqueue(Pairheap**);
 void	decreasekey(Pairheap*, double, Pairheap**);
-void	pushqueue(Node*, Pairheap**);
+Pairheap*	pushqueue(Node*, Pairheap**);
 int	lsb(uvlong);
 int	msb(uvlong);
 u64int*	baddr(Point);
--- a/pheap.c
+++ b/pheap.c
@@ -4,18 +4,89 @@
 #include "dat.h"
 #include "fns.h"
 
+/* Fredman, M.L., Sedgewick, R., Sleator, D.D.  et al.  The pairing
+ * heap: A new form of self-adjusting heap.  Algorithmica 1, 111–129
+ * (1986).  */
+
+/* this implementation requires a bigger stack size if the heap can
+ * grow big (8192 is already insufficient with 40-50 nodes);
+ * otherwise, stack overflows hidden behind more cryptic memory pool
+ * corruption errors will occur */
+
+static void
+checkheap(Pairheap *p, Pairheap *queue)
+{
+	Pairheap *q;
+
+	if(p == nil || queue == nil)
+		return;
+	if(p == queue)
+		fprint(2, "pheap::checkheap %#p\n", p);
+	assert(p == queue || p->parent != nil && p->parent != p);
+	assert(p->parent == nil || p->parent->right == p || p->parent->left == p);
+	if(p->parent != nil && p->parent->left == p)
+		assert(p->parent->sum <= p->sum);
+	for(q=p; q!=nil; q=q->right)
+		checkheap(q->left, queue);
+}
+
+static void
+printright(Pairheap *p, int level)
+{
+	int i;
+	Pairheap *q;
+
+	if(p == nil)
+		return;
+	fprint(2, "(\n");
+	for(i=0; i<level; i++)
+		fprint(2, "\t");
+	for(q=p; q!=nil; q=q->right){
+		fprint(2, "[%#p %.5f] — ", q, q->sum);
+		printright(q->left, level+1);
+	}
+	fprint(2, "\n");
+	for(i=0; i<level-1; i++)
+		fprint(2, "\t");
+	fprint(2, ")");
+}
+void
+printqueue(Pairheap **queue)
+{
+	if(queue == nil)
+		return;
+	fprint(2, "pheap::printqueue %#p ", *queue);
+	printright(*queue, 1);
+	fprint(2, "\n");
+}
+
+static void
+debugqueue(Pairheap **queue)
+{
+	if(!debug || queue == nil)
+		return;
+	printqueue(queue);
+	checkheap(*queue, *queue);
+}
+
 static Pairheap *
 mergequeue(Pairheap *a, Pairheap *b)
 {
+	dprint("pheap::mergequeue %#p %.6f b %#p %.6f\n",
+		a, a->sum, b, b!=nil ? b->sum : NaN());
 	if(b == nil)
 		return a;
 	else if(a->sum < b->sum){
 		b->right = a->left;
+		if(a->left != nil)
+			a->left->parent = b;
 		a->left = b;
 		b->parent = a;
 		return a;
 	}else{
 		a->right = b->left;
+		if(b->left != nil)
+			b->left->parent = a;
 		b->left = a;
 		a->parent = b;
 		return b;
@@ -34,8 +105,8 @@
 	if(b == nil)
 		return a;
 	a->right = nil;
-	b->parent = nil;
 	c = b->right;
+	b->parent = nil;
 	b->right = nil;
 	return mergequeue(mergequeue(a, b), mergepairs(c));
 }
@@ -45,8 +116,11 @@
 {
 	Pairheap *p;
 
-	while((p = popqueue(queue)) != nil)
+	dprint("pheap::nukequeue %#p\n", queue);
+	while((p = popqueue(queue)) != nil){
+		debugqueue(&p);
 		free(p);
+	}
 }
 
 Pairheap *
@@ -57,8 +131,10 @@
 	p = *queue;
 	if(p == nil)
 		return nil;
+	dprint("pheap::popqueue %#p %.6f\n", p, p->sum);
 	*queue = mergepairs(p->left);
-	dprint("pop %#p %P g %f sum %f\n", p->n, p->n->Point, p->n->g, p->sum);
+	debugqueue(queue);
+	p->left = p->right = nil;
 	return p;
 }
 
@@ -65,24 +141,38 @@
 void
 decreasekey(Pairheap *p, double Δ, Pairheap **queue)
 {
-	dprint("decrease %#p %P g %f sum %f by %f\n", p->n, p->n->Point, p->n->g, p->sum, Δ);
-	p->sum -= Δ;
-	if(p->parent != nil && p->sum < p->parent->sum){
-		p->parent->left = nil;
-		p->parent = nil;
-		*queue = mergequeue(p, *queue);
+	dprint("pheap::decreasekey %#p %.6f Δ %.6f\n", p, p->sum, Δ);
+	if(p->parent == nil){
+		p->sum -= Δ;
+		return;
 	}
+	if(p->parent->left == p){
+		assert(p->parent->sum <= p->sum);
+		p->parent->left = p->right;
+	}else{
+		assert(p->parent->right == p);
+		p->parent->right = p->right;
+	}
+	if(p->right != nil)
+		p->right->parent = p->parent;
+	p->right = nil;
+	p->parent = nil;
+	p->sum -= Δ;
+	*queue = mergequeue(p, *queue);
+	debugqueue(queue);
 }
 
-void
+Pairheap *
 pushqueue(Node *n, Pairheap **queue)
 {
 	Pairheap *p;
 
 	p = emalloc(sizeof *p);
-	p->n = n;
 	p->sum = n->h + n->g;
+	p->n = n;
 	n->p = p;
-	dprint("push %#p %P g %f sum %f\n", p->n, p->n->Point, p->n->g, p->sum);
+	dprint("pheap::pushqueue %#p %.6f\n", p, p->sum);
 	*queue = mergequeue(p, *queue);
+	debugqueue(queue);
+	return p;
 }