14 years
edited 8 years
Table is based on the philosophy that you can use one hashtable for your whole map. What it does is divide one hashtable into many different components, and each system in the map can have its own share of the hashtable. Taking advantage of parent keys and child keys to their fullest extent, the ability to have 1 hashtable for the whole map can now be realized.
I came up with the idea for this project after using Vexorian's Table and hitting the limits a number of times. All of those limitations have been fulfilled by this project:
You have access to all the hashtable API, so you can now save handles, booleans, reals, strings and integers, instead of just integers.
You can have up to 2 ^ 31 - 1 Table instances. Previously, you could have 400,000 if you set the constant appropriately, but that generates hundreds of lines of code. This means you don't ever have to worry about creating too many Tables, because you can never really have too many.
2-D array syntax is perfected and allows you to create things called TableArrays. The old method used the volatile StringHash, which easily bypasses the integer limit and starts saving into unpredictable places. This is dangerous when using a shared hashtable because you could overwrite someone else's data without even knowing it.
Table instances can save/load data from within module initializers. This didn't work before because the hashtable was initialized from a struct instead of from the globals block.
You can only have 256 hashtables at a time, so with 2 ^ 31 - 1 Table instances at your disposal and (that's right, I said "and", not "or") roughly 2 ^ 18 TableArray instances with array size 8192 (JASS max array size), you will find yourself with more storage options than you know what to do with.
If you take advantage of this system to its fullest, you will never need to call InitHashtable() again.
The basis of how it works is this: you often run into situations where you have no use for two keys (only a single key). Usually you just waste a key as 0 and run everything else through child-keys. This system (as well as Vexorian's Table) simply gives you a parent-key to use in a globally-shared hashtable. Just initialize an Table instance via [lcode=jass]Table.create()[/lcode].
But sometimes you need more than that, and both keys actually mean something to you. Usually the parent-key would be "this" from a struct and the child-keys are various other bits. A TableArray - an array of Tables - is a great way to achieve this. Instanciate a TableArray via [lcode=jass]TableArray[16][/lcode] for an array of Tables sized 16, or [lcode=jass]TableArray[0x2000][/lcode] for an array of Tables with the same size as a normal JASS array. The size can be very large if you want, but to be practical keep it smaller than a few million, because the total accumulated size of all your TableArrays must remain under 2 ** 31 - 1 (a little more than 2 billion) because that's the limit of how high integers can go.
If you're dealing with more randomly-accessed numbers or consistently very large indices in the parent-key field and couldn't previously accomplish it with a pre-sized TableArray, I have (on July 21, 2015) updated this to NewTable 4.0 where you can instantiate HashTables to do just that!
I now imagine this a completed project, so please let me know if there's more you'd like to see in the future and I'll take it into consideration.
Note the power of TableArray, how it splices the one hashtable into a many-dimensional array. This means you can have a multi-dimensional array (and more) per system.
I came up with the idea for this project after using Vexorian's Table and hitting the limits a number of times. All of those limitations have been fulfilled by this project:
You have access to all the hashtable API, so you can now save handles, booleans, reals, strings and integers, instead of just integers.
You can have up to 2 ^ 31 - 1 Table instances. Previously, you could have 400,000 if you set the constant appropriately, but that generates hundreds of lines of code. This means you don't ever have to worry about creating too many Tables, because you can never really have too many.
2-D array syntax is perfected and allows you to create things called TableArrays. The old method used the volatile StringHash, which easily bypasses the integer limit and starts saving into unpredictable places. This is dangerous when using a shared hashtable because you could overwrite someone else's data without even knowing it.
Table instances can save/load data from within module initializers. This didn't work before because the hashtable was initialized from a struct instead of from the globals block.
You can only have 256 hashtables at a time, so with 2 ^ 31 - 1 Table instances at your disposal and (that's right, I said "and", not "or") roughly 2 ^ 18 TableArray instances with array size 8192 (JASS max array size), you will find yourself with more storage options than you know what to do with.
If you take advantage of this system to its fullest, you will never need to call InitHashtable() again.
How it works
The basis of how it works is this: you often run into situations where you have no use for two keys (only a single key). Usually you just waste a key as 0 and run everything else through child-keys. This system (as well as Vexorian's Table) simply gives you a parent-key to use in a globally-shared hashtable. Just initialize an Table instance via [lcode=jass]Table.create()[/lcode].
But sometimes you need more than that, and both keys actually mean something to you. Usually the parent-key would be "this" from a struct and the child-keys are various other bits. A TableArray - an array of Tables - is a great way to achieve this. Instanciate a TableArray via [lcode=jass]TableArray[16][/lcode] for an array of Tables sized 16, or [lcode=jass]TableArray[0x2000][/lcode] for an array of Tables with the same size as a normal JASS array. The size can be very large if you want, but to be practical keep it smaller than a few million, because the total accumulated size of all your TableArrays must remain under 2 ** 31 - 1 (a little more than 2 billion) because that's the limit of how high integers can go.
If you're dealing with more randomly-accessed numbers or consistently very large indices in the parent-key field and couldn't previously accomplish it with a pre-sized TableArray, I have (on July 21, 2015) updated this to NewTable 4.0 where you can instantiate HashTables to do just that!
I now imagine this a completed project, so please let me know if there's more you'd like to see in the future and I'll take it into consideration.
Code (jass) Select
library Table /* made by Bribe, special thanks to Vexorian & Nestharus, version 4.1.0.1.
One map, one hashtable. Welcome to NewTable 4.1.0.1
This newest iteration of Table introduces the new HashTable struct.
You can now instantiate HashTables which enables the use of large
parent and large child keys, just like a standard hashtable. Previously,
the user would have to instantiate a Table to do this on their own which -
while doable - is something the user should not have to do if I can add it
to this resource myself (especially if they are inexperienced).
This library was originally called NewTable so it didn't conflict with
the API of Table by Vexorian. However, the damage is done and it's too
late to change the library name now. To help with damage control, I
have provided an extension library called TableBC, which bridges all
the functionality of Vexorian's Table except for 2-D string arrays &
the ".flush(integer)" method. I use ".flush()" to flush a child hash-
table, because I wanted the API in NewTable to reflect the API of real
hashtables (I thought this would be more intuitive).
API
------------
struct Table
| static method create takes nothing returns Table
| create a new Table
|
| method destroy takes nothing returns nothing
| destroy it
|
| method flush takes nothing returns nothing
| flush all stored values inside of it
|
| method remove takes integer key returns nothing
| remove the value at index "key"
|
| method operator []= takes integer key, $TYPE$ value returns nothing
| assign "value" to index "key"
|
| method operator [] takes integer key returns $TYPE$
| load the value at index "key"
|
| method has takes integer key returns boolean
| whether or not the key was assigned
|
----------------
struct TableArray
| static method operator [] takes integer array_size returns TableArray
| create a new array of Tables of size "array_size"
|
| method destroy takes nothing returns nothing
| destroy it
|
| method flush takes nothing returns nothing
| flush and destroy it
|
| method operator size takes nothing returns integer
| returns the size of the TableArray
|
| method operator [] takes integer key returns Table
| returns a Table accessible exclusively to index "key"
*/
globals
private integer less = 0 //Index generation for TableArrays (below 0).
private integer more = 8190 //Index generation for Tables.
//Configure it if you use more than 8190 "key" variables in your map (this will never happen though).
private hashtable ht = InitHashtable()
private key sizeK
private key listK
endglobals
private struct dex extends array
static method operator size takes nothing returns Table
return sizeK
endmethod
static method operator list takes nothing returns Table
return listK
endmethod
endstruct
private struct handles extends array
method has takes integer key returns boolean
return HaveSavedHandle(ht, this, key)
endmethod
method remove takes integer key returns nothing
call RemoveSavedHandle(ht, this, key)
endmethod
endstruct
private struct agents extends array
method operator []= takes integer key, agent value returns nothing
call SaveAgentHandle(ht, this, key, value)
endmethod
endstruct
//! textmacro NEW_ARRAY_BASIC takes SUPER, FUNC, TYPE
private struct $TYPE$s extends array
method operator [] takes integer key returns $TYPE$
return Load$FUNC$(ht, this, key)
endmethod
method operator []= takes integer key, $TYPE$ value returns nothing
call Save$FUNC$(ht, this, key, value)
endmethod
method has takes integer key returns boolean
return HaveSaved$SUPER$(ht, this, key)
endmethod
method remove takes integer key returns nothing
call RemoveSaved$SUPER$(ht, this, key)
endmethod
endstruct
private module $TYPE$m
method operator $TYPE$ takes nothing returns $TYPE$s
return this
endmethod
endmodule
//! endtextmacro
//! textmacro NEW_ARRAY takes FUNC, TYPE
private struct $TYPE$s extends array
method operator [] takes integer key returns $TYPE$
return Load$FUNC$Handle(ht, this, key)
endmethod
method operator []= takes integer key, $TYPE$ value returns nothing
call Save$FUNC$Handle(ht, this, key, value)
endmethod
method has takes integer key returns boolean
return HaveSavedHandle(ht, this, key)
endmethod
method remove takes integer key returns nothing
call RemoveSavedHandle(ht, this, key)
endmethod
endstruct
private module $TYPE$m
method operator $TYPE$ takes nothing returns $TYPE$s
return this
endmethod
endmodule
//! endtextmacro
//Run these textmacros to include the entire hashtable API as wrappers.
//Don't be intimidated by the number of macros - Vexorian's map optimizer is
//supposed to kill functions which inline (all of these functions inline).
//! runtextmacro NEW_ARRAY_BASIC("Real", "Real", "real")
//! runtextmacro NEW_ARRAY_BASIC("Boolean", "Boolean", "boolean")
//! runtextmacro NEW_ARRAY_BASIC("String", "Str", "string")
//New textmacro to allow table.integer[] syntax for compatibility with textmacros that might desire it.
//! runtextmacro NEW_ARRAY_BASIC("Integer", "Integer", "integer")
//! runtextmacro NEW_ARRAY("Player", "player")
//! runtextmacro NEW_ARRAY("Widget", "widget")
//! runtextmacro NEW_ARRAY("Destructable", "destructable")
//! runtextmacro NEW_ARRAY("Item", "item")
//! runtextmacro NEW_ARRAY("Unit", "unit")
//! runtextmacro NEW_ARRAY("Ability", "ability")
//! runtextmacro NEW_ARRAY("Timer", "timer")
//! runtextmacro NEW_ARRAY("Trigger", "trigger")
//! runtextmacro NEW_ARRAY("TriggerCondition", "triggercondition")
//! runtextmacro NEW_ARRAY("TriggerAction", "triggeraction")
//! runtextmacro NEW_ARRAY("TriggerEvent", "event")
//! runtextmacro NEW_ARRAY("Force", "force")
//! runtextmacro NEW_ARRAY("Group", "group")
//! runtextmacro NEW_ARRAY("Location", "location")
//! runtextmacro NEW_ARRAY("Rect", "rect")
//! runtextmacro NEW_ARRAY("BooleanExpr", "boolexpr")
//! runtextmacro NEW_ARRAY("Sound", "sound")
//! runtextmacro NEW_ARRAY("Effect", "effect")
//! runtextmacro NEW_ARRAY("UnitPool", "unitpool")
//! runtextmacro NEW_ARRAY("ItemPool", "itempool")
//! runtextmacro NEW_ARRAY("Quest", "quest")
//! runtextmacro NEW_ARRAY("QuestItem", "questitem")
//! runtextmacro NEW_ARRAY("DefeatCondition", "defeatcondition")
//! runtextmacro NEW_ARRAY("TimerDialog", "timerdialog")
//! runtextmacro NEW_ARRAY("Leaderboard", "leaderboard")
//! runtextmacro NEW_ARRAY("Multiboard", "multiboard")
//! runtextmacro NEW_ARRAY("MultiboardItem", "multiboarditem")
//! runtextmacro NEW_ARRAY("Trackable", "trackable")
//! runtextmacro NEW_ARRAY("Dialog", "dialog")
//! runtextmacro NEW_ARRAY("Button", "button")
//! runtextmacro NEW_ARRAY("TextTag", "texttag")
//! runtextmacro NEW_ARRAY("Lightning", "lightning")
//! runtextmacro NEW_ARRAY("Image", "image")
//! runtextmacro NEW_ARRAY("Ubersplat", "ubersplat")
//! runtextmacro NEW_ARRAY("Region", "region")
//! runtextmacro NEW_ARRAY("FogState", "fogstate")
//! runtextmacro NEW_ARRAY("FogModifier", "fogmodifier")
//! runtextmacro NEW_ARRAY("Hashtable", "hashtable")
struct Table extends array
// Implement modules for intuitive syntax (tb.handle; tb.unit; etc.)
implement realm
implement integerm
implement booleanm
implement stringm
implement playerm
implement widgetm
implement destructablem
implement itemm
implement unitm
implement abilitym
implement timerm
implement triggerm
implement triggerconditionm
implement triggeractionm
implement eventm
implement forcem
implement groupm
implement locationm
implement rectm
implement boolexprm
implement soundm
implement effectm
implement unitpoolm
implement itempoolm
implement questm
implement questitemm
implement defeatconditionm
implement timerdialogm
implement leaderboardm
implement multiboardm
implement multiboarditemm
implement trackablem
implement dialogm
implement buttonm
implement texttagm
implement lightningm
implement imagem
implement ubersplatm
implement regionm
implement fogstatem
implement fogmodifierm
implement hashtablem
method operator handle takes nothing returns handles
return this
endmethod
method operator agent takes nothing returns agents
return this
endmethod
//set this = tb[GetSpellAbilityId()]
method operator [] takes integer key returns Table
return LoadInteger(ht, this, key) //return this.integer[key]
endmethod
//set tb[389034] = 8192
method operator []= takes integer key, Table tb returns nothing
call SaveInteger(ht, this, key, tb) //set this.integer[key] = tb
endmethod
//set b = tb.has(2493223)
method has takes integer key returns boolean
return HaveSavedInteger(ht, this, key) //return this.integer.has(key)
endmethod
//call tb.remove(294080)
method remove takes integer key returns nothing
call RemoveSavedInteger(ht, this, key) //call this.integer.remove(key)
endmethod
//Remove all data from a Table instance
method flush takes nothing returns nothing
call FlushChildHashtable(ht, this)
endmethod
//local Table tb = Table.create()
static method create takes nothing returns Table
local Table this = dex.list[0]
if this == 0 then
set this = more + 1
set more = this
else
set dex.list[0] = dex.list[this]
call dex.list.remove(this) //Clear hashed memory
endif
debug set dex.list[this] = -1
return this
endmethod
// Removes all data from a Table instance and recycles its index.
//
// call tb.destroy()
//
method destroy takes nothing returns nothing
debug if dex.list[this] != -1 then
debug call BJDebugMsg("Table Error: Tried to double-free instance: " + I2S(this))
debug return
debug endif
call this.flush()
set dex.list[this] = dex.list[0]
set dex.list[0] = this
endmethod
//! runtextmacro optional TABLE_BC_METHODS()
endstruct
//! runtextmacro optional TABLE_BC_STRUCTS()
struct TableArray extends array
//Returns a new TableArray to do your bidding. Simply use:
//
// local TableArray ta = TableArray[array_size]
//
static method operator [] takes integer array_size returns TableArray
local Table tb = dex.size[array_size] //Get the unique recycle list for this array size
local TableArray this = tb[0] //The last-destroyed TableArray that had this array size
debug if array_size <= 0 then
debug call BJDebugMsg("TypeError: Invalid specified TableArray size: " + I2S(array_size))
debug return 0
debug endif
if this == 0 then
set this = less - array_size
set less = this
else
set tb[0] = tb[this] //Set the last destroyed to the last-last destroyed
call tb.remove(this) //Clear hashed memory
endif
set dex.size[this] = array_size //This remembers the array size
return this
endmethod
//Returns the size of the TableArray
method operator size takes nothing returns integer
return dex.size[this]
endmethod
//This magic method enables two-dimensional[array][syntax] for Tables,
//similar to the two-dimensional utility provided by hashtables them-
//selves.
//
//ta[integer a].unit[integer b] = unit u
//ta[integer a][integer c] = integer d
//
//Inline-friendly when not running in debug mode
//
method operator [] takes integer key returns Table
static if DEBUG_MODE then
local integer i = this.size
if i == 0 then
call BJDebugMsg("IndexError: Tried to get key from invalid TableArray instance: " + I2S(this))
return 0
elseif key < 0 or key >= i then
call BJDebugMsg("IndexError: Tried to get key [" + I2S(key) + "] from outside TableArray bounds: " + I2S(i))
return 0
endif
endif
return this + key
endmethod
//Destroys a TableArray without flushing it; I assume you call .flush()
//if you want it flushed too. This is a public method so that you don't
//have to loop through all TableArray indices to flush them if you don't
//need to (ie. if you were flushing all child-keys as you used them).
//
method destroy takes nothing returns nothing
local Table tb = dex.size[this.size]
debug if this.size == 0 then
debug call BJDebugMsg("TypeError: Tried to destroy an invalid TableArray: " + I2S(this))
debug return
debug endif
if tb == 0 then
//Create a Table to index recycled instances with their array size
set tb = Table.create()
set dex.size[this.size] = tb
endif
call dex.size.remove(this) //Clear the array size from hash memory
set tb[this] = tb[0]
set tb[0] = this
endmethod
private static Table tempTable
private static integer tempEnd
//Avoids hitting the op limit
private static method clean takes nothing returns nothing
local Table tb = .tempTable
local integer end = tb + 0x1000
if end < .tempEnd then
set .tempTable = end
call ForForce(bj_FORCE_PLAYER[0], function thistype.clean)
else
set end = .tempEnd
endif
loop
call tb.flush()
set tb = tb + 1
exitwhen tb == end
endloop
endmethod
//Flushes the TableArray and also destroys it. Doesn't get any more
//similar to the FlushParentHashtable native than this.
//
method flush takes nothing returns nothing
debug if this.size == 0 then
debug call BJDebugMsg("TypeError: Tried to flush an invalid TableArray instance: " + I2S(this))
debug return
debug endif
set .tempTable = this
set .tempEnd = this + this.size
call ForForce(bj_FORCE_PLAYER[0], function thistype.clean)
call this.destroy()
endmethod
endstruct
//NEW: Added in Table 4.0. A fairly simple struct but allows you to do more
//than that which was previously possible.
struct HashTable extends array
//Enables myHash[parentKey][childKey] syntax.
//Basically, it creates a Table in the place of the parent key if
//it didn't already get created earlier.
method operator [] takes integer index returns Table
local Table t = Table(this)[index]
if t == 0 then
set t = Table.create()
set Table(this)[index] = t //whoops! Forgot that line. I'm out of practice!
endif
return t
endmethod
//You need to call this on each parent key that you used if you
//intend to destroy the HashTable or simply no longer need that key.
method remove takes integer index returns nothing
local Table t = Table(this)[index]
if t != 0 then
call t.destroy()
call Table(this).remove(index)
endif
endmethod
//Added in version 4.1
method has takes integer index returns boolean
return Table(this).has(index)
endmethod
//HashTables are just fancy Table indices.
method destroy takes nothing returns nothing
call Table(this).destroy()
endmethod
//Like I said above...
static method create takes nothing returns thistype
return Table.create()
endmethod
endstruct
endlibrary
Example usage of HashTable
Code (jass) Select
local HashTable hash = HashTable.create() //create it
set hash['hfoo'][StringHash("poop")] = 66 //access large parent and child keys as needed
set hash['hfoo'].unit[99999] = GetTriggerUnit() //still works with multiple-type syntax so you still have the full hashtable API.
call hash.remove('hfoo') //This literally is calling FlushChildHashtable, and should be used when the parentkey and/or HashTable are to be retired
call hash.destroy() //DOES NOT FLUSH THE HASHTABLE. You must manually remove each parent key, first, otherwise you'll have a lot of leaked Tables.
Backwards Compatibility with Vexorian's Table
Code (jass) Select
library TableBC requires Table
/*
Backwards-compatibility add-on for scripts employing Vexorian's Table.
Added 31 July 2015: introduced static method operator [] and
static method flush2D for Table, HandleTable and StringTable. Now,
almost all of the Vexorian API has been replicated (minus the .flush paradox).
The Table library itself was unchanged to implement these
enhancements, so you need only update this library to experience the
improved syntax compatibility.
Disclaimer:
The following error does not occur with HandleTables & StringTables, only
with the standard, integer-based Table, so you do not need to make any
changes to StringTable/HandleTable-employing scripts.
The this.flush(key) method from the original Table cannot be parsed with
the new Table. For the scripts that use this method, they need to be up-
dated to use the more fitting this.remove(key) method.
Please don't try using StringTables/HandleTables with features exclusive
to the new Table as they will cause syntax errors. I do not have any plan
to endorse these types of Tables because delegation in JassHelper is not
advanced enough for three types of Tables without copying every single
method over again (as you can see this already generates plenty of code).
StringTable & HandleTable are wrappers for StringHash & GetHandleId, so
just type them out.
*/
//! textmacro TABLE_BC_METHODS
method reset takes nothing returns nothing
call this.flush()
endmethod
method exists takes integer key returns boolean
return this.has(key)
endmethod
static method operator [] takes string id returns Table
local integer index = StringHash(id)
local Table t = Table(thistype.typeid)[index]
if t == 0 then
set t = Table.create()
set Table(thistype.typeid)[index] = t
endif
return t
endmethod
static method flush2D takes string id returns nothing
local integer index = StringHash(id)
local Table t = Table(thistype.typeid)[index]
if t != 0 then
call t.destroy()
call Table(thistype.typeid).remove(index)
endif
endmethod
//! endtextmacro
//! textmacro TABLE_BC_STRUCTS
struct HandleTable extends array
static method operator [] takes string index returns thistype
return Table[index]
endmethod
static method flush2D takes string index returns nothing
call Table.flush2D(index)
endmethod
method operator [] takes handle key returns integer
return Table(this)[GetHandleId(key)]
endmethod
method operator []= takes handle key, integer value returns nothing
set Table(this)[GetHandleId(key)] = value
endmethod
method flush takes handle key returns nothing
call Table(this).remove(GetHandleId(key))
endmethod
method exists takes handle key returns boolean
return Table(this).has(GetHandleId(key))
endmethod
method reset takes nothing returns nothing
call Table(this).flush()
endmethod
method destroy takes nothing returns nothing
call Table(this).destroy()
endmethod
static method create takes nothing returns thistype
return Table.create()
endmethod
endstruct
struct StringTable extends array
static method operator [] takes string index returns thistype
return Table[index]
endmethod
static method flush2D takes string index returns nothing
call Table.flush2D(index)
endmethod
method operator [] takes string key returns integer
return Table(this)[StringHash(key)]
endmethod
method operator []= takes string key, integer value returns nothing
set Table(this)[StringHash(key)] = value
endmethod
method flush takes string key returns nothing
call Table(this).remove(StringHash(key))
endmethod
method exists takes string key returns boolean
return Table(this).has(StringHash(key))
endmethod
method reset takes nothing returns nothing
call Table(this).flush()
endmethod
method destroy takes nothing returns nothing
call Table(this).destroy()
endmethod
static method create takes nothing returns thistype
return Table.create()
endmethod
endstruct
//! endtextmacro
endlibrary
Example Usage of Table:
Code (jass) Select
struct table_demo extends array
private static method demo takes nothing returns nothing
//Create it:
local Table a = Table.create()
//Use it:
local boolean b = a.has(69)
set a[654321] = 'A'
set a[54321] = 'B'
set a.unit[12345] = GetTriggerUnit()
set a.unit[GetHandleId(a.unit[12345])] = GetSpellTargetUnit()
set a.real['ABCD'] = 3.14159
set a.integer[133] = 21
//remove entries
call a.handle.remove('ABCD')
call a.remove(54321)
//Flush/destroy it:
call a.destroy()
//Or, only flush it:
call a.flush()
endmethod
endstruct
Example Usage of TableArray:
Code (jass) Select
//Create it:
local TableArray da = TableArray[0x2000]
//Use it:
local thistype this = 0
loop
set this = this.next
exitwhen this == 0
set this.save = this.save + 1
set da[this].real[this.save * 3] = GetUnitX(this.unit)
set da[this].real[this.save * 3 + 1] = GetUnitY(this.unit)
set da[this].real[this.save * 3 + 2] = GetUnitFlyHeight(this.unit)
endloop
//Flush/destroy it:
call da.flush()
//Or, only destroy it (more efficient if you manage memory yourself)
call da.destroy()
Note the power of TableArray, how it splices the one hashtable into a many-dimensional array. This means you can have a multi-dimensional array (and more) per system.