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