How to make a virtual tree control — really virtual

How to Make CTreeCtrl Virtual

Here is the problem: You have a bunch of data which naturally come in a tree structure — but the entire tree is large, cumbersome, and/or expensive to generate, and naturally, only one or a few leaf elements of the tree will eventually be needed.

There are virtual list controls where one list can have millions of entries and is still fast, because the elements are only requested by Windows if they get actually displayed.

In my search for a virtual tree control, I stumbled upon this discussion,

The problem is: It isn’t quite as easy as that.

In a virtual list control, you tell Windows: “Ask me about the text of line X when you actually need to display it”. This way, list controls which display very long lists can still be very fast, and can defer creating the content of those lists until the point when asked for it.

In a tree control, it’s not quite the same. A list has only one dimension, its length. A tree has two dimensions in which it can be “large”, a width, and a depth.

Let’s deal with the depth first:

Imagine your tree is very deep, and creating every entry at every depth is going to be expensive. You only want to create those entries which actually are requested. Tree items may start out collapsed, and the user first has to expand them. This happens in user time, and it would therefore be ideal to only then create the data on only the depth level that’s expanded, saving on generating the whole tree at once.

When you insert an item in a tree, you specify the cChildren member of a HTREEITEM to tell how many children the item will have. You can specify 0 (for no children), 1( for some children), but for a virtual tree control, you don’t know that yet when you call InsertItem or SetItem. There, you specify I_CHILDRENCALLBACK to be called when the number of children is requested — actually, I_CHILDRENCALLBACK is -1.

Then, you have to supply a callback method to be called back for the item. That pretty much happens the same way as for a list control:

BEGIN_MESSAGE_MAP(CMyTree, CTreeCtrl)
    ON_NOTIFY_REFLECT(TVN_GETINFOTIP, &CMyTree::OnGetDispInfo)
END_MESSAGE_MAP()

...

void CMyTree::GetDispInfo(NMHDR* pNMHDR, LRESULT* pResult)
{
    NMTVDISPINFO *pDispInfo = reinterpret_cast<NMTVDISPINFO*>(pNMHDR);
    TVITEM* pItem = &(pDispInfo)->item;
...
}

or, if you don’t want to derive from CTreeCtrl, you can catch the message in the containing dialog or window:

BEGIN_MESSAGE_MAP(CMyTreeContainingDialog, CDialog)
    ON_NOTIFY(TVN_GETDISPINFO, IDC_MYTREE, &CMyTreeContainingDialog::OnGetDispInfoMyTree)
END_MESSAGE_MAP()

In the handler, you determine the number of children:

void CMyTreeContainingDialog::OnGetDispInfoMyTree(NMHDR *pNMHDR, LRESULT *pResult)
{
    NMTVDISPINFO *pDispInfo = reinterpret_cast<NMTVDISPINFO*>(pNMHDR);
    TVITEM* pItem = &(pDispInfo)->item;

    if ( pItem->mask & TVIF_CHILDREN )
    {
    	pItem->cChildren = GetMyItemNumChildren( pItem->hItem ) > 0 ? 1 : 0 ;
    }
}

What if you only actually want to create those children when required? If the tree is very wide, an item may have a lot of child items. These may not all be not currently visible in the control, and the user first has to scroll down or up to see them. Again, you want to defer the time of creating an item until that actually happens.

In this pseudocode, at the time when Windows requests the number of children of an item via TVN_GETDISPINFO, you only specify the number of children, you don’t actually create them yet. But you have to make sure they are there when the item is actually expanded. That is, between the occurrence of this TVN_GETDISPINFO message and the actual expansion of the tree, you need to insert these child items. For example, you could call InsertItem(…) right here, in the TVN_GETDISPINFO handler call that gets the number of children.

But note that the item doesn’t actually have to be expanded for this information to be requested; if the tree control has the TVS_HASBUTTONS style (and the TVS_LINESATROOT style), items with children have a “+” next to them, so Windows will ask you about the presence of children already when it displays the parent item, which may never get expanded. And if child creation is slow, you want to delay it as long as possible, anyway.

For that, you use the TVN_ITEMEXPANDING notification:

    ON_NOTIFY(TVN_ITEMEXPANDING, IDC_MYTREE, &CMyTreeContainingDialog::OnMyTreeItemExpanding)

The itemNew member of the NMTREEVIEW passed to the handler contains the info about the item that should be expanded:

void CMyTreeContainingDialog::OnMyTreeItemExpanding(NMHDR *pNMHDR, LRESULT *pResult)
{
    NMTREEVIEW *pNMTreeView = (NMTREEVIEW*)pNMHDR;
    *pResult = 0;

    if ( (pNMTreeView->action & TVE_EXPAND) != TVE_EXPAND )
    {
        return ;
    }

    /* now create the children */
    if ( GetMyItemNumChildren( pNMTreeView->itemNew.hItem ) > 0 )
    {
        if ( /* my child items are not yet created */ )
        {
    	   for ( /* creation of each of my child items */ )
    	   {
    	      e.g.
    	      myTree.InsertItem( myCreateditem.GetText() , pNMTreeView->itemNew.hItem ) ;
       	   }
           /* remember that we created all these items alredy */ ;
        }
    }
}

So now, what if the tree is very wide, i.e. there are a lot of entries on one level:?

Instead of directly inserting the item as above, you specify that its text and image (and its own children) should be retrieved later:

    	for ( /* creation of each of my child items */ )
    	{
	    TVINSERTSTRUCT tvs = {0};

	    tvs.item.mask = TVIF_TEXT|TVIF_IMAGE|TVIF_SELECTEDIMAGE|TVIF_CHILDREN|TVS_LPARAM;

	    tvs.item.pszText = LPSTR_TEXTCALLBACK ;
	    tvs.item.iImage = I_IMAGECALLBACK ;
	    tvs.item.iSelectedImage = I_IMAGECALLBACK ;
	    tvs.item.cChildren = I_CHILDRENCALLBACK;
	    tvs.item.lParam = /* whatever I need to identify this item and generate its contents later */ ;

	    tvs.hParent = pNMTreeView->itemNew.hItem;
	    tvs.hInsertAfter = TVI_LAST;
    	    myTree.InsertItem( &tvs ) ;
    	}

Then in the TVN_GETDISPINFO handler, you specify the text and the image, in addition to the children

void CMyTreeContainingDialog::OnGetDispInfoMyTree(NMHDR *pNMHDR, LRESULT *pResult)
{
    NMTVDISPINFO *pDispInfo = reinterpret_cast<NMTVDISPINFO*>(pNMHDR);
    TVITEM* pItem = &(pDispInfo)->item;

    if ( pItem->mask & TVIF_TEXT )
    {
        lstrcpyn(pItem->pszText, myTreeItemText(pItem->hItem), pItem->cchTextMax);
    }

    if ( pItem->mask & TVIF_IMAGE )
    {
            pItem->iImage = myTreeItemImage( pItem->hItem );
    }
    if ( pItem->mask & TVIF_SELECTEDIMAGE )
    {
            pItem->iSelectedImage = myTreeItemSelectedImage( pItem->hItem );
    }
    if ( pItem->mask & TVIF_CHILDREN )
    {
    	pItem->cChildren = GetMyItemNumChildren( pItem->hItem ) > 0 ? 1 : 0 ;
    }
}

This way, the tree control items will only be filled on demand.

“On Demand” can be when the user expands an item so the topmost items of the level below become visible; when he/she scrolls to an item in the list; but also when he/she types a character (or several). The tree control will want to scroll to the first entry starting with that character (or combination of characters) and will request all items until it finds one that does (or the first one later in the alphabet).

In particular, if you don’t use I_CHILDRENCALLBACK, Windows will request all child items at once when opening an item, even if not all child items are actually visible, making the “virtual” property only half as effective.

Good luck!

More by Author

Get the Free Newsletter!

Subscribe to Developer Insider for top news, trends & analysis

Must Read