Software /
code /
prosody
Annotate
util/indexedbheap.lua @ 12642:9061f9621330
Switch to a new role-based authorization framework, removing is_admin()
We began moving away from simple "is this user an admin?" permission checks
before 0.12, with the introduction of mod_authz_internal and the ability to
dynamically change the roles of individual users.
The approach in 0.12 still had various limitations however, and apart from
the introduction of roles other than "admin" and the ability to pull that info
from storage, not much actually changed.
This new framework shakes things up a lot, though aims to maintain the same
functionality and behaviour on the surface for a default Prosody
configuration. That is, if you don't take advantage of any of the new
features, you shouldn't notice any change.
The biggest change visible to developers is that usermanager.is_admin() (and
the auth provider is_admin() method) have been removed. Gone. Completely.
Permission checks should now be performed using a new module API method:
module:may(action_name, context)
This method accepts an action name, followed by either a JID (string) or
(preferably) a table containing 'origin'/'session' and 'stanza' fields (e.g.
the standard object passed to most events). It will return true if the action
should be permitted, or false/nil otherwise.
Modules should no longer perform permission checks based on the role name.
E.g. a lot of code previously checked if the user's role was prosody:admin
before permitting some action. Since many roles might now exist with similar
permissions, and the permissions of prosody:admin may be redefined
dynamically, it is no longer suitable to use this method for permission
checks. Use module:may().
If you start an action name with ':' (recommended) then the current module's
name will automatically be used as a prefix.
To define a new permission, use the new module API:
module:default_permission(role_name, action_name)
module:default_permissions(role_name, { action_name[, action_name...] })
This grants the specified role permission to execute the named action(s) by
default. This may be overridden via other mechanisms external to your module.
The built-in roles that developers should use are:
- prosody:user (normal user)
- prosody:admin (host admin)
- prosody:operator (global admin)
The new prosody:operator role is intended for server-wide actions (such as
shutting down Prosody).
Finally, all usage of is_admin() in modules has been fixed by this commit.
Some of these changes were trickier than others, but no change is expected to
break existing deployments.
EXCEPT: mod_auth_ldap no longer supports the ldap_admin_filter option. It's
very possible nobody is using this, but if someone is then we can later update
it to pull roles from LDAP somehow.
author | Matthew Wild <mwild1@gmail.com> |
---|---|
date | Wed, 15 Jun 2022 12:15:01 +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; |