A faster tree control

Download demo project - 44.1 Kb

Sample Image - RGTree.gif

Introduction

I'm writing an application for exploring the registry. Therefore I need the tree control. First I used InsertItem directly with the registry keys. Inserting an item in the SysTree is fast enough but deleting the items is very slow. I used optimizations described in Tibors article, but it wouldn't be much faster. Then I used text callback items, but the same.

For example: Adding about 50000 registry keys to system tree control needs about 6 sec, deleting these items needs about 22 sec (!) on my Thunderbird 1200.

Because each quick tree control I've found I must pay for and the free controls I've found aren't faster than the standard tree control, I decided to write my own. The tree control should work like the system tree control.

The control internally

The control data storage is based on the template CRGTreeT<_ITEMDATA>. It's an object implementing a bi-directional linked list of elements, each containing a member of type ITEMDATA.

template<class _ITEMDATA> class CRGTreeT
{
 public:
   // Construction / Destruction
   CRGTreeT();
   ~CRGTreeT();

   // returns the count of all items
   UINT GetItemCount() const;
   // returns the count of all child items
   UINT GetChildCount( /*[in]*/ POSITION posParent) const;
   // returns the root
   POSITION GetRootPosition() const;

   // returns the parent of an item
   POSITION GetParentPosition( /*[in]*/ POSITION pos) const;

   // adds an items at the begin of the list
   POSITION AddHead( /*[in]*/ const _ITEMDATA *pItemData, 
                     /*[in]*/ POSITION posParent=NULL);
   // adds an items at the end of the list
   POSITION AddTail( /*[in]*/ const _ITEMDATA *pItemData, 
                     /*[in]*/ POSITION posParent=NULL);

   POSITION InsertAfter( /*[in]*/ const _ITEMDATA *pItemData, 
                         POSITION posParent=NULL, 
                         /*[in]*/POSITION posAfter=NULL);
   // Remove the item at position pos including all subitems
   void RemoveAt( /*[in]*/ POSITION pos);
   // Removes all items
   void RemoveAll();

   // returns the first/last child item of the item at position posParent
   POSITION GetChildPosition( /*[in]*/ POSITION posParent, 
                              /*[in]*/ BOOL bFirst=TRUE) const;
   // returns the next list element, NULL if none
   POSITION GetNextPosition( /*[in]*/ POSITION pos) const;

   // returns the previous element, NULL if none
   POSITION GetPrevPosition( /*[in]*/ POSITION pos) const    

   // returning a copy of the ITEMDATA at position pos
   void GetAt( /*[in]*/ POSITION pos, /*[out]*/ _ITEMDATA* pItemData) const;
   // Returning a pointer to the ITEMDATA at position pos
   _ITEMDATA* GetAt( /*[in]*/ POSITION pos);
   // replace the ITEMDATA at position pos
   void SetAt( /*[in]*/ POSITION pos, /*[in]*/ const _ITEMDATA* pItemData);

   // sort childrens of the item at position posParent
   BOOL SortChildren( /*[in]*/ POSITION posParent, 
                      /*[in]*/ BOOL bAscending=TRUE);
   // search for an item based on the compare function
   POSITION Find( /*[in]*/ const _ITEMDATA *pItemData, 
                  /*[in]*/ POSITION posParent);

   // setting a callback function for sorting and finding items
   CompareFunc SetCompareFunc( /*[in]*/ CompareFunc func);
   DeleteFunc SetDeleteFunc( /*[in]*/ DeleteFunc func, LPARAM lParam);

protected:
   // remove all childs from an item
   void RemoveChilds( POSITION pos);

   // quick sort algorithms for sorting up- or downwards
   void QSortA( /*[in]*/ CTreeItem **pLow, /*[in]*/ CTreeItem **pHigh);
   void QSortD( /*[in]*/ CTreeItem **pLow, /*[in]*/ CTreeItem **pHigh);

private:
   CTreeItem      m_ItemRoot;
   UINT           m_nCount;
   CompareFunc    m_pCompareFunc;
   DeleteFunc     m_pDeleteFunc;
   LPARAM         m_lParamDeleteFunc;
};

The messages will be processed in its own window procedure. Some small functions I've implemented directly, the others exists as stand alone functions with the following form

LRESULT On[MessageName]( HWND hwnd, TREE_MAP_STRUCT *ptms, 
                         WPARAM wParam, LPARAM lParam)

There is a data structure holding the characteristics for each tree HWND:

struct TREE_MAP_STRUCT
{
   HWND         hwnd;                  // the handle of the control
   HWND         hWndEdit;              // the handle of the controls 
                                       //   edit window
   WNDPROC      pOldWndProc;           // the old window procedure
   int          nItemCount;            // all items inserted
   int          nMaxWidth;             // max width of the control
   int          nVScrollPos;           // vertical scroll position
   int          nHScrollPos;           // horizontal scroll position
   HTREEITEM    hItemFirstVisible;     // items ...
   HTREEITEM    hItemSelected; 
   HTREEITEM    hItemEditing;
   HTREEITEM    hItemClicked;
   HIMAGELIST   hNormalImageList;      // image list
   HIMAGELIST   hStateImageList;
   bool         bRedrawFlag;           // should the control be redrawed 
                                       //   on each inserting/erasing
   _rgTree      rgTree;                // the CRGTreeT template
};

For faster calculating of the item widths Tibor has written class holding repeatable used objects, especially the HDC and the HFONTs. You can cache their creation by SetRedraw() calls.

Next optimization is used in the internal GetItemVisibleIndex(). With many items it tries to find the items near the first visible one.

class CItemRectCache
{
public:
   CItemRectCache(HWND hWnd);
   ~CItemRectCache();
   void SetItem( RGTVITEM* pItem);
   int GetItemTextWidth();
   SIZE GetStateImageSize(TREE_MAP_STRUCT *ptms);
   SIZE GetNormalImageSizeAndOffset(TREE_MAP_STRUCT *ptms);
protected:
   bool         m_bHasLinesAtRoot;
   bool         m_bStateImageSizeInitialized;
   SIZE         m_StateImageSize;
   bool         m_bNormalImageSizeInitialized;
   SIZE         m_NormalImageSize;
   HWND         m_hWnd;
   HDC          m_hDC;
   HGDIOBJ      m_hFont;
   HGDIOBJ      m_hBoldFont;
   HGDIOBJ      m_hOldFont;
   bool         m_bBoldSelected;
   RGTVITEM*    m_pItemSet;
}

Known to-dos and limitations

Full(er) TreeCtrl functionality. At the moment we have only implemented cases interesting for us. The main missing cases are:
- Custom drawing
- TVM_INSERTITEM with TVI_SORT
- TVM_SETSCROLLTIME
- Tooltip support
- Infotips
- Keyboard notification and incremental search
Slower sorting because the quicksort algorithm is used and an array of all items to sort must be built and after sorting the previous/next position of an item must be updated
More straight code without duplicities and not commented parts
More 1:1 implementation

Are cases when hItemFirstVisible after Expand call is not the same like in system tree.
Edit control size and position depending on horizontal scrollbar position.

More and more intelligent done user interface optimization
- Can be sometimes more redraws than necessary.
- More searches can be optimized (see __GetItemVisibleIndex call in SetItem).
- See bInSetScrollBars usage as horror example.
Absolutely correct code
- Now change of item's TVIS_BOLD state not recomputes horizontal scrollbar.
- Directly defined ID_EDIT can conflict with your dialog control id (?).
With SetRedraw(false) before InsertItem()/TVIF_TEXT system tree returns item's rectangle with 0-widthed text, rgtree with computed size. System tree needs explicit SetItemText() or SetRedraw(true) before GetItemRect(... , true).

The demo project

I've written a demo project comparing the speed of the CRGTreeCtrl with the standard tree control. It measures the time for inserting, sorting and deleting items.

At first you must build RGTree than TreeDlg configuration.

We spent some time searching why the release version is slower than debug in DeleteAllItems(). You will not believe it was in the delete[] pItemData->pszText call. The funny thing is all is ok when you do not run it from developer studio (why did we not find it sooner?).

How to use in your project

If you want to use it build (release) RGTree.dll. This will produce import library RGTree.lib. Include it into Project\Settings\Link\General\Object/Library modules. Derive you tree control from CRGTree

CYourTreeCtrl.h

#include "RGTreeCtrl.h"
class CYourTreeCtrl : public CRGTreeCtrl

change all CTreeCtrl mentions like

BEGIN_MESSAGE_MAP(CYourTreeCtrl, CTreeCtrl)

to CRGTreeCtrl into CYourTreeCtrl.* and rebuild. Do not forget call SetRedraw() before and after big tree data changes.

If you will create own project for tree sources do not forget define RGTREECTRL_EXPORTS there.

Finally

Generally the control is usable. Especially inserting/deleting many items is faster comparing to the system one.

If you find corrections, improvements or add functionality let know to update this article. At first we are interested for bugs (with defined situations) and absolutely the best (you are programmers) with possible solutions.

If you're interested to join us and you don't have problems reading the sources, you're very welcome. Please contact us before your changes to avoid duplicate development.

Update history

InvalidateItemRect() calls GetItemRect() with FALSE
OnGetItem()/TVIF_TEXT fix
HitTest() knows TVHT_TOLEFT and similar flags
WM_MOUSEWHEEL handler

25 Jan 2002:

InsertItem_UpdateVScrollPos()
HitTest() vs horizontal scroll

2 Mar 2002:

SetTVITEMforNotify()
DoScroll()
GetNextItem()/TVGN_LASTVISIBLE

15 Apr 2002:

edit and scroll timers using GetDoubleClickTime()
TVS_FULLROWSELECT works without TVS_HASLINES only
drag and drop support
IsBeforeFirstVisibleItem()

23 May 2002:

TVE_COLLAPSE fix

7 Aug 2002:

NM_RCLICK thanks to Doug Garno
I_IMAGECALLBACK thanks to Doug Garno
DeleteObject(hBrush) into OnPaint()
SetItem() with image change cases

12 Sep 2002:

WM_CONTEXTMENU vs NM_RCLICK's return
Expand() in SetItem() without notify
GetNextItem(NULL) and similars newly will return NULL and not crash
MessageBeep() for not handled events to OnKeyDown()
two TVGN_DROPHILITE items - second one for "pressed" state (but pressed rgtree still enables by-tab switching)
nmtv.itemNew corrected to nmtv.itemOld in TVN_DELETEITEM thanks to Doug Garno
(mask | TVIS) corrected to (mask & TVIS) in SetTVITEMforNotify() thanks to Doug Garno

13 Sep 2002:

GetChildItem(NULL) returns root item and not NULL thanks to Doug Garno

9 Dec 2002:

no WM_CHAR beeps in editing thanks to Doug Garno
EndEditLabelNow() sends one TVN_ENDLABELEDIT only thanks to Doug Garno
SetTVITEMforNotify() into OnEditLabel() uses lParam instead of ptms->hItemEditing thanks to Doug Garno
font handling made more straight

28 Mar 2003:

better (but still not 1:1) MessageBeep() for not handled events to OnKeyDown() - see article comment
hBoldFont into OnPaint() at request only and derived from WM_GETFONT not hOldFont

17 Dec 2003:

fixed scrolling problems when inserting items to zero-sized window (_ScrollAbsolutelyDownWhenRequired)
new cases into OnKeyDown() thanks to Doug Garno

Please search article comments for actual code updates too.