qcsrc/lib/intrusivelist.qh

   1 #pragma once
   2
   3 #include "iter.qh"
   4
   5 /**
   6  * 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         ATTRIB(IntrusiveList, il_loop_item, entity, nil);
  31         INIT(IntrusiveList) { IL_INIT(this); }
  32         DESTRUCTOR(IntrusiveList) { IL_DTOR(this); }
  33 ENDCLASS(IntrusiveList)
  34
  35 // bitflags
  36 .vector il_lists;
  37 // bitflags
  38 .vector il_listmask;
  39
  40 #define IL_NEW() NEW(IntrusiveList)
  41
  42 #define IL_EMPTY(this) (this.il_head == NULL)
  43
  44 #define IL_FIRST(this) (this.il_head)
  45 #define IL_LAST(this) (this.il_tail)
  46 #define IL_PEEK(this) (this.il_tail)
  47
  48 ERASEABLE
  49 bool IL_CONTAINS(IntrusiveList this, entity it)
  50 {
  51         assert(this, return false);
  52         return it.(this.il_nextfld) || this.il_head == it || this.il_tail == it;
  53 }
  54
  55 /**
  56  * Push to tail
  57  */
  58 ERASEABLE
  59 entity IL_PUSH(IntrusiveList this, entity it)
  60 {
  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);
  66
  67         entity tail = it.(il_prev) = this.il_tail;
  68         tail ? (tail.(il_next) = it) : this.il_head = it;
  69         this.il_tail = it;
  70         it.il_lists |= this.il_listmask;
  71         return it;
  72 }
  73
  74 /**
  75  * Push to head
  76  */
  77 ERASEABLE
  78 entity IL_UNSHIFT(IntrusiveList this, entity it)
  79 {
  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);
  85
  86         entity head = it.(il_next) = this.il_head;
  87         head ? (head.(il_prev) = it) : this.il_tail = it;
  88         this.il_head = it;
  89         it.il_lists |= this.il_listmask;
  90         return it;
  91 }
  92
  93 /**
  94  * Pop from tail
  95  */
  96 ERASEABLE
  97 entity IL_POP(IntrusiveList this)
  98 {
  99         assert(this, return NULL);
 100         .entity il_next = this.il_nextfld;
 101         .entity il_prev = this.il_prevfld;
 102
 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;
 108         return it;
 109 }
 110
 111 /**
 112  * Pop from head
 113  */
 114 ERASEABLE
 115 entity IL_SHIFT(IntrusiveList this)
 116 {
 117         assert(this, return NULL);
 118         .entity il_next = this.il_nextfld;
 119         .entity il_prev = this.il_prevfld;
 120
 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;
 126         return it;
 127 }
 128
 129 /**
 130  * Remove any element, anywhere in the list
 131  */
 132 ERASEABLE
 133 void IL_REMOVE(IntrusiveList this, entity it)
 134 {
 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;
 149 }
 150
 151 /**
 152  * Remove all elements
 153  */
 154 #define IL_CLEAR(this) \
 155         MACRO_BEGIN \
 156                 IntrusiveList _il = this; \
 157                 assert(_il); \
 158                 .entity il_prev = _il.il_prevfld; \
 159                 .entity il_next = _il.il_nextfld; \
 160                 noref int i = 0; \
 161                 for (entity _next, _it = _il.il_head; _it; (_it = _next, ++i)) \
 162                 { \
 163                         _next = _it.(il_next); \
 164                         _it.(il_next) = _it.(il_prev) = NULL; \
 165                 } \
 166                 _il.il_head = _il.il_tail = NULL; \
 167         MACRO_END
 168
 169 /**
 170  * Delete the list
 171  */
 172 #define IL_DELETE(this) \
 173         MACRO_BEGIN \
 174                 delete(this); \
 175                 this = NULL; \
 176         MACRO_END
 177
 178 #define IL_EACH(this, cond, body) \
 179         MACRO_BEGIN \
 180                 IntrusiveList _il = this; \
 181                 assert(_il); \
 182                 .entity il_next = _il.il_nextfld; \
 183                 noref int i = 0; \
 184                 for (entity _next, _it = _il.il_head; _it; (_it = _next, ++i)) \
 185                 { \
 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; \
 192                         else \
 193                                 _next = it.(il_next); /* in case next item has changed */ \
 194                 } \
 195                 this.il_loop_item = nil; \
 196         MACRO_END
 197
 198 .int il_id;
 199 IntrusiveList il_links[IL_MAX];
 200 .entity il_links_flds[IL_MAX * 2];
 201 int il_links_ptr;
 202
 203 #define IL_FLOOR(n) ((n) | 0)
 204 #define IL_CEIL(n)  IL_FLOOR((n) + 0.5)
 205
 206 #define IL_LISTS_PER_BIT IL_CEIL(IL_MAX / (3 * 24))
 207
 208 ERASEABLE
 209 void IL_INIT(IntrusiveList this)
 210 {
 211         .entity nextfld, prevfld;
 212         for (int i = il_links_ptr; i < il_links_ptr + IL_MAX; ++i) {
 213                 int idx = i;
 214                 if (idx >= IL_MAX) idx -= IL_MAX;
 215                 int id = idx;
 216                 idx *= 2;
 217                 if (!il_links[idx]) {
 218                         il_links[idx] = this;
 219                         nextfld = il_links_flds[idx + 0];
 220                         prevfld = il_links_flds[idx + 1];
 221                         this.il_id = id;
 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)));
 226                         else assert(false);
 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;
 231                         return;
 232                 }
 233         }
 234         LOG_WARN("IntrusiveList overflow");
 235 }
 236
 237 ERASEABLE
 238 void IL_DTOR(IntrusiveList this)
 239 {
 240         IL_CLEAR(this);
 241         il_links[this.il_id] = NULL;
 242 }
 243
 244 ERASEABLE
 245 void IL_ENDFRAME()
 246 {
 247 #if 0
 248         // incompatible with CSQC, remove() clears entities
 249         for (int i = 0; i < IL_MAX; ++i) {
 250                 IntrusiveList list = il_links[i];
 251                 if (list) {
 252                         .entity nextfld = list.il_nextfld;
 253                         for (entity next, it = list.il_head; it; it = next) {
 254                                 next = it.(nextfld);
 255                                 if (wasfreed(it)) {
 256                                         IL_REMOVE(list, it);
 257                                 }
 258                         }
 259                 }
 260         }
 261 #endif
 262 }
 263
 264 // called when an entity is deleted with delete() / remove()
 265 // or when a player disconnects
 266 void ONREMOVE(entity this)
 267 {
 268         // remove 'this' from any intrusive lists it is on
 269         vector lists = this.il_lists;
 270         if (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);
 275                         }
 276                 }
 277         }
 278 }