qcsrc/lib/intrusivelist.qh

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