aboutsummaryrefslogtreecommitdiffstats
path: root/spec/util_indexedbheap_spec.lua
diff options
context:
space:
mode:
authorWaqas Hussain <waqas20@gmail.com>2020-09-29 21:27:16 -0500
committerWaqas Hussain <waqas20@gmail.com>2020-09-29 21:27:16 -0500
commit80beeeb187e84bda89cfe7390704f6a53406cad6 (patch)
tree0b3b8e98aec4fad5c0c62c82f312e2f60e66fdc4 /spec/util_indexedbheap_spec.lua
parentc313b10cd98e8461bc1f17c6e7f47e90e0d3c379 (diff)
downloadprosody-80beeeb187e84bda89cfe7390704f6a53406cad6.tar.gz
prosody-80beeeb187e84bda89cfe7390704f6a53406cad6.zip
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Diffstat (limited to 'spec/util_indexedbheap_spec.lua')
-rw-r--r--spec/util_indexedbheap_spec.lua33
1 files changed, 33 insertions, 0 deletions
diff --git a/spec/util_indexedbheap_spec.lua b/spec/util_indexedbheap_spec.lua
new file mode 100644
index 00000000..b10ee385
--- /dev/null
+++ b/spec/util_indexedbheap_spec.lua
@@ -0,0 +1,33 @@
+local ibh = require"util.indexedbheap";
+
+local function verify_heap_property(priorities)
+ for k in ipairs(priorities) do
+ local parent = priorities[k];
+ local childA = priorities[2*k];
+ local childB = priorities[2*k+1];
+ -- print("-", parent, childA, childB)
+ assert(childA == nil or childA > parent, "heap property violated");
+ assert(childB == nil or childB > parent, "heap property violated");
+ end
+end
+
+local h
+setup(function ()
+ h = ibh.create();
+end)
+describe("util.indexedbheap", function ()
+ it("item can be moved from end to top", function ()
+ verify_heap_property(h);
+ h:insert("a", 1);
+ verify_heap_property(h);
+ h:insert("b", 2);
+ verify_heap_property(h);
+ h:insert("c", 3);
+ verify_heap_property(h);
+ local id = h:insert("*", 10);
+ verify_heap_property(h);
+ h:reprioritize(id, 0);
+ verify_heap_property(h);
+ assert.same({ 0, "*", id }, { h:pop() });
+ end)
+end);