Optimize IL_REMOVE_RAW. It fixes #2827 (a map with a huge amount of entities crashes...

[xonotic/xonotic-data.pk3dir.git] / qcsrc / lib / intrusivelist.qh

diff --git a/qcsrc/lib/intrusivelist.qh b/qcsrc/lib/intrusivelist.qh
index 9b721a9ba42e96add17111001747949bc89763f0..385f7b3b13282edb9deb40f0252d679923f3c8ff 100644 (file)
--- a/qcsrc/lib/intrusivelist.qh
+++ b/qcsrc/lib/intrusivelist.qh
@@ -1,7 +1,12 @@
 #pragma once
 
 #include "iter.qh"
+#include "test.qh"
 
+/**
+ * Maximum amount of creatable lists.
+ * Lists can be given endless amount of entities, only restricted by engine limitations.
+ */
 const int IL_MAX = 128;
 
 ERASEABLE
@@ -23,6 +28,7 @@ CLASS(IntrusiveList, Object)
        ATTRIB(IntrusiveList, il_tail, entity);
        ATTRIB(IntrusiveList, il_nextfld, .entity, nil);
        ATTRIB(IntrusiveList, il_prevfld, .entity, nil);
+       ATTRIB(IntrusiveList, il_loop_item, entity, NULL);
        INIT(IntrusiveList) { IL_INIT(this); }
        DESTRUCTOR(IntrusiveList) { IL_DTOR(this); }
 ENDCLASS(IntrusiveList)
@@ -100,6 +106,9 @@ entity IL_POP(IntrusiveList this)
        entity prev = it.(il_prev);
        if (prev) (this.il_tail = prev).(il_next) = NULL;
        else this.il_head = this.il_tail = NULL;
+       if (this.il_loop_item == it)
+               this.il_loop_item = NULL;
+       it.(il_prev) = NULL;
        return it;
 }
 
@@ -118,6 +127,9 @@ entity IL_SHIFT(IntrusiveList this)
        entity next = it.(il_next);
        if (next) (this.il_head = next).(il_prev) = NULL;
        else this.il_head = this.il_tail = NULL;
+       if (this.il_loop_item == it)
+               this.il_loop_item = it.(il_next);
+       it.(il_next) = NULL;
        return it;
 }
 
@@ -138,6 +150,8 @@ void IL_REMOVE(IntrusiveList this, entity it)
        next ? next.(il_prev) = prev : this.il_tail = prev;
        prev ? prev.(il_next) = next : this.il_head = next;
        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);
+       if (this.il_loop_item == it)
+               this.il_loop_item = it.(il_next);
        it.(il_next) = it.(il_prev) = NULL;
 }
 
@@ -146,11 +160,17 @@ void IL_REMOVE(IntrusiveList this, entity it)
  */
 #define IL_CLEAR(this) \
        MACRO_BEGIN \
-               IntrusiveList __il = this; \
-               assert(__il); \
-               .entity il_prev = __il.il_prevfld; \
-               IL_EACH(__il, true, it.(il_next) = it.(il_prev) = NULL); \
-               __il.il_head = __il.il_tail = NULL; \
+               IntrusiveList _il = this; \
+               assert(_il); \
+               .entity il_prev = _il.il_prevfld; \
+               .entity il_next = _il.il_nextfld; \
+               noref int i = 0; \
+               for (entity _next, _it = _il.il_head; _it; (_it = _next, ++i)) \
+               { \
+                       _next = _it.(il_next); \
+                       _it.(il_next) = _it.(il_prev) = NULL; \
+               } \
+               _il.il_head = _il.il_tail = NULL; \
        MACRO_END
 
 /**
@@ -168,12 +188,20 @@ void IL_REMOVE(IntrusiveList this, entity it)
                assert(_il); \
                .entity il_next = _il.il_nextfld; \
                noref int i = 0; \
+               entity il_loop_item_save = this.il_loop_item; \
+               this.il_loop_item = NULL; \
                for (entity _next, _it = _il.il_head; _it; (_it = _next, ++i)) \
                { \
                        const noref entity it = _it; \
+                       this.il_loop_item = it; \
                        _next = it.(il_next); \
                        if (cond) { LAMBDA(body) } \
+                       if (this.il_loop_item != it) /* current item removed? */ \
+                               _next = this.il_loop_item; \
+                       else \
+                               _next = it.(il_next); /* in case next item has changed */ \
                } \
+               this.il_loop_item = il_loop_item_save; \
        MACRO_END
 
 .int il_id;
@@ -212,7 +240,7 @@ void IL_INIT(IntrusiveList this)
                        return;
                }
        }
-       LOG_WARNF("IntrusiveList overflow");
+       LOG_WARN("IntrusiveList overflow");
 }
 
 ERASEABLE
@@ -242,15 +270,105 @@ void IL_ENDFRAME()
 #endif
 }
 
-ERASEABLE
+// clears any IL data from an entity (not an intrusive list)
+// it should be used only in very particular cases such as after a copyentity call
+void IL_REMOVE_RAW(entity it)
+{
+       if (it.il_lists)
+       {
+               it.il_lists = '0 0 0';
+               for (int i = 0; i < IL_MAX * 2; ++i)
+                       it.il_links_flds[i] = nil;
+       }
+}
+
+// called when an entity is deleted with delete() / remove()
+// or when a player disconnects
 void ONREMOVE(entity this)
 {
-       if (this.il_lists) {
+       // remove 'this' from any intrusive lists it is on
+       vector lists = this.il_lists;
+       if (lists) {
                for (int i = 0; i < IL_MAX; ++i) {
                        IntrusiveList list = il_links[i];
-                       if (this.il_lists & list.il_listmask && IL_CONTAINS(list, this)) {
+                       if ((lists & list.il_listmask) && IL_CONTAINS(list, this)) {
                                IL_REMOVE(list, this);
                        }
                }
        }
 }
+
+
+#define IL_TEST_BUILD() s = il_test_build(il_test, ent1, ent2, ent3, ent4, ent5)
+
+string il_test_build(entity il_test, entity ent1, entity ent2, entity ent3, entity ent4, entity ent5)
+{
+       IL_CLEAR(il_test);
+       IL_PUSH(il_test, ent1);
+       IL_PUSH(il_test, ent2);
+       IL_PUSH(il_test, ent3);
+       IL_PUSH(il_test, ent4);
+       IL_PUSH(il_test, ent5);
+       return "";
+}
+
+TEST(intrusivelist, ModificationsWhileLooping)
+{
+       IntrusiveList il_test = IL_NEW();
+       entity ent1 = new(1), ent2 = new(2), ent3 = new(3), ent4 = new(4), ent5 = new(5);
+       string s;
+
+       IL_TEST_BUILD();
+       IL_EACH(il_test, true,
+       {
+               s = strcat(s, it.classname);
+               if (it == ent2) IL_REMOVE(il_test, ent3);
+               if (it == ent4) IL_PUSH(il_test, ent3);
+       });
+       EXPECT_TRUE(s == "12453");
+
+       IL_TEST_BUILD();
+       IL_EACH(il_test, true,
+       {
+               s = strcat(s, it.classname);
+               if (it == ent2) IL_REMOVE(il_test, ent2);
+               if (it == ent3) IL_REMOVE(il_test, ent3);
+               if (it == ent3) IL_REMOVE(il_test, ent4);
+               if (it == ent5) IL_POP(il_test);
+       });
+       EXPECT_TRUE(s == "1235");
+
+       IL_TEST_BUILD();
+       IL_REMOVE(il_test, ent5);
+       IL_EACH(il_test, true,
+       {
+               s = strcat(s, it.classname);
+               if (it == ent1) IL_SHIFT(il_test);
+               if (it == ent4) IL_POP(il_test);
+       });
+       EXPECT_TRUE(s == "1234");
+
+       IL_TEST_BUILD();
+       IL_EACH(il_test, true,
+       {
+               s = strcat(s, it.classname);
+               if (it == ent2)
+                       IL_EACH(il_test, true,
+                       {
+                               s = strcat(s, it.classname);
+                               if (it == ent3)
+                                       IL_EACH(il_test, true,
+                                       {
+                                               s = strcat(s, it.classname);
+                                       });
+                               if (it == ent4)
+                                       break;
+                       });
+       });
+       EXPECT_TRUE(s == "12123123454345");
+
+       IL_DELETE(il_test);
+       delete(ent1); delete(ent2); delete(ent3); delete(ent4); delete(ent5);
+
+       SUCCEED();
+}