5 const int IL_MAX = 128;
7 void IL_INIT(entity this);
8 void IL_DTOR(entity this);
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
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)
32 #define IL_NEW() NEW(IntrusiveList)
34 #define IL_EMPTY(this) (this.il_head == NULL)
36 #define IL_FIRST(this) (this.il_head)
37 #define IL_LAST(this) (this.il_tail)
38 #define IL_PEEK(this) (this.il_tail)
40 bool IL_CONTAINS(IntrusiveList this, entity it)
42 assert(this, return false);
43 return it.(this.il_nextfld) || this.il_head == it || this.il_tail == it;
49 entity IL_PUSH(IntrusiveList this, entity it)
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);
57 entity tail = it.(il_prev) = this.il_tail;
58 tail ? (tail.(il_next) = it) : this.il_head = it;
60 it.il_lists |= this.il_listmask;
67 entity IL_UNSHIFT(IntrusiveList this, entity it)
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);
75 entity head = it.(il_next) = this.il_head;
76 head ? (head.(il_prev) = it) : this.il_tail = it;
78 it.il_lists |= this.il_listmask;
85 entity IL_POP(IntrusiveList this)
87 assert(this, return NULL);
88 .entity il_next = this.il_nextfld;
89 .entity il_prev = this.il_prevfld;
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;
102 entity IL_SHIFT(IntrusiveList this)
104 assert(this, return NULL);
105 .entity il_next = this.il_nextfld;
106 .entity il_prev = this.il_prevfld;
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;
117 * Remove any element, anywhere in the list
119 void IL_REMOVE(IntrusiveList this, entity it)
121 assert(this, return);
122 .entity il_next = this.il_nextfld;
123 .entity il_prev = this.il_prevfld;
124 entity next = it.(il_next);
125 entity prev = it.(il_prev);
126 entity ohead = this.il_head;
127 entity otail = this.il_tail;
128 next ? next.(il_prev) = prev : this.il_tail = prev;
129 prev ? prev.(il_next) = next : this.il_head = next;
130 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);
131 it.(il_next) = it.(il_prev) = NULL;
135 * Remove all elements
137 #define IL_CLEAR(this) \
140 IntrusiveList __il = this; \
142 .entity il_prev = __il.il_prevfld; \
143 IL_EACH(__il, true, it.(il_next) = it.(il_prev) = NULL); \
144 __il.il_head = __il.il_tail = NULL; \
150 #define IL_DELETE(this) \
157 #define IL_EACH(this, cond, body) \
160 IntrusiveList _il = this; \
162 .entity il_next = _il.il_nextfld; \
164 for (entity _next, _it = _il.il_head; _it; (_it = _next, ++i)) \
166 const noref entity it = _it; \
167 _next = it.(il_next); \
168 if (cond) { LAMBDA(body) } \
173 IntrusiveList il_links[IL_MAX];
174 .entity il_links_flds[IL_MAX * 2];
177 #define IL_FLOOR(n) ((n) | 0)
178 #define IL_CEIL(n) IL_FLOOR((n) + 0.5)
180 #define IL_LISTS_PER_BIT IL_CEIL(IL_MAX / (3 * 24))
182 void IL_INIT(IntrusiveList this)
184 .entity nextfld, prevfld;
185 for (int i = il_links_ptr; i < il_links_ptr + IL_MAX; ++i) {
187 if (idx >= IL_MAX) idx -= IL_MAX;
190 if (!il_links[idx]) {
191 il_links[idx] = this;
192 nextfld = il_links_flds[idx + 0];
193 prevfld = il_links_flds[idx + 1];
195 int bit = IL_FLOOR(id / IL_LISTS_PER_BIT);
196 if (bit < (1 * 24)) this.il_listmask = '1 0 0' * (1 << (bit - (0 * 24)));
197 else if (bit < (2 * 24)) this.il_listmask = '0 1 0' * (1 << (bit - (1 * 24)));
198 else if (bit < (3 * 24)) this.il_listmask = '0 0 1' * (1 << (bit - (2 * 24)));
200 il_links_ptr = id + 1;
201 if (il_links_ptr >= IL_MAX) il_links_ptr -= IL_MAX;
202 this.il_nextfld = nextfld;
203 this.il_prevfld = prevfld;
207 LOG_WARNF("IntrusiveList overflow");
210 void IL_DTOR(IntrusiveList this)
213 il_links[this.il_id] = NULL;
219 // incompatible with CSQC, remove() clears entities
220 for (int i = 0; i < IL_MAX; ++i) {
221 IntrusiveList list = il_links[i];
223 .entity nextfld = list.il_nextfld;
224 for (entity next, it = list.il_head; it; it = next) {
235 void ONREMOVE(entity this)
238 for (int i = 0; i < IL_MAX; ++i) {
239 IntrusiveList list = il_links[i];
240 if (this.il_lists & list.il_listmask && IL_CONTAINS(list, this)) {
241 IL_REMOVE(list, this);