prosody
7d4c292f178e
spec/util_indexedbheap_spec.lua

Find changesets by keywords by author, files, the commit message, revision number or hash, or revset expression.

Software / code / prosody

Comparison

spec/util_indexedbheap_spec.lua @ 11115:7d4c292f178e 0.11

util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
author Waqas Hussain <waqas20@gmail.com>
date Tue, 29 Sep 2020 21:27:16 -0500
child 11116:d334f2bebe55
comparison
equal deleted inserted replaced
11073:5691b9773c5b 11115:7d4c292f178e
1 local ibh = require"util.indexedbheap";
2
3 local function verify_heap_property(priorities)
4 for k in ipairs(priorities) do
5 local parent = priorities[k];
6 local childA = priorities[2*k];
7 local childB = priorities[2*k+1];
8 -- print("-", parent, childA, childB)
9 assert(childA == nil or childA > parent, "heap property violated");
10 assert(childB == nil or childB > parent, "heap property violated");
11 end
12 end
13
14 local h
15 setup(function ()
16 h = ibh.create();
17 end)
18 describe("util.indexedbheap", function ()
19 it("item can be moved from end to top", function ()
20 verify_heap_property(h);
21 h:insert("a", 1);
22 verify_heap_property(h);
23 h:insert("b", 2);
24 verify_heap_property(h);
25 h:insert("c", 3);
26 verify_heap_property(h);
27 local id = h:insert("*", 10);
28 verify_heap_property(h);
29 h:reprioritize(id, 0);
30 verify_heap_property(h);
31 assert.same({ 0, "*", id }, { h:pop() });
32 end)
33 end);