Benchmarking Operations

///////////////////////////////////////////////////////
/// Strilanc's Handle Index Library
/// Last Updated: March 18, 2008
/// Version: Beta-2
///////////////////////////////////////////////////////
/// Description:
///  This library provides functions to create, destroy, and retrieve array indices
///  for handles (eg. units, locations, timers, etc). The library is easy to use
///  because it takes care of making sure the array indices don't collide, the same
///  handle doesn't have two associated indices, etc.
///
/// Explanation:
///  - The library is essentially a hash table with a very simple hash. A handle is
///  converted to a valid array index using H2I mod TABLE_SIZE. Collisions are
///  handled by probing.
///
/// Usage:
///  - Copy this trigger to your map
///  - Set the system settings just below this big comment block
///  - Create a handle index for any unit or whatever you want to work with using CreateHandleIndex
///  - Never create a handle index only if it doesn't exist; this interferes with other libraries
///  - Retrieve the handle index using GetHandleIndex
///  - Destroy the handle index when you're done with it using DestroyHandleIndex
///
/// Notes:
///  - Multiple libraries can use this library, even if they don't know about each other. This
///  works because when a handle index is created twice, it needs to be destroyed twice before
///  it is 'really' destroyed.
///  - Performance will drop if number of handles becomes large, due to probing.
///  - The constant HANDLE_INDEX_NOT_FOUND is returned when no handle index can be given.
///////////////////////////////////////////////////////
library HandleIndexLib initializer initHandleIndexLib
    globals
        //should the system show debug messages?
        private constant boolean SHOW_DEBUG_MESSAGES = true
    endglobals
    globals
        constant integer HANDLE_INDEX_NOT_FOUND = -1
        constant integer EMPTY_BUT_USED = -1
        private constant integer MAX_HANDLES = 6000
        private constant integer TABLE_SIZE = 8190

        private integer array tableValues
        private handle array tableHandles
        private integer array tableUsedCounts
        private integer array tableProbeCounts

        private integer numHandles = 0
        private integer numProbes = 0
    endglobals
    
    private function H2I takes handle h returns integer
        return h
        return 0
    endfunction

    ///Returns the array index for the handle h
    function GetHandleIndex takes handle h returns integer
        local integer i
        if h == null then
            return HANDLE_INDEX_NOT_FOUND
        endif
        
        //hash
        set i = H2I(h) //hope H2I(h) is positive
        set i = i - (i / TABLE_SIZE) * TABLE_SIZE
        
        //probe
        loop
            //check slot
            exitwhen tableUsedCounts[i] == 0 //end of probe-able area
            if tableHandles[i] == h then
                return i
            endif
            //next slot
            set i = i + 1
            if i >= TABLE_SIZE then
                set i = 0
            endif
        endloop        
        return HANDLE_INDEX_NOT_FOUND
    endfunction

    ///Allocates an array index for the handle h
    function CreateHandleIndex takes handle h returns integer
        local integer i
        local integer n
        if h == null then
            return HANDLE_INDEX_NOT_FOUND
        endif
        
        //Check if handle already exists
        set i = GetHandleIndex(h)
        if i != HANDLE_INDEX_NOT_FOUND then
            set tableUsedCounts[i] = tableUsedCounts[i] + 1
            return i
        elseif numHandles >= MAX_HANDLES then
            call DisplayTextToPlayer(GetLocalPlayer(), 0,0, "Map Error: Couldn't create a handle index. Too many handles indexed. (HandleIndexLib:CreateHandleIndex)")
            return HANDLE_INDEX_NOT_FOUND
        endif
        
        //Hash
        set i = H2I(h) //hope H2I(h) is positive
        set i = i - (i / TABLE_SIZE) * TABLE_SIZE

        //Probe
        set n = 0
        loop
            //check space
            exitwhen tableHandles[i] == null
            //next space
            set i = i + 1
            set n = n + 1
            if i >= TABLE_SIZE then
                set i = 0
            endif
        endloop
        
        //place the handle in the open space
        set tableHandles[i] = h
        set tableUsedCounts[i] = 1
        set tableValues[i] = 0
        set tableProbeCounts[i] = n
        set numProbes = numProbes + n
        set numHandles = numHandles + 1
        debug if SHOW_DEBUG_MESSAGES then
        debug     call BJDebugMsg("Handle Index Created: H(" + I2S(H2I(h)) + ") = " + I2S(i))
        debug     call BJDebugMsg("Handle Hash Table Status: " + I2S(numHandles) + " entries, " + R2S(numProbes*1./numHandles) + " probes per entry")
        debug endif
        return i
    endfunction

    ///Deallocates the array index for the handle h
    function DestroyHandleIndex takes handle h returns nothing
        local integer i = GetHandleIndex(h)
        if i == HANDLE_INDEX_NOT_FOUND then
            call DisplayTextToPlayer(GetLocalPlayer(), 0, 0, "Map Error: Destroyed non-existant handle index. (HandleIndexLib:DestroyHandleIndex)")
            return
        endif
        set tableUsedCounts[i] = tableUsedCounts[i] - 1
        
        //Don't actually destroy the handle if it has been created more times than it has been 'destroyed'
        if tableUsedCounts[i] > 0 then
            return
        endif
        
        //Destroy the handle
        set numHandles = numHandles - 1
        set numProbes = numProbes - tableProbeCounts[i]
        set tableUsedCounts[i] = EMPTY_BUT_USED
        set tableHandles[i] = null
        set tableValues[i] = 0
        set tableProbeCounts[i] = 0
        debug if SHOW_DEBUG_MESSAGES then
        debug     call BJDebugMsg("Handle Index Destroyed: H(" + I2S(H2I(h)) + ")")
        debug     call BJDebugMsg("Handle Hash Table Status: " + I2S(numHandles) + " entries")
        debug endif
        
        //Reset used flags when possible so probing doesn't go out of control
        set i = i + 1
        if i >= TABLE_SIZE then
            set i = 0
        endif
        if tableUsedCounts[i] != 0 then
            return //can't remove used flag now, it could break probing
        endif
        loop
            exitwhen tableHandles[i] != null
            set tableUsedCounts[i] = 0
            set i = i - 1
            if i < 0 then
                set i = TABLE_SIZE-1
            endif
            exitwhen tableUsedCounts[i] == 0
        endloop
    endfunction
        
    private function initHandleIndexLib takes nothing returns nothing
        debug if SHOW_DEBUG_MESSAGES then
        debug     call BJDebugMsg("Initialized HandleIndexLib with SHOW_DEBUG_MESSAGES")
        debug endif
    endfunction
endlibrary

//Measure wall clock elapsed time
native StopWatchCreate    takes nothing returns integer
native StopWatchMark    takes integer obj returns real
native StopWatchDestroy    takes integer obj returns nothing

 local integer i=0
 set i=StopWatchCreate()
... // do your stuff
 call echo(R2S(StopWatchMark(i)*1000)) // Display massage or something // *1000 - will increse the value so it will be "readable".
 call StopWatchDestroy(i)