[vJASS] Allocation and Links

MyPad · May 8, 2017

Code

Includes

How-to Use/Install

API

Allocation And Linked List library

JASS:

library AllocLink requires /*

    */ optional Table,  /*
    *       - By having this library, you can easily generate pseudo-variables that run on method
    *         operators, if you feel like running them.
    *
    */ AllocT,          /*
    *       - This is an allocator library that is now softcoded to allow up to 32766 for arrays.
    *         Since it requires a flag for such extended features, one must declare a library
    *         within the library to allow flag switching.
    *
    */ LinkedListT,     /*
    *       - This is a list ability with a minimal amount of methods introduced.
    *       - There are two versions for the linked lists, one is exclusively for the entire struct
    *         and the other is far more flexible.
    *
    *   AllocLink
    *       - This is a library that aims to join both allocation and linked lists as it was in the
    *         intention of previous libraries.
    *
    *       - This does not add any more features aside from being able to generate pseudo-variables
    *         at compile-time (through textmacros).
    *
    *   Textmacros:
    *       op_set(varName, anyName, returnType, tableType, encapsulation, nullValue)
    *           - This generates two method operators with the assigned name "varName",
    *             which returns "returnType". The "tableType" adds some abstraction in
    *             case of including struct types and not just the native types. The
    *             "encapsulation" determines if the method operators are to be seen inside
    *             the class or outside. The null value is the appropriate null value for
    *             the returnType.
    *
    *       op_read(varName, anyName, returnType, tableType, nullValue)
    *           - Fundamentally the same, but can be seen outside and only modified inside the
    *             class (struct).
    */
  
    module AllocLink
        implement AllocT
        implement DoubleLink
    endmodule
  
    module AllocLinkBundle
        implement AllocLink
    endmodule
  
    module AllocLinkBundleH
        implement AllocH
        implement DoubleLink
    endmodule
  
//! textmacro op_set takes T, T1, T2, T3, E, NaN
    static if LIBRARY_Table then
        private static Table $T1$ = 0
      
        $E$ method operator $T$ takes nothing returns $T2$
            if $T1$ == 0 then
                set $T1$ = Table.create()
            endif
            return $T1$.$T3$[this]
        endmethod
      
        $E$ method operator $T$= takes $T2$ new returns nothing
            if $T1$ == 0 then
                set $T1$ = Table.create()
            endif
            if not (new != $NaN$) then
                call $T1$.$T3$.remove(this)
            else
                set $T1$.$T3$[this] = new
            endif
        endmethod
    else
      
        //  ========================================================    //
        //  Textmacro op_set($T$, $T1$, $T2$, $T3$, $E$, $NaN$)         //
        //                                                              //
        //  Failed to implement the textmacro!                          //
        //  Reason: Missing library!                                    //
        //  Library: Table                                              //
        //  ========================================================    //
      
    endif
//! endtextmacro
  
//! textmacro op_read takes T, T1, T2, T3, NaN
    static if LIBRARY_Table then
        private static Table $T1$ = 0
      
        method operator $T$ takes nothing returns $T2$
            if $T1$ == 0 then
                set $T1$ = Table.create()
            endif
            return $T1$.$T3$[this]
        endmethod
      
        private method operator $T$= takes $T2$ new returns nothing
            if $T1$ == 0 then
                set $T1$ = Table.create()
            endif
            if not (new != $NaN$) then
                call $T1$.$T3$.remove(this)
            else
                set $T1$.$T3$[this] = new
            endif
        endmethod
    else
      
        //  ========================================================    //
        //  Textmacro op_read($T$, $T1$, $T2$, $T3$, $NaN$)             //
        //                                                              //
        //  Failed to implement the textmacro!                          //
        //  Reason: Missing library!                                    //
        //  Library: Table                                              //
        //  ========================================================    //
      
    endif
//! endtextmacro
  
endlibrary

library_once AllocationAndLinks requires AllocLink
endlibrary

Allocator library

JASS:

library AllocT requires /*

    */ optional MapVersion, /*
    *       -   Version control for the number of instances allocated.
    *       -   Very much a snippet in itself. If you like, you can declare it below
    *
    *
    */ optional Table,      /*  https://www.hiveworkshop.com/threads/snippet-new-table.188084/
    *       -   If found, the library generates an instance allocator with a maximum
    *           size of 2^31 - 1 (basically hashtables).
    *
    *       -   It also permits a textmacro (basically a generic) that generates a
    *           module with the same type of allocation for you.
    *
    *       AllocT
    *           - Edition by MyPad
    *
    *       What made me write it?
    *           - I thought of making this allocation library in anticipation of the future.
    *           - Due to using Wurst as well, I'm challenged to make a similarly-readable
    *             library dedicated to allocating.
    *
    *       What about allocation safety?
    *           - Using an algorithm that reduces variable count to just one, (two if adding
    *             a counter for number of instances currently existing), the library can
    *             recursively allocate and deallocate safely.
    *
    *           - If in debug mode, when allocating too many instances, the module will
    *             print an error message with the following information:
    *
    *               Struct Name: Instance allocation method exceeded safety limit (Method: method-name)
    *
    *               - Do note that the allocator will return -1 for this (debug mode).
    *                 In normal mode, the allocator will just crash the thread.
    *
    *           - If in debug mode, the deallocation method will display an error message
    *             with the following information:
    *
    *              Struct Name: Instance (this) was double-freed! (Method: method-name)
    **/
  
    //! novjass
        library MapVersion
            globals
                public constant boolean POST_128 = false
            endglobals
        endlibrary
    //! endnovjass
  
  
    module AllocT
        private thistype alloc
      
        method deallocate takes nothing returns nothing
            if this.alloc != 0 then
                debug call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 15, "|cffffcc00thistype|r: Instance (" + I2S(this) + ") was double-freed! (Method: deallocate)")
                return
            endif
          
            set this.alloc = thistype(0).alloc
            set thistype(0).alloc = this
        endmethod
      
        static method allocate takes nothing returns thistype
            local thistype this = thistype(0).alloc
          
            if this.alloc == 0 then
                static if MapVersion_POST_128 then
                    if integer(this) < 32767 then
                        set this = this + 1
                        set thistype(0).alloc = this
                        return this
                    else
                        debug call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 15, "|cffffcc00{thistype}|r: Exceeded safety limit 32766! (Method: allocate)")
                        debug return -1
                        set this = 1/0
                    endif
                else
                    if integer(this) < 8191 then
                        set this = this + 1
                        set thistype(0).alloc = this
                        return this
                    else
                        debug call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 15, "|cffffcc00{thistype}|r: Exceeded safety limit 8190! (Method: allocate)")
                        debug return -1
                        set this = 1/0
                    endif              
                endif
            else
                set thistype(0).alloc = this.alloc
                set this.alloc = 0
            endif          
            return this
        endmethod
    endmodule
  
//! textmacro AllocT takes T, K
    $K$ module AllocT_$T$
        private thistype $T$_alloc
      
        method $T$_deallocate takes nothing returns nothing
            if this.$T$_alloc != 0 then
                debug call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 15, "|cffffcc00thistype|r: Instance (" + I2S(this) + ") was double-freed! (Method: $T$_deallocate)")
                return
            endif
          
            set this.alloc = thistype(0).alloc
            set thistype(0).alloc = this
        endmethod
      
        static method $T$_allocate takes nothing returns thistype
            local thistype this = thistype(0).$T$_alloc
          
            if this.$T$_alloc == 0 then
                static if MapVersion_POST_128 then
                    if integer(this) < 32767 then
                        set this = this + 1
                        set thistype(0).$T$_alloc = this
                        return this
                    else
                        debug call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 15, "|cffffcc00{thistype}|r: Exceeded safety limit 32766! (Method: $T$_allocate)")
                        debug return -1
                        set this = 1/0
                    endif
                else
                    if integer(this) < 8191 then
                        set this = this + 1
                        set thistype(0).$T$_alloc = this
                        return this
                    else
                        debug call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 15, "|cffffcc00{thistype}|r: Exceeded safety limit 8190! (Method: $T$_allocate)")
                        debug return -1
                        set this = 1/0
                    endif              
                endif
            else
                set thistype(0).$T$_alloc = this.$T$_alloc
                set this.$T$_alloc = 0
            endif          
            return this
        endmethod
    endmodule
//! endtextmacro
  
    module AllocH
        static if LIBRARY_Table then
            private static Table Alloc
          
            method deallocate takes nothing returns nothing
                if Alloc.integer[this] != 0 then
                    debug call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 15, "|cffffcc00thistype[hashtable]|r: Instance (" + I2S(this) + ") was double-freed! (Method: deallocate)")
                    return
                endif
              
                set Alloc.integer[this] = Alloc.integer[0]
                set Alloc.integer[0] = this
            endmethod
          
            static method allocate takes nothing returns thistype
                local thistype this = Alloc.integer[0]

                if Alloc.integer[this] == 0 then
                    set this = this + 1
                    set Alloc.integer[0] = this
                else
                    set Alloc.integer[0] = Alloc.integer[this]
                    call Alloc.integer.remove(this)
                endif
                return this
            endmethod
        else
          
            //  =============================================================================================    //
            //  AllocH: Error! (Missing library)                                                                 //
            //  A key library is missing, which resulted in the failure of the implementation                    //
            //                                                                                                   //
            //  Missing Library: Table (See link in documentation)                                               //
            //  =============================================================================================    //
        endif
          
        private static method onInit takes nothing returns nothing
            static if LIBRARY_Table then
                set Alloc = Table.create()
            else
                debug call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 180, "|cffffcc00thistype[hashtable]|r: Cannot import the module! (AllocH)")
            endif
        endmethod
    endmodule

//! textmacro AllocH takes T, K
  
    $K$ module AllocH_$T$
        static if LIBRARY_Table then
            private static Table $T$_Alloc
      
            method $T$_deallocate takes nothing returns nothing
                if $T$_Alloc.integer[this] != 0 then
                    debug call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 15, "|cffffcc00thistype[hashtable]|r: Instance (" + I2S(this) + ") was double-freed! (Method: $T$_deallocate)")
                    return
                endif
              
                set $T$_Alloc.integer[this] = $T$_Alloc.integer[0]
                set $T$_Alloc.integer[0] = this
            endmethod
          
            static method $T$_allocate takes nothing returns thistype
                local thistype this = $T$_Alloc.integer[0]

                if $T$_Alloc.integer[this] == 0 then
                    set this = this + 1
                    set $T$_Alloc.integer[0] = this
                else
                    set $T$_Alloc.integer[0] = $T$_Alloc.integer[this]
                    call $T$_Alloc.integer.remove(this)
                endif
                return this
            endmethod
          
        else
      
            //  =============================================================================================    //
            //  AllocH_$T$: Error! (Missing library)                                                             //
            //  A key library is missing, which resulted in the failure of the implementation                    //
            //                                                                                                   //
            //  Missing Library: Table (See link in documentation)                                               //
            //  =============================================================================================    //
      
        endif
      
        private static method onInit takes nothing returns nothing
            static if LIBRARY_Table then
                set $T$_Alloc = Table.create()
            else
                debug call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 180, "|cffffcc00thistype[hashtable]|r: Cannot import the module! (AllocH_$T$)")
            endif
        endmethod
    endmodule
//! endtextmacro

endlibrary

Doubly-Linked List library

JASS:

library LinkedListT requires /*

    */ optional Table,   /*  https://www.hiveworkshop.com/threads/snippet-new-table.188084/
    *   -   If not found, the library resorts to using a hashtable. Hashtables are limited to 256
    *       in game.
    *
    */ optional AllocT,  /*
    *   -   As a manner of ordering, this library complements the LinkedListT library.
    *
    *   LinkedListT
    *   -   A simple library that converts classes into double-linked list classes.
    *   -   It can dynamically create new module objects to be imported in code,
    *           although not as powerful as generics.
    *
    *   Features:
    *       module DoubleLink
    *       <K> module DoubleLink_<T>
    *
    *       The second one, which can be generated at runtime, behaves very similarly
    *       to the ordinary DoubleLink. What sets them apart is the suffix at the end.
    *
    *   API:
    *       These modules expose the following methods:
    *           method insert(thistype that)
    *           method <T>_insert(thistype that)
    *               - Sets the next node of the current instance to request.
    *               - Adjusts the link accordingly
    *               - From 0 -> 1 to 0 -> 2 -> 1 (with 1 being that) or
    *               - From 0 -> 1 to 0 -> 1 -> 2 (with 0 being that)
    *
    *           method queue(thistype that)
    *           method <T>_queue(thistype that)
    *               - Queues an instance as its' namesake implies.
    *               - From 0 -> 1 to 0 -> 1 -> 2 (with 1 being that) or
    *               - From 0 -> 1 to 0 -> 2 -> 1 (with 0 being that)
    *
    *           method pop
    *           method <T>_pop
    *               - Unlinks an instance. Does not dereference it, though.
    *
    *   Implementation:
    *       DoubleLink
    *
    *       struct MyClass
    *           implement DoubleLink
    *
    *       DoubleLink_<T>
    *
    *       //! runtextmacro DLinkedListT("T", "K")
    *
    *       struct MyClass
    *           implement DoubleLink_<T>          
    */
  
    private struct TableCheck extends array
        static if not LIBRARY_Table then
            static constant hashtable HASH = InitHashtable()
          
            static method newTable takes nothing returns integer
                local thistype this = LoadInteger(HASH, 0, 0)
              
                set this = this + 1
                call SaveInteger(HASH, 0, 0, this)
              
                return this
            endmethod
        endif
    endstruct
  
    module DoubleLink
        static if LIBRARY_Table then
            private static Table Next = 0
            private static Table Prev = 0
            private static Table Head = 0
        else
            private static integer Next = 0
            private static integer Prev = 0
            private static integer Head = 0
        endif
      
        method operator next= takes thistype that returns nothing
            static if LIBRARY_Table then
                set Next.integer[this] = that
            else
                call SaveInteger(TableCheck.HASH, Next, this, that)
            endif
        endmethod

        method operator prev= takes thistype that returns nothing
            static if LIBRARY_Table then
                set Prev.integer[this] = that
            else
                call SaveInteger(TableCheck.HASH, Prev, this, that)
            endif
        endmethod
      
        method operator head= takes thistype that returns nothing
            static if LIBRARY_Table then
                set Head.integer[this] = that
            else
                call SaveInteger(TableCheck.HASH, Head, this, that)
            endif
        endmethod

        method operator next takes nothing returns thistype
            static if LIBRARY_Table then
                return Next.integer[this]
            else
                return LoadInteger(TableCheck.HASH, Next, this)
            endif
        endmethod
      
        method operator prev takes nothing returns thistype
            static if LIBRARY_Table then
                return Prev.integer[this]
            else
                return LoadInteger(TableCheck.HASH, Prev, this)
            endif
        endmethod
      
        method operator head takes nothing returns thistype
            static if LIBRARY_Table then
                return Head.integer[this]
            else
                return LoadInteger(TableCheck.HASH, Head, this)
            endif
        endmethod
      
        method insert takes thistype that returns nothing
            set this.next = that
            set this.prev = that.prev
            set that.prev.next = this
            set that.prev = this          
        endmethod
      
        method queue takes thistype that returns nothing
            set this.prev = that
            set this.next = that.next
            set that.next.prev = this
            set that.next = this
        endmethod
      
        method push takes nothing returns nothing
            call insert(0)
        endmethod
      
        method enqueue takes nothing returns nothing
            call queue(0)
        endmethod
      
        method pop takes nothing returns nothing
            set this.prev.next = this.next
            set this.next.prev = this.prev
            set this.head = 0
        endmethod
      
        private static method onInit takes nothing returns nothing
            static if LIBRARY_Table then
                set Next = Table.create()
                set Prev = Table.create()
                set Head = Table.create()
            else
                set Next = TableCheck.newTable()
                set Prev = TableCheck.newTable()
                set Head = TableCheck.newTable()
            endif
        endmethod
    endmodule
  
//! textmacro DLinkedListT takes T, K
    $K$ module DoubleLink_$T$
        static if LIBRARY_Table then
            private static Table Next = 0
            private static Table Prev = 0
            private static Table Head = 0
        else
            private static integer Next = 0
            private static integer Prev = 0
            private static integer Head = 0
        endif
      
        method operator $T$_next= takes thistype that returns nothing
            static if LIBRARY_Table then
                set Next.integer[this] = that
            else
                call SaveInteger(TableCheck.HASH, Next, this, that)
            endif
        endmethod

        method operator $T$_prev= takes thistype that returns nothing
            static if LIBRARY_Table then
                set Prev.integer[this] = that
            else
                call SaveInteger(TableCheck.HASH, Prev, this, that)
            endif
        endmethod
      
        method operator $T$_head= takes thistype that returns nothing
            static if LIBRARY_Table then
                set Head.integer[this] = that
            else
                call SaveInteger(TableCheck.HASH, Head, this, that)
            endif
        endmethod

        method operator $T$_next takes nothing returns thistype
            static if LIBRARY_Table then
                return Next.integer[this]
            else
                return LoadInteger(TableCheck.HASH, Next, this)
            endif
        endmethod
      
        method operator $T$_prev takes nothing returns thistype
            static if LIBRARY_Table then
                return Prev.integer[this]
            else
                return LoadInteger(TableCheck.HASH, Prev, this)
            endif
        endmethod
      
        method operator $T$_head takes nothing returns thistype
            static if LIBRARY_Table then
                return Head.integer[this]
            else
                return LoadInteger(TableCheck.HASH, Head, this)
            endif
        endmethod
      
        method $T$_insert takes thistype that returns nothing
            set this.$T$_next = that
            set this.$T$_prev = that.$T$_prev
            set that.$T$_prev.$T$_next = this
            set that.$T$_prev = this          
        endmethod
      
        method $T$_queue takes thistype that returns nothing
            set this.$T$_prev = that
            set this.$T$_next = that.$T$_next
            set that.$T$_next.$T$_prev = this
            set that.$T$_next = this
        endmethod
      
        method $T$_push takes nothing returns nothing
            call $T$_insert(0)
        endmethod
      
        method $T$_enqueue takes nothing returns nothing
            call $T$_queue(0)
        endmethod
      
        method $T$_pop takes nothing returns nothing
            set this.$T$_prev.$T$_next = this.$T$_next
            set this.$T$_next.$T$_prev = this.$T$_prev
        endmethod
      
        private static method onInit takes nothing returns nothing
            static if LIBRARY_Table then
                set Next = Table.create()
                set Prev = Table.create()
                set Head = Table.create()
            else
                set Next = TableCheck.newTable()
                set Prev = TableCheck.newTable()
                set Head = TableCheck.newTable()
            endif
        endmethod

        //  =====================================================   //
        //  Module DoubleLink_$T$ implemented successfully          //
        //                                                          //
        //  Implemented in class thistype                           //
        //  =====================================================   //
  
    endmodule
  
    //  ====================================================    //
    //  Module DoubleLink_$T$ created in library/scope          //
    //  Encapsulation type: $K$                                 //
    //  ====================================================    //
  
//! endtextmacro

endlibrary

Two allocation modules, one for arrays and another for hashtables.
A Circularly-linked double-linked list that allows traversal of points and eases linear searching (hashtable version only).

A textmacro (DLinkedListT) to ease generation of lists: (one for Tables and one for arrays)
Two more textmacros (AllocT and AllocH) for more allocation modules: (one for Tables and one for arrays)

This assumes that you have installed either the Jass NewGen Pack (for the wonderful JassHelper) or WEX.

Installation:

First, create two triggers and convert them to custom text.
Then, copy and paste the library/libraries above, and voila, you are done.

Usage:

Allocation:
Convert your struct from this:

JASS:

    struct WhichStruct
    ...

        static method create takes nothing returns thistype
            local thistype this = thistype.allocate()
            return this
        endmethod
    endstruct

to this:

JASS:

    struct WhichStruct extends array
        implement AllocT
        ...
        static method create takes nothing returns thistype
            local thistype this = thistype.allocate()
            return this
            // Or, you could just do this...
            // You can also declare an implicit static method.
            return thistype.allocate()
        endmethod
    endstruct

Linked-List:

I prefer calling it when creating an instance, but the rest's up to you

JASS:

        method destroy takes nothing returns nothing
            ...
            call pop()
            call deallocate()
        endmethod

        static method create takes nothing returns thistype
            local thistype this = allocate()
            call this.push()
            // Or
            call this.queue()
            return this
        endmethod

To get these features, all you have to do is implement the following module like this

JASS:

        implement DoubleLink  //or
        implement DoubleLink_<T>    // <T> represents whatever suffix you've provided

Created: June 27, 2017
Updated: March 22, 2018

(Note: The linked list is static)
The Linked List methods:

method pop takes nothing returns nothing
Removes a certain node from a list.

method insert takes thistype that returns nothing
Inserts an instance in between the instance that and its' previous instance that.prev.

method push takes nothing returns nothing
a wrapper method for insertion at head = 0

method queue takes thistype that returns nothing
Queues the instance towards a head instance that.

method enqueue takes nothing returns nothing
a wrapper method for queue at head = 0

static method remove takes nothing returns nothing
a wrapper static method for removal of first node at head = 0

static method eject takes nothing returns nothing
a wrapper static method for removal of last node at head = 0

The Allocation methods:

static method allocate takes nothing returns nothing, static method <T>_allocate takes nothing returns nothing
Need I explain here? Generates a unique index for the request.

method deallocate takes nothing returns nothing, method <T>_allocate takes nothing returns nothing
Deallocates a certain node. Has default double-free protection.

textmacros:

//! runtextmacro DLinkedListT(prefix, status)
A textmacro for generating a module for implementation that creates a prefix_next and prefix_prev member. The status field determines whether it is only restricted onto the library or scope or public to all.

//! runtextmacro AllocT(prefix, status), //! runtextmacro AllocH(prefix, status)
Generates allocator modules, one with arrays and the other with hashtables respectively.

Aniki · May 8, 2017

I personally find the underlying allocation scheme interesting because it doesn't need for the free-list's head pointer to start at 1 nor an extra instance-count variable, and a node.next's field doesn't need a different sentinel value of -1 (or something) to flag it as not part of the free-list, it can simply use 0 =).

I don't know why you haven't added double-free protection and instance limit (8190 for arrays), if only for debug mode, because that catches a lot of erros (for me at least) and it would be very easy to add.

The rest of the stuff seem like conveniences that I wouldn't care much about and some things are just weird:

JASS:

    //! textmacro FoG_start takes enumFunc, params
        call $enumFunc$(ENUM_GROUP, $params$)
        loop
            set enum_unit = FirstOfGroup(ENUM_GROUP)
            exitwhen enum_unit == null
    //! endtextmacro
    //! textmacro FoG_end
            call GroupRemoveUnit(ENUM_GROUP, enum_unit)
        endloop
    //! endtextmacro

    // we are trading clarity (easy to read code) for saving a bit of typing...
    // macros look nothing like normal [v]jass code
    //! runtextmacro Fog_start("GrounpEnumUnitsInRange", "some_x", "some_y", "radius", "null")
        call KillUnit( enum_unit)
    //! runtextmacro Fog_end

MyPad · May 9, 2017

Thanks for the comments. I will try to separate those textmacros though from the library itself.

~~I'll try to restate the textmacro for FoG_start though~~ Done!
Maybe I'll add some protection as well for debug mode.

Nestharus · May 20, 2017

Your allocation looks exactly like the allocation in Unique Id Allocation, which Ruk33 came up with.

JASS:

// allocate
       local thistype this = recycler[0]

       if (recycler[this] == 0) then
           set recycler[0] = this + 1
       else
           set recycler[0] = recycler[this]
       endif

// deallocate
        set recycler[this] = recycler[0]
        set recycler[0] = this

Reinventing the wheel Kappa

MyPad · May 20, 2017

Oh, didn't know that. I came up with the allocation scheme through trial and error, using notepad as my gateway of logic.

Aniki · May 20, 2017

Your allocation looks exactly like the allocation in Unique Id Allocation, which Ruk33 came up with.

Note that Ruk33's version requires setting the head pointer to 1 at initialization time:

JASS:

    /*
    *   initialization
    */
    private static method onInit takes nothing returns nothing
        set recycler[0] = 1
    endmethod

MyPad's version doesn't, so its an improvement in my opinion.

MyPad · May 21, 2017

Does anyone want to know how I got this allocation scheme to work? Here's how:

I excluded 0 from the list, effectively making it as my head and instance count at the same time.

So when I call allocate, the result would be something like this:

Pseudo-Code:

JASS:

allocate() -> int
{
    local thistype this = thistype(0).recCount
    // thistype(0).recCount is 0...
    if this.recCount == 0 then
        // If the node it's referencing is 0, then it means that there is nothing to recycle...
        this = this + 1
        thistype(0).recCount = this
        return this
    endif
    // There must be something to recycle, so I make the head point to the next recycled thing...
    thistype(0).recCount = this.recCount
    // Just in case it doesn't get allocated again.
    this.recCount = 0
    return this
}

deallocate()
{
    // Mostly the same process...
    this.recCount = thistype(0).recCount
    thistype(0).recCount = this
}

Nestharus · May 21, 2017

Hm.. your allocator leaks.

Suppose one value is remaining in your allocator. This value is 4. You have allocated everything else. You retrieve 4. You check for a next. There is no next value, so you now change 4 to 5 and store it in the recycler. Uh oh, you are returning the 5, not the 4! Thus you have leaked an instance =).

That is why you use a module initializer for this algorithm =P.

MyPad · May 21, 2017

You mean this scenario:

Code:

1,2,3,4,5

Remove:

4 - recCount[4] = recCount[0] {5}; recCount[0] = 4 (1,2,3,5)
3 - recCount[3] = recCount[0] {4}; recCount[0] = 3 (1,2,5)
2 - recCount[2] = recCount[0] {3}; recCount[0] = 2 (1,5)
1 - recCount[1] = recCount[0] {2}; recCount[0] = 1 (5)
5 - recCount[5] = recCount[0] {1}; recCount[0] = 5 ()

Allocate:

this = recCount[0] {5}

recCount[5] = 1; recCount[0] = recCount[5] {1}
recCount[5] = 0;

this = recCount[0] {1}

recCount[1] = 2; recCount[0] = recCount[1] {2}
recCount[1] = 0;

this = recCount[0] {2}

recCount[2] = 3; recCount[0] = recCount[2] {3}
recCount[2] = 0;

this = recCount[0] {3}

recCount[3] = 4; recCount[0] = recCount[3] {4}
recCount[3] = 0;

this = recCount[0] {4}

recCount[4] = 5; recCount[0] = recCount[4] {5}
recCount[4] = 0;

this = recCount[0] {5}

recCount[5] = 0; recCount[0] = recCount[0] + 1

or what other scenario do you mean?

Nestharus · May 21, 2017

Nevermind, I read your code wrong. You aren't throwing the next thing to be allocated into the stack. You're throwing the last thing that was allocated =).

edit
Do you mind if I tweak the Alloc resource slightly for this and add you to credits?

MyPad · Jun 5, 2017

Minor Update:

Added another module with the option to freely reallocate any instance from the freed-list.

MyPad · Jun 27, 2017

Minor Update:

Now supports Bribe's Table.
Added API

~Reserved for future updates.

AGD · Jul 11, 2017

I would suggest that you just require the Table library instead of having the user required to use your HashTable and an optional Table. It is more convenient for users to import 1 library vs. 1 or 2 libraries ; ). We also encourage submissions here to use from our already approved resources. If you really want to make Table optional, you can write the alternative codes in the main library instead together with static ifs.
As for the allocator, since you already wrote an equally working Alloc, I suggest just removing the optional Alloc since you can't be sure that the other Alloc have pros over yours (Sevion's for example).

For the linked list, a general insert and remove method for insertion and removal from anywhere in the list could be useful (currently, I'm confused what the insertNode method is for). Then you can just base off your push, pop, enqueue methods from the two like:

JASS:

method insert takes thistype node returns nothing
    local thistype next = this.next
    set node.prev = this
    set node.next = next
    set next.prev = node
    set this.next = node
endmethod
method remove takes nothing returns nothing
    set this.next.prev = this.prev
    set this.prev.next = this.next
    static if REMOVE_LINKS then
        //...
    endif
endmethod

//Push - insert element to the front of the list
static method push takes thistype node returns nothing
    call thistype(0).insert(node)
endmethod
//Pop - remove front element
static method pop takes nothing returns nothing
    call thistype(0).next.remove()
endmethod
//Enqueue - insert element to the back of the list
static method enqueue takes thistype node returns nothing
    call thistype(0).prev.insert(node)
endmethod
//Eject - Remove back element
static method eject takes nothing returns nothing
    call thistype(0).prev.remove()
endmethod

It provides necessary functionalities while keeping the code short.

Also, you should probably add to the docu that the linked list is static and not instantiated.

Btw, if you would submit your Alloc as a separate library, maybe we could make it replace Sevion's Alloc instead.

EDIT:
Pls provide API description for the linked list itself.

MyPad · Jul 11, 2017

Woah, I did not expect this to be moderated.
Very well, I shall submit my Allocation as a separate resource and make this a link to those instead.

AGD said:
I would suggest that you just require the Table library instead of having the user required to use your HashTable and an optional Table. It is more convenient for users to import 1 library vs. 1 or 2 libraries ; ). We also encourage submissions here to use from our already approved resources. If you really want to make Table optional, you can write the alternative codes in the main library instead together with static ifs.
As for the allocator, since you already wrote an equally working Alloc, I suggest just removing the optional Alloc since you can't be sure that the other Alloc have pros over yours (Sevion's for example).

For the linked list, a general insert and remove method for insertion and removal from anywhere in the list could be useful (currently, I'm confused what the insertNode method is for). Then you can just base off your push, pop, enqueue methods from the two like:

JASS:

method insert takes thistype node returns nothing local thistype next = this.next set node.prev = this set node.next = next set next.prev = node set this.next = node endmethod method remove takes nothing returns nothing set this.next.prev = this.prev set this.prev.next = this.next static if REMOVE_LINKS then //... endif endmethod //Push - insert element to the front of the list static method push takes thistype node returns nothing call thistype(0).insert(node) endmethod //Pop - remove front element static method pop takes nothing returns nothing call thistype(0).next.remove() endmethod //Enqueue - insert element to the back of the list static method enqueue takes thistype node returns nothing call thistype(0).prev.insert(node) endmethod //Eject - Remove back element static method eject takes nothing returns nothing call thistype(0).prev.remove() endmethod

It provides necessary functionalities while keeping the code short.

Also, you should probably add to the docu that the linked list is static and not instantiated.

Btw, if you would submit your Alloc as a separate library, maybe we could make it replace Sevion's Alloc instead.

EDIT:
Pls provide API description for the linked list itself.

Thanks for the message. I've implemented them in the next version.
I've removed the insertNode as it was a bit troublesome to understand.

It now requires either Table or Hashtable (an extension of Table) (which means you can settle with just one or two), but you cannot make AllocH and DoubleLinkH work if neither one of them is present.

IcemanBo · Oct 8, 2017

Please have one thread per resource.

MyPad · Oct 9, 2017

^^ Okay! Moving it out!

IcemanBo · Oct 24, 2017

Okay, waiting for it.

edit: It seems like good code, but at current state I won't properly review it. Ping me when things are changed.

[vJASS] Allocation and Links

Code

Includes

How-to Use/Install

API

Installation:

Usage:

Similar threads