prosody
3fd24e1945b0
util/indexedbheap.lua

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

Software / code / prosody

Annotate

util/indexedbheap.lua @ 13135:3fd24e1945b0

mod_storage_internal: Lazy-load archive items while iterating Very large list files previously ran into limits of the Lua parser, or just caused Prosody to freeze while parsing. Using the new index we can parse individual items one at a time. This probably won't reduce overall CPU usage, probably the opposite, but it will reduce the number of items in memory at once and allow collection of items after we iterated past them.
author Kim Alvefur <zash@zash.se>
date Wed, 12 May 2021 01:25:44 +0200
parent 11115:7d4c292f178e
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
5876
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
1
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
2 local setmetatable = setmetatable;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
3 local math_floor = math.floor;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
4 local t_remove = table.remove;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
5
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
6 local function _heap_insert(self, item, sync, item2, index)
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
7 local pos = #self + 1;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
8 while true do
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
9 local half_pos = math_floor(pos / 2);
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
10 if half_pos == 0 or item > self[half_pos] then break; end
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
11 self[pos] = self[half_pos];
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
12 sync[pos] = sync[half_pos];
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
13 index[sync[pos]] = pos;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
14 pos = half_pos;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
15 end
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
16 self[pos] = item;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
17 sync[pos] = item2;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
18 index[item2] = pos;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
19 end
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
20
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
21 local function _percolate_up(self, k, sync, index)
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
22 local tmp = self[k];
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
23 local tmp_sync = sync[k];
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
24 while k ~= 1 do
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
25 local parent = math_floor(k/2);
11115
7d4c292f178e util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents: 8382
diff changeset
26 if tmp >= self[parent] then break; end
5876
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
27 self[k] = self[parent];
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
28 sync[k] = sync[parent];
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
29 index[sync[k]] = k;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
30 k = parent;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
31 end
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
32 self[k] = tmp;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
33 sync[k] = tmp_sync;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
34 index[tmp_sync] = k;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
35 return k;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
36 end
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
37
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
38 local function _percolate_down(self, k, sync, index)
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
39 local tmp = self[k];
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
40 local tmp_sync = sync[k];
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
41 local size = #self;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
42 local child = 2*k;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
43 while 2*k <= size do
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
44 if child ~= size and self[child] > self[child + 1] then
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
45 child = child + 1;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
46 end
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
47 if tmp > self[child] then
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
48 self[k] = self[child];
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
49 sync[k] = sync[child];
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
50 index[sync[k]] = k;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
51 else
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
52 break;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
53 end
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
54
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
55 k = child;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
56 child = 2*k;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
57 end
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
58 self[k] = tmp;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
59 sync[k] = tmp_sync;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
60 index[tmp_sync] = k;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
61 return k;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
62 end
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
63
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
64 local function _heap_pop(self, sync, index)
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
65 local size = #self;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
66 if size == 0 then return nil; end
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
67
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
68 local result = self[1];
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
69 local result_sync = sync[1];
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
70 index[result_sync] = nil;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
71 if size == 1 then
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
72 self[1] = nil;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
73 sync[1] = nil;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
74 return result, result_sync;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
75 end
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
76 self[1] = t_remove(self);
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
77 sync[1] = t_remove(sync);
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
78 index[sync[1]] = 1;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
79
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
80 _percolate_down(self, 1, sync, index);
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
81
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
82 return result, result_sync;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
83 end
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
84
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
85 local indexed_heap = {};
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
86
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
87 function indexed_heap:insert(item, priority, id)
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
88 if id == nil then
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
89 id = self.current_id;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
90 self.current_id = id + 1;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
91 end
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
92 self.items[id] = item;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
93 _heap_insert(self.priorities, priority, self.ids, id, self.index);
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
94 return id;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
95 end
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
96 function indexed_heap:pop()
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
97 local priority, id = _heap_pop(self.priorities, self.ids, self.index);
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
98 if id then
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
99 local item = self.items[id];
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
100 self.items[id] = nil;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
101 return priority, item, id;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
102 end
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
103 end
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
104 function indexed_heap:peek()
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
105 return self.priorities[1];
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
106 end
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
107 function indexed_heap:reprioritize(id, priority)
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
108 local k = self.index[id];
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
109 if k == nil then return; end
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
110 self.priorities[k] = priority;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
111
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
112 k = _percolate_up(self.priorities, k, self.ids, self.index);
8382
e5d00bf4a4d5 util: Various minor changes to please [luacheck]
Kim Alvefur <zash@zash.se>
parents: 6151
diff changeset
113 _percolate_down(self.priorities, k, self.ids, self.index);
5876
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
114 end
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
115 function indexed_heap:remove_index(k)
6151
a34a14054532 util.indexedbheap: Fix a possible traceback when removing the last item.
Waqas Hussain <waqas20@gmail.com>
parents: 5876
diff changeset
116 local result = self.priorities[k];
a34a14054532 util.indexedbheap: Fix a possible traceback when removing the last item.
Waqas Hussain <waqas20@gmail.com>
parents: 5876
diff changeset
117 if result == nil then return; end
5876
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
118
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
119 local result_sync = self.ids[k];
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
120 local item = self.items[result_sync];
6151
a34a14054532 util.indexedbheap: Fix a possible traceback when removing the last item.
Waqas Hussain <waqas20@gmail.com>
parents: 5876
diff changeset
121 local size = #self.priorities;
5876
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
122
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
123 self.priorities[k] = self.priorities[size];
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
124 self.ids[k] = self.ids[size];
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
125 self.index[self.ids[k]] = k;
6151
a34a14054532 util.indexedbheap: Fix a possible traceback when removing the last item.
Waqas Hussain <waqas20@gmail.com>
parents: 5876
diff changeset
126
5876
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
127 t_remove(self.priorities);
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
128 t_remove(self.ids);
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
129
6151
a34a14054532 util.indexedbheap: Fix a possible traceback when removing the last item.
Waqas Hussain <waqas20@gmail.com>
parents: 5876
diff changeset
130 self.index[result_sync] = nil;
a34a14054532 util.indexedbheap: Fix a possible traceback when removing the last item.
Waqas Hussain <waqas20@gmail.com>
parents: 5876
diff changeset
131 self.items[result_sync] = nil;
a34a14054532 util.indexedbheap: Fix a possible traceback when removing the last item.
Waqas Hussain <waqas20@gmail.com>
parents: 5876
diff changeset
132
a34a14054532 util.indexedbheap: Fix a possible traceback when removing the last item.
Waqas Hussain <waqas20@gmail.com>
parents: 5876
diff changeset
133 if size > k then
a34a14054532 util.indexedbheap: Fix a possible traceback when removing the last item.
Waqas Hussain <waqas20@gmail.com>
parents: 5876
diff changeset
134 k = _percolate_up(self.priorities, k, self.ids, self.index);
8382
e5d00bf4a4d5 util: Various minor changes to please [luacheck]
Kim Alvefur <zash@zash.se>
parents: 6151
diff changeset
135 _percolate_down(self.priorities, k, self.ids, self.index);
6151
a34a14054532 util.indexedbheap: Fix a possible traceback when removing the last item.
Waqas Hussain <waqas20@gmail.com>
parents: 5876
diff changeset
136 end
5876
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
137
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
138 return result, item, result_sync;
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
139 end
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
140 function indexed_heap:remove(id)
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
141 return self:remove_index(self.index[id]);
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
142 end
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
143
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
144 local mt = { __index = indexed_heap };
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
145
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
146 local _M = {
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
147 create = function()
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
148 return setmetatable({
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
149 ids = {}; -- heap of ids, sync'd with priorities
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
150 items = {}; -- map id->items
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
151 priorities = {}; -- heap of priorities
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
152 index = {}; -- map of id->index of id in ids
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
153 current_id = 1.5
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
154 }, mt);
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
155 end
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
156 };
f62ad84811df util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff changeset
157 return _M;