Software / code / prosody
Annotate
util/indexedbheap.lua @ 13801:a5d5fefb8b68 13.0
mod_tls: Enable Prosody's certificate checking for incoming s2s connections (fixes #1916) (thanks Damian, Zash)
Various options in Prosody allow control over the behaviour of the certificate
verification process For example, some deployments choose to allow falling
back to traditional "dialback" authentication (XEP-0220), while others verify
via DANE, hard-coded fingerprints, or other custom plugins.
Implementing this flexibility requires us to override OpenSSL's default
certificate verification, to allow Prosody to verify the certificate itself,
apply custom policies and make decisions based on the outcome.
To enable our custom logic, we have to suppress OpenSSL's default behaviour of
aborting the connection with a TLS alert message. With LuaSec, this can be
achieved by using the verifyext "lsec_continue" flag.
We also need to use the lsec_ignore_purpose flag, because XMPP s2s uses server
certificates as "client" certificates (for mutual TLS verification in outgoing
s2s connections).
Commit 99d2100d2918 moved these settings out of the defaults and into mod_s2s,
because we only really need these changes for s2s, and they should be opt-in,
rather than automatically applied to all TLS services we offer.
That commit was incomplete, because it only added the flags for incoming
direct TLS connections. StartTLS connections are handled by mod_tls, which was
not applying the lsec_* flags. It previously worked because they were already
in the defaults.
This resulted in incoming s2s connections with "invalid" certificates being
aborted early by OpenSSL, even if settings such as `s2s_secure_auth = false`
or DANE were present in the config.
Outgoing s2s connections inherit verify "none" from the defaults, which means
OpenSSL will receive the cert but will not terminate the connection when it is
deemed invalid. This means we don't need lsec_continue there, and we also
don't need lsec_ignore_purpose (because the remote peer is a "server").
Wondering why we can't just use verify "none" for incoming s2s? It's because
in that mode, OpenSSL won't request a certificate from the peer for incoming
connections. Setting verify "peer" is how you ask OpenSSL to request a
certificate from the client, but also what triggers its built-in verification.
| author | Matthew Wild <mwild1@gmail.com> |
|---|---|
| date | Tue, 01 Apr 2025 17:26:56 +0100 |
| parent | 11115:7d4c292f178e |
| 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; |