qcsrc/lib/intrusivelist.qh

   1 #pragma once
   2
   3 #include "iter.qh"
   4 #include "test.qh"
   5
   6 /**
   7  * Maximum amount of creatable lists.
   8  * Lists can be given endless amount of entities, only restricted by engine limitations.
   9  */
  10 const int IL_MAX = 128;
  11
  12 ERASEABLE
  13 void IL_INIT(entity this);
  14 ERASEABLE
  15 void IL_DTOR(entity this);
  16 ERASEABLE
  17 void IL_ENDFRAME();
  18
  19 /**
  20  * limitations:
  21  *   NULL cannot be present
  22  *   elements can only be present once
  23  *   a maximum of `IL_MAX` lists can exist at one time
  24  *   freed entities must be removed from the list
  25  */
  26 CLASS(IntrusiveList, Object)
  27         ATTRIB(IntrusiveList, il_head, entity);
  28         ATTRIB(IntrusiveList, il_tail, entity);
  29         ATTRIB(IntrusiveList, il_nextfld, .entity, nil);
  30         ATTRIB(IntrusiveList, il_prevfld, .entity, nil);
  31         ATTRIB(IntrusiveList, il_loop_item, entity, NULL);
  32         INIT(IntrusiveList) { IL_INIT(this); }
  33         DESTRUCTOR(IntrusiveList) { IL_DTOR(this); }
  34 ENDCLASS(IntrusiveList)
  35
  36 // bitflags
  37 .vector il_lists;
  38 // bitflags
  39 .vector il_listmask;
  40
  41 #define IL_NEW() NEW(IntrusiveList)
  42
  43 #define IL_EMPTY(this) (this.il_head == NULL)
  44
  45 #define IL_FIRST(this) (this.il_head)
  46 #define IL_LAST(this) (this.il_tail)
  47 #define IL_PEEK(this) (this.il_tail)
  48
  49 ERASEABLE
  50 bool IL_CONTAINS(IntrusiveList this, entity it)
  51 {
  52         assert(this, return false);
  53         return it.(this.il_nextfld) || this.il_head == it || this.il_tail == it;
  54 }
  55
  56 /**
  57  * Push to tail
  58  */
  59 ERASEABLE
  60 entity IL_PUSH(IntrusiveList this, entity it)
  61 {
  62         assert(this, return NULL);
  63         assert(it, return NULL);
  64         .entity il_next = this.il_nextfld;
  65         .entity il_prev = this.il_prevfld;
  66         assert(!IL_CONTAINS(this, it), return NULL);
  67
  68         entity tail = it.(il_prev) = this.il_tail;
  69         tail ? (tail.(il_next) = it) : this.il_head = it;
  70         this.il_tail = it;
  71         it.il_lists |= this.il_listmask;
  72         return it;
  73 }
  74
  75 /**
  76  * Push to head
  77  */
  78 ERASEABLE
  79 entity IL_UNSHIFT(IntrusiveList this, entity it)
  80 {
  81         assert(this, return NULL);
  82         assert(it, return NULL);
  83         .entity il_next = this.il_nextfld;
  84         .entity il_prev = this.il_prevfld;
  85         assert(!IL_CONTAINS(this, it), return NULL);
  86
  87         entity head = it.(il_next) = this.il_head;
  88         head ? (head.(il_prev) = it) : this.il_tail = it;
  89         this.il_head = it;
  90         it.il_lists |= this.il_listmask;
  91         return it;
  92 }
  93
  94 /**
  95  * Pop from tail
  96  */
  97 ERASEABLE
  98 entity IL_POP(IntrusiveList this)
  99 {
 100         assert(this, return NULL);
 101         .entity il_next = this.il_nextfld;
 102         .entity il_prev = this.il_prevfld;
 103
 104         if (!this.il_tail) return NULL;
 105         entity it = this.il_tail;
 106         entity prev = it.(il_prev);
 107         if (prev) (this.il_tail = prev).(il_next) = NULL;
 108         else this.il_head = this.il_tail = NULL;
 109         if (this.il_loop_item == it)
 110                 this.il_loop_item = NULL;
 111         it.(il_prev) = NULL;
 112         return it;
 113 }
 114
 115 /**
 116  * Pop from head
 117  */
 118 ERASEABLE
 119 entity IL_SHIFT(IntrusiveList this)
 120 {
 121         assert(this, return NULL);
 122         .entity il_next = this.il_nextfld;
 123         .entity il_prev = this.il_prevfld;
 124
 125         if (!this.il_head) return NULL;
 126         entity it = this.il_head;
 127         entity next = it.(il_next);
 128         if (next) (this.il_head = next).(il_prev) = NULL;
 129         else this.il_head = this.il_tail = NULL;
 130         if (this.il_loop_item == it)
 131                 this.il_loop_item = it.(il_next);
 132         it.(il_next) = NULL;
 133         return it;
 134 }
 135
 136 /**
 137  * Remove any element, anywhere in the list
 138  */
 139 ERASEABLE
 140 void IL_REMOVE(IntrusiveList this, entity it)
 141 {
 142         assert(this, return);
 143         .entity il_next = this.il_nextfld;
 144         .entity il_prev = this.il_prevfld;
 145         //assert(!IL_CONTAINS(this, it), return);
 146         entity next = it.(il_next);
 147         entity prev = it.(il_prev);
 148         entity ohead = this.il_head;
 149         entity otail = this.il_tail;
 150         next ? next.(il_prev) = prev : this.il_tail = prev;
 151         prev ? prev.(il_next) = next : this.il_head = next;
 152         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);
 153         if (this.il_loop_item == it)
 154                 this.il_loop_item = it.(il_next);
 155         it.(il_next) = it.(il_prev) = NULL;
 156 }
 157
 158 /**
 159  * Remove all elements
 160  */
 161 #define IL_CLEAR(this) \
 162         MACRO_BEGIN \
 163                 IntrusiveList _il = this; \
 164                 assert(_il); \
 165                 .entity il_prev = _il.il_prevfld; \
 166                 .entity il_next = _il.il_nextfld; \
 167                 noref int i = 0; \
 168                 for (entity _next, _it = _il.il_head; _it; (_it = _next, ++i)) \
 169                 { \
 170                         _next = _it.(il_next); \
 171                         _it.(il_next) = _it.(il_prev) = NULL; \
 172                 } \
 173                 _il.il_head = _il.il_tail = NULL; \
 174         MACRO_END
 175
 176 /**
 177  * Delete the list
 178  */
 179 #define IL_DELETE(this) \
 180         MACRO_BEGIN \
 181                 delete(this); \
 182                 this = NULL; \
 183         MACRO_END
 184
 185 #define IL_EACH(this, cond, body) \
 186         MACRO_BEGIN \
 187                 IntrusiveList _il = this; \
 188                 assert(_il); \
 189                 .entity il_next = _il.il_nextfld; \
 190                 noref int i = 0; \
 191                 for (entity _next, _it = _il.il_head; _it; (_it = _next, ++i)) \
 192                 { \
 193                         const noref entity it = _it; \
 194                         this.il_loop_item = it; \
 195                         _next = it.(il_next); \
 196                         if (cond) { LAMBDA(body) } \
 197                         if (this.il_loop_item != it) /* current item removed? */ \
 198                                 _next = this.il_loop_item; \
 199                         else \
 200                                 _next = it.(il_next); /* in case next item has changed */ \
 201                 } \
 202                 this.il_loop_item = NULL; \
 203         MACRO_END
 204
 205 .int il_id;
 206 IntrusiveList il_links[IL_MAX];
 207 .entity il_links_flds[IL_MAX * 2];
 208 int il_links_ptr;
 209
 210 #define IL_FLOOR(n) ((n) | 0)
 211 #define IL_CEIL(n)  IL_FLOOR((n) + 0.5)
 212
 213 #define IL_LISTS_PER_BIT IL_CEIL(IL_MAX / (3 * 24))
 214
 215 ERASEABLE
 216 void IL_INIT(IntrusiveList this)
 217 {
 218         .entity nextfld, prevfld;
 219         for (int i = il_links_ptr; i < il_links_ptr + IL_MAX; ++i) {
 220                 int idx = i;
 221                 if (idx >= IL_MAX) idx -= IL_MAX;
 222                 int id = idx;
 223                 idx *= 2;
 224                 if (!il_links[idx]) {
 225                         il_links[idx] = this;
 226                         nextfld = il_links_flds[idx + 0];
 227                         prevfld = il_links_flds[idx + 1];
 228                         this.il_id = id;
 229                         int bit = IL_FLOOR(id / IL_LISTS_PER_BIT);
 230                         if (bit < (1 * 24)) this.il_listmask = '1 0 0' * (1 << (bit - (0 * 24)));
 231                         else if (bit < (2 * 24)) this.il_listmask = '0 1 0' * (1 << (bit - (1 * 24)));
 232                         else if (bit < (3 * 24)) this.il_listmask = '0 0 1' * (1 << (bit - (2 * 24)));
 233                         else assert(false);
 234                         il_links_ptr = id + 1;
 235                         if (il_links_ptr >= IL_MAX) il_links_ptr -= IL_MAX;
 236                         this.il_nextfld = nextfld;
 237                         this.il_prevfld = prevfld;
 238                         return;
 239                 }
 240         }
 241         LOG_WARN("IntrusiveList overflow");
 242 }
 243
 244 ERASEABLE
 245 void IL_DTOR(IntrusiveList this)
 246 {
 247         IL_CLEAR(this);
 248         il_links[this.il_id] = NULL;
 249 }
 250
 251 ERASEABLE
 252 void IL_ENDFRAME()
 253 {
 254 #if 0
 255         // incompatible with CSQC, remove() clears entities
 256         for (int i = 0; i < IL_MAX; ++i) {
 257                 IntrusiveList list = il_links[i];
 258                 if (list) {
 259                         .entity nextfld = list.il_nextfld;
 260                         for (entity next, it = list.il_head; it; it = next) {
 261                                 next = it.(nextfld);
 262                                 if (wasfreed(it)) {
 263                                         IL_REMOVE(list, it);
 264                                 }
 265                         }
 266                 }
 267         }
 268 #endif
 269 }
 270
 271 // called when an entity is deleted with delete() / remove()
 272 // or when a player disconnects
 273 void ONREMOVE(entity this)
 274 {
 275         // remove 'this' from any intrusive lists it is on
 276         vector lists = this.il_lists;
 277         if (lists) {
 278                 for (int i = 0; i < IL_MAX; ++i) {
 279                         IntrusiveList list = il_links[i];
 280                         if ((lists & list.il_listmask) && IL_CONTAINS(list, this)) {
 281                                 IL_REMOVE(list, this);
 282                         }
 283                 }
 284         }
 285 }
 286
 287
 288 #define IL_TEST_BUILD() s = il_test_build(il_test, ent1, ent2, ent3, ent4, ent5)
 289
 290 string il_test_build(entity il_test, entity ent1, entity ent2, entity ent3, entity ent4, entity ent5)
 291 {
 292         IL_CLEAR(il_test);
 293         IL_PUSH(il_test, ent1);
 294         IL_PUSH(il_test, ent2);
 295         IL_PUSH(il_test, ent3);
 296         IL_PUSH(il_test, ent4);
 297         IL_PUSH(il_test, ent5);
 298         return "";
 299 }
 300
 301 TEST(intrusivelist, ModificationsWhileLooping)
 302 {
 303         IntrusiveList il_test = IL_NEW();
 304         entity ent1 = new(1), ent2 = new(2), ent3 = new(3), ent4 = new(4), ent5 = new(5);
 305         string s;
 306
 307         IL_TEST_BUILD();
 308         IL_EACH(il_test, true,
 309         {
 310                 s = strcat(s, it.classname);
 311                 if (it == ent2) IL_REMOVE(il_test, ent3);
 312                 if (it == ent4) IL_PUSH(il_test, ent3);
 313         });
 314         EXPECT_TRUE(s == "12453");
 315
 316         IL_TEST_BUILD();
 317         IL_EACH(il_test, true,
 318         {
 319                 s = strcat(s, it.classname);
 320                 if (it == ent2) IL_REMOVE(il_test, ent2);
 321                 if (it == ent3) IL_REMOVE(il_test, ent3);
 322                 if (it == ent3) IL_REMOVE(il_test, ent4);
 323                 if (it == ent5) IL_POP(il_test);
 324         });
 325         EXPECT_TRUE(s == "1235");
 326
 327         IL_TEST_BUILD();
 328         IL_REMOVE(il_test, ent5);
 329         IL_EACH(il_test, true,
 330         {
 331                 s = strcat(s, it.classname);
 332                 if (it == ent1) IL_SHIFT(il_test);
 333                 if (it == ent4) IL_POP(il_test);
 334         });
 335         EXPECT_TRUE(s == "1234");
 336
 337         IL_DELETE(il_test);
 338         delete(ent1); delete(ent2); delete(ent3); delete(ent4); delete(ent5);
 339
 340         SUCCEED();
 341 }