Sorting array of any-sized structure

2023-08-17
2024-01-17
  • ihatemaryfisher - 2023-08-17

    In my machine's operation, I need to display multiples tables containing arrays of structured variables. The arrays change during operation, and my supervisor has advised me to write a new bubble-sort for each array.

    I think I can make a function to sort an array of any data type.

    This was my own project, and I'm a relatively new coder. I want to know the weaknesses in my approach, and a better method, if one exists. As far as I can test, the function accepts an array of a structured variable of any size, and sort it by any VAR in that structure. But it relies heavily on pointers, which I've heard are bad practice?

    Function call:

    // SORT BY BYTE-SIZED VAR
    IF xDoIt[6] THEN
        FUNBubbleSortSansBuffer(
            IN_pbySourcePointer := ADR(astArray[1]), // address of first byte in first element of array
            IN_pbyComparePointer:= ADR(astArray[1].byCompByte),  // points to first byte of the comparing variable (variable you sort by)
            IN_uiStructureSize  := SIZEOF(TYPE_STRUCTURE), // size, in bytes, of the structured variable
            IN_uiCompareSize    := SIZEOF(astArray[1].byCompByte), // size, in bytes, of the comparing variable (variable you sort by)
            diArrayElements     := UPPER_BOUND(astArray,1), // number of elements in array
            IN_xSmallToLarge    := xSortOrder // whether to sort by small2large or large2small
        );
    END_IF
    

    Function:

    FUNCTION FUNBubbleSortSansBuffer : BOOL
    VAR_INPUT
        IN_pbySourcePointer : POINTER TO BYTE; // points to beginning of array (first byte of first element)
        IN_pbyComparePointer: POINTER TO BYTE; // points to first byte of the comparing variable (variable you sort by)
        IN_uiStructureSize  : UINT; // size, in bytes, of the structured variable
        IN_uiCompareSize    : UINT; // size, in bytes, of the comparing variable (variable you sort by)
        diArrayElements     : DINT; // number of elements in array
        IN_xSmallToLarge    : BOOL; // whether to sort by small2large or large2small
    END_VAR
    VAR
        j       : DINT; // repeat iteration over array until array ends
        i       : DINT; // iterarte over array, swapping when necesary
        k       : DINT; // iterator from 1 to size of structure (stepping 'through' a single element in array)
        dwSize  : DWORD; // internal var for use in MEMUtils.MemCpy(<size>)
    
        // FOR SORTING BY BYTE VAR
        pbySourcePointer    : POINTER TO BYTE;
        pbySourcePointer2   : POINTER TO BYTE;
        pbyComparePointer   : POINTER TO BYTE;
        pbyComparePointer2  : POINTER TO BYTE;
    
        pbyPointerToBuffer  : POINTER TO BYTE; // pointer to single byte buffer
        byBufferByte        : BYTE; // single byte buffer
    END_VAR
    
    dwSize  := UINT_TO_DWORD(IN_uiStructureSize); // get structure size (number of bytes)
    pbyPointerToBuffer  := ADR(byBufferByte); // assign pointer to address of buffer byte (because MEMUtils.MemCpy requires a pointer input)
    CASE IN_uiCompareSize OF // depending on the size of the VAR to sort by (current functionality for BYTE and WORD/INT
        1: // BYTE (8 BIT)
            FOR j := 1 TO diArrayElements DO // for number of elements in array
                FOR i := 1 TO (diArrayElements-1) DO // same thing, but row[i+1] row is included in swap logic
                    pbySourcePointer    := IN_pbySourcePointer  + dwSize*(i-1); // point at #1 byte in array element[i]
                    pbySourcePointer2   := pbySourcePointer + dwSize;           // point at #1 byte in array element[i+1]
    
                    // NOTE: because of memory locations, each array element is offset from one another by a number of bytes equal to the size of the structure
                    // We can "walk" from array[i] to array[i+1] via steps equal to the size of the structure
                    // e.g., ADR(array[i+1]) == ADR(array[i]) + SIZEOF([array datatype])
    
                    pbyComparePointer   := IN_pbyComparePointer + dwSize*(i-1); // point to sorting variable in array element[i]
                    pbyComparePointer2  := pbyComparePointer + dwSize;          // point to sorting variable in array element[i+1]
    
                    // using sort order (small -> large/large -> small)
                    IF SEL(IN_xSmallToLarge, (pbyComparePointer2^ > pbyComparePointer^),(pbyComparePointer2^ < pbyComparePointer^)) THEN
                        // This is where it gets tricky. We've identified pointers for the starting bytes of aArray[i] and aArray[i+1]
                        // and we know the size of aArray[i]. We are going to swap individual bytes, one at a time, from aArray[i] and aArray[i+1]
                        // this allows us to use only a single byte var as a buffer or temporary data storage
                        // e.g., consider a structure consisting of a word, a byte, and a string. it is stored like this
                            //                  |------WORD-------|     |--BYTE-|       |STRING------...|
                            //  astArray[1] ==  1000 0100 0010 0001     1100 0011       1010 1010.... etc
                            //  astArray[2] ==  0001 0010 0100 1000     0011 1100       0101 0101.... etc
                        // performing a single swap (copy into a buffer, etc.) of the first byte of each array element creates this
                            //  astArray[1] ==  0001 0100 0010 0001     1100 0011       1010 1010.... etc
                            //  astArray[2] ==  1000 0010 0100 1000     0011 1100       0101 0101.... etc
                        // incrementing the pointer adresses for the swap by 1 and swapping again swaps the next byte in each array element
                            //  astArray[1] ==  0001 0010 0010 0001     1100 0011       1010 1010.... etc
                            //  astArray[2] ==  1000 0100 0100 1000     0011 1100       0101 0101.... etc
                        // continuing this from k to SIZEOF(TYPE_STRUCTURE) results in a toally swapped row
                        FOR k := 1 TO IN_uiStructureSize DO
                            // copy single byte[k] of array element 1 to buffer
                            MEMUtils.MemCpy(pbyDest := (pbyPointerToBuffer),    pbySrc  := (pbySourcePointer+k-1), dwSize   := 1);                  
                            // copy single byte[k] of array element 2 to 1
                            MEMUtils.MemCpy(pbyDest := pbySourcePointer+k-1,    pbySrc  := (pbySourcePointer2+k-1), dwSize  := 1);
                            // copy buffer to byte[k] array element 2 
                            MEMUtils.MemCpy(pbyDest := (pbySourcePointer2+k-1), pbySrc  := pbyPointerToBuffer, dwSize   := 1);
                        END_FOR
                    END_IF
                END_FOR
            END_FOR
    
     

    Related

    Talk.ru: 1

  • TimvH

    TimvH - 2023-08-18

    Look all the way at the end of the link below. This provides a way to use arrays with various lengths:
    https://content.helpme-codesys.com/en/CODESYS%20Development%20System/_cds_datatype_array.html

     
    • ihatemaryfisher - 2023-08-18

      With that I could make an array of varying size, but would still have to define the array type in the function's declaration

      VAR_IN_OUT
          stArray: array [*..*] of <pre-defined data type>
      END_VAR
      

      I wanted a function that could take an array of any type (e.g., a structured VAR) as an input. That way I could call it in multiple POUs to handle different arrays structures.

       

Log in to post a comment.