ref: eb37a4241e5ea1da1c4a7e4614f44888fdbe1511
parent: c85201c11dbbafb78e2a8ab58d6b73f9bc4bbe8d
author: qwx <qwx@sciops.net>
date: Wed Jun 1 22:33:24 EDT 2022
add tests for pairing heaps ... revealing a broken decreasekey operation. yay
--- a/test/pheap.awk
+++ /dev/null
@@ -1,71 +1,0 @@
-#!/bin/awk -f
-BEGIN{- print \
-"#include <u.h>\n" \
-"#include <libc.h>\n" \
-"#include \"asif.h\"\n" \
-"debuglevel = Logtrace;\n\n" \
-"void main(void) {\n" \-"Pairheap *queue, *a;\n" \
-"int i;\n" \
-"queue = nil;\n"
-}
-# pheap::pushqueue addr v
-$1 == "pheap::pushqueue" {- v = $2
- c = int($3 * 1e3)
- if(v in g)
- print "warning: duplicate open node: " $0 >"/fd/2"
- g[v] = c
- if(!(v in n))
- n[v] = ni++
- print \
-"Pairheap *a" n[v] " = pushqueue(" g[v] ", estrdup(\"" v "\"), &queue);"-}
-# pheap::popqueue addr v
-$1 == "pheap::popqueue" {- v = $2
- c = int($3 * 1e3)
- if(g[v] != c)
- print "warning: cost g mismatch: " g[v] " vs " $0 >"/fd/2"
- if(n[v] == "")
- print "warning: empty name: " $0 >"/fd/2"
- print \
-"a = popqueue(&queue);" \
- #"\n\ti = strcmp((char*)a->aux, \"" v "\");\n" \
- #"\tassert(i == 0);\n" \
- #"\tassert(a->n == " c ");"
-}
-# pheap::decreasekey addr old diff\nold
-$1 == "pheap::decreasekey" {- v = $2
- c = int($3 * 1e3)
- d = g[v] - c
- if(g[v] == 0)
- print "warning: undefined node \"" v "\" is decreased!" >"/fd/2"
- g[v] = c
- print \
-"decreasekey(a" n[v] ", " d ", &queue);"
-}
-$1 == "remain" {- v = $2
- print \
-"a = popqueue(&queue);\n" \
- "\ti = strcmp((char*)a->aux, \"" v "\");\n" \
- "\tassert(i == 0);"
-}
-$1 == "occ" {- print \
-"// " $0
-}
-END {-# print \
-#"a = popqueue(&queue);\n" \
-#assert(a == nil);\n" \
-#"}"
-print \
-"printqueue(&queue);\n" \
-"nukequeue(&queue);\n" \
-"exits(nil);\n" \
-"}"
-}
--- /dev/null
+++ b/test/pheap.dec.c
@@ -1,0 +1,33 @@
+#include <u.h>
+#include <libc.h>
+#include "asif.h"
+debuglevel = Logtrace;
+enum{+ Nnodes = 10000,
+};
+
+void main(void) {+ Pairheap *queue, *a, **t, **p;
+ int fd, i;
+ double v;
+
+ t = emalloc(Nnodes * sizeof *t);
+ if((fd = create("res", OWRITE, 0644)) < 0)+ sysfatal("create: %r");+ queue = nil;
+ srand(time(nil));
+ for(p=t; p<t+Nnodes; p++){+ v = frand() * 1e6;
+ *p = pushqueue(v, nil, &queue);
+ if(frand() < 0.5){+ a = t[nrand(p-t)];
+ decreasekey(a, a->n-frand()*1e2, &queue);
+ }
+ }
+ for(p=t; p<t+Nnodes; p++)
+ fprint(fd, "%.2f\n", (*p)->n);
+ close(fd);
+ while((a = popqueue(&queue)) != nil)
+ print("%.2f\n", a->n);+ exits(nil);
+}
--- /dev/null
+++ b/test/pheap.nodec
@@ -1,0 +1,33 @@
+#!/bin/rc
+awk '
+BEGIN{+ srand()
+ nnodes = 1e4
+ if(ARGC > 1)
+ nnodes = int(ARGV[1])
+ if(nnodes < 10){+ print "usage: " ARGV[0] " [nnodes]" >"/fd/2"
+ exit "usage"
+ }
+ for(i=1; i<=nnodes; i++){+ a[i] = int(rand() * 1e8);
+ printf "%d\n", a[i] | "sort -n"
+ }
+ close("sort -n")+ print \
+ "#include <u.h>\n" \
+ "#include <libc.h>\n" \
+ "#include \"asif.h\"\n" \
+ "debuglevel = Logtrace;\n\n" \
+ "void main(void) {\n" \+ "Pairheap *queue, *a;\n" \
+ "int i;\n" \
+ "queue = nil;\n" >"test.c"
+ for(i=1; i<=nnodes; i++)
+ print "pushqueue("a[i]", \"\", &queue);" >>"test.c"+ print "while((a = popqueue(&queue)) != nil)\n" \
+ "print(\"%lld\\n\", (vlong)a->n);\n" \
+ "exits(nil);\n" \
+ "}" >>"test.c"
+}
+' $*
--- /dev/null
+++ b/test/pheap.run
@@ -1,0 +1,71 @@
+#!/bin/awk -f
+BEGIN{+ print \
+"#include <u.h>\n" \
+"#include <libc.h>\n" \
+"#include \"asif.h\"\n" \
+"debuglevel = Logtrace;\n\n" \
+"void main(void) {\n" \+"Pairheap *queue, *a;\n" \
+"int i;\n" \
+"queue = nil;\n"
+}
+# pheap::pushqueue addr v
+$1 == "pheap::pushqueue" {+ v = $2
+ c = int($3 * 1e3)
+ if(v in g)
+ print "warning: duplicate open node: " $0 >"/fd/2"
+ g[v] = c
+ if(!(v in n))
+ n[v] = ni++
+ print \
+"Pairheap *a" n[v] " = pushqueue(" g[v] ", estrdup(\"" v "\"), &queue);"+}
+# pheap::popqueue addr v
+$1 == "pheap::popqueue" {+ v = $2
+ c = int($3 * 1e3)
+ if(g[v] != c)
+ print "warning: cost g mismatch: " g[v] " vs " $0 >"/fd/2"
+ if(n[v] == "")
+ print "warning: empty name: " $0 >"/fd/2"
+ print \
+"a = popqueue(&queue);" \
+ #"\n\ti = strcmp((char*)a->aux, \"" v "\");\n" \
+ #"\tassert(i == 0);\n" \
+ #"\tassert(a->n == " c ");"
+}
+# pheap::decreasekey addr old diff\nold
+$1 == "pheap::decreasekey" {+ v = $2
+ c = int($3 * 1e3)
+ d = g[v] - c
+ if(g[v] == 0)
+ print "warning: undefined node \"" v "\" is decreased!" >"/fd/2"
+ g[v] = c
+ print \
+"decreasekey(a" n[v] ", " d ", &queue);"
+}
+$1 == "remain" {+ v = $2
+ print \
+"a = popqueue(&queue);\n" \
+ "\ti = strcmp((char*)a->aux, \"" v "\");\n" \
+ "\tassert(i == 0);"
+}
+$1 == "occ" {+ print \
+"// " $0
+}
+END {+# print \
+#"a = popqueue(&queue);\n" \
+#assert(a == nil);\n" \
+#"}"
+print \
+"printqueue(&queue);\n" \
+"nukequeue(&queue);\n" \
+"exits(nil);\n" \
+"}"
+}