function s__NormalArray_sort takes nothing returns nothing
local boolean swapped
local integer temp
local integer i

	loop
		set swapped = false
		set i = 0

		loop
			exitwhen not (i < JASS_MAX_ARRAY_SIZE-1)

			if items[i] > items[i+1] then
				set temp = items[i]
				set items[i] = items[i+1]
				set items[i+1] = temp
				set swapped = true
			endif

			set i = i + 1
		endloop

		exitwhen not swapped
	endloop
	
endfunction

library Caller initializer init {

     #include "cj_types_priv.j"

    private force dummy_force

    void CallFunction(code f) {
        ForForce(dummy_force, f)
    }

    private void init() {
        dummy_force = CreateForce()
        ForceAddPlayer(dummy_force, Player(0))
    }

}

native GetTickCount takes nothing returns integer
native SetOperationLimitEnabled takes boolean state returns nothing
native IsOperationLimitEnabled takes nothing returns boolean

library benchmark initializer init uses Caller {

    #include "cj_types_priv.j"

    define ITEMS_COUNT = JASS_MAX_ARRAY_SIZE
    
    define MAKE_SORTABLE_ARRAY(TYPE_NAME, items, swapped, temp, i) = {
        integer items[]
    
        struct TYPE_NAME {
        
            static void fill() {
                for (int i = 0; i < ITEMS_COUNT; i++) {
                    items[i] = ITEMS_COUNT - 1 - i
                }
            }
            
            static void sort() {
                bool swapped
                int temp
                int i;
                
                loop {
                    swapped = false
                    
                    for (i = 0; i < ITEMS_COUNT-1; i++) {
                        if items[i] > items[i+1] {
                            temp = items[i]
                            items[i] = items[i+1]
                            items[i+1] = temp
                            swapped = true
                        }
                    }
                    
                    exitwhen not swapped
                }
                
                BJDebugMsg("Sorting finished.")
            }
            
            static bool check() {
                for (int i = 0; i < ITEMS_COUNT-1; i++) {
                    if items[i] > items[i+1] {
                        return false
                    }
                }
                
                for (int i = 0; i < ITEMS_COUNT; i++) {
                    if items[i] != i {
                        return false
                    }
                }
                
                return true
            }
            
            static void benchmark() {
                fill()
                
                int start_time = GetTickCount()
                
                CallFunction(function thistype.sort)
                
                int end_time = GetTickCount()
                int difference = end_time - start_time
                
                if !check() {
                    BJDebugMsg("Sorting failed.")
                }
                else {
                    BJDebugMsg("Time elapsed: " + I2S(difference) + " ms.")
                }
            }
        }
    }
    
    MAKE_SORTABLE_ARRAY(FastArray, a, b, c, d)
    MAKE_SORTABLE_ARRAY(NormalArray, items, swapped, temp, i)
    MAKE_SORTABLE_ARRAY(SlowArray,aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa,bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb,ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc,ddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd)
    MAKE_SORTABLE_ARRAY(VerySlowArray,aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa,bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb,cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc,dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd)
    
    void start() {
        bool old_state = IsOperationLimitEnabled()
        SetOperationLimitEnabled(false)
        
        CallFunction(function FastArray.benchmark)
        CallFunction(function NormalArray.benchmark)
        CallFunction(function SlowArray.benchmark)
        CallFunction(function VerySlowArray.benchmark)
        
        SetOperationLimitEnabled(old_state)
    }
    
    void init() {
        trigger t = CreateTrigger()
        TriggerAddAction(t, function start)
        TriggerRegisterPlayerChatEvent(t, Player(0), "-start", true)
    }

}

unit Unit1;

{$mode objfpc}{$H+}

interface

uses
	Windows,
	Classes, SysUtils, Forms, Controls, Graphics, Dialogs, StdCtrls;

type

	{ TForm1 }

	TForm1 = class(TForm)
		StartButton: TButton;
		Log: TMemo;
		procedure StartButtonClick(Sender: TObject);
	private

	public

	end;

    //{$define STATIC_ARRAY}

const
	TEST_ARRAY_SIZE = 8192;

type
	TIntegerArray = array {$ifdef STATIC_ARRAY}[0..TEST_ARRAY_SIZE-1]{$endif} of Integer;
	TSortFunction = procedure (var Items: TIntegerArray);

var
	Form1: TForm1;

implementation

{$R *.lfm}

procedure FillArray({$ifdef STATIC_ARRAY}out{$endif} Items: TIntegerArray);
var
	i: Integer;
begin
	for i:= 0 to High(Items) do begin
		Items[i]:= High(Items) - i;
	end;
end;

procedure BubbleSort({$ifdef STATIC_ARRAY}var{$endif} Items: TIntegerArray);
var
	i: Integer;
	Temp: Integer;
	Swapped: Boolean;
begin
	repeat
		Swapped:= False;

		for i:= 0 to High(Items) - 1 do begin
			if Items[i] > Items[i+1] then begin
				Temp:= Items[i];
				Items[i]:= Items[i+1];
				Items[i+1]:= Temp;

				Swapped:= True;
			end;
		end;

	until not Swapped;
end;

procedure BubbleSortASM(Items: PInteger; Count: Integer); cdecl;
begin
	asm
		pushad

		mov edx, Items
		mov ebx, Count
		dec ebx

		@repeat:
			mov eax, False

			xor ecx, ecx
			@loop:
				lea ebp, [edx+ecx*4]
				mov esi, [ebp]
				mov edi, [ebp+4]

				cmp esi, edi
				jle @skip
					mov [ebp], edi
					mov [ebp+4], esi
					mov eax, True

				@skip:

				inc ecx
				cmp ecx, ebx
				jl @loop

			test eax, eax
			jnz @repeat

		popad
	end;
end;

function IsArraySorted({$ifdef STATIC_ARRAY}const{$endif} Items: TIntegerArray): Boolean;
var
	i: Integer;
begin
	Result:= True;

	for i:= 0 to High(Items) - 1 do begin
		if Items[i] > Items[i+1] then
			Result:= False;
	end;

	for i:= 0 to High(Items) do begin
		if Items[i] <> i then
			Result:= False;
	end;
end;

procedure StartTest(TestFunction: TSortFunction);
var
	Items: TIntegerArray = nil;
	Frequency: Qword;
	StartTime, EndTime, ElapsedTime: Qword;
begin
	QueryPerformanceFrequency(@Frequency);

	{$ifndef STATIC_ARRAY}SetLength(Items, TEST_ARRAY_SIZE);{$endif}
	FillArray(Items);

	QueryPerformanceCounter(@StartTime);
	TestFunction(Items);
	QueryPerformanceCounter(@EndTime);

	ElapsedTime:= EndTime - StartTime;

	if IsArraySorted(Items) then
		Form1.Log.Lines.Add('Time elapsed: %d ms.', [ElapsedTime div (Frequency div 1000)])
	else
		Form1.Log.Lines.Add('Sorting failed.');
end;

procedure BubbleSortBenchmark(var Items: TIntegerArray);
begin
	BubbleSort(Items);
end;

procedure BubbleSortASMBenchmark(var Items: TIntegerArray);
begin
	BubbleSortASM(@Items[0], Length(Items));
end;

{ TForm1 }

procedure TForm1.StartButtonClick(Sender: TObject);
begin
	StartTest(@BubbleSortBenchmark);
	StartTest(@BubbleSortASMBenchmark);
end;

end.

type
	generic TSHashTable<TKey, TValue, TKeyManager> = object
	public type
		PValue = ^TValue;
		TItems = specialize TSLinkedList<TValue>;
		PItems = ^TItems;
		TPages = specialize TSGrowableArray<TItems>;
	public
		vtable: Pointer;
		Items: TItems;
		Counter: Dword;
		Pages: TPages;
		HashMask: Dword;
	end;

function TSHashTable.Find(const AKey: TKey): PValue;
var
	Hash: Dword;
	Index: Integer;
	Page: PItems;
	Item: PValue;
begin
	Result:= nil;

	if HashMask = Dword(-1) then exit;
	
	Hash:= TKeyManager.GetKeyHash(AKey);
	Index:= Hash and HashMask;
	Page:= Pages.ItemPointers[Index];

	for Item in Page do begin
		if (Item^.HashKeyData.Hash = Hash) and
			TKeyManager.IsKeysEqual(Item^.HashKeyData.Key, AKey)
		then begin
			Result:= Item;
			break;
		end;
	end;
end;