ref: f2a1c2c13ea8f9e0ece5500dd7783754362c3099
parent: 596459dd77e5c3e66a57be31e711a58624024881
author: qwx <[email protected]>
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;
}