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                 entity il_loop_item_save = this.il_loop_item; \
 192                 this.il_loop_item = NULL; \
 193                 for (entity _next, _it = _il.il_head; _it; (_it = _next, ++i)) \
 194                 { \
 195                         const noref entity it = _it; \
 196                         this.il_loop_item = it; \
 197                         _next = it.(il_next); \
 198                         if (cond) { LAMBDA(body) } \
 199                         if (this.il_loop_item != it) /* current item removed? */ \
 200                                 _next = this.il_loop_item; \
 201                         else \
 202                                 _next = it.(il_next); /* in case next item has changed */ \
 203                 } \
 204                 this.il_loop_item = il_loop_item_save; \
 205         MACRO_END
 206
 207 .int il_id;
 208 IntrusiveList il_links[IL_MAX];
 209 .entity il_links_flds[IL_MAX * 2];
 210 int il_links_ptr;
 211
 212 #define IL_FLOOR(n) ((n) | 0)
 213 #define IL_CEIL(n)  IL_FLOOR((n) + 0.5)
 214
 215 #define IL_LISTS_PER_BIT IL_CEIL(IL_MAX / (3 * 24))
 216
 217 ERASEABLE
 218 void IL_INIT(IntrusiveList this)
 219 {
 220         .entity nextfld, prevfld;
 221         for (int i = il_links_ptr; i < il_links_ptr + IL_MAX; ++i) {
 222                 int idx = i;
 223                 if (idx >= IL_MAX) idx -= IL_MAX;
 224                 int id = idx;
 225                 idx *= 2;
 226                 if (!il_links[idx]) {
 227                         il_links[idx] = this;
 228                         nextfld = il_links_flds[idx + 0];
 229                         prevfld = il_links_flds[idx + 1];
 230                         this.il_id = id;
 231                         int bit = IL_FLOOR(id / IL_LISTS_PER_BIT);
 232                         if (bit < (1 * 24)) this.il_listmask = '1 0 0' * (1 << (bit - (0 * 24)));
 233                         else if (bit < (2 * 24)) this.il_listmask = '0 1 0' * (1 << (bit - (1 * 24)));
 234                         else if (bit < (3 * 24)) this.il_listmask = '0 0 1' * (1 << (bit - (2 * 24)));
 235                         else assert(false);
 236                         il_links_ptr = id + 1;
 237                         if (il_links_ptr >= IL_MAX) il_links_ptr -= IL_MAX;
 238                         this.il_nextfld = nextfld;
 239                         this.il_prevfld = prevfld;
 240                         return;
 241                 }
 242         }
 243         LOG_WARN("IntrusiveList overflow");
 244 }
 245
 246 ERASEABLE
 247 void IL_DTOR(IntrusiveList this)
 248 {
 249         IL_CLEAR(this);
 250         il_links[this.il_id] = NULL;
 251 }
 252
 253 ERASEABLE
 254 void IL_ENDFRAME()
 255 {
 256 #if 0
 257         // incompatible with CSQC, remove() clears entities
 258         for (int i = 0; i < IL_MAX; ++i) {
 259                 IntrusiveList list = il_links[i];
 260                 if (list) {
 261                         .entity nextfld = list.il_nextfld;
 262                         for (entity next, it = list.il_head; it; it = next) {
 263                                 next = it.(nextfld);
 264                                 if (wasfreed(it)) {
 265                                         IL_REMOVE(list, it);
 266                                 }
 267                         }
 268                 }
 269         }
 270 #endif
 271 }
 272
 273 // clears any IL data from an entity (not an intrusive list)
 274 // it should be used only in very particular cases such as after a copyentity call
 275 void IL_REMOVE_RAW(entity it)
 276 {
 277         if (it.il_lists)
 278         {
 279                 it.il_lists = '0 0 0';
 280                 for (int i = 0; i < IL_MAX * 2; ++i)
 281                         it.il_links_flds[i] = nil;
 282         }
 283 }
 284
 285 // called when an entity is deleted with delete() / remove()
 286 // or when a player disconnects
 287 void ONREMOVE(entity this)
 288 {
 289         // remove 'this' from any intrusive lists it is on
 290         vector lists = this.il_lists;
 291         if (lists) {
 292                 for (int i = 0; i < IL_MAX; ++i) {
 293                         IntrusiveList list = il_links[i];
 294                         if ((lists & list.il_listmask) && IL_CONTAINS(list, this)) {
 295                                 IL_REMOVE(list, this);
 296                         }
 297                 }
 298         }
 299 }
 300
 301
 302 #define IL_TEST_BUILD() s = il_test_build(il_test, ent1, ent2, ent3, ent4, ent5)
 303
 304 string il_test_build(entity il_test, entity ent1, entity ent2, entity ent3, entity ent4, entity ent5)
 305 {
 306         IL_CLEAR(il_test);
 307         IL_PUSH(il_test, ent1);
 308         IL_PUSH(il_test, ent2);
 309         IL_PUSH(il_test, ent3);
 310         IL_PUSH(il_test, ent4);
 311         IL_PUSH(il_test, ent5);
 312         return "";
 313 }
 314
 315 TEST(intrusivelist, ModificationsWhileLooping)
 316 {
 317         IntrusiveList il_test = IL_NEW();
 318         entity ent1 = new(1), ent2 = new(2), ent3 = new(3), ent4 = new(4), ent5 = new(5);
 319         string s;
 320
 321         IL_TEST_BUILD();
 322         IL_EACH(il_test, true,
 323         {
 324                 s = strcat(s, it.classname);
 325                 if (it == ent2) IL_REMOVE(il_test, ent3);
 326                 if (it == ent4) IL_PUSH(il_test, ent3);
 327         });
 328         EXPECT_TRUE(s == "12453");
 329
 330         IL_TEST_BUILD();
 331         IL_EACH(il_test, true,
 332         {
 333                 s = strcat(s, it.classname);
 334                 if (it == ent2) IL_REMOVE(il_test, ent2);
 335                 if (it == ent3) IL_REMOVE(il_test, ent3);
 336                 if (it == ent3) IL_REMOVE(il_test, ent4);
 337                 if (it == ent5) IL_POP(il_test);
 338         });
 339         EXPECT_TRUE(s == "1235");
 340
 341         IL_TEST_BUILD();
 342         IL_REMOVE(il_test, ent5);
 343         IL_EACH(il_test, true,
 344         {
 345                 s = strcat(s, it.classname);
 346                 if (it == ent1) IL_SHIFT(il_test);
 347                 if (it == ent4) IL_POP(il_test);
 348         });
 349         EXPECT_TRUE(s == "1234");
 350
 351         IL_TEST_BUILD();
 352         IL_EACH(il_test, true,
 353         {
 354                 s = strcat(s, it.classname);
 355                 if (it == ent2)
 356                         IL_EACH(il_test, true,
 357                         {
 358                                 s = strcat(s, it.classname);
 359                                 if (it == ent3)
 360                                         IL_EACH(il_test, true,
 361                                         {
 362                                                 s = strcat(s, it.classname);
 363                                         });
 364                                 if (it == ent4)
 365                                         break;
 366                         });
 367         });
 368         EXPECT_TRUE(s == "12123123454345");
 369
 370         IL_DELETE(il_test);
 371         delete(ent1); delete(ent2); delete(ent3); delete(ent4); delete(ent5);
 372
 373         SUCCEED();
 374 }