Virtual listviews for huge number of rows

[LarsJ]

Virtual listviews are lightning fast and can handle millions of rows.

Virtual listviews are of interest when you have to insert more than 10,000 rows. When there are less than 10,000 rows, the standard listviews are sufficiently rapid. See the section "Using standard listviews" below.

In a virtual listview data are not stored directly in the listview. Data are stored in an array, a structure (DllStructCreate), a flat fixed-length record file, a database or similar. The listview only contains the rows which are visible depending on the height of the listview. See About List-View Controls in the MicroSoft documentation for more information.

An array or a structure can be used for listviews with 10,000 - 100,000 rows. If there are more than 100,000 rows a fixed-length record file or a database seems to be the best solution, because they have low impact on memory usage.

But you get nothing for free. The costs is that a part of the built-in features does not work, and you will have to implement these features yourself. Because data isn't stored in the listview the Set- and Get-functions to manipulate data doesn't work. You have to manipulate the data source directly. And sorting is not supported at all by virtual listviews.

If you need sorting, a database seems to be the best solution in all cases, because sorting can be handled by the database.

Below you'll find the following sections:

• Data stored in arrays
• Data stored in databases
• Data stored in fixed-length record files
• Sorting rows in a virtual listview
• $LVN_ODFINDITEM notifications
• Using standard listviews
• Updates
• Zip file
• Examples

The next two sections shows how to use virtual listviews, when data are stored in arrays or databases. In first section data are stored in 3 arrays with 10,000/50,000/100,000 rows and 10 columns. In second section data are stored in 3 databases with 100,000/1,000,000/10,000,000 rows and 10 columns.

 

Data stored in arrays

For a virtual listview rows are displayed with $LVN_GETDISPINFO notifications and the $tagNMLVDISPINFO structure. Code for $LVN_GETDISPINFO messages in the WM_NOTIFY function can be implemented in this manner:

Case $LVN_GETDISPINFOW
  Local $tNMLVDISPINFO = DllStructCreate( $tagNMLVDISPINFO, $lParam )
  If BitAND( DllStructGetData( $tNMLVDISPINFO, "Mask" ), $LVIF_TEXT ) Then
    Local $sItem = $aItems[DllStructGetData($tNMLVDISPINFO,"Item")][DllStructGetData($tNMLVDISPINFO,"SubItem")]
    DllStructSetData( $tText, 1, $sItem )
    DllStructSetData( $tNMLVDISPINFO, "Text", $pText )
    DllStructSetData( $tNMLVDISPINFO, "TextMax", StringLen( $sItem ) )
  EndIf

Run LvVirtArray.au3. It takes some time to create the arrays. But when the arrays are created, switching from one array to another (which means updating the listview) is instantaneous.

 

Data stored in databases

When data are stored in a database, $LVN_ODCACHEHINT notifications and the $tagNMLVCACHEHINT structure is used to insert the rows in an array cache before they are displayed with $LVN_GETDISPINFO messages.

The $tagNMLVCACHEHINT structure is defined in this way:

Global Const $tagNMLVCACHEHINT = $tagNMHDR & ";int iFrom;int iTo"

Note that $tagNMLVCACHEHINT is not included in GuiListView.au3 or StructureConstants.au3.

Code for $LVN_ODCACHEHINT messages in the WM_NOTIFY function can be implemented in this manner:

Case $LVN_ODCACHEHINT
  Local $tNMLVCACHEHINT = DllStructCreate( $tagNMLVCACHEHINT, $lParam ), $iColumns
  $iFrom = DllStructGetData( $tNMLVCACHEHINT, "iFrom" )
  Local $sSQL = "SELECT * FROM lvdata WHERE item_id >= " & $iFrom & _
    " AND item_id <= " & DllStructGetData( $tNMLVCACHEHINT, "iTo" ) & ";"
  _SQLite_GetTable2d( -1, $sSQL, $aResult, $iRows, $iColumns )

$aResult is the array cache. The purpose of the cache is to limit the number of SELECT statements.

When the listview is displayed for the first time, all visible rows (in this example about 20) have to be updated. In this case $aResult will contain 20 rows and 10 columns. 20 rows is also the maximum number of rows in $aResult. A virtual listview will never update more than the visible number of rows at one time.

Code for $LVN_GETDISPINFO messages can be implemented in this way:

Case $LVN_GETDISPINFOW
  Local $tNMLVDISPINFO = DllStructCreate( $tagNMLVDISPINFO, $lParam )
  If BitAND( DllStructGetData( $tNMLVDISPINFO, "Mask" ), $LVIF_TEXT ) Then
    Local $iIndex = DllStructGetData( $tNMLVDISPINFO, "Item" ) - $iFrom + 1
    If $iIndex > 0 And $iIndex < $iRows + 1 Then
      Local $sItem = $aResult[$iIndex][DllStructGetData($tNMLVDISPINFO,"SubItem")]
      DllStructSetData( $tText, 1, $sItem )
      DllStructSetData( $tNMLVDISPINFO, "Text", $pText )
      DllStructSetData( $tNMLVDISPINFO, "TextMax", StringLen( $sItem ) )
    EndIf
  EndIf

The zip below contains a small GUI, CreateDB.au3, to create 3 SQLite databases with 100,000/1,000,000/10,000,000 rows. The databases will use about 10/100/1000 MB of diskspace, and the creation will take about ½/5/40 minutes (on an old XP). You must select a database and click a button to start the creation. If you get tired of waiting, you can cancel (checked for every 10,000 rows) the process and continue another time. The process will continue where it stopped. You can run the examples even though the databases might only contain 30,000/200,000/1,500,000 rows. You do not have to create all three databases.

Run LvVirtDB.au3.

 

Data stored in fixed-length record files (update 2015-04-01)

Extracting data directly from a fixed-length record file by setting the file pointer to the current record and reading the required number of bytes is another example, where $LVN_ODCACHEHINT messages should be used to insert records in an array cache before they are displayed.

Code for $LVN_ODCACHEHINT and $LVN_GETDISPINFO messages can be implemented as shown:

Case $LVN_ODCACHEHINT
  Local $tNMLVCACHEHINT = DllStructCreate( $tagNMLVCACHEHINT, $lParam )
  $iFrom = DllStructGetData( $tNMLVCACHEHINT, "iFrom" )
  $iRows = DllStructGetData( $tNMLVCACHEHINT, "iTo" ) - $iFrom + 1
  FileSetPos( $hFile, $iFrom * 12, 0 ) ; Each line is 10 chars + CR + LF
  $aCache = StringSplit( FileRead( $hFile, $iRows * 12 - 2 ), @CRLF, 3 )

The purpose of the cache is to limit the number of FileRead statements.

Case $LVN_GETDISPINFOW
  Local $tNMLVDISPINFO = DllStructCreate( $tagNMLVDISPINFO, $lParam )
  If BitAND( DllStructGetData( $tNMLVDISPINFO, "Mask" ), $LVIF_TEXT ) Then
    Local $iIndex = DllStructGetData( $tNMLVDISPINFO, "Item" ) - $iFrom
    If -1 < $iIndex And $iIndex < $iRows Then
      DllStructSetData( $tText, 1, $aCache[$iIndex] )
      DllStructSetData( $tNMLVDISPINFO, "Text", $pText )
      DllStructSetData( $tNMLVDISPINFO, "TextMax", 10 ) ; Each line is 10 chars
    EndIf
  EndIf

Run LvVirtFile.au3. A fixed-length record file with 10,000 records (LvVirtFile.txt) is included in the zip.

I have tested this example on a 1,1 GB file and 100,000,000 rows. The listview responds immediately. The solution with a flat fixed-length record file is extremely fast. Much faster than a database. But also with very much limited functionality compared to a database.

 

Sorting rows in a virtual listview (update 2015-04-01)

Sorting is not supported at all by virtual listviews. If you want rows to be sorted, you have to feed the listview with the rows in sorted order. If the rows are stored in an array, you have to sort the array before you feed the listview.

If you want to sort the rows by two or more columns, you have to store the rows in two or more arrays which are sorted for the current column. Or you have to create two or more indexes to handle the sorting.

Sorting arrays and creating indexes is time consuming. If you need sorting, a database seems to be the best solution, because sorting can be handled by the database.

Nevertheless, here's an example that stores 10,000/20,000/30,000 rows and 3 columns in arrays, and creates indexes to handle the sorting. The columns are strings, integers and floating point numbers, and indexes are calculated for all 3 columns.

To be able to create the indexes as fast as possible, structures (DllStructCreate) are used to create the indexes.

This is the function to create indexes for integers and floating point numbers. The function for strings is equivalent.

$tIndex = DllStructCreate( "uint[" & $iRows & "]" )

Func SortNumbers( ByRef $aItems, $iRows, $iCol, $pIndex, $tIndex )
  Local $k, $n, $lo, $hi, $mi, $gt
  HourglassCursor( True )
  WinSetTitle( $hGui, "", "Virtual ListViews. Sort numbers: 0 rows" )
  For $i = 0 To $iRows / 10000 - 1
    $k = $i * 10000
    For $j = 0 To 9999
      $n = $aItems[$k+$j][$iCol]
      ; Binary search
      $lo = 0
      $hi = $k + $j - 1
      While $lo <= $hi
        $mi = Int( ( $lo + $hi ) / 2 )
        If $n < $aItems[DllStructGetData($tIndex,1,$mi+1)][$iCol] Then
          $gt = 0
          $hi = $mi - 1
        Else
          $gt = 1
          $lo = $mi + 1
        EndIf
      WEnd
      ; Make space for the new value
      DllCall( $hKernel32Dll, "none", "RtlMoveMemory", "struct*", $pIndex+($mi+1)*4, "struct*", $pIndex+$mi*4, "ulong_ptr", ($k+$j-$mi)*4 )
      ; Insert new value
      DllStructSetData( $tIndex, 1, $k+$j, $mi+1+$gt )
    Next
    WinSetTitle( $hGui, "", "Virtual ListViews. Sort numbers: " & $k + 10000 & " rows" )
  Next
  HourglassCursor( False )
  WinSetTitle( $hGui, "", "Virtual ListViews (sorted)" )
EndFunc

Run LvVirtArraySort.au3. It takes some time to create the arrays and indexes. But when everything is created, sorting by different columns and switching from one array to another is instantaneous.

Because it's easy and fast to save/load a structure to/from a binary file, it may be advantageous to calculate the arrays and indexes in another script before the GUI is opened.

 

$LVN_ODFINDITEM notifications (update 2015-04-01)

Three notifications are important for virtual listviews. $LVN_GETDISPINFO (to get information about the rows to display in the listview) and $LVN_ODCACHEHINT (to store rows from a file or database in an array cache before they are displayed with $LVN_GETDISPINFO messages) are already mentioned above. The last is $LVN_ODFINDITEM, which is used to find a row when you press one or a few keys on the keyboard. Information from $LVN_ODFINDITEM is stored in the $tagNMLVFINDITEM structure.

The codebox shows the code for $LVN_ODFINDITEM notifications:

Case $LVN_ODFINDITEMW
  Local $tNMLVFINDITEM = DllStructCreate( $tagNMLVFINDITEM, $lParam )
  If BitAND( DllStructGetData( $tNMLVFINDITEM, "Flags" ), $LVFI_STRING ) Then
    Return SearchText( DllStructGetData( $tNMLVFINDITEM, "Start" ), _                                     ; Start
      DllStructGetData( DllStructCreate( "wchar[20]", DllStructGetData( $tNMLVFINDITEM, "Text" ) ), 1 ) ) ; Text
  EndIf

Start is the row where you start the search. Text contains the key presses to search for. You have to implement the search function (here SearchText) yourself. If the function finds a row, it should return the index of the row. If not, it should return -1.

Run LvVirtArrayFind.au3.

 

Using standard listviews (update 2015-04-01)

If not more than 10,000 rows have to be inserted in a listview, a standard listview is sufficiently rapid. Because of speed you should use native (built-in) functions to fill the listview and not functions in GuiListView.au3 UDF. When the listview is filled, you can use all the functions in the UDF.

This code shows how to quickly fill a listview with native functions:

Func FillListView( $idLV, ByRef $aItems, $iRows )
  Local $tLVITEM = DllStructCreate( $tagLVITEM )
  Local $pLVITEM = DllStructGetPtr( $tLVITEM ), $k, $s
  DllStructSetData( $tLVITEM, "Mask", $LVIF_IMAGE ) ; Icon (or image)
  DllStructSetData( $tLVITEM, "SubItem", 0 )        ; First column
  HourglassCursor( True )
  For $i = 0 To $iRows / 10000 - 1
    $k = $i * 10000
    For $j = 0 To 9999
      ; Text
      $s = $aItems[$k+$j][0]
      For $l = 1 To 9
        $s &= "|" & $aItems[$k+$j][$l]
      Next
      GUICtrlCreateListViewItem( $s, $idLV )        ; Add item and all texts

      ; Icon
      Select
        Case Mod( $k + $j, 3 ) = 0
          DllStructSetData( $tLVITEM, "Image", 2 )  ; Icon index
        Case Mod( $k + $j, 2 ) = 0
          DllStructSetData( $tLVITEM, "Image", 1 )
        Case Else
          DllStructSetData( $tLVITEM, "Image", 0 )
      EndSelect
      DllStructSetData( $tLVITEM, "Item", $k + $j ) ; Row
      GUICtrlSendMsg( $idLV, $LVM_SETITEMW, 0, $pLVITEM ) ; Add icon
    Next
    WinSetTitle( $hGui, "", "GUICtrlCreateListViewItem ListViews. Fills listview: " & $k + 10000 & " rows" )
  Next
  HourglassCursor( False )
  WinSetTitle( $hGui, "", "GUICtrlCreateListViewItem ListViews" )
EndFunc

Run LvStandard.au3.

LvStandardIni.au3 shows how to quickly load an inifile (LvStandardIni.ini, created with IniWriteSection) into a listview. Because an inifile is a small file (only the first 32767 chars are read) it should always be loaded into a standard listview.

 

Updates

Update 2015-03-24

Added two array-examples. An example (LvVirtArrayIcons.au3) that shows how to use checkboxes and icons, and an example (LvVirtArrayColors.au3) that shows how to draw every second row with a different background color.

In this post you can find an example where all items are drawn with a random background color.

Update 2015-04-01

Cleaned up code in previous examples. Added more examples as described above. Zip updated.

 

UDF versions (2018-04-27)

Over the past weeks, new display functions have been added to Data display functions based on virtual listviews, and new functions have been added to use the listviews as embedded GUI controls.

All the functions work and are used in much the same way. Apart from the data source, the function parameters are the same for all functions.

The display functions support a wide range of features, all specified via a single function parameter $aFeatures, which is the last parameter.

The central code to handle $LVN_ODCACHEHINT and $LVN_GETDISPINFO notifications is very optimized code.

First of all, the code is implemented through the subclassing technique. This means that messages are received directly from the operating system and not from AutoIt's internal message management code. Messages are returned again directly to the operating system and again without interference with AutoIt's internal message handling code.

Next, the code is divided into different include files each taking care of a particular feature. That way, it's avoided that a lot of control statements makes the code slow. And it's enough to include the code that's actually used.

One reason why so much work has been done in optimizing code and developing features is that these functions will also work as UDF versions for the examples here.

It's far from a trivial task to develop UDF versions of examples like these. Since the first version of the display functions was created in this thread 2½ years ago and then has been continuously developed, it's obvious to use the functions as UDF versions of these examples.

The following examples are implemented as UDF versions:

• Data stored in arrays
• Data stored in CSV files
• Data stored in SQLite databases

 

Zip file

Examples in zip:

• LvVirtArray.au3 - Data stored in arrays
• LvVirtArrayColors.au3 - Alternating row colors
• LvVirtArrayFind.au3 - $LVN_ODFINDITEM notifications
• LvVirtArrayIcons.au3 - Checkboxes and icons
• LvVirtArraySort.au3 - Sorting rows in a virtual listview
• LvVirtDB.au3 - Data stored in databases (use CreateDB.au3 to create DBs)
• LvVirtFile.au3 - Data stored in fixed-length record files
• LvStandard.au3 - Using standard listviews
• LvStandardIni.au3 - Load inifile into a listview

The size of the zip is caused by a 118 KB txtfile, LvVirtFile.txt, used by LvVirtFile.au3, and a 28 KB inifile, LvStandardIni.ini, used by LvStandardIni.au3.

Tested with AutoIt 3.3.10 on Windows 7 64 bit and Windows XP 32 bit. Should work on all AutoIt versions from 3.3.10 and all Windows versions.

Virtual ListViews.7z

 

Examples

Examples based on virtual listviews.

Array examples:

• A lot of rows and random background colors for each cell - This post in another thread
• Incremental search (update as you type) in a virtual listview - Post 29

Sorting arrays:

• Rows can be sorted by strings, integers, floats and checkboxes, checked rows in top - Post 48

File sources:

• A CSV-file with 100,000 rows and 10 columns is data source - Post 56

SQLite examples:

• Various issues related to the use of a database - Post 34, 35, 43
• An example that shows a way to implement a search box - Post 41

Edited April 27, 2018 by LarsJ
UDF versions

[jcpetu]

Hi LarsJ, I got the following error:

CreateDB.au3" (89) : ==> Subscript used on non-accessible variable.:
If $aRow[0] + 1 = $iRows Then
If $aRow^ ERROR

[LarsJ]

Because SQLite is not installed.

[Terenz]

LarsJ,
Intresting the "Data stored in arrays" but seems not work with the extended style $LVS_EX_CHECKBOXES, one checkbox for row, maybe because we need to draw by ourself. In this cases i think has many drawback ( like not working the function Get-SetItemChecked and the other related ) or i'm wrong and can be added in a easy way?
Thanks

EDIT: A source in PowerBASIC --> %LVS_EX_CHECKBOXES in Virtual Listview control

Edited April 7, 2015 by Terenz

[LarsJ]

Most functions in the GuiListView UDF to maintain data and state information does not work for a virtual listview ($LVS_OWNERDATA), because the information is not stored in the listview. But something that works and works well and fast is custom drawn rows and items (for and back color). See this post.

[Terenz]

That link you posted is always a virtual listview. If you mean to use "NM_CUSTOMDRAW" i'm already using it for coloring the row. But there is many difference of speed between the "real" and the "virtual" one, with the real i need to wait minutes before see the list full loaded ( yes i'm using BeginUpdate/EndUpdate ) for items goes to 20.000 to 60.000 approx. The "virtual" is faster, no doubt on it.

Too bad i can't use the virtual listview with checkbox...

[LarsJ]

Added two array-examples. An example that shows how to use checkboxes and icons, and an example that shows how to draw every second row with a different background color. The listviews are still lightning fast and can handle millions of rows. Zip in first post updated.

[Terenz]

LarsJ,

Very cool. I'm not an expert like you but i have a suggestion for the checkbox. Clicking on the row automatically check-uncheck the chechbox ( this behavor depends by $LVS_EX_FULLROWSELECT )

I think you have to get only the message $LVHT_ONITEMSTATEICON for detect only the click on the checkbox and not on the entire row

I'll appreciate your work, thanks

Edited April 7, 2015 by Terenz

[Terenz]

I'm understanding this virtual listview, the basic thing is not treat this listview like a listview but like an array. For example this is the funtion i'll use for check-uncheck a checkbox

The funtion i'm miss is InsertItem/AddItem, increasing the array is not sufficient for add a new value. There's something I don't get!

Edited April 7, 2015 by Terenz

[LarsJ]

You have to tell the LV that you have added more rows:

 

GUICtrlSendMsg( $idLV, $LVM_SETITEMCOUNT, $iRows, 0 )

$iRows is the new (total) number of rows.

[Terenz]

You have right

Seems _GUICtrlListView_SetColumnWidth with $LVSCW_AUTOSIZE not work, and most badly GUICtrlRegisterListViewSort seems don't have any effect when you click on the colum...For the first there are some solution ( like use LVM_GETSTRINGWIDTHW? ) but for custom sort i don't have found nothing. Do you know why?

EDIT: Why you truncate any string over the 50 character?

Local Static $tText = DllStructCreate("wchar[50]")

I have just notice it, if a string is longer then 50 char it will show truncated. How to set to indefinite? Or i just need to put an higher value like 100,200?

Edited April 7, 2015 by Terenz

[LarsJ]

Sorting is not supported.

[Terenz]

What about the question about DllStructCreate("wchar[50]")?

[LarsJ]

You just set the width to match the length of your strings.

[KLM]

Thanks. Waiting for sorting. Example using ini file ( sql independent example ) ? ????

[LarsJ]

I'll see what I can do. You have to be patient for a few days.

[LarsJ]

I have added some more examples:

• Data stored in fixed-length record files.

  An example where $LVN_ODCACHEHINT messages are used to extract data directly from a fixed-length record file into an array cache by setting the file pointer to the current record and reading the required number of bytes.

• Sorting rows in a virtual listview.
• $LVN_ODFINDITEM notifications.

  Used to find a row when you press one or a few keys on the keyboard.

• Using standard listviews.

  If not more than 10,000 rows have to be inserted in a listview, a standard listview should be used. An example shows how you can quickly fill a listview with native commands. Another example shows how you can quickly fill a listview from an inifile.

More information and new zip in first post.

[KLM]

Thanks for replying.

Thanks for the ini example.

Can you please share how to get Window 7 Explorer ListView Details such as columns & rows data ? ( folder details ) USING WINAPI

Where is syslistview32 class in win 7 explorer ?

Edited April 3, 2015 by KLM

[LarsJ]

There is no SysListView32 control in Windows Explorer on Vista and later. Instead of there is a DirectUIHWND control, which is a virtual listview like in this example. Because it's a virtual listview it only contains information about the files and folders which are visible. There is no easy way to get all files and folders in the current folder.

Fortunately, there is an Automating Windows Explorer UDF, that can extract the information you are looking for. Take a look at the examples in post 7.

If there isn't an example that fits on the information you need, please let me know. It should not be too hard to add more examples.

[KLM]

Thanks. I'll try it.