6 * Maximum amount of creatable lists.
7 * Lists can be given endless amount of entities, only restricted by engine limitations.
9 const int IL_MAX = 128;
12 void IL_INIT(entity this);
14 void IL_DTOR(entity this);
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
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 ATTRIB(IntrusiveList, il_loop_item, entity, nil);
31 INIT(IntrusiveList) { IL_INIT(this); }
32 DESTRUCTOR(IntrusiveList) { IL_DTOR(this); }
33 ENDCLASS(IntrusiveList)
40 #define IL_NEW() NEW(IntrusiveList)
42 #define IL_EMPTY(this) (this.il_head == NULL)
44 #define IL_FIRST(this) (this.il_head)
45 #define IL_LAST(this) (this.il_tail)
46 #define IL_PEEK(this) (this.il_tail)
49 bool IL_CONTAINS(IntrusiveList this, entity it)
51 assert(this, return false);
52 return it.(this.il_nextfld) || this.il_head == it || this.il_tail == it;
59 entity IL_PUSH(IntrusiveList this, entity it)
61 assert(this, return NULL);
62 assert(it, return NULL);
63 .entity il_next = this.il_nextfld;
64 .entity il_prev = this.il_prevfld;
65 assert(!IL_CONTAINS(this, it), return NULL);
67 entity tail = it.(il_prev) = this.il_tail;
68 tail ? (tail.(il_next) = it) : this.il_head = it;
70 it.il_lists |= this.il_listmask;
78 entity IL_UNSHIFT(IntrusiveList this, entity it)
80 assert(this, return NULL);
81 assert(it, return NULL);
82 .entity il_next = this.il_nextfld;
83 .entity il_prev = this.il_prevfld;
84 assert(!IL_CONTAINS(this, it), return NULL);
86 entity head = it.(il_next) = this.il_head;
87 head ? (head.(il_prev) = it) : this.il_tail = it;
89 it.il_lists |= this.il_listmask;
97 entity IL_POP(IntrusiveList this)
99 assert(this, return NULL);
100 .entity il_next = this.il_nextfld;
101 .entity il_prev = this.il_prevfld;
103 if (!this.il_tail) return NULL;
104 entity it = this.il_tail;
105 entity prev = it.(il_prev);
106 if (prev) (this.il_tail = prev).(il_next) = NULL;
107 else this.il_head = this.il_tail = NULL;
115 entity IL_SHIFT(IntrusiveList this)
117 assert(this, return NULL);
118 .entity il_next = this.il_nextfld;
119 .entity il_prev = this.il_prevfld;
121 if (!this.il_head) return NULL;
122 entity it = this.il_head;
123 entity next = it.(il_next);
124 if (next) (this.il_head = next).(il_prev) = NULL;
125 else this.il_head = this.il_tail = NULL;
130 * Remove any element, anywhere in the list
133 void IL_REMOVE(IntrusiveList this, entity it)
135 assert(this, return);
136 .entity il_next = this.il_nextfld;
137 .entity il_prev = this.il_prevfld;
138 //assert(!IL_CONTAINS(this, it), return);
139 entity next = it.(il_next);
140 entity prev = it.(il_prev);
141 entity ohead = this.il_head;
142 entity otail = this.il_tail;
143 next ? next.(il_prev) = prev : this.il_tail = prev;
144 prev ? prev.(il_next) = next : this.il_head = next;
145 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);
146 if (this.il_loop_item == it)
147 this.il_loop_item = it.(il_next);
148 it.(il_next) = it.(il_prev) = NULL;
152 * Remove all elements
154 #define IL_CLEAR(this) \
156 IntrusiveList _il = this; \
158 .entity il_prev = _il.il_prevfld; \
159 .entity il_next = _il.il_nextfld; \
161 for (entity _next, _it = _il.il_head; _it; (_it = _next, ++i)) \
163 _next = _it.(il_next); \
164 _it.(il_next) = _it.(il_prev) = NULL; \
166 _il.il_head = _il.il_tail = NULL; \
172 #define IL_DELETE(this) \
178 #define IL_EACH(this, cond, body) \
180 IntrusiveList _il = this; \
182 .entity il_next = _il.il_nextfld; \
184 for (entity _next, _it = _il.il_head; _it; (_it = _next, ++i)) \
186 const noref entity it = _it; \
187 this.il_loop_item = it; \
188 _next = it.(il_next); \
189 if (cond) { LAMBDA(body) } \
190 if (this.il_loop_item != it) /* current item removed? */ \
191 _next = this.il_loop_item; \
193 _next = it.(il_next); /* in case next item has changed */ \
195 this.il_loop_item = nil; \
199 IntrusiveList il_links[IL_MAX];
200 .entity il_links_flds[IL_MAX * 2];
203 #define IL_FLOOR(n) ((n) | 0)
204 #define IL_CEIL(n) IL_FLOOR((n) + 0.5)
206 #define IL_LISTS_PER_BIT IL_CEIL(IL_MAX / (3 * 24))
209 void IL_INIT(IntrusiveList this)
211 .entity nextfld, prevfld;
212 for (int i = il_links_ptr; i < il_links_ptr + IL_MAX; ++i) {
214 if (idx >= IL_MAX) idx -= IL_MAX;
217 if (!il_links[idx]) {
218 il_links[idx] = this;
219 nextfld = il_links_flds[idx + 0];
220 prevfld = il_links_flds[idx + 1];
222 int bit = IL_FLOOR(id / IL_LISTS_PER_BIT);
223 if (bit < (1 * 24)) this.il_listmask = '1 0 0' * (1 << (bit - (0 * 24)));
224 else if (bit < (2 * 24)) this.il_listmask = '0 1 0' * (1 << (bit - (1 * 24)));
225 else if (bit < (3 * 24)) this.il_listmask = '0 0 1' * (1 << (bit - (2 * 24)));
227 il_links_ptr = id + 1;
228 if (il_links_ptr >= IL_MAX) il_links_ptr -= IL_MAX;
229 this.il_nextfld = nextfld;
230 this.il_prevfld = prevfld;
234 LOG_WARN("IntrusiveList overflow");
238 void IL_DTOR(IntrusiveList this)
241 il_links[this.il_id] = NULL;
248 // incompatible with CSQC, remove() clears entities
249 for (int i = 0; i < IL_MAX; ++i) {
250 IntrusiveList list = il_links[i];
252 .entity nextfld = list.il_nextfld;
253 for (entity next, it = list.il_head; it; it = next) {
264 // called when an entity is deleted with delete() / remove()
265 // or when a player disconnects
266 void ONREMOVE(entity this)
268 // remove 'this' from any intrusive lists it is on
269 vector lists = this.il_lists;
271 for (int i = 0; i < IL_MAX; ++i) {
272 IntrusiveList list = il_links[i];
273 if ((lists & list.il_listmask) && IL_CONTAINS(list, this)) {
274 IL_REMOVE(list, this);