Virtualizing List Views to Handle Large Amounts of Data

In a project I have recently undertook, a window was needed where it was
neccessary to display large amounts of data (over 150,000 items) in a single
CListCtrl. Futhermore, a second and even third window was needed, each with
their own CListCtrl. These additional windows worked off the same data
source as the first window, displaying different views or other alternate
information.

The technique I use is made possible with the LVS_OWNERDATA style. Basically
what that style does, is tell the CListCtrl that we are in charge of all
memory handling. You never call CListCtrl::InsertItem() when this style is
set. Everytime the control needs to paint or display text, Windows will ask
you for the text located at item, subitem (in the form of a LVN_GETDISPINFO
message). It is then your job to supply this information.

An example of this:


BEGIN_MESSAGE_MAP(CMyListCtrl, CListCtrl)
//{{AFX_MSG_MAP(CMyListCtrl)
ON_NOTIFY_REFLECT(LVN_GETDISPINFO, OnGetdispinfo)
//}}AFX_MSG_MAP
END_MESSAGE_MAP()

//Windows is asking for the text to display,
//at item(iItemIndex), subitem(pItem->iSubItem)
void CMyListCtrl::OnGetdispinfo(NMHDR* pNMHDR, LRESULT* pResult)
{
LV_DISPINFO* pDispInfo = (LV_DISPINFO*)pNMHDR;
LV_ITEM* pItem= &(pDispInfo)->item;
int iItemIndex= pItem->iItem;

if(pItem->mask & LVIF_TEXT)
{
if(pItem->iSubItem == 0) //first column
lstrcpyn(pItem->pszText,
“This is the first columns data”,
pItem->cchTextMax);
else
if(pItem->iSubItem == 1) //second column
lstrcpyn(pItem->pszText,
“Second column data”,
pItem->cchTextMax);
}
*pResult = 0;
}

In the project I described earlier, I have a single linked list, with
hundreds of thousands of elements in it. I have three different windows,
each displaying different information about the data within this massive
linked list, each in its own particular sorting order. I knew right away I
didn’t want to call InsertItem() and DeleteItem() hundreds of thousands of
times, each time the user wanted to sort. And I definitely wasn’t about to
sort this entire linked list, or make duplicate copies for the other
windows. So the technique I decided on was to simply have each CListCtrl
object maintain its own dynamic array of pointers within this linked list.
Everytime a new node is added to the linked list, I pass a pointer of the
newly created node to the CListCtrl object, which stores the pointer in its
array. I then simply call CListCtrl::SetItemCount(new_count);, which forces
a redraw of the control. No new memory is allocated (unless the array needs
to grow), and there is no delay at all from inserting the item. If many
nodes are created at the same time (as is done with this example), then I
pass them all to the view in one function call, so only a single screen
update is needed.

This technique has several advantages. The first being that I can now easily
have many CListCtrls working off the same data source, maintaining their own
personal sort order, while minimizing the amount of memory required. Sorting
is a snap: simply call the ANSI C function qsort() passing in the address of
your array, along with your own compare function. After qsort() completes,
call CListCtrl::SetItemCount(current_count) to redisplay the data. Done!

Another advantage is pure, raw speed. In the example code provided, I tested
the window with 1,000,000 items in it, and it displays and scrolls in real
time. It will scroll as fast as you can drag the mouse down. The only delay
you will notice is the time spent to initially allocate and create a linked
list with 1,000,000 elements in it. Of course that is only done once, and if
your linked list is already created, with this technique you could create
and display a CListCtrl object with well over 1,000,000 elements in less
than a second! Sorting is also faster, as the only memory being moved around
are the tiny 4byte pointers being stored in the array.

Downloads

Download demo project source code – 25 Kb

Download demo application (sans source) – 37 Kb

More by Author

Must Read