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