7 * Maximum amount of creatable lists.
8 * Lists can be given endless amount of entities, only restricted by engine limitations.
10 const int IL_MAX = 128;
13 void IL_INIT(entity this);
15 void IL_DTOR(entity this);
21 * NULL cannot be present
22 * elements can only be present once
23 * a maximum of `IL_MAX` lists can exist at one time
24 * freed entities must be removed from the list
26 CLASS(IntrusiveList, Object)
27 ATTRIB(IntrusiveList, il_head, entity);
28 ATTRIB(IntrusiveList, il_tail, entity);
29 ATTRIB(IntrusiveList, il_nextfld, .entity, nil);
30 ATTRIB(IntrusiveList, il_prevfld, .entity, nil);
31 ATTRIB(IntrusiveList, il_loop_item, entity, NULL);
32 INIT(IntrusiveList) { IL_INIT(this); }
33 DESTRUCTOR(IntrusiveList) { IL_DTOR(this); }
34 ENDCLASS(IntrusiveList)
41 #define IL_NEW() NEW(IntrusiveList)
43 #define IL_EMPTY(this) (this.il_head == NULL)
45 #define IL_FIRST(this) (this.il_head)
46 #define IL_LAST(this) (this.il_tail)
47 #define IL_PEEK(this) (this.il_tail)
50 bool IL_CONTAINS(IntrusiveList this, entity it)
52 assert(this, return false);
53 return it.(this.il_nextfld) || this.il_head == it || this.il_tail == it;
60 entity IL_PUSH(IntrusiveList this, entity it)
62 assert(this, return NULL);
63 assert(it, return NULL);
64 .entity il_next = this.il_nextfld;
65 .entity il_prev = this.il_prevfld;
66 assert(!IL_CONTAINS(this, it), return NULL);
68 entity tail = it.(il_prev) = this.il_tail;
69 tail ? (tail.(il_next) = it) : this.il_head = it;
71 it.il_lists |= this.il_listmask;
79 entity IL_UNSHIFT(IntrusiveList this, entity it)
81 assert(this, return NULL);
82 assert(it, return NULL);
83 .entity il_next = this.il_nextfld;
84 .entity il_prev = this.il_prevfld;
85 assert(!IL_CONTAINS(this, it), return NULL);
87 entity head = it.(il_next) = this.il_head;
88 head ? (head.(il_prev) = it) : this.il_tail = it;
90 it.il_lists |= this.il_listmask;
98 entity IL_POP(IntrusiveList this)
100 assert(this, return NULL);
101 .entity il_next = this.il_nextfld;
102 .entity il_prev = this.il_prevfld;
104 if (!this.il_tail) return NULL;
105 entity it = this.il_tail;
106 entity prev = it.(il_prev);
107 if (prev) (this.il_tail = prev).(il_next) = NULL;
108 else this.il_head = this.il_tail = NULL;
109 if (this.il_loop_item == it)
110 this.il_loop_item = NULL;
119 entity IL_SHIFT(IntrusiveList this)
121 assert(this, return NULL);
122 .entity il_next = this.il_nextfld;
123 .entity il_prev = this.il_prevfld;
125 if (!this.il_head) return NULL;
126 entity it = this.il_head;
127 entity next = it.(il_next);
128 if (next) (this.il_head = next).(il_prev) = NULL;
129 else this.il_head = this.il_tail = NULL;
130 if (this.il_loop_item == it)
131 this.il_loop_item = it.(il_next);
137 * Remove any element, anywhere in the list
140 void IL_REMOVE(IntrusiveList this, entity it)
142 assert(this, return);
143 .entity il_next = this.il_nextfld;
144 .entity il_prev = this.il_prevfld;
145 //assert(!IL_CONTAINS(this, it), return);
146 entity next = it.(il_next);
147 entity prev = it.(il_prev);
148 entity ohead = this.il_head;
149 entity otail = this.il_tail;
150 next ? next.(il_prev) = prev : this.il_tail = prev;
151 prev ? prev.(il_next) = next : this.il_head = next;
152 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);
153 if (this.il_loop_item == it)
154 this.il_loop_item = it.(il_next);
155 it.(il_next) = it.(il_prev) = NULL;
159 * Remove all elements
161 #define IL_CLEAR(this) \
163 IntrusiveList _il = this; \
165 .entity il_prev = _il.il_prevfld; \
166 .entity il_next = _il.il_nextfld; \
168 for (entity _next, _it = _il.il_head; _it; (_it = _next, ++i)) \
170 _next = _it.(il_next); \
171 _it.(il_next) = _it.(il_prev) = NULL; \
173 _il.il_head = _il.il_tail = NULL; \
179 #define IL_DELETE(this) \
185 #define IL_EACH(this, cond, body) \
187 IntrusiveList _il = this; \
189 .entity il_next = _il.il_nextfld; \
191 entity il_loop_item_save = this.il_loop_item; \
192 this.il_loop_item = NULL; \
193 for (entity _next, _it = _il.il_head; _it; (_it = _next, ++i)) \
195 const noref entity it = _it; \
196 this.il_loop_item = it; \
197 _next = it.(il_next); \
198 if (cond) { LAMBDA(body) } \
199 if (this.il_loop_item != it) /* current item removed? */ \
200 _next = this.il_loop_item; \
202 _next = it.(il_next); /* in case next item has changed */ \
204 this.il_loop_item = il_loop_item_save; \
208 IntrusiveList il_links[IL_MAX];
209 .entity il_links_flds[IL_MAX * 2];
212 #define IL_FLOOR(n) ((n) | 0)
213 #define IL_CEIL(n) IL_FLOOR((n) + 0.5)
215 #define IL_LISTS_PER_BIT IL_CEIL(IL_MAX / (3 * 24))
218 void IL_INIT(IntrusiveList this)
220 .entity nextfld, prevfld;
221 for (int i = il_links_ptr; i < il_links_ptr + IL_MAX; ++i) {
223 if (idx >= IL_MAX) idx -= IL_MAX;
226 if (!il_links[idx]) {
227 il_links[idx] = this;
228 nextfld = il_links_flds[idx + 0];
229 prevfld = il_links_flds[idx + 1];
231 int bit = IL_FLOOR(id / IL_LISTS_PER_BIT);
232 if (bit < (1 * 24)) this.il_listmask = '1 0 0' * (1 << (bit - (0 * 24)));
233 else if (bit < (2 * 24)) this.il_listmask = '0 1 0' * (1 << (bit - (1 * 24)));
234 else if (bit < (3 * 24)) this.il_listmask = '0 0 1' * (1 << (bit - (2 * 24)));
236 il_links_ptr = id + 1;
237 if (il_links_ptr >= IL_MAX) il_links_ptr -= IL_MAX;
238 this.il_nextfld = nextfld;
239 this.il_prevfld = prevfld;
243 LOG_WARN("IntrusiveList overflow");
247 void IL_DTOR(IntrusiveList this)
250 il_links[this.il_id] = NULL;
257 // incompatible with CSQC, remove() clears entities
258 for (int i = 0; i < IL_MAX; ++i) {
259 IntrusiveList list = il_links[i];
261 .entity nextfld = list.il_nextfld;
262 for (entity next, it = list.il_head; it; it = next) {
273 // clears any IL data from an entity (not an intrusive list)
274 // it should be used only in very particular cases such as after a copyentity call
275 void IL_REMOVE_RAW(entity it)
279 it.il_lists = '0 0 0';
280 for (int i = 0; i < IL_MAX * 2; ++i)
281 it.il_links_flds[i] = nil;
285 // called when an entity is deleted with delete() / remove()
286 // or when a player disconnects
287 void ONREMOVE(entity this)
289 // remove 'this' from any intrusive lists it is on
290 vector lists = this.il_lists;
292 for (int i = 0; i < IL_MAX; ++i) {
293 IntrusiveList list = il_links[i];
294 if ((lists & list.il_listmask) && IL_CONTAINS(list, this)) {
295 IL_REMOVE(list, this);
302 #define IL_TEST_BUILD() s = il_test_build(il_test, ent1, ent2, ent3, ent4, ent5)
304 string il_test_build(entity il_test, entity ent1, entity ent2, entity ent3, entity ent4, entity ent5)
307 IL_PUSH(il_test, ent1);
308 IL_PUSH(il_test, ent2);
309 IL_PUSH(il_test, ent3);
310 IL_PUSH(il_test, ent4);
311 IL_PUSH(il_test, ent5);
315 TEST(intrusivelist, ModificationsWhileLooping)
317 IntrusiveList il_test = IL_NEW();
318 entity ent1 = new(1), ent2 = new(2), ent3 = new(3), ent4 = new(4), ent5 = new(5);
322 IL_EACH(il_test, true,
324 s = strcat(s, it.classname);
325 if (it == ent2) IL_REMOVE(il_test, ent3);
326 if (it == ent4) IL_PUSH(il_test, ent3);
328 EXPECT_TRUE(s == "12453");
331 IL_EACH(il_test, true,
333 s = strcat(s, it.classname);
334 if (it == ent2) IL_REMOVE(il_test, ent2);
335 if (it == ent3) IL_REMOVE(il_test, ent3);
336 if (it == ent3) IL_REMOVE(il_test, ent4);
337 if (it == ent5) IL_POP(il_test);
339 EXPECT_TRUE(s == "1235");
342 IL_REMOVE(il_test, ent5);
343 IL_EACH(il_test, true,
345 s = strcat(s, it.classname);
346 if (it == ent1) IL_SHIFT(il_test);
347 if (it == ent4) IL_POP(il_test);
349 EXPECT_TRUE(s == "1234");
352 IL_EACH(il_test, true,
354 s = strcat(s, it.classname);
356 IL_EACH(il_test, true,
358 s = strcat(s, it.classname);
360 IL_EACH(il_test, true,
362 s = strcat(s, it.classname);
368 EXPECT_TRUE(s == "12123123454345");
371 delete(ent1); delete(ent2); delete(ent3); delete(ent4); delete(ent5);