As promised, let us proceed with the explanation on how to use CopyMemory to maintain a sorted array. I believe it will be best if we now use an example.
Imagine you need to maintain an array of ID's, long data type, but you also need to store two boolean values for each ID, one that will mark the ID as used in some task that we call Task1, and the other one will mark the ID as used in another task, Task2. The easiest way would be to create a UDT, and then an array of this UDT. Also, this could be set in a class module, if deemed necessary:
Private Type TypeID
lID As Long
bTask1 As Boolean
bTask2 As Boolean
End Type
'Now, we declare the array
Private arrIDs() As IDType
This array will be growing and and shrinking a lot, and it must be sorted by ID in ascending order because we need the program to rapidly find IDs for further use. Using CopyMemory will achieve great speeds while adding or removing items in large arrays. Take a look at the function PopulateArrayAPI taken from the attached example, which populates an array with random IDs.
Public Sub PopulateArrayAPI(ByRef arrData() As TypeID, ByVal lTotal As Long, ByVal oCB As ICallBack)
Dim lCount As Long
Dim lID As Long
Dim lPos As Long
Dim bFound As Boolean
Randomize
For lCount = 1 To lTotal
'Get an ID number that is not in the array
Do
lID = oCB.NewID(lTotal)
'Find the ID in the array
lPos = QuickSortFindID(lID, arrData, bFound)
Loop Until Not (bFound)
ReDim Preserve arrData(1 To lCount)
If (lPos = -1) Or (lPos = lCount) Then
'First element in the array
arrData(lCount).lID = lID
Else
'lPos contains the nearest index whose ID is greater than lID,
'which is the position where the new ID must be.
CopyMemory arrData(lPos + 1), arrData(lPos), (lCount - lPos) * LenB(arrData(LBound(arrData)))
'Now the data has been moved and position lPos is free to use!
arrData(lPos).lID = lID
End If
oCB.ProgressChange lCount
Next lCount
End Sub
The attached example project fulfills the main objective of this article, which is to show how to use CopyMemory with a sorted array so it stays like that. It is very simple and you should have no problems understanding it.
NOTE: The example project can obtain the IDs from a file. The file format, if you decide to create a new one, is simple: Open the file for binary access. The first 4 bytes are to be read and represent the amount of IDs contained in the file. After the first 4 bytes, each 4-byte value represent an ID. Just like that.
Behind the Curtains
The search function implemented in the example, QuickSortFindID, will return the index of the searched ID if it exists in the array, or will return the index where the ID must be placed in order to keep the array sorted. As you can see from the previous function, there is no loop to move part of the array one space to free the position revealed by QuickSortFindID. Instead, there is a call to CopyMemory.
CopyMemory will move one block of memory from one place to another; remember that the original name of CopyMemory is rtlMoveMemory. The arguments in order are:
1. pDest: Destination memory address (pointer). You must pass the memory address where you want to move the data to. In the example, that would be the memory address of the lPos-th element with an offset of 1 (lPos + 1).
2. pSrc: Source memory address (pointer). The source memory address is the starting byte address of the data we want to move. In the example, that would be the memory address of the lPos-th element.
3. ByteLen: The amount of bytes you want to move. This one is a tricky one when it comes to user-defined types. However, in our case is the amount of array elements we want to move, times the amount of bytes used by one of the elements. The result is the total number of bytes to be moved.
Why does this work? Please remember that earlier I mentioned that array elements are allocated in a contigous manner in RAM (one after the other).
Now to learn more about the tricky part, please turn the page.
Comments