qcsrc/lib/intrusivelist.qh

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