Snippet List Optimum Speed

[Nestharus]

Every single thing includes complete demonstrations. The highest layers are at the bottom.

Malloc
Stacks
Dequeues

Malloc

/*
    MALLOC_FIELDS takes NAMESPACE
*/

//malloc
//! textmacro MALLOC_FIELDS takes NAMESPACE
    //refers to current index of malloc
    public static integer mallocIndex$NAMESPACE$ = 1
    //refers to number of deallocated elements in the malloc
    public static integer mallocDeallocatedCount$NAMESPACE$ = 0
    //refers deallocated elements in the malloc
    public static integer array mallocDeallocated$NAMESPACE$
//! endtextmacro

/*
MALLOC_ALLOCATE_FREED takes NAMESPACE, MEMORY_REF
    //code
else
    MALLOC_ALLOCATE_NEW takes NAMESPACE, MEMORY_REF
    //code
endif
//code
*/

//try to get element from deallocated area
//! textmacro MALLOC_ALLOCATE_FREED takes NAMESPACE, MEMORY_REF
    if $MEMORY_REF$.mallocDeallocatedCount$NAMESPACE$ > 0 then //check for freed elements in the malloc
        //set memory reference to the last deallocated element and remove that element from the malloc
        set $MEMORY_REF$.mallocDeallocatedCount$NAMESPACE$ = $MEMORY_REF$.mallocDeallocatedCount$NAMESPACE$ - 1
        set $MEMORY_REF$ = $MEMORY_REF$.mallocDeallocated$NAMESPACE$[$MEMORY_REF$.mallocDeallocatedCount$NAMESPACE$]
//! endtextmacro

//try to make a new element if no freed element
//! textmacro MALLOC_ALLOCATE_NEW takes NAMESPACE, MEMORY_REF
    set $MEMORY_REF$ = $MEMORY_REF$.mallocIndex$NAMESPACE$
    set $MEMORY_REF$.mallocIndex$NAMESPACE$ = $MEMORY_REF$.mallocIndex$NAMESPACE$ + 1
//! endtextmacro

/*
MALLOC_DEALLOCATED takes NAMESPACE, MEMORY_REF
*/

//free an allocated element
//! textmacro MALLOC_DEALLOCATE takes NAMESPACE, MEMORY_REF
    set $MEMORY_REF$.mallocDeallocated$NAMESPACE$[$MEMORY_REF$.mallocDeallocatedCount$NAMESPACE$] = $MEMORY_REF$
    set $MEMORY_REF$.mallocDeallocatedCount$NAMESPACE$ = $MEMORY_REF$.mallocDeallocatedCount$NAMESPACE$ + 1
//! endtextmacro

/*
struct Test extends array
    //! runtextmacro MALLOC_FIELDS("")
    
    public static method allocate takes nothing returns thistype
        local thistype this
        //! runtextmacro MALLOC_ALLOCATE_FREED("", "this")
        else
            //! runtextmacro MALLOC_ALLOCATE_NEW("", "this")
        endif
        return this
    endmethod
    
    public method deallocate takes nothing returns nothing
        //! runtextmacro MALLOC_DEALLOCATE("", "this")
    endmethod
endstruct
*/

module MallocFields
    //! runtextmacro MALLOC_FIELDS("")
endmodule

module MallocAllocateFreed
    local thistype this
    //! runtextmacro MALLOC_ALLOCATE_FREED("", "this")
endmodule

module MallocAllocateNew
    else
        //! runtextmacro MALLOC_ALLOCATE_NEW("", "this")
endmodule

module MallocDeallocate
    //! runtextmacro MALLOC_DEALLOCATE("", "this")
endmodule

/*
struct Test extends array
    implement MallocFields
    
    public static method allocate takes nothing returns thistype
        implement MallocAllocateFreed
        implement MallocAllocateNew
        endif
        return this
    endmethod
    
    public method deallocate takes nothing returns nothing
        implement MallocDeallocate
    endmethod
endstruct
*/

module MallocStruct
    implement MallocFields
    
    public static method allocate takes nothing returns thistype
        implement MallocAllocateFreed
        implement MallocAllocateNew
        endif
        return this
    endmethod
    
    public method deallocate takes nothing returns nothing
        implement MallocDeallocate
    endmethod
endmodule

/*
struct Test extends array
    implement MallocStruct
endstruct
*/

DMalloc

globals
    boolean dNewMalloc = false
    integer dMallocAllocated
endglobals

/*
    D_MALLOC_FIELDS takes NAMESPACE
*/

//malloc
//! textmacro D_MALLOC_FIELDS takes NAMESPACE
    //refers to current index of malloc
    public static thistype dMallocIndex$NAMESPACE$ = 0
    //refers to the last deallocated element
    public static thistype dMallocDeallocated$NAMESPACE$ = 0
//! endtextmacro

//! textmacro D_MALLOC_ALLOCATE_S takes NAMESPACE, MEMORY_REF
    if $MEMORY_REF$.dMallocDeallocated$NAMESPACE$ != 0 then
        set $MEMORY_REF$ = $MEMORY_REF$.dMallocDeallocated$NAMESPACE$
        set $MEMORY_REF$.dMallocDeallocated$NAMESPACE$ = $MEMORY_REF$.dMallocDeallocated$NAMESPACE$.previous$NAMESPACE$
    else
        set $MEMORY_REF$.dMallocIndex$NAMESPACE$ = $MEMORY_REF$.dMallocIndex$NAMESPACE$ + 1
        set $MEMORY_REF$ = $MEMORY_REF$.dMallocIndex$NAMESPACE$
    endif
//! endtextmacro

//returns circular dequeue
//! textmacro D_MALLOC_ALLOCATE takes NAMESPACE, MEMORY_REF, COUNT
    if $MEMORY_REF$.dMallocDeallocated$NAMESPACE$ != 0 then
        set $MEMORY_REF$ = $MEMORY_REF$.dMallocDeallocated$NAMESPACE$
        set $COUNT$ = $COUNT$ - 1
        
        loop
            exitwhen $MEMORY_REF$.previous$NAMESPACE$ == 0 or $COUNT$ == 0
            set $MEMORY_REF$ = $MEMORY_REF$.previous$NAMESPACE$
            set $COUNT$ = $COUNT$ - 1
        endloop
        
        set $MEMORY_REF$.dMallocDeallocated$NAMESPACE$ = $MEMORY_REF$.previous$NAMESPACE$
        set dMallocAllocated = $MEMORY_REF$.dMallocDeallocated$NAMESPACE$
    else
        set $MEMORY_REF$ = 0
        set dMallocAllocated = 0
    endif
    
    if $COUNT$ != 0 then
        set $MEMORY_REF$.dMallocIndex$NAMESPACE$ = $MEMORY_REF$.dMallocIndex$NAMESPACE$ + 1
        
        if dMallocAllocated == 0 then
            set dMallocAllocated = $MEMORY_REF$.dMallocIndex$NAMESPACE$
        endif
        
        set $MEMORY_REF$.dMallocIndex$NAMESPACE$.next$NAMESPACE$ = $MEMORY_REF$
        set $MEMORY_REF$.previous$NAMESPACE$ = $MEMORY_REF$.dMallocIndex$NAMESPACE$
        
        set $COUNT$ = $COUNT$ - 1
        
        set dNewMalloc = true
    endif
    
    loop
        exitwhen $COUNT$ == 0
        set dMallocIndex$NAMESPACE$.previous$NAMESPACE$ = $MEMORY_REF$.dMallocIndex$NAMESPACE$+1
        set $MEMORY_REF$.dMallocIndex$NAMESPACE$ = $MEMORY_REF$.dMallocIndex$NAMESPACE$ + 1
        set $MEMORY_REF$.dMallocIndex$NAMESPACE$.next$NAMESPACE$ = $MEMORY_REF$.dMallocIndex$NAMESPACE$ - 1
        
        set $COUNT$ = $COUNT$ - 1
    endloop
    
    if dNewMalloc then
        set $MEMORY_REF$ = $MEMORY_REF$.dMallocIndex$NAMESPACE$
        set dNewMalloc = false
    endif
    
    set $MEMORY_REF$.previous$NAMESPACE$ = dMallocAllocated
    
    set dMallocAllocated = $MEMORY_REF$
    set $MEMORY_REF$ = dMallocAllocated
    
    set $MEMORY_REF$.next$NAMESPACE$ = dMallocAllocated
//! endtextmacro

/*
MALLOC_DEALLOCATED takes NAMESPACE, MEMORY_REF
*/

//free an allocated element
//! textmacro D_MALLOC_DEALLOCATE takes NAMESPACE, MEMORY_REF_1, MEMORY_REF_2
    set $MEMORY_REF_1$.previous$NAMESPACE$ = $MEMORY_REF_1$.dMallocDeallocated$NAMESPACE$
    set $MEMORY_REF_1$.dMallocDeallocated$NAMESPACE$.next$NAMESPACE$ = $MEMORY_REF_1$
    set $MEMORY_REF_2$.next$NAMESPACE$ = 0
    set $MEMORY_REF_1$.dMallocDeallocated$NAMESPACE$ = $MEMORY_REF_2$
//! endtextmacro

/*
struct Test extends array
    //! runtextmacro D_MALLOC_FIELDS("")
    
    public static method allocate takes nothing returns thistype
        local thistype this
        //! runtextmacro D_MALLOC_ALLOCATE_S("", "this")
        return this
    endmethod
    
    public static method allocateCount takes integer count returns thistype
        local thistype this
        //! runtextmacro D_MALLOC_ALLOCATE("", "this", "count")
        return this
    endmethod
    
    public static method deallocate takes thistype node1, thistype node2 returns nothing
        //! runtextmacro D_MALLOC_DEALLOCATE("", "node1", "node2")
    endmethod
endstruct
*/

module DMallocFields
    //! runtextmacro D_MALLOC_FIELDS("")
endmodule

module DMallocAllocateS
    local thistype this
    //! runtextmacro D_MALLOC_ALLOCATE_S("", "this")
endmodule

module DMallocAllocate
    local thistype this
    //! runtextmacro D_MALLOC_ALLOCATE("", "this", "count")
endmodule

module DMallocDeallocate
    //! runtextmacro D_MALLOC_DEALLOCATE("", "node1", "node2")
endmodule

/*
struct Test extends array
    implement DMallocFields
    
    public static method allocate takes nothing returns thistype
        implement DMallocAllocateS
        return this
    endmethod
    
    public static method allocateCount takes integer count returns thistype
        implement DMallocAllocate
        return this
    endmethod
    
    public static method deallocate takes thistype node1, thistype node2 returns nothing
        implement DMallocDeallocate
    endmethod
endstruct
*/

module DMallocStruct
    implement DMallocFields
    
    public static method allocate takes nothing returns thistype
        implement DMallocAllocateS
        return this
    endmethod
    
    public static method allocateCount takes integer count returns thistype
        implement DMallocAllocate
        return this
    endmethod
    
    public static method deallocate takes thistype node1, thistype node2 returns nothing
        implement DMallocDeallocate
    endmethod
endmodule

/*
struct Test extends array
    implement DMallocStruct
    
    implement DequeueFields
endstruct
*/

Stack

//memory for stack
//! textmacro STACK_FIELDS takes NAMESPACE
    public thistype next$NAMESPACE$
//! endtextmacro

//move node1 through node2 to in front of node3
//! textmacro STACK_MOVE takes NAMESPACE, NODE1, NODE2, NODE3
    set $NODE2$.next$NAMESPACE$ = $NODE3$.next$NAMESPACE$
    set $NODE3$.next$NAMESPACE$ = $NODE1$
//! endtextmacro

//! textmacro STACK_LINK takes NAMESPACE, NODE1, NODE2
    set $NODE1$.next$NAMESPACE$ = $NODE2$
//! endtextmacro

/*
struct Test extends array
    //! runtextmacro MALLOC_FIELDS("")
    //! runtextmacro STACK_FIELDS("")
    
    public method push takes thistype node returns nothing
        //! runtextmacro STACK_MOVE("", "node", "node", "this")
    endmethod
    
    public method pop takes nothing returns thistype
        local thistype node = next
        //! runtextmacro STACK_LINK("", "this", "node.next")
        
        return node
    endmethod
    
    //moves node1 through node2 to after node3
    public static method move takes thistype node1, thistype node2, thistype node3 returns nothing
        //! runtextmacro STACK_MOVE("", "node1", "node2", "node3")
    endmethod
    
    //links up node1 with node2
    public static method link takes thistype node1, thistype node2 returns nothing
        //! runtextmacro STACK_LINK("", "node1", "node2")
    endmethod
    
    //deallocates a range of nodes from node1 through node2
    public static method destroyRange takes thistype node1, thistype node2 returns nothing
        loop
            //! runtextmacro MALLOC_DEALLOCATE("", "node1")
            exitwhen node1 == node2
            set node1 = node1.next
        endloop
    endmethod
endstruct
*/

module StackFields
    //! runtextmacro STACK_FIELDS("")
endmodule

module StackPush
    //! runtextmacro STACK_MOVE("", "node", "node", "this")
endmodule

module StackPop
    local thistype node = next
    //! runtextmacro STACK_LINK("", "this", "node.next")
endmodule

module StackMove
    //! runtextmacro STACK_MOVE("", "node1", "node2", "node3")
endmodule

module StackLink
    //! runtextmacro STACK_LINK("", "node1", "node2")
endmodule

module StackDestroyRangeStart
    loop
        //! runtextmacro MALLOC_DEALLOCATE("", "node1")
endmodule

module StackDestroyRangeEnd
        exitwhen node1 == node2
        set node1 = node1.next
    endloop
endmodule

/*
struct Test extends array
    implement MallocStruct
    implement StackFields
    
    public method push takes thistype node returns nothing
        implement StackPush
    endmethod
    
    public method pop takes nothing returns thistype
        implement StackPop
        return node
    endmethod
    
    public static method move takes thistype node1, thistype node2, thistype node3 returns nothing
        implement StackMove
    endmethod
    
    public static method link takes thistype node1, thistype node2 returns nothing
        implement StackLink
    endmethod
    
    public static method destroyRange takes thistype node1, thistype node2 returns nothing
        implement StackDestroyRangeStart
        implement StackDestroyRangeEnd
    endmethod
endstruct
*/

module StackStruct
    implement MallocStruct
    implement StackFields
    
    public method push takes thistype node returns nothing
        implement StackPush
    endmethod
    
    public method pop takes nothing returns thistype
        implement StackPop
        return node
    endmethod
    
    public static method move takes thistype node1, thistype node2, thistype node3 returns nothing
        implement StackMove
    endmethod
    
    public static method link takes thistype node1, thistype node2 returns nothing
        implement StackLink
    endmethod
    
    public static method destroyRange takes thistype node1, thistype node2 returns nothing
        implement StackDestroyRangeStart
        implement StackDestroyRangeEnd
    endmethod
endmodule

/*
struct Test extends array
    implement StackStruct
endstruct
*/

Dequeue

//fields for temporary storage
module ListTempFields
    public static thistype nextTemp
    public static thistype previousTemp
endmodule

//dequeue fields
//! textmacro DEQUEUE_FIELDS takes NAMESPACE
    implement ListTempFields //temporary storage fields of thistype
    
    public thistype previous$NAMESPACE$ //<- previous | next ->
    public thistype next$NAMESPACE$ //<- previous | next ->
//! endtextmacro

//links up two nodes. Can be used for removing nodes or creating lists or moving nodes
//! textmacro DEQUEUE_LINK takes NAMESPACE, NODE_HEAD, NODE_REF_1, NODE_REF_2
    //this can result if head.next == head.previous, in cases where there is only one node
    //without doing this, this type of link would result in an infinite list in which the
    //node pointed to itself.
    
    //cases of 0, 0 are not dangerous
    if $NODE_REF_1$ == 0 or $NODE_REF_1$ != $NODE_REF_2$ then
        //if node ref 1 is null, link head.next to node ref 2
        if $NODE_REF_1$ == 0 then
            set $NODE_HEAD$.next$NAMESPACE$ = $NODE_REF_2$
        else //otherwise normal link
            set $NODE_REF_1$.next$NAMESPACE$ = $NODE_REF_2$
        endif
        
        //if node ref 2 is null, link head.previous to node ref 1
        if $NODE_REF_2$ == 0 then
            set $NODE_HEAD$.previous$NAMESPACE$  = $NODE_REF_1$
        else //otherwise normal link
            set $NODE_REF_2$.previous$NAMESPACE$ = $NODE_REF_1$
        endif
    endif
//! endtextmacro

//used for temporarily copying 2 nodes. Useful for swapping operations
//! textmacro DEQUEUE_TMP_COPY takes NODE_REF_1, NODE_REF_2
    set $NODE_REF_1$.previousTemp = $NODE_REF_1$
    set $NODE_REF_1$.nextTemp = $NODE_REF_2$
//! endtextmacro

//ini dequeue head
//! textmacro DEQUEUE_INI_HEAD takes NAMESPACE, HEAD
    set $HEAD$.previous$NAMESPACE$ = 0 //head.previous = 0
    set $HEAD$.next$NAMESPACE$ = 0 //head.next = 0
//! endtextmacro

/*
struct Test extends array
    //! runtextmacro MALLOC_FIELDS("")
    //! runtextmacro DEQUEUE_FIELDS("")
    
    //toList.move(args)
    public method move takes thistype node1, thistype node2, thistype toNode1, thistype toNode2 returns nothing
        //toNode1 <-> node1 <-> ...
        //! runtextmacro DEQUEUE_LINK("", "this", "toNode1", "node1")
        //... <-> node2 <-> toNode2
        //! runtextmacro DEQUEUE_LINK("", "this", "node2", "toNode2")
    endmethod
    
    //linking nodes allows for destruction, clearing, adding, moving, and swapping
    //the move operation is actually 2 links
    public method link takes thistype node1, thistype node2 returns nothing
        //node1 <-> node2
        //! runtextmacro DEQUEUE_LINK("", "this", "node1", "node2")
    endmethod
    
    //creates a head and sets it's next and previous to 0
    public static method create takes nothing returns thistype
        local thistype this
        
        //! runtextmacro MALLOC_ALLOCATE_FREED("", "this")
        else
            //! runtextmacro MALLOC_ALLOCATE_NEW("", "this")
        endif
        
        //! runtextmacro DEQUEUE_INI_HEAD("", "this")
        
        return this
    endmethod
    
    //deallocates a range of nodes
    public static method destroyRange takes thistype node1, thistype node2 returns nothing
        loop
            //! runtextmacro MALLOC_DEALLOCATE("", "node1")
            exitwhen node1 == node2
            set node1 = node1.next
        endloop
    endmethod
    
    //swap node1 and node2 part of head with toNode1 and toNode2 part of toHead
    public static method swap takes thistype head, thistype node1, thistype node2, thistype toHead, thistype toNode1, thistype toNode2 returns nothing
        //cpy node1_1.previous to previousTemp
        //cpy node1_2.next to nextTemp
        //! runtextmacro DEQUEUE_TMP_COPY("node1.previous", "node2.next")
        
        //node2_1.previous <-> node1_1 <-> node1_2 <-> node2_2.next
        //! runtextmacro DEQUEUE_LINK("", "toHead", "toNode1.previous.next", "node1")
        //! runtextmacro DEQUEUE_LINK("", "toHead", "node2", "toNode2.next.previous")
        
        //previousTemp <-> node2_1 <-> node2_2 <-> nextTemp
        //! runtextmacro DEQUEUE_LINK("", "head", "previousTemp", "toNode1")
        //! runtextmacro DEQUEUE_LINK("", "head", "toNode2", "nextTemp")
    endmethod
endstruct
*/

module DequeueFields
    //! runtextmacro DEQUEUE_FIELDS("")
endmodule

module DequeueMove
    //toNode1 <-> node1 <-> ...
    //! runtextmacro DEQUEUE_LINK("", "this", "toNode1", "node1")
    //... <-> node2 <-> toNode2
    //! runtextmacro DEQUEUE_LINK("", "this", "node2", "toNode2")
endmodule

module DequeueLink
    //node1 <-> node2
    //! runtextmacro DEQUEUE_LINK("", "this", "node1", "node2")
endmodule

module DequeueAllocateIni
    //! runtextmacro DEQUEUE_INI_HEAD("", "this")
endmodule

module DestroyRange
    //! runtextmacro D_MALLOC_DEALLOCATE("", "node1", "node2")
endmodule

module DequeueSwap
    //cpy node1_1.previous to previousTemp
    //cpy node1_2.next to nextTemp
    //! runtextmacro DEQUEUE_TMP_COPY("node1.previous", "node2.next")
    
    //node2_1.previous <-> node1_1 <-> node1_2 <-> node2_2.next
    //! runtextmacro DEQUEUE_LINK("", "toHead", "toNode1.previous.next", "node1")
    //! runtextmacro DEQUEUE_LINK("", "toHead", "node2", "toNode2.next.previous")
    
    //previousTemp <-> node2_1 <-> node2_2 <-> nextTemp
    //! runtextmacro DEQUEUE_LINK("", "head", "previousTemp", "toNode1")
    //! runtextmacro DEQUEUE_LINK("", "head", "toNode2", "nextTemp")
endmodule

/*
struct Test extends array
    implement MallocStruct
    implement DequeueFields
    
    public method link takes thistype node1, thistype node2 returns nothing
        implement DequeueLink
    endmethod
    
    public method move takes thistype node1, thistype node2, thistype toNode1, thistype toNode2 returns nothing
        implement DequeueMove
    endmethod
    
    public static method swap takes thistype head, thistype node1, thistype node2, thistype toHead, thistype toNode1, thistype toNode2 returns nothing
        implement DequeueSwap
    endmethod
    
    public static method create takes nothing returns thistype
        implement DequeueAllocateFreed
            //code to do when getting a freed index, one that's been previous used
        implement DequeueAllocateNew
            //what to do when getting a brand new index, never used
        implement DequeueAllocateIni
        
        //what to always do
        
        return this
    endmethod
    
    public static method destroyRange takes thistype node1, thistype node2 returns nothing
        implement DestroyRangeStart
        implement DestroyRangeEnd
    endmethod
endstruct
*/

module DequeueStruct
    implement DMallocStruct
    implement DequeueFields
    
    public method push takes thistype node returns nothing
        set .previous.next = node
        set node.previous = .previous
        set node.next = 0
        set .previous = node
        
        if .next == 0 then
            set .next = node
        endif
    endmethod
    
    public method pop takes nothing returns thistype
        local thistype node = .previous
        
        set .previous = node.previous
        set .previous.next = 0
        
        if .next == node then
            set .next = 0
        endif
        
        return node
    endmethod
    
    public method unshift takes thistype node returns nothing
        set .next.previous = node
        set node.next = .next
        set node.previous = 0
        set .next = node
        
        if .previous == 0 then
            set .previous = node
        endif
    endmethod
    
    public method shift takes nothing returns thistype
        local thistype node = .next
        
        set .next = node.next
        set .next.previous = 0
        
        if .previous == node then
            set .previous = 0
        endif
        
        return node
    endmethod
    
    public method link takes thistype node1, thistype node2 returns nothing
        implement DequeueLink
    endmethod
    
    public method move takes thistype node1, thistype node2, thistype toNode1, thistype toNode2 returns nothing
        implement DequeueMove
    endmethod
    
    public static method swap takes thistype head, thistype node1, thistype node2, thistype toHead, thistype toNode1, thistype toNode2 returns nothing
        implement DequeueSwap
    endmethod
    
    public static method create takes nothing returns thistype
        local thistype this
        
        //! runtextmacro D_MALLOC_ALLOCATE_S("", "this")
        
        implement DequeueAllocateIni
        
        return this
    endmethod
    
    public static method destroyRange takes thistype node1, thistype node2 returns nothing
        implement DestroyRange
    endmethod
endmodule

/*
struct Test extends array
    implement DequeueStruct
endstruct
*/

Coding With This Framework
Each portion of the framework has 3 layers that range in simplicity and power.
Layer 1- macro based and pretty hardcore
Layer 2- module based and semi hardcore
Layer 3- module based and very simple


Coding With Malloc

Spoiler

Layer 1-
-----------------------------------------------------------------------------------------------------
Malloc at layer 1 uses the allocate and deallocate methods to provide automatic memory allocation for structs that extend arrays.

public static method allocate takes nothing returns thistype
public method deallocate takes nothing returns nothing

The module containing everything is

module MallocStruct

To use it, simply make a struct that extends an array and implement the module

struct Test extends array
    implement MallocStruct
endstruct

And making instances is just like normal-

Test test = Test.allocate()
call test.deallocate()

Layer 2
-----------------------------------------------------------------------------------------------------

The stuff in layer 2 are macros geared to making the allocate and deallocate methods-

MallocFields
MallocAllocateFreed
MallocAllocateNew
MallocDeallocate

MallocFields simply implements the fields needed for malloc to work.
[ljass]implement MallocFields[/ljass]

MallocAllocateFreed attempts to get freed memory for malloc
MallocAllocateNew gets new memory for malloc

public static method allocate takes nothing returns thistype
    //declare locals

    implement MallocAllocateFreed
        //code to do when getting a freed index
    implement MallocAllocateNew
        //code to do when getting a new index
    endif

    //code to always do on allocation

    return this
endmethod

MallocDeallocate frees memory for malloc

public method deallocate takes nothing returns nothing
    //declare locals

    implement MallocDeallocate

    //code to always do on deallocation
endmethod

Layer 3
-----------------------------------------------------------------------------------------------------

//! textmacro MALLOC_FIELDS takes NAMESPACE
//! textmacro MALLOC_ALLOCATE_FREED takes NAMESPACE, MEMORY_REF
//! textmacro MALLOC_ALLOCATE_NEW takes NAMESPACE, MEMORY_REF
//! textmacro MALLOC_DEALLOCATE takes NAMESPACE, MEMORY_REF

NAMESPACE is much like a scope. With all portions of the framework, the collections and malloc styles may be declared in varying namespaces so that one struct may have a multitude of collections.

These operate much the same way as their corresponding modules on layer 2 but they have no variable declarations. Looking at the modules they are implemented in will give a great idea of how they operate.

[ljass]//! textmacro MALLOC_FIELDS takes NAMESPACE[/ljass]

module MallocFields
    //! runtextmacro MALLOC_FIELDS("")
endmodule

[ljass]//! textmacro MALLOC_ALLOCATE_FREED takes NAMESPACE, MEMORY_REF[/ljass]

module MallocAllocateFreed
     local thistype this
    //! runtextmacro MALLOC_ALLOCATE_FREED("", "this")
endmodule

[ljass]//! textmacro MALLOC_ALLOCATE_NEW takes NAMESPACE, MEMORY_REF[/ljass]

module MallocAllocateNew
    else
        //! runtextmacro MALLOC_ALLOCATE_NEW("", "this")
endmodule

[ljass]//! textmacro MALLOC_DEALLOCATE takes NAMESPACE, MEMORY_REF[/ljass]

module MallocDeallocate
    //! runtextmacro MALLOC_DEALLOCATE("", "this")
endmodule

And for a complete struct example-

struct Test extends array
    //! runtextmacro MALLOC_FIELDS("")
    
    public static method allocate takes nothing returns thistype
        local thistype this
        //! runtextmacro MALLOC_ALLOCATE_FREED("", "this")
        else
            //! runtextmacro MALLOC_ALLOCATE_NEW("", "this")
        endif
        return this
    endmethod
    
    public method deallocate takes nothing returns nothing
        //! runtextmacro MALLOC_DEALLOCATE("", "this")
    endmethod
endstruct

So why is an else required after
[ljass]//! textmacro MALLOC_ALLOCATE_FREED takes NAMESPACE, MEMORY_REF[/ljass]?

The reason is that MALLOC_ALLOCATE_FREED starts off with an if statement but has no endif or else

[ljass]if freed > 0 then[/ljass]

In essence it checks to see if there is any freed memory. If there is, it goes on to unfree it and store it in the variable you specify. The reason there is no else or endif is so that users can write code specifically for freed memory. Let's say 5 variables needed to be set whenever a brand new struct was instanced, but only 1 variable needed to be set when that struct got reused later on. This could very well happen when dealing with parallel collections or when permanently assigning a handle like a timer to a struct. Sometimes variables need to be set when the struct is used for the first time, sometimes others need to be set when a struct is reused, and sometimes stuff needs to be set every time.

Coding With DMalloc

Spoiler

DMalloc is a special type of memory allocation geared for dequeues.

Layer 1-
-----------------------------------------------------------------------------------------------------
The first layer of DMalloc is simply a module that contains 3 methods

[ljass]public static method allocate takes nothing returns thistype[/ljass]
Allocates a single node. Normal operation count per node (3).

[ljass]public static method allocateCount takes integer count returns thistype[/ljass]
Allocates a circular list of nodes. Performs around 4.5*x+12 give or take a few. Standard performs 7*x+2 (3+4 where 4 = links). This is better than standard allocate when dealing with between 4+ and 7+ nodes depending on the circumstances.

Essentially, if 10 nodes were to be allocated, the list might look like
10<->1<->2<->3<->4<->5<->6<->7<->8<->9<->10

Adding to a list might be

list.move(10.previous, 10, 0, 0)

[ljass]public static method deallocate takes thistype node1, thistype node2 returns nothing[/ljass]
Deallocates a range of nodes. Normal deallocation operations for a range of nodes are x*2 where x is the number of nodes between and including node1 and node2. The number of operations for this special deallocate is 4 regardless. This means that standard deallocation would perform 600 operations on 300 nodes where this one would perform 4.

list.deallocate(1, 10) //4 operations instead of 20

To use it, simply use the DMalloc module in accordance with a Dequeue or use the DequeueStruct as it auto implements DMalloc

struct Test extends array
    implement DequeueStruct
endstruct

Layer 2-
-----------------------------------------------------------------------------------------------------

Layer 3-
-----------------------------------------------------------------------------------------------------

Coding With Stack

Spoiler

Layer 1-
-----------------------------------------------------------------------------------------------------
The first layer of Stack is simply a module that contains 7 methods, 2 being from Malloc and 5 being from Stack
Malloc

public static method allocate takes nothing returns thistype
public method deallocate takes nothing returns nothing

Stack
[ljass]public method push takes thistype node returns nothing[/ljass]
Same as standard push

stack.push(node)

[ljass]public method pop takes nothing returns thistype[/ljass]
Same as standard pop but does not reset the pointer of the returned node.

node = stack.pop()

[ljass]public static method link takes thistype node1, thistype node2 returns nothing[/ljass]
Links two nodes together. Can be used for removing nodes, simple node link, or w/e.

Given 1, 2
link(1, 2)
1->2

[ljass]public static method move takes thistype node1, thistype node2, thistype node3 returns nothing[/ljass]
Moves node1 through node2 to after node3

Given 1->2->3->4->5->6->7->8->9
link(2, 6)
3->4->5,
1->2->6->7->8->9

move(3, 5, 9)
1->2->6->7->8->9->3->4->5

[ljass]public static method destroyRange takes thistype node1, thistype node2 returns nothing[/ljass]
Deallocates a range of nodes. Does not delink them!

Given 1->2->3->4->5->6->7

If you wanted to remove and deallocate nodes 3 through 5

link(2, 6)
3->4->5,
1->2->6->7

deallocate(3, 5)
1->2->6->7

In the background, there is still 3->4->5 as they are not delinked, so keep this in mind if a new node is allocated and for some reason it is linked up with a bundle of other nodes. Resetting a link to 0 if not linking it with something immediately is typically a good idea.

The module containing everything is

module StackStruct

To use it

struct Test extends array
    implement StackStruct
endstruct

Layer 2-
-----------------------------------------------------------------------------------------------------

Layer 3-
-----------------------------------------------------------------------------------------------------

Coding With Dequeue

Spoiler

0 is treated as null with dequeues. Using 0 is a great way to clear out the entire list or to add to the front/end.

Layer 1-
-----------------------------------------------------------------------------------------------------
The first layer of Dequeue is simply a module that contains 10 methods, 3 being from DMalloc and 9 being from Dequeue

DMalloc

public static method allocate takes nothing returns thistype
public static method allocateCount takes integer count returns thistype
public static method deallocate takes thistype node1, thistype node2 returns nothing

Dequeue
[ljass]public method push takes thistype node returns nothing[/ljass]
Standard push

[ljass]public method pop takes nothing returns thistype[/ljass]
Standard pop

[ljass]public method unshift takes thistype node returns nothing[/ljass]
Standard unshift (see Perl arrays)

[ljass]public method shift takes nothing returns thistype[/ljass]
Standard shift (see Perl arrays)

[ljass]public method link takes thistype node1, thistype node2 returns nothing[/ljass]
Links two nodes together. Can be used for removing nodes, adding nodes, or w/e.

//Given 1, 2
list.link(1, 2)
//1<->2

//Given 1
//link at front
list.link(1, list.next)
list.link(0, 1)

//or
list.link(list.previous, 1)
list.link(1, 0) //link at back
//or
list.link(0, 0) //clear entire list

Same Node Linkage

Linking a node to itself (excluding 0) will result in nothing happening. This is to ensure that infinitely linked lists do not occur.

This is a prime example

//given 1 and an empty list
//a single node
list.link(1, 0)
list.link(0, 1)

list.link(list.next, list.previous) //link 1 to 1

[ljass]public method move takes thistype node1, thistype node2, thistype toNode1, thistype toNode2 returns nothing[/ljass]
Moves node1 through node2 to between toNode1 and toNode2. The list used to call move is toList, or the list the nodes are moving to.

Given 1<->2<->3<->4<->5<->6, 7<->8<->9

list2.move(3, 5, 7, 9)

List 1
a. 1<->2->3<->4<->5<->9
b. 5<-6

List 2
7<->3<->4<->5<->9

Node 8
7<-8->9

This interesting scenario essentially removes 8 from the second list and totally screws up the first list.

A simple list.link(2, 6) could fix up the breaks in list1 and a deallocate(8) could fix up 8, but what if we wanted to move 8 into 3, 4, 5's old position?

list.move(8, 8, 2, 6)
1<->2<->8<->6
7<->3<->4<->5<->9

So what happened? 8 and 3, 4, 5 swapped positions. With 2 moves like this, a swap occurs.

[ljass]public static method swap takes thistype head, thistype node1, thistype node2, thistype toHead, thistype toNode1, thistype toNode2 returns nothing[/ljass]
Swap swaps node1 through node2 on head with toNode1 through toNode2 on toHead. Essentially 2 moves.

Given 1<->2<->3<->4<->5<->6<->7<->8<->9

swap(head, 2, 5, toHead, 6, 8)
1<->6<->7<->8<->2<->3<->4<->5<->9

[ljass]public static method create takes nothing returns thistype[/ljass]
Creates a node and sets it's next and previous to 0 so that it can be used as a head. The head node should never be manipulated or used, it's simply there to point to the dequeue. It's previous is the last node and it's next is the first node on the dequeue.

0<-head->0

When adding new nodes, the nodes are essentially added after and between the head by using 0 (null). They can also be added in between other nodes, like 1 and 5.

All dequeues must have a head.

The method returns the head.
[ljass]dequeue = Dequeue.create()[/ljass]

[ljass]public static method destroyRange takes thistype node1, thistype node2 returns nothing[/ljass]
Destroys a range of nodes. Does not delink the nodes, so removing them before deallocation is important. Can also be used to deallocate the head and tail nodes (destroying an entire list).

Given 1<->2<->3<->4<->5<->6<->7<->8<->9

list.link(2, 7)
1<->2<->7<->8<->9
2<-3<->4<->5<->6->7

Dequeue.destroyRange(3, 6)
1<->2<->7<->8<->9

The module containing everything is

module DequeuStruct

To use it

struct Test extends array
    implement DequeueStruct
endstruct

How to iterate through a dequeue
Iterating through a dequeue typically starts at the beginning of it or the end of it.

list.next is the first node
list.previous is the last node

Iteration ends when the node is 0.

Node node = list //start at list, just let the loop do the rest to save on 1 iteration
loop
    set node = node.next //move to next node
    exitwhen node == 0 //exit when node is null
    call DisplayTextToPlayer(GetLocalPlayer(), 0, 0, I2S(node))
endloop

Layer 2-
-----------------------------------------------------------------------------------------------------

Layer 3-
-----------------------------------------------------------------------------------------------------

 

[Jesus4Lyf]

Most of what you've said appears to be BS.

>It's about 6x slower than a plain hashtable.
How is it comparable?

Do not even try to tell me your ".next" method, the most used method in a list, is in any way faster than this.

You compared to a bunch of wc3c systems. Do I need to say why that's silly?

Graveyarded due to being slow and named "List Optimum Speed". If you prove me wrong by giving a "getNext" method that is faster or at least the same speed as the Linked List Module, I will ungraveyard (unless new reasons arise for this to remain graveyarded).

Spoiler

        public method next takes nothing returns integer
            set .listMethod = .currentIndex[this]
            if .listMethod == .finalIndex[this] then
                if .nextIndexQueueIndex > 0 then
                    set .nextIndexQueueIndex = .nextIndexQueueIndex - 1
                    set .currentIndex[this] = .nextIndexQueue[.nextIndexQueueIndex]
                else
                    set .currentIndex[this] = .nextIndexIndex
                    set .nextIndexIndex = .nextIndexIndex + 1
                endif
                set .lastIndex[.currentIndex[this]] = .listMethod
                set .nextIndex[.lastIndex[.currentIndex[this]]] = .currentIndex[this]
                set .finalIndex[this] = .currentIndex[this]
                set .size[this] = .size[this] + 1
            else
                set .lastIndex[.listMethod] = .listMethod
                set .currentIndex[this] = .nextIndex[.listMethod]
            endif
            return .currentIndex[this]
        endmethod

VS

        method getNext takes nothing returns thistype
            return this.next
        endmethod

 

[Nestharus]

I took out dynamic item creation -.-... just deleted all of it except for 2 lines =/=.

 

[Jesus4Lyf]

No need to get cut at me, when I see something called "Optimum Speed" that is slower than everything else, I graveyard it. Just make it live up to its name, or rename it. As the author, decide what is important - the speed or the functionality.

 

[Nestharus]

Ok...

.023 ms on a 2000 iteration for population. The fastest I've seen besides that is .027, and that didn't do everything this did.

Still trying to lower it more . I'm going for .018.


I'll test next to see if I got that any faster.

Yes, 2.0 was fast, but 3.0 is going to be even faster ^^

 

[Jesus4Lyf]

>It populates faster than everything else
Correct me if I'm wrong, but isn't that like saying "this timer system starts a timer faster than any other, and although it reads the attached data slower, it is therefore still the fastest timer system"?

Because for every time you store data, you typically want to use it more than once, and by iterating through it.

Examples (we need more):

• Attaching particles to a spell, to perform actions each period.
• Running creeps through a list of nodes for a set path.
• Firing triggers out of a list of triggers (think Event).
• Running a bunch of periodic functions (think T32).
• Checking to see if a unit is in a list of units (think custom unit groups).
• Displaying a message to all players in a list (think custom forces).
• For cycling through instances of a spell that is supposed to perform actions when any unit is damaged.

For all of these, I couldn't care less if it takes a nanosecond or two longer to add a node, all I care about is the interation speed.
(I understand that there are situations like, destroy all effects attached to a spell instance after x seconds, for which this may be faster. Faster yet is doing it yourself.)

Speed isn't everything. Perhaps functionality is worth more.

 

[Nestharus]

Fastest iteration possible is a simple next and previous and a check : \.

I mean, I might be able to get it faster, but I really doubt that.

Right now I'm trying to figure out a better idea for recycling to get the speed up more on population, joining, and so on.

For iteration, uhm.. I'll work at it ^_^.

 

[Jesus4Lyf]

>Fastest iteration possible is a simple next and previous and a check : \.
I linked you to an example that is the fastest - it inlines (no check). It is an array read. You don't need a check, just return a null struct (0) if it has no next/prev. Then you can [LJASS]loop[/LJASS] and [LJASS]exitwhen this==0[/LJASS]. :thup:

If you insist on having anything else in there (which is fine) simply choose a more appropriate name for your snippet, and let's ungraveyard this. There is no hope for this getting approved while it claims to be fast yet has the slowest iteration speed (as far as I'm concerned as a moderator). That is why this is in the graveyard.

>Right now I'm trying to figure out a better idea for recycling to get the speed up more on population, joining, and so on.

Not important...

>For iteration, uhm.. I'll work at it ^_^.
...until this is solved, or you don't market this as efficient.

 

[Nestharus]

I the iteration was well done =). Population was same speed as rest, but iteration was 3x faster than mine at .002 ms vrs .006 .

I'll try and figure out an implementation in this model. I want to keep to this model because I want to have the fast iteration and fast population =).

Mine is def #1 population, but def not #1 at iteration, and as you said, iteration is more important ; ).

 

[Jesus4Lyf]

        public method next takes nothing returns integer
            return .nextIndex
        endmethod

Better.

>Cycle Speed: .002 ms every 2000 iterations
>Average Speed of Other Lists: .006
Wtf? Benchmark systems individually or don't bother at all. We don't know what the hell those numbers are.

Ungraveyarded.

 

[Viikuna]

When benchmarking you should post your benchmarking test map, so people can complain about things you did wrong and stuff.

 

[Nestharus]

Oh, lol.

Yea, I did benchmark individually using stopwatch natives =P.

Actually, as for as population went, Romek's double ended queue was the second best by far and Romek's was a little bit better at third ^_^.

I'll put the benchmarking code up that I used : P.

Edit-
Trollvottel's was third, not Romek's : P, lol.

 

[Romek]

> Romek's double ended queue was the second best by far and Romek's was a little bit better at third ^_^.
Kewl. I beat myself.

 

[Nestharus]

Yup, lol. Good job Romek!! woo go go go ^^

I really meant Trollvottel's was third =P, haha : D.

Oh, and a look at exactly how the final API is ganna look like-

module List
    public static method new takes nothing returns List
    public method next takes nothing returns integer
    public method previous takes nothing returns integer
    public method push takes nothing returns integer
    public method unshift takes nothing returns integer
    public method pop takes nothing returns integer
    public method shift takes nothing returns integer
    public method remove takes thistype list returns nothing
    public method addPush takes thistype list returns integer
    public method addUnshift takes thistype list returns integer
    public method getFirst takes nothing returns integer
    public method getLast takes nothing returns integer
    public method clean takes nothing returns nothing
    
module RelateList
    public static method join takes List list1, List list2 returns List
    public method split takes integer index returns List

//! textmacro Iterate takes $name$, $type$
    public $type$ $name$
    public method count$name$ takes $type$ data returns integer
    public method purge$name$ takes $type$ data returns nothing
    public method has$name$ takes $type$ data returns boolean

There is no size because it'd only slow it down and no real need for size in my opinion. There's also no empty because a list is never empty O-o, it always has at least one element. You can also do hasNext to see if it has more than one element in it =P.

I tried to include all required methods and data for any list in the List Module, add practice join and split for the RelateList module, and practical iteration in the iteration macro. I split it into three so that you wouldn't have any extra code and could have exactly what you needed =).

Every method is self explanatory =). The parameters are self explanatory (you should know what they take) and the return is self explanatory (you should know what they return).

I'm not going to write any documentation on any of the methods. No need.

 

[Nestharus]

Collections 1.0 Pre-Release put up, the new face of List Optimum Speed in cJASS style

 

[TriggerHappy]

Didn't waedaar submit something called collections?

 

[Nestharus]

I've been working on Collections for a long time ; ), so I had already named it awhile ago. Collections is a suitable name as that's exactly what is is ; ). It's like an Evolved List Optimum Speed including a multitude of different types of basic collections.

I guess I could name it BasicCollections ^_^

 

[Nestharus]

Finished rewrite!! : D

 

[kingkingyyk3]

Any practical usage?

 

[Nestharus]

You tell me..

The collections framework has dynamic and indexed memory allocation and linked lists.

Dynamic Memory
===================================================================
Allocation:
thisMemory = (freedMemorySpaceSize > 0) ? freedMemorySpace[--freedMemorySpaceSize] : memory++

Deallocation:
freedMemorySpace[freedMemorySpaceSize++] = thisMemory

Indexed Memory
===================================================================
Indexed memory is used for indexed arrays. As they are arrays, each instance may only
have one single value of a single type.

List
===================================================================
Double linked list with two parents where the first parent represents the list

Example of code-
Remove (all, pop, etc, doesn't matter)

//! textmacro NODE_REMOVE takes NAMESPACE, NODE
    set $NODE$.$NAMESPACE$p__nodeNextIndex.$NAMESPACE$p__nodePreviousIndex = $NODE$.$NAMESPACE$p__nodePreviousIndex //node.next.previous = node.previous
    set $NODE$.$NAMESPACE$p__nodePreviousIndex.$NAMESPACE$p__nodeNextIndex = $NODE$.$NAMESPACE$p__nodeNextIndex //node.previous.next = node.next
//! endtextmacro

Push (push at node, push first, push last, etc, doesn't matter where)

//! textmacro NODE_PUSH takes NAMESPACE, NODE, TO_NODE
    set $NODE$.$NAMESPACE$p__nodeParentFirst = $TO_NODE$.$NAMESPACE$p__nodeParentFirst //node.list = to.list
    set $NODE$.$NAMESPACE$p__nodePreviousIndex = $TO_NODE$ //node.previous = to
    set $NODE$.$NAMESPACE$p__nodeNextIndex = $TO_NODE$.$NAMESPACE$p__nodeNextIndex //node.next = to.next
    set $TO_NODE$.$NAMESPACE$p__nodeNextIndex.$NAMESPACE$p__nodePreviousIndex = $NODE$ //to.next.previous = node
    set $TO_NODE$.$NAMESPACE$p__nodeNextIndex = $NODE$ //to.next = node
//! endtextmacro