Line data Source code
1 : /**
2 : Copyright (c) 2021 Roman Katuntsev <sbkarr@stappler.org>
3 : Copyright (c) 2023 Stappler LLC <admin@stappler.dev>
4 :
5 : Permission is hereby granted, free of charge, to any person obtaining a copy
6 : of this software and associated documentation files (the "Software"), to deal
7 : in the Software without restriction, including without limitation the rights
8 : to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9 : copies of the Software, and to permit persons to whom the Software is
10 : furnished to do so, subject to the following conditions:
11 :
12 : The above copyright notice and this permission notice shall be included in
13 : all copies or substantial portions of the Software.
14 :
15 : THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 : IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 : FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18 : AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 : LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20 : OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
21 : THE SOFTWARE.
22 : **/
23 :
24 : #ifndef STAPPLER_CORE_UTILS_SPPRIORITYLIST_H_
25 : #define STAPPLER_CORE_UTILS_SPPRIORITYLIST_H_
26 :
27 : #include "SPHashTable.h"
28 : #include <bit>
29 :
30 : namespace STAPPLER_VERSIONIZED stappler {
31 :
32 : template <typename Value>
33 : struct PriorityListEntry : memory::AllocPool {
34 : PriorityListEntry *prev;
35 : PriorityListEntry *next;
36 : void *target;
37 : int32_t priority;
38 : Value value;
39 : };
40 :
41 : template <typename Value>
42 : struct HashTraits<PriorityListEntry<Value> *> {
43 : using Entry = PriorityListEntry<Value>;
44 : static constexpr auto ValueSize = sizeof(PriorityListEntry<Value>);
45 : static constexpr auto ValueOffset = std::countr_zero(ValueSize);
46 :
47 2760 : static uint32_t hash(uint32_t salt, const Entry *value) {
48 2760 : return uint32_t(reinterpret_cast<uintptr_t>(value->target) >> ValueOffset);
49 : }
50 :
51 71894 : static uint32_t hash(uint32_t salt, const void * value) {
52 71894 : return uint32_t(reinterpret_cast<uintptr_t>(value) >> ValueOffset);
53 : }
54 :
55 25 : static bool equal(const Entry *l, const Entry *r) {
56 25 : return l->target == r->target;
57 : }
58 :
59 69159 : static bool equal(const Entry *l, const void * value) {
60 69159 : return l->target == value;
61 : }
62 : };
63 :
64 : template <typename Value>
65 : class PriorityList {
66 : public:
67 : using Pool = memory::pool_t;
68 : using Entry = PriorityListEntry<Value>;
69 :
70 46 : PriorityList(Pool *p = nullptr)
71 46 : : _pool(p ? p : memory::pool::acquire()), _hash(p ? p : memory::pool::acquire()) { }
72 :
73 46 : ~PriorityList() {
74 46 : clear();
75 46 : }
76 :
77 : template <typename ... Args>
78 : Value * emplace(void *, int32_t p, Args && ... args);
79 :
80 : Value * find(void *) const;
81 :
82 : // callback returns true if Entry should be removed
83 : void foreach(const Callback<bool(void *target, int32_t priority, Value &)> &);
84 :
85 : bool erase(const void *);
86 :
87 : void clear();
88 :
89 : bool empty() const;
90 :
91 : protected:
92 : template <typename ... Args>
93 : Value * emplace_list(bool ordered, Entry **, void *, int32_t p, Args && ... args);
94 :
95 : template <typename ... Args>
96 : Entry *allocate(void *, int32_t p, Args && ... args);
97 :
98 : void erase_entry(Entry *);
99 : void free(Entry *);
100 :
101 : void foreach_list(Entry *, const Callback<bool(void *target, int32_t priority, Value &)> &);
102 :
103 : Pool *_pool = nullptr;
104 : size_t _size = 0;
105 : Entry *_negList = nullptr;
106 : Entry *_zeroList = nullptr;
107 : Entry *_posList = nullptr;
108 : HashTable<Entry *> _hash;
109 :
110 : Entry *_free = nullptr; /* List of recycled entries */
111 : };
112 :
113 : template <typename Value>
114 : template <typename ... Args>
115 67701 : auto PriorityList<Value>::emplace(void *ptr, int32_t p, Args && ... args) -> Value * {
116 67701 : auto it = _hash.find(ptr);
117 67701 : if (it != _hash.end()) {
118 64966 : auto entry = (Entry *)*it;
119 64966 : if (entry->priority != p) {
120 0 : _hash.erase(it);
121 : } else {
122 64966 : return &entry->value;
123 : }
124 : }
125 :
126 2735 : if (p == 0) {
127 2585 : return emplace_list(false, &_zeroList, ptr, p, std::forward<Args>(args)...);
128 150 : } else if (p < 0) {
129 75 : return emplace_list(true, &_negList, ptr, p, std::forward<Args>(args)...);
130 75 : } else if (p > 0) {
131 75 : return emplace_list(true, &_posList, ptr, p, std::forward<Args>(args)...);
132 : }
133 :
134 0 : return nullptr;
135 : }
136 :
137 : template <typename Value>
138 1734 : auto PriorityList<Value>::find(void *ptr) const -> Value * {
139 1734 : auto it = _hash.find(ptr);
140 1734 : if (it != _hash.end()) {
141 1734 : auto entry = (Entry *)*it;
142 1734 : return &entry->value;
143 : }
144 0 : return nullptr;
145 : }
146 :
147 : template <typename Value>
148 9563 : void PriorityList<Value>::foreach(const Callback<bool(void *target, int32_t priority, Value &)> &cb) {
149 9563 : foreach_list(_negList, cb);
150 9563 : foreach_list(_zeroList, cb);
151 9563 : foreach_list(_posList, cb);
152 9563 : }
153 :
154 : template <typename Value>
155 2459 : bool PriorityList<Value>::erase(const void *ptr) {
156 2459 : auto it = _hash.find(ptr);
157 2459 : if (it != _hash.end()) {
158 2459 : auto v = *it;
159 2459 : erase_entry(v);
160 2459 : _hash.erase(it);
161 2459 : return true;
162 : }
163 0 : return false;
164 : }
165 :
166 : template <typename Value>
167 113 : void PriorityList<Value>::clear() {
168 289 : while (_zeroList) {
169 176 : auto v = _zeroList;
170 176 : _zeroList = _zeroList->next;
171 176 : free(v);
172 : }
173 163 : while (_negList) {
174 50 : auto v = _negList;
175 50 : _negList = _negList->next;
176 50 : free(v);
177 : }
178 138 : while (_posList) {
179 25 : auto v = _posList;
180 25 : _posList = _posList->next;
181 25 : free(v);
182 : }
183 113 : _hash.clear();
184 113 : }
185 :
186 : template <typename Value>
187 46 : bool PriorityList<Value>::empty() const {
188 46 : return _hash.empty();
189 : }
190 :
191 : template <typename Value>
192 : template <typename ... Args>
193 2735 : auto PriorityList<Value>::emplace_list(bool ordered, Entry **target, void *ptr, int32_t p, Args && ... args) -> Value * {
194 2735 : Entry *newVal = allocate(ptr, p, std::forward<Args>(args)...);
195 :
196 2735 : if (ordered && *target && (*target)->priority < p) {
197 75 : auto v = *target;
198 75 : while (v->next && v->next->priority < p) {
199 0 : target = &v->next;
200 0 : v = v->next;
201 : }
202 :
203 : // insert between v and v->next
204 75 : newVal->prev = v;
205 75 : newVal->next = v->next;
206 75 : if (newVal->next) {
207 50 : newVal->next->prev = newVal;
208 : }
209 75 : v->next = newVal;
210 75 : } else {
211 : // insert first
212 2660 : newVal->prev = nullptr;
213 2660 : newVal->next = *target;
214 2660 : if (newVal->next) {
215 2564 : newVal->next->prev = newVal;
216 : }
217 2660 : *target = newVal;
218 : }
219 :
220 2735 : _hash.emplace(newVal);
221 :
222 2735 : return &newVal->value;
223 : }
224 :
225 : template <typename Value>
226 : template <typename ... Args>
227 2735 : auto PriorityList<Value>::allocate(void *ptr, int32_t p, Args && ... args) -> Entry * {
228 2735 : Entry *ret = nullptr;
229 2735 : if (_free) {
230 1386 : ret = _free;
231 1386 : _free = ret->next;
232 1386 : ret->next = nullptr;
233 : } else {
234 1349 : ret = new (_pool) Entry;
235 : }
236 :
237 2735 : ret->target = ptr;
238 2735 : ret->priority = p;
239 2735 : new (&ret->value) Value(std::forward<Args>(args)...);
240 :
241 2735 : return ret;
242 : }
243 :
244 : template <typename Value>
245 2484 : void PriorityList<Value>::erase_entry(Entry *v) {
246 2484 : if (v == _zeroList) {
247 924 : _zeroList = v->next;
248 924 : if (_zeroList) {
249 924 : _zeroList->prev = nullptr;
250 : }
251 924 : free(v);
252 1560 : } else if (v == _negList) {
253 25 : _negList = v->next;
254 25 : if (_negList) {
255 25 : _negList->prev = nullptr;
256 : }
257 25 : free(v);
258 1535 : } else if (v == _posList) {
259 25 : _posList = v->next;
260 25 : if (_posList) {
261 25 : _posList->prev = nullptr;
262 : }
263 25 : free(v);
264 : } else {
265 1510 : if (v->prev) {
266 1510 : v->prev->next = v->next;
267 : }
268 1510 : if (v->next) {
269 1443 : v->next->prev = v->prev;
270 : }
271 1510 : free(v);
272 : }
273 2484 : }
274 :
275 : template <typename Value>
276 2735 : void PriorityList<Value>::free(Entry *v) {
277 2735 : v->value.~Value();
278 2735 : v->next = _free;
279 2735 : v->prev = nullptr;
280 2735 : if (_free) {
281 2542 : _free->prev = v;
282 : }
283 2735 : _free = v;
284 2735 : }
285 :
286 : template <typename Value>
287 28689 : void PriorityList<Value>::foreach_list(Entry *v, const Callback<bool(void *target, int32_t priority, Value &)> &cb) {
288 335117 : while (v) {
289 306428 : if (cb(v->target, v->priority, v->value)) {
290 25 : auto next = v->next;
291 25 : _hash.erase(v);
292 25 : erase_entry(v);
293 25 : v = next;
294 : } else {
295 306403 : v = v->next;
296 : }
297 : }
298 28689 : }
299 :
300 : }
301 :
302 : #endif /* STAPPLER_CORE_UTILS_SPPRIORITYLIST_H_ */
|
