trying a linked list

[Rushhour]

After reading these two words several times I decided to find out what you are all talking about
I think this is the basic concept: Each instance knows the instance 'behind' and 'in front of' itself. I didn't read any tutorial (if there exists one) and after some minutese of trial and error I made the following work as expected. But I'm pretty sure it isn't done the most elegant way so I would like you to comment about this.
I basically need to easily loop through all instances of a type so that I don't need to attach a timer to every instance. This resulted in a major drop in fps when trying it with some more units

globals
    public Illusion LastAllocated
endglobals

struct Illusion 
    thistype prev
    thistype next
    
    method Destroy takes nothing returns nothing
        if this==LastAllocated then
            set LastAllocated=this.prev
        endif
        set this.prev.next=this.next
        set this.next.prev=this.prev
        call this.deallocate()
    endmethod
    
    static method LoopThroughAll takes nothing returns nothing
        local thistype curr=LastAllocated
        loop
            call BJDebugMsg("looping through instance: "+I2S(curr)+" next is: "+I2S(curr.next))
            set curr=curr.next
            exitwhen curr==LastAllocated
        endloop
    endmethod
    
    static method create takes nothing returns Illusion
        local thistype this = Illusion.allocate()
        set this.prev=LastAllocated
        set this.next=LastAllocated.next
        set this.next.prev=this
        set LastAllocated.next=this
        set LastAllocated=this
        return this
    endmethod
    
    static method OnInit takes nothing returns nothing
        //the first allocated instance is one. it is its own next and prev instance
        set LastAllocated=1
        set LastAllocated.prev=LastAllocated
        set LastAllocated.next=LastAllocated
    endmethod
endstruct

 

[Nestharus]

exitwhen next == 0

is faster than

exitwhen curr==LastAllocated

Also, did you want this to support multiple lists or one? If only one, your design needs to change a little (lastAllocated isn't needed).

Also, you need to have one common head... constantly updating your head is silly ; P.


A linked list looks like this-

head.next = first
head.previous = last

first.previous = 0
last.next = 0

if you have single instanced list, it looks like this

thistype(0).next = first
thistype(0).previous = last
first.previous = 0
last.next = 0

Next off, if you don't have any actual destruction (just deallocation), then you should use the list nodes for your recycling as well. In this way, clear is very simple..

set head.previous.next = recycle
set recycle.previous = head.previous
set recycle = head.next
set head.next = 0
set head.previous = 0

and destroy would be
set head.next.previous = head
set head.previous.next = recycle
set recycle.previous = head.previous
set head.previous = 0
set recycle = head

 

[kingkingyyk3]

Why not just use T32? LOL

 

[Nestharus]

Why not just use T32? LOL

True that (didn't read the whole iterate on timer thing, just read his code ^_^).


Anyways, here is some pretty common timer iteration code I use if you want to try it from scratch. This is just ripped out of a garbage collector, so that's why the names are as they are.

////
//fields
private thistype next
private thistype previous
private static timer recycler = CreateTimer()
private static boolean recycleRunning = false

private static method operator head takes nothing returns thistype
    return 0
endmethod

//in destroy method
//set next.previous = previous
//set previous.next = next

        private static method runRecycle takes nothing returns nothing
            local thistype this = head.next
            loop
                exitwhen this == 0
                if (unit == null) then
                    call destroy()
                endif
                set this = next
            endloop
            
            if (head.next == 0) then
                set recycleRunning = false
                call PauseTimer(recycler)
            endif
        endmethod
        
        private method recycle takes nothing returns nothing
            set head.next.previous = this
            set next = head.next
            set head.next = this
            set previous = head
            
            if (not recycleRunning) then
                set recycleRunning = true
                call TimerStart(recycler, 2, true, function thistype.runRecycle)
            endif
        endmethod

 

[Jesus4Lyf]

Definitely investigate this. Look at the T32x module, and see if you can figure it out.

It is, as far as we can tell, the fastest linked list iteration method possible in JASS.
In fact, the fastest possible iteration method over any collection of structs (without breaking abstraction).

 

[Rushhour]

So I had a look at the T32 module. Indeed , this is just the thing I wanted to have for my struct.. I didn't know it even existed.
But I think it is always better to understand for oneself how things really work.

So this list works pretty much like mine did with the great exception that I didn't use the 0-struct instance as a constant header but always set it to the last allocated instance.

A it's a great thing to know you understood one more thing Thanks to all of you. +rep

 

[kingkingyyk3]

And yeah, for more advanced usage, you can use this.