prosody
a34a14054532
util/indexedbheap.lua

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

Software / code / prosody

Comparison

util/indexedbheap.lua @ 6151:a34a14054532

util.indexedbheap: Fix a possible traceback when removing the last item.
author Waqas Hussain <waqas20@gmail.com>
date Wed, 23 Apr 2014 11:38:34 -0400
parent 5876:f62ad84811df
child 8382:e5d00bf4a4d5
comparison
equal deleted inserted replaced
6150:5b59798c979a 6151:a34a14054532
111 111
112 k = _percolate_up(self.priorities, k, self.ids, self.index); 112 k = _percolate_up(self.priorities, k, self.ids, self.index);
113 k = _percolate_down(self.priorities, k, self.ids, self.index); 113 k = _percolate_down(self.priorities, k, self.ids, self.index);
114 end 114 end
115 function indexed_heap:remove_index(k) 115 function indexed_heap:remove_index(k)
116 local size = #self.priorities; 116 local result = self.priorities[k];
117 if result == nil then return; end
117 118
118 local result = self.priorities[k];
119 local result_sync = self.ids[k]; 119 local result_sync = self.ids[k];
120 local item = self.items[result_sync]; 120 local item = self.items[result_sync];
121 if result == nil then return; end 121 local size = #self.priorities;
122 self.index[result_sync] = nil;
123 self.items[result_sync] = nil;
124 122
125 self.priorities[k] = self.priorities[size]; 123 self.priorities[k] = self.priorities[size];
126 self.ids[k] = self.ids[size]; 124 self.ids[k] = self.ids[size];
127 self.index[self.ids[k]] = k; 125 self.index[self.ids[k]] = k;
126
128 t_remove(self.priorities); 127 t_remove(self.priorities);
129 t_remove(self.ids); 128 t_remove(self.ids);
130 129
131 k = _percolate_up(self.priorities, k, self.ids, self.index); 130 self.index[result_sync] = nil;
132 k = _percolate_down(self.priorities, k, self.ids, self.index); 131 self.items[result_sync] = nil;
132
133 if size > k then
134 k = _percolate_up(self.priorities, k, self.ids, self.index);
135 k = _percolate_down(self.priorities, k, self.ids, self.index);
136 end
133 137
134 return result, item, result_sync; 138 return result, item, result_sync;
135 end 139 end
136 function indexed_heap:remove(id) 140 function indexed_heap:remove(id)
137 return self:remove_index(self.index[id]); 141 return self:remove_index(self.index[id]);