; _______________________________________________________________________________________
;|                                                                                       |
;| ..::FreshLib::..  Free, open source. Licensed under "BSD 2-clause" license."          |
;|_______________________________________________________________________________________|
;
;  Description: OS independent dynamic arrays library.
;
;  Target OS: Any
;
;  Dependencies: memory.asm
;
;  Notes:
;_________________________________________________________________________________________

module "Arrays library"

struct TArray
  .count     dd ?           ; Count of elements in dynamic array
  .capacity  dd ?           ; Capacity of the array allocated memory.
  .itemsize  dd ?           ; Size of one element in dynamic array. Aligned on dword.
  .lparam    dd ?           ; User defined value.
  label .array dword
ends


; ____________________________________________________________________
;|                                                                    |
;| Creates dynamic array.                                             |
;|                                                                    |
;| Arguments:                                                         |
;|                                                                    |
;|   .ItemSize: size in bytes of one array element.                   |
;|              This size will be aligned to dword.                   |
;|                                                                    |
;| Return:                                                            |
;|   if CF=1 the memory can't be allocated.                           |
;|   if CF=0 eax contains pointer to the created array.               |
;|____________________________________________________________________|

proc CreateArray, .ItemSize
begin
        push    ecx edx
        mov     ecx, [.ItemSize]
        add     ecx, 3
        and     cl, $fc
        mov     edx, ecx

        imul    ecx, cInitialCapacity
        add     ecx, sizeof.TArray
        stdcall GetMem, ecx
        jc      .finish

        mov     [eax+TArray.itemsize], edx
        mov     [eax+TArray.capacity], cInitialCapacity
        clc

.finish:
        pop     edx ecx
        return
endp


; returns a pointer to the array item.
; Arguments:
;  .array - pointer to TArray
;  .index - index of the array element.
;
; Returns:
;   CF=0; EAX = pointer to the array element.
;   CF=1 - indicates that [.index] is bigger than the array element count;
;          in this case EAX = points after the last element of the array.

proc GetArrayItem, .array, .index
begin
        push    ecx esi

        mov     esi, [.array]
        mov     eax, [.index]
        mov     ecx, [esi+TArray.count]

        cmp     eax, ecx
        cmovae  eax, ecx

        imul    eax, [esi+TArray.itemsize]
        lea     eax, [esi+TArray.array+eax]

; set CF
        sub     ecx, 1
        jc      @f
        cmp     ecx, [.index]
@@:
        pop     esi ecx
        return
endp



;____________________________________________________________________
;
;  proc AddArrayItems - adds new item at the end of TArray
;                      dynamic array.
;  Arguments:
;
;    .ptrArray - pointer to dword variable containing pointer
;               to TArray structure.
;    .count - count of the elements to be added.
;
;  Returns:
;    CF=1 if error: edx - pointer to the original array.
;
;    CF=0 if OK:    eax - pointer to new created element.
;                   edx - pointer to the array.
;
;  Notes:
;    The procedure returns in edx pointer to the TArray. This pointer
;    can differs from .ptrArray argument, if the memory was
;    reallocated. The user should save the pointer for future access
;    to the array. It is safe to save the pointer before check of CF
;    for error, because the procedure returns original pointer in case
;    of memory allocation error.
;____________________________________________________________________

proc AddArrayItems, .ptrArray, .count
begin
        push    ebx ecx

        mov     edx, [.ptrArray]
        test    edx, edx
        jnz     @f

        stc
        pop     ecx ebx
        return

@@:
        mov     eax, [edx+TArray.count]
        mov     ecx, [edx+TArray.capacity]
        add     eax, [.count]
        cmp     ecx, eax
        jae     .memallocated

; enlarge the array. Strategy here is not clear.
        mov     ecx, eax
        call    dword [ResizeIt]
        jc      .finish

        mov     ebx, ecx
        imul    ecx, [edx+TArray.itemsize]
        add     ecx, sizeof.TArray

        stdcall ResizeMem, edx, ecx
.readdr:
        jc      .finish

        mov     edx, eax
        mov     [edx+TArray.capacity], ebx

.memallocated:
        mov     eax, [edx+TArray.count]
        mov     ecx, [.count]
        add     [edx+TArray.count], ecx

        imul    eax, [edx+TArray.itemsize]
        lea     eax, [edx+eax+TArray.array]
        clc

.finish:
        pop     ecx ebx
        return
endp


;____________________________________________________________________
;
;  proc InsertArrayItems - inserts new item in the array.
;
;  Arguments:
;
;    .ptrArray - pointer to TArray structure.
;    .iElement - on what index to be inserted the new elements.
;    .count    - how many elements to be inserted.
;
;  Returns:
;    CF=1 if error: edx - pointer to the original array; new elements are
;                         not inserted.
;
;    CF=0 if OK:    eax - pointer to the first of the new inserted elements.
;                   edx - pointer to the array.
;
;  Notes:
;    If .iElement is larger or equal to [TArray.count] the elements are
;    appended at the end of the array. Otherwise, all elements are moved
;    to make room for the new elements. If the capacity of the array is
;    not enough to hold the new elements, the array is resized.
;
;    The procedure returns in edx pointer to the TArray. This pointer
;    can differs from .ptrArray argument, if the memory was
;    reallocated. The user should save the pointer for future access
;    to the array. It is safe to save the pointer before check of CF
;    for error, because the procedure returns original pointer in case
;    of memory allocation error.
;____________________________________________________________________

proc InsertArrayItems, .ptrArray, .iElement, .count
begin
        stdcall AddArrayItems, [.ptrArray], [.count]
        jc      .end1

        push    ecx

        mov     ecx, [.iElement]
        add     ecx, [.count]
        cmp     ecx, [edx+TArray.count]
        jae     .end2

        push    esi edi

        imul    ecx, [edx+TArray.itemsize]
        lea     ecx, [edx+ecx+TArray.array]

        lea     esi, [eax-4]                    ; the last element.
        mov     edi, [edx+TArray.count]
        imul    edi, [edx+TArray.itemsize]
        lea     edi, [edx+edi+TArray.array]     ; end of the array.

        mov     eax, ecx
        sub     eax, [edx+TArray.itemsize]

        sub     ecx, edi
        neg     ecx
        shr     ecx, 2

        sub     edi, 4

        std

; scroll the data.
        rep movsd

; clear the new items.
        mov     ecx, [edx+TArray.itemsize]
        imul    ecx, [.count]
        shr     ecx, 2
        xor     eax, eax
        rep stosd

        lea     eax, [edi+4]
        cld

        pop     edi esi

.end2:
        pop     ecx
.end1:
        return
endp


;**************************************************************
;  proc DeleteArrayItems - deletes the items with the specified
;                          index and specified count from TArray
;                          dynamic array.
;  If the capacity of the array is bigger than the recomended
;  for the new count, then the array is resized.
;  The recomended size is calculated using ResizeIt procedure
;  from memory library.
;
;  Arguments:
;    .ptrArray - pointer to TArray structure.
;    .iElement - index of the element to be deleted.
;    .count    - how many elements to be deleted.
;
;  Returns: edx - pointer to the TArray. In the most cases
;                 this pointer will not be changed, but this
;                 also depends on the current OS memory
;                 allocation API, so it is safer to store
;                 the pointer for future use instead of
;                 passed to the procedure.
;
;  Notes:
;           This function can't fail, because delete is
;           always possible in already allocated array.
;           in some cases shrinking resize possibly can fail
;           but this will not affect the data in the array.
;
;           if [.iElement]+[.count] is bigger that the [TArray.count]
;           of the array, only the elements to the end of the array
;           will be deleted.
;
;*******************************************************
proc DeleteArrayItems, .ptrArray, .iElement, .count
begin
        push    edi esi ecx ebx eax

        mov     edx, [.ptrArray]
        test    edx, edx
        jz      .exit

        mov     ecx, [.iElement]
        mov     eax, [edx+TArray.count]

        test    ecx, ecx
        js      .exit

        cmp     ecx, eax
        jae     .exit                   ; index greater or equal to the count...

        add     ecx, [.count]
        cmp     ecx, eax
        jae     .movedone               ; if there is no more elements after the last deleted element, don't move

        mov     eax, [edx+TArray.itemsize]

        imul    ecx, eax
        lea     esi, [edx+ecx+TArray.array]     ; the first after deleted

        mov     ecx, [.iElement]
        imul    ecx, eax                        ; offset of the deleted element.
        lea     edi, [edx+ecx+TArray.array]     ; destination address.

        mov     ecx, [edx+TArray.count]
        imul    ecx, eax
        lea     ecx, [ecx+edx+TArray.array]
        sub     ecx, esi                        ; bytes to be moved. It should be dword aligned count.

        shr     ecx, 2
        rep movsd                               ; move the data.

.movedone:
        mov     ecx, [edx+TArray.count]
        mov     eax, [.iElement]
        sub     ecx, [.count]
        cmp     ecx, eax
        ja      @f
        mov     ecx, eax
@@:
        mov     [edx+TArray.count], ecx

        call    [ResizeIt]
        jc      .exit                           ; the array is OK, but the resize failed.

        cmp     ecx, [edx+TArray.capacity]
        jae     .exit                           ; the array have smaller capacity than recomended, so don't resize.

        mov     eax, ecx
        imul    eax, [edx+TArray.itemsize]
        add     eax, sizeof.TArray
        stdcall ResizeMem, edx, eax
        jc      .exit                           ; the resize failed, but the array is ok.

        mov     edx, eax
        mov     [edx+TArray.capacity], ecx      ; set new capacity.

.exit:
        pop     eax ebx ecx esi edi
        return
endp



;**************************************************************
;  proc VacuumArray - deletes the reserved memory from the array.
;
;  Arguments:
;    .ptrArray - pointer to TArray structure.
;
;  Returns: edx - pointer to the TArray. In the most cases
;                 this pointer will not be changed, but this
;                 also depends on the current OS memory
;                 allocation API, so it is safer to store
;                 the pointer for future use instead of
;                 passed to the procedure.
;           CF=1 - there is a error on vacuuming. This is not
;                  exactly error, because this case indicates
;                  simply some memory manager unabiliry to reallocate
;                  memory. Although the array will not be changed.
;
; This procedure removes all reserved space in the array.
; Vacuum can save a lot of memory space, but takes time and
; also will make future inserts of new elements
; slower at least for the first add/insert.
;
; it is wise to vacuum the array after it is filled with
; most/all of the needed elements.
;
proc VacuumArray, .ptrArray
begin
        push    eax ecx

        mov     edx, [.ptrArray]
        mov     ecx, [edx+TArray.count]
        mov     eax, [edx+TArray.itemsize]
        add     ecx, 1
        imul    eax, ecx
        add     eax, sizeof.TArray

        stdcall ResizeMem, edx, eax
        jc      .exit

        mov     edx, eax
        mov     [eax+TArray.capacity], ecx

.exit:
        pop     ecx eax
        return

endp





;****************************************************
; Quick sort of the array in the memory.
;
;  ptrArray       - pointer to TArray structure.
;  ptrCompareProc - pointer to procedure that compares two elements.
;
; ptrCompareProc have interface:
;  proc CompareSomething, ptrElement1, ptrElement2
;    returns: c=1 if elements are not properly sorted.
;             c=0 if elements are sorted, i.e.
;                 element1 should be before element2
;****************************************************


proc SortArray, .ptrArray, .ptrCompareProc
begin
        pushad

        mov     esi, [.ptrArray]
        mov     edi, [.ptrCompareProc]
        mov     ebx, [esi+TArray.itemsize]

        mov     eax, [esi+TArray.count]
        dec     eax
        xor     ecx, ecx
        lea     esi, [esi+TArray.array]

        stdcall __DoQSort, ecx, eax

        popad
        return
endp

;*****************************************************
; Procedure for internal call from QSort procedure.
;*****************************************************
proc __DoQSort, .Left, .Right
begin
        push    ecx

        mov     ecx, [.Left]     ; i variable
        mov     eax, ecx
        mov     edx, [.Right]    ; j variable
        add     eax, edx

        cmp     ecx, edx
        je      .rightok

        sar     eax, 1
        imul    eax, ebx
        imul    ecx, ebx
        imul    edx, ebx
        add     eax, esi
        add     ecx, esi
        add     edx, esi

        call    ___CopyMiddleElement

.repeat:
        sub     ecx, ebx
        add     edx, ebx

.whilei:
        add     ecx, ebx
        stdcall edi, ecx, eax
        jnc     .whilei

.whilej:
        sub     edx, ebx
        stdcall edi, eax, edx
        jnc     .whilej

        cmp     ecx, edx
        jg      .next           ;i>j
        je      .swapok
        call    ___SwapElements
.swapok:
        add     ecx, ebx
        sub     edx, ebx

.next:
        cmp     ecx, edx
        jle     .repeat

        stdcall FreeMem, eax

        mov     eax, edx        ;j
        sub     eax, esi
        cdq
        idiv    ebx

        cmp     [.Left], eax
        jge     .leftok

        stdcall __DoQSort, [.Left], eax

.leftok:
        mov     eax, ecx        ;i
        sub     eax, esi
        cdq
        idiv    ebx

        cmp     eax, [.Right]
        jge     .rightok

        stdcall __DoQSort, eax, [.Right]

.rightok:
        pop     ecx
        return
endp



;********************************************
; Swaps two elements of the array with
; pointers in:
;   Element1 - ecx
;   Element2 - edx
;   ElementSize - ebx
;********************************************
proc ___SwapElements
begin
        pushad

        xor     esi, esi
.loop:
        mov     al, [ecx+esi]
        xchg    al, [edx+esi]
        mov     [ecx+esi], al

        inc     esi
        cmp     esi, ebx
        jne     .loop

        popad
        return
endp


proc ___CopyMiddleElement
begin
        push    ecx esi edi

        mov     esi, eax
        stdcall GetMem, ebx
        mov     edi, eax
        mov     ecx, ebx

        rep movsb
        pop     edi esi ecx
        return
endp




proc CompareIntAscending, .ptrElement1, .ptrElement2
begin
        push    eax esi edi

        mov     esi, [.ptrElement1]
        mov     edi, [.ptrElement2]

        mov     eax, [esi]
        cmp     eax, [edi]
        jl      .qfalse

        stc
        pop     edi esi eax
        return


.qfalse:
        clc
        pop     edi esi eax
        return
endp







;____________________________________________________________________
;
; proc ListIndexOf, .ptrArray, .item - searches dynamic list for
;                                    the given item.
;
; List is a special case of dynamic array, where the size of the
; elements is dword (4 bytes).
;
; Arguments:
;   .ptrList - pointer to TArray dynamic array.
;   .item    - value of the element.
; Returns:
;   CF = 0 if the element was found. eax contains index of
;          the element.
;   CF = 1 the element is not found.
;____________________________________________________________________

proc ListIndexOf, .ptrList, .Item
begin
        push    edi ecx

        mov     edi, [.ptrList]

        cmp     [edi+TArray.itemsize], 4
        jne     .notfound

        mov     ecx, [edi+TArray.count]
        jecxz   .notfound

        lea     edi, [edi+4*ecx+TArray.array-4] ; from the end
        mov     eax, [.Item]
        std
        repnz scasd
        cld
        jz      .found

.notfound:
        stc
        pop     ecx edi
        return

.found:
        clc
        mov     eax, ecx
        pop     ecx edi
        return
endp


;--------------------------------------------
; Frees all elements of the list calling
; [FreeProc] on every element.
; (proc FreeProc, ptrItem)
; Frees the array of items
;--------------------------------------------
proc ListFree, .ptrList, .FreeProc
begin
        pushad

        mov     edi, [.ptrList]
        mov     ebx, [edi+TArray.count]

        cmp     [.FreeProc], 0
        je      .endwhile

.freeloop:
        dec     ebx
        js      .endwhile

        stdcall [.FreeProc], [edi+4*ebx+TArray.array]
        jmp     .freeloop

.endwhile:
        stdcall FreeMem, edi

.finish:
        popad
        return
endp


endmodule