qcsrc/lib/intrusivelist.qh

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