]> git.xonotic.org Git - xonotic/xonotic-data.pk3dir.git/blob - qcsrc/lib/intrusivelist.qh
Reloadable shotgun: when clip is empty automatically reload regardless of whether...
[xonotic/xonotic-data.pk3dir.git] / qcsrc / lib / intrusivelist.qh
1 #pragma once
2
3 #include "iter.qh"
4
5 /**
6  * Maximum amount of creatable lists.
7  * Lists can be given endless amount of entities, only restricted by engine limitations.
8  */
9 const int IL_MAX = 128;
10
11 ERASEABLE
12 void IL_INIT(entity this);
13 ERASEABLE
14 void IL_DTOR(entity this);
15 ERASEABLE
16 void IL_ENDFRAME();
17
18 /**
19  * limitations:
20  *   NULL cannot be present
21  *   elements can only be present once
22  *   a maximum of `IL_MAX` lists can exist at one time
23  *   freed entities must be removed from the list
24  */
25 CLASS(IntrusiveList, Object)
26         ATTRIB(IntrusiveList, il_head, entity);
27         ATTRIB(IntrusiveList, il_tail, entity);
28         ATTRIB(IntrusiveList, il_nextfld, .entity, nil);
29         ATTRIB(IntrusiveList, il_prevfld, .entity, nil);
30         INIT(IntrusiveList) { IL_INIT(this); }
31         DESTRUCTOR(IntrusiveList) { IL_DTOR(this); }
32 ENDCLASS(IntrusiveList)
33
34 // bitflags
35 .vector il_lists;
36 // bitflags
37 .vector il_listmask;
38
39 #define IL_NEW() NEW(IntrusiveList)
40
41 #define IL_EMPTY(this) (this.il_head == NULL)
42
43 #define IL_FIRST(this) (this.il_head)
44 #define IL_LAST(this) (this.il_tail)
45 #define IL_PEEK(this) (this.il_tail)
46
47 ERASEABLE
48 bool IL_CONTAINS(IntrusiveList this, entity it)
49 {
50         assert(this, return false);
51         return it.(this.il_nextfld) || this.il_head == it || this.il_tail == it;
52 }
53
54 /**
55  * Push to tail
56  */
57 ERASEABLE
58 entity IL_PUSH(IntrusiveList this, entity it)
59 {
60         assert(this, return NULL);
61         assert(it, return NULL);
62         .entity il_next = this.il_nextfld;
63         .entity il_prev = this.il_prevfld;
64         assert(!IL_CONTAINS(this, it), return NULL);
65
66         entity tail = it.(il_prev) = this.il_tail;
67         tail ? (tail.(il_next) = it) : this.il_head = it;
68         this.il_tail = it;
69         it.il_lists |= this.il_listmask;
70         return it;
71 }
72
73 /**
74  * Push to head
75  */
76 ERASEABLE
77 entity IL_UNSHIFT(IntrusiveList this, entity it)
78 {
79         assert(this, return NULL);
80         assert(it, return NULL);
81         .entity il_next = this.il_nextfld;
82         .entity il_prev = this.il_prevfld;
83         assert(!IL_CONTAINS(this, it), return NULL);
84
85         entity head = it.(il_next) = this.il_head;
86         head ? (head.(il_prev) = it) : this.il_tail = it;
87         this.il_head = it;
88         it.il_lists |= this.il_listmask;
89         return it;
90 }
91
92 /**
93  * Pop from tail
94  */
95 ERASEABLE
96 entity IL_POP(IntrusiveList this)
97 {
98         assert(this, return NULL);
99         .entity il_next = this.il_nextfld;
100         .entity il_prev = this.il_prevfld;
101
102         if (!this.il_tail) return NULL;
103         entity it = this.il_tail;
104         entity prev = it.(il_prev);
105         if (prev) (this.il_tail = prev).(il_next) = NULL;
106         else this.il_head = this.il_tail = NULL;
107         return it;
108 }
109
110 /**
111  * Pop from head
112  */
113 ERASEABLE
114 entity IL_SHIFT(IntrusiveList this)
115 {
116         assert(this, return NULL);
117         .entity il_next = this.il_nextfld;
118         .entity il_prev = this.il_prevfld;
119
120         if (!this.il_head) return NULL;
121         entity it = this.il_head;
122         entity next = it.(il_next);
123         if (next) (this.il_head = next).(il_prev) = NULL;
124         else this.il_head = this.il_tail = NULL;
125         return it;
126 }
127
128 /**
129  * Remove any element, anywhere in the list
130  */
131 ERASEABLE
132 void IL_REMOVE(IntrusiveList this, entity it)
133 {
134         assert(this, return);
135         .entity il_next = this.il_nextfld;
136         .entity il_prev = this.il_prevfld;
137         //assert(!IL_CONTAINS(this, it), return);
138         entity next = it.(il_next);
139         entity prev = it.(il_prev);
140         entity ohead = this.il_head;
141         entity otail = this.il_tail;
142         next ? next.(il_prev) = prev : this.il_tail = prev;
143         prev ? prev.(il_next) = next : this.il_head = next;
144         LOG_DEBUGF("remove %i (%i :: %i), head: %i -> %i, tail: %i -> %i", it, it.(il_prev), it.(il_next), ohead, this.il_head, otail, this.il_tail);
145         it.(il_next) = it.(il_prev) = NULL;
146 }
147
148 /**
149  * Remove all elements
150  */
151 #define IL_CLEAR(this) \
152         MACRO_BEGIN \
153                 IntrusiveList __il = this; \
154                 assert(__il); \
155                 .entity il_prev = __il.il_prevfld; \
156                 IL_EACH(__il, true, it.(il_next) = it.(il_prev) = NULL); \
157                 __il.il_head = __il.il_tail = NULL; \
158         MACRO_END
159
160 /**
161  * Delete the list
162  */
163 #define IL_DELETE(this) \
164         MACRO_BEGIN \
165                 delete(this); \
166                 this = NULL; \
167         MACRO_END
168
169 #define IL_EACH(this, cond, body) \
170         MACRO_BEGIN \
171                 IntrusiveList _il = this; \
172                 assert(_il); \
173                 .entity il_next = _il.il_nextfld; \
174                 noref int i = 0; \
175                 for (entity _next, _it = _il.il_head; _it; (_it = _next, ++i)) \
176                 { \
177                         const noref entity it = _it; \
178                         _next = it.(il_next); \
179                         if (cond) { LAMBDA(body) } \
180                 } \
181         MACRO_END
182
183 .int il_id;
184 IntrusiveList il_links[IL_MAX];
185 .entity il_links_flds[IL_MAX * 2];
186 int il_links_ptr;
187
188 #define IL_FLOOR(n) ((n) | 0)
189 #define IL_CEIL(n)  IL_FLOOR((n) + 0.5)
190
191 #define IL_LISTS_PER_BIT IL_CEIL(IL_MAX / (3 * 24))
192
193 ERASEABLE
194 void IL_INIT(IntrusiveList this)
195 {
196         .entity nextfld, prevfld;
197         for (int i = il_links_ptr; i < il_links_ptr + IL_MAX; ++i) {
198                 int idx = i;
199                 if (idx >= IL_MAX) idx -= IL_MAX;
200                 int id = idx;
201                 idx *= 2;
202                 if (!il_links[idx]) {
203                         il_links[idx] = this;
204                         nextfld = il_links_flds[idx + 0];
205                         prevfld = il_links_flds[idx + 1];
206                         this.il_id = id;
207                         int bit = IL_FLOOR(id / IL_LISTS_PER_BIT);
208                         if (bit < (1 * 24)) this.il_listmask = '1 0 0' * (1 << (bit - (0 * 24)));
209                         else if (bit < (2 * 24)) this.il_listmask = '0 1 0' * (1 << (bit - (1 * 24)));
210                         else if (bit < (3 * 24)) this.il_listmask = '0 0 1' * (1 << (bit - (2 * 24)));
211                         else assert(false);
212                         il_links_ptr = id + 1;
213                         if (il_links_ptr >= IL_MAX) il_links_ptr -= IL_MAX;
214                         this.il_nextfld = nextfld;
215                         this.il_prevfld = prevfld;
216                         return;
217                 }
218         }
219         LOG_WARN("IntrusiveList overflow");
220 }
221
222 ERASEABLE
223 void IL_DTOR(IntrusiveList this)
224 {
225         IL_CLEAR(this);
226         il_links[this.il_id] = NULL;
227 }
228
229 ERASEABLE
230 void IL_ENDFRAME()
231 {
232 #if 0
233         // incompatible with CSQC, remove() clears entities
234         for (int i = 0; i < IL_MAX; ++i) {
235                 IntrusiveList list = il_links[i];
236                 if (list) {
237                         .entity nextfld = list.il_nextfld;
238                         for (entity next, it = list.il_head; it; it = next) {
239                                 next = it.(nextfld);
240                                 if (wasfreed(it)) {
241                                         IL_REMOVE(list, it);
242                                 }
243                         }
244                 }
245         }
246 #endif
247 }
248
249 // called when an entity is deleted with delete() / remove()
250 // or when a player disconnects
251 void ONREMOVE(entity this)
252 {
253         // remove 'this' from any intrusive lists it is on
254         vector lists = this.il_lists;
255         if (lists) {
256                 for (int i = 0; i < IL_MAX; ++i) {
257                         IntrusiveList list = il_links[i];
258                         if ((lists & list.il_listmask) && IL_CONTAINS(list, this)) {
259                                 IL_REMOVE(list, this);
260                         }
261                 }
262         }
263 }