Jesus4Lyf
Good Idea™
- Reaction score
- 397
Faster Table
Requirements:
- Jass NewGen
Description:
Hey look, it's faster!
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 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.
//*
//***************************************************************
//=============================================================
globals
private constant integer MAX_INSTANCES=8190 //400000
//=========================================================
private gamecache gc
endglobals
//Hey: Don't instanciate other people's textmacros that you are not supposed to, thanks.
//! textmacro Table__make takes name, type, key
struct $name$[MAX_INSTANCES]
private string base
static method create takes nothing returns $name$
local $name$ d=$name$.allocate()
set d.base=I2S(d)
return d
endmethod
method reset takes nothing returns nothing
call FlushStoredMission(gc,this.base)
endmethod
private method onDestroy takes nothing returns nothing
call FlushStoredMission(gc,this.base)
endmethod
method operator [] takes $type$ key returns integer
return GetStoredInteger(gc,this.base,$key$)
endmethod
method operator []= takes $type$ key, integer value returns nothing
call StoreInteger(gc,this.base,$key$, value)
endmethod
method flush takes $type$ key returns nothing
call FlushStoredInteger(gc,this.base,$key$)
endmethod
method exists takes $type$ key returns boolean
return HaveStoredInteger(gc,this.base,$key$)
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))" )
//=============================================================
// initialize it all.
//
private function init takes nothing returns nothing
call FlushGameCache(InitGameCache("libtable.gc"))
set gc=InitGameCache("libtable.gc")
endfunction
endlibraryTable-X, my successful attempt at not using gamecache, for those who want to see some interesting code. It virtually simulates gamecache, with the disadvantage being it doesn't save/load correctly, apparently. This might even be fixable.
JASS:
library Table
//***************************************************************
//*** Jesus4Lyf's ** TABLE-X ** Version 1.02 ***
//***************************************************************
//* Table object
//* ------------
//*
//* 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.
//*
//***************************************************************
//* This version of Table does not use GameCache.
//* Please note that all data attaching is messed up if you load
//* a saved game. Use normal Table if you need to load games.
///////////////
// Constants //
//===============================================================
globals
private constant integer MAX_INSTANCES=8100 //400000
private constant integer MAX_ATTACHMENTS=8190
// MAX_ATTACHMENTS is the maximum number of things being
// attached to in total + the number of tables in
// existance + 1, at any one time.
// If it is any higher than 8190, it is slower than normal Table.
///////////////////////////
// System Implementation //
//===============================================================
private constant integer MAX_STRINGID=MAX_ATTACHMENTS-1
private integer RandomData=MAX_ATTACHMENTS
endglobals
private keyword GTable
//////////////////////////////////////////////////////
// 2D DOUBLY LINKED-LIST HASHING TABLE SYNTAX CANDY //
/////////////////////////////////////////////////////////////
// Sounds fun? Think again. Use (for my own reference):
// d.delete()
// d.chainDelete()
// Data.getPointer() --> Data
// Data.getForRead(stringid) --> Data or 0
// Data.getForWrite(trackingPointer, stringid) --> Data
private struct Data[MAX_ATTACHMENTS] // Not really a struct, just syntax candy.
integer stringid
integer value
Data prev
Data next
Data drill // down
Data roll // counter-down (for unlinking)
/////////////
// GENERAL //
/////////////////////////////////////////////////////////
method wipe takes nothing returns nothing
set this.stringid=0
set this.value=0
set this.prev=0
set this.next=0
set this.drill=0
set this.roll=0
endmethod
method move takes Data targ returns Data
// Copy
set targ.stringid=this.stringid
set targ.value=this.value
set targ.prev=this.prev
set targ.next=this.next
set targ.drill=this.drill
set targ.roll=this.roll
// Fix pointers
set this.next.prev=targ
set this.prev.next=targ
set this.drill.roll=targ
set this.roll.drill=targ
// Clean up
call this.wipe()
// Done
return targ // Probably unneeded.
endmethod
method init takes Data prev, integer stringid returns nothing
set this.stringid=stringid
set prev.next.prev=this
set this.next=prev.next
set prev.next=this
set this.prev=prev
endmethod
static method getRandom takes nothing returns Data
local integer oldrandom=RandomData
set RandomData=RandomData-1
loop
if RandomData<1 then
set RandomData=MAX_ATTACHMENTS-1
endif
exitwhen Data(RandomData).stringid==0
if RandomData==oldrandom then
call BJDebugMsg("Table-X out of space. Increase MAX_ATTACHMENTS constant.")
endif
set RandomData=RandomData-1
endloop
return RandomData
endmethod
method delete takes nothing returns nothing
set this.next.prev=this.prev
set this.prev.next=this.next
set this.drill.roll=this.roll
set this.roll.drill=this.drill
if this.roll==0 and this.drill!=0 then
call this.drill.move(this)
else
call this.wipe()
endif
endmethod
method chainDelete takes nothing returns nothing
if this==0 then
return
endif
call this.next.chainDelete()
if this.roll==0 and this.drill!=0 then
call this.drill.move(this)
else
call this.wipe()
endif
endmethod
static method getPointer takes nothing returns Data
local Data d=Data.getRandom()
set d.stringid=-1
return d
endmethod
//////////////////////////
// STACKING ABSTRACTION //
/////////////////////////////////////////////////////////
method stack takes Data nextDown returns Data
set this.drill.roll=nextDown
set nextDown.drill=this.drill
set this.drill=nextDown
set nextDown.roll=this
return nextDown
endmethod
static method get takes integer stringid returns Data
local Data d=stringid-(stringid/MAX_STRINGID)*MAX_STRINGID+1
loop
if d.stringid==stringid then
return d // d.stringid=stringid
endif
exitwhen d.drill==0
set d=d.drill
endloop
return d // may be empty or not, but is not the stringid's data, so stack or init here.
endmethod
static method getForRead takes integer stringid returns Data
local Data d=stringid-(stringid/MAX_STRINGID)*MAX_STRINGID+1
loop
if d.stringid==stringid then
return d // d.stringid=stringid
endif
exitwhen d.drill==0
set d=d.drill
endloop
return 0
endmethod
static method getForWrite takes Data flushList, integer stringid returns Data
local Data d=stringid-(stringid/MAX_STRINGID)*MAX_STRINGID+1
loop
if d.stringid==stringid then
return d // d.stringid=stringid
endif
exitwhen d.drill==0
set d=d.drill
endloop
if d.stringid!=0 then
set d=d.stack(Data.getRandom()) // Get one stacked onto returned one.
// d has become the result of getRandom here.
endif
call d.init(flushList,stringid)
return d
endmethod
endstruct
private function StringID takes string s returns integer
return s
return 0
endfunction
private function H2I takes handle h returns integer
return h
return 0
endfunction
private struct GTable[MAX_INSTANCES]
// A "protected" keyword would've been really nice here.
// Don't play with "trackingPointer" or "base" in your map.
// Looking for ideas on how to protect them, still.
Data trackingPointer
string base
method reset takes nothing returns nothing
call this.trackingPointer.chainDelete()
set this.trackingPointer=Data.getPointer()
//call FlushStoredMission(gc,I2S(this))
endmethod
private method onDestroy takes nothing returns nothing
call this.trackingPointer.chainDelete()
//call FlushStoredMission(gc,I2S(this))
endmethod
endstruct
globals//locals
private integer sid
private Data dat
endglobals
//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
static method create takes nothing returns $name$
local $name$ d=$name$.allocate()
set d.trackingPointer=Data.getPointer()
set d.base=I2S(d)+"x"
return d
endmethod
method operator [] takes $type$ key returns integer
set sid=StringID(this.base+$key$)
set dat=sid-(sid/MAX_STRINGID)*MAX_STRINGID+1
loop
if dat.stringid==sid then
return dat.value // d.stringid=stringid
endif
exitwhen dat.drill==0
set dat=dat.drill
endloop
return 0
endmethod
method operator []= takes $type$ key, integer value returns nothing
set sid=StringID(this.base+$key$)
set dat=sid-(sid/MAX_STRINGID)*MAX_STRINGID+1
loop
exitwhen dat.stringid==sid
if dat.drill==0 then
if dat.stringid!=0 then
set dat=dat.stack(Data.getRandom()) // Get one stacked onto returned one.
// d has become the result of getRandom here.
endif
call dat.init(this.trackingPointer,sid)
return
endif
set dat=dat.drill
endloop
set dat.value=value
endmethod
method flush takes $type$ key returns nothing
local Data d=Data.getForRead(StringID(this.base+$key$))
if d!=0 then
call d.delete()
endif
endmethod
method exists takes $type$ key returns boolean
return Data.getForRead(StringID(this.base+$key$))!=0
endmethod
endstruct
//! endtextmacro
//! runtextmacro Table__make("Table","integer","I2S(key)")
//! runtextmacro Table__make("StringTable","string","key")
//! runtextmacro Table__make("HandleTable","handle","I2S(H2I(key))")
endlibraryUpdates:
- Version ??: Did an optimisation of Table and left it at that.
- Version 1.02: Did a hack-job optimisation of reading/writing. It's now faster than gamecache by about 7%. Meh.
- Version 1.01: Implemented hashing, and 2d linked lists for collisions and flushing.
- Version 1.00: BETA release/proof of concept.
