Software / code / prosody
Changeset
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 |
| parents | 11073:5691b9773c5b |
| children | 11116:d334f2bebe55 11117:590ac42d81c5 |
| files | spec/util_indexedbheap_spec.lua util/indexedbheap.lua |
| diffstat | 2 files changed, 34 insertions(+), 1 deletions(-) [+] |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/spec/util_indexedbheap_spec.lua Tue Sep 29 21:27:16 2020 -0500 @@ -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);
--- a/util/indexedbheap.lua Mon Jun 15 14:16:34 2020 +0100 +++ b/util/indexedbheap.lua Tue Sep 29 21:27:16 2020 -0500 @@ -23,7 +23,7 @@ local tmp_sync = sync[k]; while k ~= 1 do local parent = math_floor(k/2); - if tmp < self[parent] then break; end + if tmp >= self[parent] then break; end self[k] = self[parent]; sync[k] = sync[parent]; index[sync[k]] = k;
