ListModule

[grim001]

This library provides the List module, which allows you to easily create a linked list of all of the allocated instances of a struct-type. Iterating through a linked list is about 12% faster than iteratating through an array in JASS. There is no faster method to iterate through a list of structs than the method used by this module. Aside from the marginal speed gain, the best use of this library is to hide some ugly low-level code from your structs. Rather than manually building and maintaining a list of struct instances, just implement the List module, and your code will become much prettier.

JASS:

library ListModule
//===========================================================================
// Information:
//==============
//
//     This library provides the List module, which allows you to easily create
// a linked list of all of the allocated instances of a struct-type. Iterating
// through a linked list is about 12% faster than iteratating through an array
// in JASS. There is no faster method to iterate through a list of structs than
// the method used by this module. Aside from the marginal speed gain, the best
// use of this library is to hide some ugly low-level code from your structs.
// Rather than manually building and maintaining a list of struct instances,
// just implement the List module, and your code will become much prettier.
//
//===========================================================================
// How to use the List module:
//=============================
//
//     Using the List module is pretty simple. First, implement it in your
// struct (preferably at the top to avoid unnecessary TriggerEvaluate calls).
// In the struct's create method, you must call listAdd(). In the onDestroy
// method, you must also call listRemove(). An example is shown below:
/*
    struct Example
        implement List
        
        static method create takes nothing returns Example
            local Example this = allocate()
                call listAdd() //This method adds the instance to the list.
            return this
        endmethod
        
        method onDestroy takes nothing returns nothing
            call listRemove() //This method removes the instance from the list.
        endmethod
    endstruct
*/
//     The requirement to call listAdd() and listRemove() will be done away
// with once JassHelper supports module onDestroy and module onCreate, but
// for now, it is not too much of a burden.
//
//     Once this is done, your struct will gain all of the methods detailed
// in the API section. Below is an example of how to iterate through the list
// of allocated structs of the implementing struct-type:
/*
    function IterationExample takes nothing returns nothing
        local Example e = Example.first
            loop
                exitwhen e == 0
                //Do something with e here.
                set e = e.next
            endloop
        //Use .last and .prev instead to iterate backwards.
    endmethod
*/
//
//===========================================================================
// List module API:
//==================
//
// (readonly)(static) first -> thistype
//   This member contains the first instance of thistype in the list.
//
// (readonly)(static) last -> thistype
//   This member contains the last instance of thistype in the list.
//
// (readonly)(static) count -> integer
//   This member contains the number of allocated structs of thistype.
//
// (readonly) next -> thistype
//   This member contains the next instance of thistype in the list.
//
// (readonly) prev -> thistype
//   This member contains the previous instance of thistype in the list.
//
// listAdd()
//   This method adds this instance to the list of structs of thistype.
//   This should be called on each instance after it is allocated (within
//   the create method).
//
// listRemove()
//   This method removes this instance from the list of structs of thistype.
//   This should be called on each instance before it is destroyed (within
//   the onDestroy method).
//
// (static) listDestroy()
//   This method destroys all the structs of thistype within the list.
//
//===========================================================================

module List
    private static boolean destroying = false
    private boolean inlist = false
    
    readonly static integer count = 0
    
    readonly thistype next = 0
    readonly thistype prev = 0
    
    static method operator first takes nothing returns thistype
        return thistype(0).next
    endmethod
    
    static method operator last takes nothing returns thistype
        return thistype(0).prev
    endmethod
    
    method listRemove takes nothing returns nothing
        if not inlist then
            return
        endif
        set inlist = false
        set prev.next = next
        set next.prev = prev
        set count = count - 1
    endmethod

    method listAdd takes nothing returns nothing
        if inlist or destroying then
            return
        endif
        set inlist = true
        set last.next = this
        set prev = last
        set thistype(0).prev = this
        set count = count + 1
    endmethod
    
    static method listDestroy takes nothing returns nothing
        local thistype this = last
            set destroying = true
            loop
                exitwhen this == 0
                call destroy()
                set this = prev
            endloop
            set destroying = false
    endmethod
    
endmodule

endlibrary

[akolyt0r]

looks much better than DataTable ;)

however in your first example the "LoopThroughAllYourStructs" method most probably should be static ;)

[Here-b-Trollz]

StackModule too plx.

[grim001]

Updated, it regained the ability to destroy structs attached to units leaving the game.

[akolyt0r]

Originally Posted by grim001

Updated, it regained the ability to destroy structs attached to units leaving the game.

that should be optional .. add a boolean to UnitList...

[grim001]

You mean give the user the option to leak?

[dead_or_alivex]

Great, I was just thinking of something like this. I was toying with the idea of making structs extend a linked list struct, then thought to use the new modules, and then came across this topic.

Originally Posted by Documentation

The "List" module allows you to create a linked list containing all of the allocated instances of a struct.

This is slightly misleading. You can choose which structs go into the list, right? When I first read it I got the impression that you couldn't.

[grim001]

You can leave structs out of the list, but I can't think of any application where it makes sense to do so. Documentation gets long enough without describing unintended ways of using it. If Vex adds module-specific onCreate, onDestroy, etc., I could make the adding/removing automatic.

[Tide-Arc Ephemera]

Grim, change your user title to "Requires vJass" so you don't have to type it for everything you do at WC3C.

[grim001]

Originally Posted by Here-b-Trollz

StackModule too plx.

Do you actually need fast random access? Otherwise linked list is superior.

[PipeDream]

It doesn't exactly implement what we usually call lists, since there's two extra invariants: uniqueness of entries and it's static in the single instance sense. Because of the uniqueness the base name should be Set. I'm uncertain what to do about the single instantiability - consider SingletonSet, StaticSet.

I'm skeptical of the claim that it's faster than iterating over an array, but I like the style.

[grim001]

Let's compare array iteration and linked list iteration:

Array style:

JASS:

function DoLoop takes nothing returns nothing
    local integer n = MyStruct.stack_n //global read
    local MyStruct ms
        loop
            exitwhen n < 0 //var read and comparison
            set ms = MyStruct[n] //var set, var read, array read
            //do stuff
            set n = n - 1 //var read, subtraction, var set
        endloop
endfunction

Requires 2 local integer declarations, 1 global read
Requires 1 comparison, 1 global array read, 3 local read, 2 local sets, 1 subtraction per loop

Linked list style:

JASS:

function DoLoop takes nothing returns nothing
    local MyStruct ms = MyStruct.first //global read
        loop
            exitwhen ms == 0 //var read and comparison
            //do stuff
            set ms = ms.next //var set, var read, array read
        endloop
endfunction

Requires 1 local integer declaration, 1 global read
Requires 1 comparison, 1 global array read, 2 local read, 1 local set

The difference comes out to 1 fewer local declaration in the function, and 1 less local read/local set/subtraction per loop (all from getting rid of the n = n - 1 line). It's not that big of a deal but it should please the "speed wanker" group as they have been referred to lately.

[PipeDream]

Count literal values as well in ops

The subtlety I missed is the extra layer of indirection required by an array implementation which is absorbed naturally by linked lists.

Not a criticism:
You don't have to have indirection at the cost of copying the entire struct contents. Since iteration is more frequent than modification, some structs are small, etc, it's not nonsensical. It could even happen in a system like this w vjass support for automatic struct assignment by value, or a requirement that people write a copy or move by value method.

[grim001]

I'm going to split this into two libraries since UnitList has become much bigger.

[Vexorian]

Could you move UnitListModule to another thread? I'll review ListModule:
...
Ok, ListModule has been approved, but I'd rather you move UnitListModule to another thread, so I can just approve this one and review that other one later instead of having to wait till reviewing UnitListModule before approving this one.