Click here to Skip to main content
15,609,135 members
Articles / Desktop Programming / MFC
Posted 18 Aug 2001


82 bookmarked

A Faster Tree Control

Rate me:
Please Sign up or sign in to vote.
4.69/5 (13 votes)
16 Dec 2003CPOL5 min read
An article about an open source and free fast tree control

Sample Image - RGTree.gif


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
   // Construction / Destruction

   // 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);

   // 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);

   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. I've implemented some small functions directly, the others exist as standalone 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:

   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
   CItemRectCache(HWND hWnd);
   void SetItem( RGTVITEM* pItem);
   int GetItemTextWidth();
   SIZE GetStateImageSize(TREE_MAP_STRUCT *ptms);
   SIZE GetNormalImageSizeAndOffset(TREE_MAP_STRUCT *ptms);
   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
    • 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 your tree control from CRGTree.


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

change all CTreeCtrl mentions like...

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

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


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

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

If you're interested in joining 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()
15 Apr 2002
  • Edit and scroll timers using GetDoubleClickTime()
  • Drag and drop support
  • IsBeforeFirstVisibleItem()
23 May 2002
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
  • Expand() in SetItem() without notify
  • GetNextItem(NULL) and similarly 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.


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Written By
Software Developer (Senior)
Slovakia Slovakia
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Written By
Software Developer
Germany Germany
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

QuestionLicense type Pin
alex viptov23-Feb-12 22:09
alex viptov23-Feb-12 22:09 
AnswerRe: License type Pin
Tibor Blazko23-Feb-12 22:49
Tibor Blazko23-Feb-12 22:49 
AnswerRe: License type Pin
René Greiner25-Feb-12 6:56
René Greiner25-Feb-12 6:56 
GeneralRe: License type Pin
alex viptov27-Feb-12 0:05
alex viptov27-Feb-12 0:05 
Tibor Blazko27-Feb-12 0:28
Tibor Blazko27-Feb-12 0:28 
QuestionIs LPSTR_TEXTCALLBACK supported in InsertItem? Pin
alex viptov27-Dec-11 2:11
alex viptov27-Dec-11 2:11 
AnswerRe: Is LPSTR_TEXTCALLBACK supported in InsertItem? Pin
Tibor Blazko27-Dec-11 2:39
Tibor Blazko27-Dec-11 2:39 
GeneralAdding check box... Pin
kim7810252-Mar-10 3:15
kim7810252-Mar-10 3:15 
GeneralRe: Adding check box... Pin
Tibor Blazko2-Mar-10 3:32
Tibor Blazko2-Mar-10 3:32 
GeneralRe: Adding check box... Pin
kim78102526-Apr-10 19:01
kim78102526-Apr-10 19:01 
GeneralRe: Adding check box... Pin
Tibor Blazko26-Apr-10 19:55
Tibor Blazko26-Apr-10 19:55 
GeneralRe: Adding check box... Pin
kim78102526-Apr-10 20:16
kim78102526-Apr-10 20:16 
GeneralAbout a problem of memory Pin
kim78102523-Feb-10 22:34
kim78102523-Feb-10 22:34 
GeneralRe: About a problem of memory Pin
Tibor Blazko23-Feb-10 22:43
Tibor Blazko23-Feb-10 22:43 
GeneralI have a better solution for fast addition Pin
rm82212-Jan-07 4:33
rm82212-Jan-07 4:33 
GeneralRighttree Scroll Problem Pin
Z.L. Dong11-Apr-06 22:09
Z.L. Dong11-Apr-06 22:09 
GeneralRe: Righttree Scroll Problem Pin
Tibor Blazko11-Apr-06 23:49
Tibor Blazko11-Apr-06 23:49 
GeneralUsing with MFC Statically Linked Pin
JStanford25-Jan-06 8:47
JStanford25-Jan-06 8:47 
GeneralRe: Using with MFC Statically Linked Pin
Tibor Blazko11-Apr-06 23:45
Tibor Blazko11-Apr-06 23:45 
QuestionLatest version available ? Pin
Defenestration4-Aug-05 15:48
Defenestration4-Aug-05 15:48 
AnswerRe: Latest version available ? Pin
Tibor Blazko4-Aug-05 19:16
Tibor Blazko4-Aug-05 19:16 
GeneralUnable to build on VS 2003 Pin
totem1624-Mar-05 16:28
totem1624-Mar-05 16:28 
GeneralRe: Unable to build on VS 2003 Pin
Tibor Blazko28-Mar-05 18:25
Tibor Blazko28-Mar-05 18:25 
GeneralScrollbar problem with large amount of items solved!!! Pin
Alexey Markov4-Feb-04 20:07
Alexey Markov4-Feb-04 20:07 
GeneralRe: Scrollbar problem with large amount of items solved!!! Pin
Tibor Blazko4-Feb-04 21:55
Tibor Blazko4-Feb-04 21:55 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.