GroupUtils

02-05-2009, 01:54 PM

GroupUtils Library

Background:
This is a simple library that includes a group stack for dynamic groups, a global group that can be used for enumerations, and a pair of TRUE/FALSE boolexprs for preventing the null boolexpr leak in enumerations backwards compatibility with old maps that use them. Since the 1.24c patch, the null boolexpr leak in enumerations no longer exists. It also implements Griffen's method of GroupRefresh, which makes this a nice, all-encompassing utility set standard for group handling. Lastly, this library has means to group units in an area of effect while considering collision, something the GroupEnumUnitsInRange native does not do.

Requirements:

None

Requirements (Optional):

xebasic, by Vexorian

Credits:

GroupRefresh, Captain Griffen

Code:

Library:

library GroupUtils initializer Init requires optional xebasic
//******************************************************************************
//* BY: Rising_Dusk
//* 
//* This library is a combination of several features relevant to groups. First
//* and foremost, it contains a group stack that you can access dynamic groups
//* from. It also provides means to refresh groups and clear any shadow
//* references within them. The included boolexprs are there for backwards
//* compatibility with maps that happen to use them. Since the 1.24c patch,
//* null boolexprs used in GroupEnumUnits* calls no longer leak, so there is no
//* performance gain to using the BOOLEXPR_TRUE constant.
//* 
//* Instead of creating/destroying groups, we have moved on to recycling them.
//* NewGroup pulls a group from the stack and ReleaseGroup adds it back. Always
//* remember to call ReleaseGroup on a group when you are done using it. If you
//* fail to do so enough times, the stack will overflow and no longer work.
//* 
//* GroupRefresh cleans a group of any shadow references which may be clogging
//* its hashtable. If you remove a unit from the game who is a member of a unit
//* group, it will 'effectively' remove the unit from the group, but leave a
//* shadow in its place. Calling GroupRefresh on a group will clean up any
//* shadow references that may exist within it. It is only worth doing this on
//* groups that you plan to have around for awhile.
//* 
//* Constants that can be used from the library:
//*     [group]    ENUM_GROUP      As you might expect, this group is good for
//*                                when you need a group just for enumeration.
//*     [boolexpr] BOOLEXPR_TRUE   This is a true boolexpr, which is important
//*                                because a 'null' boolexpr in enumeration
//*                                calls results in a leak. Use this instead.
//*     [boolexpr] BOOLEXPR_FALSE  This exists mostly for completeness.
//* 
//* This library also includes a simple implementation of a group enumeration
//* call that factors collision of units in a given area of effect. This is
//* particularly useful because GroupEnumUnitsInRange doesn't factor collision.
//* 
//* In your map, you can just replace all instances of GroupEnumUnitsInRange
//* with GroupEnumUnitsInArea with identical arguments and your spells will
//* consider all units colliding with the area of effect. After calling this
//* function as you would normally call GroupEnumUnitsInRange, you are free to
//* do anything with the group that you would normally do.
//* 
//* If you don't use xebasic in your map, you may edit the MAX_COLLISION_SIZE
//* variable below and the library will use that as the added radius to check.
//* If you use xebasic, however, the script will automatically use xe's
//* collision size variable.
//* 
//* You are also able to use GroupUnitsInArea. This function returns all units
//* within the area, no matter what they are, which can be convenient for those
//* instances where you actually want that.
//* 
//* Example usage:
//*     local group MyGroup = NewGroup()
//*     call GroupRefresh(MyGroup)
//*     call ReleaseGroup(MyGroup)
//*     call GroupEnumUnitsInArea(ENUM_GROUP, x, y, 350., BOOLEXPR_TRUE)
//*     call GroupUnitsInArea(ENUM_GROUP, x, y, 350.)
//* 
globals
    //If you don't have xebasic in your map, this value will be used instead.
    //This value corresponds to the max collision size of a unit in your map.
    private constant real    MAX_COLLISION_SIZE = 197.
    //If you are insane and don't care about any of the protection involved in
    //this library, but want this script to be really fast, set this to true.
    private constant boolean LESS_SAFETY        = false
endglobals

globals
    //* Constants that are available to the user
    group    ENUM_GROUP     = CreateGroup()
    boolexpr BOOLEXPR_TRUE  = null
    boolexpr BOOLEXPR_FALSE = null
endglobals

globals
    //* Hashtable for debug purposes
    private hashtable     ht     = InitHashtable()
    //* Temporary references for GroupRefresh
    private boolean       Flag   = false
    private group         Refr   = null
    //* Arrays and counter for the group stack
    private group   array Groups
    private integer       Count  = 0
    //* Variables for use with the GroupUnitsInArea function
    private real          X      = 0.
    private real          Y      = 0.
    private real          R      = 0.
    private hashtable     H      = InitHashtable()
endglobals

private function HookDestroyGroup takes group g returns nothing
    if g == ENUM_GROUP then
        call BJDebugMsg(SCOPE_PREFIX+"Warning: ENUM_GROUP destroyed")
    endif
endfunction

debug hook DestroyGroup HookDestroyGroup

private function AddEx takes nothing returns nothing
    if Flag then
        call GroupClear(Refr)
        set Flag = false
    endif
    call GroupAddUnit(Refr, GetEnumUnit())
endfunction
function GroupRefresh takes group g returns nothing
    set Flag = true
    set Refr = g
    call ForGroup(Refr, function AddEx)
    if Flag then
        call GroupClear(g)
    endif
endfunction

function NewGroup takes nothing returns group
    if Count == 0 then
        set Groups[0] = CreateGroup()
    else
        set Count = Count - 1
    endif
    static if not LESS_SAFETY then
        call SaveInteger(ht, 0, GetHandleId(Groups[Count]), 1)
    endif
    return Groups[Count]
endfunction
function ReleaseGroup takes group g returns boolean
    local integer id = GetHandleId(g)
    static if LESS_SAFETY then
        if g == null then
            debug call BJDebugMsg(SCOPE_PREFIX+"Error: Null groups cannot be released")
            return false
        elseif Count == 8191 then
            debug call BJDebugMsg(SCOPE_PREFIX+"Error: Max groups achieved, destroying group")
            call DestroyGroup(g)
            return false
        endif
    else
        if g == null then
            debug call BJDebugMsg(SCOPE_PREFIX+"Error: Null groups cannot be released")
            return false
        elseif not HaveSavedInteger(ht, 0, id) then
            debug call BJDebugMsg(SCOPE_PREFIX+"Error: Group not part of stack")
            return false
        elseif LoadInteger(ht, 0, id) == 2 then
            debug call BJDebugMsg(SCOPE_PREFIX+"Error: Groups cannot be multiply released")
            return false
        elseif Count == 8191 then
            debug call BJDebugMsg(SCOPE_PREFIX+"Error: Max groups achieved, destroying group")
            call DestroyGroup(g)
            return false
        endif
        call SaveInteger(ht, 0, id, 2)
    endif
    call GroupClear(g)
    set Groups[Count] = g
    set Count         = Count + 1
    return true
endfunction

private function Filter takes nothing returns boolean
    return IsUnitInRangeXY(GetFilterUnit(), X, Y, R)
endfunction

private function HookDestroyBoolExpr takes boolexpr b returns nothing
    local integer bid = GetHandleId(b)
    if HaveSavedHandle(H, 0, bid) then
        //Clear the saved boolexpr
        call DestroyBoolExpr(LoadBooleanExprHandle(H, 0, bid))
        call RemoveSavedHandle(H, 0, bid)
    endif
endfunction

hook DestroyBoolExpr HookDestroyBoolExpr

private constant function GetRadius takes real radius returns real
    static if LIBRARY_xebasic then
        return radius+XE_MAX_COLLISION_SIZE
    else
        return radius+MAX_COLLISION_SIZE
    endif
endfunction

function GroupEnumUnitsInArea takes group whichGroup, real x, real y, real radius, boolexpr filter returns nothing
    local real    prevX = X
    local real    prevY = Y
    local real    prevR = R
    local integer bid   = 0
    
    //Set variables to new values
    set X = x
    set Y = y
    set R = radius
    if filter == null then
        //Adjusts for null boolexprs passed to the function
        set filter = Condition(function Filter)
    else
        //Check for a saved boolexpr
        set bid = GetHandleId(filter) 
        if HaveSavedHandle(H, 0, bid) then
            //Set the filter to use to the saved one
            set filter = LoadBooleanExprHandle(H, 0, bid)
        else
            //Create a new And() boolexpr for this filter
            set filter = And(Condition(function Filter), filter)
            call SaveBooleanExprHandle(H, 0, bid, filter)
        endif
    endif
    //Enumerate, if they want to use the boolexpr, this lets them
    call GroupEnumUnitsInRange(whichGroup, x, y, GetRadius(radius), filter)
    //Give back original settings so nested enumerations work
    set X = prevX
    set Y = prevY
    set R = prevR
endfunction

function GroupUnitsInArea takes group whichGroup, real x, real y, real radius returns nothing
    local real prevX = X
    local real prevY = Y
    local real prevR = R
    
    //Set variables to new values
    set X = x
    set Y = y
    set R = radius
    //Enumerate
    call GroupEnumUnitsInRange(whichGroup, x, y, GetRadius(radius), Condition(function Filter))
    //Give back original settings so nested enumerations work
    set X = prevX
    set Y = prevY
    set R = prevR
endfunction

private function True takes nothing returns boolean
    return true
endfunction
private function False takes nothing returns boolean
    return false
endfunction
private function Init takes nothing returns nothing
    set BOOLEXPR_TRUE  = Condition(function True)
    set BOOLEXPR_FALSE = Condition(function False)
endfunction
endlibrary

Function List:
This library provides the following functions to the user.

function NewGroup takes nothing returns group
function ReleaseGroup takes group g returns boolean
function GroupRefresh takes group g returns nothing
function GroupEnumUnitsInArea takes group whichGroup, real x, real y, real radius, boolexpr filter returns nothing
function GroupUnitsInArea takes group whichGroup, real x, real y, real radius returns nothing

This library also provides the following global variables to the user.

group ENUM_GROUP
boolexpr BOOLEXPR_TRUE
boolexpr BOOLEXPR_FALSE

The reason why GroupRefresh exists is best explained by Griffen here. It is quoted below for the readers' convenience.

Quote:

Originally Posted by Captain Griffen

Units that are removed from the game or decay while part of a group remain in the hash table. They also appear to remain in the list (which can cause issues with FirstOfGroup loops).

Therefore, if units are not removed manually from the group before this happens, there is a minor leak, and the CPU cost of many group operations increases dramatically. Verification is in this thread here.

NB: This only applies to where a group has units in it for longer than an instant, and where those units may decay / be removed. Most uses of groups are not vulnerable to that (most uses you should be using a static group and a boolexpr these days - those are completely unaffected).

Fortunately, GroupClear solves the problem, enabling the creation of a function that can be called on a group and flushes out all of the shadow units in it. The cost is pretty much O(n), where n is the number of real units in the group (rather than shadows).

GroupRefresh does not affect the group in a noticeable way, aside from removing the shadow references in the hash table, which speeds up most operations (see the link above for further details). The only effect it will have on outputs is on FirstOfGroup, which can return null when it comes to a shadow reference in the list, even if there are real units after it. GroupRefresh clears those out, so makes FirstOfGroup act properly again.

More frequent calls of GroupRefresh will reduce CPU costs of most operations involving groups whose usage makes them vulnerable to this, but will incur a higher CPU cost of its own. Look at the benchmarks on the link above and decide for yourself what the best balance is.

Backwards Compatibility:
In the event that you used one of the libraries this has deprecated, the following backwards compatibility libraries have been provided for your convenience. Simply replace the old library with the respective library below and it will work fine.

GroupRefresh:

library GroupRefresh requires GroupUtils
endlibrary

CSSafety:

library CSSafety requires GroupUtils, TimerUtils
endlibrary

BoolexprUtils:

library BoolexprUtils requires GroupUtils
endlibrary

Thanks guys, hopefully this helps streamline group handling!

02-05-2009, 02:53 PM	#2
Seshiro	Hey Rising Dusk, That thing here is just the CS thing, if you'd looked into the TimerUtils thread, you had seen that there is the group stack :D Therefore i think that this is nearly useless ;) Greez

02-05-2009, 03:28 PM	#3
Vexorian	But the CS thing blows. Dusk, could you add a group cleaner like Griffen's it would make sense to make it GroupUtils a sort of standard if it had that. I think this also needs a double free protection, at least during debug mode. Using SCOPE_PREFIX like that is a little exaggerated.

02-05-2009, 04:11 PM

Rising_Dusk

Quote:

Originally Posted by Seshiro

That thing here is just the CS thing, if you'd looked into the TimerUtils thread, you had seen that there is the group stack :D
Therefore i think that this is nearly useless ;)

I'd never even noticed that before. After reading the TimerUtils thread, it appears that it was only for backwards compatibility and not actual usage.

Quote:

Originally Posted by Vexorian

Dusk, could you add a group cleaner like Griffen's it would make sense to make it GroupUtils a sort of standard if it had that. I think this also needs a double free protection, at least during debug mode.

Certainly. Hrm, Table is probably the most logical means for double free protection as far as I can see. Do you agree or..?

Quote:

Originally Posted by Vexorian

Using SCOPE_PREFIX like that is a little exaggerated.

Yeah, but I think it's a healthy habit to be in. :)
I can remove it if you'd prefer.

02-05-2009, 04:18 PM	#5
Vexorian	There should be a better way than table.

02-05-2009, 05:03 PM

Captain Griffen

Quote:

Originally Posted by Vexorian

Or just add GroupRefresh, a compatability library for backward compatabilty, and then be done with it (oh, and link to my thread for the background on why you need it, then GY that).

A standard would be nice.

02-05-2009, 05:08 PM

Rising_Dusk

Quote:

Originally Posted by Vexorian

There should be a better way than table.

Probably, I'll look into it.

Quote:

Originally Posted by Captain Griffen

I think the syntax for GroupRefresh is clean enough that a backwards compatibility library likely won't be necessary. I'll see what I can do, a standard for this thing would be big.

02-05-2009, 07:51 PM	#8
emjlr3	wasnt one of these included with cs_safety? (along with the timersafety bit)

02-05-2009, 08:03 PM	#9
Joker	So...are we supposed to call JASS: ForGroup() stuff with ENUM_GROUP? I'm confuzed.

02-05-2009, 08:21 PM

#10

Rising_Dusk

You could, if you don't need to hold the group for longer than an instant. NewGroup and ReleaseGroup only make sense when you need a group for longer than a given instant. ENUM_GROUP and any group obtained with NewGroup() will work in ForGroup() calls, though.

Quote:

Originally Posted by emjlr3

wasnt one of these included with cs_safety? (along with the timersafety bit)

Probably, but the CS is obsolete. Now we have xe, but some stanardized GroupUtils is still missing from the database. I'll work on this when I get home tonight.

02-05-2009, 08:46 PM

#11

Captain Griffen

Quote:

Originally Posted by Rising_Dusk

I think the syntax for GroupRefresh is clean enough that a backwards compatibility library likely won't be necessary. I'll see what I can do, a standard for this thing would be big.

JASS:

library GroupRefresh requires GroupUtils
endlibrary

And you could also have:

JASS:

library CSSafety requires GroupUtils, TimerUtils
endlibrary

02-05-2009, 09:59 PM	#12
Av3n	If this is GroupUtilities, I'm not saying that it is necessary, it would be nice to have a Enum function that checks units in range by collision. Just my opinion. -Av3n

02-05-2009, 10:16 PM	#13
Rising_Dusk	Such a function could be created and then require GroupUtils.

02-06-2009, 03:12 AM	#14
fX_	Well if groups are such hazard handles as timers and this is TimerUtils for groups and TimerUtils is like, essential, then this should be essential, too.

02-06-2009, 08:53 AM	#15
Captain Griffen	Except in 90% of cases of groups, you don't want to do this. In the other 9% of cases, you can use structs to recycle timers more efficiently.