- Joined
- Nov 7, 2014
- Messages
- 571
barray (b standing for balanced / binary) is an implementation of 1 based arrays (not 0, in my opinion 1 based arrays are "people friendly"
and 0 based are "machine friendly") that trades flexibility (total number of arrays and maximum array index) for speed; specifically
array reads (operator[]), should be close to jass array speeds (not hashtable's LoadInteger nor function call speeds).
The primary purpose is to be used as members of structs, without reducing the struct's maximum instance limit (vJass structs can
have "dumb" array members but they reduce the instance limit even when an instance's array member is not used (i.e its null,
or it's just using a fraction of it's total capacity).
The barray limitations are that at any give moment you can only have:
and this is where the balancing (barrays remember?) part comes in.
The user needs to "balance" the total number of arrays with the maximum element count of any of the arrays.
That would probably require careful tuning but the library tries to help the user with "helpful" error messages.
barrays should be adequate for systems that don't require a lot of storage, and for the rest there's Save|Store|Integer of course.
So here's the implementation (I guess it probably has a few bugs and/or quirks):
and 0 based are "machine friendly") that trades flexibility (total number of arrays and maximum array index) for speed; specifically
array reads (operator[]), should be close to jass array speeds (not hashtable's LoadInteger nor function call speeds).
The primary purpose is to be used as members of structs, without reducing the struct's maximum instance limit (vJass structs can
have "dumb" array members but they reduce the instance limit even when an instance's array member is not used (i.e its null,
or it's just using a fraction of it's total capacity).
JASS:
struct Foo
integer bar
endstruct
struct Baz
Barray foos // could be null
string qux
endstruct
...
local Baz baz
local Baz baz2
set baz = Baz.create()
set baz.foos = Barray.new()
call baz.foos.push(Foo.create())
// other baz instances might not use their .foos array at all
set baz2 = Baz.create()
set baz2.qux = "quux"
...The barray limitations are that at any give moment you can only have:
JASS:
1 array with 0 .. 8190 elements or
2 arrays with 0 .. 4095 elements or
4 arrays with 0 .. 2047 elements or
8 arrays with 0 .. 1023 elements or
16 arrays with 0 .. 511 elements or
32 arrays with 0 .. 255 elements or
64 arrays with 0 .. 127 elements or
128 arrays with 0 .. 63 elements or
256 arrays with 0 .. 31 elements or
512 arrays with 0.. 15 elements or
1024 arrays with 0 .. 7 elementsand this is where the balancing (barrays remember?) part comes in.
The user needs to "balance" the total number of arrays with the maximum element count of any of the arrays.
That would probably require careful tuning but the library tries to help the user with "helpful" error messages.
barrays should be adequate for systems that don't require a lot of storage, and for the rest there's Save|Store|Integer of course.
So here's the implementation (I guess it probably has a few bugs and/or quirks):
JASS:
library barray
globals
force barray_ef_force = CreateForce()
integer barray_ef_ba
integer array barray_soff
endglobals
function barray_execute_func takes code func returns nothing
call ForForce(barray_ef_force, func)
endfunction
function barray_starting_offset_init takes nothing returns nothing
local integer n
local integer first
local integer prev
local boolean odd = true
local integer c
local integer i
set barray_soff[1] = 1
set barray_soff[2] = 4096
set c = 2
set n = 2
loop
exitwhen n > 512
set first = 4096 / n
set i = 1
loop
exitwhen i > n
if odd then
set odd = not odd
set prev = first * i
set c = c + 1
set barray_soff[c] = prev
else
set odd = not odd
set c = c + 1
set barray_soff[c] = prev + 4096
endif
set i = i + 1
endloop
set n = n * 2
endloop
endfunction
function barray_init takes nothing returns nothing
call ForceAddPlayer(barray_ef_force, Player(15))
call barray_execute_func(function barray_starting_offset_init)
endfunction
module barray_asap
static method onInit takes nothing returns nothing
call barray_init()
endmethod
endmodule
struct barray_run_asap extends array
implement barray_asap
endstruct
function barray_max_index_for_count takes integer arrays_count returns integer
if arrays_count <= 1 then
return 8190
elseif arrays_count <= 2 then
return 4095
elseif arrays_count <= 4 then
return 2047
elseif arrays_count <= 8 then
return 1023
elseif arrays_count <= 16 then
return 511
elseif arrays_count <= 32 then
return 255
elseif arrays_count <= 64 then
return 127
elseif arrays_count <= 128 then
return 63
elseif arrays_count <= 256 then
return 31
elseif arrays_count <= 512 then
return 15
else // if arrays_count <= 1024 then
return 7
endif
endfunction
function barray_max_count_for_index takes integer index returns integer
if index <= 7 then
return 1024
elseif index <= 15 then
return 512
elseif index <= 31 then
return 256
elseif index <= 63 then
return 128
elseif index <= 127 then
return 64
elseif index <= 255 then
return 32
elseif index <= 511 then
return 16
elseif index <= 1023 then
return 8
elseif index <= 2047 then
return 4
elseif index <= 4095 then
return 2
else // if index <= 8190 then
return 1
endif
endfunction
module barray
static integer max_index = 8190
static integer arrays_count = 0
static integer max_arrays_count = 1024
static integer array bas // the underlying storage for all barrays
static integer node_head = 1
static integer array node_next
integer len
integer prev_max_count
integer max_count
static method error takes string msg returns nothing
static if DEBUG_MODE then
// the thistype substring will expand to the struct name even in strings
call BJDebugMsg("|cffFF0000[thistype] error: " + msg)
endif
endmethod
static method new takes nothing returns thistype
local thistype ba
if arrays_count >= max_arrays_count then
call error("could not create a thistype; reason: out of storage space")
return 0
endif
set arrays_count = arrays_count + 1
set max_index = barray_max_index_for_count(arrays_count)
set ba = node_head
set node_head = node_next[node_head]
if node_head == 0 then
set node_head = ba + 1
endif
set ba.len = 0
set ba.prev_max_count = max_arrays_count
set ba.max_count = max_arrays_count
set node_next[ba] = -1
return ba
endmethod
static method ef_clear takes nothing returns nothing
local thistype ba = barray_ef_ba
local integer i
set i = 1
loop
exitwhen i > max_index
set bas[ barray_soff[ba] + i - 1] = 0
set i = i + 1
endloop
endmethod
method clear takes nothing returns nothing
local integer ba = this
local integer i
// try not to "eat" too much from the op-limit
if max_index > 63 then
set barray_ef_ba = ba
call barray_execute_func(function thistype.ef_clear)
else
set i = 1
loop
exitwhen i > max_index
set bas[ barray_soff[ba] + i - 1] = 0
set i = i + 1
endloop
endif
endmethod
static method cnew takes nothing returns thistype
local thistype ba = new()
call ba.clear()
return ba
endmethod
method free takes nothing returns nothing
local thistype ba = this
if ba == 0 then
call error("unable to free a null thistype")
return
elseif node_next[ba] != -1 then
call error("double free on a thistype(" + I2S(ba) + ")")
return
endif
set arrays_count = arrays_count - 1
set max_index = barray_max_index_for_count(arrays_count)
if ba.max_count == max_arrays_count then
set max_arrays_count = ba.prev_max_count
endif
set node_next[ba] = node_head
set node_head = ba
endmethod
method operator[]= takes integer i, integer v returns nothing
local thistype ba = this
static if DEBUG_MODE then
if not (1 <= i and i <= max_index) then
call error("in operator[]=; index " + I2S(i) + " is out of bounds for thistype(" + I2S(ba) + "); max_index(" + I2S(max_index) + ")")
return
endif
set max_arrays_count = barray_max_count_for_index(i)
set ba.max_count = max_arrays_count
endif
if i > ba.len then
set ba.len = i
endif
set bas[ barray_soff[ba] + i - 1] = v
endmethod
method operator[] takes integer i returns integer
static if DEBUG_MODE then
if not (1 <= i and i <= max_index) then
call error("in operator[]; index " + I2S(i) + " is out of bounds for thistype(" + I2S(this) + "); max_index(" + I2S(max_index) + ")")
return 0
endif
endif
// hopefully get's inlined in non-debug mode
return bas[ barray_soff[this] + i - 1]
endmethod
method operator cap takes nothing returns integer
return max_index
endmethod
method push takes integer v returns integer
local thistype ba = this
if ba.len == max_index then
call error("in push for thistype(" + I2S(ba) + "); reason: thistype(" + I2S(ba) + ").len == max_index(" + I2S(max_index) + ")")
return 0
endif
set bas[barray_soff[ba] + ba.len] = v
set ba.len = ba.len + 1
return ba.len
endmethod
method pop takes nothing returns integer
local thistype ba = this
local integer result
if ba.len <= 0 then
call error("in pop for thistype(" + I2S(ba) + "); reason: thistype(" + I2S(ba) + ") is empty")
return 0
endif
set result = bas[barray_soff[ba] + ba.len - 1]
set ba.len = ba.len - 1
return result
endmethod
endmodule
endlibrary
JASS:
struct Barray extends array
implement barray
endstruct
