intrusivelist.qh

Go to the documentation of this file.

#pragma once
 
#include "bits.qh"
#include "iter.qh"
#include "test.qh"

const int IL_MAX = 128;
 
ERASEABLE
void IL_INIT(entity this);
ERASEABLE
void IL_DTOR(entity this);
ERASEABLE
void IL_ENDFRAME();

CLASS(IntrusiveList, Object)
    ATTRIB(IntrusiveList, il_head, entity);
    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)
 
// bitflags
.vector il_lists;
// bitflags
.vector il_listmask;
 
#define IL_NEW() NEW(IntrusiveList)
 
#define IL_EMPTY(this) (this.il_head == NULL)
 
#define IL_FIRST(this) (this.il_head)
#define IL_LAST(this) (this.il_tail)
#define IL_PEEK(this) (this.il_tail)
 
ERASEABLE
bool IL_CONTAINS(IntrusiveList this, entity it)
{
    assert(this, return false);
    return it.(this.il_nextfld) || this.il_head == it || this.il_tail == it;
}

ERASEABLE
entity IL_PUSH(IntrusiveList this, entity it)
{
    assert(this, return NULL);
    assert(it, return NULL);
    .entity il_next = this.il_nextfld;
    .entity il_prev = this.il_prevfld;
    assert(!IL_CONTAINS(this, it), return NULL);
 
    entity tail = it.(il_prev) = this.il_tail;
    tail ? (tail.(il_next) = it) : this.il_head = it;
    this.il_tail = it;
    it.il_lists |= this.il_listmask;
    return it;
}

ERASEABLE
entity IL_UNSHIFT(IntrusiveList this, entity it)
{
    assert(this, return NULL);
    assert(it, return NULL);
    .entity il_next = this.il_nextfld;
    .entity il_prev = this.il_prevfld;
    assert(!IL_CONTAINS(this, it), return NULL);
 
    entity head = it.(il_next) = this.il_head;
    head ? (head.(il_prev) = it) : this.il_tail = it;
    this.il_head = it;
    it.il_lists |= this.il_listmask;
    return it;
}

ERASEABLE
entity IL_POP(IntrusiveList this)
{
    assert(this, return NULL);
    .entity il_next = this.il_nextfld;
    .entity il_prev = this.il_prevfld;
 
    if (!this.il_tail) return NULL;
    entity it = this.il_tail;
    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;
}

ERASEABLE
entity IL_SHIFT(IntrusiveList this)
{
    assert(this, return NULL);
    .entity il_next = this.il_nextfld;
    .entity il_prev = this.il_prevfld;
 
    if (!this.il_head) return NULL;
    entity it = this.il_head;
    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;
}

ERASEABLE
void IL_REMOVE(IntrusiveList this, entity it)
{
    assert(this, return);
    .entity il_next = this.il_nextfld;
    .entity il_prev = this.il_prevfld;
    //assert(!IL_CONTAINS(this, it), return);
    entity next = it.(il_next);
    entity prev = it.(il_prev);
    entity ohead = this.il_head;
    entity otail = this.il_tail;
    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;
}

#define IL_CLEAR(this) \
    MACRO_BEGIN \
        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

#define IL_DELETE(this) \
    MACRO_BEGIN \
        delete(this); \
        this = NULL; \
    MACRO_END
 
#define IL_EACH(this, cond, body) \
    MACRO_BEGIN \
        IntrusiveList _il = this; \
        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;
IntrusiveList il_links[IL_MAX];
.entity il_links_flds[IL_MAX * 2];
int il_links_ptr;
 
#define IL_FLOOR(n) ((n) | 0)
#define IL_CEIL(n)  IL_FLOOR((n) + 0.5)
 
#define IL_LISTS_PER_BIT IL_CEIL(IL_MAX / (3 * 24))
 
ERASEABLE
void IL_INIT(IntrusiveList this)
{
    .entity nextfld, prevfld;
    for (int i = il_links_ptr; i < il_links_ptr + IL_MAX; ++i) {
        int id = i;
        if (id >= IL_MAX) id -= IL_MAX;
 
        if (!il_links[id]) {
            il_links[id] = this;
            int flds_idx = id * 2;
            nextfld = il_links_flds[flds_idx + 0];
            prevfld = il_links_flds[flds_idx + 1];
            this.il_id = id;
            int bit = IL_FLOOR(id / IL_LISTS_PER_BIT);
            if (bit < (1 * 24)) this.il_listmask = '1 0 0' * BIT(bit - (0 * 24));
            else if (bit < (2 * 24)) this.il_listmask = '0 1 0' * BIT(bit - (1 * 24));
            else if (bit < (3 * 24)) this.il_listmask = '0 0 1' * BIT(bit - (2 * 24));
            else assert(false);
            il_links_ptr = id + 1;
            if (il_links_ptr >= IL_MAX) il_links_ptr -= IL_MAX;
            this.il_nextfld = nextfld;
            this.il_prevfld = prevfld;
            return;
        }
    }
    LOG_WARN("IntrusiveList overflow");
}
 
ERASEABLE
void IL_DTOR(IntrusiveList this)
{
    IL_CLEAR(this);
    il_links[this.il_id] = NULL;
}
 
ERASEABLE
void IL_ENDFRAME()
{
#if 0
    // incompatible with CSQC, remove() clears entities
    for (int i = 0; i < IL_MAX; ++i) {
        IntrusiveList list = il_links[i];
        if (list) {
            .entity nextfld = list.il_nextfld;
            for (entity next, it = list.il_head; it; it = next) {
                next = it.(nextfld);
                if (wasfreed(it)) {
                    IL_REMOVE(list, it);
                }
            }
        }
    }
#endif
}
 
// 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)
{
    // 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 ((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();
}