5 const int IL_MAX = 128;
8 void IL_INIT(entity this);
10 void IL_DTOR(entity this);
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
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)
35 #define IL_NEW() NEW(IntrusiveList)
37 #define IL_EMPTY(this) (this.il_head == NULL)
39 #define IL_FIRST(this) (this.il_head)
40 #define IL_LAST(this) (this.il_tail)
41 #define IL_PEEK(this) (this.il_tail)
44 bool IL_CONTAINS(IntrusiveList this, entity it)
46 assert(this, return false);
47 return it.(this.il_nextfld) || this.il_head == it || this.il_tail == it;
54 entity IL_PUSH(IntrusiveList this, entity it)
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);
62 entity tail = it.(il_prev) = this.il_tail;
63 tail ? (tail.(il_next) = it) : this.il_head = it;
65 it.il_lists |= this.il_listmask;
73 entity IL_UNSHIFT(IntrusiveList this, entity it)
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);
81 entity head = it.(il_next) = this.il_head;
82 head ? (head.(il_prev) = it) : this.il_tail = it;
84 it.il_lists |= this.il_listmask;
92 entity IL_POP(IntrusiveList this)
94 assert(this, return NULL);
95 .entity il_next = this.il_nextfld;
96 .entity il_prev = this.il_prevfld;
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;
110 entity IL_SHIFT(IntrusiveList this)
112 assert(this, return NULL);
113 .entity il_next = this.il_nextfld;
114 .entity il_prev = this.il_prevfld;
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;
125 * Remove any element, anywhere in the list
128 void IL_REMOVE(IntrusiveList this, entity it)
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;
145 * Remove all elements
147 #define IL_CLEAR(this) \
149 IntrusiveList __il = this; \
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; \
159 #define IL_DELETE(this) \
165 #define IL_EACH(this, cond, body) \
167 IntrusiveList _il = this; \
169 .entity il_next = _il.il_nextfld; \
171 for (entity _next, _it = _il.il_head; _it; (_it = _next, ++i)) \
173 const noref entity it = _it; \
174 _next = it.(il_next); \
175 if (cond) { LAMBDA(body) } \
180 IntrusiveList il_links[IL_MAX];
181 .entity il_links_flds[IL_MAX * 2];
184 #define IL_FLOOR(n) ((n) | 0)
185 #define IL_CEIL(n) IL_FLOOR((n) + 0.5)
187 #define IL_LISTS_PER_BIT IL_CEIL(IL_MAX / (3 * 24))
190 void IL_INIT(IntrusiveList this)
192 .entity nextfld, prevfld;
193 for (int i = il_links_ptr; i < il_links_ptr + IL_MAX; ++i) {
195 if (idx >= IL_MAX) idx -= IL_MAX;
198 if (!il_links[idx]) {
199 il_links[idx] = this;
200 nextfld = il_links_flds[idx + 0];
201 prevfld = il_links_flds[idx + 1];
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)));
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;
215 LOG_WARN("IntrusiveList overflow");
219 void IL_DTOR(IntrusiveList this)
222 il_links[this.il_id] = NULL;
229 // incompatible with CSQC, remove() clears entities
230 for (int i = 0; i < IL_MAX; ++i) {
231 IntrusiveList list = il_links[i];
233 .entity nextfld = list.il_nextfld;
234 for (entity next, it = list.il_head; it; it = next) {
246 void ONREMOVE(entity this)
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);