Table 3.1

[Vexorian]

Table used to be just vJassified gamecache, now it is vJassified 'hashtable'. It is made to look like using an associative array or 'dictionary'. And the methods are coded so they are inline friendly, in other words when you use sometable[someint] and set sometable[someint]=something , you are actually using native gamecache usage. So, even though the looks understandable and self documenting, it is very close to the fastest way to use gamecache. Perhaps saving the contents of I2S in some variable before calling these functions thrice would be mildly faster, but probably not in a relevant way, there is also no good reason for doing multiple consecutive calls on the same index either.

Why gamecache? In all seriousness, speed is gamecache's only issue, Table has some advantages over customly made hash systems and CSData:
- No practical limits
- Very multi instanceable. You can have more than 1 table at the same time, in fact you may have 400000 tables at the same time, each being an indepent associative array. Oh, and its multi instancibility won't make it so you end up with 50 lines of code per instance.
- Cleaning all the contents of one Table is possibly O(1)

Why hashtable? Basically, hashtable keeps all those advantages for gamecache but it is also quite fast. Theory has it that it is just 2x times an array usage...

Some stuff:
* You may change maxinstances, a big value will remove the 8000 limit and just make allocation slower, allocation does not really matter too much or at all when you use Table correctly.
* 2d array syntax to have access to simulate "mission keys", just calls StringHash on them.

Table 3.1 (for patch 1.23b +):

library Table
//***************************************************************
//* Table object 3.1
//* ------------
//*
//*   set t=Table.create() - instanceates a new table object
//*   call t.destroy()     - destroys it
//*   t[1234567]           - Get value for key 1234567
//*                          (zero if not assigned previously)
//*   set t[12341]=32      - Assigning it.
//*   call t.flush(12341)  - Flushes the stored value, so it
//*                          doesn't use any more memory
//*   t.exists(32)         - Was key 32 assigned? Notice
//*                          that flush() unassigns values.
//*   call t.reset()       - Flushes the whole contents of the
//*                          Table.
//*
//*   call t.destroy()     - Does reset() and also recycles the id.
//*
//*   If you use HandleTable instead of Table, it is the same
//* but it uses handles as keys, the same with StringTable.
//*
//*  You can use Table on structs' onInit  if the struct is
//* placed in a library that requires Table or outside a library.
//*
//*  You can also do 2D array syntax if you want to touch
//* mission keys directly, however, since this is shared space
//* you may want to prefix your mission keys accordingly:
//*
//*  set Table["thisstring"][ 7 ] = 2
//*  set Table["thisstring"][ 5 ] = Table["thisstring"][7]
//*
//***************************************************************

//=============================================================
    globals
        private constant integer MAX_INSTANCES=8100 //400000
        //Feel free to change max instances if necessary, it will only affect allocation
        //speed which shouldn't matter that much.

    //=========================================================
        private hashtable ht = InitHashtable()
    endglobals

    private struct GTable[MAX_INSTANCES]

        method reset takes nothing returns nothing
            call FlushChildHashtable(ht, integer(this) )
        endmethod

        private method onDestroy takes nothing returns nothing
            call this.reset()
        endmethod

    endstruct

    //Hey: Don't instanciate other people's textmacros that you are not supposed to, thanks.
    //! textmacro Table__make takes name, type, key
    struct $name$ extends GTable

        method operator [] takes $type$ key returns integer
            return LoadInteger(ht, integer(this), $key$)
        endmethod

        method operator []= takes $type$ key, integer value returns nothing
            call SaveInteger(ht,  integer(this)  ,$key$, value)
        endmethod

        method flush takes $type$ key returns nothing
            call RemoveSavedInteger(ht, integer(this), $key$)
        endmethod

        method exists takes $type$ key returns boolean
            return HaveSavedInteger( ht,  integer(this)  ,$key$)
        endmethod

        static method flush2D takes string firstkey returns nothing
            call $name$(- StringHash(firstkey)).reset()
        endmethod

        static method operator [] takes string firstkey returns $name$
            return $name$(- StringHash(firstkey) )
        endmethod

    endstruct
    //! endtextmacro

    //! runtextmacro Table__make("Table","integer","key" )
    //! runtextmacro Table__make("StringTable","string", "StringHash(key)" )
    //! runtextmacro Table__make("HandleTable","handle","GetHandleId(key)" )

endlibrary

Table 2.0 (for wc3 version 1.23 or earlier):

library Table
//***************************************************************
//* Table object 2.0
//* ------------
//*
//*   set t=Table.create() - instanceates a new table object
//*   call t.destroy()     - destroys it
//*   t[1234567]           - Get value for key 1234567
//*                          (zero if not assigned previously)
//*   set t[12341]=32      - Assigning it.
//*   call t.flush(12341)  - Flushes the stored value, so it
//*                          doesn't use any more memory
//*   t.exists(32)         - Was key 32 assigned? Notice
//*                          that flush() unassigns values.
//*   call t.reset()       - Flushes the whole contents of the
//*                          Table.
//*
//*   call t.destroy()     - Does reset() and also recycles the id.
//*
//*   If you use HandleTable instead of Table, it is the same
//* but it uses handles as keys, the same with StringTable.
//*
//*  You can use Table on structs' onInit  if the struct is
//* placed in a library that requires Table or outside a library.
//*
//*  You can also do 2D array syntax if you want to touch
//* mission keys directly, however, since this is shared space
//* you may want to prefix your mission keys accordingly:
//*
//*  set Table["thisstring"][ 7 ] = 2
//*  set Table["thisstring"][ 5 ] = Table["thisstring"][7]
//*
//***************************************************************

//=============================================================
    globals
        private constant integer MAX_INSTANCES=8100 //400000

    //=========================================================
        private gamecache gc
    endglobals

    private keyword hack

    private struct GTable[MAX_INSTANCES]
        readonly string sthis

        static method create takes nothing returns GTable
         local GTable this = GTable.allocate()
             set this.sthis = SCOPE_PRIVATE + I2S(this)
         return this
        endmethod

        method reset takes nothing returns nothing
            call FlushStoredMission(gc,  this.sthis  )
        endmethod

        private method onDestroy takes nothing returns nothing
            call FlushStoredMission(gc,  this.sthis  )
        endmethod

        static method hack takes string s returns nothing
             set GTable(0).sthis  = s
        endmethod

        //=============================================================
        // initialize it all.
        //
        private static method onInit takes nothing returns nothing
            call FlushGameCache(InitGameCache("libtable.gc"))
            set gc=InitGameCache("libtable.gc")
        endmethod

    endstruct

    //Hey: Don't instanciate other people's textmacros that you are not supposed to, thanks.
    //! textmacro Table__make takes name, type, key
    struct $name$ extends GTable

        method operator [] takes $type$ key returns integer
            return GetStoredInteger(gc,  this.sthis  ,$key$)
        endmethod

        method operator []= takes $type$ key, integer value returns nothing
            call StoreInteger(gc,  this.sthis  ,$key$, value)
        endmethod

        method flush takes $type$ key returns nothing
            call FlushStoredInteger(gc,  this.sthis  ,$key$)
        endmethod

        method exists takes $type$ key returns boolean
            return HaveStoredInteger(gc,  this.sthis  ,$key$)
        endmethod

        static method flush2D takes string firstkey returns nothing
            call GTable.hack(firstkey) //inline friendly, I hope
            call $name$(0).reset()
        endmethod

        static method operator [] takes string firstkey returns $name$
            call GTable.hack(firstkey) //inline friendly, I hope
            return $name$(0)
        endmethod

    endstruct
    //! endtextmacro

    private function H2I takes handle h returns integer
        return h
        return 0
    endfunction
    
    //! runtextmacro Table__make("Table","integer","I2S(key)" )
    //! runtextmacro Table__make("StringTable","string","key" )
    //! runtextmacro Table__make("HandleTable","handle","I2S(H2I(key))" )

endlibrary

Changes in 2.0
* A 2D array syntax to handle mission keys, however, this comes with a price as in: function calls.
* The other aspects of Table have gotten a little faster as I2S is replaced with an array look up. this comes with a price as if you now change the instance limit to something larger than 8190, Table will become much slower. Just hope you don't ever, ever, need to do that.
* initializing is done using struct onInit instead of library initializer, this simply is to also allow other structs using onInit to use Tables, notice that as long as you use the Table in a library that requires Table or in a scope, its initializers are guaranteed to run after Table's.

Changes in 2.1
* Works in patch 1.23b.
* Will only work with patch 1.23b.

Thanks go to blizzard for listening in adding GetHandleId , without such native Table would have been killed.

Changes in 3.0
* Fuxing thanks to blizzard, the hashtable natives are great. Moved from gamecache to hashtable, the interface is the same, speed should have improved greatly, the static [] operator is faster. Basically, everything will get inlined to hashtable native usage now...

Changes in 3.1
* Can now be used in module initializers.

[Here-b-Trollz]

Hmm, minimal but also possible... what about this?

JASS:

library Table initializer init
//***************************************************************
//* Table object
//* ------------
//*
//*   set t=Table.create() - instanceates a new table object
//*   call t.destroy()     - destroys it
//*   t[1234567]           - Get value for index 1234567
//*                          (zero if not assigned previously)
//*   set t[12341]=32      - Assigning it.
//*   call t.flush(12341)  - Flushes the stored value, so it
//*                          doesn't use any more memory
//*   call t.reset()       - Flushes the whole contents of the
//*                          Table.
//*   call t.destroy()     - Does reset() and also recycles the id.
//*
//*
//***************************************************************

//=============================================================
    globals
        private constant integer MAX_INSTANCES=400000

    //=========================================================
        private gamecache gc
    endglobals

    struct Table[MAX_INSTANCES]
        private string index=I2S(this)
        method operator [] takes integer key returns integer
            return GetStoredInteger(gc,.index,I2S(key))
        endmethod

        method operator []= takes integer key, integer value returns nothing
            call StoreInteger(gc,.index,I2S(key), value)
        endmethod

        method flush takes integer key returns nothing
            call FlushStoredInteger(gc,.index,I2S(key))
        endmethod

        method reset takes nothing returns nothing
            call FlushStoredMission(gc,.index)
        endmethod

        private method onDestroy takes nothing returns nothing
            call FlushStoredMission(gc,.index)
        endmethod
    endstruct


    private function init takes nothing returns nothing
        call FlushGameCache(InitGameCache("libtable.gc"))
        set gc=InitGameCache("libtable.gc")
    endfunction
endlibrary

Seems to work for me, and it saves a function call. Although... i suppose it would depend on whether or not your table indexes go up past one array's worth.

[Vexorian]

That one actually replaces an I2S with a function call, try compiling it. If you replace MAX_INSTANCES with 8000 it becomes an array lookup, not sure if I2S is faster than an array lookup or viceversa.

[Here-b-Trollz]

Meh. I've never done any serious benchmarking. I would assume though that since I2S doesn't create a handle, it's relatively fast? (comparatively) If that's the case, it's prolly better just to keep I2S. Gah.

By the way it rules that we finally have a scripts section up

[moyack]

Just one question.... you could add a customizable gamecache filename...

JASS:

globals
        private constant integer MAX_INSTANCES=400000
        private constant string FILE_NAME = "MyGC" //<= the game cache filename used in your map...

    //=========================================================
        private gamecache gc
    endglobals

...

    private function init takes nothing returns nothing
        call FlushGameCache(InitGameCache(FILE_NAME))
        set gc=InitGameCache(FILE_NAME)
    endfunction

[Vexorian]

but what if the map already uses missionkeys and keys that could collide with Table's?

[cohadar]

Just a small technicality, this is not an associative array because key is always integer.
This is a simple dynamic array allocator.

[Vexorian]

this is not an associative array because key is always integer

It's relative, what I think of associative arrays is key->value, I prefer calling them associative arrays since they are not really arrays, there are no bounds for the key. You may even use negative key and things like that.

[cohadar]

Originally Posted by Wiki

From the perspective of a computer programmer, an associative array can be viewed as a generalization of an array. While a regular array maps an index to an arbitrary data type such as integers, other primitive types, or even objects, an associative array's keys can be arbitrarily typed.

So the fact you can use negative values does not make it associative because negative integer is still an integer, same type.
Your code represents a dynamic array.

Gamecache is associative array.

Technicality like I said, but misusing names is always dangerous in the long run.

[Vexorian]

wikipedia is wikipedia in that paragraph it is mentioning what a programmer thinks of associative arrays, not the definition. I really think these are closer to being associative than to normal arrays, it is also a good way to avoid people from thinking it is a good idea to use them in spite of dynamic arrays.

Originally Posted by wiki

An associative array (also associative container, map, mapping, hash, dictionary, finite map, lookup table, and in query-processing an index or index file) is an abstract data type composed of a collection of unique keys and a collection of values, where each key is associated with one value. The operation of finding the value associated with a key is called a lookup or indexing, and this is the most important operation supported by an associative array. The relationship between a key and its value is sometimes called a mapping or binding. For example, if the value associated with the key "bob" is 7, we say that our array maps "bob" to 7. Associative arrays are very closely related to the mathematical concept of a function with a finite domain. As a consequence, a common and important use of associative arrays is in memoization.

This reminded me I needed an exists() method. Updating.

[moyack]

Originally Posted by Vexorian

but what if the map already uses missionkeys and keys that could collide with Table's?

Still this option helps the user to set the proper name of the table if this situation happens.

[Vexorian]

Another thing is that the initializer must flush the gamecache.

[the-thingy]

Three questions about this:

1) Must I call t.reset before t.destroy? I don't really understand how GC works :P

2) Do I declare t like local Table t = Table.create ()? If not, how do I do it?

3) Let's say I have a trigger that stores an integer, then recalls it after 5 seconds. If that trigger runs twice within 5 seconds, will I have use a different key for set t[1234567] = GetRandomInt (1, 10) everytime the trigger fires, or will it get the correct value, even if the same key is used for both instances?

JASS:

function Test takes nothing returns nothing
//See Q2 for the declaration part :P
local integer rnd = GetRandomInt (1, 10)
set t[1] = rnd
call BJDebugMsg (I2S (t[1]))
call TriggerSleepAction (5.)
call BJDebugMsg (I2S (t[1]))

endfunction

If rnd = 5 on first instance, and rnd = 7 on second instance, would my result be (- representing one second of the wait)

5
7
-
-
-
-
-
5
7

[Here-b-Trollz]

JASS:

method reset takes nothing returns nothing
    call FlushStoredMission(gc,I2S(this))
endmethod

private method onDestroy takes nothing returns nothing
    call FlushStoredMission(gc,I2S(this))
endmethod

Strange... destroy and reset would appear to do the *exact* same thing. So, if you are removing the Timer object, just destroy it, but if you want to keep the object and just empty it out, use .reset()


Table is probably most useful as a global. But you can still use it as a local. In both cases, you create a new table with Table.create(), yes.


As for question three.... I don't think GetRandomInt() works the way you want it to...

[the-thingy]

As for question three.... I don't think GetRandomInt() works the way you want it to...

OK, ignoring the GetRandomInt part, what if you have an array of values, and each instance used the next value in the array (lets say, the value held in the array slot corresponds to the array's index i.e. myArray[0] = 0, myArray[1] = 1, etc)

If that was the case, would 0 and 1 be displayed if the trigger fired twice within the 5 second window?